vector: Add REMOVE, ADD_SORTED and RESET macros

Based on feedback from Corey Farrell and Y Ateya, a few new
macros have been added...

AST_VECTOR_REMOVE which takes a parameter to indicate if
order should be preserved.

AST_VECTOR_ADD_SORTED which adds an element to
a sorted vector.

AST_VECTOR_RESET which cleans all elements from the vector
leaving the storage intact.

Change-Id: I41d32dbdf7137e0557134efeff9f9f1064b58d14

diff --git a/include/asterisk/vector.h b/include/asterisk/vector.h
index 255c30b..0a13c56 100644 (file)
--- a/include/asterisk/vector.h
+++ b/include/asterisk/vector.h
@@ -273,6 +273,36 @@
 })
 
 /*!
+ * \brief Add an element into a sorted vector
+ *
+ * \param vec Sorted vector to add to.
+ * \param elem Element to insert.
+ * \param cmp A strcmp compatible compare function.
+ *
+ * \return 0 on success.
+ * \return Non-zero on failure.
+ *
+ * \warning Use of this macro on an unsorted vector will produce unpredictable results
+ */
+#define AST_VECTOR_ADD_SORTED(vec, elem, cmp) ({ \
+       int res = 0; \
+       size_t __idx = (vec)->current; \
+       do { \
+               if (__make_room((vec)->current, vec) != 0) { \
+                       res = -1; \
+                       break; \
+               } \
+               while (__idx > 0 && (cmp((vec)->elems[__idx - 1], elem) > 0)) { \
+                       (vec)->elems[__idx] = (vec)->elems[__idx - 1]; \
+                       __idx--; \
+               } \
+               (vec)->elems[__idx] = elem; \
+               (vec)->current++; \
+       } while (0); \
+       res; \
+})
+
+/*!
  * \brief Remove an element from a vector by index.
  *
  * Note that elements in the vector may be reordered, so that the remove can
@@ -280,35 +310,48 @@
  *
  * \param vec Vector to remove from.
  * \param idx Index of the element to remove.
+ * \param preserve_order Preserve the vector order.
+ *
  * \return The element that was removed.
  */
-#define AST_VECTOR_REMOVE_UNORDERED(vec, idx) ({               \
-       typeof((vec)->elems[0]) res;                            \
-       size_t __idx = (idx);                                   \
-       ast_assert(__idx < (vec)->current);                     \
-       res = (vec)->elems[__idx];                              \
-       (vec)->elems[__idx] = (vec)->elems[--(vec)->current];   \
+#define AST_VECTOR_REMOVE(vec, idx, preserve_ordered) ({ \
+       typeof((vec)->elems[0]) res; \
+       size_t __idx = (idx); \
+       ast_assert(__idx < (vec)->current); \
+       res = (vec)->elems[__idx]; \
+       if ((preserve_ordered)) { \
+               size_t __move; \
+               __move = ((vec)->current - (__idx) - 1) * sizeof(typeof((vec)->elems[0])); \
+               memmove(&(vec)->elems[__idx], &(vec)->elems[__idx + 1], __move); \
+               (vec)->current--; \
+       } else { \
+               (vec)->elems[__idx] = (vec)->elems[--(vec)->current];   \
+       }; \
        res;                                                    \
 })
 
 /*!
+ * \brief Remove an element from an unordered vector by index.
+ *
+ * Note that elements in the vector may be reordered, so that the remove can
+ * happen in constant time.
+ *
+ * \param vec Vector to remove from.
+ * \param idx Index of the element to remove.
+ * \return The element that was removed.
+ */
+#define AST_VECTOR_REMOVE_UNORDERED(vec, idx) \
+       AST_VECTOR_REMOVE(vec, idx, 0)
+
+/*!
  * \brief Remove an element from a vector by index while maintaining order.
  *
  * \param vec Vector to remove from.
  * \param idx Index of the element to remove.
  * \return The element that was removed.
  */
