From 155f04de2ed32d784bae64899f2f9ad28aee564d Mon Sep 17 00:00:00 2001 From: 0scar Date: Fri, 31 Dec 2021 14:09:18 +0100 Subject: Improve btree iteration --- src/btree.h | 4 +- src/btree_naive.c | 116 ++++++++++++++++++++++++++++++++++++------------------ 2 files changed, 80 insertions(+), 40 deletions(-) diff --git a/src/btree.h b/src/btree.h index fc558a7..78a63ea 100644 --- a/src/btree.h +++ b/src/btree.h @@ -13,6 +13,7 @@ #define BTREE_CMP_GT ( 1 ) struct btree; +struct btree_iter_t; /* elem_size: the size of the elements, typically `sizeof(struct )` * t: degree of the btree, if you're in doubt, use `BTREE_SIZE_DEFAULT` @@ -48,6 +49,7 @@ void* btree_last(struct btree *btree); size_t btree_size(struct btree *btree); -void* btree_iter(struct btree *tree); +struct btree_iter_t * btree_iter_t_new(struct btree *tree); +void* btree_iter(struct btree *tree, struct btree_iter_t *iter); #endif diff --git a/src/btree_naive.c b/src/btree_naive.c index 43daf8c..8f4a469 100644 --- a/src/btree_naive.c +++ b/src/btree_naive.c @@ -32,6 +32,16 @@ struct btree { int (*cmp)(const void *a, const void *b); }; +struct btree_iter_t { + size_t head; + struct stack{ + int pos; + struct node* node; + } stack[512]; + /* This heavily relies on the assumption that a tree never grows deeper than + * 512 nodes */ +}; + /**********************/ /* Node functionality */ /**********************/ @@ -712,78 +722,106 @@ size_t u32_pow(size_t base, size_t exponent) { return res; } + size_t btree_size(struct btree *btree) { return u32_pow(2 * btree->degree, btree_height(btree)) - 1; } -void* btree_iter(struct btree *tree) { - static size_t head; - static struct btree *btree; - static struct stack{ - int pos; - struct node* node; - } stack[512]; - if (tree != NULL) { - head = 0; - memset(stack, 0, 512 * sizeof(struct node*)); +struct btree_iter_t * btree_iter_t_new(struct btree *tree) { + struct btree_iter_t *iter = NULL; + iter = (struct btree_iter_t*)malloc(sizeof(struct btree_iter_t*)); - btree = tree; + if (tree != NULL) { + iter->head = 0; + memset(iter->stack, 0, 512 * sizeof(struct node*)); - stack[head].pos = 0; - stack[head].node = btree->root; + iter->stack[iter->head].pos = 0; + iter->stack[iter->head].node = tree->root; + } else { + perror("Cannot instantiate iterator from null-pointer tree"); } + return iter; +} + + +void* btree_iter(struct btree *tree, struct btree_iter_t *iter) { + register int pos; + register ssize_t head; + register ssize_t n; + + head = iter->head; + pos = iter->stack[head].pos; + n = iter->stack[head].node->n; /* Check if we have reached the end of a node. * Take note of the difference of inequality in the if statement and * following while */ /* Leafs are a special case */ - if (node_leaf(stack[head].node) && stack[head].pos >= 2 * stack[head].node->n) { /* +1 ?? */ + if (node_leaf(iter->stack[iter->head].node) && pos >= 2 * n) { /* +1 ?? */ if (head == 0) return NULL; - /* Pop, if so */ - stack[head].pos = 0; - stack[head].node = NULL; - head--; - stack[head].pos++; + { /* Pop, if so */ + iter->stack[head].pos = 0; + iter->stack[head].node = NULL; + iter->head--; head--; + iter->stack[head].pos++; + + pos = iter->stack[head].pos; + n = iter->stack[head].node->n; + } } /* Leafs are a special case */ - while (stack[head].pos > 2 * stack[head].node->n) { /* +1 ?? */ + while (pos > 2 * n) { /* +1 ?? */ if (head == 0) return NULL; - /* Pop, if so */ - stack[head].pos = 0; - stack[head].node = NULL; - head--; - stack[head].pos++; + { /* Pop, if so */ + iter->stack[head].pos = 0; + iter->stack[head].node = NULL; + iter->head--; head--; + iter->stack[head].pos++; + + pos = iter->stack[head].pos; + n = iter->stack[head].node->n; + } } /* On evens, we decent into children */ - if (!node_leaf(stack[head].node)) { - if (stack[head].pos % 2 == 0) { - /* push child node onto stack */ - stack[head + 1].pos = 0; - stack[head + 1].node = stack[head].node->children[stack[head].pos / 2]; - head++; + if (!node_leaf(iter->stack[head].node)) { + if (pos % 2 == 0) { + { /* push child node onto iter->stack */ + iter->stack[head + 1].pos = 0; + iter->stack[head + 1].node = iter->stack[head].node->children[pos / 2]; + iter->head++; head++; + + pos = iter->stack[head].pos; + n = iter->stack[head].node->n; + } /* Decent all the way to the left, if pos == 0 */ - while (!node_leaf(stack[head].node)) { - stack[head + 1].pos = 0; - stack[head + 1].node = stack[head].node->children[0]; - head++; + while (!node_leaf(iter->stack[iter->head].node)) { + iter->stack[head + 1].pos = 0; + iter->stack[head + 1].node = iter->stack[head].node->children[0]; + iter->head++; head++; + + pos = iter->stack[head].pos; + n = iter->stack[head].node->n; } } } /* Finally, update index and return a value */ - if (node_leaf(stack[head].node)) { - stack[head].pos += 2; + if (node_leaf(iter->stack[head].node)) { + iter->stack[head].pos += 2; + pos = iter->stack[head].pos; } else { - stack[head].pos++; + iter->stack[head].pos++; + pos = iter->stack[head].pos; } - return stack[head].node->items + btree->elem_size * ((stack[head].pos - 1) / 2); + return iter->stack[head].node->items + + tree->elem_size * ( (pos - 1) / 2 ); return NULL; } -- cgit v1.3