Macros
kbtree.h File Reference
#include <stdlib.h>
#include <string.h>
#include <stdint.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(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(x); \
} \
} \
xfree(stack); \
} while (0)
if
if(len)
Definition: encode.c:226
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:167
for
for(size_t i=1;i< ARRAY_SIZE(argv);i++)
Definition: typval.c:1215
xcalloc
void * xcalloc(size_t count, size_t size) FUNC_ATTR_MALLOC FUNC_ATTR_ALLOC_SIZE_PROD(1
while
while((size_t)(++hi-hifirst)< hinum)
Definition: eval.c:22195
i
int i
Definition: typval.c:868
xfree
xfree(sourcing_name)
__KB_PTR
#define __KB_PTR(btr, x)
Definition: kbtree.h:40
#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); \
}
if
if(len)
Definition: encode.c:226
__KB_KEY
#define __KB_KEY(type, x)
Definition: kbtree.h:39
return
return
Definition: eval.c:14724
while
while((size_t)(++hi-hifirst)< hinum)
Definition: eval.c:22195
name
char * name
Definition: eval.c:1850
i
int i
Definition: typval.c:868
__KB_PTR
#define __KB_PTR(btr, x)
Definition: kbtree.h:40
#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; \
}
if
if(len)
Definition: encode.c:226
__KB_KEY
#define __KB_KEY(type, x)
Definition: kbtree.h:39
n
static char size_t n
Definition: memline.c:3251
return
return
Definition: eval.c:14724
while
while((size_t)(++hi-hifirst)< hinum)
Definition: eval.c:22195
name
char * name
Definition: eval.c:1850
else
else
Definition: eval.c:1854
#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); \
}
if
if(len)
Definition: encode.c:226
__KB_KEY
#define __KB_KEY(type, x)
Definition: kbtree.h:39
n
static char size_t n
Definition: memline.c:3251
return
return
Definition: eval.c:14724
while
while((size_t)(++hi-hifirst)< hinum)
Definition: eval.c:22195
name
char * name
Definition: eval.c:1850
i
int i
Definition: typval.c:868
__KB_PTR
#define __KB_PTR(btr, x)
Definition: kbtree.h:40
#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; \
n
static char size_t n
Definition: memline.c:3251
name
char * name
Definition: eval.c:1850
KB_MAX_DEPTH
#define KB_MAX_DEPTH
Definition: kbtree.h:37
i
int i
Definition: typval.c:868
p
char_u * p
Definition: eval.c:2042
#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)
__KB_ITR
#define __KB_ITR(name, key_t, kbnode_t)
Definition: kbtree.h:317
__KB_GET
#define __KB_GET(name, key_t, kbnode_t)
Definition: kbtree.h:106
__KB_TREE_T
#define __KB_TREE_T(name, key_t, T)
Definition: kbtree.h:42
__KB_GET_AUX1
#define __KB_GET_AUX1(name, key_t, kbnode_t, __cmp)
Definition: kbtree.h:90
__KB_INTERVAL
#define __KB_INTERVAL(name, key_t, kbnode_t)
Definition: kbtree.h:127
name
char * name
Definition: eval.c:1850
__KB_PUT
#define __KB_PUT(name, key_t, kbnode_t, __cmp, T, ILEN)
Definition: kbtree.h:153
__KB_DEL
#define __KB_DEL(name, key_t, kbnode_t, T)
Definition: kbtree.h:217
#define kbtree_t (   name)    kbtree_##name##_t