1 files changed, 126 insertions, 0 deletions
diff --git a/lib/includes/hicn/util/slab.h b/lib/includes/hicn/util/slab.h
new file mode 100644
index 000000000..2c6546add
--- /dev/null
+++ b/lib/includes/hicn/util/slab.h
@@ -0,0 +1,126 @@
+/*
+ * Copyright (c) 2022 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * @brief The slab is used to store elements of the same size.
+ *
+ * The slab contains blocks of contiguous memory. Each block contains multiple
+ * chunks. An element is stored inside a chunk and the chunk has a header with
+ * a pointer to the block it belongs to.
+ *
+ * Blocks are stored in two doubly-linked lists: 'full' for blocks that
+ * are already full, 'partial_or_empty' for blocks with available chunks. When
+ * a block becomes full it is moved into the 'full' list and vice versa.
+ *
+ * When allocationg an element, a block is taken from the 'partial_or_empty'
+ * list if such list is not empty. If empty, a new block of contiguous memory
+ * is created and put in the 'partial_or_empty' list. Then, a chunk is taken
+ * from the block. When releasing an element, the block it belongs to is
+ * retrieved from the chunk header and used to release the chunk.
+ *
+ * Blocks are created with increasing capacity (i.e. number of chunks they
+ * contain) such that every new block allocaion doubles the total number of
+ * chunks stored in the slab.
+ */
+
+#ifndef UTIL_SLAB_H
+#define UTIL_SLAB_H
+
+#include <stddef.h>
+
+#define SLAB_INIT_SIZE 32
+
+/* CHUNK */
+
+typedef struct block_s block_t;
+typedef struct
+{
+  block_t *block; // Pointer to the block that contains the chunk
+} chunk_hdr_t;
+
+#define CHUNK_HDRLEN	 SIZEOF_ALIGNED (chunk_hdr_t)
+#define chunk_hdr(chunk) ((chunk_hdr_t *) ((uint8_t *) (chunk) -CHUNK_HDRLEN))
+
+/* BLOCK */
+
+struct block_s
+{
+  void *pool;
+  block_t *prev;
+  block_t *next;
+};
+
+/* SLAB */
+
+typedef struct
+{
+  size_t num_chunks; // Total number of chunks (from all blocks) currently
+		     // stored in the slab
+  size_t chunk_size;
+  block_t *full;
+  block_t *partial_or_empty;
+} slab_t;
+
+/* Internal API */
+
+slab_t *_slab_create (size_t elt_size, size_t num_elts);
+void *_slab_get (slab_t *slab);
+void _slab_put (slab_t *slab, void *elt);
+
+/* Public API */
+
+/**
+ * @brief Create a slab able to store elements of type 'TYPE'.
+ *
+ * @param[in] TYPE Type of the elements to store in the slab.
+ * @param[in] SIZE Initial size of the slab, i.e. size of the initial block.
+ * @return slab_t* The slab created, NULL if error.
+ */
+#define slab_create(TYPE, SIZE) _slab_create (sizeof (TYPE), SIZE)
+
+/**
+ * @brief Free a slab.
+ *
+ * @param[in] slab Slab to free.
+ */
+void slab_free (slab_t *slab);
+
+/**
+ * @brief Get an element from the slab.
+ *
+ * @param[in] TYPE Type of the elements stored in the slab.
+ * @param[in] SLAB Slab to take the element from.
+ * @return TYPE* Element retrieved from the slab
+ */
+#define slab_get(TYPE, SLAB) (TYPE *) _slab_get (SLAB)
+
+/**
+ * @brief Same as 'slab_get' but with a different signature, to avoid passing
+ * the type that is instead inferred from the element.
+ *
+ * @param[in] SLAB Slab to take the element from.
+ * @param[in, out] ELT Element retrieved from the slab.
+ */
+#define slab_get2(SLAB, ELT) ELT = (typeof (*(ELT)) *) _slab_get (SLAB)
+
+/**
+ * @brief Put an element back into the slab.
+ *
+ * @param[in] SLAB Slab to return the element to.
+ * @param[in] ELT Element to put in the slab.
+ */
+#define slab_put(SLAB, ELT) _slab_put (SLAB, (void *) ELT)
+
+#endif /* UTIL_SLAB_H */