test_astobj2.c

{
	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;
	case TEST_CONTAINER_RBTREE:
		container = ao2_t_container_alloc_rbtree(AO2_ALLOC_OPT_LOCK_MUTEX, options,
			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_check(container, 0)) {
			ast_test_status_update(test, "%s: Container integrity check failed linking vector[%d]:%d\n",
				prefix, idx, vector[idx]);
			return -1;
		}

		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;
		}
	}

	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");
		}

		if (ao2_container_check(container, 0)) {
			ast_test_status_update(test, "%s: Container integrity check failed linking num:%d dup:%d\n",
				prefix, number, count);
			if (obj_dup) {
				ao2_t_ref(obj_dup, -1, "test");
			}
			return -1;
		}
	}

	/* 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 linking obj_dup\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) {
		ast_test_status_update(test, "Container c1 creation failed.\n");
		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) {
		ast_test_status_update(test, "Container c2 creation failed.\n");
		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;
	case TEST_CONTAINER_RBTREE:
		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;
	case TEST_CONTAINER_RBTREE:
		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;
	case TEST_CONTAINER_RBTREE:
		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) {
		ast_test_status_update(test, "Container c1 creation failed.\n");
		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) {
		ast_test_status_update(test, "Container c2 creation failed.\n");
		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;
	}

#if defined(TEST_CONTAINER_DEBUG_DUMP)
	ao2_container_dump(c1, 0, "c1(DUPS_ALLOW)", (void *) test, (ao2_prnt_fn *) ast_test_debug, test_prnt_obj);
	ao2_container_stats(c1, 0, "c1(DUPS_ALLOW)", (void *) test, (ao2_prnt_fn *) ast_test_debug);
	ao2_container_dump(c2, 0, "c2(DUPS_ALLOW)", (void *) test, (ao2_prnt_fn *) ast_test_debug, test_prnt_obj);
	ao2_container_stats(c2, 0, "c2(DUPS_ALLOW)", (void *) test, (ao2_prnt_fn *) ast_test_debug);
#endif	/* defined(TEST_CONTAINER_DEBUG_DUMP) */

	/* Check container iteration directions */
	switch (type) {
	case TEST_CONTAINER_RBTREE:
	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_RBTREE:
	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_RBTREE:
	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;
	}

#if defined(TEST_CONTAINER_DEBUG_DUMP)
	ao2_container_dump(c1, 0, "c1(DUPS_ALLOW) w/ dups", (void *) test, (ao2_prnt_fn *) ast_test_debug, test_prnt_obj);
	ao2_container_stats(c1, 0, "c1(DUPS_ALLOW) w/ dups", (void *) test, (ao2_prnt_fn *) ast_test_debug);
	ao2_container_dump(c2, 0, "c2(DUPS_ALLOW) w/ dups", (void *) test, (ao2_prnt_fn *) ast_test_debug, test_prnt_obj);
	ao2_container_stats(c2, 0, "c2(DUPS_ALLOW) w/ dups", (void *) test, (ao2_prnt_fn *) ast_test_debug);
#endif	/* defined(TEST_CONTAINER_DEBUG_DUMP) */

	/* 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) {
		ast_test_status_update(test, "Container c1 creation failed.\n");
		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) {
		ast_test_status_update(test, "Container c2 creation failed.\n");
		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) {
		ast_test_status_update(test, "Container c1 creation failed.\n");
		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) {
		ast_test_status_update(test, "Container c2 creation failed.\n");
		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) {
		ast_test_status_update(test, "Container c1 creation failed.\n");
		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) {
		ast_test_status_update(test, "Container c2 creation failed.\n");
		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);
	res = test_traversal_sorted(res, 5, TEST_CONTAINER_RBTREE, test);

	return res;
}

static enum ast_test_result_state test_performance(struct ast_test *test,
	enum test_container_type type, unsigned int copt)
{
/*!
 * \brief The number of objects inserted and searched for in the container under test.
 */
#define OBJS 73
	int res = AST_TEST_PASS;
	struct ao2_container *c1 = NULL;
	struct test_obj *tobj[OBJS];
	struct test_obj *tobj2;
	int i;

	switch (type) {
	case TEST_CONTAINER_HASH:
		c1 = ao2_container_alloc_hash(AO2_ALLOC_OPT_LOCK_MUTEX, copt, 17,
			test_hash_cb, test_sort_cb, test_cmp_cb);
		break;
	case TEST_CONTAINER_LIST:
		c1 = ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, copt,
			test_sort_cb, test_cmp_cb);
		break;
	case TEST_CONTAINER_RBTREE:
		c1 = ao2_container_alloc_rbtree(AO2_ALLOC_OPT_LOCK_MUTEX, copt,
			test_sort_cb, test_cmp_cb);
		break;
	}

	for (i = 0; i < OBJS; i++) {
		tobj[i] = NULL;
	}

	if (!c1) {
		ast_test_status_update(test, "Container c1 creation failed.\n");
		res = AST_TEST_FAIL;
		goto test_cleanup;
	}

	for (i = 0; i < OBJS; i++) {
		tobj[i] = ao2_alloc(sizeof(struct test_obj), test_obj_destructor);
		if (!tobj[i]) {
			ast_test_status_update(test, "test object creation failed.\n");
			res = AST_TEST_FAIL;
			goto test_cleanup;
		}
		tobj[i]->i = i;
		ao2_link(c1, tobj[i]);
	}

	for (i = 0; i < OBJS; i++) {
		if ((!(tobj2 = ao2_find(c1, &i, OBJ_KEY)))) {
			ast_test_status_update(test, "Should have found object %d in container.\n", i);
			res = AST_TEST_FAIL;
			goto test_cleanup;
		}
		ao2_ref(tobj2, -1);
		tobj2 = NULL;
	}

test_cleanup:
	for (i = 0; i < OBJS ; i++) {
		ao2_cleanup(tobj[i]);
	}
	ao2_cleanup(c1);
	return res;
}

static enum ast_test_result_state testloop(struct ast_test *test,
	enum test_container_type type, int copt, int iterations)
{
	int res = AST_TEST_PASS;
	int i;
	struct timeval start;

	start = ast_tvnow();
	for (i = 1 ; i <= iterations && res == AST_TEST_PASS ; i++) {