Enhance astobj2 to support other types of containers.
authorRichard Mudgett <rmudgett@digium.com>
Wed, 12 Sep 2012 21:02:29 +0000 (21:02 +0000)
committerRichard Mudgett <rmudgett@digium.com>
Wed, 12 Sep 2012 21:02:29 +0000 (21:02 +0000)
The new API allows for sorted containers, insertion options, duplicate
handling options, and traversal order options.

* Adds the ability for containers to be sorted when they are created.

* Adds container creation options to handle duplicates when they are
inserted.

* Adds container creation option to insert objects at the beginning or end
of the container traversal order.

* Adds OBJ_PARTIAL_KEY to allow searching with a partial key.  The partial
key works similarly to the OBJ_KEY flag.  (The real search speed
improvement with this flag will come when red-black trees are added.)

* Adds container traversal and iteration order options: Ascending and
Descending.

* Adds an AST_DEVMODE compile feature to check the stats and integrity of
registered containers using the CLI "astobj2 container stats <name>" and
"astobj2 container check <name>".  The channels container is normally
registered since it is one of the most important containers in the system.

* Adds ao2_iterator_restart() to allow iteration to be restarted from the
beginning.

* Changes the generic container object to have a v_method table pointer to
support other types of containers.

* Changes the container nodes holding objects to be ref counted.

The ref counted nodes and v_method table pointer changes pave the way to
allow other types of containers.

* Includes a large astobj2 unit test enhancement that tests the new
features.

(closes issue ASTERISK-19969)
Reported by: rmudgett

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

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

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

index d7d9d79..3b93a02 100644 (file)
@@ -728,8 +728,10 @@ Operations on container include:
     OBJ_MULTIPLE - don't stop at first match
     OBJ_POINTER - if set, 'arg' is an object pointer, and a hash table
                   search will be done. If not, a traversal is done.
-    OBJ_KEY - if set, 'arg', is a hashable item that is not an object.
+    OBJ_KEY - if set, 'arg', is a search key item that is not an object.
               Similar to OBJ_POINTER and mutually exclusive.
+    OBJ_PARTIAL_KEY - if set, 'arg', is a partial search key item that is not an object.
+              Similar to OBJ_KEY and mutually exclusive.
 
   -  \b ao2_callback(c, flags, fn, arg)
     apply fn(obj, arg) to all objects in the container.
@@ -743,8 +745,10 @@ Operations on container include:
          OBJ_POINTER  - if set, 'arg' is an object pointer, and a hash table
                         search will be done. If not, a traversal is done through
                         all the hash table 'buckets'..
-         OBJ_KEY      - if set, 'arg', is a hashable item that is not an object.
+         OBJ_KEY      - if set, 'arg', is a search key item that is not an object.
                         Similar to OBJ_POINTER and mutually exclusive.
+         OBJ_PARTIAL_KEY - if set, 'arg', is a partial search key item that is not an object.
+                        Similar to OBJ_KEY and mutually exclusive.
       - fn is a func that returns int, and takes 3 args:
         (void *obj, void *arg, int flags);
           obj is an object
@@ -801,32 +805,6 @@ to define callback and hash functions and their arguments.
  */
 
 /*! \brief
- * Type of a generic callback function
- * \param obj  pointer to the (user-defined part) of an object.
- * \param arg callback argument from ao2_callback()
- * \param flags flags from ao2_callback()
- *
- * The return values are a combination of enum _cb_results.
- * Callback functions are used to search or manipulate objects in a container.
- */
-typedef int (ao2_callback_fn)(void *obj, void *arg, int flags);
-
-/*! \brief
- * Type of a generic callback function
- * \param obj pointer to the (user-defined part) of an object.
- * \param arg callback argument from ao2_callback()
- * \param data arbitrary data from ao2_callback()
- * \param flags flags from ao2_callback()
- *
- * The return values are a combination of enum _cb_results.
- * Callback functions are used to search or manipulate objects in a container.
- */
-typedef int (ao2_callback_data_fn)(void *obj, void *arg, void *data, int flags);
-
-/*! \brief A common ao2_callback is one that matches by address. */
-int ao2_match_by_addr(void *obj, void *arg, int flags);
-
-/*! \brief
  * A callback function will return a combination of CMP_MATCH and CMP_STOP.
  * The latter will terminate the search in a container.
  */
@@ -835,8 +813,13 @@ enum _cb_results {
        CMP_STOP        = 0x2,  /*!< stop the search now */
 };
 
-/*! \brief
- * Flags passed to ao2_callback() and ao2_hash_fn() to modify its behaviour.
+/*!
+ * \brief Flags passed to ao2_callback_fn(), ao2_hash_fn(), and ao2_sort_fn() to modify behaviour.
+ *
+ * \todo XXX OBJ_POINTER, OBJ_KEY, and OBJ_PARTIAL_KEY need to
+ * be put into a bit field like OBJ_ORDER_MASK since they are
+ * mutually exclusive.  This change unfortunately is not
+ * backwards compatible.
  */
 enum search_flags {
        /*!
@@ -855,21 +838,42 @@ enum search_flags {
         */
        OBJ_MULTIPLE = (1 << 2),
        /*!
-        * The given obj is an object of the same type as the one being
-        * searched for, so use the object's hash function for optimized
-        * searching.
+        * \brief The arg parameter is an object of the same type.
+        *
+        * \details
+        * The arg parameter is an object of the same type as the one
+        * being searched for, so use the object's ao2_hash_fn and/or
+        * ao2_sort_fn functions for optimized searching.
         *
-        * The matching function is unaffected (i.e. The cb_fn argument
-        * to ao2_callback).
+        * \note The supplied ao2_callback_fn is called after the
+        * container nodes have been filtered by the ao2_hash_fn and/or
+        * ao2_sort_fn functions.
+        *
+        * \note OBJ_POINTER, OBJ_KEY, and OBJ_PARTIAL_KEY are mutually
+        * exclusive.
         */
        OBJ_POINTER = (1 << 3),
        /*!
-        * \brief Continue if a match is not found in the hashed out bucket
+        * \brief Continue if a match is not found.
+        *
+        * \details
+        * This flag forces a whole container search.  The OBJ_POINTER,
+        * OBJ_KEY, and OBJ_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.
         *
-        * This flag is to be used in combination with OBJ_POINTER.  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.
+        * 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.
+        *
+        * \note The supplied ao2_callback_fn is called for every node
+        * in the container from the starting point.
         */
        OBJ_CONTINUE = (1 << 4),
        /*!
@@ -887,26 +891,169 @@ enum search_flags {
         */
        OBJ_NOLOCK = (1 << 5),
        /*!
-        * \brief The data is hashable, but is not an object.
+        * \brief The arg parameter is a search key, but is not an object.
         *
         * \details
         * This can be used when you want to be able to pass custom data
-        * to the container's stored ao2_hash_fn and ao2_find
-        * ao2_callback_fn functions that is not a full object, but
-        * perhaps just a string.
+        * to the container's stored ao2_hash_fn, ao2_sort_fn, and
+        * ao2_find ao2_callback_fn functions that is not a full object,
+        * but perhaps just a string.
+        *
+        * \note The supplied ao2_callback_fn is called after the
+        * container nodes have been filtered by the ao2_hash_fn and/or
+        * ao2_sort_fn functions.
         *
-        * \note OBJ_KEY and OBJ_POINTER are mutually exclusive options.
+        * \note OBJ_POINTER, OBJ_KEY, and OBJ_PARTIAL_KEY are mutually
+        * exclusive.
         */
        OBJ_KEY = (1 << 6),
+       /*!
+        * \brief The arg parameter is a partial search key similar to OBJ_KEY.
+        *
+        * \details
+        * The partial key can be used by the ao2_sort_fn to guide the
+        * search to find a contiguous subset of a sorted container.
+        * For example, a sorted container holds: "A", "B", "Bert",
+        * "Beth", "Earnie".  Doing a partial key search with "B" will
+        * find the sorted subset of all held objects starting with "B".
+        *
+        * \note The supplied ao2_callback_fn is called after the
+        * container nodes have been filtered by the ao2_sort_fn
+        * function.
+        *
+        * \note OBJ_POINTER, OBJ_KEY, and OBJ_PARTIAL_KEY are mutually
+        * exclusive.
+        */
+       OBJ_PARTIAL_KEY = (1 << 7),
+
+       /*! \brief Traverse order option field mask. */
+       OBJ_ORDER_MASK = (0x03 << 8),
+       /*! \brief Traverse in ascending order (First to last container object) */
+       OBJ_ORDER_ASCENDING = (0 << 8),
+       /*! \brief Traverse in descending order (Last to first container object) */
+       OBJ_ORDER_DESCENDING = (1 << 8),
+};
+
+/*!
+ * \brief Options available when allocating an ao2 container object.
+ *
+ * \note Each option is open to some interpretation by the
+ * container type as long as it makes sense with the option
+ * name.
+ */
+enum ao2_container_opts {
+       /*!
+        * \brief Insert objects at the beginning of the container.
+        * (Otherwise it is the opposite; insert at the end.)
+        *
+        * \note If an ao2_sort_fn is provided, the object is inserted
+        * before any objects with duplicate keys.
+        *
+        * \note Hash containers insert the object in the computed hash
+        * bucket in the indicated manner.
+        */
+       AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN = (1 << 0),
+
+       /*!
+        * \brief The ao2 container objects with duplicate keys option field mask.
+        */
+       AO2_CONTAINER_ALLOC_OPT_DUPS_MASK = (3 << 1),
+       /*!
+        * \brief Allow objects with duplicate keys in container.
+        */
+       AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW = (0 << 1),
+       /*!
+        * \brief Reject objects with duplicate keys in container.
+        *
+        * \note The container must be sorted.  i.e. have an
+        * ao2_sort_fn.
+        */
+       AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT = (1 << 1),
+       /*!
+        * \brief Reject duplicate objects in container.
+        *
+        * \details Don't link the same object into the container twice.
+        * However, you can link a different object with the same key.
+        *
+        * \note The container must be sorted.  i.e. have an
+        * ao2_sort_fn.
+        *
+        * \note It is assumed that the objects are located where the
+        * search key says they should be located.
+        */
+       AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT = (2 << 1),
+       /*!
+        * \brief Replace objects with duplicate keys in container.
+        *
+        * \details The existing duplicate object is removed and the new
+        * object takes the old object's place.
+        *
+        * \note The container must be sorted.  i.e. have an
+        * ao2_sort_fn.
+        */
+       AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE = (3 << 1),
 };
 
 /*!
+ * \brief Type of a generic callback function
+ * \param obj  pointer to the (user-defined part) of an object.
+ * \param arg callback argument from ao2_callback()
+ * \param flags flags from ao2_callback()
+ *   OBJ_POINTER - if set, 'arg', is an object.
+ *   OBJ_KEY - if set, 'arg', is a search key item that is not an object.
+ *   OBJ_PARTIAL_KEY - if set, 'arg', is a partial search key item that is not an object.
+ *
+ * The return values are a combination of enum _cb_results.
+ * Callback functions are used to search or manipulate objects in a container.
+ */
+typedef int (ao2_callback_fn)(void *obj, void *arg, int flags);
+
+/*! \brief A common ao2_callback is one that matches by address. */
+int ao2_match_by_addr(void *obj, void *arg, int flags);
+
+/*!
+ * \brief Type of a generic callback function
+ * \param obj pointer to the (user-defined part) of an object.
+ * \param arg callback argument from ao2_callback()
+ * \param data arbitrary data from ao2_callback()
+ * \param flags flags from ao2_callback()
+ *   OBJ_POINTER - if set, 'arg', is an object.
+ *   OBJ_KEY - if set, 'arg', is a search key item that is not an object.
+ *   OBJ_PARTIAL_KEY - if set, 'arg', is a partial search key item that is not an object.
+ *
+ * The return values are a combination of enum _cb_results.
+ * Callback functions are used to search or manipulate objects in a container.
+ */
+typedef int (ao2_callback_data_fn)(void *obj, void *arg, void *data, int flags);
+
+/*!
  * Type of a generic function to generate a hash value from an object.
- * flags is ignored at the moment. Eventually, it will include the
- * value of OBJ_POINTER passed to ao2_callback().
+ *
+ * \param obj pointer to the (user-defined part) of an object.
+ * \param flags flags from ao2_callback()
+ *   OBJ_POINTER - if set, 'obj', is an object.
+ *   OBJ_KEY - if set, 'obj', is a search key item that is not an object.
+ *
+ * \return Computed hash value.
  */
 typedef int (ao2_hash_fn)(const void *obj, int flags);
 
+/*!
+ * \brief Type of generic container sort function.
+ *
+ * \param obj_left pointer to the (user-defined part) of an object.
+ * \param obj_right pointer to the (user-defined part) of an object.
+ * \param flags flags from ao2_callback()
+ *   OBJ_POINTER - if set, 'obj_right', is an object.
+ *   OBJ_KEY - if set, 'obj_right', is a search key item that is not an object.
+ *   OBJ_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object.
+ *
+ * \retval <0 if obj_left < obj_right
+ * \retval =0 if obj_left == obj_right
+ * \retval >0 if obj_left > obj_right
+ */
+typedef int (ao2_sort_fn)(const void *obj_left, const void *obj_right, int flags);
+
 /*! \name Object Containers
  * Here start declarations of containers.
  */
@@ -929,50 +1076,112 @@ struct ao2_container;
  * \return A pointer to a struct container.
  *
  * \note Destructor is set implicitly.
+ * \note This is legacy container creation that is mapped to the new method.
  */
 
-#if defined(REF_DEBUG)
-
 #define ao2_t_container_alloc_options(options, n_buckets, hash_fn, cmp_fn, tag) \
-       __ao2_container_alloc_debug((options), (n_buckets), (hash_fn), (cmp_fn), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__, 1)
+       ao2_t_container_alloc_hash((options), 0, (n_buckets), (hash_fn), NULL, (cmp_fn), (tag))
 #define ao2_container_alloc_options(options, n_buckets, hash_fn, cmp_fn) \
-       __ao2_container_alloc_debug((options), (n_buckets), (hash_fn), (cmp_fn), "",  __FILE__, __LINE__, __PRETTY_FUNCTION__, 1)
+       ao2_container_alloc_hash((options), 0, (n_buckets), (hash_fn), NULL, (cmp_fn))
 
 #define ao2_t_container_alloc(n_buckets, hash_fn, cmp_fn, tag) \
-       __ao2_container_alloc_debug(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__, 1)
+       ao2_t_container_alloc_options(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), (tag))
 #define ao2_container_alloc(n_buckets, hash_fn, cmp_fn) \
-       __ao2_container_alloc_debug(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), "",  __FILE__, __LINE__, __PRETTY_FUNCTION__, 1)
+       ao2_container_alloc_options(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn))
 
-#elif defined(__AST_DEBUG_MALLOC)
+/*!
+ * \brief Allocate and initialize a hash container with the desired number of buckets.
+ *
+ * \details
+ * We allocate space for a struct astobj_container, struct container
+ * and the buckets[] array.
+ *
+ * \param ao2_options Container ao2 object options (See enum ao2_alloc_opts)
+ * \param container_options Container behaviour options (See enum ao2_container_opts)
+ * \param n_buckets Number of buckets for hash
+ * \param hash_fn Pointer to a function computing a hash value. (NULL if everyting goes in first bucket.)
+ * \param sort_fn Pointer to a sort function. (NULL to not sort the buckets.)
+ * \param cmp_fn Pointer to a compare function used by ao2_find. (NULL to match everything)
+ * \param tag used for debugging.
+ *
+ * \return A pointer to a struct container.
+ *
+ * \note Destructor is set implicitly.
+ */
 
-#define ao2_t_container_alloc_options(options, n_buckets, hash_fn, cmp_fn, tag) \
-       __ao2_container_alloc_debug((options), (n_buckets), (hash_fn), (cmp_fn), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__, 0)
-#define ao2_container_alloc_options(options, n_buckets, hash_fn, cmp_fn) \
-       __ao2_container_alloc_debug((options), (n_buckets), (hash_fn), (cmp_fn), "",  __FILE__, __LINE__, __PRETTY_FUNCTION__, 0)
+#if defined(REF_DEBUG)
 
-#define ao2_t_container_alloc(n_buckets, hash_fn, cmp_fn, tag) \
-       __ao2_container_alloc_debug(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__, 0)
-#define ao2_container_alloc(n_buckets, hash_fn, cmp_fn) \
-       __ao2_container_alloc_debug(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn), "",  __FILE__, __LINE__, __PRETTY_FUNCTION__, 0)
+#define ao2_t_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn, tag) \
+       __ao2_container_alloc_hash_debug((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__, 1)
+#define ao2_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn) \
+       __ao2_container_alloc_hash_debug((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn), "",  __FILE__, __LINE__, __PRETTY_FUNCTION__, 1)
+
+#elif defined(__AST_DEBUG_MALLOC)
+
+#define ao2_t_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn, tag) \
+       __ao2_container_alloc_hash_debug((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__, 0)
+#define ao2_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn) \
+       __ao2_container_alloc_hash_debug((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn), "",  __FILE__, __LINE__, __PRETTY_FUNCTION__, 0)
 
 #else
 
-#define ao2_t_container_alloc_options(options, n_buckets, hash_fn, cmp_fn, tag) \
-       __ao2_container_alloc((options), (n_buckets), (hash_fn), (cmp_fn))
-#define ao2_container_alloc_options(options, n_buckets, hash_fn, cmp_fn) \
-       __ao2_container_alloc((options), (n_buckets), (hash_fn), (cmp_fn))
+#define ao2_t_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn, tag) \
+       __ao2_container_alloc_hash((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn))
+#define ao2_container_alloc_hash(ao2_options, container_options, n_buckets, hash_fn, sort_fn, cmp_fn) \
+       __ao2_container_alloc_hash((ao2_options), (container_options), (n_buckets), (hash_fn), (sort_fn), (cmp_fn))
 
-#define ao2_t_container_alloc(n_buckets, hash_fn, cmp_fn, tag) \
-       __ao2_container_alloc(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn))
-#define ao2_container_alloc(n_buckets, hash_fn, cmp_fn) \
-       __ao2_container_alloc(AO2_ALLOC_OPT_LOCK_MUTEX, (n_buckets), (hash_fn), (cmp_fn))
+#endif
+
+struct ao2_container *__ao2_container_alloc_hash(unsigned int ao2_options,
+       unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
+       ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn);
+struct ao2_container *__ao2_container_alloc_hash_debug(unsigned int ao2_options,
+       unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
+       ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
+       const char *tag, const char *file, int line, const char *func, int ref_debug);
+
+/*!
+ * \brief Allocate and initialize a list container.
+ *
+ * \param ao2_options Container ao2 object options (See enum ao2_alloc_opts)
+ * \param container_options Container behaviour options (See enum ao2_container_opts)
+ * \param sort_fn Pointer to a sort function. (NULL if list not sorted.)
+ * \param cmp_fn Pointer to a compare function used by ao2_find. (NULL to match everything)
+ * \param tag used for debugging.
+ *
+ * \return A pointer to a struct container.
+ *
+ * \note Destructor is set implicitly.
+ * \note Implemented as a degenerate hash table.
+ */
+
+#if defined(REF_DEBUG)
+
+#define ao2_t_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn, tag) \
+       __ao2_container_alloc_list_debug((ao2_options), (container_options), (sort_fn), (cmp_fn), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__, 1)
+#define ao2_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn) \
+       __ao2_container_alloc_list_debug((ao2_options), (container_options), (sort_fn), (cmp_fn), "",  __FILE__, __LINE__, __PRETTY_FUNCTION__, 1)
+
+#elif defined(__AST_DEBUG_MALLOC)
+
+#define ao2_t_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn, tag) \
+       __ao2_container_alloc_list_debug((ao2_options), (container_options), (sort_fn), (cmp_fn), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__, 0)
+#define ao2_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn) \
+       __ao2_container_alloc_list_debug((ao2_options), (container_options), (sort_fn), (cmp_fn), "",  __FILE__, __LINE__, __PRETTY_FUNCTION__, 0)
+
+#else
+
+#define ao2_t_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn, tag) \
+       __ao2_container_alloc_list((ao2_options), (container_options), (sort_fn), (cmp_fn))
+#define ao2_container_alloc_list(ao2_options, container_options, sort_fn, cmp_fn) \
+       __ao2_container_alloc_list((ao2_options), (container_options), (sort_fn), (cmp_fn))
 
 #endif
 
-struct ao2_container *__ao2_container_alloc(unsigned int options,
-       unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn);
-struct ao2_container *__ao2_container_alloc_debug(unsigned int options,
-       unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn,
+struct ao2_container *__ao2_container_alloc_list(unsigned int ao2_options,
+       unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn);
+struct ao2_container *__ao2_container_alloc_list_debug(unsigned int ao2_options,
+       unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
        const char *tag, const char *file, int line, const char *func, int ref_debug);
 
 /*! \brief
@@ -1032,6 +1241,40 @@ struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, en
 
 #endif
 
+/*!
+ * \brief Perform an integrity check on the specified container.
+ * \since 12.0.0
+ *
+ * \param self Container to check integrity.
+ * \param flags OBJ_NOLOCK if a lock is already held on the container.
+ *
+ * \retval 0 on success.
+ * \retval -1 on error.
+ */
+int ao2_container_check(struct ao2_container *self, enum search_flags flags);
+
+/*!
+ * \brief Register a container for CLI stats and integrity check.
+ * \since 12.0.0
+ *
+ * \param name Name to register the container under.
+ * \param self Container to register.
+ *
+ * \retval 0 on success.
+ * \retval -1 on error.
+ */
+int ao2_container_register(const char *name, struct ao2_container *self);
+
+/*!
+ * \brief Unregister a container for CLI stats and integrity check.
+ * \since 12.0.0
+ *
+ * \param name Name the container is registered under.
+ *
+ * \return Nothing
+ */
+void ao2_container_unregister(const char *name);
+
 /*@} */
 
 /*! \name Object Management
@@ -1049,8 +1292,8 @@ struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, en
  * \param obj The object to be added.
  * \param tag used for debugging.
  *
- * \retval NULL on errors.
- * \retval !NULL on success.
+ * \retval 0 on errors.
+ * \retval 1 on success.
  *
  * This function inserts an object in a container according its key.
  *
@@ -1095,8 +1338,8 @@ struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, en
 
 #endif
 
-void *__ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func);
-void *__ao2_link(struct ao2_container *c, void *obj_new, int flags);
+int __ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func);
+int __ao2_link(struct ao2_container *c, void *obj_new, int flags);
 
 /*!
  * \brief Remove an object from a container
@@ -1230,7 +1473,8 @@ void *__ao2_unlink(struct ao2_container *c, void *obj, int flags);
  *      OBJ_MULTIPLE            return multiple matches
  *                              Default is no.
  *      OBJ_POINTER             the pointer is an object pointer
- *      OBJ_KEY                 the pointer is to a hashable key
+ *      OBJ_KEY                 the pointer is to a search key
+ *      OBJ_PARTIAL_KEY         the pointer is to a partial search key
  *
  * \note When the returned object is no longer in use, ao2_ref() should
  * be used to free the additional reference possibly created by this function.
@@ -1327,32 +1571,24 @@ void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags fla
  * ao2_iterator to keep track of the current position.
  *
  * Because the navigation is typically done without holding the
- * lock on the container across the loop, objects can be inserted or deleted
- * or moved while we work. As a consequence, there is no guarantee that
- * we manage to touch all the elements in the container, and it is possible
- * that we touch the same object multiple times.
- *
- * However, within the current hash table container, the following is true:
- *  - It is not possible to miss an object in the container while iterating
- *    unless it gets added after the iteration begins and is added to a bucket
- *    that is before the one the current object is in.  In this case, even if
- *    you locked the container around the entire iteration loop, you still would
- *    not see this object, because it would still be waiting on the container
- *    lock so that it can be added.
- *  - It would be extremely rare to see an object twice.  The only way this can
- *    happen is if an object got unlinked from the container and added again
- *    during the same iteration.  Furthermore, when the object gets added back,
- *    it has to be in the current or later bucket for it to be seen again.
- *
- * An iterator must be first initialized with ao2_iterator_init(),
- * then we can use o = ao2_iterator_next() to move from one
- * element to the next. Remember that the object returned by
- * ao2_iterator_next() has its refcount incremented,
- * and the reference must be explicitly released when done with it.
- *
- * In addition, ao2_iterator_init() will hold a reference to the container
- * being iterated, which will be freed when ao2_iterator_destroy() is called
- * to free up the resources used by the iterator (if any).
+ * lock on the container across the loop, objects can be
+ * inserted or deleted or moved while we work.  As a
+ * consequence, there is no guarantee that we manage to touch
+ * all the elements in the container, and it is possible that we
+ * touch the same object multiple times.
+ *
+ * An iterator must be first initialized with
+ * ao2_iterator_init(), then we can use o = ao2_iterator_next()
+ * to move from one element to the next.  Remember that the
+ * object returned by ao2_iterator_next() has its refcount
+ * incremented, and the reference must be explicitly released
+ * when done with it.
+ *
+ * In addition, ao2_iterator_init() will hold a reference to the
+ * container being iterated and the last container node found.
+ * Thes objects will be unreffed when ao2_iterator_destroy() is
+ * called to free up the resources used by the iterator (if
+ * any).
  *
  * Example:
  *
@@ -1369,14 +1605,20 @@ void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags fla
  *     ao2_ref(o, -1);
  *  }
  *
+ *  ao2_iterator_restart(&i);
+ *  while ((o = ao2_iterator_next(&i))) {
+ *     ... do something on o ...
+ *     ao2_ref(o, -1);
+ *  }
+ *
  *  ao2_iterator_destroy(&i);
  *
  *  \endcode
  *
  */
 
-/*! \brief
- * The astobj2 iterator
+/*!
+ * \brief The astobj2 iterator
  *
  * \note You are not supposed to know the internals of an iterator!
  * We would like the iterator to be opaque, unfortunately
@@ -1386,34 +1628,19 @@ void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags fla
  * The iterator has a pointer to the container, and a flags
  * field specifying various things e.g. whether the container
  * should be locked or not while navigating on it.
- * The iterator "points" to the current object, which is identified
- * by three values:
- *
- * - a bucket number;
- * - the object_id, which is also the container version number
- *   when the object was inserted. This identifies the object
- *   uniquely, however reaching the desired object requires
- *   scanning a list.
- * - a pointer, and a container version when we saved the pointer.
- *   If the container has not changed its version number, then we
- *   can safely follow the pointer to reach the object in constant time.
+ * The iterator "points" to the current container node.
  *
  * Details are in the implementation of ao2_iterator_next()
- * A freshly-initialized iterator has bucket=0, version=0.
  */
 struct ao2_iterator {
-       /*! the container */
+       /*! The container (Has a reference) */
        struct ao2_container *c;
-       /*! operation flags */
+       /*! Last container node (Has a reference) */
+       void *last_node;
+       /*! Nonzero if the iteration has completed. */
+       int complete;
+       /*! operation flags (enum ao2_iterator_flags) */
        int flags;
-       /*! current bucket */
-       int bucket;
-       /*! container version */
-       unsigned int c_version;
-       /*! pointer to the current object */
-       void *obj;
-       /*! container version when the object was created */
-       unsigned int version;
 };
 
 /*! Flags that can be passed to ao2_iterator_init() to modify the behavior
@@ -1431,7 +1658,10 @@ enum ao2_iterator_flags {
         * to the original locked state.
         *
         * \note Only use this flag if the ao2_container is manually
-        * locked already.
+        * locked already.  You should hold the lock until after
+        * ao2_iterator_destroy().  If you must release the lock then
+        * you must at least hold the lock whenever you call an
+        * ao2_iterator_xxx function with this iterator.
         */
        AO2_ITERATOR_DONTLOCK = (1 << 0),
        /*!
@@ -1445,13 +1675,25 @@ enum ao2_iterator_flags {
         * from the container.
         */
        AO2_ITERATOR_UNLINK = (1 << 2),
+       /*!
+        * Iterate in descending order (Last to first container object)
+        * (Otherwise ascending order)
+        *
+        * \note Other traversal orders such as pre-order and post-order
+        * do not make sense because they require the container
+        * structure to be static during the traversal.  Iterators just
+        * about guarantee that is not going to happen because the
+        * container is allowed to change by other threads during the
+        * iteration.
+        */
+       AO2_ITERATOR_DESCENDING = (1 << 3),
 };
 
 /*!
  * \brief Create an iterator for a container
  *
  * \param c the container
- * \param flags one or more flags from ao2_iterator_flags
+ * \param flags one or more flags from ao2_iterator_flags.
  *
  * \retval the constructed iterator
  *
@@ -1461,7 +1703,6 @@ enum ao2_iterator_flags {
  *       allocated on the stack or on the heap.
  *
  * This function will take a reference on the container being iterated.
- *
  */
 struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags);
 
