projects / darkstat-debian / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Use the host compiler for build tool c-ify.
[darkstat-debian] / tree.h
1 /* This is a cut down version of NetBSD's /usr/include/sys/tree.h */
2
3 /* $NetBSD: tree.h,v 1.20 2013/09/14 13:20:45 joerg Exp $ */
4 /* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
5 /*
6 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 #ifndef _SYS_TREE_H_
31 #define _SYS_TREE_H_
32
33 #include "cdefs.h"
34
35 /* Macros that define a red-black tree */
36 #define RB_HEAD(name, type) \
37 struct name { \
38 struct type *rbh_root; /* root of the tree */ \
39 }
40
41 #define RB_INITIALIZER(root) \
42 { NULL }
43
44 #define RB_INIT(root) do { \
45 (root)->rbh_root = NULL; \
46 } while (/*CONSTCOND*/ 0)
47
48 #define RB_BLACK 0
49 #define RB_RED 1
50 #define RB_ENTRY(type) \
51 struct { \
52 struct type *rbe_left; /* left element */ \
53 struct type *rbe_right; /* right element */ \
54 struct type *rbe_parent; /* parent element */ \
55 int rbe_color; /* node color */ \
56 }
57
58 #define RB_LEFT(elm, field) (elm)->field.rbe_left
59 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
60 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
61 #define RB_COLOR(elm, field) (elm)->field.rbe_color
62 #define RB_ROOT(head) (head)->rbh_root
63 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
64
65 #define RB_SET(elm, parent, field) do { \
66 RB_PARENT(elm, field) = parent; \
67 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
68 RB_COLOR(elm, field) = RB_RED; \
69 } while (/*CONSTCOND*/ 0)
70
71 #define RB_SET_BLACKRED(black, red, field) do { \
72 RB_COLOR(black, field) = RB_BLACK; \
73 RB_COLOR(red, field) = RB_RED; \
74 } while (/*CONSTCOND*/ 0)
75
76 #ifndef RB_AUGMENT
77 #define RB_AUGMENT(x) do {} while (/*CONSTCOND*/ 0)
78 #endif
79
80 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
81 (tmp) = RB_RIGHT(elm, field); \
82 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
83 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
84 } \
85 RB_AUGMENT(elm); \
86 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
87 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
88 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
89 else \
90 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
91 } else \
92 (head)->rbh_root = (tmp); \
93 RB_LEFT(tmp, field) = (elm); \
94 RB_PARENT(elm, field) = (tmp); \
95 RB_AUGMENT(tmp); \
96 if ((RB_PARENT(tmp, field))) \
97 RB_AUGMENT(RB_PARENT(tmp, field)); \
98 } while (/*CONSTCOND*/ 0)
99
100 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
101 (tmp) = RB_LEFT(elm, field); \
102 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
103 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
104 } \
105 RB_AUGMENT(elm); \
106 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
107 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
108 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
109 else \
110 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
111 } else \
112 (head)->rbh_root = (tmp); \
113 RB_RIGHT(tmp, field) = (elm); \
114 RB_PARENT(elm, field) = (tmp); \
115 RB_AUGMENT(tmp); \
116 if ((RB_PARENT(tmp, field))) \
117 RB_AUGMENT(RB_PARENT(tmp, field)); \
118 } while (/*CONSTCOND*/ 0)
119
120 /* Generates prototypes and inline functions */
121 #define RB_PROTOTYPE(name, type, field, cmp) \
122 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
123 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
124 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, _unused_ static)
125 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
126 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
127 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
128 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
129 attr struct type *name##_RB_INSERT(struct name *, struct type *); \
130 attr struct type *name##_RB_FIND(struct name *, struct type *); \
131 attr struct type *name##_RB_NFIND(struct name *, struct type *); \
132 attr struct type *name##_RB_NEXT(struct type *); \
133 attr struct type *name##_RB_PREV(struct type *); \
134 attr struct type *name##_RB_MINMAX(struct name *, int); \
135 \
136
137 #include <assert.h>
138
139 /* Main rb operation.
140 * Moves node close to the key of elm to top
141 */
142 #define RB_GENERATE(name, type, field, cmp) \
143 RB_GENERATE_INTERNAL(name, type, field, cmp,)
144 #define RB_GENERATE_STATIC(name, type, field, cmp) \
145 RB_GENERATE_INTERNAL(name, type, field, cmp, _unused_ static)
146 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
147 attr void \
148 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
149 { \
150 struct type *parent, *gparent, *tmp; \
151 while ((parent = RB_PARENT(elm, field)) != NULL && \
152 RB_COLOR(parent, field) == RB_RED) { \
153 gparent = RB_PARENT(parent, field); \
154 assert(gparent != NULL); \
155 if (parent == RB_LEFT(gparent, field)) { \
156 tmp = RB_RIGHT(gparent, field); \
157 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
158 RB_COLOR(tmp, field) = RB_BLACK; \
159 RB_SET_BLACKRED(parent, gparent, field);\
160 elm = gparent; \
161 continue; \
162 } \
163 if (RB_RIGHT(parent, field) == elm) { \
164 RB_ROTATE_LEFT(head, parent, tmp, field);\
165 tmp = parent; \
166 parent = elm; \
167 elm = tmp; \
168 } \
169 RB_SET_BLACKRED(parent, gparent, field); \
170 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
171 } else { \
172 tmp = RB_LEFT(gparent, field); \
173 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
174 RB_COLOR(tmp, field) = RB_BLACK; \
175 RB_SET_BLACKRED(parent, gparent, field);\
176 elm = gparent; \
177 continue; \
178 } \
179 if (RB_LEFT(parent, field) == elm) { \
180 RB_ROTATE_RIGHT(head, parent, tmp, field);\
181 tmp = parent; \
182 parent = elm; \
183 elm = tmp; \
184 } \
185 RB_SET_BLACKRED(parent, gparent, field); \
186 RB_ROTATE_LEFT(head, gparent, tmp, field); \
187 } \
188 } \
189 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
190 } \
191 \
192 attr void \
193 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
194 { \
195 struct type *tmp; \
196 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
197 elm != RB_ROOT(head)) { \
198 if (RB_LEFT(parent, field) == elm) { \
199 tmp = RB_RIGHT(parent, field); \
200 if (RB_COLOR(tmp, field) == RB_RED) { \
201 RB_SET_BLACKRED(tmp, parent, field); \
202 RB_ROTATE_LEFT(head, parent, tmp, field);\
203 tmp = RB_RIGHT(parent, field); \
204 } \
205 assert(tmp != NULL); \
206 if ((RB_LEFT(tmp, field) == NULL || \
207 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
208 (RB_RIGHT(tmp, field) == NULL || \
209 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
210 RB_COLOR(tmp, field) = RB_RED; \
211 elm = parent; \
212 parent = RB_PARENT(elm, field); \
213 } else { \
214 if (RB_RIGHT(tmp, field) == NULL || \
215 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
216 struct type *oleft; \
217 if ((oleft = RB_LEFT(tmp, field)) \
218 != NULL) \
219 RB_COLOR(oleft, field) = RB_BLACK;\
220 RB_COLOR(tmp, field) = RB_RED; \
221 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
222 tmp = RB_RIGHT(parent, field); \
223 } \
224 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
225 RB_COLOR(parent, field) = RB_BLACK; \
226 if (RB_RIGHT(tmp, field)) \
227 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
228 RB_ROTATE_LEFT(head, parent, tmp, field);\
229 elm = RB_ROOT(head); \
230 break; \
231 } \
232 } else { \
233 tmp = RB_LEFT(parent, field); \
234 if (RB_COLOR(tmp, field) == RB_RED) { \
235 RB_SET_BLACKRED(tmp, parent, field); \
236 RB_ROTATE_RIGHT(head, parent, tmp, field);\
237 tmp = RB_LEFT(parent, field); \
238 } \
239 assert(tmp != NULL); \
240 if ((RB_LEFT(tmp, field) == NULL || \
241 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
242 (RB_RIGHT(tmp, field) == NULL || \
243 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
244 RB_COLOR(tmp, field) = RB_RED; \
245 elm = parent; \
246 parent = RB_PARENT(elm, field); \
247 } else { \
248 if (RB_LEFT(tmp, field) == NULL || \
249 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
250 struct type *oright; \
251 if ((oright = RB_RIGHT(tmp, field)) \
252 != NULL) \
253 RB_COLOR(oright, field) = RB_BLACK;\
254 RB_COLOR(tmp, field) = RB_RED; \
255 RB_ROTATE_LEFT(head, tmp, oright, field);\
256 tmp = RB_LEFT(parent, field); \
257 } \
258 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
259 RB_COLOR(parent, field) = RB_BLACK; \
260 if (RB_LEFT(tmp, field)) \
261 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
262 RB_ROTATE_RIGHT(head, parent, tmp, field);\
263 elm = RB_ROOT(head); \
264 break; \
265 } \
266 } \
267 } \
268 if (elm) \
269 RB_COLOR(elm, field) = RB_BLACK; \
270 } \
271 \
272 attr struct type * \
273 name##_RB_REMOVE(struct name *head, struct type *elm) \
274 { \
275 struct type *child, *parent, *old = elm; \
276 int color; \
277 if (RB_LEFT(elm, field) == NULL) \
278 child = RB_RIGHT(elm, field); \
279 else if (RB_RIGHT(elm, field) == NULL) \
280 child = RB_LEFT(elm, field); \
281 else { \
282 struct type *left; \
283 elm = RB_RIGHT(elm, field); \
284 while ((left = RB_LEFT(elm, field)) != NULL) \
285 elm = left; \
286 child = RB_RIGHT(elm, field); \
287 parent = RB_PARENT(elm, field); \
288 color = RB_COLOR(elm, field); \
289 if (child) \
290 RB_PARENT(child, field) = parent; \
291 if (parent) { \
292 if (RB_LEFT(parent, field) == elm) \
293 RB_LEFT(parent, field) = child; \
294 else \
295 RB_RIGHT(parent, field) = child; \
296 RB_AUGMENT(parent); \
297 } else \
298 RB_ROOT(head) = child; \
299 if (RB_PARENT(elm, field) == old) \
300 parent = elm; \
301 (elm)->field = (old)->field; \
302 if (RB_PARENT(old, field)) { \
303 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
304 RB_LEFT(RB_PARENT(old, field), field) = elm;\
305 else \
306 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
307 RB_AUGMENT(RB_PARENT(old, field)); \
308 } else \
309 RB_ROOT(head) = elm; \
310 assert(RB_LEFT(old, field) != NULL); \
311 RB_PARENT(RB_LEFT(old, field), field) = elm; \
312 if (RB_RIGHT(old, field)) \
313 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
314 if (parent) { \
315 left = parent; \
316 do { \
317 RB_AUGMENT(left); \
318 } while ((left = RB_PARENT(left, field)) != NULL); \
319 } \
320 goto color; \
321 } \
322 parent = RB_PARENT(elm, field); \
323 color = RB_COLOR(elm, field); \
324 if (child) \
325 RB_PARENT(child, field) = parent; \
326 if (parent) { \
327 if (RB_LEFT(parent, field) == elm) \
328 RB_LEFT(parent, field) = child; \
329 else \
330 RB_RIGHT(parent, field) = child; \
331 RB_AUGMENT(parent); \
332 } else \
333 RB_ROOT(head) = child; \
334 color: \
335 if (color == RB_BLACK) \
336 name##_RB_REMOVE_COLOR(head, parent, child); \
337 return (old); \
338 } \
339 \
340 /* Inserts a node into the RB tree */ \
341 attr struct type * \
342 name##_RB_INSERT(struct name *head, struct type *elm) \
343 { \
344 struct type *tmp; \
345 struct type *parent = NULL; \
346 int comp = 0; \
347 tmp = RB_ROOT(head); \
348 while (tmp) { \
349 parent = tmp; \
350 comp = (cmp)(elm, parent); \
351 if (comp < 0) \
352 tmp = RB_LEFT(tmp, field); \
353 else if (comp > 0) \
354 tmp = RB_RIGHT(tmp, field); \
355 else \
356 return (tmp); \
357 } \
358 RB_SET(elm, parent, field); \
359 if (parent != NULL) { \
360 if (comp < 0) \
361 RB_LEFT(parent, field) = elm; \
362 else \
363 RB_RIGHT(parent, field) = elm; \
364 RB_AUGMENT(parent); \
365 } else \
366 RB_ROOT(head) = elm; \
367 name##_RB_INSERT_COLOR(head, elm); \
368 return (NULL); \
369 } \
370 \
371 /* Finds the node with the same key as elm */ \
372 attr struct type * \
373 name##_RB_FIND(struct name *head, struct type *elm) \
374 { \
375 struct type *tmp = RB_ROOT(head); \
376 int comp; \
377 while (tmp) { \
378 comp = cmp(elm, tmp); \
379 if (comp < 0) \
380 tmp = RB_LEFT(tmp, field); \
381 else if (comp > 0) \
382 tmp = RB_RIGHT(tmp, field); \
383 else \
384 return (tmp); \
385 } \
386 return (NULL); \
387 } \
388 \
389 /* Finds the first node greater than or equal to the search key */ \
390 attr struct type * \
391 name##_RB_NFIND(struct name *head, struct type *elm) \
392 { \
393 struct type *tmp = RB_ROOT(head); \
394 struct type *res = NULL; \
395 int comp; \
396 while (tmp) { \
397 comp = cmp(elm, tmp); \
398 if (comp < 0) { \
399 res = tmp; \
400 tmp = RB_LEFT(tmp, field); \
401 } \
402 else if (comp > 0) \
403 tmp = RB_RIGHT(tmp, field); \
404 else \
405 return (tmp); \
406 } \
407 return (res); \
408 } \
409 \
410 /* ARGSUSED */ \
411 attr struct type * \
412 name##_RB_NEXT(struct type *elm) \
413 { \
414 if (RB_RIGHT(elm, field)) { \
415 elm = RB_RIGHT(elm, field); \
416 while (RB_LEFT(elm, field)) \
417 elm = RB_LEFT(elm, field); \
418 } else { \
419 if (RB_PARENT(elm, field) && \
420 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
421 elm = RB_PARENT(elm, field); \
422 else { \
423 while (RB_PARENT(elm, field) && \
424 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
425 elm = RB_PARENT(elm, field); \
426 elm = RB_PARENT(elm, field); \
427 } \
428 } \
429 return (elm); \
430 } \
431 \
432 /* ARGSUSED */ \
433 attr struct type * \
434 name##_RB_PREV(struct type *elm) \
435 { \
436 if (RB_LEFT(elm, field)) { \
437 elm = RB_LEFT(elm, field); \
438 while (RB_RIGHT(elm, field)) \
439 elm = RB_RIGHT(elm, field); \
440 } else { \
441 if (RB_PARENT(elm, field) && \
442 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
443 elm = RB_PARENT(elm, field); \
444 else { \
445 while (RB_PARENT(elm, field) && \
446 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
447 elm = RB_PARENT(elm, field); \
448 elm = RB_PARENT(elm, field); \
449 } \
450 } \
451 return (elm); \
452 } \
453 \
454 attr struct type * \
455 name##_RB_MINMAX(struct name *head, int val) \
456 { \
457 struct type *tmp = RB_ROOT(head); \
458 struct type *parent = NULL; \
459 while (tmp) { \
460 parent = tmp; \
461 if (val < 0) \
462 tmp = RB_LEFT(tmp, field); \
463 else \
464 tmp = RB_RIGHT(tmp, field); \
465 } \
466 return (parent); \
467 }
468
469 #define RB_NEGINF -1
470 #define RB_INF 1
471
472 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
473 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
474 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
475 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
476 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
477 #define RB_PREV(name, x, y) name##_RB_PREV(y)
478 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
479 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
480
481 #define RB_FOREACH(x, name, head) \
482 for ((x) = RB_MIN(name, head); \
483 (x) != NULL; \
484 (x) = name##_RB_NEXT(x))
485
486 #define RB_FOREACH_FROM(x, name, y) \
487 for ((x) = (y); \
488 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
489 (x) = (y))
490
491 #define RB_FOREACH_SAFE(x, name, head, y) \
492 for ((x) = RB_MIN(name, head); \
493 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
494 (x) = (y))
495
496 #define RB_FOREACH_REVERSE(x, name, head) \
497 for ((x) = RB_MAX(name, head); \
498 (x) != NULL; \
499 (x) = name##_RB_PREV(x))
500
501 #define RB_FOREACH_REVERSE_FROM(x, name, y) \
502 for ((x) = (y); \
503 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
504 (x) = (y))
505
506 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
507 for ((x) = RB_MAX(name, head); \
508 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
509 (x) = (y))
510
511 #endif /* _SYS_TREE_H_ */
Debian package for darkstat