]>
git.proxmox.com Git - mirror_frr.git/blob - lib/typerb.h
2 * The following Red-Black tree implementation is based off code with
5 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
30 struct typed_rb_entry
{
31 struct typed_rb_entry
*rbt_parent
;
32 struct typed_rb_entry
*rbt_left
;
33 struct typed_rb_entry
*rbt_right
;
34 unsigned int rbt_color
;
37 struct typed_rb_root
{
38 struct typed_rb_entry
*rbt_root
;
42 struct typed_rb_entry
*typed_rb_insert(struct typed_rb_root
*rbt
,
43 struct typed_rb_entry
*rbe
,
45 const struct typed_rb_entry
*a
,
46 const struct typed_rb_entry
*b
));
47 struct typed_rb_entry
*typed_rb_remove(struct typed_rb_root
*rbt
,
48 struct typed_rb_entry
*rbe
);
49 const struct typed_rb_entry
*typed_rb_find(const struct typed_rb_root
*rbt
,
50 const struct typed_rb_entry
*rbe
,
52 const struct typed_rb_entry
*a
,
53 const struct typed_rb_entry
*b
));
54 const struct typed_rb_entry
*typed_rb_find_gteq(const struct typed_rb_root
*rbt
,
55 const struct typed_rb_entry
*rbe
,
57 const struct typed_rb_entry
*a
,
58 const struct typed_rb_entry
*b
));
59 const struct typed_rb_entry
*typed_rb_find_lt(const struct typed_rb_root
*rbt
,
60 const struct typed_rb_entry
*rbe
,
62 const struct typed_rb_entry
*a
,
63 const struct typed_rb_entry
*b
));
64 struct typed_rb_entry
*typed_rb_min(const struct typed_rb_root
*rbt
);
65 struct typed_rb_entry
*typed_rb_max(const struct typed_rb_root
*rbt
);
66 struct typed_rb_entry
*typed_rb_prev(const struct typed_rb_entry
*rbe
);
67 struct typed_rb_entry
*typed_rb_next(const struct typed_rb_entry
*rbe
);
68 bool typed_rb_member(const struct typed_rb_root
*rbt
,
69 const struct typed_rb_entry
*rbe
);
71 #define _PREDECL_RBTREE(prefix) \
72 struct prefix ## _head { struct typed_rb_root rr; }; \
73 struct prefix ## _item { struct typed_rb_entry re; }; \
74 MACRO_REQUIRE_SEMICOLON() /* end */
76 #define INIT_RBTREE_UNIQ(var) { }
77 #define INIT_RBTREE_NONUNIQ(var) { }
79 #define _DECLARE_RBTREE(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
81 macro_inline void prefix ## _init(struct prefix##_head *h) \
83 memset(h, 0, sizeof(*h)); \
85 macro_inline void prefix ## _fini(struct prefix##_head *h) \
87 memset(h, 0, sizeof(*h)); \
89 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
91 struct typed_rb_entry *re; \
92 re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq); \
93 return container_of_null(re, type, field.re); \
95 macro_inline const type *prefix ## _const_find_gteq( \
96 const struct prefix##_head *h, const type *item) \
98 const struct typed_rb_entry *re; \
99 re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq); \
100 return container_of_null(re, type, field.re); \
102 macro_inline const type *prefix ## _const_find_lt( \
103 const struct prefix##_head *h, const type *item) \
105 const struct typed_rb_entry *re; \
106 re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq); \
107 return container_of_null(re, type, field.re); \
109 TYPESAFE_FIND_CMP(prefix, type) \
110 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
112 struct typed_rb_entry *re; \
113 re = typed_rb_remove(&h->rr, &item->field.re); \
114 return container_of_null(re, type, field.re); \
116 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
118 struct typed_rb_entry *re; \
119 re = typed_rb_min(&h->rr); \
122 typed_rb_remove(&h->rr, re); \
123 return container_of(re, type, field.re); \
125 TYPESAFE_SWAP_ALL_SIMPLE(prefix) \
126 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
128 const struct typed_rb_entry *re; \
129 re = typed_rb_min(&h->rr); \
130 return container_of_null(re, type, field.re); \
132 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
135 const struct typed_rb_entry *re; \
136 re = typed_rb_next(&item->field.re); \
137 return container_of_null(re, type, field.re); \
139 TYPESAFE_FIRST_NEXT(prefix, type) \
140 macro_pure const type *prefix ## _const_last(const struct prefix##_head *h) \
142 const struct typed_rb_entry *re; \
143 re = typed_rb_max(&h->rr); \
144 return container_of_null(re, type, field.re); \
146 macro_pure const type *prefix ## _const_prev(const struct prefix##_head *h, \
149 const struct typed_rb_entry *re; \
150 re = typed_rb_prev(&item->field.re); \
151 return container_of_null(re, type, field.re); \
153 TYPESAFE_LAST_PREV(prefix, type) \
154 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
156 struct typed_rb_entry *re; \
157 re = item ? typed_rb_next(&item->field.re) : NULL; \
158 return container_of_null(re, type, field.re); \
160 macro_pure type *prefix ## _prev_safe(struct prefix##_head *h, type *item) \
162 struct typed_rb_entry *re; \
163 re = item ? typed_rb_prev(&item->field.re) : NULL; \
164 return container_of_null(re, type, field.re); \
166 macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
168 return h->rr.count; \
170 macro_pure bool prefix ## _member(const struct prefix##_head *h, \
173 return typed_rb_member(&h->rr, &item->field.re); \
175 MACRO_REQUIRE_SEMICOLON() /* end */
177 #define PREDECL_RBTREE_UNIQ(prefix) \
178 _PREDECL_RBTREE(prefix)
179 #define DECLARE_RBTREE_UNIQ(prefix, type, field, cmpfn) \
181 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \
182 const struct typed_rb_entry *b) \
184 return cmpfn(container_of(a, type, field.re), \
185 container_of(b, type, field.re)); \
187 macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \
190 const struct typed_rb_entry *re; \
191 re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp); \
192 return container_of_null(re, type, field.re); \
194 TYPESAFE_FIND(prefix, type) \
196 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp); \
197 MACRO_REQUIRE_SEMICOLON() /* end */
199 #define PREDECL_RBTREE_NONUNIQ(prefix) \
200 _PREDECL_RBTREE(prefix)
201 #define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn) \
203 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \
204 const struct typed_rb_entry *b) \
206 return cmpfn(container_of(a, type, field.re), \
207 container_of(b, type, field.re)); \
209 macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a, \
210 const struct typed_rb_entry *b) \
212 int cmpval = cmpfn(container_of(a, type, field.re), \
213 container_of(b, type, field.re)); \
223 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq); \
224 MACRO_REQUIRE_SEMICOLON() /* end */
230 #endif /* _FRR_TYPERB_H */