astobj2_rbtree.c

				g_parent->left->is_red = 0;
				g_parent->right->is_red = 0;
				g_parent->is_red = 1;

				node = g_parent;
			} else {
				/* The uncle node is black. */
				if (node->parent->left == node) {
					/*
					 * Case 2: The node is a left child.
					 *
					 * Which node is the grand parent does not change.
					 */
					AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[1]);
					node = node->parent;
					rb_rotate_right(self, node);
				}
				/* Case 3: The node is a right child. */
				AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[2]);
				node->parent->is_red = 0;
				g_parent->is_red = 1;
				rb_rotate_left(self, g_parent);
			}
		}
	}

	/*
	 * The root could be red here because:
	 * 1) We just inserted the root node in an empty tree.
	 *
	 * 2) Case 1 could leave the root red if the grand parent were
	 * the root.
	 */
	self->root->is_red = 0;
}

/*!
 * \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 rb_ao2_insert_node(struct ao2_container_rbtree *self, struct rbtree_node *node)
{
	int cmp;
	struct rbtree_node *cur;
	struct rbtree_node *next;
	ao2_sort_fn *sort_fn;
	uint32_t options;
	enum equal_node_bias bias;

	if (!self->root) {
		/* The tree is empty. */
		self->root = node;
		return AO2_CONTAINER_INSERT_NODE_INSERTED;
	}

	sort_fn = self->common.sort_fn;
	options = self->common.options;
	switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
	default:
	case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
		if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
			bias = BIAS_FIRST;
		} else {
			bias = BIAS_LAST;
		}
		break;
	case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
	case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
	case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
		bias = BIAS_EQUAL;
		break;
	}

	/*
	 * New nodes are always colored red when initially inserted into
	 * the tree.  (Except for the root which is always black.)
	 */
	node->is_red = 1;

	/* Find node where normal insert would put a new node. */
	cur = self->root;
	for (;;) {
		if (!cur->common.obj) {
			/* Which direction do we go to insert this node? */
			if (rb_find_empty_direction(cur, sort_fn, node->common.obj, OBJ_SEARCH_OBJECT, bias)
				== GO_LEFT) {
				if (cur->left) {
					cur = cur->left;
					continue;
				}

				/* Node becomes a left child */
				cur->left = node;
				node->parent = cur;
				rb_insert_fixup(self, node);
				return AO2_CONTAINER_INSERT_NODE_INSERTED;
			}
			if (cur->right) {
				cur = cur->right;
				continue;
			}

			/* Node becomes a right child */
			cur->right = node;
			node->parent = cur;
			rb_insert_fixup(self, node);
			return AO2_CONTAINER_INSERT_NODE_INSERTED;
		}
		cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
		if (cmp > 0) {
			if (cur->left) {
				cur = cur->left;
				continue;
			}

			/* Node becomes a left child */
			cur->left = node;
			node->parent = cur;
			rb_insert_fixup(self, node);
			return AO2_CONTAINER_INSERT_NODE_INSERTED;
		} else if (cmp < 0) {
			if (cur->right) {
				cur = cur->right;
				continue;
			}

			/* Node becomes a right child */
			cur->right = node;
			node->parent = cur;
			rb_insert_fixup(self, node);
			return AO2_CONTAINER_INSERT_NODE_INSERTED;
		}
		switch (bias) {
		case BIAS_FIRST:
			/* Duplicate nodes unconditionally accepted. */
			if (cur->left) {
				cur = cur->left;
				continue;
			}

			/* Node becomes a left child */
			cur->left = node;
			node->parent = cur;
			rb_insert_fixup(self, node);
			return AO2_CONTAINER_INSERT_NODE_INSERTED;
		case BIAS_EQUAL:
			break;
		case BIAS_LAST:
			/* Duplicate nodes unconditionally accepted. */
			if (cur->right) {
				cur = cur->right;
				continue;
			}

			/* Node becomes a right child */
			cur->right = node;
			node->parent = cur;
			rb_insert_fixup(self, node);
			return AO2_CONTAINER_INSERT_NODE_INSERTED;
		}

		break;
	}

	/* Node is a dupliate */
	switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
	default:
	case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
		ast_assert(0);/* Case already handled by BIAS_FIRST/BIAS_LAST. */
		return AO2_CONTAINER_INSERT_NODE_REJECTED;
	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;
		}
		next = cur;
		if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
			/* Search to end of duplicates for the same object. */
			for (;;) {
				next = rb_node_next_full(next);
				if (!next) {
					break;
				}
				if (next->common.obj == node->common.obj) {
					/* Reject inserting the same object */
					return AO2_CONTAINER_INSERT_NODE_REJECTED;
				}
				cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
				if (cmp) {
					break;
				}
			}

			/* Find first duplicate node. */
			for (;;) {
				next = rb_node_prev_full(cur);
				if (!next) {
					break;
				}
				if (next->common.obj == node->common.obj) {
					/* Reject inserting the same object */
					return AO2_CONTAINER_INSERT_NODE_REJECTED;
				}
				cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
				if (cmp) {
					break;
				}
				cur = next;
			}
			if (!cur->left) {
				/* Node becomes a left child */
				cur->left = node;
			} else {
				/* Node becomes a right child */
				cur = rb_node_most_right(cur->left);
				cur->right = node;
			}
		} else {
			/* Search to beginning of duplicates for the same object. */
			for (;;) {
				next = rb_node_prev_full(next);
				if (!next) {
					break;
				}
				if (next->common.obj == node->common.obj) {
					/* Reject inserting the same object */
					return AO2_CONTAINER_INSERT_NODE_REJECTED;
				}
				cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
				if (cmp) {
					break;
				}
			}

			/* Find last duplicate node. */
			for (;;) {
				next = rb_node_next_full(cur);
				if (!next) {
					break;
				}
				if (next->common.obj == node->common.obj) {
					/* Reject inserting the same object */
					return AO2_CONTAINER_INSERT_NODE_REJECTED;
				}
				cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
				if (cmp) {
					break;
				}
				cur = next;
			}
			if (!cur->right) {
				/* Node becomes a right child */
				cur->right = node;
			} else {
				/* Node becomes a left child */
				cur = rb_node_most_left(cur->right);
				cur->left = node;
			}
		}
		break;
	case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
		SWAP(cur->common.obj, node->common.obj);
		__ao2_ref(node, -1);
		return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
	}

	/* Complete inserting duplicate node. */
	node->parent = cur;
	rb_insert_fixup(self, node);
	return AO2_CONTAINER_INSERT_NODE_INSERTED;
}

