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