kbtree.h File Reference

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.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)
#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

__KB_DEL

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

__kb_destroy

#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)

__KB_GET

#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); \
  }

__KB_GET_AUX1

#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; \
  }

__KB_INTERVAL

#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); \
  }

__KB_ITR

#define __KB_ITR	(		name,
			key_t,
			kbnode_t
	)

__KB_KEY

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

__KB_PTR

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

__KB_PUT

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

__KB_TREE_T

#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; \

KB_DEFAULT_SIZE

#define KB_DEFAULT_SIZE   512

kb_del

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

kb_del_itr

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

kb_delp

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

kb_destroy

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

kb_generic_cmp

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

kb_get

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

kb_getp

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

kb_init

#define kb_init

(

b

)

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

kb_interval

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

kb_intervalp

#define kb_intervalp	(		name,
			b,
			k,
			l,
			u
	)		kb_intervalp_##name(b, k, l, u)

kb_itr_first

#define kb_itr_first	(		name,
			b,
			i
	)		kb_itr_first_##name(b, i)

kb_itr_get

#define kb_itr_get	(		name,
			b,
			k,
			i
	)		kb_itr_get_##name(b, k, i)

kb_itr_getp

#define kb_itr_getp	(		name,
			b,
			k,
			i
	)		kb_itr_getp_##name(b, k, i)

kb_itr_key

#define kb_itr_key

(

itr

)

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

kb_itr_next

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

kb_itr_prev

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

kb_itr_valid

#define kb_itr_valid

(

itr

)

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

KB_MAX_DEPTH

#define KB_MAX_DEPTH   64

kb_put

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

kb_putp

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

kb_size

#define kb_size

(

b

)

((b)->n_keys)

kb_str_cmp

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

kbitr_t

#define kbitr_t

(

name

)

kbitr_##name##_t

KBTREE_INIT

#define KBTREE_INIT	(		name,
			key_t,
			__cmp,
			T
	)

Value:

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

KBTREE_INIT_IMPL

#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)

kbtree_t

#define kbtree_t

(

name

)

kbtree_##name##_t