00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef RBT_COMMON_H
00023 #define RBT_COMMON_H
00024
00025 #include <stdint.h>
00026 #include <stdbool.h>
00027
00028 #if defined(RBT_IMPLICIT_LOCKING)
00029 # include <pthread.h>
00030 #endif
00031
00032 typedef enum {
00033 RBT_GENKEY,
00034 RBT_STRKEY,
00035 RBT_I32KEY,
00036 RBT_I64KEY
00037 } rbt_type_t;
00038
00039 typedef enum {
00040 RBT_WALK_PREORDER = 0x01,
00041 RBT_WALK_INORDER = 0x02,
00042 RBT_WALK_POSTORDER = 0x03,
00043 RBT_WALK_LEVELORDER = 0x04,
00044 RBT_WALK_RAWNODE = 0x10
00045 } rbt_walk_t;
00046
00047 #define RBT_WALK_TYPEMASK 0x0f
00048 #define RBT_WALK_FLAGMASK 0xf0
00049
00054 struct rbt_node {
00055 struct rbt_node *_chld[2];
00056 uint8_t _node[];
00057 };
00058
00059 #define RBT_NODE_CB 0
00060 #define RBT_NODE_CR 1
00061 #define RBT_NODE_SL 0
00062 #define RBT_NODE_SR 1
00063
00064 #define rbt_node_ptr(np) ((struct rbt_node *)((uintptr_t)(np)&(UINTPTR_MAX << 1)))
00065 #define rbt_node_setptr(dst,src) (dst) = (struct rbt_node *)((uintptr_t)rbt_node_ptr(src)|((uintptr_t)(dst)&1))
00066
00067 #define rbt_node_setcolor(np, cb) \
00068 do { \
00069 register struct rbt_node *__n = rbt_node_ptr(np); \
00070 register uint8_t __c = (cb) & 1; \
00071 \
00072 if (__n != NULL) { \
00073 if (__c) __n->_chld[0] = (struct rbt_node *)((uintptr_t)(__n->_chld[0]) | 1); \
00074 else __n->_chld[0] = rbt_node_ptr(__n->_chld[0]); \
00075 } \
00076 } while(0)
00077 #define rbt_node_getcolor_raw(cp) ((uintptr_t)(cp) & 1)
00078 #define rbt_node_getcolor(np) (rbt_node_ptr(np) == NULL ? RBT_NODE_CB : rbt_node_getcolor_raw(rbt_node_ptr(np)->_chld[0]))
00079 #define rbt_node_cpycolor(dn, sn) rbt_node_setcolor((dn), rbt_node_getcolor(sn))
00080
00081 #define rbt_hpush4(__a, __p) \
00082 do { \
00083 __a[3] = __a[2]; \
00084 __a[2] = __a[1]; \
00085 __a[1] = __a[0]; \
00086 __a[0] = __p; \
00087 } while(0)
00088
00089 #define rbt_hpush3(__a, __p) \
00090 do { \
00091 __a[2] = __a[1]; \
00092 __a[1] = __a[0]; \
00093 __a[0] = __p; \
00094 } while(0)
00095
00096 #define rbt_redfix(__h, __d, v) \
00097 do { \
00098 if (((__d) & 3) < 2) { \
00099 if (((__d) & 3) == 0) { \
00100 rbt_node_setptr(v, rbt_node_rotate_R(__h[2])); \
00101 } else { \
00102 rbt_node_setptr(v, rbt_node_rotate_RL(__h[2])); \
00103 } \
00104 } else { \
00105 if (((__d) & 3) == 2) { \
00106 rbt_node_setptr(v, rbt_node_rotate_LR(__h[2])); \
00107 } else { \
00108 rbt_node_setptr(v, rbt_node_rotate_L(__h[2])); \
00109 } \
00110 } \
00111 } while(0)
00112
00113 struct rbt {
00114 struct rbt_node *root;
00115 size_t size;
00116 rbt_type_t type;
00117 #if defined(RBT_IMPLICIT_LOCKING)
00118 pthread_rwlock_t lock;
00119 #endif
00120 };
00121
00122 typedef struct rbt rbt_t;
00123
00128 rbt_t *rbt_new(rbt_type_t type);
00129
00136 void rbt_free(rbt_t *rbt, void (*callback)(void *));
00137
00142 int rbt_rlock(rbt_t *rbt);
00143
00148 void rbt_runlock(rbt_t *rbt);
00149
00154 int rbt_wlock(rbt_t *rbt);
00155
00160 void rbt_wunlock(rbt_t *rbt);
00161
00162 struct rbt_node *rbt_node_rotate_L(struct rbt_node *);
00163 struct rbt_node *rbt_node_rotate_R(struct rbt_node *);
00164 struct rbt_node *rbt_node_rotate_LR(struct rbt_node *);
00165 struct rbt_node *rbt_node_rotate_RL(struct rbt_node *);
00166
00167 size_t rbt_size(rbt_t *rbt);
00168
00169 #define rbt_walk_push(n) stack[depth++] = (n)
00170 #define rbt_walk_pop() stack[--depth]
00171 #define rbt_walk_top() stack[depth-1]
00172
00173 int rbt_walk_preorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00174 int rbt_walk_inorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00175 int rbt_walk_postorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00176
00177 #endif