]>
Commit | Line | Data |
---|---|---|
abd71baa DL |
1 | /* |
2 | * Copyright (c) 2016-2019 David Lamparter, for NetDEF, Inc. | |
3 | * | |
4 | * Permission to use, copy, modify, and distribute this software for any | |
5 | * purpose with or without fee is hereby granted, provided that the above | |
6 | * copyright notice and this permission notice appear in all copies. | |
7 | * | |
8 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |
9 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |
10 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |
11 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |
12 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |
13 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |
14 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |
15 | */ | |
16 | ||
17 | #ifndef _FRR_TYPESAFE_H | |
18 | #define _FRR_TYPESAFE_H | |
19 | ||
20 | #include <stddef.h> | |
21 | #include <stdint.h> | |
22 | #include <stdbool.h> | |
23 | #include <assert.h> | |
24 | #include "compiler.h" | |
25 | ||
eea3c899 RW |
26 | #ifdef __cplusplus |
27 | extern "C" { | |
28 | #endif | |
29 | ||
abd71baa DL |
30 | /* generic macros for all list-like types */ |
31 | ||
81fddbe7 | 32 | #define frr_each(prefix, head, item) \ |
abd71baa DL |
33 | for (item = prefix##_first(head); item; \ |
34 | item = prefix##_next(head, item)) | |
81fddbe7 | 35 | #define frr_each_safe(prefix, head, item) \ |
abd71baa DL |
36 | for (typeof(prefix##_next_safe(head, NULL)) prefix##_safe = \ |
37 | prefix##_next_safe(head, \ | |
38 | (item = prefix##_first(head))); \ | |
39 | item; \ | |
40 | item = prefix##_safe, \ | |
41 | prefix##_safe = prefix##_next_safe(head, prefix##_safe)) | |
81fddbe7 | 42 | #define frr_each_from(prefix, head, item, from) \ |
abd71baa DL |
43 | for (item = from, from = prefix##_next_safe(head, item); \ |
44 | item; \ | |
45 | item = from, from = prefix##_next_safe(head, from)) | |
46 | ||
47 | /* single-linked list, unsorted/arbitrary. | |
48 | * can be used as queue with add_tail / pop | |
49 | */ | |
50 | ||
51 | /* don't use these structs directly */ | |
52 | struct slist_item { | |
53 | struct slist_item *next; | |
54 | }; | |
55 | ||
56 | struct slist_head { | |
57 | struct slist_item *first, **last_next; | |
58 | size_t count; | |
59 | }; | |
60 | ||
61 | static inline void typesafe_list_add(struct slist_head *head, | |
62 | struct slist_item **pos, struct slist_item *item) | |
63 | { | |
64 | item->next = *pos; | |
65 | *pos = item; | |
66 | if (pos == head->last_next) | |
67 | head->last_next = &item->next; | |
68 | head->count++; | |
69 | } | |
70 | ||
71 | /* use as: | |
72 | * | |
73 | * PREDECL_LIST(namelist) | |
74 | * struct name { | |
75 | * struct namelist_item nlitem; | |
76 | * } | |
77 | * DECLARE_LIST(namelist, struct name, nlitem) | |
78 | */ | |
79 | #define PREDECL_LIST(prefix) \ | |
80 | struct prefix ## _head { struct slist_head sh; }; \ | |
81 | struct prefix ## _item { struct slist_item si; }; | |
82 | ||
83 | #define INIT_LIST(var) { .sh = { .last_next = &var.sh.first, }, } | |
84 | ||
85 | #define DECLARE_LIST(prefix, type, field) \ | |
86 | \ | |
87 | macro_inline void prefix ## _init(struct prefix##_head *h) \ | |
88 | { \ | |
89 | memset(h, 0, sizeof(*h)); \ | |
90 | h->sh.last_next = &h->sh.first; \ | |
91 | } \ | |
92 | macro_inline void prefix ## _fini(struct prefix##_head *h) \ | |
93 | { \ | |
94 | memset(h, 0, sizeof(*h)); \ | |
95 | } \ | |
96 | macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \ | |
97 | { \ | |
98 | typesafe_list_add(&h->sh, &h->sh.first, &item->field.si); \ | |
99 | } \ | |
100 | macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \ | |
101 | { \ | |
102 | typesafe_list_add(&h->sh, h->sh.last_next, &item->field.si); \ | |
103 | } \ | |
104 | macro_inline void prefix ## _add_after(struct prefix##_head *h, \ | |
105 | type *after, type *item) \ | |
106 | { \ | |
107 | struct slist_item **nextp; \ | |
108 | nextp = after ? &after->field.si.next : &h->sh.first; \ | |
109 | typesafe_list_add(&h->sh, nextp, &item->field.si); \ | |
110 | } \ | |
111 | /* TODO: del_hint */ \ | |
da098d78 | 112 | macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ |
abd71baa DL |
113 | { \ |
114 | struct slist_item **iter = &h->sh.first; \ | |
115 | while (*iter && *iter != &item->field.si) \ | |
116 | iter = &(*iter)->next; \ | |
117 | if (!*iter) \ | |
da098d78 | 118 | return NULL; \ |
abd71baa DL |
119 | h->sh.count--; \ |
120 | *iter = item->field.si.next; \ | |
121 | if (!item->field.si.next) \ | |
122 | h->sh.last_next = iter; \ | |
da098d78 | 123 | return item; \ |
abd71baa DL |
124 | } \ |
125 | macro_inline type *prefix ## _pop(struct prefix##_head *h) \ | |
126 | { \ | |
127 | struct slist_item *sitem = h->sh.first; \ | |
128 | if (!sitem) \ | |
129 | return NULL; \ | |
130 | h->sh.count--; \ | |
131 | h->sh.first = sitem->next; \ | |
132 | if (h->sh.first == NULL) \ | |
133 | h->sh.last_next = &h->sh.first; \ | |
134 | return container_of(sitem, type, field.si); \ | |
135 | } \ | |
136 | macro_pure type *prefix ## _first(struct prefix##_head *h) \ | |
137 | { \ | |
138 | return container_of_null(h->sh.first, type, field.si); \ | |
139 | } \ | |
140 | macro_pure type *prefix ## _next(struct prefix##_head * h, type *item) \ | |
141 | { \ | |
142 | struct slist_item *sitem = &item->field.si; \ | |
143 | return container_of_null(sitem->next, type, field.si); \ | |
144 | } \ | |
145 | macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ | |
146 | { \ | |
147 | struct slist_item *sitem; \ | |
148 | if (!item) \ | |
149 | return NULL; \ | |
150 | sitem = &item->field.si; \ | |
151 | return container_of_null(sitem->next, type, field.si); \ | |
152 | } \ | |
0ca16c58 | 153 | macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ |
abd71baa DL |
154 | { \ |
155 | return h->sh.count; \ | |
156 | } \ | |
157 | /* ... */ | |
158 | ||
fdad523b DL |
159 | /* don't use these structs directly */ |
160 | struct dlist_item { | |
161 | struct dlist_item *next; | |
162 | struct dlist_item *prev; | |
163 | }; | |
164 | ||
165 | struct dlist_head { | |
166 | struct dlist_item hitem; | |
167 | size_t count; | |
168 | }; | |
169 | ||
170 | static inline void typesafe_dlist_add(struct dlist_head *head, | |
171 | struct dlist_item *prev, struct dlist_item *item) | |
172 | { | |
173 | item->next = prev->next; | |
174 | item->next->prev = item; | |
175 | item->prev = prev; | |
176 | prev->next = item; | |
177 | head->count++; | |
178 | } | |
179 | ||
180 | /* double-linked list, for fast item deletion | |
181 | */ | |
182 | #define PREDECL_DLIST(prefix) \ | |
183 | struct prefix ## _head { struct dlist_head dh; }; \ | |
184 | struct prefix ## _item { struct dlist_item di; }; | |
185 | ||
186 | #define INIT_DLIST(var) { .dh = { \ | |
187 | .hitem = { &var.dh.hitem, &var.dh.hitem }, }, } | |
188 | ||
189 | #define DECLARE_DLIST(prefix, type, field) \ | |
190 | \ | |
191 | macro_inline void prefix ## _init(struct prefix##_head *h) \ | |
192 | { \ | |
193 | memset(h, 0, sizeof(*h)); \ | |
194 | h->dh.hitem.prev = &h->dh.hitem; \ | |
195 | h->dh.hitem.next = &h->dh.hitem; \ | |
196 | } \ | |
197 | macro_inline void prefix ## _fini(struct prefix##_head *h) \ | |
198 | { \ | |
199 | memset(h, 0, sizeof(*h)); \ | |
200 | } \ | |
201 | macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \ | |
202 | { \ | |
203 | typesafe_dlist_add(&h->dh, &h->dh.hitem, &item->field.di); \ | |
204 | } \ | |
205 | macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \ | |
206 | { \ | |
207 | typesafe_dlist_add(&h->dh, h->dh.hitem.prev, &item->field.di); \ | |
208 | } \ | |
209 | macro_inline void prefix ## _add_after(struct prefix##_head *h, \ | |
210 | type *after, type *item) \ | |
211 | { \ | |
212 | struct dlist_item *prev; \ | |
213 | prev = after ? &after->field.di : &h->dh.hitem; \ | |
214 | typesafe_dlist_add(&h->dh, prev, &item->field.di); \ | |
215 | } \ | |
da098d78 | 216 | macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ |
fdad523b DL |
217 | { \ |
218 | struct dlist_item *ditem = &item->field.di; \ | |
219 | ditem->prev->next = ditem->next; \ | |
220 | ditem->next->prev = ditem->prev; \ | |
221 | h->dh.count--; \ | |
222 | ditem->prev = ditem->next = NULL; \ | |
da098d78 | 223 | return item; \ |
fdad523b DL |
224 | } \ |
225 | macro_inline type *prefix ## _pop(struct prefix##_head *h) \ | |
226 | { \ | |
227 | struct dlist_item *ditem = h->dh.hitem.next; \ | |
228 | if (ditem == &h->dh.hitem) \ | |
229 | return NULL; \ | |
230 | ditem->prev->next = ditem->next; \ | |
231 | ditem->next->prev = ditem->prev; \ | |
232 | h->dh.count--; \ | |
233 | return container_of(ditem, type, field.di); \ | |
234 | } \ | |
235 | macro_pure type *prefix ## _first(struct prefix##_head *h) \ | |
236 | { \ | |
237 | struct dlist_item *ditem = h->dh.hitem.next; \ | |
238 | if (ditem == &h->dh.hitem) \ | |
239 | return NULL; \ | |
240 | return container_of(ditem, type, field.di); \ | |
241 | } \ | |
242 | macro_pure type *prefix ## _next(struct prefix##_head * h, type *item) \ | |
243 | { \ | |
244 | struct dlist_item *ditem = &item->field.di; \ | |
245 | if (ditem->next == &h->dh.hitem) \ | |
246 | return NULL; \ | |
247 | return container_of(ditem->next, type, field.di); \ | |
248 | } \ | |
249 | macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ | |
250 | { \ | |
251 | if (!item) \ | |
252 | return NULL; \ | |
253 | return prefix ## _next(h, item); \ | |
254 | } \ | |
0ca16c58 | 255 | macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ |
fdad523b DL |
256 | { \ |
257 | return h->dh.count; \ | |
258 | } \ | |
259 | /* ... */ | |
260 | ||
5cb4277d DL |
261 | /* note: heap currently caps out at 4G items */ |
262 | ||
263 | #define HEAP_NARY 8U | |
264 | typedef uint32_t heap_index_i; | |
265 | ||
266 | struct heap_item { | |
267 | uint32_t index; | |
268 | }; | |
269 | ||
270 | struct heap_head { | |
271 | struct heap_item **array; | |
272 | uint32_t arraysz, count; | |
273 | }; | |
274 | ||
275 | #define HEAP_RESIZE_TRESH_UP(h) \ | |
276 | (h->hh.count + 1 >= h->hh.arraysz) | |
277 | #define HEAP_RESIZE_TRESH_DN(h) \ | |
278 | (h->hh.count == 0 || \ | |
279 | h->hh.arraysz - h->hh.count > (h->hh.count + 1024) / 2) | |
280 | ||
281 | #define PREDECL_HEAP(prefix) \ | |
282 | struct prefix ## _head { struct heap_head hh; }; \ | |
283 | struct prefix ## _item { struct heap_item hi; }; | |
284 | ||
285 | #define INIT_HEAP(var) { } | |
286 | ||
287 | #define DECLARE_HEAP(prefix, type, field, cmpfn) \ | |
288 | \ | |
289 | macro_inline void prefix ## _init(struct prefix##_head *h) \ | |
290 | { \ | |
291 | memset(h, 0, sizeof(*h)); \ | |
292 | } \ | |
293 | macro_inline void prefix ## _fini(struct prefix##_head *h) \ | |
294 | { \ | |
295 | assert(h->hh.count == 0); \ | |
296 | memset(h, 0, sizeof(*h)); \ | |
297 | } \ | |
298 | macro_inline int prefix ## __cmp(const struct heap_item *a, \ | |
299 | const struct heap_item *b) \ | |
300 | { \ | |
301 | return cmpfn(container_of(a, type, field.hi), \ | |
302 | container_of(b, type, field.hi)); \ | |
303 | } \ | |
304 | macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ | |
305 | { \ | |
306 | if (HEAP_RESIZE_TRESH_UP(h)) \ | |
307 | typesafe_heap_resize(&h->hh, true); \ | |
308 | typesafe_heap_pullup(&h->hh, h->hh.count, &item->field.hi, \ | |
309 | prefix ## __cmp); \ | |
310 | h->hh.count++; \ | |
311 | return NULL; \ | |
312 | } \ | |
da098d78 | 313 | macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ |
5cb4277d DL |
314 | { \ |
315 | struct heap_item *other; \ | |
316 | uint32_t index = item->field.hi.index; \ | |
317 | assert(h->hh.array[index] == &item->field.hi); \ | |
318 | h->hh.count--; \ | |
319 | other = h->hh.array[h->hh.count]; \ | |
320 | if (cmpfn(container_of(other, type, field.hi), item) < 0) \ | |
321 | typesafe_heap_pullup(&h->hh, index, other, prefix ## __cmp); \ | |
322 | else \ | |
323 | typesafe_heap_pushdown(&h->hh, index, other, prefix ## __cmp); \ | |
324 | if (HEAP_RESIZE_TRESH_DN(h)) \ | |
325 | typesafe_heap_resize(&h->hh, false); \ | |
da098d78 | 326 | return item; \ |
5cb4277d DL |
327 | } \ |
328 | macro_inline type *prefix ## _pop(struct prefix##_head *h) \ | |
329 | { \ | |
330 | struct heap_item *hitem, *other; \ | |
331 | if (h->hh.count == 0) \ | |
332 | return NULL; \ | |
333 | hitem = h->hh.array[0]; \ | |
334 | h->hh.count--; \ | |
335 | other = h->hh.array[h->hh.count]; \ | |
336 | typesafe_heap_pushdown(&h->hh, 0, other, prefix ## __cmp); \ | |
337 | if (HEAP_RESIZE_TRESH_DN(h)) \ | |
338 | typesafe_heap_resize(&h->hh, false); \ | |
339 | return container_of(hitem, type, field.hi); \ | |
340 | } \ | |
341 | macro_pure type *prefix ## _first(struct prefix##_head *h) \ | |
342 | { \ | |
343 | if (h->hh.count == 0) \ | |
344 | return NULL; \ | |
345 | return container_of(h->hh.array[0], type, field.hi); \ | |
346 | } \ | |
347 | macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ | |
348 | { \ | |
349 | uint32_t idx = item->field.hi.index + 1; \ | |
350 | if (idx >= h->hh.count) \ | |
351 | return NULL; \ | |
352 | return container_of(h->hh.array[idx], type, field.hi); \ | |
353 | } \ | |
354 | macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ | |
355 | { \ | |
356 | if (!item) \ | |
357 | return NULL; \ | |
358 | return prefix ## _next(h, item); \ | |
359 | } \ | |
0ca16c58 | 360 | macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ |
5cb4277d DL |
361 | { \ |
362 | return h->hh.count; \ | |
363 | } \ | |
364 | /* ... */ | |
365 | ||
366 | extern void typesafe_heap_resize(struct heap_head *head, bool grow); | |
367 | extern void typesafe_heap_pushdown(struct heap_head *head, uint32_t index, | |
368 | struct heap_item *item, | |
369 | int (*cmpfn)(const struct heap_item *a, | |
370 | const struct heap_item *b)); | |
371 | extern void typesafe_heap_pullup(struct heap_head *head, uint32_t index, | |
372 | struct heap_item *item, | |
373 | int (*cmpfn)(const struct heap_item *a, | |
374 | const struct heap_item *b)); | |
375 | ||
abd71baa DL |
376 | /* single-linked list, sorted. |
377 | * can be used as priority queue with add / pop | |
378 | */ | |
379 | ||
380 | /* don't use these structs directly */ | |
381 | struct ssort_item { | |
382 | struct ssort_item *next; | |
383 | }; | |
384 | ||
385 | struct ssort_head { | |
386 | struct ssort_item *first; | |
387 | size_t count; | |
388 | }; | |
389 | ||
390 | /* use as: | |
391 | * | |
392 | * PREDECL_SORTLIST(namelist) | |
393 | * struct name { | |
394 | * struct namelist_item nlitem; | |
395 | * } | |
396 | * DECLARE_SORTLIST(namelist, struct name, nlitem) | |
397 | */ | |
398 | #define _PREDECL_SORTLIST(prefix) \ | |
399 | struct prefix ## _head { struct ssort_head sh; }; \ | |
400 | struct prefix ## _item { struct ssort_item si; }; | |
401 | ||
402 | #define INIT_SORTLIST_UNIQ(var) { } | |
403 | #define INIT_SORTLIST_NONUNIQ(var) { } | |
404 | ||
405 | #define PREDECL_SORTLIST_UNIQ(prefix) \ | |
406 | _PREDECL_SORTLIST(prefix) | |
407 | #define PREDECL_SORTLIST_NONUNIQ(prefix) \ | |
408 | _PREDECL_SORTLIST(prefix) | |
409 | ||
410 | #define _DECLARE_SORTLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \ | |
411 | \ | |
412 | macro_inline void prefix ## _init(struct prefix##_head *h) \ | |
413 | { \ | |
414 | memset(h, 0, sizeof(*h)); \ | |
415 | } \ | |
416 | macro_inline void prefix ## _fini(struct prefix##_head *h) \ | |
417 | { \ | |
418 | memset(h, 0, sizeof(*h)); \ | |
419 | } \ | |
420 | macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ | |
421 | { \ | |
422 | struct ssort_item **np = &h->sh.first; \ | |
423 | int c = 1; \ | |
424 | while (*np && (c = cmpfn_uq( \ | |
425 | container_of(*np, type, field.si), item)) < 0) \ | |
426 | np = &(*np)->next; \ | |
427 | if (c == 0) \ | |
428 | return container_of(*np, type, field.si); \ | |
429 | item->field.si.next = *np; \ | |
430 | *np = &item->field.si; \ | |
431 | h->sh.count++; \ | |
432 | return NULL; \ | |
433 | } \ | |
434 | macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ | |
435 | const type *item) \ | |
436 | { \ | |
437 | struct ssort_item *sitem = h->sh.first; \ | |
438 | int cmpval = 0; \ | |
439 | while (sitem && (cmpval = cmpfn_nuq( \ | |
4d5cf6bc | 440 | container_of(sitem, type, field.si), item)) < 0) \ |
abd71baa DL |
441 | sitem = sitem->next; \ |
442 | return container_of_null(sitem, type, field.si); \ | |
443 | } \ | |
444 | macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \ | |
445 | const type *item) \ | |
446 | { \ | |
447 | struct ssort_item *prev = NULL, *sitem = h->sh.first; \ | |
448 | int cmpval = 0; \ | |
449 | while (sitem && (cmpval = cmpfn_nuq( \ | |
4d5cf6bc | 450 | container_of(sitem, type, field.si), item)) < 0) \ |
abd71baa DL |
451 | sitem = (prev = sitem)->next; \ |
452 | return container_of_null(prev, type, field.si); \ | |
453 | } \ | |
454 | /* TODO: del_hint */ \ | |
da098d78 | 455 | macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ |
abd71baa DL |
456 | { \ |
457 | struct ssort_item **iter = &h->sh.first; \ | |
458 | while (*iter && *iter != &item->field.si) \ | |
459 | iter = &(*iter)->next; \ | |
460 | if (!*iter) \ | |
da098d78 | 461 | return NULL; \ |
abd71baa DL |
462 | h->sh.count--; \ |
463 | *iter = item->field.si.next; \ | |
da098d78 | 464 | return item; \ |
abd71baa DL |
465 | } \ |
466 | macro_inline type *prefix ## _pop(struct prefix##_head *h) \ | |
467 | { \ | |
468 | struct ssort_item *sitem = h->sh.first; \ | |
469 | if (!sitem) \ | |
470 | return NULL; \ | |
471 | h->sh.count--; \ | |
472 | h->sh.first = sitem->next; \ | |
473 | return container_of(sitem, type, field.si); \ | |
474 | } \ | |
475 | macro_pure type *prefix ## _first(struct prefix##_head *h) \ | |
476 | { \ | |
477 | return container_of_null(h->sh.first, type, field.si); \ | |
478 | } \ | |
479 | macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ | |
480 | { \ | |
481 | struct ssort_item *sitem = &item->field.si; \ | |
482 | return container_of_null(sitem->next, type, field.si); \ | |
483 | } \ | |
484 | macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ | |
485 | { \ | |
486 | struct ssort_item *sitem; \ | |
487 | if (!item) \ | |
488 | return NULL; \ | |
489 | sitem = &item->field.si; \ | |
490 | return container_of_null(sitem->next, type, field.si); \ | |
491 | } \ | |
0ca16c58 | 492 | macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ |
abd71baa DL |
493 | { \ |
494 | return h->sh.count; \ | |
495 | } \ | |
496 | /* ... */ | |
497 | ||
498 | #define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn) \ | |
499 | _DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn) \ | |
500 | \ | |
791ac7c7 | 501 | macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ |
abd71baa DL |
502 | { \ |
503 | struct ssort_item *sitem = h->sh.first; \ | |
504 | int cmpval = 0; \ | |
505 | while (sitem && (cmpval = cmpfn( \ | |
4d5cf6bc | 506 | container_of(sitem, type, field.si), item)) < 0) \ |
abd71baa DL |
507 | sitem = sitem->next; \ |
508 | if (!sitem || cmpval > 0) \ | |
509 | return NULL; \ | |
510 | return container_of(sitem, type, field.si); \ | |
511 | } \ | |
512 | /* ... */ | |
513 | ||
514 | #define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn) \ | |
515 | macro_inline int _ ## prefix ## _cmp(const type *a, const type *b) \ | |
516 | { \ | |
517 | int cmpval = cmpfn(a, b); \ | |
518 | if (cmpval) \ | |
519 | return cmpval; \ | |
520 | if (a < b) \ | |
521 | return -1; \ | |
522 | if (a > b) \ | |
523 | return 1; \ | |
524 | return 0; \ | |
525 | } \ | |
526 | _DECLARE_SORTLIST(prefix, type, field, cmpfn, _ ## prefix ## _cmp) \ | |
527 | /* ... */ | |
528 | ||
529 | ||
530 | /* hash, "sorted" by hash value | |
531 | */ | |
532 | ||
533 | /* don't use these structs directly */ | |
534 | struct thash_item { | |
535 | struct thash_item *next; | |
536 | uint32_t hashval; | |
537 | }; | |
538 | ||
539 | struct thash_head { | |
540 | struct thash_item **entries; | |
541 | uint32_t count; | |
542 | ||
543 | uint8_t tabshift; | |
544 | uint8_t minshift, maxshift; | |
545 | }; | |
546 | ||
547 | #define _HASH_SIZE(tabshift) \ | |
548 | ((1U << (tabshift)) >> 1) | |
549 | #define HASH_SIZE(head) \ | |
550 | _HASH_SIZE((head).tabshift) | |
551 | #define _HASH_KEY(tabshift, val) \ | |
552 | ((val) >> (33 - (tabshift))) | |
553 | #define HASH_KEY(head, val) \ | |
554 | _HASH_KEY((head).tabshift, val) | |
555 | #define HASH_GROW_THRESHOLD(head) \ | |
556 | ((head).count >= HASH_SIZE(head)) | |
557 | #define HASH_SHRINK_THRESHOLD(head) \ | |
558 | ((head).count <= (HASH_SIZE(head) - 1) / 2) | |
559 | ||
560 | extern void typesafe_hash_grow(struct thash_head *head); | |
561 | extern void typesafe_hash_shrink(struct thash_head *head); | |
562 | ||
563 | /* use as: | |
564 | * | |
565 | * PREDECL_HASH(namelist) | |
566 | * struct name { | |
567 | * struct namelist_item nlitem; | |
568 | * } | |
569 | * DECLARE_HASH(namelist, struct name, nlitem, cmpfunc, hashfunc) | |
570 | */ | |
571 | #define PREDECL_HASH(prefix) \ | |
572 | struct prefix ## _head { struct thash_head hh; }; \ | |
573 | struct prefix ## _item { struct thash_item hi; }; | |
574 | ||
575 | #define INIT_HASH(var) { } | |
576 | ||
577 | #define DECLARE_HASH(prefix, type, field, cmpfn, hashfn) \ | |
578 | \ | |
579 | macro_inline void prefix ## _init(struct prefix##_head *h) \ | |
580 | { \ | |
581 | memset(h, 0, sizeof(*h)); \ | |
582 | } \ | |
583 | macro_inline void prefix ## _fini(struct prefix##_head *h) \ | |
584 | { \ | |
585 | assert(h->hh.count == 0); \ | |
586 | h->hh.minshift = 0; \ | |
587 | typesafe_hash_shrink(&h->hh); \ | |
588 | memset(h, 0, sizeof(*h)); \ | |
589 | } \ | |
590 | macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ | |
591 | { \ | |
592 | h->hh.count++; \ | |
593 | if (!h->hh.tabshift || HASH_GROW_THRESHOLD(h->hh)) \ | |
594 | typesafe_hash_grow(&h->hh); \ | |
595 | \ | |
596 | uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \ | |
597 | item->field.hi.hashval = hval; \ | |
598 | struct thash_item **np = &h->hh.entries[hbits]; \ | |
599 | while (*np && (*np)->hashval < hval) \ | |
600 | np = &(*np)->next; \ | |
601 | if (*np && cmpfn(container_of(*np, type, field.hi), item) == 0) { \ | |
602 | h->hh.count--; \ | |
603 | return container_of(*np, type, field.hi); \ | |
604 | } \ | |
605 | item->field.hi.next = *np; \ | |
606 | *np = &item->field.hi; \ | |
607 | return NULL; \ | |
608 | } \ | |
791ac7c7 | 609 | macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ |
abd71baa DL |
610 | { \ |
611 | if (!h->hh.tabshift) \ | |
612 | return NULL; \ | |
613 | uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \ | |
614 | struct thash_item *hitem = h->hh.entries[hbits]; \ | |
615 | while (hitem && hitem->hashval < hval) \ | |
616 | hitem = hitem->next; \ | |
617 | while (hitem && hitem->hashval == hval) { \ | |
618 | if (!cmpfn(container_of(hitem, type, field.hi), item)) \ | |
619 | return container_of(hitem, type, field.hi); \ | |
620 | hitem = hitem->next; \ | |
621 | } \ | |
622 | return NULL; \ | |
623 | } \ | |
da098d78 | 624 | macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ |
abd71baa DL |
625 | { \ |
626 | if (!h->hh.tabshift) \ | |
da098d78 | 627 | return NULL; \ |
abd71baa DL |
628 | uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \ |
629 | struct thash_item **np = &h->hh.entries[hbits]; \ | |
630 | while (*np && (*np)->hashval < hval) \ | |
631 | np = &(*np)->next; \ | |
632 | while (*np && *np != &item->field.hi && (*np)->hashval == hval) \ | |
633 | np = &(*np)->next; \ | |
634 | if (*np != &item->field.hi) \ | |
da098d78 | 635 | return NULL; \ |
abd71baa DL |
636 | *np = item->field.hi.next; \ |
637 | item->field.hi.next = NULL; \ | |
638 | h->hh.count--; \ | |
639 | if (HASH_SHRINK_THRESHOLD(h->hh)) \ | |
640 | typesafe_hash_shrink(&h->hh); \ | |
da098d78 | 641 | return item; \ |
abd71baa DL |
642 | } \ |
643 | macro_inline type *prefix ## _pop(struct prefix##_head *h) \ | |
644 | { \ | |
645 | uint32_t i; \ | |
646 | for (i = 0; i < HASH_SIZE(h->hh); i++) \ | |
647 | if (h->hh.entries[i]) { \ | |
648 | struct thash_item *hitem = h->hh.entries[i]; \ | |
649 | h->hh.entries[i] = hitem->next; \ | |
650 | h->hh.count--; \ | |
651 | hitem->next = NULL; \ | |
652 | if (HASH_SHRINK_THRESHOLD(h->hh)) \ | |
653 | typesafe_hash_shrink(&h->hh); \ | |
654 | return container_of(hitem, type, field.hi); \ | |
655 | } \ | |
656 | return NULL; \ | |
657 | } \ | |
658 | macro_pure type *prefix ## _first(struct prefix##_head *h) \ | |
659 | { \ | |
660 | uint32_t i; \ | |
661 | for (i = 0; i < HASH_SIZE(h->hh); i++) \ | |
662 | if (h->hh.entries[i]) \ | |
663 | return container_of(h->hh.entries[i], type, field.hi); \ | |
664 | return NULL; \ | |
665 | } \ | |
666 | macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ | |
667 | { \ | |
668 | struct thash_item *hitem = &item->field.hi; \ | |
669 | if (hitem->next) \ | |
670 | return container_of(hitem->next, type, field.hi); \ | |
671 | uint32_t i = HASH_KEY(h->hh, hitem->hashval) + 1; \ | |
672 | for (; i < HASH_SIZE(h->hh); i++) \ | |
673 | if (h->hh.entries[i]) \ | |
674 | return container_of(h->hh.entries[i], type, field.hi); \ | |
675 | return NULL; \ | |
676 | } \ | |
677 | macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ | |
678 | { \ | |
679 | if (!item) \ | |
680 | return NULL; \ | |
681 | return prefix ## _next(h, item); \ | |
682 | } \ | |
0ca16c58 | 683 | macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ |
abd71baa DL |
684 | { \ |
685 | return h->hh.count; \ | |
686 | } \ | |
687 | /* ... */ | |
688 | ||
689 | /* skiplist, sorted. | |
690 | * can be used as priority queue with add / pop | |
691 | */ | |
692 | ||
693 | /* don't use these structs directly */ | |
694 | #define SKIPLIST_MAXDEPTH 16 | |
695 | #define SKIPLIST_EMBED 4 | |
696 | #define SKIPLIST_OVERFLOW (SKIPLIST_EMBED - 1) | |
697 | ||
698 | struct sskip_item { | |
699 | struct sskip_item *next[SKIPLIST_EMBED]; | |
700 | }; | |
701 | ||
702 | struct sskip_overflow { | |
703 | struct sskip_item *next[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW]; | |
704 | }; | |
705 | ||
706 | struct sskip_head { | |
707 | struct sskip_item hitem; | |
708 | struct sskip_item *overflow[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW]; | |
709 | size_t count; | |
710 | }; | |
711 | ||
712 | /* use as: | |
713 | * | |
714 | * PREDECL_SKIPLIST(namelist) | |
715 | * struct name { | |
716 | * struct namelist_item nlitem; | |
717 | * } | |
718 | * DECLARE_SKIPLIST(namelist, struct name, nlitem, cmpfunc) | |
719 | */ | |
720 | #define _PREDECL_SKIPLIST(prefix) \ | |
721 | struct prefix ## _head { struct sskip_head sh; }; \ | |
722 | struct prefix ## _item { struct sskip_item si; }; | |
723 | ||
724 | #define INIT_SKIPLIST_UNIQ(var) { } | |
725 | #define INIT_SKIPLIST_NONUNIQ(var) { } | |
726 | ||
727 | #define _DECLARE_SKIPLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \ | |
728 | \ | |
729 | macro_inline void prefix ## _init(struct prefix##_head *h) \ | |
730 | { \ | |
731 | memset(h, 0, sizeof(*h)); \ | |
732 | h->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \ | |
733 | ((uintptr_t)h->sh.overflow | 1); \ | |
734 | } \ | |
735 | macro_inline void prefix ## _fini(struct prefix##_head *h) \ | |
736 | { \ | |
737 | memset(h, 0, sizeof(*h)); \ | |
738 | } \ | |
739 | macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ | |
740 | { \ | |
741 | struct sskip_item *si; \ | |
742 | si = typesafe_skiplist_add(&h->sh, &item->field.si, cmpfn_uq); \ | |
743 | return container_of_null(si, type, field.si); \ | |
744 | } \ | |
745 | macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ | |
746 | const type *item) \ | |
747 | { \ | |
748 | struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh, \ | |
749 | &item->field.si, cmpfn_nuq); \ | |
750 | return container_of_null(sitem, type, field.si); \ | |
751 | } \ | |
752 | macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \ | |
753 | const type *item) \ | |
754 | { \ | |
755 | struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh, \ | |
756 | &item->field.si, cmpfn_nuq); \ | |
757 | return container_of_null(sitem, type, field.si); \ | |
758 | } \ | |
da098d78 | 759 | macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ |
abd71baa | 760 | { \ |
da098d78 SW |
761 | struct sskip_item *sitem = typesafe_skiplist_del(&h->sh, \ |
762 | &item->field.si, cmpfn_uq); \ | |
763 | return container_of_null(sitem, type, field.si); \ | |
abd71baa DL |
764 | } \ |
765 | macro_inline type *prefix ## _pop(struct prefix##_head *h) \ | |
766 | { \ | |
01734da3 DL |
767 | struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh); \ |
768 | return container_of_null(sitem, type, field.si); \ | |
abd71baa DL |
769 | } \ |
770 | macro_pure type *prefix ## _first(struct prefix##_head *h) \ | |
771 | { \ | |
772 | struct sskip_item *first = h->sh.hitem.next[0]; \ | |
773 | return container_of_null(first, type, field.si); \ | |
774 | } \ | |
775 | macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ | |
776 | { \ | |
777 | struct sskip_item *next = item->field.si.next[0]; \ | |
778 | return container_of_null(next, type, field.si); \ | |
779 | } \ | |
780 | macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ | |
781 | { \ | |
782 | struct sskip_item *next; \ | |
783 | next = item ? item->field.si.next[0] : NULL; \ | |
784 | return container_of_null(next, type, field.si); \ | |
785 | } \ | |
0ca16c58 | 786 | macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ |
abd71baa DL |
787 | { \ |
788 | return h->sh.count; \ | |
789 | } \ | |
790 | /* ... */ | |
791 | ||
792 | #define PREDECL_SKIPLIST_UNIQ(prefix) \ | |
793 | _PREDECL_SKIPLIST(prefix) | |
794 | #define DECLARE_SKIPLIST_UNIQ(prefix, type, field, cmpfn) \ | |
795 | \ | |
796 | macro_inline int prefix ## __cmp(const struct sskip_item *a, \ | |
797 | const struct sskip_item *b) \ | |
798 | { \ | |
799 | return cmpfn(container_of(a, type, field.si), \ | |
800 | container_of(b, type, field.si)); \ | |
801 | } \ | |
791ac7c7 | 802 | macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \ |
abd71baa DL |
803 | { \ |
804 | struct sskip_item *sitem = typesafe_skiplist_find(&h->sh, \ | |
805 | &item->field.si, &prefix ## __cmp); \ | |
806 | return container_of_null(sitem, type, field.si); \ | |
807 | } \ | |
808 | \ | |
809 | _DECLARE_SKIPLIST(prefix, type, field, \ | |
810 | prefix ## __cmp, prefix ## __cmp) \ | |
811 | /* ... */ | |
812 | ||
813 | #define PREDECL_SKIPLIST_NONUNIQ(prefix) \ | |
814 | _PREDECL_SKIPLIST(prefix) | |
815 | #define DECLARE_SKIPLIST_NONUNIQ(prefix, type, field, cmpfn) \ | |
816 | \ | |
817 | macro_inline int prefix ## __cmp(const struct sskip_item *a, \ | |
818 | const struct sskip_item *b) \ | |
819 | { \ | |
820 | return cmpfn(container_of(a, type, field.si), \ | |
821 | container_of(b, type, field.si)); \ | |
822 | } \ | |
823 | macro_inline int prefix ## __cmp_uq(const struct sskip_item *a, \ | |
824 | const struct sskip_item *b) \ | |
825 | { \ | |
826 | int cmpval = cmpfn(container_of(a, type, field.si), \ | |
827 | container_of(b, type, field.si)); \ | |
828 | if (cmpval) \ | |
829 | return cmpval; \ | |
830 | if (a < b) \ | |
831 | return -1; \ | |
832 | if (a > b) \ | |
833 | return 1; \ | |
834 | return 0; \ | |
835 | } \ | |
836 | \ | |
837 | _DECLARE_SKIPLIST(prefix, type, field, \ | |
838 | prefix ## __cmp, prefix ## __cmp_uq) \ | |
839 | /* ... */ | |
840 | ||
841 | ||
842 | extern struct sskip_item *typesafe_skiplist_add(struct sskip_head *head, | |
843 | struct sskip_item *item, int (*cmpfn)( | |
844 | const struct sskip_item *a, | |
845 | const struct sskip_item *b)); | |
846 | extern struct sskip_item *typesafe_skiplist_find(struct sskip_head *head, | |
847 | const struct sskip_item *item, int (*cmpfn)( | |
848 | const struct sskip_item *a, | |
849 | const struct sskip_item *b)); | |
850 | extern struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head, | |
851 | const struct sskip_item *item, int (*cmpfn)( | |
852 | const struct sskip_item *a, | |
853 | const struct sskip_item *b)); | |
854 | extern struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head, | |
855 | const struct sskip_item *item, int (*cmpfn)( | |
856 | const struct sskip_item *a, | |
857 | const struct sskip_item *b)); | |
da098d78 SW |
858 | extern struct sskip_item *typesafe_skiplist_del( |
859 | struct sskip_head *head, struct sskip_item *item, int (*cmpfn)( | |
abd71baa DL |
860 | const struct sskip_item *a, |
861 | const struct sskip_item *b)); | |
01734da3 | 862 | extern struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head); |
abd71baa | 863 | |
eea3c899 RW |
864 | #ifdef __cplusplus |
865 | } | |
866 | #endif | |
867 | ||
80911bc2 DL |
868 | /* this needs to stay at the end because both files include each other. |
869 | * the resolved order is typesafe.h before typerb.h | |
870 | */ | |
871 | #include "typerb.h" | |
872 | ||
abd71baa | 873 | #endif /* _FRR_TYPESAFE_H */ |