diff options
| -rw-r--r-- | include/asterisk/vector.h | 90 | ||||
| -rw-r--r-- | tests/test_vector.c | 31 |
2 files changed, 101 insertions, 20 deletions
diff --git a/include/asterisk/vector.h b/include/asterisk/vector.h index 255c30b43..0a13c560b 100644 --- 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 6badd75af..8ca4efa1a 100644 --- a/tests/test_vector.c +++ b/tests/test_vector.c @@ -61,7 +61,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"; @@ -200,6 +202,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; @@ -216,13 +241,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"; |