/*!
 * \internal
 * \brief Find the next rbtree container node in a traversal.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 * \param state Traversal state to restart rbtree 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 rbtree_node *rb_ao2_find_next(struct ao2_container_rbtree *self, struct rbtree_traversal_state *state, struct rbtree_node *prev)
{
	struct rbtree_node *node;
	void *arg;
	enum search_flags flags;
	int cmp;

	arg = state->arg;
	flags = state->flags;

	node = prev;
	for (;;) {
		/* Find next node in traversal order. */
		switch (flags & OBJ_ORDER_MASK) {
		default:
		case OBJ_ORDER_ASCENDING:
			node = rb_node_next(node);
			break;
		case OBJ_ORDER_DESCENDING:
			node = rb_node_prev(node);
			break;
		case OBJ_ORDER_PRE:
			node = rb_node_pre(node);
			break;
		case OBJ_ORDER_POST:
			node = rb_node_post(node);
			break;
		}
		if (!node) {
			/* No more nodes left to traverse. */
			break;
		}
		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_SEARCH_MASK);
			if (cmp) {
				/* No more nodes in this container 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;
	}

	/* No more nodes in the container left to traverse. */
	__ao2_ref(prev, -1);
	return NULL;
}

/*!
 * \internal
 * \brief Find an initial matching node.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 * \param obj_right pointer to the (user-defined part) of an object.
 * \param flags flags from ao2_callback()
 *   OBJ_SEARCH_OBJECT - if set, 'obj_right', is an object.
 *   OBJ_SEARCH_KEY - if set, 'obj_right', is a search key item that is not an object.
 *   OBJ_SEARCH_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object.
 * \param bias How to bias search direction for duplicates
 *
 * \retval node on success.
 * \retval NULL if not found.
 */
