]>
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.
29 struct typed_rb_entry
{
30 struct typed_rb_entry
*rbt_parent
;
31 struct typed_rb_entry
*rbt_left
;
32 struct typed_rb_entry
*rbt_right
;
33 unsigned int rbt_color
;
36 struct typed_rb_root
{
37 struct typed_rb_entry
*rbt_root
;
41 struct typed_rb_entry
*typed_rb_insert(struct typed_rb_root
*rbt
,
42 struct typed_rb_entry
*rbe
,
44 const struct typed_rb_entry
*a
,
45 const struct typed_rb_entry
*b
));
46 struct typed_rb_entry
*typed_rb_remove(struct typed_rb_root
*rbt
,
47 struct typed_rb_entry
*rbe
);
48 struct typed_rb_entry
*typed_rb_find(struct typed_rb_root
*rbt
,
49 const struct typed_rb_entry
*rbe
,
51 const struct typed_rb_entry
*a
,
52 const struct typed_rb_entry
*b
));
53 struct typed_rb_entry
*typed_rb_find_gteq(struct typed_rb_root
*rbt
,
54 const struct typed_rb_entry
*rbe
,
56 const struct typed_rb_entry
*a
,
57 const struct typed_rb_entry
*b
));
58 struct typed_rb_entry
*typed_rb_find_lt(struct typed_rb_root
*rbt
,
59 const struct typed_rb_entry
*rbe
,
61 const struct typed_rb_entry
*a
,
62 const struct typed_rb_entry
*b
));
63 struct typed_rb_entry
*typed_rb_min(struct typed_rb_root
*rbt
);
64 struct typed_rb_entry
*typed_rb_next(struct typed_rb_entry
*rbe
);
66 #define _PREDECL_RBTREE(prefix) \
67 struct prefix ## _head { struct typed_rb_root rr; }; \
68 struct prefix ## _item { struct typed_rb_entry re; };
70 #define INIT_RBTREE_UNIQ(var) { }
71 #define INIT_RBTREE_NONUNIQ(var) { }
73 #define _DECLARE_RBTREE(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
75 macro_inline void prefix ## _init(struct prefix##_head *h) \
77 memset(h, 0, sizeof(*h)); \
79 macro_inline void prefix ## _fini(struct prefix##_head *h) \
81 memset(h, 0, sizeof(*h)); \
83 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
85 struct typed_rb_entry *re; \
86 re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq); \
87 return container_of_null(re, type, field.re); \
89 macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \
92 struct typed_rb_entry *re; \
93 re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq); \
94 return container_of_null(re, type, field.re); \
96 macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \
99 struct typed_rb_entry *re; \
100 re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq); \
101 return container_of_null(re, type, field.re); \
103 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
105 struct typed_rb_entry *re; \
106 re = typed_rb_remove(&h->rr, &item->field.re); \
107 return container_of_null(re, type, field.re); \
109 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
111 struct typed_rb_entry *re; \
112 re = typed_rb_min(&h->rr); \
115 typed_rb_remove(&h->rr, re); \
116 return container_of(re, type, field.re); \
118 macro_pure type *prefix ## _first(struct prefix##_head *h) \
120 struct typed_rb_entry *re; \
121 re = typed_rb_min(&h->rr); \
122 return container_of_null(re, type, field.re); \
124 macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \
126 struct typed_rb_entry *re; \
127 re = typed_rb_next(&item->field.re); \
128 return container_of_null(re, type, field.re); \
130 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
132 struct typed_rb_entry *re; \
133 re = item ? typed_rb_next(&item->field.re) : NULL; \
134 return container_of_null(re, type, field.re); \
136 macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
138 return h->rr.count; \
142 #define PREDECL_RBTREE_UNIQ(prefix) \
143 _PREDECL_RBTREE(prefix)
144 #define DECLARE_RBTREE_UNIQ(prefix, type, field, cmpfn) \
146 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \
147 const struct typed_rb_entry *b) \
149 return cmpfn(container_of(a, type, field.re), \
150 container_of(b, type, field.re)); \
152 macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \
154 struct typed_rb_entry *re; \
155 re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp); \
156 return container_of_null(re, type, field.re); \
159 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp) \
162 #define PREDECL_RBTREE_NONUNIQ(prefix) \
163 _PREDECL_RBTREE(prefix)
164 #define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn) \
166 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \
167 const struct typed_rb_entry *b) \
169 return cmpfn(container_of(a, type, field.re), \
170 container_of(b, type, field.re)); \
172 macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a, \
173 const struct typed_rb_entry *b) \
175 int cmpval = cmpfn(container_of(a, type, field.re), \
176 container_of(b, type, field.re)); \
186 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq) \
193 #endif /* _FRR_TYPERB_H */