1 files changed, 327 insertions, 0 deletions
diff --git a/hicn-light/src/hicn/base/vector.h b/hicn-light/src/hicn/base/vector.h
new file mode 100644
index 000000000..0b7a74aeb
--- /dev/null
+++ b/hicn-light/src/hicn/base/vector.h
@@ -0,0 +1,327 @@
+/*
+ * Copyright (c) 2021 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.
+ */
+
+/**
+ * \file vector.h
+ * \brief Resizeable static array
+ *
+ * A vector is a resizeable area of contiguous memory that contains elements of
+ * fixed size. It is mostly useful to serve as the basis for more advanced data
+ * structures such as memory pools.
+ *
+ * The internal API manipulates a pointer to the vector so that it can be
+ * seamlessly resized, and a more convenient user interface is provided through
+ * macros.
+ *
+ * A vector starts at index 0, and is typed according to the elements it
+ * contains. For that matter, the data structure header precedes the returned
+ * pointer which corresponds to the storage area.
+ *
+ * A vector is by default used as a stack where an end marker is maintained and
+ * new elements are pushed right after this end marker (an indication of
+ * the size of the vector) after ensuring the vector is sufficiently large.
+ *
+ * A user should not store any pointer to vector elements as this might change
+ * during reallocations, but should use indices instead.
+ *
+ * NOTE: a maximum size is currently not implemented.
+ *
+ * It is freely inspired (and simplified) from the VPP infra infrastructure
+ * library.
+ */
+
+#ifndef UTIL_VECTOR_H
+#define UTIL_VECTOR_H
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+#include <sys/types.h>
+
+#include "common.h"
+
+/******************************************************************************/
+/* Vector header */
+
+typedef struct {
+  size_t cur_size;   /** Vector current size (corresponding to the highest used
+                        element). */
+  size_t alloc_size; /** The currently allocated size. */
+  size_t max_size;   /** The maximum allowed size (0 = no limit) */
+} vector_hdr_t;
+
+/* Make sure elements following the header are aligned */
+#define VECTOR_HDRLEN SIZEOF_ALIGNED(vector_hdr_t)
+
+/* This header actually prepends the actual content of the vector */
+#define vector_hdr(vector) ((vector_hdr_t *)((uint8_t *)vector - VECTOR_HDRLEN))
+
+/******************************************************************************/
+/* Helpers */
+
+/** Local variable naming macro. */
+#define _vector_var(v) _vector_##v
+
+/**
+ * @brief Allocate and initialize a vector data structure (helper function).
+ *
+ * @param[in,out] vector_ptr Vector to allocate and initialize.
+ * @param[in] elt_size Size of a vector element.
+ * @param[in] init_size Initial vector size.
+ * @param[in] max_size Maximum vector size (O = unlimited).
+ */
+void _vector_init(void **vector_ptr, size_t elt_size, size_t init_size,
+                  size_t max_size);
+
+/**
+ * @brief Free a vector data structure.
+ *
+ * @param vector_ptr[in] Pointer to the vector data structure to free.
+ */
+void _vector_free(void **vector_ptr);
+
+/**
+ * @brief Resize a vector data structure.
+ *
+ * @param[in] vector_ptr A pointer to the vector data structure to resize.
+ * @param[in] elt_size The size of a vector element.
+ * @param[in] pos The position at which the vector should be able to hold an
+ * element.
+ *
+ * @return int Flag indicating whether the vector has been correctly resized.
+ *
+ * NOTE:
+ *  - The resize operation does not specify the final size of the vector but
+ * instead ensure that it is large enough to hold an element at the specified
+ * position. This allows the caller not to care about doing successive calls to
+ * this API while the vector is growing in size.
+ */
+int _vector_resize(void **vector_ptr, size_t elt_size, off_t pos);
+
+/**
+ * @brief Ensures a vector is sufficiently large to hold an element at the
+ * given position.
+ *
+ * @param[in] vector_ptr A pointer to the vector data structure to resize.
+ * @param[in] elt_size The size of a vector element.
+ * @param[in] pos The position to validate.
+ *
+ * @return int Flag indicating whether the vector is available.
+ *
+ * NOTE:
+ *  - This function should always be called before writing to a vector element
+ *  to eventually make room for it (the vector will eventually be resized).
+ *  - This function can fail if the vector is full and for any reason it cannot
+ *  be resized.
+ */
+static inline int _vector_ensure_pos(void **vector_ptr, size_t elt_size,
+                                     off_t pos) {
+  vector_hdr_t *vh = vector_hdr(*vector_ptr);
+  if (pos >= (off_t)vh->alloc_size)
+    return _vector_resize(vector_ptr, elt_size, pos + 1);
+  return 0;
+}
+
+/**
+ * @brief Push an element at the end of a vector.
+ *
+ * @param[in] vector_ptr A pointer to the vector data structure to resize.
+ * @param[in] elt_size The size of a vector element.
+ * @param[in] elt The element to insert.
+ *
+ * NOTE:
+ *  - This function ensures there is sufficient room for inserting the element,
+ *  and evenutually resizes the vector to make room for it (if allowed by
+ *  maximum size).
+ */
+static inline int _vector_push(void **vector_ptr, size_t elt_size, void *elt) {
+  vector_hdr_t *vh = vector_hdr(*vector_ptr);
+  if (_vector_ensure_pos(vector_ptr, elt_size, vh->cur_size) < 0) return -1;
+
+  /* Always get header after a potential resize */
+  vh = vector_hdr(*vector_ptr);
+  memcpy((uint8_t *)*vector_ptr + vh->cur_size * elt_size, elt, elt_size);
+  vh = vector_hdr(*vector_ptr);
+  vh->cur_size++;
+  return 0;
+}
+
+/**
+ * @brief Remove all the occurrencies of an element from the vector.
+ * The order of the elements is NOT maintained.
+ *
+ * @param[in, out] vector The vector data structure to resize
+ * @param[in] elt_size The size of a vector element
+ * @param[in] elt The element to remove
+ * @return int Number of elemets (equal to 'elt') removed from the vector
+ */
+static inline int _vector_remove_unordered(void *vector, size_t elt_size,
+                                           void *elt) {
+  size_t num_removed = 0;
+  vector_hdr_t *vh = vector_hdr(vector);
+  for (size_t i = 0; i < vector_hdr(vector)->cur_size; i++) {
+    if (memcmp((uint8_t *)vector + i * elt_size, elt, elt_size) == 0) {
+      vh->cur_size--;
+      memcpy((uint8_t *)vector + i * elt_size,
+             (uint8_t *)vector + vh->cur_size * elt_size, elt_size);
+      num_removed++;
+    }
+  }
+  return num_removed;
+}
+
+/******************************************************************************/
+/* Public API */
+
+/**
+ * @brief Allocate and initialize a vector data structure.
+ *
+ * @param[in,out] vector Vector to allocate and initialize.
+ * @param[in] init_size Initial vector size.
+ * @param[in] max_size Maximum vector size (nonzero).
+ *
+ * NOTE:
+ *  - Allocated memory is set to 0 (used by bitmap)
+ */
+
+#define vector_init(vector, init_size, max_size) \
+  _vector_init((void **)&vector, sizeof(vector[0]), init_size, max_size)
+
+/**
+ * @brief Free a vector data structure.
+ *
+ * @param[in] vector The vector data structure to free.
+ */
+#define vector_free(vector) _vector_free((void **)&vector)
+
+/**
+ * @brief Resize a vector data structure.
+ *
+ * @param[in] vector The vector data structure to resize.
+ * @param[in] pos The position at which the vector should be able to hold an
+ * element.
+ *
+ * @return int Flag indicating whether the vector has been correctly resized.
+ *
+ * NOTE:
+ *  - The resize operation does not specify the final size of the vector but
+ * instead ensure that it is large enough to hold an element at the specified
+ * position. This allows the caller not to care about doing successive calls to
+ * this API while the vector is growing in size.
+ *  - If the new size is smaller than the current size, the content of the
+ *  vector will be truncated.
+ * - Newly allocated memory is set to 0 (used by bitmap)
+ */
+#define vector_resize(vector) \
+  _vector_resize((void **)&(vector), sizeof((vector)[0]), 0)
+
+/**
+ * @brief Ensures a vector is sufficiently large to hold an element at the
+ * given position.
+ *
+ * @param[in] vector The vector for which to validate the position.
+ * @param[in] pos The position to validate.
+ *
+ * NOTE:
+ *  - This function should always be called before writing to a vector element
+ *  to eventually make room for it (the vector will eventually be resized).
+ */
+#define vector_ensure_pos(vector, pos) \
+  _vector_ensure_pos((void **)&(vector), sizeof((vector)[0]), pos);
+
+/**
+ * @brief Push an element at the end of a vector.
+ *
+ * @param[in] vector The vector in which to insert the element.
+ * @param[in] elt The element to insert.
+ *
+ * NOTE:
+ *  - This function ensures there is sufficient room for inserting the element,
+ *  and evenutually resizes the vector to make room for it (if allowed by
+ *  maximum size).
+ */
+#define vector_push(vector, elt)                                         \
+  ({                                                                     \
+    typeof(elt) x = elt;                                                 \
+    _vector_push((void **)&(vector), sizeof((vector)[0]), (void *)(&x)); \
+  })
+
+/**
+ * @brief Remove all the occurrencies of an element from the vector.
+ * The order of the elements is NOT maintained.
+ *
+ * @param[in, out] vector The vector data structure to resize
+ * @param[in] elt The element to remove
+ * @return int Number of elemets (equal to 'elt') removed from the vector
+ */
+#define vector_remove_unordered(vector, elt)                        \
+  ({                                                                \
+    typeof(elt) x = elt;                                            \
+    _vector_remove_unordered((void *)(vector), sizeof((vector)[0]), \
+                             (void *)(&x));                         \
+  })
+
+/**
+ * @brief Returns the length of a vector.
+ *
+ * @param[in] vector The vector from which to get the size.
+ *
+ * @see vector_ensure_pos
+ *
+ * NOTE:
+ *  - The size of the vector corresponds to the highest accessed index (for
+ * example as specified in the resize operation) and not the currently
+ * allocated size which will typically be bigger to amortize allocations.
+ *  - A user should always call vector_ensure_pos to ensure the vector is
+ *  sufficiently large to hold an element at the specified position.
+ */
+#define vector_len(vector) vector_hdr(vector)->cur_size
+
+/**
+ * @brief Returns the allocated size of a vector.
+ */
+#define vector_get_alloc_size(vector) vector_hdr(vector)->alloc_size
+
+/**
+ * @brief Iterate over elements in a vector.
+ *
+ * @param[in] pool The vector data structure to iterate over
+ * @param[in, out] eltp A pointer to the element that will be used for
+ * iteration
+ * @param[in] BODY Block to execute during iteration
+ *
+ * @note Iteration will execute BODY with eltp corresponding successively to all
+ * elements found in the vector. It is implemented using the more generic
+ * enumeration function.
+ */
+#define vector_foreach(vector, eltp, BODY)                    \
+  ({                                                          \
+    unsigned _vector_var(i);                                  \
+    vector_enumerate((vector), _vector_var(i), (eltp), BODY); \
+  })
+
+/**
+ * @brief Helper function used by vector_foreach().
+ */
+#define vector_enumerate(vector, i, eltp, BODY)      \
+  ({                                                 \
+    for ((i) = 0; (i) < vector_len(vector); (i)++) { \
+      eltp = (vector) + (i);                         \
+      { BODY; }                                      \
+    }                                                \
+  })
+
+#endif /* UTIL_VECTOR_H */