From 22e1e915aeea56a3b5bff2e3fe34f63cda00914b Mon Sep 17 00:00:00 2001 From: Heng Li Date: Thu, 17 Sep 2015 19:23:33 -0400 Subject: [PATCH] added iterator interface to kbtree and deprecated the old macro interface --- kbtree.h | 152 +++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 98 insertions(+), 54 deletions(-) diff --git a/kbtree.h b/kbtree.h index 5ed5330..4eff10e 100644 --- a/kbtree.h +++ b/kbtree.h @@ -32,10 +32,21 @@ #include #include +#define KB_MAX_DEPTH 64 + typedef struct { int32_t is_internal:1, n:31; } kbnode_t; +typedef struct { + kbnode_t *x; + int i; +} kbpos_t; + +typedef struct { + kbpos_t stack[KB_MAX_DEPTH], *p; +} kbitr_t; + #define __KB_KEY(type, x) ((type*)((char*)x + 4)) #define __KB_PTR(btr, x) ((kbnode_t**)((char*)x + btr->off_ptr)) @@ -89,27 +100,6 @@ typedef struct { free(b); free(stack); \ } while (0) -#define __kb_get_first(key_t, b, ret) do { \ - kbnode_t *__x = (b)->root; \ - while (__KB_PTR(b, __x)[0] != 0) \ - __x = __KB_PTR(b, __x)[0]; \ - (ret) = __KB_KEY(key_t, __x)[0]; \ - } while (0) - -#define __KB_GET_AUX0(name, key_t, __cmp) \ - static inline int __kb_get_aux_##name(const kbnode_t * __restrict x, const key_t * __restrict k, int *r) \ - { \ - int tr, *rr, begin, end, n = x->n >> 1; \ - if (x->n == 0) return -1; \ - if (__cmp(*k, __KB_KEY(key_t, x)[n]) < 0) { \ - begin = 0; end = n; \ - } else { begin = n; end = x->n - 1; } \ - rr = r? r : &tr; \ - n = end; \ - while (n >= begin && (*rr = __cmp(*k, __KB_KEY(key_t, x)[n])) < 0) --n; \ - return n; \ - } - #define __KB_GET_AUX1(name, key_t, __cmp) \ static inline int __kb_getp_aux_##name(const kbnode_t * __restrict x, const key_t * __restrict k, int *r) \ { \ @@ -185,14 +175,16 @@ typedef struct { __KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[b->t - 1]; \ ++x->n; \ } \ - static void __kb_putp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k) \ + static key_t *__kb_putp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k) \ { \ int i = x->n - 1; \ + key_t *ret; \ if (x->is_internal == 0) { \ i = __kb_getp_aux_##name(x, k, 0); \ if (i != x->n - 1) \ memmove(__KB_KEY(key_t, x) + i + 2, __KB_KEY(key_t, x) + i + 1, (x->n - i - 1) * sizeof(key_t)); \ - __KB_KEY(key_t, x)[i + 1] = *k; \ + ret = &__KB_KEY(key_t, x)[i + 1]; \ + *ret = *k; \ ++x->n; \ } else { \ i = __kb_getp_aux_##name(x, k, 0) + 1; \ @@ -200,10 +192,11 @@ typedef struct { __kb_split_##name(b, x, i, __KB_PTR(b, x)[i]); \ if (__cmp(*k, __KB_KEY(key_t, x)[i]) > 0) ++i; \ } \ - __kb_putp_aux_##name(b, __KB_PTR(b, x)[i], k); \ + ret = __kb_putp_aux_##name(b, __KB_PTR(b, x)[i], k); \ } \ + return ret; \ } \ - static void kb_putp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ + static key_t *kb_putp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ { \ kbnode_t *r, *s; \ ++b->n_keys; \ @@ -216,7 +209,7 @@ typedef struct { __kb_split_##name(b, s, 0, r); \ r = s; \ } \ - __kb_putp_aux_##name(b, r, k); \ + return __kb_putp_aux_##name(b, r, k); \ } \ static inline void kb_put_##name(kbtree_##name##_t *b, const key_t k) \ { \ @@ -324,34 +317,49 @@ typedef struct { return kb_delp_##name(b, &k); \ } -typedef struct { - kbnode_t *x; - int i; -} __kbstack_t; +#define kb_itr_key(type, itr) __KB_KEY(type, (itr)->p->x)[(itr)->p->i] -#define __kb_traverse(key_t, b, __func) do { \ - int __kmax = 8; \ - __kbstack_t *__kstack, *__kp; \ - __kp = __kstack = (__kbstack_t*)calloc(__kmax, sizeof(__kbstack_t)); \ - __kp->x = (b)->root; __kp->i = 0; \ - for (;;) { \ - while (__kp->x && __kp->i <= __kp->x->n) { \ - if (__kp - __kstack == __kmax - 1) { \ - __kmax <<= 1; \ - __kstack = (__kbstack_t*)realloc(__kstack, __kmax * sizeof(__kbstack_t)); \ - __kp = __kstack + (__kmax>>1) - 1; \ - } \ - (__kp+1)->i = 0; (__kp+1)->x = __kp->x->is_internal? __KB_PTR(b, __kp->x)[__kp->i] : 0; \ - ++__kp; \ - } \ - --__kp; \ - if (__kp >= __kstack) { \ - if (__kp->x && __kp->i < __kp->x->n) __func(&__KB_KEY(key_t, __kp->x)[__kp->i]); \ - ++__kp->i; \ - } else break; \ - } \ - free(__kstack); \ - } while (0) +#define __KB_ITR(name, key_t) \ + static inline void kb_itr_first_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + { \ + itr->p = itr->stack; \ + itr->p->x = b->root; itr->p->i = 0; \ + while (itr->p->x->is_internal && __KB_PTR(b, itr->p->x)[0] != 0) { \ + kbnode_t *x = itr->p->x; \ + ++itr->p; \ + itr->p->x = __KB_PTR(b, x)[0]; itr->p->i = 0; \ + } \ + } \ + static int kb_itr_get_##name(kbtree_##name##_t *b, const key_t * __restrict k, kbitr_t *itr) \ + { \ + int i, r = 0; \ + itr->p = itr->stack; \ + itr->p->x = b->root; itr->p->i = 0; \ + while (itr->p->x) { \ + i = __kb_getp_aux_##name(itr->p->x, k, &r); \ + if (i >= 0 && r == 0) return 0; \ + if (itr->p->x->is_internal == 0) return -1; \ + itr->p[1].x = __KB_PTR(b, itr->p->x)[i + 1]; \ + itr->p[1].i = i; \ + ++itr->p; \ + } \ + return -1; \ + } \ + static inline int kb_itr_next_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + { \ + if (itr->p < itr->stack) return 0; \ + for (;;) { \ + ++itr->p->i; \ + while (itr->p->x && itr->p->i <= itr->p->x->n) { \ + itr->p[1].i = 0; \ + itr->p[1].x = itr->p->x->is_internal? __KB_PTR(b, itr->p->x)[itr->p->i] : 0; \ + ++itr->p; \ + } \ + --itr->p; \ + if (itr->p < itr->stack) return 0; \ + if (itr->p->x && itr->p->i < itr->p->x->n) return 1; \ + } \ + } #define KBTREE_INIT(name, key_t, __cmp) \ __KB_TREE_T(name) \ @@ -360,7 +368,8 @@ typedef struct { __KB_GET(name, key_t) \ __KB_INTERVAL(name, key_t) \ __KB_PUT(name, key_t, __cmp) \ - __KB_DEL(name, key_t) + __KB_DEL(name, key_t) \ + __KB_ITR(name, key_t) #define KB_DEFAULT_SIZE 512 @@ -376,9 +385,44 @@ typedef struct { #define kb_delp(name, b, k) kb_delp_##name(b, k) #define kb_intervalp(name, b, k, l, u) kb_intervalp_##name(b, k, l, u) +#define kb_itr_first(name, b, i) kb_itr_first_##name(b, i) +#define kb_itr_get(name, b, k, i) kb_itr_get_##name(b, k, i) +#define kb_itr_next(name, b, i) kb_itr_next_##name(b, i) + #define kb_size(b) ((b)->n_keys) #define kb_generic_cmp(a, b) (((b) < (a)) - ((a) < (b))) #define kb_str_cmp(a, b) strcmp(a, b) +/* The following is *DEPRECATED*!!! Use the iterator interface instead! */ + +typedef struct { + kbnode_t *x; + int i; +} __kbstack_t; + +#define __kb_traverse(key_t, b, __func) do { \ + int __kmax = 8; \ + __kbstack_t *__kstack, *__kp; \ + __kp = __kstack = (__kbstack_t*)calloc(__kmax, sizeof(__kbstack_t)); \ + __kp->x = (b)->root; __kp->i = 0; \ + for (;;) { \ + while (__kp->x && __kp->i <= __kp->x->n) { \ + if (__kp - __kstack == __kmax - 1) { \ + __kmax <<= 1; \ + __kstack = (__kbstack_t*)realloc(__kstack, __kmax * sizeof(__kbstack_t)); \ + __kp = __kstack + (__kmax>>1) - 1; \ + } \ + (__kp+1)->i = 0; (__kp+1)->x = __kp->x->is_internal? __KB_PTR(b, __kp->x)[__kp->i] : 0; \ + ++__kp; \ + } \ + --__kp; \ + if (__kp >= __kstack) { \ + if (__kp->x && __kp->i < __kp->x->n) __func(&__KB_KEY(key_t, __kp->x)[__kp->i]); \ + ++__kp->i; \ + } else break; \ + } \ + free(__kstack); \ + } while (0) + #endif -- 2.47.3