kbtree.h File Reference

#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>
#include "nvim/memory.h"

Go to the source code of this file.

Macros
#define	KB_MAX_DEPTH   64
#define	__KB_KEY(type, x)   (x->key)
#define	__KB_PTR(btr, x)   (x->ptr)
#define	__KB_TREE_T(name, key_t, T)
#define	__kb_destroy(kbnode_t, b)
#define	__KB_GET_AUX1(name, key_t, kbnode_t, __cmp)
#define	__KB_GET(name, key_t, kbnode_t)
#define	__KB_INTERVAL(name, key_t, kbnode_t)
#define	__KB_PUT(name, key_t, kbnode_t, __cmp, T, ILEN)
#define	__KB_DEL(name, key_t, kbnode_t, T)
#define	__KB_ITR(name, key_t, kbnode_t)
#define	KBTREE_INIT(name, key_t, __cmp, T)   KBTREE_INIT_IMPL(name, key_t, kbnode_##name##_t, __cmp, T, (sizeof(kbnode_##name##_t)+(2*T)*sizeof(void *)))
#define	KBTREE_INIT_IMPL(name, key_t, kbnode_t, __cmp, T, ILEN)
#define	KB_DEFAULT_SIZE   512
#define	kbtree_t(name)   kbtree_##name##_t
#define	kbitr_t(name)   kbitr_##name##_t
#define	kb_init(b)   ((b)->n_keys = (b)->n_nodes = 0, (b)->root = 0)
#define	kb_destroy(name, b)   __kb_destroy(kbnode_##name##_t, b)
#define	kb_get(name, b, k)   kb_get_##name(b, k)
#define	kb_put(name, b, k)   kb_put_##name(b, k)
#define	kb_del(name, b, k)   kb_del_##name(b, k)
#define	kb_interval(name, b, k, l, u)   kb_interval_##name(b, k, l, u)
#define	kb_getp(name, b, k)   kb_getp_##name(b, k)
#define	kb_putp(name, b, k)   kb_putp_##name(b, k)
#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_getp(name, b, k, i)   kb_itr_getp_##name(b, k, i)
#define	kb_itr_next(name, b, i)   kb_itr_next_##name(b, i)
#define	kb_itr_prev(name, b, i)   kb_itr_prev_##name(b, i)
#define	kb_del_itr(name, b, i)   kb_del_itr_##name(b, i)
#define	kb_itr_key(itr)   __KB_KEY(dummy, (itr)->p->x)[(itr)->p->i]
#define	kb_itr_valid(itr)   ((itr)->p >= (itr)->stack)
#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)

Macro Definition Documentation

#define __KB_DEL	(		name,
			key_t,
			kbnode_t,
			T
	)

#define __kb_destroy	(		kbnode_t,
			b
	)

Value:

do {                                            \
        int i;                                                          \
        unsigned int max = 8;                                           \
        kbnode_t *x, **top, **stack = 0;                                \
		if (b->root) {                                                    \
            top = stack = (kbnode_t**)xcalloc(max, sizeof(kbnode_t*));  \
            *top++ = (b)->root;                                         \
			while (top != stack) {                                       \
                x = *--top;                                             \
				if (x->is_internal == 0) { XFREE_CLEAR(x); continue; }          \
				for (i = 0; i <= x->n; ++i)                             \
                    if (__KB_PTR(b, x)[i]) {                            \
						if (top - stack == (int)max) {                    \
                            max <<= 1;                                  \
                            stack = (kbnode_t**)xrealloc(stack, max * sizeof(kbnode_t*)); \
                            top = stack + (max>>1);                     \
                        }                                               \
                        *top++ = __KB_PTR(b, x)[i];                     \
                    }                                                   \
				XFREE_CLEAR(x);                                             \
            }                                                           \
        }                                                               \
		XFREE_CLEAR(stack);                                           \
    } while (0)

#define __KB_GET	(		name,
			key_t,
			kbnode_t
	)

Value:

static key_t *kb_getp_##name(kbtree_##name##_t *b, key_t * __restrict k) \
    {                                                                   \
		if (!b->root) { \
		    return 0; \
        } \
        int i, r = 0;                                                   \
        kbnode_t *x = b->root;                                          \
		while (x) {                                                       \
			i = __kb_getp_aux_##name(x, k, &r);                          \
			if (i >= 0 && r == 0) return &__KB_KEY(key_t, x)[i];     \
            if (x->is_internal == 0) return 0;                          \
            x = __KB_PTR(b, x)[i + 1];                                  \
        }                                                               \
        return 0;                                                       \
    }                                                                   \
    static inline key_t *kb_get_##name(kbtree_##name##_t *b, key_t k) \
    {                                                                   \
        return kb_getp_##name(b, &k);                                   \
    }

#define __KB_GET_AUX1	(		name,
			key_t,
			kbnode_t,
			__cmp
	)

Value:

static inline int __kb_getp_aux_##name(const kbnode_t * __restrict x, key_t * __restrict k, int *r) \
    {                                                                   \
        int tr, *rr, begin = 0, end = x->n;                             \
		if (x->n == 0) return -1;                                     \
        rr = r? r : &tr;                                                \
        while (begin < end) {                                           \
            int mid = (begin + end) >> 1;                               \
			if (__cmp(__KB_KEY(key_t, x)[mid], *k) < 0) begin = mid + 1; \
            else end = mid;                                             \
        }                                                               \
        if (begin == x->n) { *rr = 1; return x->n - 1; }                \
		if ((*rr = __cmp(*k, __KB_KEY(key_t, x)[begin])) < 0) --begin;    \
		return begin;                                                 \
    }