static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
{
	int cmp;
	enum search_flags sort_flags;
	struct rbtree_node *node;
	struct rbtree_node *next = NULL;
	ao2_sort_fn *sort_fn;

	sort_flags = flags & OBJ_SEARCH_MASK;
	sort_fn = self->common.sort_fn;

	/* Find node where normal search would find it. */
	node = self->root;
	if (!node) {
		return NULL;
	}
	for (;;) {
		if (!node->common.obj) {
			/* Which direction do we go to find the node? */
			if (rb_find_empty_direction(node, sort_fn, obj_right, sort_flags, bias)
				== GO_LEFT) {
				next = node->left;
			} else {
				next = node->right;
			}
			if (!next) {
				switch (bias) {
				case BIAS_FIRST:
					/* Check successor node for match. */
					next = rb_node_next_full(node);
					break;
				case BIAS_EQUAL:
					break;
				case BIAS_LAST:
					/* Check previous node for match. */
					next = rb_node_prev_full(node);
					break;
				}
				if (next) {
					cmp = sort_fn(next->common.obj, obj_right, sort_flags);
					if (cmp == 0) {
						/* Found the first/last matching node. */
						return next;
					}
					next = NULL;
				}

				/* No match found. */
				return next;
			}
		} else {
			cmp = sort_fn(node->common.obj, obj_right, sort_flags);
			if (cmp > 0) {
				next = node->left;
			} else if (cmp < 0) {
				next = node->right;
			} else {
				switch (bias) {
				case BIAS_FIRST:
					next = node->left;
					break;
				case BIAS_EQUAL:
					return node;
				case BIAS_LAST:
					next = node->right;
					break;
				}
				if (!next) {
					/* Found the first/last matching node. */
					return node;
				}
			}
			if (!next) {
				switch (bias) {
				case BIAS_FIRST:
					if (cmp < 0) {
						/* Check successor node for match. */
						next = rb_node_next_full(node);
					}
					break;
				case BIAS_EQUAL:
					break;
				case BIAS_LAST:
					if (cmp > 0) {
						/* Check previous node for match. */
						next = rb_node_prev_full(node);
					}
					break;
				}
				if (next) {
					cmp = sort_fn(next->common.obj, obj_right, sort_flags);
					if (cmp == 0) {
						/* Found the first/last matching node. */
						return next;
					}
				}

				/* No match found. */
				return NULL;
			}
		}
		node = next;
	}
}

/*!
 * \internal
 * \brief Find the first rbtree 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 rbtree container traversal.
 *
 * \retval node-ptr of found node (Reffed).
 * \retval NULL when no node found.
 */
static struct rbtree_node *rb_ao2_find_first(struct ao2_container_rbtree *self, enum search_flags flags, void *arg, struct rbtree_traversal_state *state)
{
	struct rbtree_node *node;
	enum equal_node_bias bias;

	if (self->common.destroying) {
		/* Force traversal to be post order for tree destruction. */
		flags = OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE | OBJ_ORDER_POST;
	}

	memset(state, 0, sizeof(*state));
	state->arg = arg;
	state->flags = flags;

	switch (flags & OBJ_SEARCH_MASK) {
	case OBJ_SEARCH_OBJECT:
	case OBJ_SEARCH_KEY:
	case OBJ_SEARCH_PARTIAL_KEY:
		/* We are asked to do a directed search. */
		state->sort_fn = self->common.sort_fn;
		break;
	default:
		/* Don't know, let's visit all nodes */
		state->sort_fn = NULL;
		break;
	}

