1 // SPDX-License-Identifier: ISC
3 * Copyright (c) 2019 David Lamparter, for NetDEF, Inc.
18 DEFINE_MTYPE_STATIC(LIB
, TYPEDHASH_BUCKET
, "Typed-hash bucket");
19 DEFINE_MTYPE_STATIC(LIB
, SKIPLIST_OFLOW
, "Skiplist overflow");
20 DEFINE_MTYPE_STATIC(LIB
, HEAP_ARRAY
, "Typed-heap array");
22 struct slist_item typesafe_slist_sentinel
= { NULL
};
24 bool typesafe_list_member(const struct slist_head
*head
,
25 const struct slist_item
*item
)
27 struct slist_item
*fromhead
= head
->first
;
28 struct slist_item
**fromnext
= (struct slist_item
**)&item
->next
;
30 while (fromhead
!= _SLIST_LAST
) {
31 if (fromhead
== item
|| fromnext
== head
->last_next
)
34 fromhead
= fromhead
->next
;
35 if (!*fromnext
|| *fromnext
== _SLIST_LAST
)
37 fromnext
= &(*fromnext
)->next
;
43 bool typesafe_dlist_member(const struct dlist_head
*head
,
44 const struct dlist_item
*item
)
46 const struct dlist_item
*fromhead
= head
->hitem
.next
;
47 const struct dlist_item
*fromitem
= item
->next
;
49 if (!item
->prev
|| !item
->next
)
52 while (fromhead
!= &head
->hitem
&& fromitem
!= item
) {
53 if (fromitem
== &head
->hitem
|| fromhead
== item
)
55 fromhead
= fromhead
->next
;
56 fromitem
= fromitem
->next
;
63 static void hash_consistency_check(struct thash_head
*head
)
66 struct thash_item
*item
, *prev
;
68 for (i
= 0; i
< HASH_SIZE(*head
); i
++) {
69 item
= head
->entries
[i
];
72 assert(HASH_KEY(*head
, item
->hashval
) == i
);
73 assert(!prev
|| item
->hashval
>= prev
->hashval
);
80 #define hash_consistency_check(x)
83 void typesafe_hash_grow(struct thash_head
*head
)
85 uint32_t newsize
= head
->count
, i
, j
;
86 uint8_t newshift
, delta
;
88 /* note hash_grow is called after head->count++, so newsize is
89 * guaranteed to be >= 1. So the minimum argument to builtin_ctz
90 * below is 2, which returns 1, and that makes newshift >= 2.
92 * Calling hash_grow with a zero head->count would result in a
93 * malformed hash table that has tabshift == 1.
95 assert(head
->count
> 0);
97 hash_consistency_check(head
);
99 newsize
|= newsize
>> 1;
100 newsize
|= newsize
>> 2;
101 newsize
|= newsize
>> 4;
102 newsize
|= newsize
>> 8;
103 newsize
|= newsize
>> 16;
105 newshift
= __builtin_ctz(newsize
) + 1;
107 if (head
->maxshift
&& newshift
> head
->maxshift
)
108 newshift
= head
->maxshift
;
109 if (newshift
== head
->tabshift
)
111 newsize
= _HASH_SIZE(newshift
);
113 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
114 sizeof(head
->entries
[0]) * newsize
);
115 memset(head
->entries
+ HASH_SIZE(*head
), 0,
116 sizeof(head
->entries
[0]) *
117 (newsize
- HASH_SIZE(*head
)));
119 delta
= newshift
- head
->tabshift
;
121 i
= HASH_SIZE(*head
);
125 struct thash_item
**apos
, *item
;
128 apos
= &head
->entries
[i
];
130 for (j
= 0; j
< (1U << delta
); j
++) {
134 head
->entries
[(i
<< delta
) + j
] = item
;
135 apos
= &head
->entries
[(i
<< delta
) + j
];
137 while ((item
= *apos
)) {
139 midbits
= _HASH_KEY(newshift
, item
->hashval
);
140 midbits
&= (1 << delta
) - 1;
149 head
->tabshift
= newshift
;
150 hash_consistency_check(head
);
153 void typesafe_hash_shrink(struct thash_head
*head
)
155 uint32_t newsize
= head
->count
, i
, j
;
156 uint8_t newshift
, delta
;
158 hash_consistency_check(head
);
161 XFREE(MTYPE_TYPEDHASH_BUCKET
, head
->entries
);
166 newsize
|= newsize
>> 1;
167 newsize
|= newsize
>> 2;
168 newsize
|= newsize
>> 4;
169 newsize
|= newsize
>> 8;
170 newsize
|= newsize
>> 16;
172 newshift
= __builtin_ctz(newsize
) + 1;
174 if (head
->minshift
&& newshift
< head
->minshift
)
175 newshift
= head
->minshift
;
176 if (newshift
== head
->tabshift
)
178 newsize
= _HASH_SIZE(newshift
);
180 delta
= head
->tabshift
- newshift
;
182 for (i
= 0; i
< newsize
; i
++) {
183 struct thash_item
**apos
= &head
->entries
[i
];
185 for (j
= 0; j
< (1U << delta
); j
++) {
186 *apos
= head
->entries
[(i
<< delta
) + j
];
188 apos
= &(*apos
)->next
;
191 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
192 sizeof(head
->entries
[0]) * newsize
);
193 head
->tabshift
= newshift
;
195 hash_consistency_check(head
);
200 static inline struct sskip_item
*sl_level_get(const struct sskip_item
*item
,
203 if (level
< SKIPLIST_OVERFLOW
)
204 return item
->next
[level
];
205 if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
206 return item
->next
[level
];
208 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
209 ptrval
&= UINTPTR_MAX
- 3;
210 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
211 return oflow
->next
[level
- SKIPLIST_OVERFLOW
];
214 static inline void sl_level_set(struct sskip_item
*item
, size_t level
,
215 struct sskip_item
*value
)
217 if (level
< SKIPLIST_OVERFLOW
)
218 item
->next
[level
] = value
;
219 else if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
220 item
->next
[level
] = value
;
222 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
223 ptrval
&= UINTPTR_MAX
- 3;
224 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
225 oflow
->next
[level
- SKIPLIST_OVERFLOW
] = value
;
229 struct sskip_item
*typesafe_skiplist_add(struct sskip_head
*head
,
230 struct sskip_item
*item
,
231 int (*cmpfn
)(const struct sskip_item
*a
,
232 const struct sskip_item
*b
))
234 size_t level
= SKIPLIST_MAXDEPTH
, newlevel
, auxlevel
;
235 struct sskip_item
*prev
= &head
->hitem
, *next
, *auxprev
, *auxnext
;
238 /* level / newlevel are 1-counted here */
239 newlevel
= __builtin_ctz(frr_weak_random()) + 1;
240 if (newlevel
> SKIPLIST_MAXDEPTH
)
241 newlevel
= SKIPLIST_MAXDEPTH
;
244 while (level
>= newlevel
) {
245 next
= sl_level_get(prev
, level
- 1);
250 cmpval
= cmpfn(next
, item
);
254 } else if (cmpval
== 0) {
260 /* check for duplicate item - could be removed if code doesn't rely
261 * on it, but not really work the complication. */
266 auxnext
= sl_level_get(auxprev
, auxlevel
);
268 while (auxnext
&& (cmpval
= cmpfn(auxnext
, item
)) < 0) {
270 auxnext
= sl_level_get(auxprev
, auxlevel
);
277 memset(item
, 0, sizeof(*item
));
278 if (newlevel
> SKIPLIST_EMBED
) {
279 struct sskip_overflow
*oflow
;
280 oflow
= XMALLOC(MTYPE_SKIPLIST_OFLOW
, sizeof(void *)
281 * (newlevel
- SKIPLIST_OVERFLOW
));
282 item
->next
[SKIPLIST_OVERFLOW
] = (struct sskip_item
*)
283 ((uintptr_t)oflow
| 1);
286 sl_level_set(item
, level
, next
);
287 sl_level_set(prev
, level
, item
);
288 /* level is now 0-counted and < newlevel*/
291 next
= sl_level_get(prev
, level
);
292 while (next
&& cmpfn(next
, item
) < 0) {
294 next
= sl_level_get(prev
, level
);
297 sl_level_set(item
, level
, next
);
298 sl_level_set(prev
, level
, item
);
303 /* NOTE: level counting below is 1-based since that makes the code simpler! */
305 const struct sskip_item
*typesafe_skiplist_find(
306 const struct sskip_head
*head
,
307 const struct sskip_item
*item
, int (*cmpfn
)(
308 const struct sskip_item
*a
,
309 const struct sskip_item
*b
))
311 size_t level
= SKIPLIST_MAXDEPTH
;
312 const struct sskip_item
*prev
= &head
->hitem
, *next
;
316 next
= sl_level_get(prev
, level
- 1);
321 cmpval
= cmpfn(next
, item
);
333 const struct sskip_item
*typesafe_skiplist_find_gteq(
334 const struct sskip_head
*head
,
335 const struct sskip_item
*item
, int (*cmpfn
)(
336 const struct sskip_item
*a
,
337 const struct sskip_item
*b
))
339 size_t level
= SKIPLIST_MAXDEPTH
;
340 const struct sskip_item
*prev
= &head
->hitem
, *next
;
344 next
= sl_level_get(prev
, level
- 1);
349 cmpval
= cmpfn(next
, item
);
361 const struct sskip_item
*typesafe_skiplist_find_lt(
362 const struct sskip_head
*head
,
363 const struct sskip_item
*item
, int (*cmpfn
)(
364 const struct sskip_item
*a
,
365 const struct sskip_item
*b
))
367 size_t level
= SKIPLIST_MAXDEPTH
;
368 const struct sskip_item
*prev
= &head
->hitem
, *next
, *best
= NULL
;
372 next
= sl_level_get(prev
, level
- 1);
377 cmpval
= cmpfn(next
, item
);
387 struct sskip_item
*typesafe_skiplist_del(
388 struct sskip_head
*head
, struct sskip_item
*item
,
389 int (*cmpfn
)(const struct sskip_item
*a
, const struct sskip_item
*b
))
391 size_t level
= SKIPLIST_MAXDEPTH
;
392 struct sskip_item
*prev
= &head
->hitem
, *next
;
397 next
= sl_level_get(prev
, level
- 1);
403 sl_level_set(prev
, level
- 1,
404 sl_level_get(item
, level
- 1));
409 cmpval
= cmpfn(next
, item
);
420 /* TBD: assert when trying to remove non-existing item? */
423 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
424 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
425 ptrval
&= UINTPTR_MAX
- 3;
426 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
427 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
429 memset(item
, 0, sizeof(*item
));
434 struct sskip_item
*typesafe_skiplist_pop(struct sskip_head
*head
)
436 size_t level
= SKIPLIST_MAXDEPTH
;
437 struct sskip_item
*prev
= &head
->hitem
, *next
, *item
;
439 item
= sl_level_get(prev
, 0);
446 next
= sl_level_get(prev
, level
);
450 sl_level_set(prev
, level
, sl_level_get(item
, level
));
455 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
456 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
457 ptrval
&= UINTPTR_MAX
- 3;
458 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
459 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
461 memset(item
, 0, sizeof(*item
));
469 static void heap_consistency_check(struct heap_head
*head
,
470 int (*cmpfn
)(const struct heap_item
*a
,
471 const struct heap_item
*b
),
474 uint32_t rghtpos
= pos
+ 1;
475 uint32_t downpos
= HEAP_NARY
* (pos
+ 1);
477 if (pos
+ 1 > ~0U / HEAP_NARY
)
480 if ((pos
& (HEAP_NARY
- 1)) != HEAP_NARY
- 1 && rghtpos
< head
->count
) {
481 assert(cmpfn(head
->array
[rghtpos
], head
->array
[pos
]) >= 0);
482 heap_consistency_check(head
, cmpfn
, rghtpos
);
484 if (downpos
< head
->count
) {
485 assert(cmpfn(head
->array
[downpos
], head
->array
[pos
]) >= 0);
486 heap_consistency_check(head
, cmpfn
, downpos
);
490 #define heap_consistency_check(head, cmpfn, pos)
493 void typesafe_heap_resize(struct heap_head
*head
, bool grow
)
498 newsize
= head
->arraysz
;
501 else if (newsize
< 262144)
502 newsize
+= newsize
/ 2;
503 else if (newsize
< 0xaaaa0000)
504 newsize
+= newsize
/ 3;
507 } else if (head
->count
> 0) {
508 newsize
= head
->count
;
510 XFREE(MTYPE_HEAP_ARRAY
, head
->array
);
515 newsize
+= HEAP_NARY
- 1;
516 newsize
&= ~(HEAP_NARY
- 1);
517 if (newsize
== head
->arraysz
)
520 head
->array
= XREALLOC(MTYPE_HEAP_ARRAY
, head
->array
,
521 newsize
* sizeof(struct heap_item
*));
522 head
->arraysz
= newsize
;
525 void typesafe_heap_pushdown(struct heap_head
*head
, uint32_t pos
,
526 struct heap_item
*item
,
527 int (*cmpfn
)(const struct heap_item
*a
,
528 const struct heap_item
*b
))
530 uint32_t rghtpos
, downpos
, moveto
;
533 /* rghtpos: neighbor to the "right", inside block of NARY.
534 * may be invalid if last in block, check nary_last()
535 * downpos: first neighbor in the "downwards" block further
540 /* make sure we can use the full 4G items */
541 downpos
= HEAP_NARY
* (pos
+ 1);
542 if (pos
+ 1 > ~0U / HEAP_NARY
)
543 /* multiplication overflowed. ~0U is guaranteed
544 * to be an invalid index; size limit is enforced in
549 /* only used on break */
552 #define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1)
553 if (downpos
>= head
->count
554 || cmpfn(head
->array
[downpos
], item
) >= 0) {
555 /* not moving down; either at end or down is >= item */
556 if (nary_last(pos
) || rghtpos
>= head
->count
557 || cmpfn(head
->array
[rghtpos
], item
) >= 0)
558 /* not moving right either - got our spot */
563 /* else: downpos is valid and < item. choose between down
564 * or right (if the latter is an option) */
565 } else if (nary_last(pos
) || cmpfn(head
->array
[rghtpos
],
566 head
->array
[downpos
]) >= 0)
572 head
->array
[pos
] = head
->array
[moveto
];
573 head
->array
[pos
]->index
= pos
;
577 head
->array
[moveto
] = item
;
578 item
->index
= moveto
;
580 heap_consistency_check(head
, cmpfn
, 0);
583 void typesafe_heap_pullup(struct heap_head
*head
, uint32_t pos
,
584 struct heap_item
*item
,
585 int (*cmpfn
)(const struct heap_item
*a
,
586 const struct heap_item
*b
))
591 if ((pos
& (HEAP_NARY
- 1)) == 0)
592 moveto
= pos
/ HEAP_NARY
- 1;
596 if (cmpfn(head
->array
[moveto
], item
) <= 0)
599 head
->array
[pos
] = head
->array
[moveto
];
600 head
->array
[pos
]->index
= pos
;
605 head
->array
[pos
] = item
;
608 heap_consistency_check(head
, cmpfn
, 0);