summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog2
-rw-r--r--krl.c4
-rw-r--r--openbsd-compat/sys-tree.h109
3 files changed, 94 insertions, 21 deletions
diff --git a/ChangeLog b/ChangeLog
index 43cedb63e..7bc6b451c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -24,6 +24,8 @@
24 - markus@cvs.openbsd.org 2013/01/19 12:34:55 24 - markus@cvs.openbsd.org 2013/01/19 12:34:55
25 [krl.c] 25 [krl.c]
26 RB_INSERT does not remove existing elments; ok djm@ 26 RB_INSERT does not remove existing elments; ok djm@
27 - (djm) [openbsd-compat/sys-tree.h] Sync with OpenBSD. krl.c needs newer
28 version.
27 29
2820130118 3020130118
29 - (djm) OpenBSD CVS Sync 31 - (djm) OpenBSD CVS Sync
diff --git a/krl.c b/krl.c
index b09f2dc11..fe22bde25 100644
--- a/krl.c
+++ b/krl.c
@@ -20,8 +20,8 @@
20 20
21#include <sys/types.h> 21#include <sys/types.h>
22#include <sys/param.h> 22#include <sys/param.h>
23#include <sys/tree.h> 23#include <openbsd-compat/sys-tree.h>
24#include <sys/queue.h> 24#include <openbsd-compat/sys-queue.h>
25 25
26#include <errno.h> 26#include <errno.h>
27#include <fcntl.h> 27#include <fcntl.h>
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) \
379void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 379 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
380void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 380#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
381struct type *name##_RB_REMOVE(struct name *, struct type *); \ 381 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
382struct type *name##_RB_INSERT(struct name *, struct type *); \ 382#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
383struct type *name##_RB_FIND(struct name *, struct type *); \ 383attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
384struct type *name##_RB_NEXT(struct type *); \ 384attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
385struct type *name##_RB_MINMAX(struct name *, int); 385attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
386 386attr struct type *name##_RB_INSERT(struct name *, struct type *); \
387attr struct type *name##_RB_FIND(struct name *, struct type *); \
388attr struct type *name##_RB_NFIND(struct name *, struct type *); \
389attr struct type *name##_RB_NEXT(struct type *); \
390attr struct type *name##_RB_PREV(struct type *); \
391attr 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) \
392void \ 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) \
402attr void \
393name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 403name##_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 \
436void \ 446attr void \
437name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 447name##_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 \
512struct type * \ 522attr struct type * \
513name##_RB_REMOVE(struct name *head, struct type *elm) \ 523name##_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 */ \
580struct type * \ 590attr struct type * \
581name##_RB_INSERT(struct name *head, struct type *elm) \ 591name##_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 */ \
611struct type * \ 621attr struct type * \
612name##_RB_FIND(struct name *head, struct type *elm) \ 622name##_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 \
628struct type * \ 638/* Finds the first node greater than or equal to the search key */ \
639attr struct type * \
640name##_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 */ \
660attr struct type * \
629name##_RB_NEXT(struct type *elm) \ 661name##_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 \
649struct type * \ 681/* ARGSUSED */ \
682attr struct type * \
683name##_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 \
703attr struct type * \
650name##_RB_MINMAX(struct name *head, int val) \ 704name##_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_ */
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-18 21:38:39 +0000