	if (!self->root) {
		/* Tree is empty. */
		return NULL;
	}

	/* Find first traversal node. */
	switch (flags & OBJ_ORDER_MASK) {
	default:
	case OBJ_ORDER_ASCENDING:
		if (!state->sort_fn) {
			/* Find left most child. */
			node = rb_node_most_left(self->root);
			if (!node->common.obj) {
				node = rb_node_next_full(node);
				if (!node) {
					return NULL;
				}
			}
			break;
		}

		/* Search for initial node. */
		switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
		case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
		case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
			if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
				/* There are no duplicates allowed. */
				bias = BIAS_EQUAL;
				break;
			}
			/* Fall through */
		default:
		case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
		case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
			/* Find first duplicate node. */
			bias = BIAS_FIRST;
			break;
		}
		node = rb_find_initial(self, arg, flags, bias);
		if (!node) {
			return NULL;
		}
		break;
	case OBJ_ORDER_DESCENDING:
		if (!state->sort_fn) {
			/* Find right most child. */
			node = rb_node_most_right(self->root);
			if (!node->common.obj) {
				node = rb_node_prev_full(node);
				if (!node) {
					return NULL;
				}
			}
			break;
		}

		/* Search for initial node. */
		switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
		case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
		case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
			if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
				/* There are no duplicates allowed. */
				bias = BIAS_EQUAL;
				break;
			}
			/* Fall through */
		default:
		case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
		case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
			/* Find last duplicate node. */
			bias = BIAS_LAST;
			break;
		}
		node = rb_find_initial(self, arg, flags, bias);
		if (!node) {
			return NULL;
		}
		break;
	case OBJ_ORDER_PRE:
		/* This is a tree structure traversal so we must visit all nodes. */
		state->sort_fn = NULL;

		node = self->root;

		/* Find a non-empty node. */
		while (!node->common.obj) {
			node = rb_node_pre(node);
			if (!node) {
				return NULL;
			}
		}
		break;
	case OBJ_ORDER_POST:
		/* This is a tree structure traversal so we must visit all nodes. */
		state->sort_fn = NULL;

		/* Find the left most childless node. */
		node = self->root;
		for (;;) {
			node = rb_node_most_left(node);
			if (!node->right) {
				/* This node has no children. */
				break;
			}
			node = node->right;
		}

		/* Find a non-empty node. */
		while (!node->common.obj) {
			node = rb_node_post(node);
			if (!node) {
				return NULL;
			}
		}
		break;
	}

	/* We have the first traversal node */
	__ao2_ref(node, +1);
	return node;
}

/*!
 * \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 rbtree_node *rb_ao2_iterator_next(struct ao2_container_rbtree *self, struct rbtree_node *node, enum ao2_iterator_flags flags)
{
	if (flags & AO2_ITERATOR_DESCENDING) {
		if (!node) {
			/* Find right most node. */
			if (!self->root) {
				return NULL;
			}
			node = rb_node_most_right(self->root);
			if (node->common.obj) {
				/* Found a non-empty node. */
				return node;
			}
		}
		/* Find next non-empty node. */
		node = rb_node_prev_full(node);
	} else {
		if (!node) {
			/* Find left most node. */
			if (!self->root) {
				return NULL;
			}
			node = rb_node_most_left(self->root);
			if (node->common.obj) {
				/* Found a non-empty node. */
				return node;
			}
		}
		/* Find next non-empty node. */
		node = rb_node_next_full(node);
	}

	return node;
}

/*!
 * \internal
 *
 * \brief Destroy this container.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 *
 * \return Nothing
 */
static void rb_ao2_destroy(struct ao2_container_rbtree *self)
{
	/* Check that the container no longer has any nodes */
	if (self->root) {
		ast_log(LOG_ERROR, "Node ref leak.  Red-Black tree container still has nodes!\n");
		ast_assert(0);
	}
}

