astobj2: Remove OBJ_CONTINUE support.
authorRichard Mudgett <rmudgett@digium.com>
Fri, 27 Sep 2013 17:11:22 +0000 (17:11 +0000)
committerRichard Mudgett <rmudgett@digium.com>
Fri, 27 Sep 2013 17:11:22 +0000 (17:11 +0000)
OBJ_CONTINUE was a strange feature that came into the world under
suspicious circumstances to support an abuse of the ao2_container by
chan_iax2.  Since chan_iax2 no longer uses OBJ_CONTINUE, it is safe to
remove it.

The simplified code should help performance slightly and make
understanding the code easier.

Review: https://reviewboard.asterisk.org/r/2887/
........

Merged revisions 399937 from http://svn.asterisk.org/svn/asterisk/branches/12

git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@399938 65c4cc65-6c06-0410-ace0-fbb531ad65f3

include/asterisk/astobj2.h
main/astobj2.c
tests/test_astobj2.c

index 073197d..9129c4b 100644 (file)
@@ -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
index 008c803..88a6a6a 100644 (file)
@@ -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)
index 591326b..11c7994 100644 (file)
@@ -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");