diff options
| -rw-r--r-- | include/asterisk/astobj2.h | 32 | ||||
| -rw-r--r-- | main/astobj2.c | 205 | ||||
| -rw-r--r-- | tests/test_astobj2.c | 135 |
3 files changed, 6 insertions, 366 deletions
diff --git a/include/asterisk/astobj2.h b/include/asterisk/astobj2.h index 073197d47..9129c4b67 100644 --- a/include/asterisk/astobj2.h +++ b/include/asterisk/astobj2.h @@ -896,34 +896,6 @@ enum search_flags { */ OBJ_MULTIPLE = (1 << 2), /*! - * \brief Continue if a match is not found. - * - * \details - * This flag forces a whole container search. The - * OBJ_SEARCH_OBJECT, OBJ_SEARCH_KEY, and OBJ_SEARCH_PARTIAL_KEY - * flags just specify where to start the search in the - * container. If the search is not stopped early then the - * search _continues_ until the search wraps around to the - * starting point. - * - * Normal searches start where the search key specifies to start - * and end when the search key indicates that the object is not - * in the container. - * - * For hash containers, this tells the ao2_callback() core to - * keep searching through the rest of the buckets if a match is - * not found in the starting bucket defined by the hash value on - * the argument. - * - * For rbtree containers, if the search key is not in the - * container, the search will start either at the first item - * before the search key or the first item after the search key. - * - * \note The supplied ao2_callback_fn is called for every node - * in the container from the starting point. - */ - OBJ_CONTINUE = (1 << 3), - /*! * \brief Assume that the ao2_container is already locked. * * \note For ao2_containers that have mutexes, no locking will @@ -1127,6 +1099,8 @@ typedef int (ao2_callback_data_fn)(void *obj, void *arg, void *data, int flags); * OBJ_SEARCH_OBJECT - if set, 'obj', is an object. * OBJ_SEARCH_KEY - if set, 'obj', is a search key item that is not an object. * + * \note This function must be idempotent. + * * \return Computed hash value. */ typedef int (ao2_hash_fn)(const void *obj, int flags); @@ -1141,6 +1115,8 @@ typedef int (ao2_hash_fn)(const void *obj, int flags); * OBJ_SEARCH_KEY - if set, 'obj_right', is a search key item that is not an object. * OBJ_SEARCH_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object. * + * \note This function must be idempotent. + * * \retval <0 if obj_left < obj_right * \retval =0 if obj_left == obj_right * \retval >0 if obj_left > obj_right diff --git a/main/astobj2.c b/main/astobj2.c index 008c803cc..88a6a6a23 100644 --- a/main/astobj2.c +++ b/main/astobj2.c @@ -2249,8 +2249,6 @@ static enum ao2_container_insert hash_ao2_insert_node(struct ao2_container_hash struct hash_traversal_state { /*! Active sort function in the traversal if not NULL. */ ao2_sort_fn *sort_fn; - /*! Node returned in the sorted starting hash bucket if OBJ_CONTINUE flag set. (Reffed) */ - struct hash_bucket_node *first_node; /*! Saved comparison callback arg pointer. */ void *arg; /*! Starting hash bucket */ @@ -2261,8 +2259,6 @@ struct hash_traversal_state { enum search_flags flags; /*! TRUE if it is a descending search */ unsigned int descending:1; - /*! TRUE if the starting bucket needs to be rechecked because of sorting skips. */ - unsigned int recheck_starting_bucket:1; }; struct hash_traversal_state_check { @@ -2344,12 +2340,6 @@ static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *s } else { state->bucket_last = bucket_cur; } - if (flags & OBJ_CONTINUE) { - state->bucket_last = 0; - if (state->sort_fn) { - state->recheck_starting_bucket = 1; - } - } state->bucket_start = bucket_cur; /* For each bucket */ @@ -2369,14 +2359,7 @@ static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *s if (cmp > 0) { continue; } - if (flags & OBJ_CONTINUE) { - /* Remember first node when we wrap around. */ - __ao2_ref(node, +1); - state->first_node = node; - - /* From now on all nodes are matching */ - state->sort_fn = NULL; - } else if (cmp < 0) { + if (cmp < 0) { /* No more nodes in this bucket are possible to match. */ break; } @@ -2386,31 +2369,6 @@ static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *s __ao2_ref(node, +1); return node; } - - /* Was this the starting bucket? */ - if (bucket_cur == state->bucket_start - && (flags & OBJ_CONTINUE) - && (flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_NONE) { - /* In case the bucket was empty or none of the nodes matched. */ - state->sort_fn = NULL; - } - - /* Was this the first container bucket? */ - if (bucket_cur == 0 - && (flags & OBJ_CONTINUE) - && (flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_NONE) { - /* Move to the end to ensure we check every bucket */ - bucket_cur = self->n_buckets; - state->bucket_last = state->bucket_start + 1; - if (state->recheck_starting_bucket) { - /* - * We have to recheck the first part of the starting bucket - * because of sorting skips. - */ - state->recheck_starting_bucket = 0; - --state->bucket_last; - } - } } } else { /* @@ -2424,12 +2382,6 @@ static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *s } else { state->bucket_last = bucket_cur + 1; } - if (flags & OBJ_CONTINUE) { - state->bucket_last = self->n_buckets; - if (state->sort_fn) { - state->recheck_starting_bucket = 1; - } - } state->bucket_start = bucket_cur; /* For each bucket */ @@ -2449,14 +2401,7 @@ static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *s if (cmp < 0) { continue; } - if (flags & OBJ_CONTINUE) { - /* Remember first node when we wrap around. */ - __ao2_ref(node, +1); - state->first_node = node; - - /* From now on all nodes are matching */ - state->sort_fn = NULL; - } else if (cmp > 0) { + if (cmp > 0) { /* No more nodes in this bucket are possible to match. */ break; } @@ -2466,31 +2411,6 @@ static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *s __ao2_ref(node, +1); return node; } - - /* Was this the starting bucket? */ - if (bucket_cur == state->bucket_start - && (flags & OBJ_CONTINUE) - && (flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_NONE) { - /* In case the bucket was empty or none of the nodes matched. */ - state->sort_fn = NULL; - } - - /* Was this the last container bucket? */ - if (bucket_cur == self->n_buckets - 1 - && (flags & OBJ_CONTINUE) - && (flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_NONE) { - /* Move to the beginning to ensure we check every bucket */ - bucket_cur = -1; - state->bucket_last = state->bucket_start; - if (state->recheck_starting_bucket) { - /* - * We have to recheck the first part of the starting bucket - * because of sorting skips. - */ - state->recheck_starting_bucket = 0; - ++state->bucket_last; - } - } } } @@ -2539,11 +2459,6 @@ static struct hash_bucket_node *hash_ao2_find_next(struct ao2_container_hash *se for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list); node; node = AST_DLLIST_PREV(node, links)) { - if (node == state->first_node) { - /* We have wrapped back to the starting point. */ - __ao2_ref(prev, -1); - return NULL; - } if (!node->common.obj) { /* Node is empty */ continue; @@ -2578,23 +2493,6 @@ static struct hash_bucket_node *hash_ao2_find_next(struct ao2_container_hash *se hash_descending_resume:; } - - /* Was this the first container bucket? */ - if (bucket_cur == 0 - && (flags & OBJ_CONTINUE) - && (flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_NONE) { - /* Move to the end to ensure we check every bucket */ - bucket_cur = self->n_buckets; - state->bucket_last = state->bucket_start + 1; - if (state->recheck_starting_bucket) { - /* - * We have to recheck the first part of the starting bucket - * because of sorting skips. - */ - state->recheck_starting_bucket = 0; - --state->bucket_last; - } - } } } else { goto hash_ascending_resume; @@ -2605,11 +2503,6 @@ hash_descending_resume:; for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list); node; node = AST_DLLIST_NEXT(node, links)) { - if (node == state->first_node) { - /* We have wrapped back to the starting point. */ - __ao2_ref(prev, -1); - return NULL; - } if (!node->common.obj) { /* Node is empty */ continue; @@ -2644,23 +2537,6 @@ hash_descending_resume:; hash_ascending_resume:; } - - /* Was this the last container bucket? */ - if (bucket_cur == self->n_buckets - 1 - && (flags & OBJ_CONTINUE) - && (flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_NONE) { - /* Move to the beginning to ensure we check every bucket */ - bucket_cur = -1; - state->bucket_last = state->bucket_start; - if (state->recheck_starting_bucket) { - /* - * We have to recheck the first part of the starting bucket - * because of sorting skips. - */ - state->recheck_starting_bucket = 0; - ++state->bucket_last; - } - } } } @@ -2671,22 +2547,6 @@ hash_ascending_resume:; /*! * \internal - * \brief Cleanup the hash container traversal state. - * \since 12.0.0 - * - * \param state Traversal state to cleanup. - * - * \return Nothing - */ -static void hash_ao2_find_cleanup(struct hash_traversal_state *state) -{ - if (state->first_node) { - __ao2_ref(state->first_node, -1); - } -} - -/*! - * \internal * \brief Find the next non-empty iteration node in the container. * \since 12.0.0 * @@ -3110,7 +2970,6 @@ static const struct ao2_container_methods v_table_hash = { .insert = (ao2_container_insert_fn) hash_ao2_insert_node, .traverse_first = (ao2_container_find_first_fn) hash_ao2_find_first, .traverse_next = (ao2_container_find_next_fn) hash_ao2_find_next, - .traverse_cleanup = (ao2_container_find_cleanup_fn) hash_ao2_find_cleanup, .iterator_next = (ao2_iterator_next_fn) hash_ao2_iterator_next, .destroy = (ao2_container_destroy_fn) hash_ao2_destroy, #if defined(AST_DEVMODE) @@ -4461,8 +4320,6 @@ static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree struct rbtree_traversal_state { /*! Active sort function in the traversal if not NULL. */ ao2_sort_fn *sort_fn; - /*! First node returned if OBJ_CONTINUE flag set. (Reffed) */ - struct rbtree_node *first_node; /*! Saved comparison callback arg pointer. */ void *arg; /*! Saved search flags to control traversing the container. */ @@ -4507,31 +4364,9 @@ static struct rbtree_node *rb_ao2_find_next(struct ao2_container_rbtree *self, s default: case OBJ_ORDER_ASCENDING: node = rb_node_next(node); - if (!node) { - if (!state->first_node) { - break; - } - /* Wrap around to the beginning. */ - node = rb_node_most_left(self->root); - } - if (node == state->first_node) { - /* We have wrapped back to the starting point. */ - node = NULL; - } break; case OBJ_ORDER_DESCENDING: node = rb_node_prev(node); - if (!node) { - if (!state->first_node) { - break; - } - /* Wrap around to the end. */ - node = rb_node_most_right(self->root); - } - if (node == state->first_node) { - /* We have wrapped back to the starting point. */ - node = NULL; - } break; case OBJ_ORDER_PRE: node = rb_node_pre(node); @@ -4590,7 +4425,6 @@ static struct rbtree_node *rb_ao2_find_next(struct ao2_container_rbtree *self, s * OBJ_SEARCH_OBJECT - if set, 'obj_right', is an object. * OBJ_SEARCH_KEY - if set, 'obj_right', is a search key item that is not an object. * OBJ_SEARCH_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object. - * OBJ_CONTINUE - if set, return node right before or right after search key if not a match. * \param bias How to bias search direction for duplicates * * \retval node on success. @@ -4644,12 +4478,6 @@ static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, vo } /* No match found. */ - if (flags & OBJ_CONTINUE) { - next = rb_node_next_full(node); - if (!next) { - next = rb_node_prev_full(node); - } - } return next; } } else { @@ -4700,9 +4528,6 @@ static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, vo } /* No match found. */ - if (flags & OBJ_CONTINUE) { - return node; - } return NULL; } } @@ -4867,15 +4692,6 @@ static struct rbtree_node *rb_ao2_find_first(struct ao2_container_rbtree *self, break; } - if (state->sort_fn && (flags & OBJ_CONTINUE)) { - /* Remember first node when we wrap around. */ - __ao2_ref(node, +1); - state->first_node = node; - - /* From now on all nodes are matching */ - state->sort_fn = NULL; - } - /* We have the first traversal node */ __ao2_ref(node, +1); return node; @@ -4883,22 +4699,6 @@ static struct rbtree_node *rb_ao2_find_first(struct ao2_container_rbtree *self, /*! * \internal - * \brief Cleanup the rbtree container traversal state. - * \since 12.0.0 - * - * \param state Traversal state to cleanup. - * - * \return Nothing - */ -static void rb_ao2_find_cleanup(struct rbtree_traversal_state *state) -{ - if (state->first_node) { - __ao2_ref(state->first_node, -1); - } -} - -/*! - * \internal * \brief Find the next non-empty iteration node in the container. * \since 12.0.0 * @@ -5282,7 +5082,6 @@ static const struct ao2_container_methods v_table_rbtree = { .insert = (ao2_container_insert_fn) rb_ao2_insert_node, .traverse_first = (ao2_container_find_first_fn) rb_ao2_find_first, .traverse_next = (ao2_container_find_next_fn) rb_ao2_find_next, - .traverse_cleanup = (ao2_container_find_cleanup_fn) rb_ao2_find_cleanup, .iterator_next = (ao2_iterator_next_fn) rb_ao2_iterator_next, .destroy = (ao2_container_destroy_fn) rb_ao2_destroy, #if defined(AST_DEVMODE) diff --git a/tests/test_astobj2.c b/tests/test_astobj2.c index 591326b2d..11c79946e 100644 --- a/tests/test_astobj2.c +++ b/tests/test_astobj2.c @@ -85,10 +85,6 @@ struct test_obj { /*! Partial search key +/- matching range. */ int partial_key_match_range; -/*! Special iax2 OBJ_CONTINUE test. Bucket selected. */ -int special_bucket; -/*! Special iax2 OBJ_CONTINUE test. Object number select. */ -int special_match; static void test_obj_destructor(void *v_obj) { @@ -138,11 +134,6 @@ static int test_cmp_cb(void *obj, void *arg, int flags) } else { struct test_obj *arg_obj = (struct test_obj *) arg; - if (!arg_obj) { - /* Never match on the special iax2 OBJ_CONTINUE test. */ - return 0; - } - return (cmp_obj->i == arg_obj->i) ? CMP_MATCH : 0; } } @@ -162,14 +153,6 @@ static int test_hash_cb(const void *obj, const int flags) } else { const struct test_obj *hash_obj = obj; - if (!hash_obj) { - /* - * Use the special_bucket as the bucket for the special iax2 - * OBJ_CONTINUE test. - */ - return special_bucket; - } - return hash_obj->i; } } @@ -194,14 +177,6 @@ static int test_sort_cb(const void *obj_left, const void *obj_right, int flags) } else { const struct test_obj *test_right = obj_right; - if (!test_right) { - /* - * Compare with special_match in the special iax2 OBJ_CONTINUE - * test. - */ - return test_left->i - special_match; - } - return test_left->i - test_right->i; } } @@ -453,11 +428,9 @@ static int astobj2_test_1_helper(int tst_num, enum test_container_type type, int struct ao2_iterator it; struct ao2_iterator *mult_it; struct test_obj *obj; - ao2_callback_fn *cmp_fn; int n_buckets = 0; int increment = 0; int destructor_count = 0; - int count; int num; int res = AST_TEST_PASS; @@ -465,11 +438,6 @@ static int astobj2_test_1_helper(int tst_num, enum test_container_type type, int ast_test_status_update(test, "Test %d, %s containers (%s).\n", tst_num, c_type, use_sort ? "sorted" : "non-sorted"); - /* Need at least 12 objects for the special iax2 OBJ_CONTINUE test. */ - if (lim < 12) { - lim = 12; - } - c1 = NULL; switch (type) { case TEST_CONTAINER_LIST: @@ -480,10 +448,6 @@ static int astobj2_test_1_helper(int tst_num, enum test_container_type type, int break; case TEST_CONTAINER_HASH: n_buckets = (ast_random() % ((lim / 4) + 1)) + 1; - if (n_buckets < 6) { - /* Need at least 6 buckets for the special iax2 OBJ_CONTINUE test. */ - n_buckets = 6; - } c1 = ao2_t_container_alloc_hash(AO2_ALLOC_OPT_LOCK_MUTEX, 0, n_buckets, test_hash_cb, use_sort ? test_sort_cb : NULL, test_cmp_cb, "test"); break; @@ -543,105 +507,6 @@ static int astobj2_test_1_helper(int tst_num, enum test_container_type type, int /* Testing ao2_find with OBJ_PARTIAL_KEY */ res = test_ao2_find_w_OBJ_PARTIAL_KEY(res, c1, lim, test); - /* - * Testing ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE. - * In this test items are unlinked from c1 and placed in c2. Then - * unlinked from c2 and placed back into c1. - * - * For this module and set of custom hash/cmp functions, an object - * should only be found if the astobj2 default cmp function is used. - * This test is designed to mimic the chan_iax.c call number use case. - * - * Must test the custom cmp_cb case first since it should never - * find and thus unlink anything for this test. - */ - for (cmp_fn = test_cmp_cb; ; cmp_fn = NULL) { - num = lim; - for (count = 0; num && count < 100; ++count) { - --num; - - /* This special manipulation is needed for sorted hash buckets. */ - special_bucket = num; - switch (count) { - case 0: - /* Beyond end of bucket list. */ - special_match = lim; - break; - case 1: - /* At end of bucket list. */ - special_match = num; - break; - case 2: - /* In between in middle of bucket list. */ - special_match = num - 1; - break; - case 3: - /* Beginning of bucket list. */ - special_match = num % n_buckets; - break; - case 4: - /* Before bucket list. */ - special_match = -1; - break; - default: - /* Empty bucket list. (If possible to empty it.) */ - special_match = -1; - special_bucket = lim - 1; - break; - } - - /* ao2_find is just a shortcut notation for ao2_callback(). */ - obj = ao2_callback(c1, OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE, cmp_fn, NULL); - if (!obj) { - if (!cmp_fn) { - ast_test_status_update(test, - "ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE failed with default cmp_cb.\n"); - res = AST_TEST_FAIL; - } - } else { - if (cmp_fn) { - ast_test_status_update(test, - "ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE failed with custom cmp_cb.\n"); - res = AST_TEST_FAIL; - } - ao2_link(c2, obj); - ao2_t_ref(obj, -1, "test"); - } - } - if (ao2_container_check(c1, 0)) { - ast_test_status_update(test, "container integrity check failed\n"); - res = AST_TEST_FAIL; - goto cleanup; - } - if (ao2_container_check(c2, 0)) { - ast_test_status_update(test, "container integrity check failed\n"); - res = AST_TEST_FAIL; - goto cleanup; - } - it = ao2_iterator_init(c2, 0); - while ((obj = ao2_t_iterator_next(&it, "test"))) { - ao2_t_unlink(c2, obj, "test"); - ao2_t_link(c1, obj, "test"); - ao2_t_ref(obj, -1, "test"); - } - ao2_iterator_destroy(&it); - if (ao2_container_check(c1, 0)) { - ast_test_status_update(test, "container integrity check failed\n"); - res = AST_TEST_FAIL; - goto cleanup; - } - if (ao2_container_check(c2, 0)) { - ast_test_status_update(test, "container integrity check failed\n"); - res = AST_TEST_FAIL; - goto cleanup; - } - - if (!cmp_fn) { - /* Completed testing with custom cmp_cb and default cmp_cb */ - break; - } - } - /* Test Callback with no flags. */ increment = 0; ao2_t_callback(c1, 0, increment_cb, &increment, "test callback"); |