diff options
Diffstat (limited to 'openbsd-compat')
-rw-r--r-- | openbsd-compat/sys-tree.h | 109 |
1 files changed, 90 insertions, 19 deletions
diff --git a/openbsd-compat/sys-tree.h b/openbsd-compat/sys-tree.h index d4949b5e7..058fa3b23 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. |
@@ -331,7 +331,7 @@ struct { \ | |||
331 | } while (0) | 331 | } while (0) |
332 | 332 | ||
333 | #ifndef RB_AUGMENT | 333 | #ifndef RB_AUGMENT |
334 | #define RB_AUGMENT(x) | 334 | #define RB_AUGMENT(x) do {} while (0) |
335 | #endif | 335 | #endif |
336 | 336 | ||
337 | #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ | 337 | #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ |
@@ -375,21 +375,31 @@ struct { \ | |||
375 | } while (0) | 375 | } while (0) |
376 | 376 | ||
377 | /* Generates prototypes and inline functions */ | 377 | /* Generates prototypes and inline functions */ |
378 | #define RB_PROTOTYPE(name, type, field, cmp) \ | 378 | #define RB_PROTOTYPE(name, type, field, cmp) \ |
379 | void name##_RB_INSERT_COLOR(struct name *, struct type *); \ | 379 | RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) |
380 | void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ | 380 | #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ |
381 | struct type *name##_RB_REMOVE(struct name *, struct type *); \ | 381 | RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) |
382 | struct type *name##_RB_INSERT(struct name *, struct type *); \ | 382 | #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ |
383 | struct type *name##_RB_FIND(struct name *, struct type *); \ | 383 | attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ |
384 | struct type *name##_RB_NEXT(struct type *); \ | 384 | attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ |
385 | struct type *name##_RB_MINMAX(struct name *, int); | 385 | attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ |
386 | 386 | attr struct type *name##_RB_INSERT(struct name *, struct type *); \ | |
387 | attr struct type *name##_RB_FIND(struct name *, struct type *); \ | ||
388 | attr struct type *name##_RB_NFIND(struct name *, struct type *); \ | ||
389 | attr struct type *name##_RB_NEXT(struct type *); \ | ||
390 | attr struct type *name##_RB_PREV(struct type *); \ | ||
391 | attr struct type *name##_RB_MINMAX(struct name *, int); \ | ||
392 | \ | ||
387 | 393 | ||
388 | /* Main rb operation. | 394 | /* Main rb operation. |
389 | * Moves node close to the key of elm to top | 395 | * Moves node close to the key of elm to top |
390 | */ | 396 | */ |
391 | #define RB_GENERATE(name, type, field, cmp) \ | 397 | #define RB_GENERATE(name, type, field, cmp) \ |
392 | void \ | 398 | RB_GENERATE_INTERNAL(name, type, field, cmp,) |
399 | #define RB_GENERATE_STATIC(name, type, field, cmp) \ | ||
400 | RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) | ||
401 | #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ | ||
402 | attr void \ | ||
393 | name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | 403 | name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ |
394 | { \ | 404 | { \ |
395 | struct type *parent, *gparent, *tmp; \ | 405 | struct type *parent, *gparent, *tmp; \ |
@@ -433,7 +443,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ | |||
433 | RB_COLOR(head->rbh_root, field) = RB_BLACK; \ | 443 | RB_COLOR(head->rbh_root, field) = RB_BLACK; \ |
434 | } \ | 444 | } \ |
435 | \ | 445 | \ |
436 | void \ | 446 | attr void \ |
437 | name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ | 447 | name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ |
438 | { \ | 448 | { \ |
439 | struct type *tmp; \ | 449 | struct type *tmp; \ |
@@ -509,7 +519,7 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) | |||
509 | RB_COLOR(elm, field) = RB_BLACK; \ | 519 | RB_COLOR(elm, field) = RB_BLACK; \ |
510 | } \ | 520 | } \ |
511 | \ | 521 | \ |
512 | struct type * \ | 522 | attr struct type * \ |
513 | name##_RB_REMOVE(struct name *head, struct type *elm) \ | 523 | name##_RB_REMOVE(struct name *head, struct type *elm) \ |
514 | { \ | 524 | { \ |
515 | struct type *child, *parent, *old = elm; \ | 525 | struct type *child, *parent, *old = elm; \ |
@@ -577,7 +587,7 @@ color: \ | |||
577 | } \ | 587 | } \ |
578 | \ | 588 | \ |
579 | /* Inserts a node into the RB tree */ \ | 589 | /* Inserts a node into the RB tree */ \ |
580 | struct type * \ | 590 | attr struct type * \ |
581 | name##_RB_INSERT(struct name *head, struct type *elm) \ | 591 | name##_RB_INSERT(struct name *head, struct type *elm) \ |
582 | { \ | 592 | { \ |
583 | struct type *tmp; \ | 593 | struct type *tmp; \ |
@@ -608,7 +618,7 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ | |||
608 | } \ | 618 | } \ |
609 | \ | 619 | \ |
610 | /* Finds the node with the same key as elm */ \ | 620 | /* Finds the node with the same key as elm */ \ |
611 | struct type * \ | 621 | attr struct type * \ |
612 | name##_RB_FIND(struct name *head, struct type *elm) \ | 622 | name##_RB_FIND(struct name *head, struct type *elm) \ |
613 | { \ | 623 | { \ |
614 | struct type *tmp = RB_ROOT(head); \ | 624 | struct type *tmp = RB_ROOT(head); \ |
@@ -625,7 +635,29 @@ name##_RB_FIND(struct name *head, struct type *elm) \ | |||
625 | return (NULL); \ | 635 | return (NULL); \ |
626 | } \ | 636 | } \ |
627 | \ | 637 | \ |
628 | struct type * \ | 638 | /* Finds the first node greater than or equal to the search key */ \ |
639 | attr struct type * \ | ||
640 | name##_RB_NFIND(struct name *head, struct type *elm) \ | ||
641 | { \ | ||
642 | struct type *tmp = RB_ROOT(head); \ | ||
643 | struct type *res = NULL; \ | ||
644 | int comp; \ | ||
645 | while (tmp) { \ | ||
646 | comp = cmp(elm, tmp); \ | ||
647 | if (comp < 0) { \ | ||
648 | res = tmp; \ | ||
649 | tmp = RB_LEFT(tmp, field); \ | ||
650 | } \ | ||
651 | else if (comp > 0) \ | ||
652 | tmp = RB_RIGHT(tmp, field); \ | ||
653 | else \ | ||
654 | return (tmp); \ | ||
655 | } \ | ||
656 | return (res); \ | ||
657 | } \ | ||
658 | \ | ||
659 | /* ARGSUSED */ \ | ||
660 | attr struct type * \ | ||
629 | name##_RB_NEXT(struct type *elm) \ | 661 | name##_RB_NEXT(struct type *elm) \ |
630 | { \ | 662 | { \ |
631 | if (RB_RIGHT(elm, field)) { \ | 663 | if (RB_RIGHT(elm, field)) { \ |
@@ -646,7 +678,29 @@ name##_RB_NEXT(struct type *elm) \ | |||
646 | return (elm); \ | 678 | return (elm); \ |
647 | } \ | 679 | } \ |
648 | \ | 680 | \ |
649 | struct type * \ | 681 | /* ARGSUSED */ \ |
682 | attr struct type * \ | ||
683 | name##_RB_PREV(struct type *elm) \ | ||
684 | { \ | ||
685 | if (RB_LEFT(elm, field)) { \ | ||
686 | elm = RB_LEFT(elm, field); \ | ||
687 | while (RB_RIGHT(elm, field)) \ | ||
688 | elm = RB_RIGHT(elm, field); \ | ||
689 | } else { \ | ||
690 | if (RB_PARENT(elm, field) && \ | ||
691 | (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ | ||
692 | elm = RB_PARENT(elm, field); \ | ||
693 | else { \ | ||
694 | while (RB_PARENT(elm, field) && \ | ||
695 | (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ | ||
696 | elm = RB_PARENT(elm, field); \ | ||
697 | elm = RB_PARENT(elm, field); \ | ||
698 | } \ | ||
699 | } \ | ||
700 | return (elm); \ | ||
701 | } \ | ||
702 | \ | ||
703 | attr struct type * \ | ||
650 | name##_RB_MINMAX(struct name *head, int val) \ | 704 | name##_RB_MINMAX(struct name *head, int val) \ |
651 | { \ | 705 | { \ |
652 | struct type *tmp = RB_ROOT(head); \ | 706 | struct type *tmp = RB_ROOT(head); \ |
@@ -667,7 +721,9 @@ name##_RB_MINMAX(struct name *head, int val) \ | |||
667 | #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) | 721 | #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) |
668 | #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) | 722 | #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) |
669 | #define RB_FIND(name, x, y) name##_RB_FIND(x, y) | 723 | #define RB_FIND(name, x, y) name##_RB_FIND(x, y) |
724 | #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) | ||
670 | #define RB_NEXT(name, x, y) name##_RB_NEXT(y) | 725 | #define RB_NEXT(name, x, y) name##_RB_NEXT(y) |
726 | #define RB_PREV(name, x, y) name##_RB_PREV(y) | ||
671 | #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) | 727 | #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) |
672 | #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) | 728 | #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) |
673 | 729 | ||
@@ -676,4 +732,19 @@ name##_RB_MINMAX(struct name *head, int val) \ | |||
676 | (x) != NULL; \ | 732 | (x) != NULL; \ |
677 | (x) = name##_RB_NEXT(x)) | 733 | (x) = name##_RB_NEXT(x)) |
678 | 734 | ||
735 | #define RB_FOREACH_SAFE(x, name, head, y) \ | ||
736 | for ((x) = RB_MIN(name, head); \ | ||
737 | ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ | ||
738 | (x) = (y)) | ||
739 | |||
740 | #define RB_FOREACH_REVERSE(x, name, head) \ | ||
741 | for ((x) = RB_MAX(name, head); \ | ||
742 | (x) != NULL; \ | ||
743 | (x) = name##_RB_PREV(x)) | ||
744 | |||
745 | #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ | ||
746 | for ((x) = RB_MAX(name, head); \ | ||
747 | ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ | ||
748 | (x) = (y)) | ||
749 | |||
679 | #endif /* _SYS_TREE_H_ */ | 750 | #endif /* _SYS_TREE_H_ */ |