Macros
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,
 
)
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->key)

◆ __KB_PTR

#define __KB_PTR (   btr,
 
)    (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,
 
)    __kb_destroy(kbnode_##name##_t, b)

◆ kb_generic_cmp

#define kb_generic_cmp (   a,
 
)    (((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,
 
)    kb_interval_##name(b, k, l, u)

◆ kb_intervalp

#define kb_intervalp (   name,
  b,
  k,
  l,
 
)    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,
 
)    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
__KB_PTR
#define __KB_PTR(btr, x)
Definition: kbtree.h:47
ptr
char_u * ptr
Definition: normal.c:3172
xcalloc
void * xcalloc(size_t count, size_t size) FUNC_ATTR_MALLOC FUNC_ATTR_ALLOC_SIZE_PROD(1
i
static void int i
Definition: edit.c:2997
p
char_u * p
Definition: eval.c:2013
KBTREE_INIT_IMPL
#define KBTREE_INIT_IMPL(name, key_t, kbnode_t, __cmp, T, ILEN)
Definition: kbtree.h:440
xrealloc
void * xrealloc(void *ptr, size_t size) FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_ALLOC_SIZE(2) FUNC_ATTR_NONNULL_RET
Definition: memory.c:154
__KB_KEY
#define __KB_KEY(type, x)
Definition: kbtree.h:46
while
while((size_t)(++hi - hifirst)< hinum)
Definition: eval.c:10350
if
if(len)
Definition: encode.c:226
n
int n
Definition: funcs.c:8562
k
int k
Definition: regexp_nfa.c:3965
ILEN
#define ILEN
Definition: marktree.c:57
T
#define T
Definition: marktree.c:56
r
regsubs_T * r
Definition: regexp_nfa.c:4372
return
return
Definition: funcs.c:9014
KB_MAX_DEPTH
#define KB_MAX_DEPTH
Definition: kbtree.h:44
name
char_u * name
Definition: userfunc.c:821
else
else
Definition: funcs.c:8584
XFREE_CLEAR
#define XFREE_CLEAR(ptr)
Definition: memory.h:44
__KB_TREE_T
#define __KB_TREE_T(name, key_t, T)
Definition: kbtree.h:49