[Asterisk-code-review] vector: Add REMOVE, SORT and RESET macros (asterisk[13])
George Joseph
asteriskteam at digium.com
Sat May 9 17:10:57 CDT 2015
George Joseph has uploaded a new change for review.
https://gerrit.asterisk.org/421
Change subject: vector: Add REMOVE, SORT and RESET macros
......................................................................
vector: Add REMOVE, SORT 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_SORT which performs a qsort on a vector with
a user supplied compare function.
AST_VECTOR_RESET which cleans all elements from the vector
leaving the storage intact.
Change-Id: I41d32dbdf7137e0557134efeff9f9f1064b58d14
---
M include/asterisk/vector.h
M tests/test_vector.c
2 files changed, 93 insertions(+), 17 deletions(-)
git pull ssh://gerrit.asterisk.org:29418/asterisk refs/changes/21/421/1
diff --git a/include/asterisk/vector.h b/include/asterisk/vector.h
index 255c30b..9ef672f 100644
--- a/include/asterisk/vector.h
+++ b/include/asterisk/vector.h
@@ -280,16 +280,38 @@
*
* \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.
@@ -298,17 +320,8 @@
* \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 +434,29 @@
#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) ({ \
+ size_t idx; \
+ for (idx = 0; idx < (vec)->current; ++idx) { \
+ cleanup((vec)->elems[idx]); \
+ } \
+ (vec)->current = 0; \
+})
+
+/*!
+ * \brief Sort vector.
+ *
+ * \param vec Vector to sort.
+ * \param comparison_fn The comparison_fn_t cpmpatible compare function.
+ */
+#define AST_VECTOR_SORT(vec, comparison_fn) \
+ qsort((vec)->elems, (vec)->current, sizeof(*((vec)->elems)), comparison_fn)
+
+/*!
* \brief Get an address of element in a vector.
*
* \param vec Vector to query.
@@ -508,6 +544,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 6badd75..52cf34c 100644
--- a/tests/test_vector.c
+++ b/tests/test_vector.c
@@ -210,6 +210,14 @@
cleanup_count++;
}
+static int sort_int(const void *a, const void *b)
+{
+ const int *ia = a;
+ const int *ib = b;
+
+ return (*ia > *ib) - (*ia < *ib);
+}
+
AST_TEST_DEFINE(basic_ops_integer)
{
AST_VECTOR(test_struct, int) sv1;
@@ -331,6 +339,36 @@
/* CCC should still be there though */
ast_test_validate_cleanup(test, *(int *)AST_VECTOR_GET_CMP(&sv1, CCC, AST_VECTOR_ELEM_DEFAULT_CMP) == CCC, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_SIZE(&sv1) == 1, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_APPEND(&sv1, ZZZ) == 0, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_APPEND(&sv1, BBB) == 0, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_APPEND(&sv1, AAA) == 0, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_APPEND(&sv1, CCC) == 0, rc, cleanup);
+
+ AST_VECTOR_SORT(&sv1, sort_int);
+ 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) == CCC, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_GET(&sv1, 4) == ZZZ, rc, cleanup);
+
+ cleanup_count = 0;
+ AST_VECTOR_RESET(&sv1, cleanup_int);
+ 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_count = 0;
+ AST_VECTOR_RESET(&sv1, AST_VECTOR_ELEM_CLEANUP_NOOP);
+ ast_test_validate_cleanup(test, AST_VECTOR_APPEND(&sv1, ZZZ) == 0, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_APPEND(&sv1, BBB) == 0, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_APPEND(&sv1, AAA) == 0, rc, cleanup);
+ ast_test_validate_cleanup(test, AST_VECTOR_APPEND(&sv1, CCC) == 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 == 0, rc, cleanup);
+
cleanup:
AST_VECTOR_FREE(&sv1);
return rc;
--
To view, visit https://gerrit.asterisk.org/421
To unsubscribe, visit https://gerrit.asterisk.org/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: I41d32dbdf7137e0557134efeff9f9f1064b58d14
Gerrit-PatchSet: 1
Gerrit-Project: asterisk
Gerrit-Branch: 13
Gerrit-Owner: George Joseph <george.joseph at fairview5.com>
More information about the asterisk-code-review
mailing list