]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: ISC |
80911bc2 DL |
2 | /* |
3 | * The following Red-Black tree implementation is based off code with | |
4 | * original copyright: | |
5 | * | |
6 | * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> | |
80911bc2 DL |
7 | */ |
8 | ||
9 | #ifndef _FRR_TYPERB_H | |
10 | #define _FRR_TYPERB_H | |
11 | ||
b0993fb2 | 12 | #include <string.h> |
80911bc2 DL |
13 | #include "typesafe.h" |
14 | ||
eea3c899 RW |
15 | #ifdef __cplusplus |
16 | extern "C" { | |
17 | #endif | |
18 | ||
80911bc2 DL |
19 | struct typed_rb_entry { |
20 | struct typed_rb_entry *rbt_parent; | |
21 | struct typed_rb_entry *rbt_left; | |
22 | struct typed_rb_entry *rbt_right; | |
23 | unsigned int rbt_color; | |
24 | }; | |
25 | ||
26 | struct typed_rb_root { | |
27 | struct typed_rb_entry *rbt_root; | |
28 | size_t count; | |
29 | }; | |
30 | ||
571a045b | 31 | struct typed_rb_entry *typed_rb_insert(struct typed_rb_root *rbt, |
80911bc2 DL |
32 | struct typed_rb_entry *rbe, |
33 | int (*cmpfn)( | |
34 | const struct typed_rb_entry *a, | |
35 | const struct typed_rb_entry *b)); | |
571a045b | 36 | struct typed_rb_entry *typed_rb_remove(struct typed_rb_root *rbt, |
da098d78 | 37 | struct typed_rb_entry *rbe); |
daf3441d | 38 | const struct typed_rb_entry *typed_rb_find(const struct typed_rb_root *rbt, |
80911bc2 DL |
39 | const struct typed_rb_entry *rbe, |
40 | int (*cmpfn)( | |
41 | const struct typed_rb_entry *a, | |
42 | const struct typed_rb_entry *b)); | |
daf3441d | 43 | const struct typed_rb_entry *typed_rb_find_gteq(const struct typed_rb_root *rbt, |
80911bc2 DL |
44 | const struct typed_rb_entry *rbe, |
45 | int (*cmpfn)( | |
46 | const struct typed_rb_entry *a, | |
47 | const struct typed_rb_entry *b)); | |
daf3441d | 48 | const struct typed_rb_entry *typed_rb_find_lt(const struct typed_rb_root *rbt, |
80911bc2 DL |
49 | const struct typed_rb_entry *rbe, |
50 | int (*cmpfn)( | |
51 | const struct typed_rb_entry *a, | |
52 | const struct typed_rb_entry *b)); | |
daf3441d | 53 | struct typed_rb_entry *typed_rb_min(const struct typed_rb_root *rbt); |
643ea83b DL |
54 | struct typed_rb_entry *typed_rb_max(const struct typed_rb_root *rbt); |
55 | struct typed_rb_entry *typed_rb_prev(const struct typed_rb_entry *rbe); | |
daf3441d | 56 | struct typed_rb_entry *typed_rb_next(const struct typed_rb_entry *rbe); |
f45897e4 DL |
57 | bool typed_rb_member(const struct typed_rb_root *rbt, |
58 | const struct typed_rb_entry *rbe); | |
80911bc2 DL |
59 | |
60 | #define _PREDECL_RBTREE(prefix) \ | |
61 | struct prefix ## _head { struct typed_rb_root rr; }; \ | |
960b9a53 DL |
62 | struct prefix ## _item { struct typed_rb_entry re; }; \ |
63 | MACRO_REQUIRE_SEMICOLON() /* end */ | |
80911bc2 DL |
64 | |
65 | #define INIT_RBTREE_UNIQ(var) { } | |
66 | #define INIT_RBTREE_NONUNIQ(var) { } | |
67 | ||
68 | #define _DECLARE_RBTREE(prefix, type, field, cmpfn_nuq, cmpfn_uq) \ | |
69 | \ | |
70 | macro_inline void prefix ## _init(struct prefix##_head *h) \ | |
71 | { \ | |
72 | memset(h, 0, sizeof(*h)); \ | |
73 | } \ | |
74 | macro_inline void prefix ## _fini(struct prefix##_head *h) \ | |
75 | { \ | |
76 | memset(h, 0, sizeof(*h)); \ | |
77 | } \ | |
78 | macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ | |
79 | { \ | |
80 | struct typed_rb_entry *re; \ | |
81 | re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq); \ | |
82 | return container_of_null(re, type, field.re); \ | |
83 | } \ | |
daf3441d DL |
84 | macro_inline const type *prefix ## _const_find_gteq( \ |
85 | const struct prefix##_head *h, const type *item) \ | |
80911bc2 | 86 | { \ |
daf3441d | 87 | const struct typed_rb_entry *re; \ |
80911bc2 DL |
88 | re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq); \ |
89 | return container_of_null(re, type, field.re); \ | |
90 | } \ | |
daf3441d DL |
91 | macro_inline const type *prefix ## _const_find_lt( \ |
92 | const struct prefix##_head *h, const type *item) \ | |
80911bc2 | 93 | { \ |
daf3441d | 94 | const struct typed_rb_entry *re; \ |
80911bc2 DL |
95 | re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq); \ |
96 | return container_of_null(re, type, field.re); \ | |
97 | } \ | |
daf3441d | 98 | TYPESAFE_FIND_CMP(prefix, type) \ |
da098d78 | 99 | macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ |
80911bc2 | 100 | { \ |
da098d78 SW |
101 | struct typed_rb_entry *re; \ |
102 | re = typed_rb_remove(&h->rr, &item->field.re); \ | |
103 | return container_of_null(re, type, field.re); \ | |
80911bc2 DL |
104 | } \ |
105 | macro_inline type *prefix ## _pop(struct prefix##_head *h) \ | |
106 | { \ | |
107 | struct typed_rb_entry *re; \ | |
108 | re = typed_rb_min(&h->rr); \ | |
109 | if (!re) \ | |
110 | return NULL; \ | |
111 | typed_rb_remove(&h->rr, re); \ | |
112 | return container_of(re, type, field.re); \ | |
113 | } \ | |
507e0e5d | 114 | TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ |
daf3441d | 115 | macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ |
80911bc2 | 116 | { \ |
daf3441d | 117 | const struct typed_rb_entry *re; \ |
80911bc2 DL |
118 | re = typed_rb_min(&h->rr); \ |
119 | return container_of_null(re, type, field.re); \ | |
120 | } \ | |
daf3441d DL |
121 | macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ |
122 | const type *item) \ | |
80911bc2 | 123 | { \ |
daf3441d | 124 | const struct typed_rb_entry *re; \ |
80911bc2 DL |
125 | re = typed_rb_next(&item->field.re); \ |
126 | return container_of_null(re, type, field.re); \ | |
127 | } \ | |
daf3441d | 128 | TYPESAFE_FIRST_NEXT(prefix, type) \ |
643ea83b DL |
129 | macro_pure const type *prefix ## _const_last(const struct prefix##_head *h) \ |
130 | { \ | |
131 | const struct typed_rb_entry *re; \ | |
132 | re = typed_rb_max(&h->rr); \ | |
133 | return container_of_null(re, type, field.re); \ | |
134 | } \ | |
135 | macro_pure const type *prefix ## _const_prev(const struct prefix##_head *h, \ | |
136 | const type *item) \ | |
137 | { \ | |
138 | const struct typed_rb_entry *re; \ | |
139 | re = typed_rb_prev(&item->field.re); \ | |
140 | return container_of_null(re, type, field.re); \ | |
141 | } \ | |
142 | TYPESAFE_LAST_PREV(prefix, type) \ | |
80911bc2 DL |
143 | macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ |
144 | { \ | |
145 | struct typed_rb_entry *re; \ | |
146 | re = item ? typed_rb_next(&item->field.re) : NULL; \ | |
147 | return container_of_null(re, type, field.re); \ | |
148 | } \ | |
643ea83b DL |
149 | macro_pure type *prefix ## _prev_safe(struct prefix##_head *h, type *item) \ |
150 | { \ | |
151 | struct typed_rb_entry *re; \ | |
152 | re = item ? typed_rb_prev(&item->field.re) : NULL; \ | |
153 | return container_of_null(re, type, field.re); \ | |
154 | } \ | |
0ca16c58 | 155 | macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ |
80911bc2 DL |
156 | { \ |
157 | return h->rr.count; \ | |
158 | } \ | |
f45897e4 DL |
159 | macro_pure bool prefix ## _member(const struct prefix##_head *h, \ |
160 | const type *item) \ | |
161 | { \ | |
162 | return typed_rb_member(&h->rr, &item->field.re); \ | |
163 | } \ | |
960b9a53 | 164 | MACRO_REQUIRE_SEMICOLON() /* end */ |
80911bc2 DL |
165 | |
166 | #define PREDECL_RBTREE_UNIQ(prefix) \ | |
167 | _PREDECL_RBTREE(prefix) | |
168 | #define DECLARE_RBTREE_UNIQ(prefix, type, field, cmpfn) \ | |
169 | \ | |
170 | macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \ | |
171 | const struct typed_rb_entry *b) \ | |
172 | { \ | |
173 | return cmpfn(container_of(a, type, field.re), \ | |
174 | container_of(b, type, field.re)); \ | |
175 | } \ | |
daf3441d DL |
176 | macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ |
177 | const type *item) \ | |
80911bc2 | 178 | { \ |
daf3441d | 179 | const struct typed_rb_entry *re; \ |
80911bc2 DL |
180 | re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp); \ |
181 | return container_of_null(re, type, field.re); \ | |
182 | } \ | |
daf3441d | 183 | TYPESAFE_FIND(prefix, type) \ |
80911bc2 | 184 | \ |
960b9a53 DL |
185 | _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp); \ |
186 | MACRO_REQUIRE_SEMICOLON() /* end */ | |
80911bc2 DL |
187 | |
188 | #define PREDECL_RBTREE_NONUNIQ(prefix) \ | |
189 | _PREDECL_RBTREE(prefix) | |
190 | #define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn) \ | |
191 | \ | |
192 | macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \ | |
193 | const struct typed_rb_entry *b) \ | |
194 | { \ | |
195 | return cmpfn(container_of(a, type, field.re), \ | |
196 | container_of(b, type, field.re)); \ | |
197 | } \ | |
198 | macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a, \ | |
199 | const struct typed_rb_entry *b) \ | |
200 | { \ | |
201 | int cmpval = cmpfn(container_of(a, type, field.re), \ | |
202 | container_of(b, type, field.re)); \ | |
203 | if (cmpval) \ | |
204 | return cmpval; \ | |
205 | if (a < b) \ | |
206 | return -1; \ | |
207 | if (a > b) \ | |
208 | return 1; \ | |
209 | return 0; \ | |
210 | } \ | |
211 | \ | |
960b9a53 DL |
212 | _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq); \ |
213 | MACRO_REQUIRE_SEMICOLON() /* end */ | |
80911bc2 | 214 | |
eea3c899 RW |
215 | #ifdef __cplusplus |
216 | } | |
217 | #endif | |
218 | ||
80911bc2 | 219 | #endif /* _FRR_TYPERB_H */ |