diff options
| -rw-r--r-- | rdxtree.c | 20 | ||||
| -rw-r--r-- | rdxtree.h | 9 | ||||
| -rw-r--r-- | rdxtree_i.h | 6 | ||||
| -rw-r--r-- | test/test_rdxtree.c | 28 |
4 files changed, 53 insertions, 10 deletions
@@ -700,20 +700,24 @@ rdxtree_walk_next(struct rdxtree *tree, struct rdxtree_iter *iter) return NULL; if (!rdxtree_entry_is_node(entry)) { - if (iter->key != 0) + if (iter->key != (rdxtree_key_t)-1) return NULL; else { - iter->key = 1; + iter->key = 0; return rdxtree_entry_addr(entry); } } + key = iter->key + 1; + + if ((key == 0) && (iter->node != NULL)) + return NULL; + root = rdxtree_entry_addr(entry); restart: node = root; height = root->height + 1; - key = iter->key; if (key > rdxtree_max_key(height)) return NULL; @@ -728,7 +732,11 @@ restart: if (node == NULL) { shift += RDXTREE_RADIX; - iter->key = ((key >> shift) + 1) << shift; + key = ((key >> shift) + 1) << shift; + + if (key == 0) + return NULL; + goto restart; } @@ -740,7 +748,7 @@ restart: } while (height > 0); iter->node = prev; - iter->key = key + 1; + iter->key = key; return node; } @@ -753,7 +761,7 @@ rdxtree_walk(struct rdxtree *tree, struct rdxtree_iter *iter) if (iter->node == NULL) return rdxtree_walk_next(tree, iter); - index = iter->key & RDXTREE_RADIX_MASK; + index = (iter->key + 1) & RDXTREE_RADIX_MASK; if (index != 0) { orig_index = index; @@ -184,6 +184,15 @@ for (rdxtree_iter_init(iter), ptr = rdxtree_walk(tree, iter); \ ptr = rdxtree_walk(tree, iter)) /* + * Return the key of the current pointer from an iterator. + */ +static inline rdxtree_key_t +rdxtree_iter_key(const struct rdxtree_iter *iter) +{ + return iter->key; +} + +/* * Remove all pointers from a tree. * * The common way to destroy a tree and its pointers is to loop over all diff --git a/rdxtree_i.h b/rdxtree_i.h index 1a72bca..1bd1f64 100644 --- a/rdxtree_i.h +++ b/rdxtree_i.h @@ -34,8 +34,8 @@ struct rdxtree { * Radix tree iterator. * * The node member refers to the node containing the current pointer, if any. - * The key member refers to the key from which to look up the next pointer, - * in ascending order. + * The key member refers to the current pointer, and is valid if and only if + * rdxtree_walk() has been called at least once on the iterator. */ struct rdxtree_iter { void *node; @@ -49,7 +49,7 @@ static inline void rdxtree_iter_init(struct rdxtree_iter *iter) { iter->node = NULL; - iter->key = 0; + iter->key = (rdxtree_key_t)-1; } int rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key, diff --git a/test/test_rdxtree.c b/test/test_rdxtree.c index a92b1b6..69dccee 100644 --- a/test/test_rdxtree.c +++ b/test/test_rdxtree.c @@ -144,8 +144,10 @@ destroy_tree(struct rdxtree *tree) struct rdxtree_iter iter; struct obj *obj; - rdxtree_for_each(tree, &iter, obj) + rdxtree_for_each(tree, &iter, obj) { + assert(obj->id == rdxtree_iter_key(&iter)); obj_destroy(obj); + } rdxtree_remove_all(tree); } @@ -1007,6 +1009,29 @@ test_37(void) } #endif /* RDXTREE_KEY_32 */ +static void +test_38(void) +{ + struct rdxtree tree; + struct obj *obj; + int error; + + TITLE("insert 1, 3 and max_key"); + + rdxtree_init(&tree); + obj = obj_create(1); + error = rdxtree_insert(&tree, obj->id, obj); + assert(!error); + obj = obj_create(3); + error = rdxtree_insert(&tree, obj->id, obj); + assert(!error); + obj = obj_create((rdxtree_key_t)-1); + error = rdxtree_insert(&tree, obj->id, obj); + assert(!error); + print_tree(&tree); + destroy_tree(&tree); +} + int main(int argc, char *argv[]) { @@ -1054,5 +1079,6 @@ main(int argc, char *argv[]) #ifndef RDXTREE_KEY_32 test_37(); #endif /* RDXTREE_KEY_32 */ + test_38(); return 0; } |