summaryrefslogtreecommitdiff
path: root/openbsd-compat/sys-tree.h
diff options
context:
space:
mode:
Diffstat (limited to 'openbsd-compat/sys-tree.h')
-rw-r--r--openbsd-compat/sys-tree.h114
1 files changed, 95 insertions, 19 deletions
diff --git a/openbsd-compat/sys-tree.h b/openbsd-compat/sys-tree.h
index d4949b5e7..7f7546ecd 100644
--- a/openbsd-compat/sys-tree.h
+++ b/openbsd-compat/sys-tree.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: tree.h,v 1.10 2007/10/29 23:49:41 djm Exp $ */ 1/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
2/* 2/*
3 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 3 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4 * All rights reserved. 4 * All rights reserved.
@@ -26,6 +26,11 @@
26 26
27/* OPENBSD ORIGINAL: sys/sys/tree.h */ 27/* OPENBSD ORIGINAL: sys/sys/tree.h */
28 28
29#include "config.h"
30#ifdef NO_ATTRIBUTE_ON_RETURN_TYPE
31# define __attribute__(x)
32#endif
33
29#ifndef _SYS_TREE_H_ 34#ifndef _SYS_TREE_H_
30#define _SYS_TREE_H_ 35#define _SYS_TREE_H_
31 36
@@ -331,7 +336,7 @@ struct { \
331} while (0) 336} while (0)
332 337
333#ifndef RB_AUGMENT 338#ifndef RB_AUGMENT
334#define RB_AUGMENT(x) 339#define RB_AUGMENT(x) do {} while (0)
335#endif 340#endif
336 341
337#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 342#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
@@ -375,21 +380,31 @@ struct { \
375} while (0) 380} while (0)
376 381
377/* Generates prototypes and inline functions */ 382/* Generates prototypes and inline functions */
378#define RB_PROTOTYPE(name, type, field, cmp) \ 383#define RB_PROTOTYPE(name, type, field, cmp) \
379void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 384 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
380void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 385#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
381struct type *name##_RB_REMOVE(struct name *, struct type *); \ 386 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
382struct type *name##_RB_INSERT(struct name *, struct type *); \ 387#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
383struct type *name##_RB_FIND(struct name *, struct type *); \ 388attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
384struct type *name##_RB_NEXT(struct type *); \ 389attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
385struct type *name##_RB_MINMAX(struct name *, int); 390attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
386 391attr struct type *name##_RB_INSERT(struct name *, struct type *); \
392attr struct type *name##_RB_FIND(struct name *, struct type *); \
393attr struct type *name##_RB_NFIND(struct name *, struct type *); \
394attr struct type *name##_RB_NEXT(struct type *); \
395attr struct type *name##_RB_PREV(struct type *); \
396attr struct type *name##_RB_MINMAX(struct name *, int); \
397 \
387 398
388/* Main rb operation. 399/* Main rb operation.
389 * Moves node close to the key of elm to top 400 * Moves node close to the key of elm to top
390 */ 401 */
391#define RB_GENERATE(name, type, field, cmp) \ 402#define RB_GENERATE(name, type, field, cmp) \
392void \ 403 RB_GENERATE_INTERNAL(name, type, field, cmp,)
404#define RB_GENERATE_STATIC(name, type, field, cmp) \
405 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
406#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
407attr void \
393name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 408name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
394{ \ 409{ \
395 struct type *parent, *gparent, *tmp; \ 410 struct type *parent, *gparent, *tmp; \
@@ -433,7 +448,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
433 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 448 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
434} \ 449} \
435 \ 450 \
436void \ 451attr void \
437name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 452name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
438{ \ 453{ \
439 struct type *tmp; \ 454 struct type *tmp; \
@@ -509,7 +524,7 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm)
509 RB_COLOR(elm, field) = RB_BLACK; \ 524 RB_COLOR(elm, field) = RB_BLACK; \
510} \ 525} \
511 \ 526 \
512struct type * \ 527attr struct type * \
513name##_RB_REMOVE(struct name *head, struct type *elm) \ 528name##_RB_REMOVE(struct name *head, struct type *elm) \
514{ \ 529{ \
515 struct type *child, *parent, *old = elm; \ 530 struct type *child, *parent, *old = elm; \
@@ -577,7 +592,7 @@ color: \
577} \ 592} \
578 \ 593 \
579/* Inserts a node into the RB tree */ \ 594/* Inserts a node into the RB tree */ \
580struct type * \ 595attr struct type * \
581name##_RB_INSERT(struct name *head, struct type *elm) \ 596name##_RB_INSERT(struct name *head, struct type *elm) \
582{ \ 597{ \
583 struct type *tmp; \ 598 struct type *tmp; \
@@ -608,7 +623,7 @@ name##_RB_INSERT(struct name *head, struct type *elm) \
608} \ 623} \
609 \ 624 \
610/* Finds the node with the same key as elm */ \ 625/* Finds the node with the same key as elm */ \
611struct type * \ 626attr struct type * \
612name##_RB_FIND(struct name *head, struct type *elm) \ 627name##_RB_FIND(struct name *head, struct type *elm) \
613{ \ 628{ \
614 struct type *tmp = RB_ROOT(head); \ 629 struct type *tmp = RB_ROOT(head); \
@@ -625,7 +640,29 @@ name##_RB_FIND(struct name *head, struct type *elm) \
625 return (NULL); \ 640 return (NULL); \
626} \ 641} \
627 \ 642 \
628struct type * \ 643/* Finds the first node greater than or equal to the search key */ \
644attr struct type * \
645name##_RB_NFIND(struct name *head, struct type *elm) \
646{ \
647 struct type *tmp = RB_ROOT(head); \
648 struct type *res = NULL; \
649 int comp; \
650 while (tmp) { \
651 comp = cmp(elm, tmp); \
652 if (comp < 0) { \
653 res = tmp; \
654 tmp = RB_LEFT(tmp, field); \
655 } \
656 else if (comp > 0) \
657 tmp = RB_RIGHT(tmp, field); \
658 else \
659 return (tmp); \
660 } \
661 return (res); \
662} \
663 \
664/* ARGSUSED */ \
665attr struct type * \
629name##_RB_NEXT(struct type *elm) \ 666name##_RB_NEXT(struct type *elm) \
630{ \ 667{ \
631 if (RB_RIGHT(elm, field)) { \ 668 if (RB_RIGHT(elm, field)) { \
@@ -646,7 +683,29 @@ name##_RB_NEXT(struct type *elm) \
646 return (elm); \ 683 return (elm); \
647} \ 684} \
648 \ 685 \
649struct type * \ 686/* ARGSUSED */ \
687attr struct type * \
688name##_RB_PREV(struct type *elm) \
689{ \
690 if (RB_LEFT(elm, field)) { \
691 elm = RB_LEFT(elm, field); \
692 while (RB_RIGHT(elm, field)) \
693 elm = RB_RIGHT(elm, field); \
694 } else { \
695 if (RB_PARENT(elm, field) && \
696 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
697 elm = RB_PARENT(elm, field); \
698 else { \
699 while (RB_PARENT(elm, field) && \
700 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
701 elm = RB_PARENT(elm, field); \
702 elm = RB_PARENT(elm, field); \
703 } \
704 } \
705 return (elm); \
706} \
707 \
708attr struct type * \
650name##_RB_MINMAX(struct name *head, int val) \ 709name##_RB_MINMAX(struct name *head, int val) \
651{ \ 710{ \
652 struct type *tmp = RB_ROOT(head); \ 711 struct type *tmp = RB_ROOT(head); \
@@ -667,7 +726,9 @@ name##_RB_MINMAX(struct name *head, int val) \
667#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 726#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
668#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 727#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
669#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 728#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
729#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
670#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 730#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
731#define RB_PREV(name, x, y) name##_RB_PREV(y)
671#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 732#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
672#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 733#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
673 734
@@ -676,4 +737,19 @@ name##_RB_MINMAX(struct name *head, int val) \
676 (x) != NULL; \ 737 (x) != NULL; \
677 (x) = name##_RB_NEXT(x)) 738 (x) = name##_RB_NEXT(x))
678 739
740#define RB_FOREACH_SAFE(x, name, head, y) \
741 for ((x) = RB_MIN(name, head); \
742 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
743 (x) = (y))
744
745#define RB_FOREACH_REVERSE(x, name, head) \
746 for ((x) = RB_MAX(name, head); \
747 (x) != NULL; \
748 (x) = name##_RB_PREV(x))
749
750#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
751 for ((x) = RB_MAX(name, head); \
752 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
753 (x) = (y))
754
679#endif /* _SYS_TREE_H_ */ 755#endif /* _SYS_TREE_H_ */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-05 22:26:08 +0000