@@ -1474,13 +1715,13 @@ struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags);
  *
  * This function will release the container reference held by the iterator
  * and any other resources it may be holding.
- *
  */
 #if defined(TEST_FRAMEWORK)
 void ao2_iterator_destroy(struct ao2_iterator *iter) __attribute__((noinline));
 #else
 void ao2_iterator_destroy(struct ao2_iterator *iter);
-#endif
+#endif /* defined(TEST_FRAMEWORK) */
+
 #ifdef REF_DEBUG
 
 #define ao2_t_iterator_next(iter, tag) __ao2_iterator_next_debug((iter), (tag),  __FILE__, __LINE__, __PRETTY_FUNCTION__)
@@ -1496,6 +1737,19 @@ void ao2_iterator_destroy(struct ao2_iterator *iter);
 void *__ao2_iterator_next_debug(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func);
 void *__ao2_iterator_next(struct ao2_iterator *iter);
 
+/*!
+ * \brief Restart an iteration.
+ *
+ * \param iter the iterator to restart
+ *
+ * \note A restart is not going to have any effect if the
+ * iterator was created with the AO2_ITERATOR_UNLINK flag.  Any
+ * previous objects returned were removed from the container.
+ *
+ * \retval none
+ */
+void ao2_iterator_restart(struct ao2_iterator *iter);
+
 /* extra functions */
 void ao2_bt(void);     /* backtrace */
 
index 176ea5a..9b5f842 100644 (file)
  * at the top of the source tree.
  */
 
-/*
- * Function implementing astobj2 objects.
+/*! \file
+ *
+ * \brief Functions implementing astobj2 objects.
+ *
+ * \author Richard Mudgett <rmudgett@digium.com>
  */
 
 /*** MODULEINFO
@@ -28,7 +31,7 @@ ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
 
 #include "asterisk/_private.h"
 #include "asterisk/astobj2.h"
-#include "asterisk/linkedlists.h"
+#include "asterisk/dlinkedlists.h"
 #include "asterisk/utils.h"
 #include "asterisk/cli.h"
 #define REF_FILE "/tmp/refs"
@@ -161,11 +164,6 @@ static inline struct astobj2 *INTERNAL_OBJ(void *user_data)
        return p;
 }
 
-enum ao2_callback_type {
-       DEFAULT,
-       WITH_DATA,
-};
-
 /*!
  * \brief convert from a pointer _p to an astobj2 object
  *
@@ -181,6 +179,7 @@ int __ao2_lock(void *user_data, enum ao2_lock_req lock_how, const char *file, co
        int res = 0;
 
        if (obj == NULL) {
+               ast_assert(0);
                return -1;
        }
 
@@ -239,6 +238,7 @@ int __ao2_unlock(void *user_data, const char *file, const char *func, int line,
        int current_value;
 
        if (obj == NULL) {
+               ast_assert(0);
                return -1;
        }
 
@@ -287,6 +287,7 @@ int __ao2_trylock(void *user_data, enum ao2_lock_req lock_how, const char *file,
        int res = 0;
 
        if (obj == NULL) {
+               ast_assert(0);
                return -1;
        }
 
@@ -406,6 +407,7 @@ void *ao2_object_get_lockaddr(void *user_data)
        struct astobj2_lock *obj_mutex;
 
        if (obj == NULL) {
+               ast_assert(0);
                return NULL;
        }
 
@@ -429,6 +431,7 @@ static int internal_ao2_ref(void *user_data, int delta, const char *file, int li
        int ret;
 
        if (obj == NULL) {
+               ast_assert(0);
                return -1;
        }
 
@@ -513,8 +516,10 @@ int __ao2_ref_debug(void *user_data, int delta, const char *tag, const char *fil
 {
        struct astobj2 *obj = INTERNAL_OBJ(user_data);
 
-       if (obj == NULL)
+       if (obj == NULL) {
+               ast_assert(0);
                return -1;
+       }
 
        if (delta != 0) {
                FILE *refo = fopen(REF_FILE, "a");
@@ -539,6 +544,13 @@ int __ao2_ref(void *user_data, int delta)
        return internal_ao2_ref(user_data, delta, __FILE__, __LINE__, __FUNCTION__);
 }
 
+void ao2_cleanup(void *obj)
+{
+       if (obj) {
+               ao2_ref(obj, -1);
+       }
+}
+
 static void *internal_ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options, const char *file, int line, const char *func)
 {
        /* allocation */
