Line data Source code
1 : // SPDX-License-Identifier: ISC AND BSD-2-Clause
2 : /* $OpenBSD: tree.h,v 1.14 2015/05/25 03:07:49 deraadt Exp $ */
3 : /*
4 : * Copyright 2002 Niels Provos <provos@citi.umich.edu>
5 : */
6 :
7 : #ifndef _SYS_TREE_H_
8 : #define _SYS_TREE_H_
9 :
10 : #ifdef __cplusplus
11 : extern "C" {
12 : #endif
13 :
14 : /*
15 : * This file defines data structures for different types of trees:
16 : * splay trees and red-black trees.
17 : *
18 : * A splay tree is a self-organizing data structure. Every operation
19 : * on the tree causes a splay to happen. The splay moves the requested
20 : * node to the root of the tree and partly rebalances it.
21 : *
22 : * This has the benefit that request locality causes faster lookups as
23 : * the requested nodes move to the top of the tree. On the other hand,
24 : * every lookup causes memory writes.
25 : *
26 : * The Balance Theorem bounds the total access time for m operations
27 : * and n inserts on an initially empty tree as O((m + n)lg n). The
28 : * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
29 : *
30 : * A red-black tree is a binary search tree with the node color as an
31 : * extra attribute. It fulfills a set of conditions:
32 : * - every search path from the root to a leaf consists of the
33 : * same number of black nodes,
34 : * - each red node (except for the root) has a black parent,
35 : * - each leaf node is black.
36 : *
37 : * Every operation on a red-black tree is bounded as O(lg n).
38 : * The maximum height of a red-black tree is 2lg (n+1).
39 : */
40 :
41 : #define SPLAY_HEAD(name, type) \
42 : struct name { \
43 : struct type *sph_root; /* root of the tree */ \
44 : }
45 :
46 : #define SPLAY_INITIALIZER(root) \
47 : { \
48 : NULL \
49 : }
50 :
51 : #define SPLAY_INIT(root) \
52 : do { \
53 : (root)->sph_root = NULL; \
54 : } while (0)
55 :
56 : #define SPLAY_ENTRY(type) \
57 : struct { \
58 : struct type *spe_left; /* left element */ \
59 : struct type *spe_right; /* right element */ \
60 : }
61 :
62 : #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
63 : #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
64 : #define SPLAY_ROOT(head) (head)->sph_root
65 : #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
66 :
67 : /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
68 : #define SPLAY_ROTATE_RIGHT(head, tmp, field) \
69 : do { \
70 : SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
71 : SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
72 : (head)->sph_root = tmp; \
73 : } while (0)
74 :
75 : #define SPLAY_ROTATE_LEFT(head, tmp, field) \
76 : do { \
77 : SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
78 : SPLAY_LEFT(tmp, field) = (head)->sph_root; \
79 : (head)->sph_root = tmp; \
80 : } while (0)
81 :
82 : #define SPLAY_LINKLEFT(head, tmp, field) \
83 : do { \
84 : SPLAY_LEFT(tmp, field) = (head)->sph_root; \
85 : tmp = (head)->sph_root; \
86 : (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
87 : } while (0)
88 :
89 : #define SPLAY_LINKRIGHT(head, tmp, field) \
90 : do { \
91 : SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
92 : tmp = (head)->sph_root; \
93 : (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
94 : } while (0)
95 :
96 : #define SPLAY_ASSEMBLE(head, node, left, right, field) \
97 : do { \
98 : SPLAY_RIGHT(left, field) = \
99 : SPLAY_LEFT((head)->sph_root, field); \
100 : SPLAY_LEFT(right, field) = \
101 : SPLAY_RIGHT((head)->sph_root, field); \
102 : SPLAY_LEFT((head)->sph_root, field) = \
103 : SPLAY_RIGHT(node, field); \
104 : SPLAY_RIGHT((head)->sph_root, field) = \
105 : SPLAY_LEFT(node, field); \
106 : } while (0)
107 :
108 : /* Generates prototypes and inline functions */
109 :
110 : #define SPLAY_PROTOTYPE(name, type, field, cmp) \
111 : void name##_SPLAY(struct name *, struct type *); \
112 : void name##_SPLAY_MINMAX(struct name *, int); \
113 : struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
114 : struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
115 : \
116 : /* Finds the node with the same key as elm */ \
117 : static __inline struct type *name##_SPLAY_FIND(struct name *head, \
118 : struct type *elm) \
119 : { \
120 : if (SPLAY_EMPTY(head)) \
121 : return (NULL); \
122 : name##_SPLAY(head, elm); \
123 : if ((cmp)(elm, (head)->sph_root) == 0) \
124 : return (head->sph_root); \
125 : return (NULL); \
126 : } \
127 : \
128 : static __inline struct type *name##_SPLAY_NEXT(struct name *head, \
129 : struct type *elm) \
130 : { \
131 : name##_SPLAY(head, elm); \
132 : if (SPLAY_RIGHT(elm, field) != NULL) { \
133 : elm = SPLAY_RIGHT(elm, field); \
134 : while (SPLAY_LEFT(elm, field) != NULL) { \
135 : elm = SPLAY_LEFT(elm, field); \
136 : } \
137 : } else \
138 : elm = NULL; \
139 : return (elm); \
140 : } \
141 : \
142 : static __inline struct type *name##_SPLAY_MIN_MAX(struct name *head, \
143 : int val) \
144 : { \
145 : name##_SPLAY_MINMAX(head, val); \
146 : return (SPLAY_ROOT(head)); \
147 : }
148 :
149 : /* Main splay operation.
150 : * Moves node close to the key of elm to top
151 : */
152 : #define SPLAY_GENERATE(name, type, field, cmp) \
153 : struct type *name##_SPLAY_INSERT(struct name *head, struct type *elm) \
154 : { \
155 : if (SPLAY_EMPTY(head)) { \
156 : SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = \
157 : NULL; \
158 : } else { \
159 : int __comp; \
160 : name##_SPLAY(head, elm); \
161 : __comp = (cmp)(elm, (head)->sph_root); \
162 : if (__comp < 0) { \
163 : SPLAY_LEFT(elm, field) = \
164 : SPLAY_LEFT((head)->sph_root, field); \
165 : SPLAY_RIGHT(elm, field) = (head)->sph_root; \
166 : SPLAY_LEFT((head)->sph_root, field) = NULL; \
167 : } else if (__comp > 0) { \
168 : SPLAY_RIGHT(elm, field) = \
169 : SPLAY_RIGHT((head)->sph_root, field); \
170 : SPLAY_LEFT(elm, field) = (head)->sph_root; \
171 : SPLAY_RIGHT((head)->sph_root, field) = NULL; \
172 : } else \
173 : return ((head)->sph_root); \
174 : } \
175 : (head)->sph_root = (elm); \
176 : return (NULL); \
177 : } \
178 : \
179 : struct type *name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
180 : { \
181 : struct type *__tmp; \
182 : if (SPLAY_EMPTY(head)) \
183 : return (NULL); \
184 : name##_SPLAY(head, elm); \
185 : if ((cmp)(elm, (head)->sph_root) == 0) { \
186 : if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
187 : (head)->sph_root = \
188 : SPLAY_RIGHT((head)->sph_root, field); \
189 : } else { \
190 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
191 : (head)->sph_root = \
192 : SPLAY_LEFT((head)->sph_root, field); \
193 : name##_SPLAY(head, elm); \
194 : SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
195 : } \
196 : return (elm); \
197 : } \
198 : return (NULL); \
199 : } \
200 : \
201 : void name##_SPLAY(struct name *head, struct type *elm) \
202 : { \
203 : struct type __node, *__left, *__right, *__tmp; \
204 : int __comp; \
205 : \
206 : SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \
207 : NULL; \
208 : __left = __right = &__node; \
209 : \
210 : while ((__comp = (cmp)(elm, (head)->sph_root))) { \
211 : if (__comp < 0) { \
212 : __tmp = SPLAY_LEFT((head)->sph_root, field); \
213 : if (__tmp == NULL) \
214 : break; \
215 : if ((cmp)(elm, __tmp) < 0) { \
216 : SPLAY_ROTATE_RIGHT(head, __tmp, \
217 : field); \
218 : if (SPLAY_LEFT((head)->sph_root, \
219 : field) \
220 : == NULL) \
221 : break; \
222 : } \
223 : SPLAY_LINKLEFT(head, __right, field); \
224 : } else if (__comp > 0) { \
225 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
226 : if (__tmp == NULL) \
227 : break; \
228 : if ((cmp)(elm, __tmp) > 0) { \
229 : SPLAY_ROTATE_LEFT(head, __tmp, field); \
230 : if (SPLAY_RIGHT((head)->sph_root, \
231 : field) \
232 : == NULL) \
233 : break; \
234 : } \
235 : SPLAY_LINKRIGHT(head, __left, field); \
236 : } \
237 : } \
238 : SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
239 : } \
240 : \
241 : /* Splay with either the minimum or the maximum element \
242 : * Used to find minimum or maximum element in tree. \
243 : */ \
244 : void name##_SPLAY_MINMAX(struct name *head, int __comp) \
245 : { \
246 : struct type __node, *__left, *__right, *__tmp; \
247 : \
248 : SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \
249 : NULL; \
250 : __left = __right = &__node; \
251 : \
252 : while (1) { \
253 : if (__comp < 0) { \
254 : __tmp = SPLAY_LEFT((head)->sph_root, field); \
255 : if (__tmp == NULL) \
256 : break; \
257 : if (__comp < 0) { \
258 : SPLAY_ROTATE_RIGHT(head, __tmp, \
259 : field); \
260 : if (SPLAY_LEFT((head)->sph_root, \
261 : field) \
262 : == NULL) \
263 : break; \
264 : } \
265 : SPLAY_LINKLEFT(head, __right, field); \
266 : } else if (__comp > 0) { \
267 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
268 : if (__tmp == NULL) \
269 : break; \
270 : if (__comp > 0) { \
271 : SPLAY_ROTATE_LEFT(head, __tmp, field); \
272 : if (SPLAY_RIGHT((head)->sph_root, \
273 : field) \
274 : == NULL) \
275 : break; \
276 : } \
277 : SPLAY_LINKRIGHT(head, __left, field); \
278 : } \
279 : } \
280 : SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
281 : }
282 :
283 : #define SPLAY_NEGINF -1
284 : #define SPLAY_INF 1
285 :
286 : #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
287 : #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
288 : #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
289 : #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
290 : #define SPLAY_MIN(name, x) \
291 : (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
292 : #define SPLAY_MAX(name, x) \
293 : (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
294 :
295 : #define SPLAY_FOREACH(x, name, head) \
296 : for ((x) = SPLAY_MIN(name, head); (x) != NULL; \
297 : (x) = SPLAY_NEXT(name, head, x))
298 :
299 : /*
300 : * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
301 : */
302 :
303 : #define RB_BLACK 0
304 : #define RB_RED 1
305 :
306 : struct rb_type {
307 : int (*t_compare)(const void *, const void *);
308 : void (*t_augment)(void *);
309 : unsigned int t_offset; /* offset of rb_entry in type */
310 : };
311 :
312 : struct rbt_tree {
313 : struct rb_entry *rbt_root;
314 : };
315 :
316 : struct rb_entry {
317 : struct rb_entry *rbt_parent;
318 : struct rb_entry *rbt_left;
319 : struct rb_entry *rbt_right;
320 : unsigned int rbt_color;
321 : };
322 :
323 : #define RB_HEAD(_name, _type) \
324 : struct _name { \
325 : struct rbt_tree rbh_root; \
326 : }
327 :
328 : #define RB_ENTRY(_type) struct rb_entry
329 :
330 32 : static inline void _rb_init(struct rbt_tree *rbt)
331 : {
332 30 : rbt->rbt_root = NULL;
333 : }
334 :
335 98 : static inline int _rb_empty(const struct rbt_tree *rbt)
336 : {
337 98 : return (rbt->rbt_root == NULL);
338 : }
339 :
340 : void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *);
341 : void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *);
342 : void *_rb_find(const struct rb_type *, const struct rbt_tree *, const void *);
343 : void *_rb_nfind(const struct rb_type *, const struct rbt_tree *, const void *);
344 : void *_rb_root(const struct rb_type *, const struct rbt_tree *);
345 : void *_rb_min(const struct rb_type *, const struct rbt_tree *);
346 : void *_rb_max(const struct rb_type *, const struct rbt_tree *);
347 : void *_rb_next(const struct rb_type *, void *);
348 : void *_rb_prev(const struct rb_type *, void *);
349 : void *_rb_left(const struct rb_type *, void *);
350 : void *_rb_right(const struct rb_type *, void *);
351 : void *_rb_parent(const struct rb_type *, void *);
352 : void _rb_set_left(const struct rb_type *, void *, void *);
353 : void _rb_set_right(const struct rb_type *, void *, void *);
354 : void _rb_set_parent(const struct rb_type *, void *, void *);
355 : void _rb_poison(const struct rb_type *, void *, unsigned long);
356 : int _rb_check(const struct rb_type *, void *, unsigned long);
357 :
358 : #define RB_INITIALIZER(_head) { { NULL } }
359 :
360 : #define RB_PROTOTYPE(_name, _type, _field, _cmp) \
361 : extern const struct rb_type *const _name##_RB_TYPE; \
362 : \
363 : __attribute__((__unused__)) static inline void _name##_RB_INIT( \
364 : struct _name *head) \
365 : { \
366 : _rb_init(&head->rbh_root); \
367 : } \
368 : \
369 : __attribute__((__unused__)) static inline struct _type \
370 : *_name##_RB_INSERT(struct _name *head, struct _type *elm) \
371 : { \
372 : return (struct _type *)_rb_insert(_name##_RB_TYPE, \
373 : &head->rbh_root, elm); \
374 : } \
375 : \
376 : __attribute__((__unused__)) static inline struct _type \
377 : *_name##_RB_REMOVE(struct _name *head, struct _type *elm) \
378 : { \
379 : return (struct _type *)_rb_remove(_name##_RB_TYPE, \
380 : &head->rbh_root, elm); \
381 : } \
382 : \
383 : __attribute__((__unused__)) static inline struct _type \
384 : *_name##_RB_FIND(const struct _name *head, \
385 : const struct _type *key) \
386 : { \
387 : return (struct _type *)_rb_find(_name##_RB_TYPE, \
388 : &head->rbh_root, key); \
389 : } \
390 : \
391 : __attribute__((__unused__)) static inline struct _type \
392 : *_name##_RB_NFIND(const struct _name *head, \
393 : const struct _type *key) \
394 : { \
395 : return (struct _type *)_rb_nfind(_name##_RB_TYPE, \
396 : &head->rbh_root, key); \
397 : } \
398 : \
399 : __attribute__((__unused__)) static inline struct _type \
400 : *_name##_RB_ROOT(const struct _name *head) \
401 : { \
402 : return (struct _type *)_rb_root(_name##_RB_TYPE, \
403 : &head->rbh_root); \
404 : } \
405 : \
406 : __attribute__((__unused__)) static inline int _name##_RB_EMPTY( \
407 : const struct _name *head) \
408 : { \
409 : return _rb_empty(&head->rbh_root); \
410 : } \
411 : \
412 : __attribute__((__unused__)) static inline struct _type \
413 : *_name##_RB_MIN(const struct _name *head) \
414 : { \
415 : return (struct _type *)_rb_min(_name##_RB_TYPE, \
416 : &head->rbh_root); \
417 : } \
418 : \
419 : __attribute__((__unused__)) static inline struct _type \
420 : *_name##_RB_MAX(const struct _name *head) \
421 : { \
422 : return (struct _type *)_rb_max(_name##_RB_TYPE, \
423 : &head->rbh_root); \
424 : } \
425 : \
426 : __attribute__((__unused__)) static inline struct _type \
427 : *_name##_RB_NEXT(struct _type *elm) \
428 : { \
429 : return (struct _type *)_rb_next(_name##_RB_TYPE, elm); \
430 : } \
431 : \
432 : __attribute__((__unused__)) static inline struct _type \
433 : *_name##_RB_PREV(struct _type *elm) \
434 : { \
435 : return (struct _type *)_rb_prev(_name##_RB_TYPE, elm); \
436 : } \
437 : \
438 : __attribute__((__unused__)) static inline struct _type \
439 : *_name##_RB_LEFT(struct _type *elm) \
440 : { \
441 : return (struct _type *)_rb_left(_name##_RB_TYPE, elm); \
442 : } \
443 : \
444 : __attribute__((__unused__)) static inline struct _type \
445 : *_name##_RB_RIGHT(struct _type *elm) \
446 : { \
447 : return (struct _type *)_rb_right(_name##_RB_TYPE, elm); \
448 : } \
449 : \
450 : __attribute__((__unused__)) static inline struct _type \
451 : *_name##_RB_PARENT(struct _type *elm) \
452 : { \
453 : return (struct _type *)_rb_parent(_name##_RB_TYPE, elm); \
454 : } \
455 : \
456 : __attribute__((__unused__)) static inline void _name##_RB_SET_LEFT( \
457 : struct _type *elm, struct _type *left) \
458 : { \
459 : _rb_set_left(_name##_RB_TYPE, elm, left); \
460 : } \
461 : \
462 : __attribute__((__unused__)) static inline void _name##_RB_SET_RIGHT( \
463 : struct _type *elm, struct _type *right) \
464 : { \
465 : _rb_set_right(_name##_RB_TYPE, elm, right); \
466 : } \
467 : \
468 : __attribute__((__unused__)) static inline void _name##_RB_SET_PARENT( \
469 : struct _type *elm, struct _type *parent) \
470 : { \
471 : _rb_set_parent(_name##_RB_TYPE, elm, parent); \
472 : } \
473 : \
474 : __attribute__((__unused__)) static inline void _name##_RB_POISON( \
475 : struct _type *elm, unsigned long poison) \
476 : { \
477 : _rb_poison(_name##_RB_TYPE, elm, poison); \
478 : } \
479 : \
480 : __attribute__((__unused__)) static inline int _name##_RB_CHECK( \
481 : struct _type *elm, unsigned long poison) \
482 : { \
483 : return _rb_check(_name##_RB_TYPE, elm, poison); \
484 : }
485 :
486 : #define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \
487 : static int _name##_RB_COMPARE(const void *lptr, const void *rptr) \
488 : { \
489 : const struct _type *l = lptr, *r = rptr; \
490 : return _cmp(l, r); \
491 : } \
492 : static const struct rb_type _name##_RB_INFO = { \
493 : _name##_RB_COMPARE, _aug, offsetof(struct _type, _field), \
494 : }; \
495 : const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO;
496 :
497 : #define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \
498 : static void _name##_RB_AUGMENT(void *ptr) \
499 : { \
500 : struct _type *p = ptr; \
501 : return _aug(p); \
502 : } \
503 : RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT)
504 :
505 : #define RB_GENERATE(_name, _type, _field, _cmp) \
506 : RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
507 :
508 : #define RB_INIT(_name, _head) _name##_RB_INIT(_head)
509 : #define RB_INSERT(_name, _head, _elm) _name##_RB_INSERT(_head, _elm)
510 : #define RB_REMOVE(_name, _head, _elm) _name##_RB_REMOVE(_head, _elm)
511 : #define RB_FIND(_name, _head, _key) _name##_RB_FIND(_head, _key)
512 : #define RB_NFIND(_name, _head, _key) _name##_RB_NFIND(_head, _key)
513 : #define RB_ROOT(_name, _head) _name##_RB_ROOT(_head)
514 : #define RB_EMPTY(_name, _head) _name##_RB_EMPTY(_head)
515 : #define RB_MIN(_name, _head) _name##_RB_MIN(_head)
516 : #define RB_MAX(_name, _head) _name##_RB_MAX(_head)
517 : #define RB_NEXT(_name, _elm) _name##_RB_NEXT(_elm)
518 : #define RB_PREV(_name, _elm) _name##_RB_PREV(_elm)
519 : #define RB_LEFT(_name, _elm) _name##_RB_LEFT(_elm)
520 : #define RB_RIGHT(_name, _elm) _name##_RB_RIGHT(_elm)
521 : #define RB_PARENT(_name, _elm) _name##_RB_PARENT(_elm)
522 : #define RB_SET_LEFT(_name, _elm, _l) _name##_RB_SET_LEFT(_elm, _l)
523 : #define RB_SET_RIGHT(_name, _elm, _r) _name##_RB_SET_RIGHT(_elm, _r)
524 : #define RB_SET_PARENT(_name, _elm, _p) _name##_RB_SET_PARENT(_elm, _p)
525 : #define RB_POISON(_name, _elm, _p) _name##_RB_POISON(_elm, _p)
526 : #define RB_CHECK(_name, _elm, _p) _name##_RB_CHECK(_elm, _p)
527 :
528 : #define RB_FOREACH(_e, _name, _head) \
529 : for ((_e) = RB_MIN(_name, (_head)); (_e) != NULL; \
530 : (_e) = RB_NEXT(_name, (_e)))
531 :
532 : #define RB_FOREACH_SAFE(_e, _name, _head, _n) \
533 : for ((_e) = RB_MIN(_name, (_head)); \
534 : (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); (_e) = (_n))
535 :
536 : #define RB_FOREACH_REVERSE(_e, _name, _head) \
537 : for ((_e) = RB_MAX(_name, (_head)); (_e) != NULL; \
538 : (_e) = RB_PREV(_name, (_e)))
539 :
540 : #define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \
541 : for ((_e) = RB_MAX(_name, (_head)); \
542 : (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); (_e) = (_n))
543 :
544 : #ifdef __cplusplus
545 : }
546 : #endif
547 :
548 : #endif /* _SYS_TREE_H_ */
|
