Enhance astobj2 to support other types of containers.

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

1 files changed, 2064 insertions, 380 deletions

diff --git a/main/astobj2.c b/main/astobj2.c
index 176ea5aea..9b5f8420e 100644
--- a/main/astobj2.c
+++ b/main/astobj2.c
@@ -14,8 +14,11 @@
  * 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;
-	}
+	struct ao2_container_node *node;
 
-	if (INTERNAL_OBJ(c) == NULL) {
-		return NULL;
-	}
-
-	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;
+	/* Create a buffer for the traversal state. */
+	traversal_state = alloca(AO2_TRAVERSAL_STATE_SIZE);
 
-		AST_LIST_TRAVERSE_SAFE_BEGIN(&c->buckets[i], cur, entry) {
-			int match = (CMP_MATCH | CMP_STOP);
-
-			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) */
 
-			/* inc refcount of returned object */
+			/* Transfer the object ref from the container to the returned object. */
+			node->obj = NULL;
+
+			/* 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);
 
-	for (i = 0; i < c->n_buckets; i++) {
-		struct bucket_entry *current;
+	/* Unlink any stored objects in the container. */
+	c->destroying = 1;
+	__ao2_callback(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL);
 
-		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,16 +1628,15 @@ static void container_destruct(void *_c)
 static void container_destruct_debug(void *_c)
 {
 	struct ao2_container *c = _c;
-	int i;
-
-	__ao2_callback_debug(c, OBJ_UNLINK, cd_cb_debug, NULL, "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__);
 
-	for (i = 0; i < c->n_buckets; i++) {
-		struct bucket_entry *current;
+	/* 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__);
 
-		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
@@ -1458,18 +1693,15 @@ int ao2_container_dup(struct ao2_container *dest, struct ao2_container *src, enu
 struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum search_flags flags)
 {
 	struct ao2_container *clone;
-	struct astobj2 *orig_obj;
-	unsigned int options;
 	int failed;
 
-	orig_obj = INTERNAL_OBJ(orig);
-	if (!orig_obj) {
+	/* 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;
 	}
-	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);
+	clone = orig->v_table->alloc_empty_clone(orig);
 	if (!clone) {
 		return NULL;
 	}
@@ -1492,19 +1724,15 @@ struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum sea
 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;
-	struct astobj2 *orig_obj;
-	unsigned int options;
 	int failed;
 
-	orig_obj = INTERNAL_OBJ(orig);
-	if (!orig_obj) {
+	/* 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;
 	}
-	options = orig_obj->priv_data.options;
-
-	/* 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);
+	clone = orig->v_table->alloc_empty_clone_debug(orig, tag, file, line, func, ref_debug);
 	if (!clone) {
 		return NULL;
 	}
@@ -1528,18 +1756,1260 @@ struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, en
 	return clone;
 }
 
-void ao2_cleanup(void *obj)
+#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 (obj) {
-		ao2_ref(obj, -1);
+	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) */
 
-void ao2_iterator_cleanup(struct ao2_iterator *iter)
+int ao2_container_check(struct ao2_container *self, enum search_flags flags)
 {
-	if (iter) {
-		ao2_iterator_destroy(iter);
+	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;
+
+	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) */
+
+/*!
+ * \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;
+
+	/* 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;
+		}
+	}
+}
+
+#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.
+ *
+ * \note The container is already locked for reading.
+ *
+ * \return Nothing
+ */
+static void hash_ao2_stats(struct ao2_container_hash *self, int fd, void (*prnt)(int fd, const char *fmt, ...) __attribute__((format(printf, 2, 3))))
+{
+#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");
+		}
+	}
+
+#undef FORMAT
+#undef FORMAT2
+}
+#endif	/* defined(AST_DEVMODE) */
+
+#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)
+{
+	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;
+		}
+
+		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;
 	}
+
+	/* 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;
+	}
+
+	/* 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 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) */
+};
+
+/*!
+ * \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)
+{
+	return 0;
+}
+
+/*!
+ * \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;
+	}
+
+	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;
+
+#ifdef AO2_DEBUG
+	ast_atomic_fetchadd_int(&ao2.total_containers, 1);
+#endif
+
+	return (struct ao2_container *) self;
+}
+
+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)
+{
+	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(container_size, container_destruct, ao2_options);
+	return hash_ao2_container_init(self, container_options, num_buckets,
+		hash_fn, sort_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)
+{
+	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);
+}
+
+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)
+{
+	return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL, sort_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)
+{
+	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;
 }