#if defined(AO2_DEBUG)
/*!
 * \internal
 * \brief Display contents of the specified container.
 * \since 12.0.0
 *
 * \param self Container to dump.
 * \param where User data needed by prnt to determine where to put output.
 * \param prnt Print output callback function to use.
 * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
 *
 * \return Nothing
 */
static void rb_ao2_dump(struct ao2_container_rbtree *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
{
#define FORMAT  "%16s, %16s, %16s, %16s, %5s, %16s, %s\n"
#define FORMAT2 "%16p, %16p, %16p, %16p, %5s, %16p, "

	struct rbtree_node *node;

	prnt(where, FORMAT, "Node", "Parent", "Left", "Right", "Color", "Obj", "Key");
	for (node = self->root; node; node = rb_node_pre(node)) {
		prnt(where, FORMAT2,
			node,
			node->parent,
			node->left,
			node->right,
			node->is_red ? "Red" : "Black",
			node->common.obj);
		if (node->common.obj && prnt_obj) {
			prnt_obj(node->common.obj, where, prnt);
		}
		prnt(where, "\n");
	}

#undef FORMAT
#undef FORMAT2
}
#endif	/* defined(AO2_DEBUG) */

#if defined(AO2_DEBUG)
/*!
 * \internal
 * \brief Display statistics of the specified container.
 * \since 12.0.0
 *
 * \param self Container to display statistics.
 * \param where User data needed by prnt to determine where to put output.
 * \param prnt Print output callback function to use.
 *
 * \note The container is already locked for reading.
 *
 * \return Nothing
 */
static void rb_ao2_stats(struct ao2_container_rbtree *self, void *where, ao2_prnt_fn *prnt)
{
	int idx;

	for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_insert_left); ++idx) {
		prnt(where, "Number of left insert fixups case %d: %d\n", idx + 1,
			self->stats.fixup_insert_left[idx]);
	}
	for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_insert_right); ++idx) {
		prnt(where, "Number of right insert fixups case %d: %d\n", idx + 1,
			self->stats.fixup_insert_right[idx]);
	}

	for (idx = 0; idx < ARRAY_LEN(self->stats.delete_children); ++idx) {
		prnt(where, "Number of nodes deleted with %d children: %d\n", idx,
			self->stats.delete_children[idx]);
	}
	for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_delete_left); ++idx) {
		prnt(where, "Number of left delete fixups case %d: %d\n", idx + 1,
			self->stats.fixup_delete_left[idx]);
	}
	for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_delete_right); ++idx) {
		prnt(where, "Number of right delete fixups case %d: %d\n", idx + 1,
			self->stats.fixup_delete_right[idx]);
	}
}
#endif	/* defined(AO2_DEBUG) */

#if defined(AO2_DEBUG)
/*!
 * \internal
 * \brief Check the black height of the given node.
 * \since 12.0.0
 *
 * \param node Node to check black height.
 *
 * \retval black-height of node on success.
 * \retval -1 on error.  Node black height did not balance.
 */
static int rb_check_black_height(struct rbtree_node *node)
{
	int height_left;
	int height_right;

	if (!node) {
		/* A NULL child is a black node. */
		return 0;
	}

	height_left = rb_check_black_height(node->left);
	if (height_left < 0) {
		return -1;
	}
	height_right = rb_check_black_height(node->right);
	if (height_right < 0) {
		return -1;
	}
	if (height_left != height_right) {
		ast_log(LOG_ERROR,
			"Tree node black height of children does not match! L:%d != R:%d\n",
			height_left, height_right);
		return -1;
	}
	if (!node->is_red) {
		/* The node itself is black. */
		++height_left;
	}
	return height_left;
}

#endif	/* defined(AO2_DEBUG) */

