55#define LLRB_VENDOR "william@25thandClement.com"
56#define LLRB_VERSION 0x20130925
60#define LLRB_STATIC __attribute__((__unused__)) static
62#define LLRB_STATIC static
66#define LLRB_HEAD(name, type) \
67struct name { struct type *rbh_root; }
69#define LLRB_INITIALIZER(root) { 0 }
71#define LLRB_INIT(root) do { (root)->rbh_root = 0; } while (0)
76#define LLRB_ENTRY(type) \
77struct { struct type *rbe_left, *rbe_right, *rbe_parent; _Bool rbe_color; }
79#define LLRB_LEFT(elm, field) (elm)->field.rbe_left
80#define LLRB_RIGHT(elm, field) (elm)->field.rbe_right
81#define LLRB_PARENT(elm, field) (elm)->field.rbe_parent
82#define LLRB_EDGE(head, elm, field) (((elm) == LLRB_ROOT(head))? &LLRB_ROOT(head) : ((elm) == LLRB_LEFT(LLRB_PARENT((elm), field), field))? &LLRB_LEFT(LLRB_PARENT((elm), field), field) : &LLRB_RIGHT(LLRB_PARENT((elm), field), field))
83#define LLRB_COLOR(elm, field) (elm)->field.rbe_color
84#define LLRB_ROOT(head) (head)->rbh_root
85#define LLRB_EMPTY(head) ((head)->rbh_root == 0)
86#define LLRB_ISRED(elm, field) ((elm) && LLRB_COLOR((elm), field) == LLRB_RED)
88#define LLRB_PROTOTYPE(name, type, field, cmp) \
89 LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
90#define LLRB_PROTOTYPE_STATIC(name, type, field, cmp) \
91 LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
92#define LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
93attr struct type *name##_LLRB_INSERT(struct name *, struct type *); \
94attr struct type *name##_LLRB_DELETE(struct name *, struct type *); \
95attr struct type *name##_LLRB_FIND(struct name *, struct type *); \
96attr struct type *name##_LLRB_MIN(struct type *); \
97attr struct type *name##_LLRB_MAX(struct type *); \
98attr struct type *name##_LLRB_NEXT(struct type *);
100#define LLRB_GENERATE(name, type, field, cmp) \
101 LLRB_GENERATE_INTERNAL(name, type, field, cmp,)
102#define LLRB_GENERATE_STATIC(name, type, field, cmp) \
103 LLRB_GENERATE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
104#define LLRB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
105static inline void name##_LLRB_ROTL(struct type **pivot) { \
106 struct type *a = *pivot; \
107 struct type *b = LLRB_RIGHT(a, field); \
108 if ((LLRB_RIGHT(a, field) = LLRB_LEFT(b, field))) \
109 LLRB_PARENT(LLRB_RIGHT(a, field), field) = a; \
110 LLRB_LEFT(b, field) = a; \
111 LLRB_COLOR(b, field) = LLRB_COLOR(a, field); \
112 LLRB_COLOR(a, field) = LLRB_RED; \
113 LLRB_PARENT(b, field) = LLRB_PARENT(a, field); \
114 LLRB_PARENT(a, field) = b; \
117static inline void name##_LLRB_ROTR(struct type **pivot) { \
118 struct type *b = *pivot; \
119 struct type *a = LLRB_LEFT(b, field); \
120 if ((LLRB_LEFT(b, field) = LLRB_RIGHT(a, field))) \
121 LLRB_PARENT(LLRB_LEFT(b, field), field) = b; \
122 LLRB_RIGHT(a, field) = b; \
123 LLRB_COLOR(a, field) = LLRB_COLOR(b, field); \
124 LLRB_COLOR(b, field) = LLRB_RED; \
125 LLRB_PARENT(a, field) = LLRB_PARENT(b, field); \
126 LLRB_PARENT(b, field) = a; \
129static inline void name##_LLRB_FLIP(struct type *root) { \
130 LLRB_COLOR(root, field) = !LLRB_COLOR(root, field); \
131 LLRB_COLOR(LLRB_LEFT(root, field), field) = !LLRB_COLOR(LLRB_LEFT(root, field), field); \
132 LLRB_COLOR(LLRB_RIGHT(root, field), field) = !LLRB_COLOR(LLRB_RIGHT(root, field), field); \
134static inline void name##_LLRB_FIXUP(struct type **root) { \
135 if (LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field)) \
136 name##_LLRB_ROTL(root); \
137 if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
138 name##_LLRB_ROTR(root); \
139 if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_RIGHT(*root, field), field)) \
140 name##_LLRB_FLIP(*root); \
142attr struct type *name##_LLRB_INSERT(struct name *head, struct type *elm) { \
143 struct type **root = &LLRB_ROOT(head); \
144 struct type *parent = 0; \
146 int comp = (cmp)((elm), (*root)); \
149 root = &LLRB_LEFT(*root, field); \
151 root = &LLRB_RIGHT(*root, field); \
155 LLRB_LEFT((elm), field) = 0; \
156 LLRB_RIGHT((elm), field) = 0; \
157 LLRB_COLOR((elm), field) = LLRB_RED; \
158 LLRB_PARENT((elm), field) = parent; \
160 while (parent && (LLRB_ISRED(LLRB_LEFT(parent, field), field) || LLRB_ISRED(LLRB_RIGHT(parent, field), field))) { \
161 root = LLRB_EDGE(head, parent, field); \
162 parent = LLRB_PARENT(parent, field); \
163 name##_LLRB_FIXUP(root); \
165 LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
168static inline void name##_LLRB_MOVL(struct type **pivot) { \
169 name##_LLRB_FLIP(*pivot); \
170 if (LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*pivot, field), field), field)) { \
171 name##_LLRB_ROTR(&LLRB_RIGHT(*pivot, field)); \
172 name##_LLRB_ROTL(pivot); \
173 name##_LLRB_FLIP(*pivot); \
176static inline void name##_LLRB_MOVR(struct type **pivot) { \
177 name##_LLRB_FLIP(*pivot); \
178 if (LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) { \
179 name##_LLRB_ROTR(pivot); \
180 name##_LLRB_FLIP(*pivot); \
183static inline struct type *name##_DELETEMIN(struct name *head, struct type **root) { \
184 struct type **pivot = root, *deleted, *parent; \
185 while (LLRB_LEFT(*pivot, field)) { \
186 if (!LLRB_ISRED(LLRB_LEFT(*pivot, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) \
187 name##_LLRB_MOVL(pivot); \
188 pivot = &LLRB_LEFT(*pivot, field); \
191 parent = LLRB_PARENT(*pivot, field); \
193 while (root != pivot) { \
194 pivot = LLRB_EDGE(head, parent, field); \
195 parent = LLRB_PARENT(parent, field); \
196 name##_LLRB_FIXUP(pivot); \
200attr struct type *name##_LLRB_DELETE(struct name *head, struct type *elm) { \
201 struct type **root = &LLRB_ROOT(head), *parent = 0, *deleted = 0; \
204 parent = LLRB_PARENT(*root, field); \
205 comp = (cmp)(elm, *root); \
207 if (LLRB_LEFT(*root, field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
208 name##_LLRB_MOVL(root); \
209 root = &LLRB_LEFT(*root, field); \
211 if (LLRB_ISRED(LLRB_LEFT(*root, field), field)) { \
212 name##_LLRB_ROTR(root); \
213 comp = (cmp)(elm, *root); \
215 if (!comp && !LLRB_RIGHT(*root, field)) { \
220 if (LLRB_RIGHT(*root, field) && !LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*root, field), field), field)) { \
221 name##_LLRB_MOVR(root); \
222 comp = (cmp)(elm, *root); \
225 struct type *orphan = name##_DELETEMIN(head, &LLRB_RIGHT(*root, field)); \
226 LLRB_COLOR(orphan, field) = LLRB_COLOR(*root, field); \
227 LLRB_PARENT(orphan, field) = LLRB_PARENT(*root, field); \
228 if ((LLRB_RIGHT(orphan, field) = LLRB_RIGHT(*root, field))) \
229 LLRB_PARENT(LLRB_RIGHT(orphan, field), field) = orphan; \
230 if ((LLRB_LEFT(orphan, field) = LLRB_LEFT(*root, field))) \
231 LLRB_PARENT(LLRB_LEFT(orphan, field), field) = orphan; \
237 root = &LLRB_RIGHT(*root, field); \
241 root = LLRB_EDGE(head, parent, field); \
242 parent = LLRB_PARENT(parent, field); \
243 name##_LLRB_FIXUP(root); \
245 if (LLRB_ROOT(head)) \
246 LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
249attr struct type *name##_LLRB_FIND(struct name *head, struct type *key) { \
250 struct type *elm = LLRB_ROOT(head); \
252 int comp = (cmp)(key, elm); \
254 elm = LLRB_LEFT(elm, field); \
256 elm = LLRB_RIGHT(elm, field); \
262attr struct type *name##_LLRB_MIN(struct type *elm) { \
263 while (elm && LLRB_LEFT(elm, field)) \
264 elm = LLRB_LEFT(elm, field); \
267attr struct type *name##_LLRB_MAX(struct type *elm) { \
268 while (elm && LLRB_RIGHT(elm, field)) \
269 elm = LLRB_RIGHT(elm, field); \
272attr struct type *name##_LLRB_NEXT(struct type *elm) { \
273 if (LLRB_RIGHT(elm, field)) { \
274 return name##_LLRB_MIN(LLRB_RIGHT(elm, field)); \
275 } else if (LLRB_PARENT(elm, field)) { \
276 if (elm == LLRB_LEFT(LLRB_PARENT(elm, field), field)) \
277 return LLRB_PARENT(elm, field); \
278 while (LLRB_PARENT(elm, field) && elm == LLRB_RIGHT(LLRB_PARENT(elm, field), field)) \
279 elm = LLRB_PARENT(elm, field); \
280 return LLRB_PARENT(elm, field); \
284#define LLRB_INSERT(name, head, elm) name##_LLRB_INSERT((head), (elm))
285#define LLRB_DELETE(name, head, elm) name##_LLRB_DELETE((head), (elm))
286#define LLRB_REMOVE(name, head, elm) name##_LLRB_DELETE((head), (elm))
287#define LLRB_FIND(name, head, elm) name##_LLRB_FIND((head), (elm))
288#define LLRB_MIN(name, head) name##_LLRB_MIN(LLRB_ROOT((head)))
289#define LLRB_MAX(name, head) name##_LLRB_MAX(LLRB_ROOT((head)))
290#define LLRB_NEXT(name, head, elm) name##_LLRB_NEXT((elm))
292#define LLRB_FOREACH(elm, name, head) \
293for ((elm) = LLRB_MIN(name, head); (elm); (elm) = name##_LLRB_NEXT((elm)))
319 if (a->expires < b->expires) {
321 }
else if (a->expires > b->expires) {
332LLRB_GENERATE_STATIC(tree,
rbtimeout, rbe, timeoutcmp)
334static void *init(
struct timeout *
timeout,
size_t count,
int verbose) {
338 T = malloc(
sizeof *
T);
342 for (i = 0; i < count; i++) {
352static void add(
void *ctx,
struct timeout *_to, timeout_t expires) {
357 LLRB_REMOVE(tree, &
T->tree, to);
359 to->expires =
T->curtime + expires;
360 LLRB_INSERT(tree, &
T->tree, to);
365static void del(
void *ctx,
struct timeout *_to) {
369 LLRB_REMOVE(tree, &
T->tree, to);
375static struct timeout *get(
void *ctx) {
379 if ((to = LLRB_MIN(tree, &
T->tree)) && to->expires <=
T->curtime) {
380 LLRB_REMOVE(tree, &
T->tree, to);
391static void update(
void *ctx, timeout_t ts) {
397static void check(
void *ctx) {
402static int empty(
void *ctx) {
405 return LLRB_EMPTY(&
T->tree);
409static void destroy(
void *ctx) {