-#define AST_VECTOR_REMOVE_ORDERED(vec, idx) ({                         \
-       typeof((vec)->elems[0]) res;                                    \
-       size_t __idx = (idx);                                           \
-       size_t __move;                                                  \
-       ast_assert(__idx < (vec)->current);                             \
-       res = (vec)->elems[__idx];                                      \
-       __move = ((vec)->current - (__idx) - 1) * sizeof(typeof((vec)->elems[0])); \
-       memmove(&(vec)->elems[__idx], &(vec)->elems[__idx + 1], __move); \
-       (vec)->current--;                                               \
-       res;                                                            \
-})
+#define AST_VECTOR_REMOVE_ORDERED(vec, idx) \
+       AST_VECTOR_REMOVE(vec, idx, 1)
 
 /*!
  * \brief Remove an element from a vector that matches the given comparison
@@ -421,6 +464,17 @@
 #define AST_VECTOR_SIZE(vec) (vec)->current
 
 /*!
+ * \brief Reset vector.
+ *
+ * \param vec Vector to reset.
+ * \param callback A cleanup callback or AST_VECTOR_ELEM_CLEANUP_NOOP.
+ */
+#define AST_VECTOR_RESET(vec, cleanup) ({ \
+       AST_VECTOR_CALLBACK_VOID(vec, cleanup); \
+       (vec)->current = 0; \
+})
+
+/*!
  * \brief Get an address of element in a vector.
  *
  * \param vec Vector to query.
@@ -508,6 +562,8 @@
  * \brief Execute a callback on every element in a vector returning the matching
  * elements in a new vector
  *
+ * This macro basically provides a filtered clone.
+ *
  * \param vec Vector to operate on.
  * \param callback A callback that takes at least 1 argument (the element)
  * plus number of optional arguments

diff --git a/tests/test_vector.c b/tests/test_vector.c
index bd45b0c..ff305b5 100644 (file)
--- a/tests/test_vector.c
+++ b/tests/test_vector.c
@@ -63,7 +63,9 @@ AST_TEST_DEFINE(basic_ops)
        char *CCC = "CCC";
        char *YYY = "YYY";
        char *ZZZ = "ZZZ";
+       char CCC2[4];
 
+       strcpy(CCC2, "CCC");
        switch (cmd) {
        case TEST_INIT:
                info->name = "basic";
@@ -202,6 +204,29 @@ AST_TEST_DEFINE(basic_ops)
        ast_test_validate_cleanup(test, AST_VECTOR_GET(&sv1, 0) == CCC, rc, cleanup);
        ast_test_validate_cleanup(test, cleanup_count == 1, rc, cleanup);
 
+       /* Test INSERT_SORTED */
+       AST_VECTOR_FREE(&sv1);
+       ast_test_validate(test, AST_VECTOR_INIT(&sv1, 0) == 0);
+
+       ast_test_validate_cleanup(test, AST_VECTOR_ADD_SORTED(&sv1, BBB, strcmp) == 0, rc, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_ADD_SORTED(&sv1, ZZZ, strcmp) == 0, rc, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_ADD_SORTED(&sv1, CCC, strcmp) == 0, rc, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_ADD_SORTED(&sv1, AAA, strcmp) == 0, rc, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_ADD_SORTED(&sv1, CCC2, strcmp) == 0, rc, cleanup);
+
+       ast_test_validate_cleanup(test, AST_VECTOR_GET(&sv1, 0) == AAA, rc, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_GET(&sv1, 1) == BBB, rc, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_GET(&sv1, 2) == CCC, rc, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_GET(&sv1, 3) == CCC2, rc, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_GET(&sv1, 4) == ZZZ, rc, cleanup);
+
+       cleanup_count = 0;
+       AST_VECTOR_RESET(&sv1, cleanup);
+       ast_test_validate_cleanup(test, AST_VECTOR_SIZE(&sv1) == 0, rc, cleanup);
+       ast_test_validate_cleanup(test, sv1.max >= 5, rc, cleanup);
+       ast_test_validate_cleanup(test, sv1.elems != NULL, rc, cleanup);
+       ast_test_validate_cleanup(test, cleanup_count == 5, rc, cleanup);
+
 cleanup:
        AST_VECTOR_FREE(&sv1);
        return rc;
@@ -218,13 +243,13 @@ AST_TEST_DEFINE(basic_ops_integer)
        int rc = AST_TEST_PASS;
 
        int AAA = 1;
-       int BBB = 2;
-       int CCC = 3;
+       int BBB = 3;
+       int CCC = 5;
        int ZZZ = 26;
 
        switch (cmd) {
        case TEST_INIT:
-               info->name = "basic integer";
+               info->name = "basic_integer";
                info->category = "/main/vector/";
                info->summary = "Test integer vector basic ops";
                info->description = "Test integer vector basic ops";