#if defined(AO2_DEBUG)
/*!
 * \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 rb_ao2_integrity(struct ao2_container_rbtree *self)
{
	int res;
	int count_node;
	int count_obj;
	void *obj_last;
	struct rbtree_node *node;

	res = 0;

	count_node = 0;
	count_obj = 0;

	/*
	 * See the properties listed at struct rbtree_node definition.
	 *
	 * The rbtree properties 1 and 3 are not testable.
	 *
	 * Property 1 is not testable because we are not rebalancing at
	 * this time so all nodes are either red or black.
	 *
	 * Property 3 is not testable because it is the definition of a
	 * NULL child.
	 */
	if (self->root) {
		/* Check tree links. */
		if (self->root->parent) {
			if (self->root->parent == self->root) {
				ast_log(LOG_ERROR, "Tree root parent pointer points to itself!\n");
			} else {
				ast_log(LOG_ERROR, "Tree root is not a root node!\n");
			}
			return -1;
		}
		if (self->root->is_red) {
			/* Violation rbtree property 2. */
			ast_log(LOG_ERROR, "Tree root is red!\n");
			res = -1;
		}
		node = self->root;
		do {
			if (node->left) {
				if (node->left == node) {
					ast_log(LOG_ERROR, "Tree node's left pointer points to itself!\n");
					return -1;
				}
				if (node->left->parent != node) {
					ast_log(LOG_ERROR, "Tree node's left child does not link back!\n");
					return -1;
				}
			}
			if (node->right) {
				if (node->right == node) {
					ast_log(LOG_ERROR, "Tree node's right pointer points to itself!\n");
					return -1;
				}
				if (node->right->parent != node) {
					ast_log(LOG_ERROR, "Tree node's right child does not link back!\n");
					return -1;
				}
			}

			/* Check red/black node flags. */
			if (node->is_red) {
				/* A red node must have two black children or no children. */
				if (node->left && node->right) {
					/* Node has two children. */
					if (node->left->is_red) {
						/* Violation rbtree property 4. */
						ast_log(LOG_ERROR, "Tree node is red and its left child is red!\n");
						res = -1;
					}
					if (node->right->is_red) {
						/* Violation rbtree property 4. */
						ast_log(LOG_ERROR, "Tree node is red and its right child is red!\n");
						res = -1;
					}
				} else if (node->left || node->right) {
					/*
					 * Violation rbtree property 4 if the child is red.
					 * Violation rbtree property 5 if the child is black.
					 */
					ast_log(LOG_ERROR, "Tree node is red and it only has one child!\n");
					res = -1;
				}
			} else {
				/*
				 * A black node must have two children, or one red child, or no
				 * children.  If the black node has two children and only one of
				 * them is red, that red child must have two children.
				 */
				if (node->left && node->right) {
					/* Node has two children. */
					if (node->left->is_red != node->right->is_red) {
						/* The children are not the same color. */
						struct rbtree_node *red;

						if (node->left->is_red) {
							red = node->left;
						} else {
							red = node->right;
						}
						if (!red->left || !red->right) {
							/* Violation rbtree property 5. */
							ast_log(LOG_ERROR,
								"Tree node is black and the red child does not have two children!\n");
							res = -1;
						}
					}
				} else if ((node->left && !node->left->is_red)
					|| (node->right && !node->right->is_red)) {
					/* Violation rbtree property 5. */
					ast_log(LOG_ERROR, "Tree node is black and its only child is black!\n");
					res = -1;
				}
			}

			/* Count nodes and objects. */
			++count_node;
			if (node->common.obj) {
				++count_obj;
			}

			node = rb_node_pre(node);
		} while (node);

		/* Check node key sort order. */
		obj_last = NULL;
		for (node = rb_node_most_left(self->root); node; node = rb_node_next(node)) {
			if (!node->common.obj) {
				/* Node is empty. */
				continue;
			}

			if (obj_last) {
				if (self->common.sort_fn(obj_last, node->common.obj, OBJ_SEARCH_OBJECT) > 0) {
					ast_log(LOG_ERROR, "Tree nodes are out of sorted order!\n");
					return -1;
				}
			}
			obj_last = node->common.obj;
		}

		/* Completely check property 5 */
		if (!res && rb_check_black_height(self->root) < 0) {
			/* Violation rbtree property 5. */
			res = -1;
		}