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 #ifdef HAVE_CONFIG_H
00026 #include <config.h>
00027 #endif
00028
00029 #include <stdint.h>
00030 #include <stdbool.h>
00031
00032 #if defined(RBT_IMPLICIT_LOCKING)
00033 # include <pthread.h>
00034 #endif
00035
00036 #ifndef HAVE_POSIX_MEMALIGN
00037 # ifdef HAVE_MEMALIGN
00038 int posix_memalign(void **memptr, size_t alignment, size_t size);
00039 # endif
00040 #endif
00041
00042 typedef enum {
00043 RBT_GENKEY,
00044 RBT_STRKEY,
00045 RBT_I32KEY,
00046 RBT_I64KEY
00047 } rbt_type_t;
00048
00049 typedef enum {
00050 RBT_WALK_PREORDER = 0x01,
00051 RBT_WALK_INORDER = 0x02,
00052 RBT_WALK_POSTORDER = 0x03,
00053 RBT_WALK_LEVELORDER = 0x04,
00054 RBT_WALK_RAWNODE = 0x10
00055 } rbt_walk_t;
00056
00057 #define RBT_WALK_TYPEMASK 0x0f
00058 #define RBT_WALK_FLAGMASK 0xf0
00059
00064 struct rbt_node {
00065 struct rbt_node *_chld[2];
00066 uint8_t _node[];
00067 };
00068
00069 #define RBT_NODE_CB 0
00070 #define RBT_NODE_CR 1
00071 #define RBT_NODE_SL 0
00072 #define RBT_NODE_SR 1
00073
00074 __attribute__((pure)) static inline struct rbt_node *rbt_node_ptr(const struct rbt_node *nodep)
00075 {
00076 register uintptr_t nodep_uint = (uintptr_t)(nodep);
00077 nodep_uint &= UINTPTR_MAX << 1;
00078 return (struct rbt_node *)(nodep_uint);
00079 }
00080
00081 #define rbt_node_setptr(dst,src) (dst) = (struct rbt_node *)((uintptr_t)rbt_node_ptr(src)|((uintptr_t)(dst)&1))
00082
00083 #define rbt_node_setcolor(np, cb) \
00084 do { \
00085 register struct rbt_node *__n = rbt_node_ptr(np); \
00086 register uint8_t __c = (cb) & 1; \
00087 \
00088 if (__n != NULL) { \
00089 if (__c) __n->_chld[0] = (struct rbt_node *)((uintptr_t)(__n->_chld[0]) | 1); \
00090 else __n->_chld[0] = rbt_node_ptr(__n->_chld[0]); \
00091 } \
00092 } while(0)
00093 #define rbt_node_getcolor_raw(cp) ((uintptr_t)(cp) & 1)
00094 #define rbt_node_getcolor(np) (rbt_node_ptr(np) == NULL ? RBT_NODE_CB : rbt_node_getcolor_raw(rbt_node_ptr(np)->_chld[0]))
00095 #define rbt_node_cpycolor(dn, sn) rbt_node_setcolor((dn), rbt_node_getcolor(sn))
00096
00097 #define rbt_hpush4(__a, __p) \
00098 do { \
00099 __a[3] = __a[2]; \
00100 __a[2] = __a[1]; \
00101 __a[1] = __a[0]; \
00102 __a[0] = __p; \
00103 } while(0)
00104
00105 #define rbt_hpush3(__a, __p) \
00106 do { \
00107 __a[2] = __a[1]; \
00108 __a[1] = __a[0]; \
00109 __a[0] = __p; \
00110 } while(0)
00111
00112 #define rbt_redfix(__h, __d, v) \
00113 do { \
00114 if (((__d) & 3) < 2) { \
00115 if (((__d) & 3) == 0) { \
00116 rbt_node_setptr(v, rbt_node_rotate_R(__h[2])); \
00117 } else { \
00118 rbt_node_setptr(v, rbt_node_rotate_RL(__h[2])); \
00119 } \
00120 } else { \
00121 if (((__d) & 3) == 2) { \
00122 rbt_node_setptr(v, rbt_node_rotate_LR(__h[2])); \
00123 } else { \
00124 rbt_node_setptr(v, rbt_node_rotate_L(__h[2])); \
00125 } \
00126 } \
00127 } while(0)
00128
00129 struct rbt {
00130 struct rbt_node *root;
00131 size_t size;
00132 rbt_type_t type;
00133 #if defined(RBT_IMPLICIT_LOCKING)
00134 pthread_rwlock_t lock;
00135 #endif
00136 };
00137
00138 typedef struct rbt rbt_t;
00139
00144 rbt_t *rbt_new(rbt_type_t type);
00145
00152 void rbt_free(rbt_t *rbt, void (*callback)(void *));
00153 void rbt_free2(rbt_t *rbt, void (*callback)(void *, void *), void *user);
00154
00159 int rbt_rlock(rbt_t *rbt);
00160
00165 void rbt_runlock(rbt_t *rbt);
00166
00171 int rbt_wlock(rbt_t *rbt);
00172
00177 void rbt_wunlock(rbt_t *rbt);
00178
00179 struct rbt_node *rbt_node_rotate_L(struct rbt_node *);
00180 struct rbt_node *rbt_node_rotate_R(struct rbt_node *);
00181 struct rbt_node *rbt_node_rotate_LR(struct rbt_node *);
00182 struct rbt_node *rbt_node_rotate_RL(struct rbt_node *);
00183
00184 size_t rbt_size(rbt_t *rbt);
00185
00186 #define rbt_walk_push(n) stack[depth++] = (n)
00187 #define rbt_walk_pop() stack[--depth]
00188 #define rbt_walk_top() stack[depth-1]
00189
00190 int rbt_walk_preorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00191 int rbt_walk_inorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00192 int rbt_walk_inorder2(rbt_t *rbt, int (*callback)(void *, void *), void *user, rbt_walk_t flags);
00193 int rbt_walk_postorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00194
00195 #endif