From b9962ee26a47355aed9e4229dfe241b760b95c96 Mon Sep 17 00:00:00 2001 From: Richard Mudgett Date: Wed, 3 Apr 2013 16:01:51 +0000 Subject: astobj2: Fix rbtree duplicate handling. OBJ_PARTIAL_KEY searching a rbtree did not find all possible matches if the container did not accept duplicates. Added matching node bias to indicate which matching node is being searched for: first, last, any. git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@384616 65c4cc65-6c06-0410-ace0-fbb531ad65f3 --- main/astobj2.c | 255 ++++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 160 insertions(+), 95 deletions(-) (limited to 'main/astobj2.c') diff --git a/main/astobj2.c b/main/astobj2.c index e1fb81b76..72a171de9 100644 --- a/main/astobj2.c +++ b/main/astobj2.c @@ -3468,6 +3468,15 @@ static struct rbtree_node *rb_node_prev_full(struct rbtree_node *node) } } +enum equal_node_bias { + /*! Bias search toward first matching node in the container. */ + BIAS_FIRST, + /*! Bias search toward any matching node. */ + BIAS_EQUAL, + /*! Bias search toward last matching node in the container. */ + BIAS_LAST, +}; + enum empty_node_direction { GO_LEFT, GO_RIGHT, @@ -3485,10 +3494,11 @@ enum empty_node_direction { * OBJ_POINTER - if set, 'obj_right', is an object. * OBJ_KEY - if set, 'obj_right', is a search key item that is not an object. * OBJ_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object. + * \param bias How to bias search direction for duplicates * * \return enum empty_node_direction to proceed. */ -static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *empty, ao2_sort_fn *sort_fn, void *obj_right, enum search_flags flags) +static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *empty, ao2_sort_fn *sort_fn, void *obj_right, enum search_flags flags, enum equal_node_bias bias) { int cmp; struct rbtree_node *cur; @@ -3505,6 +3515,9 @@ static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *emp if (cmp < 0) { return GO_RIGHT; } + if (cmp == 0 && bias == BIAS_LAST) { + return GO_RIGHT; + } return GO_LEFT; } @@ -3516,10 +3529,13 @@ static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *emp cur = rb_node_most_left(empty->right); if (cur->common.obj) { cmp = sort_fn(cur->common.obj, obj_right, flags); - if (cmp <= 0) { - return GO_RIGHT; + if (cmp > 0) { + return GO_LEFT; } - return GO_LEFT; + if (cmp == 0 && bias == BIAS_FIRST) { + return GO_LEFT; + } + return GO_RIGHT; } /* @@ -3553,6 +3569,9 @@ static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *emp if (cmp < 0) { return GO_RIGHT; } + if (cmp == 0 && bias == BIAS_LAST) { + return GO_RIGHT; + } return GO_LEFT; } } @@ -4185,6 +4204,7 @@ static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree struct rbtree_node *next; ao2_sort_fn *sort_fn; uint32_t options; + enum equal_node_bias bias; if (!self->root) { /* The tree is empty. */ @@ -4194,6 +4214,21 @@ static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree 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 @@ -4206,7 +4241,7 @@ static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree 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_POINTER) + if (rb_find_empty_direction(cur, sort_fn, node->common.obj, OBJ_POINTER, bias) == GO_LEFT) { if (cur->left) { cur = cur->left; @@ -4254,6 +4289,34 @@ static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree 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; } @@ -4262,50 +4325,8 @@ static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) { default: case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW: - if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) { - /* Find first duplicate node. */ - for (;;) { - next = rb_node_prev_full(cur); - if (!next) { - break; - } - cmp = sort_fn(next->common.obj, node->common.obj, OBJ_POINTER); - 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 { - /* Find last duplicate node. */ - for (;;) { - next = rb_node_next_full(cur); - if (!next) { - break; - } - cmp = sort_fn(next->common.obj, node->common.obj, OBJ_POINTER); - 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; + 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; @@ -4545,16 +4566,17 @@ static struct rbtree_node *rb_ao2_find_next(struct ao2_container_rbtree *self, s * OBJ_KEY - if set, 'obj_right', is a search key item that is not an object. * OBJ_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object. * OBJ_CONTINUE - if set, return node right before or right after search key if not a match. + * \param bias How to bias search direction for duplicates * * \retval node on success. * \retval NULL if not found. */ -static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags) +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; + struct rbtree_node *next = NULL; ao2_sort_fn *sort_fn; sort_flags = flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY); @@ -4568,13 +4590,34 @@ static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, vo 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) + 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. */ if (flags & OBJ_CONTINUE) { next = rb_node_next_full(node); @@ -4591,9 +4634,46 @@ static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, vo } else if (cmp < 0) { next = node->right; } else { - return node; + 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. */ if (flags & OBJ_CONTINUE) { return node; @@ -4620,9 +4700,8 @@ static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, vo */ 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 *next; struct rbtree_node *node; - int cmp; + enum equal_node_bias bias; if (self->common.destroying) { /* Force traversal to be post order for tree destruction. */ @@ -4663,33 +4742,26 @@ static struct rbtree_node *rb_ao2_find_first(struct ao2_container_rbtree *self, } /* Search for initial node. */ - node = rb_find_initial(self, arg, flags); - if (!node) { - return NULL; - } 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_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY)) != OBJ_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. */ - for (;;) { - next = rb_node_prev_full(node); - if (!next) { - break; - } - cmp = state->sort_fn(next->common.obj, arg, - flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY)); - if (cmp) { - break; - } - node = next; - } - break; - case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT: - case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE: - /* There are no duplicates allowed. */ + 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) { @@ -4705,33 +4777,26 @@ static struct rbtree_node *rb_ao2_find_first(struct ao2_container_rbtree *self, } /* Search for initial node. */ - node = rb_find_initial(self, arg, flags); - if (!node) { - return NULL; - } 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_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY)) != OBJ_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. */ - for (;;) { - next = rb_node_next_full(node); - if (!next) { - break; - } - cmp = state->sort_fn(next->common.obj, arg, - flags & (OBJ_POINTER | OBJ_KEY | OBJ_PARTIAL_KEY)); - if (cmp) { - break; - } - node = next; - } - break; - case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT: - case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE: - /* There are no duplicates allowed. */ + 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. */ -- cgit v1.2.3