@@ -645,10 +657,12 @@ void __ao2_global_obj_release(struct ao2_global_obj *holder, const char *tag, co
        if (!holder) {
                /* For sanity */
                ast_log(LOG_ERROR, "Must be called with a global object!\n");
+               ast_assert(0);
                return;
        }
        if (__ast_rwlock_wrlock(file, line, func, &holder->lock, name)) {
                /* Could not get the write lock. */
+               ast_assert(0);
                return;
        }
 
@@ -668,10 +682,12 @@ void *__ao2_global_obj_replace(struct ao2_global_obj *holder, void *obj, const c
        if (!holder) {
                /* For sanity */
                ast_log(LOG_ERROR, "Must be called with a global object!\n");
+               ast_assert(0);
                return NULL;
        }
        if (__ast_rwlock_wrlock(file, line, func, &holder->lock, name)) {
                /* Could not get the write lock. */
+               ast_assert(0);
                return NULL;
        }
 
@@ -705,11 +721,13 @@ void *__ao2_global_obj_ref(struct ao2_global_obj *holder, const char *tag, const
        if (!holder) {
                /* For sanity */
                ast_log(LOG_ERROR, "Must be called with a global object!\n");
+               ast_assert(0);
                return NULL;
        }
 
        if (__ast_rwlock_rdlock(file, line, func, &holder->lock, name)) {
                /* Could not get the read lock. */
+               ast_assert(0);
                return NULL;
        }
 
@@ -723,192 +741,339 @@ void *__ao2_global_obj_ref(struct ao2_global_obj *holder, const char *tag, const
        return obj;
 }
 
-/* internal callback to destroy a container. */
-static void container_destruct(void *c);
+enum ao2_callback_type {
+       AO2_CALLBACK_DEFAULT,
+       AO2_CALLBACK_WITH_DATA,
+};
+
+enum ao2_container_insert {
+       /*! The node was inserted into the container. */
+       AO2_CONTAINER_INSERT_NODE_INSERTED,
+       /*! The node object replaced an existing node object. */
+       AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED,
+       /*! The node was rejected (duplicate). */
+       AO2_CONTAINER_INSERT_NODE_REJECTED,
+};
 
-/* internal callback to destroy a container. */
-static void container_destruct_debug(void *c);
+enum ao2_container_rtti {
+       /*! This is a hash container */
+       AO2_CONTAINER_RTTI_HASH,
+};
 
 /*!
- * A structure to create a linked list of entries,
- * used within a bucket.
- * XXX \todo this should be private to the container code
+ * \brief Generic container node.
+ *
+ * \details This is the base container node type that contains
+ * values common to all container nodes.
  */
-struct bucket_entry {
-       AST_LIST_ENTRY(bucket_entry) entry;
-       int version;
-       struct astobj2 *astobj;/* pointer to internal data */
+struct ao2_container_node {
+       /*! Stored object in node. */
+       void *obj;
+       /*! Container holding the node.  (Does not hold a reference.) */
+       struct ao2_container *my_container;
+       /*! TRUE if the node is linked into the container. */
+       unsigned int is_linked:1;
 };
 
-/* each bucket in the container is a tailq. */
-AST_LIST_HEAD_NOLOCK(bucket, bucket_entry);
+/*!
+ * \brief Destroy this container.
+ *
+ * \param self Container to operate upon.
+ *
+ * \return Nothing
+ */
+typedef void (*ao2_container_destroy_fn)(struct ao2_container *self);
 
 /*!
- * A container; stores the hash and callback functions, information on
- * the size, the hash bucket heads, and a version number, starting at 0
- * (for a newly created, empty container)
- * and incremented every time an object is inserted or deleted.
- * The assumption is that an object is never moved in a container,
- * but removed and readded with the new number.
- * The version number is especially useful when implementing iterators.
- * In fact, we can associate a unique, monotonically increasing number to
- * each object, which means that, within an iterator, we can store the
- * version number of the current object, and easily look for the next one,
- * which is the next one in the list with a higher number.
- * Since all objects have a version >0, we can use 0 as a marker for
- * 'we need the first object in the bucket'.
- *
- * \todo Linking and unlink objects is typically expensive, as it
- * involves a malloc() of a small object which is very inefficient.
- * To optimize this, we allocate larger arrays of bucket_entry's
- * when we run out of them, and then manage our own freelist.
- * This will be more efficient as we can do the freelist management while
- * we hold the lock (that we need anyways).
+ * \brief Create an empty copy of this container.
+ *
+ * \param self Container to operate upon.
+ *
+ * \retval empty-container on success.
+ * \retval NULL on error.
  */
-struct ao2_container {
-       ao2_hash_fn *hash_fn;
-       ao2_callback_fn *cmp_fn;
-       int n_buckets;
-       /*! Number of elements in the container */
-       int elements;
-       /*! described above */
-       int version;
-       /*! variable size */
-       struct bucket buckets[0];
-};
+typedef struct ao2_container *(*ao2_container_alloc_empty_clone_fn)(struct ao2_container *self);
 
 /*!
- * \brief always zero hash function
+ * \brief Create an empty copy of this container. (Debug version)
  *
- * it is convenient to have a hash function that always returns 0.
- * This is basically used when we want to have a container that is
- * a simple linked list.
+ * \param self Container to operate upon.
+ * \param tag used for debugging.
+ * \param file Debug file name invoked from
+ * \param line Debug line invoked from
+ * \param func Debug function name invoked from
+ * \param ref_debug TRUE if to output a debug reference message.
  *
- * \returns 0
+ * \retval empty-container on success.
+ * \retval NULL on error.
  */
-static int hash_zero(const void *user_obj, const int flags)
-{
-       return 0;
-}
+typedef struct ao2_container *(*ao2_container_alloc_empty_clone_debug_fn)(struct ao2_container *self, const char *tag, const char *file, int line, const char *func, int ref_debug);
 
-/*
- * A container is just an object, after all!
+/*!
+ * \brief Create a new container node.
+ *
+ * \param self Container to operate upon.
+ * \param obj_new Object to put into the node.
+ * \param tag used for debugging.
+ * \param file Debug file name invoked from
+ * \param line Debug line invoked from
+ * \param func Debug function name invoked from
+ *
+ * \retval initialized-node on success.
+ * \retval NULL on error.
  */
-static struct ao2_container *internal_ao2_container_alloc(struct ao2_container *c,
-       unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn)
-{
-       /* XXX maybe consistency check on arguments ? */
-       /* compute the container size */
+typedef struct ao2_container_node *(*ao2_container_new_node_fn)(struct ao2_container *self, void *obj_new, const char *tag, const char *file, int line, const char *func);
 
-       if (!c) {
-               return NULL;
-       }
+/*!
+ * \brief Insert a node into this container.
+ *
+ * \param self Container to operate upon.
+ * \param node Container node to insert into the container.
+ *
+ * \return enum ao2_container_insert value.
+ */
+typedef enum ao2_container_insert (*ao2_container_insert_fn)(struct ao2_container *self, struct ao2_container_node *node);
 
-       c->version = 1; /* 0 is a reserved value here */
-       c->n_buckets = hash_fn ? n_buckets : 1;
-       c->hash_fn = hash_fn ? hash_fn : hash_zero;
-       c->cmp_fn = cmp_fn;
+/*!
+ * \brief Find the first container node in a traversal.
+ *
+ * \param self Container to operate upon.
+ * \param flags search_flags to control traversing the container
+ * \param arg Comparison callback arg parameter.
+ * \param v_state Traversal state to restart container traversal.
+ *
+ * \retval node-ptr of found node (Reffed).
+ * \retval NULL when no node found.
+ */
+typedef struct ao2_container_node *(*ao2_container_find_first_fn)(struct ao2_container *self, enum search_flags flags, void *arg, void *v_state);
 
-#ifdef AO2_DEBUG
-       ast_atomic_fetchadd_int(&ao2.total_containers, 1);
-#endif
+/*!
+ * \brief Find the next container node in a traversal.
+ *
+ * \param self Container to operate upon.
+ * \param v_state Traversal state to restart container traversal.
+ * \param prev Previous node returned by the traversal search functions.
+ *    The ref ownership is passed back to this function.
+ *
+ * \retval node-ptr of found node (Reffed).
+ * \retval NULL when no node found.
+ */
+typedef struct ao2_container_node *(*ao2_container_find_next_fn)(struct ao2_container *self, void *v_state, struct ao2_container_node *prev);
 
-       return c;
-}
+/*!
+ * \brief Cleanup the container traversal state.
+ *
+ * \param v_state Traversal state to cleanup.
+ *
+ * \return Nothing
+ */
+typedef void (*ao2_container_find_cleanup_fn)(void *v_state);
 
-struct ao2_container *__ao2_container_alloc_debug(unsigned int options,
-       unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn,
-       const char *tag, const char *file, int line, const char *func, int ref_debug)
-{
-       /* XXX maybe consistency check on arguments ? */
-       /* compute the container size */
-       unsigned int num_buckets = hash_fn ? n_buckets : 1;
-       size_t container_size = sizeof(struct ao2_container) + num_buckets * sizeof(struct bucket);
-       struct ao2_container *c = __ao2_alloc_debug(container_size, container_destruct_debug, options, tag, file, line, func, ref_debug);
+/*!
+ * \brief Find the next non-empty iteration node in the container.
+ *
+ * \param self Container to operate upon.
+ * \param prev Previous node returned by the iterator.
+ * \param flags search_flags to control iterating the container.
+ *   Only AO2_ITERATOR_DESCENDING is useful by the method.
+ *
+ * \note The container is already locked.
+ *
+ * \retval node on success.
+ * \retval NULL on error or no more nodes in the container.
+ */
+typedef struct ao2_container_node *(*ao2_iterator_next_fn)(struct ao2_container *self, struct ao2_container_node *prev, enum ao2_iterator_flags flags);
 
-       return internal_ao2_container_alloc(c, num_buckets, hash_fn, cmp_fn);
-}
+/*!
+ * \brief Display statistics of the specified container.
+ *
+ * \param self Container to display statistics.
+ * \param fd File descriptor to send output.
+ * \param prnt Print output callback function to use.
+ *
+ * \note The container is already locked for reading.
+ *
+ * \return Nothing
+ */
+typedef void (*ao2_container_statistics)(struct ao2_container *self, int fd, void (*prnt)(int fd, const char *fmt, ...) __attribute__((format(printf, 2, 3))));
 
-struct ao2_container *__ao2_container_alloc(unsigned int options,
-       unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_callback_fn *cmp_fn)
-{
-       /* XXX maybe consistency check on arguments ? */
-       /* compute the container size */
-       const unsigned int num_buckets = hash_fn ? n_buckets : 1;
-       size_t container_size = sizeof(struct ao2_container) + num_buckets * sizeof(struct bucket);
-       struct ao2_container *c = __ao2_alloc(container_size, container_destruct, options);
+/*!
+ * \brief Perform an integrity check on the specified container.
+ *
+ * \param self Container to check integrity.
+ *
+ * \note The container is already locked for reading.
+ *
+ * \retval 0 on success.
+ * \retval -1 on error.
+ */
+typedef int (*ao2_container_integrity)(struct ao2_container *self);
+
+/*! Container virtual methods template. */
+struct ao2_container_methods {
+       /*! Run Time Type Identification */
+       enum ao2_container_rtti type;
+       /*! Destroy this container. */
+       ao2_container_destroy_fn destroy;
+       /*! \brief Create an empty copy of this container. */
+       ao2_container_alloc_empty_clone_fn alloc_empty_clone;
+       /*! \brief Create an empty copy of this container. (Debug version) */
+       ao2_container_alloc_empty_clone_debug_fn alloc_empty_clone_debug;
+       /*! Create a new container node. */
+       ao2_container_new_node_fn new_node;
+       /*! Insert a node into this container. */
+       ao2_container_insert_fn insert;
+       /*! Traverse the container, find the first node. */
+       ao2_container_find_first_fn traverse_first;
+       /*! Traverse the container, find the next node. */
+       ao2_container_find_next_fn traverse_next;
+       /*! Traverse the container, cleanup state. */
+       ao2_container_find_cleanup_fn traverse_cleanup;
+       /*! Find the next iteration element in the container. */
+       ao2_iterator_next_fn iterator_next;
+#if defined(AST_DEVMODE)
+       /*! Display container debug statistics. (Method for debug purposes) */
+       ao2_container_statistics stats;
+       /*! Perform an integrity check on the container. (Method for debug purposes) */
+       ao2_container_integrity integrity;
+#endif /* defined(AST_DEVMODE) */
+};
 
-       return internal_ao2_container_alloc(c, num_buckets, hash_fn, cmp_fn);
-}
+/*!
+ * \brief Generic container type.
+ *
+ * \details This is the base container type that contains values
+ * common to all container types.
+ *
+ * \todo Linking and unlinking container objects is typically
+ * expensive, as it involves a malloc()/free() of a small object
+ * which is very inefficient.  To optimize this, we can allocate
+ * larger arrays of container nodes when we run out of them, and
+ * then manage our own freelist.  This will be more efficient as
+ * we can do the freelist management while we hold the lock
+ * (that we need anyway).
+ */
+struct ao2_container {
+       /*! Container virtual method table. */
+       const struct ao2_container_methods *v_table;
+       /*! Container sort function if the container is sorted. */
+       ao2_sort_fn *sort_fn;
+       /*! Container traversal matching function for ao2_find. */
+       ao2_callback_fn *cmp_fn;
+       /*! The container option flags */
+       uint32_t options;
+       /*! Number of elements in the container. */
+       int elements;
+#if defined(AST_DEVMODE)
+       /*! Number of nodes in the container. */
+       int nodes;
+       /*! Maximum number of empty nodes in the container. (nodes - elements) */
+       int max_empty_nodes;
+#endif /* defined(AST_DEVMODE) */
+       /*!
+        * \brief TRUE if the container is being destroyed.
+        *
+        * \note The destruction traversal should override any requested
+        * search order to do the most efficient order for destruction.
+        *
+        * \note There should not be any empty nodes in the container
+        * during destruction.  If there are then an error needs to be
+        * issued about container node reference leaks.
+        */
+       unsigned int destroying:1;
+};
 
 /*!
  * return the number of elements in the container
  */
 int ao2_container_count(struct ao2_container *c)
 {
-       return c->elements;
+       return ast_atomic_fetchadd_int(&c->elements, 0);
 }
 
-/*
- * link an object to a container
+#if defined(AST_DEVMODE)
+static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node);
+static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node);
+#endif /* defined(AST_DEVMODE) */
+
+/*!
+ * \internal
+ * \brief Link an object into this container.  (internal)
+ *
+ * \param self Container to operate upon.
+ * \param obj_new Object to insert into the container.
+ * \param flags search_flags to control linking the object.  (OBJ_NOLOCK)
+ * \param tag used for debugging.
+ * \param file Debug file name invoked from
+ * \param line Debug line invoked from
+ * \param func Debug function name invoked from
+ *
+ * \retval 0 on errors.
+ * \retval 1 on success.
  */
-static struct bucket_entry *internal_ao2_link(struct ao2_container *c, void *user_data, int flags, const char *tag, const char *file, int line, const char *func)
+static int internal_ao2_link(struct ao2_container *self, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func)
 {
-       int i;
+       int res;
        enum ao2_lock_req orig_lock;
-       /* create a new list entry */
-       struct bucket_entry *p;
-       struct astobj2 *obj = INTERNAL_OBJ(user_data);
-
-       if (obj == NULL) {
-               return NULL;
-       }
-
-       if (INTERNAL_OBJ(c) == NULL) {
-               return NULL;
-       }
+       struct ao2_container_node *node;
 
-       p = ast_calloc(1, sizeof(*p));
-       if (!p) {
-               return NULL;
+       if (!INTERNAL_OBJ(obj_new) || !INTERNAL_OBJ(self)
+               || !self->v_table || !self->v_table->new_node || !self->v_table->insert) {
+               /* Sanity checks. */
+               ast_assert(0);
+               return 0;
        }
 
-       i = abs(c->hash_fn(user_data, OBJ_POINTER));
-
        if (flags & OBJ_NOLOCK) {
-               orig_lock = adjust_lock(c, AO2_LOCK_REQ_WRLOCK, 1);
+               orig_lock = adjust_lock(self, AO2_LOCK_REQ_WRLOCK, 1);
        } else {
-               ao2_wrlock(c);
+               ao2_wrlock(self);
                orig_lock = AO2_LOCK_REQ_MUTEX;
        }
 
-       i %= c->n_buckets;
-       p->astobj = obj;
-       p->version = ast_atomic_fetchadd_int(&c->version, 1);
-       AST_LIST_INSERT_TAIL(&c->buckets[i], p, entry);
-       ast_atomic_fetchadd_int(&c->elements, 1);
+       res = 0;
+       node = self->v_table->new_node(self, obj_new, tag, file, line, func);
+       if (node) {
+               /* Insert the new node. */
+               switch (self->v_table->insert(self, node)) {
+               case AO2_CONTAINER_INSERT_NODE_INSERTED:
+                       node->is_linked = 1;
+                       ast_atomic_fetchadd_int(&self->elements, 1);
+#if defined(AST_DEVMODE)
+                       ++self->nodes;
+                       switch (self->v_table->type) {
+                       case AO2_CONTAINER_RTTI_HASH:
+                               hash_ao2_link_node_stat(self, node);
+                               break;
+                       }
+#endif /* defined(AST_DEVMODE) */
 
-       if (tag) {
-               __ao2_ref_debug(user_data, +1, tag, file, line, func);
-       } else {
-               __ao2_ref(user_data, +1);
+                       res = 1;
+                       break;
+               case AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED:
+                       res = 1;
+                       /* Fall through */
+               case AO2_CONTAINER_INSERT_NODE_REJECTED:
+                       __ao2_ref(node, -1);
+                       break;
+               }
        }
 
        if (flags & OBJ_NOLOCK) {
-               adjust_lock(c, orig_lock, 0);
+               adjust_lock(self, orig_lock, 0);
        } else {
-               ao2_unlock(c);
+               ao2_unlock(self);
        }
 
-       return p;
+       return res;
 }
 
-void *__ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func)
+int __ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func)
 {
        return internal_ao2_link(c, obj_new, flags, tag, file, line, func);
 }
 
-void *__ao2_link(struct ao2_container *c, void *obj_new, int flags)
+int __ao2_link(struct ao2_container *c, void *obj_new, int flags)
 {
        return internal_ao2_link(c, obj_new, flags, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__);
 }
@@ -928,7 +1093,9 @@ int ao2_match_by_addr(void *user_data, void *arg, int flags)
 void *__ao2_unlink_debug(struct ao2_container *c, void *user_data, int flags,
        const char *tag, const char *file, int line, const char *func)
 {
-       if (INTERNAL_OBJ(user_data) == NULL) {  /* safety check on the argument */
+       if (!INTERNAL_OBJ(user_data)) {
+               /* Sanity checks. */
+               ast_assert(0);
                return NULL;
        }
 
@@ -940,7 +1107,9 @@ void *__ao2_unlink_debug(struct ao2_container *c, void *user_data, int flags,
 
 void *__ao2_unlink(struct ao2_container *c, void *user_data, int flags)
 {
-       if (INTERNAL_OBJ(user_data) == NULL) {  /* safety check on the argument */
+       if (!INTERNAL_OBJ(user_data)) {
+               /* Sanity checks. */
+               ast_assert(0);
                return NULL;
        }
 
@@ -966,27 +1135,51 @@ static int cb_true_data(void *user_data, void *arg, void *data, int flags)
        return CMP_MATCH;
 }
 
+/*! Allow enough room for container specific traversal state structs */
+#define AO2_TRAVERSAL_STATE_SIZE       100
+
 /*!
- * Browse the container using different stategies accoding the flags.
- * \return Is a pointer to an object or to a list of object if OBJ_MULTIPLE is
- * specified.
- * Luckily, for debug purposes, the added args (tag, file, line, func)
- * aren't an excessive load to the system, as the callback should not be
- * called as often as, say, the ao2_ref func is called.
+ * \internal
+ * \brief Traverse the container.  (internal)
+ *
+ * \param self Container to operate upon.
+ * \param flags search_flags to control traversing the container
+ * \param cb_fn Comparison callback function.
+ * \param arg Comparison callback arg parameter.
+ * \param data Data comparison callback data parameter.
+ * \param type Type of comparison callback cb_fn.
+ * \param tag used for debugging.
+ * \param file Debug file name invoked from
+ * \param line Debug line invoked from
+ * \param func Debug function name invoked from
+ *
+ * \retval NULL on failure or no matching object found.
+ *
+ * \retval object found if OBJ_MULTIPLE is not set in the flags
+ * parameter.
+ *
+ * \retval ao2_iterator pointer if OBJ_MULTIPLE is set in the
+ * flags parameter.  The iterator must be destroyed with
+ * ao2_iterator_destroy() when the caller no longer needs it.
  */
-static void *internal_ao2_callback(struct ao2_container *c, enum search_flags flags,
-       void *cb_fn, void *arg, void *data, enum ao2_callback_type type, const char *tag,
-       const char *file, int line, const char *func)
+static void *internal_ao2_traverse(struct ao2_container *self, enum search_flags flags,
+       void *cb_fn, void *arg, void *data, enum ao2_callback_type type,
+       const char *tag, const char *file, int line, const char *func)
 {
-       int i, start, last;     /* search boundaries */
-       enum ao2_lock_req orig_lock;
-       void *ret = NULL;
+       void *ret;
        ao2_callback_fn *cb_default = NULL;
        ao2_callback_data_fn *cb_withdata = NULL;
+       struct ao2_container_node *node;
+       void *traversal_state;
+
+       enum ao2_lock_req orig_lock;
        struct ao2_container *multi_container = NULL;
        struct ao2_iterator *multi_iterator = NULL;
 
-       if (INTERNAL_OBJ(c) == NULL) {  /* safety check on the argument */
+       if (!INTERNAL_OBJ(self) || !self->v_table || !self->v_table->traverse_first
+               || !self->v_table->traverse_next) {
+               /* Sanity checks. */
+               ast_assert(0);
                return NULL;
        }
 
@@ -1003,7 +1196,8 @@ static void *internal_ao2_callback(struct ao2_container *c, enum search_flags fl
                 * is destroyed, the container will be automatically
                 * destroyed as well.
                 */
-               multi_container = __ao2_container_alloc(AO2_ALLOC_OPT_LOCK_NOLOCK, 1, NULL, NULL);
+               multi_container = __ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_NOLOCK, 0, NULL,
+                       NULL);
                if (!multi_container) {
                        return NULL;
                }
@@ -1013,159 +1207,171 @@ static void *internal_ao2_callback(struct ao2_container *c, enum search_flags fl
                }
        }
 
-       /* override the match function if necessary */
-       if (cb_fn == NULL) { /* if NULL, match everything */
-               if (type == WITH_DATA) {
+       if (!cb_fn) {
+               /* Match everything if no callback match function provided. */
+               if (type == AO2_CALLBACK_WITH_DATA) {
                        cb_withdata = cb_true_data;
                } else {
                        cb_default = cb_true;
                }
        } else {
-               /* We do this here to avoid the per object casting penalty (even though
-                  that is probably optimized away anyway). */
-               if (type == WITH_DATA) {
+               /*
+                * We do this here to avoid the per object casting penalty (even
+                * though that is probably optimized away anyway).
+                */
+               if (type == AO2_CALLBACK_WITH_DATA) {
                        cb_withdata = cb_fn;
                } else {
                        cb_default = cb_fn;
                }
        }
 
-       /*
-        * XXX this can be optimized.
-        * If we have a hash function and lookup by pointer,
-        * run the hash function. Otherwise, scan the whole container
-        * (this only for the time being. We need to optimize this.)
-        */
-       if ((flags & (OBJ_POINTER | OBJ_KEY))) {
-               /* we know hash can handle this case */
-               start = i = c->hash_fn(arg, flags & (OBJ_POINTER | OBJ_KEY)) % c->n_buckets;
-       } else {
-               /* don't know, let's scan all buckets */
-               start = i = -1;         /* XXX this must be fixed later. */
-       }
-
-       /* determine the search boundaries: i..last-1 */
-       if (i < 0) {
-               start = i = 0;
-               last = c->n_buckets;
-       } else if ((flags & OBJ_CONTINUE)) {
-               last = c->n_buckets;
-       } else {
-               last = i + 1;
-       }
-
        /* avoid modifications to the content */
        if (flags & OBJ_NOLOCK) {
                if (flags & OBJ_UNLINK) {
-                       orig_lock = adjust_lock(c, AO2_LOCK_REQ_WRLOCK, 1);
+                       orig_lock = adjust_lock(self, AO2_LOCK_REQ_WRLOCK, 1);
                } else {
-                       orig_lock = adjust_lock(c, AO2_LOCK_REQ_RDLOCK, 1);
+                       orig_lock = adjust_lock(self, AO2_LOCK_REQ_RDLOCK, 1);
                }
        } else {
                orig_lock = AO2_LOCK_REQ_MUTEX;
                if (flags & OBJ_UNLINK) {
-                       ao2_wrlock(c);
+                       ao2_wrlock(self);
                } else {
-                       ao2_rdlock(c);
+                       ao2_rdlock(self);
                }
        }
 
-       for (; i < last ; i++) {
-               /* scan the list with prev-cur pointers */
-               struct bucket_entry *cur;
-
-               AST_LIST_TRAVERSE_SAFE_BEGIN(&c->buckets[i], cur, entry) {
-                       int match = (CMP_MATCH | CMP_STOP);
+       /* Create a buffer for the traversal state. */
+       traversal_state = alloca(AO2_TRAVERSAL_STATE_SIZE);
 
-                       if (type == WITH_DATA) {
-                               match &= cb_withdata(EXTERNAL_OBJ(cur->astobj), arg, data, flags);
-                       } else {
-                               match &= cb_default(EXTERNAL_OBJ(cur->astobj), arg, flags);
-                       }
+       ret = NULL;
+       for (node = self->v_table->traverse_first(self, flags, arg, traversal_state);
+               node;
+               node = self->v_table->traverse_next(self, traversal_state, node)) {
+               int match;
 
-                       /* we found the object, performing operations according flags */
-                       if (match == 0) {       /* no match, no stop, continue */
-                               continue;
-                       } else if (match == CMP_STOP) { /* no match but stop, we are done */
-                               i = last;
-                               break;
-                       }
+               /* Visit the current node. */
+               match = (CMP_MATCH | CMP_STOP);
+               if (type == AO2_CALLBACK_WITH_DATA) {
+                       match &= cb_withdata(node->obj, arg, data, flags);
+               } else {
+                       match &= cb_default(node->obj, arg, flags);
+               }
+               if (match == 0) {
+                       /* no match, no stop, continue */
+                       continue;
+               }
+               if (match == CMP_STOP) {
+                       /* no match but stop, we are done */
+                       break;
+               }
 
-                       /* we have a match (CMP_MATCH) here */
-                       if (!(flags & OBJ_NODATA)) {    /* if must return the object, record the value */
-                               /* it is important to handle this case before the unlink */
-                               ret = EXTERNAL_OBJ(cur->astobj);
-                               if (!(flags & (OBJ_UNLINK | OBJ_MULTIPLE))) {
+               /*
+                * CMP_MATCH is set here
+                *
+                * we found the object, performing operations according to flags
+                */
+               if (node->obj) {
+                       /* The object is still in the container. */
+                       if (!(flags & OBJ_NODATA)) {
+                               /*
+                                * We are returning the object, record the value.  It is
+                                * important to handle this case before the unlink.
+                                */
+                               if (multi_container) {
+                                       /*
+                                        * Link the object into the container that will hold the
+                                        * results.
+                                        */
                                        if (tag) {
-                                               __ao2_ref_debug(ret, 1, tag, file, line, func);
+                                               __ao2_link_debug(multi_container, node->obj, flags,
+                                                       tag, file, line, func);
                                        } else {
-                                               __ao2_ref(ret, 1);
+                                               __ao2_link(multi_container, node->obj, flags);
                                        }
-                               }
-                       }
-
-                       /* If we are in OBJ_MULTIPLE mode and OBJ_NODATA is off,
-                        * link the object into the container that will hold the results.
-                        */
-                       if (ret && (multi_container != NULL)) {
-                               if (tag) {
-                                       __ao2_link_debug(multi_container, ret, flags, tag, file, line, func);
                                } else {
-                                       __ao2_link(multi_container, ret, flags);
+                                       ret = node->obj;
+                                       /* Returning a single object. */
+                                       if (!(flags & OBJ_UNLINK)) {
+                                               /*
+                                                * Bump the ref count since we are not going to unlink and
+                                                * transfer the container's object ref to the returned object.
+                                                */
+                                               if (tag) {
+                                                       __ao2_ref_debug(ret, 1, tag, file, line, func);
+                                               } else {
+                                                       __ao2_ref(ret, 1);
+                                               }
+                                       }
                                }
-                               ret = NULL;
                        }
 
-                       if (flags & OBJ_UNLINK) {       /* must unlink */
-                               /* we are going to modify the container, so update version */
-                               ast_atomic_fetchadd_int(&c->version, 1);
-                               AST_LIST_REMOVE_CURRENT(entry);
+                       if (flags & OBJ_UNLINK) {
                                /* update number of elements */
-                               ast_atomic_fetchadd_int(&c->elements, -1);
-
-                               /* - When unlinking and not returning the result, (OBJ_NODATA), the ref from the container
-                                * must be decremented.
-                                * - When unlinking with OBJ_MULTIPLE the ref from the original container
-                                * must be decremented regardless if OBJ_NODATA is used. This is because the result is
-                                * returned in a new container that already holds its own ref for the object. If the ref
-                                * from the original container is not accounted for here a memory leak occurs. */
-                               if (flags & (OBJ_NODATA | OBJ_MULTIPLE)) {
-                                       if (tag)
-                                               __ao2_ref_debug(EXTERNAL_OBJ(cur->astobj), -1, tag, file, line, func);
-                                       else
-                                               __ao2_ref(EXTERNAL_OBJ(cur->astobj), -1);
+                               ast_atomic_fetchadd_int(&self->elements, -1);
+#if defined(AST_DEVMODE)
+                               {
+                                       int empty = self->nodes - self->elements;
+
+                                       if (self->max_empty_nodes < empty) {
+                                               self->max_empty_nodes = empty;
+                                       }
                                }
-                               ast_free(cur);  /* free the link record */
-                       }
+                               switch (self->v_table->type) {
+                               case AO2_CONTAINER_RTTI_HASH:
+                                       hash_ao2_unlink_node_stat(self, node);
+                                       break;
+                               }
+#endif /* defined(AST_DEVMODE) */
+
+                               /*
+                                * - When unlinking and not returning the result, OBJ_NODATA is
+                                * set, the ref from the container must be decremented.
+                                *
+                                * - When unlinking with a multi_container the ref from the
+                                * original container must be decremented.  This is because the
+                                * result is returned in a new container that already holds its
+                                * own ref for the object.
+                                *
+                                * If the ref from the original container is not accounted for
+                                * here a memory leak occurs.
+                                */
+                               if (multi_container || (flags & OBJ_NODATA)) {
+                                       if (tag) {
+                                               __ao2_ref_debug(node->obj, -1, tag, file, line, func);
+                                       } else {
+                                               __ao2_ref(node->obj, -1);
+                                       }
+                               }
+                               node->obj = NULL;
 
-                       if ((match & CMP_STOP) || !(flags & OBJ_MULTIPLE)) {
-                               /* We found our only (or last) match, so force an exit from
-                                  the outside loop. */
-                               i = last;
-                               break;
+                               /* Unref the node from the container. */
+                               __ao2_ref(node, -1);
                        }
                }
-               AST_LIST_TRAVERSE_SAFE_END;
 
-               if (ret) {
+               if ((match & CMP_STOP) || !(flags & OBJ_MULTIPLE)) {
+                       /* We found our only (or last) match, so we are done */
                        break;
                }
-
-               if (i == c->n_buckets - 1 && (flags & OBJ_POINTER) && (flags & OBJ_CONTINUE)) {
-                       /* Move to the beginning to ensure we check every bucket */
-                       i = -1;
-                       last = start;
-               }
+       }
+       if (self->v_table->traverse_cleanup) {
+               self->v_table->traverse_cleanup(traversal_state);
+       }
+       if (node) {
+               /* Unref the node from self->v_table->traverse_first/traverse_next() */
+               __ao2_ref(node, -1);
        }
 
        if (flags & OBJ_NOLOCK) {
-               adjust_lock(c, orig_lock, 0);
+               adjust_lock(self, orig_lock, 0);
        } else {
-               ao2_unlock(c);
+               ao2_unlock(self);
        }
 
        /* if multi_container was created, we are returning multiple objects */
-       if (multi_container != NULL) {
+       if (multi_container) {
                *multi_iterator = ao2_iterator_init(multi_container,
                        AO2_ITERATOR_UNLINK | AO2_ITERATOR_MALLOCD);
                ao2_ref(multi_container, -1);
@@ -1179,26 +1385,26 @@ void *__ao2_callback_debug(struct ao2_container *c, enum search_flags flags,
        ao2_callback_fn *cb_fn, void *arg, const char *tag, const char *file, int line,
        const char *func)
 {
-       return internal_ao2_callback(c,flags, cb_fn, arg, NULL, DEFAULT, tag, file, line, func);
+       return internal_ao2_traverse(c, flags, cb_fn, arg, NULL, AO2_CALLBACK_DEFAULT, tag, file, line, func);
 }
 
 void *__ao2_callback(struct ao2_container *c, enum search_flags flags,
        ao2_callback_fn *cb_fn, void *arg)
 {
-       return internal_ao2_callback(c,flags, cb_fn, arg, NULL, DEFAULT, NULL, NULL, 0, NULL);
+       return internal_ao2_traverse(c, flags, cb_fn, arg, NULL, AO2_CALLBACK_DEFAULT, NULL, NULL, 0, NULL);
 }
 
 void *__ao2_callback_data_debug(struct ao2_container *c, enum search_flags flags,
        ao2_callback_data_fn *cb_fn, void *arg, void *data, const char *tag, const char *file,
        int line, const char *func)
 {
-       return internal_ao2_callback(c, flags, cb_fn, arg, data, WITH_DATA, tag, file, line, func);
+       return internal_ao2_traverse(c, flags, cb_fn, arg, data, AO2_CALLBACK_WITH_DATA, tag, file, line, func);
 }
 
 void *__ao2_callback_data(struct ao2_container *c, enum search_flags flags,
        ao2_callback_data_fn *cb_fn, void *arg, void *data)
 {
-       return internal_ao2_callback(c, flags, cb_fn, arg, data, WITH_DATA, NULL, NULL, 0, NULL);
+       return internal_ao2_traverse(c, flags, cb_fn, arg, data, AO2_CALLBACK_WITH_DATA, NULL, NULL, 0, NULL);
 }
 
 /*!
@@ -1209,6 +1415,11 @@ void *__ao2_find_debug(struct ao2_container *c, const void *arg, enum search_fla
 {
        void *arged = (void *) arg;/* Done to avoid compiler const warning */
 
+       if (!c) {
+               /* Sanity checks. */
+               ast_assert(0);
+               return NULL;
+       }
        return __ao2_callback_debug(c, flags, c->cmp_fn, arged, tag, file, line, func);
 }
 
@@ -1216,6 +1427,11 @@ void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags fla
 {
        void *arged = (void *) arg;/* Done to avoid compiler const warning */
 
+       if (!c) {
+               /* Sanity checks. */
+               ast_assert(0);
+               return NULL;
+       }
        return __ao2_callback(c, flags, c->cmp_fn, arged);
 }
 
@@ -1234,16 +1450,57 @@ struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags)
        return a;
 }
 
-/*!
- * destroy an iterator
- */
+void ao2_iterator_restart(struct ao2_iterator *iter)
+{
+       /* Release the last container node reference if we have one. */
+       if (iter->last_node) {
+               enum ao2_lock_req orig_lock;
+
+               /*
+                * Do a read lock in case the container node unref does not
+                * destroy the node.  If the container node is destroyed then
+                * the lock will be upgraded to a write lock.
+                */
+               if (iter->flags & AO2_ITERATOR_DONTLOCK) {
+                       orig_lock = adjust_lock(iter->c, AO2_LOCK_REQ_RDLOCK, 1);
+               } else {
+                       orig_lock = AO2_LOCK_REQ_MUTEX;
+                       ao2_rdlock(iter->c);
+               }
+
+               ao2_ref(iter->last_node, -1);
+               iter->last_node = NULL;
+
+               if (iter->flags & AO2_ITERATOR_DONTLOCK) {
+                       adjust_lock(iter->c, orig_lock, 0);
+               } else {
+                       ao2_unlock(iter->c);
+               }
+       }
+
+       /* The iteration is no longer complete. */
+       iter->complete = 0;
+}
+
 void ao2_iterator_destroy(struct ao2_iterator *iter)
 {
+       /* Release any last container node reference. */
+       ao2_iterator_restart(iter);
+
+       /* Release the iterated container reference. */
        ao2_ref(iter->c, -1);
+       iter->c = NULL;
+
+       /* Free the malloced iterator. */
        if (iter->flags & AO2_ITERATOR_MALLOCD) {
                ast_free(iter);
-       } else {
-               iter->c = NULL;
+       }
+}
+
+void ao2_iterator_cleanup(struct ao2_iterator *iter)
+{
+       if (iter) {
+               ao2_iterator_destroy(iter);
        }
 }
 
@@ -1252,12 +1509,18 @@ void ao2_iterator_destroy(struct ao2_iterator *iter)
  */
 static void *internal_ao2_iterator_next(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func)
 {
-       int lim;
        enum ao2_lock_req orig_lock;
-       struct bucket_entry *p = NULL;
+       struct ao2_container_node *node;
        void *ret;
 
-       if (INTERNAL_OBJ(iter->c) == NULL) {
+       if (!INTERNAL_OBJ(iter->c) || !iter->c->v_table || !iter->c->v_table->iterator_next) {
+               /* Sanity checks. */
+               ast_assert(0);
+               return NULL;
+       }
+
+       if (iter->complete) {
+               /* Don't return any more objects. */
                return NULL;
        }
 
@@ -1276,65 +1539,55 @@ static void *internal_ao2_iterator_next(struct ao2_iterator *iter, const char *t
                }
        }
 
-       /* optimization. If the container is unchanged and
-        * we have a pointer, try follow it
-        */
-       if (iter->c->version == iter->c_version && (p = iter->obj)) {
-               if ((p = AST_LIST_NEXT(p, entry))) {
-                       goto found;
-               }
-               /* nope, start from the next bucket */
-               iter->bucket++;
-               iter->version = 0;
-               iter->obj = NULL;
-       }
-
-       lim = iter->c->n_buckets;
-
-       /* Browse the buckets array, moving to the next
-        * buckets if we don't find the entry in the current one.
-        * Stop when we find an element with version number greater
-        * than the current one (we reset the version to 0 when we
-        * switch buckets).
-        */
-       for (; iter->bucket < lim; iter->bucket++, iter->version = 0) {
-               /* scan the current bucket */
-               AST_LIST_TRAVERSE(&iter->c->buckets[iter->bucket], p, entry) {
-                       if (p->version > iter->version) {
-                               goto found;
-                       }
-               }
-       }
+       node = iter->c->v_table->iterator_next(iter->c, iter->last_node, iter->flags);
+       if (node) {
+               ret = node->obj;
 
-found:
-       if (p) {
-               ret = EXTERNAL_OBJ(p->astobj);
                if (iter->flags & AO2_ITERATOR_UNLINK) {
-                       /* we are going to modify the container, so update version */
-                       ast_atomic_fetchadd_int(&iter->c->version, 1);
-                       AST_LIST_REMOVE(&iter->c->buckets[iter->bucket], p, entry);
                        /* update number of elements */
                        ast_atomic_fetchadd_int(&iter->c->elements, -1);
-                       iter->version = 0;
-                       iter->obj = NULL;
-                       iter->c_version = iter->c->version;
-                       ast_free(p);
-               } else {
-                       iter->version = p->version;
-                       iter->obj = p;
-                       iter->c_version = iter->c->version;
+#if defined(AST_DEVMODE)
+                       {
+                               int empty = iter->c->nodes - iter->c->elements;
+
+                               if (iter->c->max_empty_nodes < empty) {
+                                       iter->c->max_empty_nodes = empty;
+                               }
+                       }
+                       switch (iter->c->v_table->type) {
+                       case AO2_CONTAINER_RTTI_HASH:
+                               hash_ao2_unlink_node_stat(iter->c, node);
+                               break;
+                       }
+#endif /* defined(AST_DEVMODE) */
+
+                       /* Transfer the object ref from the container to the returned object. */
+                       node->obj = NULL;
 
-                       /* inc refcount of returned object */
+                       /* Transfer the container's node ref to the iterator. */
+               } else {
+                       /* Bump ref of returned object */
                        if (tag) {
-                               __ao2_ref_debug(ret, 1, tag, file, line, func);
+                               __ao2_ref_debug(ret, +1, tag, file, line, func);
                        } else {
-                               __ao2_ref(ret, 1);
+                               __ao2_ref(ret, +1);
                        }
+
+                       /* Bump the container's node ref for the iterator. */
+                       __ao2_ref(node, +1);
                }
        } else {
+               /* The iteration has completed. */
+               iter->complete = 1;
                ret = NULL;
        }
 
+       /* Replace the iterator's node */
+       if (iter->last_node) {
+               __ao2_ref(iter->last_node, -1);
+       }
+       iter->last_node = node;
+
        if (iter->flags & AO2_ITERATOR_DONTLOCK) {
                adjust_lock(iter->c, orig_lock, 0);
        } else {
@@ -1354,34 +1607,17 @@ void *__ao2_iterator_next(struct ao2_iterator *iter)
        return internal_ao2_iterator_next(iter, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__);
 }
 
-/* callback for destroying container.
- * we can make it simple as we know what it does
- */
-static int cd_cb(void *obj, void *arg, int flag)
-{
-       __ao2_ref(obj, -1);
-       return 0;
-}
-
-static int cd_cb_debug(void *obj, void *arg, int flag)
-{
-       __ao2_ref_debug(obj, -1, "deref object via container destroy",  __FILE__, __LINE__, __PRETTY_FUNCTION__);
-       return 0;
-}
-
 static void container_destruct(void *_c)
 {
        struct ao2_container *c = _c;
-       int i;
 
-       __ao2_callback(c, OBJ_UNLINK, cd_cb, NULL);
+       /* Unlink any stored objects in the container. */
+       c->destroying = 1;
+       __ao2_callback(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL);
 
-       for (i = 0; i < c->n_buckets; i++) {
-               struct bucket_entry *current;
-
-               while ((current = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) {
-                       ast_free(current);
-               }
+       /* Perform any extra container cleanup. */
+       if (c->v_table && c->v_table->destroy) {
+               c->v_table->destroy(c);
        }
 
 #ifdef AO2_DEBUG
@@ -1392,154 +1628,1388 @@ static void container_destruct(void *_c)
 static void container_destruct_debug(void *_c)
 {
        struct ao2_container *c = _c;
+
+       /* Unlink any stored objects in the container. */
+       c->destroying = 1;
+       __ao2_callback_debug(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL,
+               "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__);
+
+       /* Perform any extra container cleanup. */
+       if (c->v_table && c->v_table->destroy) {
+               c->v_table->destroy(c);
+       }
+
+#ifdef AO2_DEBUG
+       ast_atomic_fetchadd_int(&ao2.total_containers, -1);
+#endif
+}
+
+/*!
+ * \internal
+ * \brief Put obj into the arg container.
+ * \since 11.0
+ *
+ * \param obj  pointer to the (user-defined part) of an object.
+ * \param arg callback argument from ao2_callback()
+ * \param flags flags from ao2_callback()
+ *
+ * \retval 0 on success.
+ * \retval CMP_STOP|CMP_MATCH on error.
+ */
+static int dup_obj_cb(void *obj, void *arg, int flags)
+{
+       struct ao2_container *dest = arg;
+
+       return __ao2_link(dest, obj, OBJ_NOLOCK) ? 0 : (CMP_MATCH | CMP_STOP);
+}
+
+int ao2_container_dup(struct ao2_container *dest, struct ao2_container *src, enum search_flags flags)
+{
+       void *obj;
+       int res = 0;
+
+       if (!(flags & OBJ_NOLOCK)) {
+               ao2_rdlock(src);
+               ao2_wrlock(dest);
+       }
+       obj = __ao2_callback(src, OBJ_NOLOCK, dup_obj_cb, dest);
+       if (obj) {
+               /* Failed to put this obj into the dest container. */
+               __ao2_ref(obj, -1);
+
+               /* Remove all items from the dest container. */
+               __ao2_callback(dest, OBJ_NOLOCK | OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL,
+                       NULL);
+               res = -1;
+       }
+       if (!(flags & OBJ_NOLOCK)) {
+               ao2_unlock(dest);
+               ao2_unlock(src);
+       }
+
+       return res;
+}
+
+struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum search_flags flags)
+{
+       struct ao2_container *clone;
+       int failed;
+
+       /* Create the clone container with the same properties as the original. */
+       if (!INTERNAL_OBJ(orig) || !orig->v_table || !orig->v_table->alloc_empty_clone) {
+               /* Sanity checks. */
+               ast_assert(0);
+               return NULL;
+       }
+       clone = orig->v_table->alloc_empty_clone(orig);
+       if (!clone) {
+               return NULL;
+       }
+
+       if (flags & OBJ_NOLOCK) {
+               ao2_wrlock(clone);
+       }
+       failed = ao2_container_dup(clone, orig, flags);
+       if (flags & OBJ_NOLOCK) {
+               ao2_unlock(clone);
+       }
+       if (failed) {
+               /* Object copy into the clone container failed. */
+               __ao2_ref(clone, -1);
+               clone = NULL;
+       }
+       return clone;
+}
+
+struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, enum search_flags flags, const char *tag, const char *file, int line, const char *func, int ref_debug)
+{
+       struct ao2_container *clone;
+       int failed;
+
+       /* Create the clone container with the same properties as the original. */
+       if (!INTERNAL_OBJ(orig) || !orig->v_table || !orig->v_table->alloc_empty_clone_debug) {
+               /* Sanity checks. */
+               ast_assert(0);
+               return NULL;
+       }
+       clone = orig->v_table->alloc_empty_clone_debug(orig, tag, file, line, func, ref_debug);
+       if (!clone) {
+               return NULL;
+       }
+
+       if (flags & OBJ_NOLOCK) {
+               ao2_wrlock(clone);
+       }
+       failed = ao2_container_dup(clone, orig, flags);
+       if (flags & OBJ_NOLOCK) {
+               ao2_unlock(clone);
+       }
+       if (failed) {
+               /* Object copy into the clone container failed. */
+               if (ref_debug) {
+                       __ao2_ref_debug(clone, -1, tag, file, line, func);
+               } else {
+                       __ao2_ref(clone, -1);
+               }
+               clone = NULL;
+       }
+       return clone;
+}
+
+#if defined(AST_DEVMODE)
+/*!
+ * \internal
+ * \brief Display statistics of the specified container.
+ * \since 12.0.0
+ *
+ * \param self Container to display statistics.
+ * \param fd File descriptor to send output.
+ * \param prnt Print output callback function to use.
+ *
+ * \return Nothing
+ */
+static void ao2_container_stats(struct ao2_container *self, int fd, void (*prnt)(int fd, const char *fmt, ...) __attribute__((format(printf, 2, 3))))
+{
+       if (!INTERNAL_OBJ(self) || !self->v_table) {
+               prnt(fd, "Invalid container\n");
+               ast_assert(0);
+               return;
+       }
+
+       ao2_rdlock(self);
+       prnt(fd, "Number of objects: %d\n", self->elements);
+       prnt(fd, "Number of nodes: %d\n", self->nodes);
+       prnt(fd, "Number of empty nodes: %d\n", self->nodes - self->elements);
+       /*
+        * XXX
+        * If the max_empty_nodes count gets out of single digits you
+        * likely have a code path where ao2_iterator_destroy() is not
+        * called.
+        *
+        * Empty nodes do not harm the container but they do make
+        * container operations less efficient.
+        */
+       prnt(fd, "Maximum empty nodes: %d\n", self->max_empty_nodes);
+       if (self->v_table->stats) {
+               self->v_table->stats(self, fd, prnt);
+       }
+       ao2_unlock(self);
+}
+#endif /* defined(AST_DEVMODE) */
+
+int ao2_container_check(struct ao2_container *self, enum search_flags flags)
+{
+       int res = 0;
+
+       if (!INTERNAL_OBJ(self) || !self->v_table) {
+               /* Sanity checks. */
+               ast_assert(0);
+               return -1;
+       }
+#if defined(AST_DEVMODE)
+       if (!self->v_table->integrity) {
+               /* No ingetrigy check available.  Assume container is ok. */
+               return 0;
+       }
+
+       if (!(flags & OBJ_NOLOCK)) {
+               ao2_rdlock(self);
+       }
+       res = self->v_table->integrity(self);
+       if (!(flags & OBJ_NOLOCK)) {
+               ao2_unlock(self);
+       }
+#endif /* defined(AST_DEVMODE) */
+       return res;
+}
+
+/*!
+ * A structure to create a linked list of entries,
+ * used within a bucket.
+ */
+struct hash_bucket_node {
+       /*!
+        * \brief Items common to all container nodes.
+        * \note Must be first in the specific node struct.
+        */
+       struct ao2_container_node common;
+       /*! Next node links in the list. */
+       AST_DLLIST_ENTRY(hash_bucket_node) links;
+       /*! Hash bucket holding the node. */
+       int my_bucket;
+};
+
+struct hash_bucket {
+       /*! List of objects held in the bucket. */
+       AST_DLLIST_HEAD_NOLOCK(, hash_bucket_node) list;
+#if defined(AST_DEVMODE)
+       /*! Number of elements currently in the bucket. */
+       int elements;
+       /*! Maximum number of elements in the bucket. */
+       int max_elements;
+#endif /* defined(AST_DEVMODE) */
+};
+
+/*!
+ * A hash container in addition to values common to all
+ * container types, stores the hash callback function, the
+ * number of hash buckets, and the hash bucket heads.
+ */
+struct ao2_container_hash {
+       /*!
+        * \brief Items common to all containers.
+        * \note Must be first in the specific container struct.
+        */
+       struct ao2_container common;
+       ao2_hash_fn *hash_fn;
+       /*! Number of hash buckets in this container. */
+       int n_buckets;
+       /*! Hash bucket array of n_buckets.  Variable size. */
+       struct hash_bucket buckets[0];
+};
+
+/*!
+ * \internal
+ * \brief Create an empty copy of this container.
+ * \since 12.0.0
+ *
+ * \param self Container to operate upon.
+ *
+ * \retval empty-clone-container on success.
+ * \retval NULL on error.
+ */
+static struct ao2_container *hash_ao2_alloc_empty_clone(struct ao2_container_hash *self)
+{
+       struct astobj2 *orig_obj;
+       unsigned int ao2_options;
+
+       /* Get container ao2 options. */
+       orig_obj = INTERNAL_OBJ(self);
+       if (!orig_obj) {
+               return NULL;
+       }
+       ao2_options = orig_obj->priv_data.options;
+
+       return __ao2_container_alloc_hash(ao2_options, self->common.options, self->n_buckets,
+               self->hash_fn, self->common.sort_fn, self->common.cmp_fn);
+}
+
+/*!
+ * \internal
+ * \brief Create an empty copy of this container. (Debug version)
+ * \since 12.0.0
+ *
+ * \param self Container to operate upon.
+ * \param tag used for debugging.
+ * \param file Debug file name invoked from
+ * \param line Debug line invoked from
+ * \param func Debug function name invoked from
+ * \param ref_debug TRUE if to output a debug reference message.
+ *
+ * \retval empty-clone-container on success.
+ * \retval NULL on error.
+ */
+static struct ao2_container *hash_ao2_alloc_empty_clone_debug(struct ao2_container_hash *self, const char *tag, const char *file, int line, const char *func, int ref_debug)
+{
+       struct astobj2 *orig_obj;
+       unsigned int ao2_options;
+
+       /* Get container ao2 options. */
+       orig_obj = INTERNAL_OBJ(self);
+       if (!orig_obj) {
+               return NULL;
+       }
+       ao2_options = orig_obj->priv_data.options;
+
+       return __ao2_container_alloc_hash_debug(ao2_options, self->common.options,
+               self->n_buckets, self->hash_fn, self->common.sort_fn, self->common.cmp_fn,
+               tag, file, line, func, ref_debug);
+}
+
+/*!
+ * \internal
+ * \brief Destroy a hash container list node.
+ * \since 12.0.0
+ *
+ * \param v_doomed Container node to destroy.
+ *
+ * \details
+ * The container node unlinks itself from the container as part
+ * of its destruction.  The node must be destroyed while the
+ * container is already locked.
+ *
+ * \return Nothing
+ */
+static void hash_ao2_node_destructor(void *v_doomed)
+{
+       struct hash_bucket_node *doomed = v_doomed;
+
+       if (doomed->common.is_linked) {
+               struct ao2_container_hash *my_container;
+               struct hash_bucket *bucket;
+
+               /*
+                * Promote to write lock if not already there.  Since
+                * adjust_lock() can potentially release and block waiting for a
+                * write lock, care must be taken to ensure that node references
+                * are released before releasing the container references.
+                *
+                * Node references held by an iterator can only be held while
+                * the iterator also holds a reference to the container.  These
+                * node references must be unreferenced before the container can
+                * be unreferenced to ensure that the node will not get a
+                * negative reference and the destructor called twice for the
+                * same node.
+                */
+               my_container = (struct ao2_container_hash *) doomed->common.my_container;
+               adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);
+
+               bucket = &my_container->buckets[doomed->my_bucket];
+               AST_DLLIST_REMOVE(&bucket->list, doomed, links);
+
+#if defined(AST_DEVMODE)
+               --my_container->common.nodes;
+#endif /* defined(AST_DEVMODE) */
+       }
+
+       /*
+        * We could have an object in the node if the container is being
+        * destroyed or the node had not been linked in yet.
+        */
+       if (doomed->common.obj) {
+               ao2_ref(doomed->common.obj, -1);
+               doomed->common.obj = NULL;
+       }
+}
+
+/*!
+ * \internal
+ * \brief Create a new container node.
+ * \since 12.0.0
+ *
+ * \param self Container to operate upon.
+ * \param obj_new Object to put into the node.
+ * \param tag used for debugging.
+ * \param file Debug file name invoked from
+ * \param line Debug line invoked from
+ * \param func Debug function name invoked from
+ *
+ * \retval initialized-node on success.
+ * \retval NULL on error.
+ */
+static struct hash_bucket_node *hash_ao2_new_node(struct ao2_container_hash *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
+{
+       struct hash_bucket_node *node;
        int i;
 
-       __ao2_callback_debug(c, OBJ_UNLINK, cd_cb_debug, NULL, "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__);
+       node = __ao2_alloc(sizeof(*node), hash_ao2_node_destructor, AO2_ALLOC_OPT_LOCK_NOLOCK);
+       if (!node) {
+               return NULL;
+       }
+
+       i = abs(self->hash_fn(obj_new, OBJ_POINTER));
+       i %= self->n_buckets;
+
+       if (tag) {
+               __ao2_ref_debug(obj_new, +1, tag, file, line, func);
+       } else {
+               __ao2_ref(obj_new, +1);
+       }
+       node->common.obj = obj_new;
+       node->common.my_container = (struct ao2_container *) self;
+       node->my_bucket = i;
+
+       return node;
+}
+
+/*!
+ * \internal
+ * \brief Insert a node into this container.
+ * \since 12.0.0
+ *
+ * \param self Container to operate upon.
+ * \param node Container node to insert into the container.
+ *
+ * \return enum ao2_container_insert value.
+ */
+static enum ao2_container_insert hash_ao2_insert_node(struct ao2_container_hash *self, struct hash_bucket_node *node)
+{
+       int cmp;
+       struct hash_bucket *bucket;
+       struct hash_bucket_node *cur;
+       ao2_sort_fn *sort_fn;
+       uint32_t options;
+
+       bucket = &self->buckets[node->my_bucket];
+       sort_fn = self->common.sort_fn;
+       options = self->common.options;
+
+       if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
+               if (sort_fn) {
+                       AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&bucket->list, cur, links) {
+                               cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_POINTER);
+                               if (cmp > 0) {
+                                       continue;
+                               }
+                               if (cmp < 0) {
+                                       AST_DLLIST_INSERT_AFTER_CURRENT(node, links);
+                                       return AO2_CONTAINER_INSERT_NODE_INSERTED;
+                               }
+                               switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
+                               default:
+                               case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
+                                       break;
+                               case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
+                                       /* Reject all objects with the same key. */
+                                       return AO2_CONTAINER_INSERT_NODE_REJECTED;
+                               case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
+                                       if (cur->common.obj == node->common.obj) {
+                                               /* Reject inserting the same object */
+                                               return AO2_CONTAINER_INSERT_NODE_REJECTED;
+                                       }
+                                       break;
+                               case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
+                                       SWAP(cur->common.obj, node->common.obj);
+                                       return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
+                               }
+                       }
+                       AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
+               }
+               AST_DLLIST_INSERT_HEAD(&bucket->list, node, links);
+       } else {
+               if (sort_fn) {
+                       AST_DLLIST_TRAVERSE_SAFE_BEGIN(&bucket->list, cur, links) {
+                               cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_POINTER);
+                               if (cmp < 0) {
+                                       continue;
+                               }
+                               if (cmp > 0) {
+                                       AST_DLLIST_INSERT_BEFORE_CURRENT(node, links);
+                                       return AO2_CONTAINER_INSERT_NODE_INSERTED;
+                               }
+                               switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
+                               default:
+                               case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
+                                       break;
+                               case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
+                                       /* Reject all objects with the same key. */
+                                       return AO2_CONTAINER_INSERT_NODE_REJECTED;
+                               case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
+                                       if (cur->common.obj == node->common.obj) {
+                                               /* Reject inserting the same object */
+                                               return AO2_CONTAINER_INSERT_NODE_REJECTED;
+                                       }
+                                       break;
+                               case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
+                                       SWAP(cur->common.obj, node->common.obj);
+                                       return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
+                               }
+                       }
+                       AST_DLLIST_TRAVERSE_SAFE_END;
+               }
+               AST_DLLIST_INSERT_TAIL(&bucket->list, node, links);
+       }
+       return AO2_CONTAINER_INSERT_NODE_INSERTED;
+}
+
+/*! Traversal state to restart a hash container traversal. */
+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 */
+       int bucket_start;
+       /*! Stopping hash bucket */
+       int bucket_last;
+       /*! Saved search flags to control traversing the container. */
+       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 {
+       /*
+        * If we have a division by zero compile error here then there
+        * is not enough room for the state.  Increase AO2_TRAVERSAL_STATE_SIZE.
+        */
+       char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct hash_traversal_state))];
+};
+
+/*!
+ * \internal
+ * \brief Find the first hash container node in a traversal.
+ * \since 12.0.0
+ *
+ * \param self Container to operate upon.
+ * \param flags search_flags to control traversing the container
+ * \param arg Comparison callback arg parameter.
+ * \param state Traversal state to restart hash container traversal.
+ *
+ * \retval node-ptr of found node (Reffed).
+ * \retval NULL when no node found.
+ */
+static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *self, enum search_flags flags, void *arg, struct hash_traversal_state *state)
+{
+       struct hash_bucket_node *node;
+       int bucket_cur;
+       int cmp;
+
+       memset(state, 0, sizeof(*state));
+       state->arg = arg;
+       state->flags = flags;
+
+       /* Determine traversal order. */
+       switch (flags & OBJ_ORDER_MASK) {
+       case OBJ_ORDER_DESCENDING:
+               state->descending = 1;
+               break;
+       case OBJ_ORDER_ASCENDING:
+       default:
+               break;
+       }
+
+       /*
+        * If lookup by pointer or search key, run the hash and optional
+        * sort functions.  Otherwise, traverse the whole container.
+        */
+       if (flags & (OBJ_POINTER | OBJ_KEY)) {
+               /* we know hash can handle this case */
+               bucket_cur = abs(self->hash_fn(arg, flags & (OBJ_POINTER | OBJ_KEY)));
+               bucket_cur %= self->n_buckets;
+               state->sort_fn = self->common.sort_fn;
+       } else {
+               /* don't know, let's scan all buckets */
+               bucket_cur = -1;
+               state->sort_fn = (flags & OBJ_PARTIAL_KEY) ? self->common.sort_fn : NULL;
+       }
+
+       if (state->descending) {
+               /*
+                * Determine the search boundaries of a descending traversal.
+                *
+                * bucket_cur downto state->bucket_last
+                */
+               if (bucket_cur < 0) {
+                       bucket_cur = self->n_buckets - 1;
+                       state->bucket_last = 0;
+               } 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 */
+               for (; state->bucket_last <= bucket_cur; --bucket_cur) {
+                       /* For each node in the bucket. */
+                       for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
+                               node;
+                               node = AST_DLLIST_PREV(node, links)) {
+                               if (!node->common.obj) {
+                                       /* Node is empty */
+                                       continue;
+                               }
+
+                               if (state->sort_fn) {
+                                       /* Filter node through the sort_fn */
+                                       cmp = state->sort_fn(node->common.obj, arg,
+                                               flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY));
+                                       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) {
+                                               /* No more nodes in this bucket are possible to match. */
+                                               break;
+                                       }
+                               }
+
+                               /* We have the first traversal node */
+                               __ao2_ref(node, +1);
+                               return node;
+                       }
+
+                       /* Was this the starting bucket? */
+                       if (bucket_cur == state->bucket_start
+                               && (flags & OBJ_CONTINUE)
+                               && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) {
+                               /* 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_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) {
+                               /* 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 {
+               /*
+                * Determine the search boundaries of an ascending traversal.
+                *
+                * bucket_cur to state->bucket_last-1
+                */
+               if (bucket_cur < 0) {
+                       bucket_cur = 0;
+                       state->bucket_last = self->n_buckets;
+               } 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 */
+               for (; bucket_cur < state->bucket_last; ++bucket_cur) {
+                       /* For each node in the bucket. */
+                       for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
+                               node;
+                               node = AST_DLLIST_NEXT(node, links)) {
+                               if (!node->common.obj) {
+                                       /* Node is empty */
+                                       continue;
+                               }
+
+                               if (state->sort_fn) {
+                                       /* Filter node through the sort_fn */
+                                       cmp = state->sort_fn(node->common.obj, arg,
+                                               flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY));
+                                       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) {
+                                               /* No more nodes in this bucket are possible to match. */
+                                               break;
+                                       }
+                               }
+
+                               /* We have the first traversal node */
+                               __ao2_ref(node, +1);
+                               return node;
+                       }
+
+                       /* Was this the starting bucket? */
+                       if (bucket_cur == state->bucket_start
+                               && (flags & OBJ_CONTINUE)
+                               && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) {
+                               /* 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_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) {
+                               /* 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;
+                               }
+                       }
+               }
+       }
+
+       return NULL;
+}
+
+/*!
+ * \internal
+ * \brief Find the next hash container node in a traversal.
+ * \since 12.0.0
+ *
+ * \param self Container to operate upon.
+ * \param state Traversal state to restart hash container traversal.
+ * \param prev Previous node returned by the traversal search functions.
+ *    The ref ownership is passed back to this function.
+ *
+ * \retval node-ptr of found node (Reffed).
+ * \retval NULL when no node found.
+ */
+static struct hash_bucket_node *hash_ao2_find_next(struct ao2_container_hash *self, struct hash_traversal_state *state, struct hash_bucket_node *prev)
+{
+       struct hash_bucket_node *node;
+       void *arg;
+       enum search_flags flags;
+       int bucket_cur;
+       int cmp;
+
+       arg = state->arg;
+       flags = state->flags;
+       bucket_cur = prev->my_bucket;
+       node = prev;
+
+       /*
+        * This function is structured the same as hash_ao2_find_first()
+        * intentionally.  We are resuming the search loops from
+        * hash_ao2_find_first() in order to find the next node.  The
+        * search loops must be resumed where hash_ao2_find_first()
+        * returned with the first node.
+        */
+       if (state->descending) {
+               goto hash_descending_resume;
+
+               /* For each bucket */
+               for (; state->bucket_last <= bucket_cur; --bucket_cur) {
+                       /* For each node in the bucket. */
+                       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;
+                               }
+
+                               if (state->sort_fn) {
+                                       /* Filter node through the sort_fn */
+                                       cmp = state->sort_fn(node->common.obj, arg,
+                                               flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY));
+                                       if (cmp > 0) {
+                                               continue;
+                                       }
+                                       if (cmp < 0) {
+                                               /* No more nodes in this bucket are possible to match. */
+                                               break;
+                                       }
+                               }
+
+                               /* We have the next traversal node */
+                               __ao2_ref(node, +1);
+
+                               /*
+                                * Dereferencing the prev node may result in our next node
+                                * object being removed by another thread.  This could happen if
+                                * the container uses RW locks and the container was read
+                                * locked.
+                                */
+                               __ao2_ref(prev, -1);
+                               if (node->common.obj) {
+                                       return node;
+                               }
+                               prev = node;
+
+hash_descending_resume:;
+                       }
+
+                       /* Was this the first container bucket? */
+                       if (bucket_cur == 0
+                               && (flags & OBJ_CONTINUE)
+                               && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) {
+                               /* 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;
+
+               /* For each bucket */
+               for (; bucket_cur < state->bucket_last; ++bucket_cur) {
+                       /* For each node in the bucket. */
+                       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;
+                               }
+
+                               if (state->sort_fn) {
+                                       /* Filter node through the sort_fn */
+                                       cmp = state->sort_fn(node->common.obj, arg,
+                                               flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY));
+                                       if (cmp < 0) {
+                                               continue;
+                                       }
+                                       if (cmp > 0) {
+                                               /* No more nodes in this bucket are possible to match. */
+                                               break;
+                                       }
+                               }
+
+                               /* We have the next traversal node */
+                               __ao2_ref(node, +1);
+
+                               /*
+                                * Dereferencing the prev node may result in our next node
+                                * object being removed by another thread.  This could happen if
+                                * the container uses RW locks and the container was read
+                                * locked.
+                                */
+                               __ao2_ref(prev, -1);
+                               if (node->common.obj) {
+                                       return node;
+                               }
+                               prev = node;
+
+hash_ascending_resume:;
+                       }
+
+                       /* Was this the last container bucket? */
+                       if (bucket_cur == self->n_buckets - 1
+                               && (flags & OBJ_CONTINUE)
+                               && (flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY))) {
+                               /* 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;
+                               }
+                       }
+               }
+       }
+
+       /* No more nodes in the container left to traverse. */
+       __ao2_ref(prev, -1);
+       return NULL;
+}
+
+/*!
+ * \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
+ *
+ * \param self Container to operate upon.
+ * \param node Previous node returned by the iterator.
+ * \param flags search_flags to control iterating the container.
+ *   Only AO2_ITERATOR_DESCENDING is useful by the method.
+ *
+ * \note The container is already locked.
+ *
+ * \retval node on success.
+ * \retval NULL on error or no more nodes in the container.
+ */
+static struct hash_bucket_node *hash_ao2_iterator_next(struct ao2_container_hash *self, struct hash_bucket_node *node, enum ao2_iterator_flags flags)
+{
+       int cur_bucket;
+
+       if (flags & AO2_ITERATOR_DESCENDING) {
+               if (node) {
+                       cur_bucket = node->my_bucket;
+
+                       /* Find next non-empty node. */
+                       for (;;) {
+                               node = AST_DLLIST_PREV(node, links);
+                               if (!node) {
+                                       break;
+                               }
+                               if (node->common.obj) {
+                                       /* Found a non-empty node. */
+                                       return node;
+                               }
+                       }
+               } else {
+                       /* Find first non-empty node. */
+                       cur_bucket = self->n_buckets;
+               }
+
+               /* Find a non-empty node in the remaining buckets */
+               while (0 <= --cur_bucket) {
+                       node = AST_DLLIST_LAST(&self->buckets[cur_bucket].list);
+                       while (node) {
+                               if (node->common.obj) {
+                                       /* Found a non-empty node. */
+                                       return node;
+                               }
+                               node = AST_DLLIST_PREV(node, links);
+                       }
+               }
+       } else {
+               if (node) {
+                       cur_bucket = node->my_bucket;
+
+                       /* Find next non-empty node. */
+                       for (;;) {
+                               node = AST_DLLIST_NEXT(node, links);
+                               if (!node) {
+                                       break;
+                               }
+                               if (node->common.obj) {
+                                       /* Found a non-empty node. */
+                                       return node;
+                               }
+                       }
+               } else {
+                       /* Find first non-empty node. */
+                       cur_bucket = -1;
+               }
+
+               /* Find a non-empty node in the remaining buckets */
+               while (++cur_bucket < self->n_buckets) {
+                       node = AST_DLLIST_FIRST(&self->buckets[cur_bucket].list);
+                       while (node) {
+                               if (node->common.obj) {
+                                       /* Found a non-empty node. */
+                                       return node;
+                               }
+                               node = AST_DLLIST_NEXT(node, links);
+                       }
+               }
+       }
+
+       /* No more nodes to visit in the container. */
+       return NULL;
+}
+
+#if defined(AST_DEVMODE)
+/*!
+ * \internal
+ * \brief Increment the hash container linked object statistic.
+ * \since 12.0.0
+ *
+ * \param hash Container to operate upon.
+ * \param hash_node Container node linking object to.
+ *
+ * \return Nothing
+ */
+static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
+{
+       struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
+       struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
+       int i = node->my_bucket;
+
+       ++self->buckets[i].elements;
+       if (self->buckets[i].max_elements < self->buckets[i].elements) {
+               self->buckets[i].max_elements = self->buckets[i].elements;
+       }
+}
+#endif /* defined(AST_DEVMODE) */
+
+#if defined(AST_DEVMODE)
+/*!
+ * \internal
+ * \brief Decrement the hash container linked object statistic.
+ * \since 12.0.0
+ *
+ * \param hash Container to operate upon.
+ * \param hash_node Container node unlinking object from.
+ *
+ * \return Nothing
+ */
+static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
+{
+       struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
+       struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
+
+       --self->buckets[node->my_bucket].elements;
+}
+#endif /* defined(AST_DEVMODE) */
 
-       for (i = 0; i < c->n_buckets; i++) {
-               struct bucket_entry *current;
+/*!
+ * \internal
+ *
+ * \brief Destroy this container.
+ * \since 12.0.0
+ *
+ * \param self Container to operate upon.
+ *
+ * \return Nothing
+ */
+static void hash_ao2_destroy(struct ao2_container_hash *self)
+{
+       int idx;
 
-               while ((current = AST_LIST_REMOVE_HEAD(&c->buckets[i], entry))) {
-                       ast_free(current);
+       /* Check that the container no longer has any nodes */
+       for (idx = self->n_buckets; idx--;) {
+               if (!AST_DLLIST_EMPTY(&self->buckets[idx].list)) {
+                       ast_log(LOG_ERROR, "Node ref leak.  Hash container still has nodes!\n");
+                       ast_assert(0);
+                       break;
                }
        }
-
-#ifdef AO2_DEBUG
-       ast_atomic_fetchadd_int(&ao2.total_containers, -1);
-#endif
 }
 
+#if defined(AST_DEVMODE)
 /*!
  * \internal
- * \brief Put obj into the arg container.
- * \since 11.0
+ * \brief Display statistics of the specified container.
+ * \since 12.0.0
  *
- * \param obj  pointer to the (user-defined part) of an object.
- * \param arg callback argument from ao2_callback()
- * \param flags flags from ao2_callback()
+ * \param self Container to display statistics.
+ * \param fd File descriptor to send output.
+ * \param prnt Print output callback function to use.
  *
- * \retval 0 on success.
- * \retval CMP_STOP|CMP_MATCH on error.
+ * \note The container is already locked for reading.
+ *
+ * \return Nothing
  */
-static int dup_obj_cb(void *obj, void *arg, int flags)
+static void hash_ao2_stats(struct ao2_container_hash *self, int fd, void (*prnt)(int fd, const char *fmt, ...) __attribute__((format(printf, 2, 3))))
 {
-       struct ao2_container *dest = arg;
+#define FORMAT  "%10.10s %10.10s %10.10s\n"
+#define FORMAT2 "%10d %10d %10d\n"
+
+       int bucket;
+       int suppressed_buckets = 0;
+
+       prnt(fd, "Number of buckets: %d\n\n", self->n_buckets);
+
+       prnt(fd, FORMAT, "Bucket", "Objects", "Max");
+       for (bucket = 0; bucket < self->n_buckets; ++bucket) {
+               if (self->buckets[bucket].max_elements) {
+                       prnt(fd, FORMAT2, bucket, self->buckets[bucket].elements,
+                               self->buckets[bucket].max_elements);
+                       suppressed_buckets = 0;
+               } else if (!suppressed_buckets) {
+                       suppressed_buckets = 1;
+                       prnt(fd, "...\n");
+               }
+       }
 
-       return __ao2_link(dest, obj, OBJ_NOLOCK) ? 0 : (CMP_MATCH | CMP_STOP);
+#undef FORMAT
+#undef FORMAT2
 }
+#endif /* defined(AST_DEVMODE) */
 
-int ao2_container_dup(struct ao2_container *dest, struct ao2_container *src, enum search_flags flags)
+#if defined(AST_DEVMODE)
+/*!
+ * \internal
+ * \brief Perform an integrity check on the specified container.
+ * \since 12.0.0
+ *
+ * \param self Container to check integrity.
+ *
+ * \note The container is already locked for reading.
+ *
+ * \retval 0 on success.
+ * \retval -1 on error.
+ */
+static int hash_ao2_integrity(struct ao2_container_hash *self)
 {
-       void *obj;
-       int res = 0;
+       int bucket_exp;
+       int bucket;
+       int count_obj;
+       int count_total_obj;
+       int count_total_node;
+       void *obj_last;
+       struct hash_bucket_node *node;
+       struct hash_bucket_node *prev;
+       struct hash_bucket_node *next;
+
+       count_total_obj = 0;
+       count_total_node = 0;
+
+       /* For each bucket in the container. */
+       for (bucket = 0; bucket < self->n_buckets; ++bucket) {
+               if (!AST_DLLIST_FIRST(&self->buckets[bucket].list)
+                       && !AST_DLLIST_LAST(&self->buckets[bucket].list)) {
+                       /* The bucket list is empty. */
+                       continue;
+               }
 
-       if (!(flags & OBJ_NOLOCK)) {
-               ao2_rdlock(src);
-               ao2_wrlock(dest);
+               count_obj = 0;
+               obj_last = NULL;
+
+               /* Check bucket list links and nodes. */
+               node = AST_DLLIST_LAST(&self->buckets[bucket].list);
+               if (!node) {
+                       ast_log(LOG_ERROR, "Bucket %d list tail is NULL when it should not be!\n",
+                               bucket);
+                       return -1;
+               }
+               if (AST_DLLIST_NEXT(node, links)) {
+                       ast_log(LOG_ERROR, "Bucket %d list tail node is not the last node!\n",
+                               bucket);
+                       return -1;
+               }
+               node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
+               if (!node) {
+                       ast_log(LOG_ERROR, "Bucket %d list head is NULL when it should not be!\n",
+                               bucket);
+                       return -1;
+               }
+               if (AST_DLLIST_PREV(node, links)) {
+                       ast_log(LOG_ERROR, "Bucket %d list head node is not the first node!\n",
+                               bucket);
+                       return -1;
+               }
+               for (; node; node = next) {
+                       /* Check backward link. */
+                       prev = AST_DLLIST_PREV(node, links);
+                       if (prev) {
+                               if (node != AST_DLLIST_NEXT(prev, links)) {
+                                       ast_log(LOG_ERROR, "Bucket %d list node's prev node does not link back!\n",
+                                               bucket);
+                                       return -1;
+                               }
+                       } else if (node != AST_DLLIST_FIRST(&self->buckets[bucket].list)) {
+                               ast_log(LOG_ERROR, "Bucket %d backward list chain is broken!\n",
+                                       bucket);
+                               return -1;
+                       }
+
+                       /* Check forward link. */
+                       next = AST_DLLIST_NEXT(node, links);
+                       if (next) {
+                               if (node != AST_DLLIST_PREV(next, links)) {
+                                       ast_log(LOG_ERROR, "Bucket %d list node's next node does not link back!\n",
+                                               bucket);
+                                       return -1;
+                               }
+                       } else if (node != AST_DLLIST_LAST(&self->buckets[bucket].list)) {
+                               ast_log(LOG_ERROR, "Bucket %d forward list chain is broken!\n",
+                                       bucket);
+                               return -1;
+                       }
+
+                       if (bucket != node->my_bucket) {
+                               ast_log(LOG_ERROR, "Bucket %d node claims to be in bucket %d!\n",
+                                       bucket, node->my_bucket);
+                               return -1;
+                       }
+
+                       ++count_total_node;
+                       if (!node->common.obj) {
+                               /* Node is empty. */
+                               continue;
+                       }
+                       ++count_obj;
+
+                       /* Check container hash key for expected bucket. */
+                       bucket_exp = abs(self->hash_fn(node->common.obj, OBJ_POINTER));
+                       bucket_exp %= self->n_buckets;
+                       if (bucket != bucket_exp) {
+                               ast_log(LOG_ERROR, "Bucket %d node hashes to bucket %d!\n",
+                                       bucket, bucket_exp);
+                               return -1;
+                       }
+
+                       /* Check sort if configured. */
+                       if (self->common.sort_fn) {
+                               if (obj_last
+                                       && self->common.sort_fn(obj_last, node->common.obj, OBJ_POINTER) > 0) {
+                                       ast_log(LOG_ERROR, "Bucket %d nodes out of sorted order!\n",
+                                               bucket);
+                                       return -1;
+                               }
+                               obj_last = node->common.obj;
+                       }
+               }
+
+               /* Check bucket obj count statistic. */
+               if (count_obj != self->buckets[bucket].elements) {
+                       ast_log(LOG_ERROR, "Bucket %d object count of %d does not match stat of %d!\n",
+                               bucket, count_obj, self->buckets[bucket].elements);
+                       return -1;
+               }
+
+               /* Accumulate found object counts. */
+               count_total_obj += count_obj;
        }
-       obj = __ao2_callback(src, OBJ_NOLOCK, dup_obj_cb, dest);
-       if (obj) {
-               /* Failed to put this obj into the dest container. */
-               __ao2_ref(obj, -1);
 
-               /* Remove all items from the dest container. */
-               __ao2_callback(dest, OBJ_NOLOCK | OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL,
-                       NULL);
-               res = -1;
+       /* Check total obj count. */
+       if (count_total_obj != ao2_container_count(&self->common)) {
+               ast_log(LOG_ERROR,
+                       "Total object count of %d does not match ao2_container_count() of %d!\n",
+                       count_total_obj, ao2_container_count(&self->common));
+               return -1;
        }
-       if (!(flags & OBJ_NOLOCK)) {
-               ao2_unlock(dest);
-               ao2_unlock(src);
+
+       /* Check total node count. */
+       if (count_total_node != self->common.nodes) {
+               ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n",
+                       count_total_node, self->common.nodes);
+               return -1;
        }
 
-       return res;
+       return 0;
 }
+#endif /* defined(AST_DEVMODE) */
+
+/*! Hash container virtual method table. */
+static const struct ao2_container_methods v_table_hash = {
+       .type = AO2_CONTAINER_RTTI_HASH,
+       .alloc_empty_clone = (ao2_container_alloc_empty_clone_fn) hash_ao2_alloc_empty_clone,
+       .alloc_empty_clone_debug =
+               (ao2_container_alloc_empty_clone_debug_fn) hash_ao2_alloc_empty_clone_debug,
+       .new_node = (ao2_container_new_node_fn) hash_ao2_new_node,
+       .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)
+       .stats = (ao2_container_statistics) hash_ao2_stats,
+       .integrity = (ao2_container_integrity) hash_ao2_integrity,
+#endif /* defined(AST_DEVMODE) */
+};
 
-struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum search_flags flags)
+/*!
+ * \brief always zero hash function
+ *
+ * it is convenient to have a hash function that always returns 0.
+ * This is basically used when we want to have a container that is
+ * a simple linked list.
+ *
+ * \returns 0
+ */
+static int hash_zero(const void *user_obj, const int flags)
 {
-       struct ao2_container *clone;
-       struct astobj2 *orig_obj;
-       unsigned int options;
-       int failed;
+       return 0;
+}
 
-       orig_obj = INTERNAL_OBJ(orig);
-       if (!orig_obj) {
+/*!
+ * \brief Initialize a hash container with the desired number of buckets.
+ *
+ * \param self Container to initialize.
+ * \param options Container behaviour options (See enum ao2_container_opts)
+ * \param n_buckets Number of buckets for hash
+ * \param hash_fn Pointer to a function computing a hash value.
+ * \param sort_fn Pointer to a sort function.
+ * \param cmp_fn Pointer to a compare function used by ao2_find.
+ *
+ * \return A pointer to a struct container.
+ */
+static struct ao2_container *hash_ao2_container_init(
+       struct ao2_container_hash *self, unsigned int options, unsigned int n_buckets,
+       ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
+{
+       if (!self) {
                return NULL;
        }
-       options = orig_obj->priv_data.options;
 
-       /* Create the clone container with the same properties as the original. */
-       clone = __ao2_container_alloc(options, orig->n_buckets, orig->hash_fn, orig->cmp_fn);
-       if (!clone) {
-               return NULL;
-       }
+       self->common.v_table = &v_table_hash;
+       self->common.sort_fn = sort_fn;
+       self->common.cmp_fn = cmp_fn;
+       self->common.options = options;
+       self->hash_fn = hash_fn ? hash_fn : hash_zero;
+       self->n_buckets = n_buckets;
 
-       if (flags & OBJ_NOLOCK) {
-               ao2_wrlock(clone);
-       }
-       failed = ao2_container_dup(clone, orig, flags);
-       if (flags & OBJ_NOLOCK) {
-               ao2_unlock(clone);
-       }
-       if (failed) {
-               /* Object copy into the clone container failed. */
-               __ao2_ref(clone, -1);
-               clone = NULL;
-       }
-       return clone;
+#ifdef AO2_DEBUG
+       ast_atomic_fetchadd_int(&ao2.total_containers, 1);
+#endif
+
+       return (struct ao2_container *) self;
 }
 
-struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, enum search_flags flags, const char *tag, const char *file, int line, const char *func, int ref_debug)
+struct ao2_container *__ao2_container_alloc_hash(unsigned int ao2_options,
+       unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
+       ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
 {
-       struct ao2_container *clone;
-       struct astobj2 *orig_obj;
-       unsigned int options;
-       int failed;
+       unsigned int num_buckets;
+       size_t container_size;
+       struct ao2_container_hash *self;
 
-       orig_obj = INTERNAL_OBJ(orig);
-       if (!orig_obj) {
-               return NULL;
-       }
-       options = orig_obj->priv_data.options;
+       num_buckets = hash_fn ? n_buckets : 1;
+       container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket);
 
-       /* Create the clone container with the same properties as the original. */
-       clone = __ao2_container_alloc_debug(options, orig->n_buckets, orig->hash_fn,
-               orig->cmp_fn, tag, file, line, func, ref_debug);
-       if (!clone) {
-               return NULL;
-       }
+       self = __ao2_alloc(container_size, container_destruct, ao2_options);
+       return hash_ao2_container_init(self, container_options, num_buckets,
+               hash_fn, sort_fn, cmp_fn);
+}
 
-       if (flags & OBJ_NOLOCK) {
-               ao2_wrlock(clone);
-       }
-       failed = ao2_container_dup(clone, orig, flags);
-       if (flags & OBJ_NOLOCK) {
-               ao2_unlock(clone);
-       }
-       if (failed) {
-               /* Object copy into the clone container failed. */
-               if (ref_debug) {
-                       __ao2_ref_debug(clone, -1, tag, file, line, func);
-               } else {
-                       __ao2_ref(clone, -1);
-               }
-               clone = NULL;
-       }
-       return clone;
+struct ao2_container *__ao2_container_alloc_hash_debug(unsigned int ao2_options,
+       unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
+       ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
+       const char *tag, const char *file, int line, const char *func, int ref_debug)
+{
+       unsigned int num_buckets;
+       size_t container_size;
+       struct ao2_container_hash *self;
+
+       num_buckets = hash_fn ? n_buckets : 1;
+       container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket);
+
+       self = __ao2_alloc_debug(container_size, container_destruct_debug, ao2_options,
+               tag, file, line, func, ref_debug);
+       return hash_ao2_container_init(self, container_options, num_buckets, hash_fn,
+               sort_fn, cmp_fn);
 }
 
-void ao2_cleanup(void *obj)
+struct ao2_container *__ao2_container_alloc_list(unsigned int ao2_options,
+       unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
 {
-       if (obj) {
-               ao2_ref(obj, -1);
-       }
+       return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL, sort_fn,
+               cmp_fn);
 }
 
-void ao2_iterator_cleanup(struct ao2_iterator *iter)
+struct ao2_container *__ao2_container_alloc_list_debug(unsigned int ao2_options,
+       unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
+       const char *tag, const char *file, int line, const char *func, int ref_debug)
 {
-       if (iter) {
-               ao2_iterator_destroy(iter);
-       }
+       return __ao2_container_alloc_hash_debug(ao2_options, container_options, 1, NULL,
+               sort_fn, cmp_fn, tag, file, line, func, ref_debug);
 }
 
 #ifdef AO2_DEBUG
@@ -1591,7 +3061,7 @@ static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cl
                e->command = "astobj2 test";
                e->usage = "Usage: astobj2 test <num>\n"
                           "       Runs astobj2 test. Creates 'num' objects,\n"
-                          "       and test iterators, callbacks and may be other stuff\n";
+                          "       and test iterators, callbacks and maybe other stuff\n";
                return NULL;
        case CLI_GENERATE:
                return NULL;
@@ -1610,10 +3080,10 @@ static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cl
 
        handle_astobj2_stats(e, CLI_HANDLER, &fake_args);
        /*
-        * allocate a container with no default callback, and no hash function.
-        * No hash means everything goes in the same bucket.
+        * Allocate a list container.
         */
-       c1 = ao2_t_container_alloc(100, NULL /* no callback */, NULL /* no hash */,"test");
+       c1 = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, 0, NULL /* no sort */,
+               NULL /* no callback */, "test");
        ast_cli(a->fd, "container allocated as %p\n", c1);
 
        /*
@@ -1671,7 +3141,7 @@ static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cl
        ast_cli(a->fd, "testing callbacks again\n");
        ao2_t_callback(c1, 0, print_cb, a, "test callback");
 
-       ast_verbose("now you should see an error message:\n");
+       ast_verbose("now you should see an error and possible assertion failure messages:\n");
        ao2_t_ref(&i, -1, "");  /* i is not a valid object so we print an error here */
 
        ast_cli(a->fd, "destroy container\n");
@@ -1680,18 +3150,232 @@ static char *handle_astobj2_test(struct ast_cli_entry *e, int cmd, struct ast_cl
        handle_astobj2_stats(e, CLI_HANDLER, &fake_args);
        return CLI_SUCCESS;
 }
+#endif /* AO2_DEBUG */
+
+#if defined(AST_DEVMODE)
+static struct ao2_container *reg_containers;
+
+struct ao2_reg_container {
+       /*! Registered container pointer. */
+       struct ao2_container *registered;
+       /*! Name container registered under. */
+       char name[1];
+};
+
+struct ao2_reg_partial_key {
+       /*! Length of partial key match. */
+       int len;
+       /*! Registration partial key name. */
+       const char *name;
+};
+
+struct ao2_reg_match {
+       /*! The nth match to find. */
+       int find_nth;
+       /*! Count of the matches already found. */
+       int count;
+};
+#endif /* defined(AST_DEVMODE) */
+
+#if defined(AST_DEVMODE)
+static int ao2_reg_sort_cb(const void *obj_left, const void *obj_right, int flags)
+{
+       const struct ao2_reg_container *reg_left = obj_left;
+       int cmp;
+
+       if (flags & OBJ_KEY) {
+               const char *name = obj_right;
+
+               cmp = strcasecmp(reg_left->name, name);
+       } else if (flags & OBJ_PARTIAL_KEY) {
+               const struct ao2_reg_partial_key *partial_key = obj_right;
+
+               cmp = strncasecmp(reg_left->name, partial_key->name, partial_key->len);
+       } else {
+               const struct ao2_reg_container *reg_right = obj_right;
+
+               cmp = strcasecmp(reg_left->name, reg_right->name);
+       }
+       return cmp;
+}
+#endif /* defined(AST_DEVMODE) */
+
+#if defined(AST_DEVMODE)
+static void ao2_reg_destructor(void *v_doomed)
+{
+       struct ao2_reg_container *doomed = v_doomed;
+
+       if (doomed->registered) {
+               ao2_ref(doomed->registered, -1);
+       }
+}
+#endif /* defined(AST_DEVMODE) */
+
+int ao2_container_register(const char *name, struct ao2_container *self)
+{
+       int res = 0;
+#if defined(AST_DEVMODE)
+       struct ao2_reg_container *reg;
+
+       reg = ao2_alloc_options(sizeof(*reg) + strlen(name), ao2_reg_destructor,
+               AO2_ALLOC_OPT_LOCK_NOLOCK);
+       if (!reg) {
+               return -1;
+       }
+
+       /* Fill in registered entry */
+       ao2_ref(self, +1);
+       reg->registered = self;
+       strcpy(reg->name, name);/* safe */
+
+       if (!ao2_link(reg_containers, reg)) {
+               res = -1;
+       }
+
+       ao2_ref(reg, -1);
+#endif /* defined(AST_DEVMODE) */
+       return res;
+}
+
+void ao2_container_unregister(const char *name)
+{
+#if defined(AST_DEVMODE)
+       ao2_find(reg_containers, name, OBJ_UNLINK | OBJ_NODATA | OBJ_KEY);
+#endif /* defined(AST_DEVMODE) */
+}
+
+#if defined(AST_DEVMODE)
+static int ao2_complete_reg_cb(void *obj, void *arg, void *data, int flags)
+{
+       struct ao2_reg_match *which = data;
+
+       /* ao2_reg_sort_cb() has already filtered the search to matching keys */
+       return (which->find_nth < ++which->count) ? (CMP_MATCH | CMP_STOP) : 0;
+}
+#endif /* defined(AST_DEVMODE) */
+
+#if defined(AST_DEVMODE)
+static char *complete_container_names(struct ast_cli_args *a)
+{
+       struct ao2_reg_partial_key partial_key;
+       struct ao2_reg_match which;
+       struct ao2_reg_container *reg;
+       char *name;
+
+       if (a->pos != 3) {
+               return NULL;
+       }
+
+       partial_key.len = strlen(a->word);
+       partial_key.name = a->word;
+       which.find_nth = a->n;
+       which.count = 0;
+       reg = ao2_callback_data(reg_containers, partial_key.len ? OBJ_PARTIAL_KEY : 0,
+               ao2_complete_reg_cb, &partial_key, &which);
+       if (reg) {
+               name = ast_strdup(reg->name);
+               ao2_ref(reg, -1);
+       } else {
+               name = NULL;
+       }
+       return name;
+}
+#endif /* defined(AST_DEVMODE) */
+
+#if defined(AST_DEVMODE)
+/*! \brief Show container statistics - CLI command */
+static char *handle_cli_astobj2_container_stats(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
+{
+       const char *name;
+       struct ao2_reg_container *reg;
+
+       switch (cmd) {
+       case CLI_INIT:
+               e->command = "astobj2 container stats";
+               e->usage =
+                       "Usage: astobj2 container stats <name>\n"
+                       "       Show statistics about the specified container <name>.\n";
+               return NULL;
+       case CLI_GENERATE:
+               return complete_container_names(a);
+       }
+
+       if (a->argc != 4) {
+               return CLI_SHOWUSAGE;
+       }
+
+       name = a->argv[3];
+       reg = ao2_find(reg_containers, name, OBJ_KEY);
+       if (reg) {
+               ao2_container_stats(reg->registered, a->fd, ast_cli);
+               ao2_ref(reg, -1);
+       } else {
+               ast_cli(a->fd, "Container '%s' not found.\n", name);
+       }
+
+       return CLI_SUCCESS;
+}
+#endif /* defined(AST_DEVMODE) */
+
+#if defined(AST_DEVMODE)
+/*! \brief Show container check results - CLI command */
+static char *handle_cli_astobj2_container_check(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
+{
+       const char *name;
+       struct ao2_reg_container *reg;
+
+       switch (cmd) {
+       case CLI_INIT:
+               e->command = "astobj2 container check";
+               e->usage =
+                       "Usage: astobj2 container check <name>\n"
+                       "       Perform a container integrity check on <name>.\n";
+               return NULL;
+       case CLI_GENERATE:
+               return complete_container_names(a);
+       }
+
+       if (a->argc != 4) {
+               return CLI_SHOWUSAGE;
+       }
+
+       name = a->argv[3];
+       reg = ao2_find(reg_containers, name, OBJ_KEY);
+       if (reg) {
+               ast_cli(a->fd, "Container check of '%s': %s.\n", name,
+                       ao2_container_check(reg->registered, 0) ? "failed" : "OK");
+               ao2_ref(reg, -1);
+       } else {
+               ast_cli(a->fd, "Container '%s' not found.\n", name);
+       }
+
+       return CLI_SUCCESS;
+}
+#endif /* defined(AST_DEVMODE) */
 
+#if defined(AO2_DEBUG) || defined(AST_DEVMODE)
 static struct ast_cli_entry cli_astobj2[] = {
+#if defined(AO2_DEBUG)
        AST_CLI_DEFINE(handle_astobj2_stats, "Print astobj2 statistics"),
        AST_CLI_DEFINE(handle_astobj2_test, "Test astobj2"),
+#endif /* defined(AO2_DEBUG) */
+#if defined(AST_DEVMODE)
+       AST_CLI_DEFINE(handle_cli_astobj2_container_stats, "Show container statistics"),
+       AST_CLI_DEFINE(handle_cli_astobj2_container_check, "Perform a container integrity check"),
+#endif /* defined(AST_DEVMODE) */
 };
-#endif /* AO2_DEBUG */
+#endif /* defined(AO2_DEBUG) || defined(AST_DEVMODE) */
+
 
 int astobj2_init(void)
 {
-#ifdef AO2_DEBUG
+#if defined(AST_DEVMODE)
+       reg_containers = ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_RWLOCK,
+               AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE, ao2_reg_sort_cb, NULL);
+#endif /* defined(AST_DEVMODE) */
+#if defined(AO2_DEBUG) || defined(AST_DEVMODE)
        ast_cli_register_multiple(cli_astobj2, ARRAY_LEN(cli_astobj2));
-#endif
+#endif /* defined(AO2_DEBUG) || defined(AST_DEVMODE) */
 
        return 0;
 }
index 0faf165..d62f342 100644 (file)
@@ -8508,6 +8508,9 @@ void ast_channels_init(void)
 {
        channels = ao2_container_alloc(NUM_CHANNEL_BUCKETS,
                        ast_channel_hash_cb, ast_channel_cmp_cb);
+       if (channels) {
+               ao2_container_register("channels", channels);
+       }
 
        ast_cli_register_multiple(cli_channel, ARRAY_LEN(cli_channel));
 
index 275c260..95d7e75 100644 (file)
@@ -37,15 +37,59 @@ ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
 #include "asterisk/test.h"
 #include "asterisk/astobj2.h"
 
+enum test_container_type {
+       TEST_CONTAINER_LIST,
+       TEST_CONTAINER_HASH,
+};
+
+/*!
+ * \internal
+ * \brief Convert the container type enum to string.
+ * \since 12.0.0
+ *
+ * \param type Container type value to convert to string.
+ *
+ * \return String value of container type.
+ */
+static const char *test_container2str(enum test_container_type type)
+{
+       const char *c_type;
+
+       c_type = "Unknown";
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               c_type = "List";
+               break;
+       case TEST_CONTAINER_HASH:
+               c_type = "Hash";
+               break;
+       }
+       return c_type;
+}
+
 struct test_obj {
-       int i;
+       /*! What to decrement when object is destroyed. */
        int *destructor_count;
+       /*! Container object key */
+       int i;
+       /*! Identifier for duplicate object key tests. */
+       int dup_number;
 };
 
-static void test_obj_destructor(void *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)
 {
-       struct test_obj *test_obj = (struct test_obj *) obj;
-       *test_obj->destructor_count = *test_obj->destructor_count - 1;
+       struct test_obj *obj = (struct test_obj *) v_obj;
+
+       if (obj->destructor_count) {
+               --*obj->destructor_count;
+       }
 }
 
 static int increment_cb(void *obj, void *arg, int flag)
@@ -58,124 +102,140 @@ static int increment_cb(void *obj, void *arg, int flag)
 
 static int all_but_one_cb(void *obj, void *arg, int flag)
 {
-       struct test_obj *test_obj = (struct test_obj *) obj;
+       struct test_obj *cmp_obj = (struct test_obj *) obj;
 
-       return (test_obj->i > 1) ? CMP_MATCH : 0;
+       return (cmp_obj->i) ? CMP_MATCH : 0;
 }
 
 static int multiple_cb(void *obj, void *arg, int flag)
 {
        int *i = (int *) arg;
-       struct test_obj *test_obj = (struct test_obj *) obj;
+       struct test_obj *cmp_obj = (struct test_obj *) obj;
 
-       return (test_obj->i <= *i) ? CMP_MATCH : 0;
+       return (cmp_obj->i < *i) ? CMP_MATCH : 0;
 }
 
 static int test_cmp_cb(void *obj, void *arg, int flags)
 {
        struct test_obj *cmp_obj = (struct test_obj *) obj;
 
-       if (!arg) {
-               return 0;
-       }
-
        if (flags & OBJ_KEY) {
                int *i = (int *) arg;
-               return (cmp_obj->i == *i) ? CMP_MATCH | CMP_STOP : 0;
+
+               return (cmp_obj->i == *i) ? CMP_MATCH : 0;
+       } else if (flags & OBJ_PARTIAL_KEY) {
+               int *i = (int *) arg;
+
+               return (*i - partial_key_match_range <= cmp_obj->i
+                       && cmp_obj->i <= *i + partial_key_match_range) ? CMP_MATCH : 0;
        } else {
-               struct test_obj *test_obj = (struct test_obj *) arg;
-               return (cmp_obj->i == test_obj->i) ? CMP_MATCH | CMP_STOP : 0;
+               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;
        }
 }
 
 static int test_hash_cb(const void *obj, const int flags)
 {
-       if (!obj) {
-               return 0;
-       }
-
        if (flags & OBJ_KEY) {
                const int *i = obj;
 
                return *i;
+       } else if (flags & OBJ_PARTIAL_KEY) {
+               /* This is absolutely wrong to be called with this flag value. */
+               abort();
+               /* Just in case abort() doesn't work or something else super silly */
+               *((int *) 0) = 0;
+               return 0;
        } else {
-               const struct test_obj *test_obj = obj;
+               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 test_obj->i;
+               return hash_obj->i;
        }
 }
 
-static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, struct ast_test *test)
+static int test_sort_cb(const void *obj_left, const void *obj_right, int flags)
 {
-       struct ao2_container *c1;
-       struct ao2_container *c2;
-       struct ao2_container *c3 = NULL;
-       struct ao2_iterator it;
-       struct ao2_iterator *mult_it;
-       struct test_obj *obj;
-       struct test_obj *obj2;
-       struct test_obj tmp_obj;
-       int bucket_size;
-       int increment = 0;
-       int destructor_count = 0;
-       int num;
-       int  res = AST_TEST_PASS;
-
-       /* This test needs at least 5 objects */
-       if (lim < 5) {
-               lim = 5;
-       }
+       const struct test_obj *test_left = obj_left;
 
-       bucket_size = (ast_random() % ((lim / 4) + 1)) + 1;
-       c1 = ao2_t_container_alloc(bucket_size, use_hash ? test_hash_cb : NULL, use_cmp ? test_cmp_cb : NULL, "test");
-       c2 = ao2_t_container_alloc(bucket_size, test_hash_cb, test_cmp_cb, "test");
+       if (flags & OBJ_KEY) {
+               const int *i = obj_right;
 
-       if (!c1 || !c2) {
-               ast_test_status_update(test, "ao2_container_alloc failed.\n");
-               res = AST_TEST_FAIL;
-               goto cleanup;
-       }
+               return test_left->i - *i;
+       } else if (flags & OBJ_PARTIAL_KEY) {
+               int *i = (int *) obj_right;
 
-       /* Create objects and link into container */
-       destructor_count = lim;
-       for (num = 1; num <= lim; num++) {
-               if (!(obj = ao2_t_alloc(sizeof(struct test_obj), test_obj_destructor, "making zombies"))) {
-                       ast_test_status_update(test, "ao2_alloc failed.\n");
-                       res = AST_TEST_FAIL;
-                       goto cleanup;
+               if (*i - partial_key_match_range <= test_left->i
+                       && test_left->i <= *i + partial_key_match_range) {
+                       return 0;
                }
-               obj->destructor_count = &destructor_count;
-               obj->i = num;
-               ao2_link(c1, obj);
-               ao2_t_ref(obj, -1, "test");
-               if (ao2_container_count(c1) != num) {
-                       ast_test_status_update(test, "container did not link correctly\n");
-                       res = AST_TEST_FAIL;
+
+               return test_left->i - *i;
+       } 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;
        }
+}
 
-       ast_test_status_update(test, "Container created: random bucket size %d: number of items: %d\n", bucket_size, lim);
+/*!
+ * \internal
+ * \brief Test container cloning.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param orig Container to clone.
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_container_clone(int res, struct ao2_container *orig, struct ast_test *test)
+{
+       struct ao2_container *clone;
+       struct test_obj *obj;
+       struct test_obj *obj2;
+       struct ao2_iterator iter;
 
-       /* Testing ao2_container_clone */
-       c3 = ao2_container_clone(c1, 0);
-       if (!c3) {
+       clone = ao2_container_clone(orig, 0);
+       if (!clone) {
                ast_test_status_update(test, "ao2_container_clone failed.\n");
-               res = AST_TEST_FAIL;
-               goto cleanup;
+               return AST_TEST_FAIL;
        }
-       if (ao2_container_count(c1) != ao2_container_count(c3)) {
+       if (ao2_container_check(clone, 0)) {
+               ast_test_status_update(test, "container integrity check failed\n");
+               res = AST_TEST_FAIL;
+       } else if (ao2_container_count(orig) != ao2_container_count(clone)) {
                ast_test_status_update(test, "Cloned container does not have the same number of objects.\n");
                res = AST_TEST_FAIL;
        } else {
-               it = ao2_iterator_init(c1, 0);
-               for (; (obj = ao2_t_iterator_next(&it, "test orig")); ao2_t_ref(obj, -1, "test orig")) {
+               iter = ao2_iterator_init(orig, 0);
+               for (; (obj = ao2_t_iterator_next(&iter, "test orig")); ao2_t_ref(obj, -1, "test orig")) {
                        /*
                         * Unlink the matching object from the cloned container to make
                         * the next search faster.  This is a big speed optimization!
-                        * It reduces the container with 100000 objects test time from
-                        * 18 seconds to 200 ms.
                         */
-                       obj2 = ao2_t_callback(c3, OBJ_POINTER | OBJ_UNLINK, ao2_match_by_addr, obj,
+                       obj2 = ao2_t_callback(clone, OBJ_POINTER | OBJ_UNLINK, ao2_match_by_addr, obj,
                                "test clone");
                        if (obj2) {
                                ao2_t_ref(obj2, -1, "test clone");
@@ -185,98 +245,366 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru
                                "Orig container has an object %p not in the clone container.\n", obj);
                        res = AST_TEST_FAIL;
                }
-               ao2_iterator_destroy(&it);
-               if (ao2_container_count(c3)) {
+               ao2_iterator_destroy(&iter);
+               if (ao2_container_count(clone)) {
                        ast_test_status_update(test, "Cloned container still has objects.\n");
                        res = AST_TEST_FAIL;
                }
+               if (ao2_container_check(clone, 0)) {
+                       ast_test_status_update(test, "container integrity check failed\n");
+                       res = AST_TEST_FAIL;
+               }
        }
-       ao2_t_ref(c3, -1, "bye c3");
-       c3 = NULL;
+       ao2_t_ref(clone, -1, "bye clone");
+
+       return res;
+}
+
+/*!
+ * \internal
+ * \brief Test ao2_find with no flags.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param look_in Container to search.
+ * \param limit Container contains objects 0 - (limit - 1).
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_ao2_find_w_no_flags(int res, struct ao2_container *look_in, int limit, struct ast_test *test)
+{
+       int i;
+       int num;
+       struct test_obj tmp_obj = { 0, };
+       struct test_obj *obj;
+
+       for (num = 100; num--;) {
+               i = ast_random() % limit; /* find a random object */
 
-       /* Testing ao2_find with no flags */
-       num = 100;
-       for (; num; num--) {
-               int i = (ast_random() % ((lim / 2)) + 1); /* find a random object */
                tmp_obj.i = i;
-               if (!(obj = ao2_find(c1, &tmp_obj, 0))) {
-                       res = AST_TEST_FAIL;
+               obj = ao2_find(look_in, &tmp_obj, 0);
+               if (!obj) {
                        ast_test_status_update(test, "COULD NOT FIND:%d, ao2_find() with no flags failed.\n", i);
+                       res = AST_TEST_FAIL;
                } else {
-                       /* a correct match will only take place when the custom cmp function is used */
-                       if (use_cmp && obj->i != i) {
-                               ast_test_status_update(test, "object %d does not match object %d\n", obj->i, tmp_obj.i);
+                       if (obj->i != i) {
+                               ast_test_status_update(test, "object %d does not match %d\n", obj->i, i);
                                res = AST_TEST_FAIL;
                        }
                        ao2_t_ref(obj, -1, "test");
                }
        }
 
-       /* Testing ao2_find with OBJ_POINTER */
-       num = 75;
-       for (; num; num--) {
-               int i = (ast_random() % ((lim / 2)) + 1); /* find a random object */
+       return res;
+}
+
+/*!
+ * \internal
+ * \brief Test ao2_find with OBJ_POINTER.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param look_in Container to search.
+ * \param limit Container contains objects 0 - (limit - 1).
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_ao2_find_w_OBJ_POINTER(int res, struct ao2_container *look_in, int limit, struct ast_test *test)
+{
+       int i;
+       int num;
+       struct test_obj tmp_obj = { 0, };
+       struct test_obj *obj;
+
+       for (num = 75; num--;) {
+               i = ast_random() % limit; /* find a random object */
+
                tmp_obj.i = i;
-               if (!(obj = ao2_find(c1, &tmp_obj, OBJ_POINTER))) {
-                       res = AST_TEST_FAIL;
+               obj = ao2_find(look_in, &tmp_obj, OBJ_POINTER);
+               if (!obj) {
                        ast_test_status_update(test, "COULD NOT FIND:%d, ao2_find() with OBJ_POINTER flag failed.\n", i);
+                       res = AST_TEST_FAIL;
                } else {
-                       /* a correct match will only take place when the custom cmp function is used */
-                       if (use_cmp && obj->i != i) {
-                               ast_test_status_update(test, "object %d does not match object %d\n", obj->i, tmp_obj.i);
+                       if (obj->i != i) {
+                               ast_test_status_update(test, "object %d does not match %d\n", obj->i, i);
                                res = AST_TEST_FAIL;
                        }
                        ao2_t_ref(obj, -1, "test");
                }
        }
 
-       /* Testing ao2_find with OBJ_KEY */
-       num = 75;
-       for (; num; num--) {
-               int i = (ast_random() % ((lim / 2)) + 1); /* find a random object */
-               if (!(obj = ao2_find(c1, &i, OBJ_KEY))) {
-                       res = AST_TEST_FAIL;
+       return res;
+}
+
+/*!
+ * \internal
+ * \brief Test ao2_find with OBJ_KEY.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param look_in Container to search.
+ * \param limit Container contains objects 0 - (limit - 1).
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_ao2_find_w_OBJ_KEY(int res, struct ao2_container *look_in, int limit, struct ast_test *test)
+{
+       int i;
+       int num;
+       struct test_obj *obj;
+
+       for (num = 75; num--;) {
+               i = ast_random() % limit; /* find a random object */
+
+               obj = ao2_find(look_in, &i, OBJ_KEY);
+               if (!obj) {
                        ast_test_status_update(test, "COULD NOT FIND:%d, ao2_find() with OBJ_KEY flag failed.\n", i);
+                       res = AST_TEST_FAIL;
+               } else {
+                       if (obj->i != i) {
+                               ast_test_status_update(test, "object %d does not match %d\n", obj->i, i);
+                               res = AST_TEST_FAIL;
+                       }
+                       ao2_t_ref(obj, -1, "test");
+               }
+       }
+
+       return res;
+}
+
+/*!
+ * \internal
+ * \brief Test ao2_find with OBJ_PARTIAL_KEY.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param look_in Container to search.
+ * \param limit Container contains objects 0 - (limit - 1).
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_ao2_find_w_OBJ_PARTIAL_KEY(int res, struct ao2_container *look_in, int limit, struct ast_test *test)
+{
+       int i;
+       int num;
+       struct test_obj *obj;
+
+       /* Set partial match to find exactly. */
+       partial_key_match_range = 0;
+
+       for (num = 100; num--;) {
+               i = ast_random() % limit; /* find a random object */
+
+               obj = ao2_find(look_in, &i, OBJ_PARTIAL_KEY);
+               if (!obj) {
+                       ast_test_status_update(test, "COULD NOT FIND:%d, ao2_find() with OBJ_PARTIAL_KEY flag failed.\n", i);
+                       res = AST_TEST_FAIL;
                } else {
-                       /* a correct match will only take place when the custom cmp function is used */
-                       if (use_cmp && obj->i != i) {
-                               ast_test_status_update(test, "object %d does not match object %d\n", obj->i, tmp_obj.i);
+                       if (obj->i != i) {
+                               ast_test_status_update(test, "object %d does not match %d\n", obj->i, i);
                                res = AST_TEST_FAIL;
                        }
                        ao2_t_ref(obj, -1, "test");
                }
        }
 
-       /* Testing ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE.
+       return res;
+}
+
+static int astobj2_test_1_helper(int tst_num, enum test_container_type type, int use_sort, unsigned int lim, struct ast_test *test)
+{
+       const char *c_type;
+       struct ao2_container *c1;
+       struct ao2_container *c2;
+       struct ao2_iterator it;
+       struct ao2_iterator *mult_it;
+       struct test_obj *obj;
+       ao2_callback_fn *cmp_fn;
+       int n_buckets;
+       int increment = 0;
+       int destructor_count = 0;
+       int count;
+       int num;
+       int res = AST_TEST_PASS;
+
+       c_type = test_container2str(type);
+       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:
+               /* Lists just have one bucket. */
+               n_buckets = 1;
+               c1 = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, 0,
+                       use_sort ? test_sort_cb : NULL, test_cmp_cb, "test");
+               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;
+       }
+       c2 = ao2_t_container_alloc(1, NULL, NULL, "test");
+
+       if (!c1 || !c2) {
+               ast_test_status_update(test, "ao2_container_alloc failed.\n");
+               res = AST_TEST_FAIL;
+               goto cleanup;
+       }
+
+       /* Create objects and link into container */
+       destructor_count = lim;
+       for (num = 0; num < lim; ++num) {
+               if (!(obj = ao2_t_alloc(sizeof(struct test_obj), test_obj_destructor, "making zombies"))) {
+                       ast_test_status_update(test, "ao2_alloc failed.\n");
+                       res = AST_TEST_FAIL;
+                       goto cleanup;
+               }
+               obj->destructor_count = &destructor_count;
+               obj->i = num;
+               ao2_link(c1, obj);
+               ao2_t_ref(obj, -1, "test");
+               if (ao2_container_count(c1) != num + 1) {
+                       ast_test_status_update(test, "container did not link correctly\n");
+                       res = AST_TEST_FAIL;
+               }
+       }
+       if (ao2_container_check(c1, 0)) {
+               ast_test_status_update(test, "container integrity check failed\n");
+               res = AST_TEST_FAIL;
+               goto cleanup;
+       }
+
+       ast_test_status_update(test, "%s container created: buckets: %d, items: %d\n",
+               c_type, n_buckets, lim);
+
+       /* Testing ao2_container_clone */
+       res = test_container_clone(res, c1, test);
+
+       /* Testing ao2_find with no flags */
+       res = test_ao2_find_w_no_flags(res, c1, lim, test);
+
+       /* Testing ao2_find with OBJ_POINTER */
+       res = test_ao2_find_w_OBJ_POINTER(res, c1, lim, test);
+
+       /* Testing ao2_find with OBJ_KEY */
+       res = test_ao2_find_w_OBJ_KEY(res, c1, lim, test);
+
+       /* 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. */
-       num = lim < 25 ? lim : 25;
-       for (; num; num--) {
-               if (!(obj = ao2_find(c1, NULL, OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE))) {
-                       if (!use_cmp) {
-                               ast_test_status_update(test, "ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE failed with default hash function.\n");
-                               res = AST_TEST_FAIL;
+        * 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;
                        }
-               } else {
-                       if (use_cmp) {
-                               ast_test_status_update(test, "ao2_find with OBJ_POINTER | OBJ_UNLINK | OBJ_CONTINUE failed with custom hash function.\n");
-                               res = AST_TEST_FAIL;
+
+                       /* 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");
                        }
-                       ao2_link(c2, obj);
+               }
+               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;
+               }
        }
-       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);
 
        /* Test Callback with no flags. */
        increment = 0;
@@ -294,10 +622,10 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru
                res = AST_TEST_FAIL;
        }
 
-       /* Test OBJ_MULTIPLE with OBJ_UNLINK*/
+       /* Test OBJ_MULTIPLE with OBJ_UNLINK, add items back afterwards */
        num = lim < 25 ? lim : 25;
        if (!(mult_it = ao2_t_callback(c1, OBJ_MULTIPLE | OBJ_UNLINK, multiple_cb, &num, "test multiple"))) {
-               ast_test_status_update(test, "OBJ_MULTIPLE iwth OBJ_UNLINK test failed.\n");
+               ast_test_status_update(test, "OBJ_MULTIPLE with OBJ_UNLINK test failed.\n");
                res = AST_TEST_FAIL;
        } else {
                /* make sure num items unlinked is as expected */
@@ -305,6 +633,11 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru
                        ast_test_status_update(test, "OBJ_MULTIPLE | OBJ_UNLINK test failed, did not unlink correct number of objects.\n");
                        res = AST_TEST_FAIL;
                }
+               if (ao2_container_check(c1, 0)) {
+                       ast_test_status_update(test, "container integrity check failed\n");
+                       res = AST_TEST_FAIL;
+                       goto cleanup;
+               }
 
                /* link what was unlinked back into c1 */
                while ((obj = ao2_t_iterator_next(mult_it, "test"))) {
@@ -312,10 +645,15 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru
                        ao2_t_ref(obj, -1, "test"); /* remove ref from iterator */
                }
                ao2_iterator_destroy(mult_it);
+               if (ao2_container_check(c1, 0)) {
+                       ast_test_status_update(test, "container integrity check failed\n");
+                       res = AST_TEST_FAIL;
+                       goto cleanup;
+               }
        }
 
-       /* Test OBJ_MULTIPLE without unlink, add items back afterwards */
-       num = lim < 25 ? lim : 25;
+       /* Test OBJ_MULTIPLE without unlink and iterate the returned container */
+       num = 5;
        if (!(mult_it = ao2_t_callback(c1, OBJ_MULTIPLE, multiple_cb, &num, "test multiple"))) {
                ast_test_status_update(test, "OBJ_MULTIPLE without OBJ_UNLINK test failed.\n");
                res = AST_TEST_FAIL;
@@ -327,7 +665,7 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru
        }
 
        /* Test OBJ_MULTIPLE without unlink and no iterating */
-       num = lim < 5 ? lim : 5;
+       num = 5;
        if (!(mult_it = ao2_t_callback(c1, OBJ_MULTIPLE, multiple_cb, &num, "test multiple"))) {
                ast_test_status_update(test, "OBJ_MULTIPLE with no OBJ_UNLINK and no iterating failed.\n");
                res = AST_TEST_FAIL;
@@ -343,11 +681,18 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru
 
        /* Testing iterator.  Unlink a single object and break. do not add item back */
        it = ao2_iterator_init(c1, 0);
-       num = (lim / 4) + 1;
+       num = ast_random() % lim; /* remove a random object */
+       if (!num) {
+               /*
+                * Well we cannot remove object zero because of test with
+                * all_but_one_cb later.
+                */
+               num = 1;
+       }
        while ((obj = ao2_t_iterator_next(&it, "test"))) {
                if (obj->i == num) {
-                       ao2_t_ref(obj, -1, "test");
                        ao2_t_unlink(c1, obj, "test");
+                       ao2_t_ref(obj, -1, "test");
                        break;
                }
                ao2_t_ref(obj, -1, "test");
@@ -359,6 +704,11 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru
                ast_test_status_update(test, "unlink during iterator failed. Number %d was not removed.\n", num);
                res = AST_TEST_FAIL;
        }
+       if (ao2_container_check(c1, 0)) {
+               ast_test_status_update(test, "container integrity check failed\n");
+               res = AST_TEST_FAIL;
+               goto cleanup;
+       }
 
        /* Test unlink all with OBJ_MULTIPLE, leave a single object for the container to destroy */
        ao2_t_callback(c1, OBJ_MULTIPLE | OBJ_UNLINK | OBJ_NODATA, all_but_one_cb, NULL, "test multiple");
@@ -367,6 +717,10 @@ static int astobj2_test_helper(int use_hash, int use_cmp, unsigned int lim, stru
                ast_test_status_update(test, "OBJ_MULTIPLE | OBJ_UNLINK | OBJ_NODATA failed. destructor count %d\n", destructor_count);
                res = AST_TEST_FAIL;
        }
+       if (ao2_container_check(c1, 0)) {
+               ast_test_status_update(test, "container integrity check failed\n");
+               res = AST_TEST_FAIL;
+       }
 
 cleanup:
        /* destroy containers */
@@ -376,9 +730,6 @@ cleanup:
        if (c2) {
                ao2_t_ref(c2, -1, "bye c2");
        }
-       if (c3) {
-               ao2_t_ref(c3, -1, "bye c3");
-       }
 
        if (destructor_count > 0) {
                ast_test_status_update(test, "all destructors were not called, destructor count is %d\n", destructor_count);
@@ -399,7 +750,7 @@ AST_TEST_DEFINE(astobj2_test_1)
        case TEST_INIT:
                info->name = "astobj2_test1";
                info->category = "/main/astobj2/";
-               info->summary = "astobj2 test using ao2 objects, containers, callbacks, and iterators";
+               info->summary = "Test ao2 objects, containers, callbacks, and iterators";
                info->description =
                        "Builds ao2_containers with various item numbers, bucket sizes, cmp and hash "
                        "functions. Runs a series of tests to manipulate the container using callbacks "
@@ -409,28 +760,20 @@ AST_TEST_DEFINE(astobj2_test_1)
                break;
        }
 
-
-       /* Test 1, 500 items with custom hash and cmp functions */
-       ast_test_status_update(test, "Test 1, astobj2 test with 500 items.\n");
-       if ((res = astobj2_test_helper(1, 1, 500, test)) == AST_TEST_FAIL) {
+       /* Test number, container_type, use_sort, number of objects. */
+       if ((res = astobj2_test_1_helper(1, TEST_CONTAINER_LIST, 0, 50, test)) == AST_TEST_FAIL) {
                return res;
        }
 
-       /* Test 2, 1000 items with custom hash and default cmp functions */
-       ast_test_status_update(test, "Test 2, astobj2 test with 1000 items.\n");
-       if ((res = astobj2_test_helper(1, 0, 1000, test)) == AST_TEST_FAIL) {
+       if ((res = astobj2_test_1_helper(2, TEST_CONTAINER_LIST, 1, 50, test)) == AST_TEST_FAIL) {
                return res;
        }
 
-       /* Test 3, 10000 items with default hash and custom cmp functions */
-       ast_test_status_update(test, "Test 3, astobj2 test with 10000 items.\n");
-       if ((res = astobj2_test_helper(0, 1, 10000, test)) == AST_TEST_FAIL) {
+       if ((res = astobj2_test_1_helper(3, TEST_CONTAINER_HASH, 0, 1000, test)) == AST_TEST_FAIL) {
                return res;
        }
 
-       /* Test 4, 100000 items with default hash and cmp functions */
-       ast_test_status_update(test, "Test 4, astobj2 test with 100000 items.\n");
-       if ((res = astobj2_test_helper(0, 0, 100000, test)) == AST_TEST_FAIL) {
+       if ((res = astobj2_test_1_helper(4, TEST_CONTAINER_HASH, 1, 1000, test)) == AST_TEST_FAIL) {
                return res;
        }
 
@@ -484,6 +827,11 @@ AST_TEST_DEFINE(astobj2_test_2)
                        res = AST_TEST_FAIL;
                }
        }
+       if (ao2_container_check(c, 0)) {
+               ast_test_status_update(test, "container integrity check failed\n");
+               res = AST_TEST_FAIL;
+               goto cleanup;
+       }
 
        /*
         * Iteration take 1.  Just make sure we see all NUM_OBJS objects.
@@ -698,11 +1046,929 @@ cleanup:
        return res;
 }
 
+/*!
+ * \internal
+ * \brief Make a nonsorted container for astobj2 testing.
+ * \since 12.0.0
+ *
+ * \param type Container type to create.
+ * \param options Container options
+ *
+ * \retval container on success.
+ * \retval NULL on error.
+ */
+static struct ao2_container *test_make_nonsorted(enum test_container_type type, int options)
+{
+       struct ao2_container *container;
+
+       container = NULL;
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               container = ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, options,
+                       NULL, test_cmp_cb);
+               break;
+       case TEST_CONTAINER_HASH:
+               container = ao2_container_alloc_hash(AO2_ALLOC_OPT_LOCK_MUTEX, options, 5,
+                       test_hash_cb, NULL, test_cmp_cb);
+               break;
+       }
+
+       return container;
+}
+
+/*!
+ * \internal
+ * \brief Make a sorted container for astobj2 testing.
+ * \since 12.0.0
+ *
+ * \param type Container type to create.
+ * \param options Container options
+ *
+ * \retval container on success.
+ * \retval NULL on error.
+ */
+static struct ao2_container *test_make_sorted(enum test_container_type type, int options)
+{
+       struct ao2_container *container;
+
+       container = NULL;
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               container = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, options,
+                       test_sort_cb, test_cmp_cb, "test");
+               break;
+       case TEST_CONTAINER_HASH:
+               container = ao2_t_container_alloc_hash(AO2_ALLOC_OPT_LOCK_MUTEX, options, 5,
+                       test_hash_cb, test_sort_cb, test_cmp_cb, "test");
+               break;
+       }
+
+       return container;
+}
+
+/*!
+ * \internal
+ * \brief Insert the given test vector into the given container.
+ * \since 12.0.0
+ *
+ * \note The given test vector must not have any duplicates.
+ *
+ * \param container Container to insert the test vector.
+ * \param destroy_counter What to increment when the object is destroyed.
+ * \param vector Test vector to insert.
+ * \param count Number of objects in the vector.
+ * \param prefix Test output prefix string.
+ * \param test Test output controller.
+ *
+ * \retval 0 on success.
+ * \retval -1 on error.
+ */
+static int insert_test_vector(struct ao2_container *container, int *destroy_counter, const int *vector, int count, const char *prefix, struct ast_test *test)
+{
+       int idx;
+       struct test_obj *obj;
+
+       for (idx = 0; idx < count; ++idx) {
+               obj = ao2_alloc(sizeof(struct test_obj), test_obj_destructor);
+               if (!obj) {
+                       ast_test_status_update(test, "%s: ao2_alloc failed.\n", prefix);
+                       return -1;
+               }
+               if (destroy_counter) {
+                       /* This object ultimately needs to be destroyed. */
+                       ++*destroy_counter;
+               }
+               obj->destructor_count = destroy_counter;
+               obj->i = vector[idx];
+               ao2_link(container, obj);
+               ao2_t_ref(obj, -1, "test");
+
+               if (ao2_container_count(container) != idx + 1) {
+                       ast_test_status_update(test,
+                               "%s: Unexpected container count.  Expected:%d Got:%d\n",
+                               prefix, idx + 1, ao2_container_count(container));
+                       return -1;
+               }
+       }
+       if (ao2_container_check(container, 0)) {
+               ast_test_status_update(test, "%s: Container integrity check failed\n", prefix);
+               return -1;
+       }
+
+       return 0;
+}
+
+/*!
+ * \internal
+ * \brief Insert duplicates of number into the given container.
+ * \since 12.0.0
+ *
+ * \note The given container must not already have the number in it.
+ *
+ * \param container Container to insert the duplicates.
+ * \param destroy_counter What to increment when the object is destroyed.
+ * \param number Number of object to duplicate.
+ * \param prefix Test output prefix string.
+ * \param test Test output controller.
+ *
+ * \retval 0 on success.
+ * \retval -1 on error.
+ */
+static int insert_test_duplicates(struct ao2_container *container, int *destroy_counter, int number, const char *prefix, struct ast_test *test)
+{
+       int count;
+       struct test_obj *obj;
+       struct test_obj *obj_dup;
+
+       /* Check if object already exists in the container. */
+       obj = ao2_find(container, &number, OBJ_KEY);
+       if (obj) {
+               ast_test_status_update(test, "%s: Object %d already exists.\n", prefix, number);
+               ao2_t_ref(obj, -1, "test");
+               return -1;
+       }
+
+       /* Add three duplicate keyed objects. */
+       obj_dup = NULL;
+       for (count = 0; count < 4; ++count) {
+               obj = ao2_alloc(sizeof(struct test_obj), test_obj_destructor);
+               if (!obj) {
+                       ast_test_status_update(test, "%s: ao2_alloc failed.\n", prefix);
+                       if (obj_dup) {
+                               ao2_t_ref(obj_dup, -1, "test");
+                       }
+                       return -1;
+               }
+               if (destroy_counter) {
+                       /* This object ultimately needs to be destroyed. */
+                       ++*destroy_counter;
+               }
+               obj->destructor_count = destroy_counter;
+               obj->i = number;
+               obj->dup_number = count;
+               ao2_link(container, obj);
+
+               if (count == 2) {
+                       /* Duplicate this object. */
+                       obj_dup = obj;
+               } else {
+                       ao2_t_ref(obj, -1, "test");
+               }
+       }
+
+       /* Add the duplicate object. */
+       ao2_link(container, obj_dup);
+       ao2_t_ref(obj_dup, -1, "test");
+
+       if (ao2_container_check(container, 0)) {
+               ast_test_status_update(test, "%s: Container integrity check failed\n", prefix);
+               return -1;
+       }
+
+       return 0;
+}
+
+/*!
+ * \internal
+ * \brief Iterate over the container and compare the objects with the given vector.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param container Container to iterate.
+ * \param flags Flags controlling the iteration.
+ * \param vector Expected vector to find.
+ * \param count Number of objects in the vector.
+ * \param prefix Test output prefix string.
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_ao2_iteration(int res, struct ao2_container *container,
+       enum ao2_iterator_flags flags,
+       const int *vector, int count, const char *prefix, struct ast_test *test)
+{
+       struct ao2_iterator iter;
+       struct test_obj *obj;
+       int idx;
+
+       if (ao2_container_count(container) != count) {
+               ast_test_status_update(test, "%s: Container count doesn't match vector count.\n",
+                       prefix);
+               res = AST_TEST_FAIL;
+       }
+
+       iter = ao2_iterator_init(container, flags);
+
+       /* Check iterated objects against the given vector. */
+       for (idx = 0; idx < count; ++idx) {
+               obj = ao2_iterator_next(&iter);
+               if (!obj) {
+                       ast_test_status_update(test, "%s: Too few objects found.\n", prefix);
+                       res = AST_TEST_FAIL;
+                       break;
+               }
+               if (vector[idx] != obj->i) {
+                       ast_test_status_update(test, "%s: Object %d != vector[%d] %d.\n",
+                               prefix, obj->i, idx, vector[idx]);
+                       res = AST_TEST_FAIL;
+               }
+               ao2_ref(obj, -1); /* remove ref from iterator */
+       }
+       obj = ao2_iterator_next(&iter);
+       if (obj) {
+               ast_test_status_update(test, "%s: Too many objects found.  Object %d\n",
+                       prefix, obj->i);
+               ao2_ref(obj, -1); /* remove ref from iterator */
+               res = AST_TEST_FAIL;
+       }
+
+       ao2_iterator_destroy(&iter);
+
+       return res;
+}
+
+/*!
+ * \internal
+ * \brief Run an ao2_callback() and compare the returned vector with the given vector.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param container Container to traverse.
+ * \param flags Callback flags controlling the traversal.
+ * \param cmp_fn Compare function to select objects.
+ * \param arg Optional argument.
+ * \param vector Expected vector to find.
+ * \param count Number of objects in the vector.
+ * \param prefix Test output prefix string.
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_ao2_callback_traversal(int res, struct ao2_container *container,
+       enum search_flags flags, ao2_callback_fn *cmp_fn, void *arg,
+       const int *vector, int count, const char *prefix, struct ast_test *test)
+{
+       struct ao2_iterator *mult_iter;
+       struct test_obj *obj;
+       int idx;
+
+       mult_iter = ao2_callback(container, flags | OBJ_MULTIPLE, cmp_fn, arg);
+       if (!mult_iter) {
+               ast_test_status_update(test, "%s: Did not return iterator.\n", prefix);
+               return AST_TEST_FAIL;
+       }
+
+       /* Check matching objects against the given vector. */
+       for (idx = 0; idx < count; ++idx) {
+               obj = ao2_iterator_next(mult_iter);
+               if (!obj) {
+                       ast_test_status_update(test, "%s: Too few objects found.\n", prefix);
+                       res = AST_TEST_FAIL;
+                       break;
+               }
+               if (vector[idx] != obj->i) {
+                       ast_test_status_update(test, "%s: Object %d != vector[%d] %d.\n",
+                               prefix, obj->i, idx, vector[idx]);
+                       res = AST_TEST_FAIL;
+               }
+               ao2_ref(obj, -1); /* remove ref from iterator */
+       }
+       obj = ao2_iterator_next(mult_iter);
+       if (obj) {
+               ast_test_status_update(test, "%s: Too many objects found.  Object %d\n",
+                       prefix, obj->i);
+               ao2_ref(obj, -1); /* remove ref from iterator */
+               res = AST_TEST_FAIL;
+       }
+       ao2_iterator_destroy(mult_iter);
+
+       return res;
+}
+
+/*!
+ * \internal
+ * \brief Run an ao2_find() for duplicates and compare the returned vector with the given vector.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param container Container to traverse.
+ * \param flags Callback flags controlling the traversal.
+ * \param number Number of object to find all duplicates.
+ * \param vector Expected vector to find.
+ * \param count Number of objects in the vector.
+ * \param prefix Test output prefix string.
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_expected_duplicates(int res, struct ao2_container *container,
+       enum search_flags flags, int number,
+       const int *vector, int count, const char *prefix, struct ast_test *test)
+{
+       struct ao2_iterator *mult_iter;
+       struct test_obj *obj;
+       int idx;
+
+       mult_iter = ao2_find(container, &number, flags | OBJ_MULTIPLE | OBJ_KEY);
+       if (!mult_iter) {
+               ast_test_status_update(test, "%s: Did not return iterator.\n", prefix);
+               return AST_TEST_FAIL;
+       }
+
+       /* Check matching objects against the given vector. */
+       for (idx = 0; idx < count; ++idx) {
+               obj = ao2_iterator_next(mult_iter);
+               if (!obj) {
+                       ast_test_status_update(test, "%s: Too few objects found.\n", prefix);
+                       res = AST_TEST_FAIL;
+                       break;
+               }
+               if (number != obj->i) {
+                       ast_test_status_update(test, "%s: Object %d != %d.\n",
+                               prefix, obj->i, number);
+                       res = AST_TEST_FAIL;
+               }
+               if (vector[idx] != obj->dup_number) {
+                       ast_test_status_update(test, "%s: Object dup id %d != vector[%d] %d.\n",
+                               prefix, obj->dup_number, idx, vector[idx]);
+                       res = AST_TEST_FAIL;
+               }
+               ao2_ref(obj, -1); /* remove ref from iterator */
+       }
+       obj = ao2_iterator_next(mult_iter);
+       if (obj) {
+               ast_test_status_update(test,
+                       "%s: Too many objects found.  Object %d, dup id %d\n",
+                       prefix, obj->i, obj->dup_number);
+               ao2_ref(obj, -1); /* remove ref from iterator */
+               res = AST_TEST_FAIL;
+       }
+       ao2_iterator_destroy(mult_iter);
+
+       return res;
+}
+
+/*!
+ * \internal
+ * \brief Test nonsorted container traversal.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param tst_num Test number.
+ * \param type Container type to test.
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_traversal_nonsorted(int res, int tst_num, enum test_container_type type, struct ast_test *test)
+{
+       struct ao2_container *c1;
+       struct ao2_container *c2 = NULL;
+       int partial;
+       int destructor_count = 0;
+
+       /*! Container object insertion vector. */
+       static const int test_initial[] = {
+               1, 0, 2, 6, 4, 7, 5, 3, 9, 8
+       };
+
+       /*! Container object insertion vector reversed. */
+       static const int test_reverse[] = {
+               8, 9, 3, 5, 7, 4, 6, 2, 0, 1
+       };
+       static const int test_list_partial_forward[] = {
+               6, 7, 5
+       };
+       static const int test_list_partial_backward[] = {
+               5, 7, 6
+       };
+
+       /* The hash orders assume that there are 5 buckets. */
+       static const int test_hash_end_forward[] = {
+               0, 5, 1, 6, 2, 7, 3, 8, 4, 9
+       };
+       static const int test_hash_end_backward[] = {
+               9, 4, 8, 3, 7, 2, 6, 1, 5, 0
+       };
+       static const int test_hash_begin_forward[] = {
+               5, 0, 6, 1, 7, 2, 8, 3, 9, 4
+       };
+       static const int test_hash_begin_backward[] = {
+               4, 9, 3, 8, 2, 7, 1, 6, 0, 5
+       };
+       static const int test_hash_partial_forward[] = {
+               5, 6, 7
+       };
+       static const int test_hash_partial_backward[] = {
+               7, 6, 5
+       };
+
+       ast_test_status_update(test, "Test %d, %s containers.\n",
+               tst_num, test_container2str(type));
+
+       /* Create container that inserts objects at the end. */
+       c1 = test_make_nonsorted(type, 0);
+       if (!c1) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+
+       /* Create container that inserts objects at the beginning. */
+       c2 = test_make_nonsorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN);
+       if (!c2) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+
+       /* Check container iteration directions */
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               res = test_ao2_iteration(res, c1, 0,
+                       test_initial, ARRAY_LEN(test_initial),
+                       "Iteration (ascending, insert end)", test);
+               res = test_ao2_iteration(res, c1, AO2_ITERATOR_DESCENDING,
+                       test_reverse, ARRAY_LEN(test_reverse),
+                       "Iteration (descending, insert end)", test);
+
+               res = test_ao2_iteration(res, c2, 0,
+                       test_reverse, ARRAY_LEN(test_reverse),
+                       "Iteration (ascending, insert begin)", test);
+               res = test_ao2_iteration(res, c2, AO2_ITERATOR_DESCENDING,
+                       test_initial, ARRAY_LEN(test_initial),
+                       "Iteration (descending, insert begin)", test);
+               break;
+       case TEST_CONTAINER_HASH:
+               res = test_ao2_iteration(res, c1, 0,
+                       test_hash_end_forward, ARRAY_LEN(test_hash_end_forward),
+                       "Iteration (ascending, insert end)", test);
+               res = test_ao2_iteration(res, c1, AO2_ITERATOR_DESCENDING,
+                       test_hash_end_backward, ARRAY_LEN(test_hash_end_backward),
+                       "Iteration (descending, insert end)", test);
+
+               res = test_ao2_iteration(res, c2, 0,
+                       test_hash_begin_forward, ARRAY_LEN(test_hash_begin_forward),
+                       "Iteration (ascending, insert begin)", test);
+               res = test_ao2_iteration(res, c2, AO2_ITERATOR_DESCENDING,
+                       test_hash_begin_backward, ARRAY_LEN(test_hash_begin_backward),
+                       "Iteration (descending, insert begin)", test);
+               break;
+       }
+
+       /* Check container traversal directions */
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_ASCENDING, NULL, NULL,
+                       test_initial, ARRAY_LEN(test_initial),
+                       "Traversal (ascending, insert end)", test);
+               res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_DESCENDING, NULL, NULL,
+                       test_reverse, ARRAY_LEN(test_reverse),
+                       "Traversal (descending, insert end)", test);
+
+               res = test_ao2_callback_traversal(res, c2, OBJ_ORDER_ASCENDING, NULL, NULL,
+                       test_reverse, ARRAY_LEN(test_reverse),
+                       "Traversal (ascending, insert begin)", test);
+               res = test_ao2_callback_traversal(res, c2, OBJ_ORDER_DESCENDING, NULL, NULL,
+                       test_initial, ARRAY_LEN(test_initial),
+                       "Traversal (descending, insert begin)", test);
+               break;
+       case TEST_CONTAINER_HASH:
+               res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_ASCENDING, NULL, NULL,
+                       test_hash_end_forward, ARRAY_LEN(test_hash_end_forward),
+                       "Traversal (ascending, insert end)", test);
+               res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_DESCENDING, NULL, NULL,
+                       test_hash_end_backward, ARRAY_LEN(test_hash_end_backward),
+                       "Traversal (descending, insert end)", test);
+
+               res = test_ao2_callback_traversal(res, c2, OBJ_ORDER_ASCENDING, NULL, NULL,
+                       test_hash_begin_forward, ARRAY_LEN(test_hash_begin_forward),
+                       "Traversal (ascending, insert begin)", test);
+               res = test_ao2_callback_traversal(res, c2, OBJ_ORDER_DESCENDING, NULL, NULL,
+                       test_hash_begin_backward, ARRAY_LEN(test_hash_begin_backward),
+                       "Traversal (descending, insert begin)", test);
+               break;
+       }
+
+       /* Check traversal with OBJ_PARTIAL_KEY search range. */
+       partial = 6;
+       partial_key_match_range = 1;
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_ASCENDING,
+                       test_cmp_cb, &partial,
+                       test_list_partial_forward, ARRAY_LEN(test_list_partial_forward),
+                       "Traversal OBJ_PARTIAL_KEY (ascending)", test);
+               res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_DESCENDING,
+                       test_cmp_cb, &partial,
+                       test_list_partial_backward, ARRAY_LEN(test_list_partial_backward),
+                       "Traversal OBJ_PARTIAL_KEY (descending)", test);
+               break;
+       case TEST_CONTAINER_HASH:
+               res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_ASCENDING,
+                       test_cmp_cb, &partial,
+                       test_hash_partial_forward, ARRAY_LEN(test_hash_partial_forward),
+                       "Traversal OBJ_PARTIAL_KEY (ascending)", test);
+               res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_DESCENDING,
+                       test_cmp_cb, &partial,
+                       test_hash_partial_backward, ARRAY_LEN(test_hash_partial_backward),
+                       "Traversal OBJ_PARTIAL_KEY (descending)", test);
+               break;
+       }
+
+test_cleanup:
+       /* destroy containers */
+       if (c1) {
+               ao2_t_ref(c1, -1, "bye c1");
+       }
+       if (c2) {
+               ao2_t_ref(c2, -1, "bye c2");
+       }
+
+       if (destructor_count > 0) {
+               ast_test_status_update(test,
+                       "all destructors were not called, destructor count is %d\n",
+                       destructor_count);
+               res = AST_TEST_FAIL;
+       } else if (destructor_count < 0) {
+               ast_test_status_update(test,
+                       "Destructor was called too many times, destructor count is %d\n",
+                       destructor_count);
+               res = AST_TEST_FAIL;
+       }
+
+       return res;
+}
+
+/*!
+ * \internal
+ * \brief Test sorted container traversal.
+ * \since 12.0.0
+ *
+ * \param res Passed in enum ast_test_result_state.
+ * \param tst_num Test number.
+ * \param type Container type to test.
+ * \param test Test output controller.
+ *
+ * \return enum ast_test_result_state
+ */
+static int test_traversal_sorted(int res, int tst_num, enum test_container_type type, struct ast_test *test)
+{
+       struct ao2_container *c1;
+       struct ao2_container *c2 = NULL;
+       int partial;
+       int destructor_count = 0;
+       int duplicate_number = 100;
+
+       /*! Container object insertion vector. */
+       static const int test_initial[] = {
+               1, 0, 2, 6, 4, 7, 5, 3, 9, 8
+       };
+
+       /*! Container forward traversal/iteration. */
+       static const int test_forward[] = {
+               0, 1, 2, 3, 4, 5, 6, 7, 8, 9
+       };
+       /*! Container backward traversal/iteration. */
+       static const int test_backward[] = {
+               9, 8, 7, 6, 5, 4, 3, 2, 1, 0
+       };
+
+       static const int test_partial_forward[] = {
+               5, 6, 7
+       };
+       static const int test_partial_backward[] = {
+               7, 6, 5
+       };
+
+       /* The hash orders assume that there are 5 buckets. */
+       static const int test_hash_forward[] = {
+               0, 5, 1, 6, 2, 7, 3, 8, 4, 9
+       };
+       static const int test_hash_backward[] = {
+               9, 4, 8, 3, 7, 2, 6, 1, 5, 0
+       };
+       static const int test_hash_partial_forward[] = {
+               5, 6, 7
+       };
+       static const int test_hash_partial_backward[] = {
+               7, 6, 5
+       };
+
+       /* Duplicate identifier order */
+       static const int test_dup_allow_forward[] = {
+               0, 1, 2, 3, 2
+       };
+       static const int test_dup_allow_backward[] = {
+               2, 3, 2, 1, 0
+       };
+       static const int test_dup_reject[] = {
+               0
+       };
+       static const int test_dup_obj_reject_forward[] = {
+               0, 1, 2, 3
+       };
+       static const int test_dup_obj_reject_backward[] = {
+               3, 2, 1, 0
+       };
+       static const int test_dup_replace[] = {
+               2
+       };
+
+       ast_test_status_update(test, "Test %d, %s containers.\n",
+               tst_num, test_container2str(type));
+
+       /* Create container that inserts duplicate objects after matching objects. */
+       c1 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW);
+       if (!c1) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1(DUPS_ALLOW)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+
+       /* Create container that inserts duplicate objects before matching objects. */
+       c2 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN | AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW);
+       if (!c2) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2(DUPS_ALLOW)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+
+       /* Check container iteration directions */
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               res = test_ao2_iteration(res, c1, 0,
+                       test_forward, ARRAY_LEN(test_forward),
+                       "Iteration (ascending)", test);
+               res = test_ao2_iteration(res, c1, AO2_ITERATOR_DESCENDING,
+                       test_backward, ARRAY_LEN(test_backward),
+                       "Iteration (descending)", test);
+               break;
+       case TEST_CONTAINER_HASH:
+               res = test_ao2_iteration(res, c1, 0,
+                       test_hash_forward, ARRAY_LEN(test_hash_forward),
+                       "Iteration (ascending)", test);
+               res = test_ao2_iteration(res, c1, AO2_ITERATOR_DESCENDING,
+                       test_hash_backward, ARRAY_LEN(test_hash_backward),
+                       "Iteration (descending)", test);
+               break;
+       }
+
+       /* Check container traversal directions */
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_ASCENDING, NULL, NULL,
+                       test_forward, ARRAY_LEN(test_forward),
+                       "Traversal (ascending)", test);
+               res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_DESCENDING, NULL, NULL,
+                       test_backward, ARRAY_LEN(test_backward),
+                       "Traversal (descending)", test);
+               break;
+       case TEST_CONTAINER_HASH:
+               res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_ASCENDING, NULL, NULL,
+                       test_hash_forward, ARRAY_LEN(test_hash_forward),
+                       "Traversal (ascending, insert end)", test);
+               res = test_ao2_callback_traversal(res, c1, OBJ_ORDER_DESCENDING, NULL, NULL,
+                       test_hash_backward, ARRAY_LEN(test_hash_backward),
+                       "Traversal (descending)", test);
+               break;
+       }
+
+       /* Check traversal with OBJ_PARTIAL_KEY search range. */
+       partial = 6;
+       partial_key_match_range = 1;
+       switch (type) {
+       case TEST_CONTAINER_LIST:
+               res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_ASCENDING,
+                       test_cmp_cb, &partial,
+                       test_partial_forward, ARRAY_LEN(test_partial_forward),
+                       "Traversal OBJ_PARTIAL_KEY (ascending)", test);
+               res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_DESCENDING,
+                       test_cmp_cb, &partial,
+                       test_partial_backward, ARRAY_LEN(test_partial_backward),
+                       "Traversal OBJ_PARTIAL_KEY (descending)", test);
+               break;
+       case TEST_CONTAINER_HASH:
+               res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_ASCENDING,
+                       test_cmp_cb, &partial,
+                       test_hash_partial_forward, ARRAY_LEN(test_hash_partial_forward),
+                       "Traversal OBJ_PARTIAL_KEY (ascending)", test);
+               res = test_ao2_callback_traversal(res, c1, OBJ_PARTIAL_KEY | OBJ_ORDER_DESCENDING,
+                       test_cmp_cb, &partial,
+                       test_hash_partial_backward, ARRAY_LEN(test_hash_partial_backward),
+                       "Traversal OBJ_PARTIAL_KEY (descending)", test);
+               break;
+       }
+
+       /* Add duplicates to initial containers that allow duplicates */
+       if (insert_test_duplicates(c1, &destructor_count, duplicate_number, "c1(DUPS_ALLOW)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_duplicates(c2, &destructor_count, duplicate_number, "c2(DUPS_ALLOW)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+
+       /* Check duplicates in containers that allow duplicates. */
+       res = test_expected_duplicates(res, c1, OBJ_ORDER_ASCENDING, duplicate_number,
+               test_dup_allow_forward, ARRAY_LEN(test_dup_allow_forward),
+               "Duplicates (ascending, DUPS_ALLOW)", test);
+       res = test_expected_duplicates(res, c1, OBJ_ORDER_DESCENDING, duplicate_number,
+               test_dup_allow_backward, ARRAY_LEN(test_dup_allow_backward),
+               "Duplicates (descending, DUPS_ALLOW)", test);
+
+       ao2_t_ref(c1, -1, "bye c1");
+       c1 = NULL;
+       ao2_t_ref(c2, -1, "bye c2");
+       c2 = NULL;
+
+       /* Create containers that reject duplicate keyed objects. */
+       c1 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT);
+       if (!c1) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1(DUPS_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_duplicates(c1, &destructor_count, duplicate_number, "c1(DUPS_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       c2 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN | AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT);
+       if (!c2) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2(DUPS_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_duplicates(c2, &destructor_count, duplicate_number, "c2(DUPS_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+
+       /* Check duplicates in containers that reject duplicate keyed objects. */
+       res = test_expected_duplicates(res, c1, OBJ_ORDER_ASCENDING, duplicate_number,
+               test_dup_reject, ARRAY_LEN(test_dup_reject),
+               "Duplicates (ascending, DUPS_REJECT)", test);
+       res = test_expected_duplicates(res, c1, OBJ_ORDER_DESCENDING, duplicate_number,
+               test_dup_reject, ARRAY_LEN(test_dup_reject),
+               "Duplicates (descending, DUPS_REJECT)", test);
+
+       ao2_t_ref(c1, -1, "bye c1");
+       c1 = NULL;
+       ao2_t_ref(c2, -1, "bye c2");
+       c2 = NULL;
+
+       /* Create containers that reject duplicate objects. */
+       c1 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT);
+       if (!c1) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1(DUPS_OBJ_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_duplicates(c1, &destructor_count, duplicate_number, "c1(DUPS_OBJ_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       c2 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN | AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT);
+       if (!c2) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2(DUPS_OBJ_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_duplicates(c2, &destructor_count, duplicate_number, "c2(DUPS_OBJ_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+
+       /* Check duplicates in containers that reject duplicate objects. */
+       res = test_expected_duplicates(res, c1, OBJ_ORDER_ASCENDING, duplicate_number,
+               test_dup_obj_reject_forward, ARRAY_LEN(test_dup_obj_reject_forward),
+               "Duplicates (ascending, DUPS_OBJ_REJECT)", test);
+       res = test_expected_duplicates(res, c1, OBJ_ORDER_DESCENDING, duplicate_number,
+               test_dup_obj_reject_backward, ARRAY_LEN(test_dup_obj_reject_backward),
+               "Duplicates (descending, DUPS_OBJ_REJECT)", test);
+
+       ao2_t_ref(c1, -1, "bye c1");
+       c1 = NULL;
+       ao2_t_ref(c2, -1, "bye c2");
+       c2 = NULL;
+
+       /* Create container that replaces duplicate keyed objects. */
+       c1 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE);
+       if (!c1) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c1, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c1(DUPS_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_duplicates(c1, &destructor_count, duplicate_number, "c1(DUPS_REJECT)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       c2 = test_make_sorted(type, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN | AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE);
+       if (!c2) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_vector(c2, &destructor_count, test_initial, ARRAY_LEN(test_initial), "c2(DUPS_REPLACE)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+       if (insert_test_duplicates(c2, &destructor_count, duplicate_number, "c2(DUPS_REPLACE)", test)) {
+               res = AST_TEST_FAIL;
+               goto test_cleanup;
+       }
+
+       /* Check duplicates in containers that replaces duplicate keyed objects. */
+       res = test_expected_duplicates(res, c1, OBJ_ORDER_ASCENDING, duplicate_number,
+               test_dup_replace, ARRAY_LEN(test_dup_replace),
+               "Duplicates (ascending, DUPS_REPLACE)", test);
+       res = test_expected_duplicates(res, c1, OBJ_ORDER_DESCENDING, duplicate_number,
+               test_dup_replace, ARRAY_LEN(test_dup_replace),
+               "Duplicates (descending, DUPS_REPLACE)", test);
+
+test_cleanup:
+       /* destroy containers */
+       if (c1) {
+               ao2_t_ref(c1, -1, "bye c1");
+       }
+       if (c2) {
+               ao2_t_ref(c2, -1, "bye c2");
+       }
+
+       if (destructor_count > 0) {
+               ast_test_status_update(test,
+                       "all destructors were not called, destructor count is %d\n",
+                       destructor_count);
+               res = AST_TEST_FAIL;
+       } else if (destructor_count < 0) {
+               ast_test_status_update(test,
+                       "Destructor was called too many times, destructor count is %d\n",
+                       destructor_count);
+               res = AST_TEST_FAIL;
+       }
+
+       return res;
+}
+
+AST_TEST_DEFINE(astobj2_test_4)
+{
+       int res = AST_TEST_PASS;
+
+       switch (cmd) {
+       case TEST_INIT:
+               info->name = "astobj2_test4";
+               info->category = "/main/astobj2/";
+               info->summary = "Test container traversal/iteration";
+               info->description =
+                       "This test is to see if the container traversal/iteration works "
+                       "as intended for each supported container type.";
+               return AST_TEST_NOT_RUN;
+       case TEST_EXECUTE:
+               break;
+       }
+
+       res = test_traversal_nonsorted(res, 1, TEST_CONTAINER_LIST, test);
+       res = test_traversal_nonsorted(res, 2, TEST_CONTAINER_HASH, test);
+
+       res = test_traversal_sorted(res, 3, TEST_CONTAINER_LIST, test);
+       res = test_traversal_sorted(res, 4, TEST_CONTAINER_HASH, test);
+
+       return res;
+}
+
 static int unload_module(void)
 {
        AST_TEST_UNREGISTER(astobj2_test_1);
        AST_TEST_UNREGISTER(astobj2_test_2);
        AST_TEST_UNREGISTER(astobj2_test_3);
+       AST_TEST_UNREGISTER(astobj2_test_4);
        return 0;
 }
 
@@ -711,6 +1977,7 @@ static int load_module(void)
        AST_TEST_REGISTER(astobj2_test_1);
        AST_TEST_REGISTER(astobj2_test_2);
        AST_TEST_REGISTER(astobj2_test_3);
+       AST_TEST_REGISTER(astobj2_test_4);
        return AST_MODULE_LOAD_SUCCESS;
 }