#define __KB_INTERVAL	(		name,
			key_t,
			kbnode_t
	)

Value:

static inline void kb_intervalp_##name(kbtree_##name##_t *b, key_t * __restrict k, key_t **lower, key_t **upper)    \
    {                                                                   \
		if (!b->root) { \
		    return; \
        } \
        int i, r = 0;                                                   \
        kbnode_t *x = b->root;                                          \
        *lower = *upper = 0;                                            \
		while (x) {                                                       \
			i = __kb_getp_aux_##name(x, k, &r);                          \
			if (i >= 0 && r == 0) {                                      \
                *lower = *upper = &__KB_KEY(key_t, x)[i];               \
				return;                                                 \
            }                                                           \
			if (i >= 0) *lower = &__KB_KEY(key_t, x)[i];             \
			if (i < x->n - 1) *upper = &__KB_KEY(key_t, x)[i + 1];       \
			if (x->is_internal == 0) return;                         \
            x = __KB_PTR(b, x)[i + 1];                                  \
        }                                                               \
    }                                                                   \
    static inline void kb_interval_##name(kbtree_##name##_t *b, key_t k, key_t **lower, key_t **upper) \
    {                                                                   \
        kb_intervalp_##name(b, &k, lower, upper);                       \
    }

#define __KB_ITR	(		name,
			key_t,
			kbnode_t
	)

#define __KB_KEY	(		type,
			x
	)		(x->key)

#define __KB_PTR	(		btr,
			x
	)		(x->ptr)

#define __KB_PUT	(		name,
			key_t,
			kbnode_t,
			__cmp,
			T,
			ILEN
	)

#define __KB_TREE_T	(		name,
			key_t,
			T
	)

Value:

typedef struct kbnode_##name##_s kbnode_##name##_t;     \
    struct kbnode_##name##_s {              \
      int32_t n; \
      bool is_internal; \
      key_t key[2*T-1]; \
      kbnode_##name##_t *ptr[]; \
    } ; \
    \
    typedef struct { \
        kbnode_##name##_t *root; \
        int n_keys, n_nodes; \
    } kbtree_##name##_t; \
    \
    typedef struct { \
        kbnode_##name##_t *x; \
        int i; \
    } kbpos_##name##_t; \
    typedef struct { \
        kbpos_##name##_t stack[KB_MAX_DEPTH], *p; \
    } kbitr_##name##_t; \

#define KB_DEFAULT_SIZE   512

#define kb_del	(		name,
			b,
			k
	)		kb_del_##name(b, k)

#define kb_del_itr	(		name,
			b,
			i
	)		kb_del_itr_##name(b, i)

#define kb_delp	(		name,
			b,
			k
	)		kb_delp_##name(b, k)

#define kb_destroy	(		name,
			b
	)		__kb_destroy(kbnode_##name##_t, b)

#define kb_generic_cmp	(		a,
			b
	)		(((b) < (a)) - ((a) < (b)))

#define kb_get	(		name,
			b,
			k
	)		kb_get_##name(b, k)

#define kb_getp	(		name,
			b,
			k
	)		kb_getp_##name(b, k)

#define kb_init

(

b

)

((b)->n_keys = (b)->n_nodes = 0, (b)->root = 0)

#define kb_interval	(		name,
			b,
			k,
			l,
			u
	)		kb_interval_##name(b, k, l, u)

#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_getp	(		name,
			b,
			k,
			i
	)		kb_itr_getp_##name(b, k, i)

#define kb_itr_key

(

itr

)

__KB_KEY(dummy, (itr)->p->x)[(itr)->p->i]

#define kb_itr_next	(		name,
			b,
			i
	)		kb_itr_next_##name(b, i)

#define kb_itr_prev	(		name,
			b,
			i
	)		kb_itr_prev_##name(b, i)

#define kb_itr_valid

(

itr

)

((itr)->p >= (itr)->stack)

#define KB_MAX_DEPTH   64

#define kb_put	(		name,
			b,
			k
	)		kb_put_##name(b, k)

#define kb_putp	(		name,
			b,
			k
	)		kb_putp_##name(b, k)

#define kb_size

(

b

)

((b)->n_keys)

#define kb_str_cmp	(		a,
			b
	)		strcmp(a, b)

#define kbitr_t

(

name

)

kbitr_##name##_t

#define KBTREE_INIT	(		name,
			key_t,
			__cmp,
			T
	)		KBTREE_INIT_IMPL(name, key_t, kbnode_##name##_t, __cmp, T, (sizeof(kbnode_##name##_t)+(2*T)*sizeof(void *)))

#define KBTREE_INIT_IMPL	(		name,
			key_t,
			kbnode_t,
			__cmp,
			T,
			ILEN
	)

Value:

__KB_TREE_T(name, key_t, T)                         \
	__KB_GET_AUX1(name, key_t, kbnode_t, __cmp)            \
	__KB_GET(name, key_t, kbnode_t)                        \
	__KB_INTERVAL(name, key_t, kbnode_t)                   \
	__KB_PUT(name, key_t, kbnode_t, __cmp, T, ILEN)                \
	__KB_DEL(name, key_t, kbnode_t, T) \
	__KB_ITR(name, key_t, kbnode_t)

#define kbtree_t

(

name

)

kbtree_##name##_t