32 #if defined(RBT_IMPLICIT_LOCKING)
36 #ifndef HAVE_POSIX_MEMALIGN
38 int posix_memalign(
void **memptr,
size_t alignment,
size_t size);
50 RBT_WALK_PREORDER = 0x01,
51 RBT_WALK_INORDER = 0x02,
52 RBT_WALK_POSTORDER = 0x03,
53 RBT_WALK_LEVELORDER = 0x04,
54 RBT_WALK_RAWNODE = 0x10
57 #define RBT_WALK_TYPEMASK 0x0f
58 #define RBT_WALK_FLAGMASK 0xf0
74 #define rbt_node_ptr(np) ((struct rbt_node *)((uintptr_t)(np)&(UINTPTR_MAX << 1)))
75 #define rbt_node_setptr(dst,src) (dst) = (struct rbt_node *)((uintptr_t)rbt_node_ptr(src)|((uintptr_t)(dst)&1))
77 #define rbt_node_setcolor(np, cb) \
79 register struct rbt_node *__n = rbt_node_ptr(np); \
80 register uint8_t __c = (cb) & 1; \
83 if (__c) __n->_chld[0] = (struct rbt_node *)((uintptr_t)(__n->_chld[0]) | 1); \
84 else __n->_chld[0] = rbt_node_ptr(__n->_chld[0]); \
87 #define rbt_node_getcolor_raw(cp) ((uintptr_t)(cp) & 1)
88 #define rbt_node_getcolor(np) (rbt_node_ptr(np) == NULL ? RBT_NODE_CB : rbt_node_getcolor_raw(rbt_node_ptr(np)->_chld[0]))
89 #define rbt_node_cpycolor(dn, sn) rbt_node_setcolor((dn), rbt_node_getcolor(sn))
91 #define rbt_hpush4(__a, __p) \
99 #define rbt_hpush3(__a, __p) \
106 #define rbt_redfix(__h, __d, v) \
108 if (((__d) & 3) < 2) { \
109 if (((__d) & 3) == 0) { \
110 rbt_node_setptr(v, rbt_node_rotate_R(__h[2])); \
112 rbt_node_setptr(v, rbt_node_rotate_RL(__h[2])); \
115 if (((__d) & 3) == 2) { \
116 rbt_node_setptr(v, rbt_node_rotate_LR(__h[2])); \
118 rbt_node_setptr(v, rbt_node_rotate_L(__h[2])); \
127 #if defined(RBT_IMPLICIT_LOCKING)
128 pthread_rwlock_t lock;
138 rbt_t *rbt_new(rbt_type_t type);
147 void rbt_free2(
rbt_t *rbt,
void (*
callback)(
void *,
void *),
void *user);
153 int rbt_rlock(
rbt_t *rbt);
159 void rbt_runlock(
rbt_t *rbt);
165 int rbt_wlock(
rbt_t *rbt);
171 void rbt_wunlock(
rbt_t *rbt);
178 size_t rbt_size(
rbt_t *rbt);
180 #define rbt_walk_push(n) stack[depth++] = (n)
181 #define rbt_walk_pop() stack[--depth]
182 #define rbt_walk_top() stack[depth-1]
184 int rbt_walk_preorder(
rbt_t *rbt,
int (*
callback)(
void *), rbt_walk_t flags);
185 int rbt_walk_inorder(
rbt_t *rbt,
int (*
callback)(
void *), rbt_walk_t flags);
186 int rbt_walk_inorder2(
rbt_t *rbt,
int (*
callback)(
void *,
void *),
void *user, rbt_walk_t flags);
187 int rbt_walk_postorder(
rbt_t *rbt,
int (*
callback)(
void *), rbt_walk_t flags);