2 * Copyright (c) 2019 David Lamparter, for NetDEF, Inc.
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.
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.
29 DEFINE_MTYPE_STATIC(LIB
, TYPEDHASH_BUCKET
, "Typed-hash bucket");
30 DEFINE_MTYPE_STATIC(LIB
, SKIPLIST_OFLOW
, "Skiplist overflow");
31 DEFINE_MTYPE_STATIC(LIB
, HEAP_ARRAY
, "Typed-heap array");
33 struct slist_item typesafe_slist_sentinel
= { NULL
};
35 bool typesafe_list_member(const struct slist_head
*head
,
36 const struct slist_item
*item
)
38 struct slist_item
*fromhead
= head
->first
;
39 struct slist_item
**fromnext
= (struct slist_item
**)&item
->next
;
41 while (fromhead
!= _SLIST_LAST
) {
42 if (fromhead
== item
|| fromnext
== head
->last_next
)
45 fromhead
= fromhead
->next
;
46 if (!*fromnext
|| *fromnext
== _SLIST_LAST
)
48 fromnext
= &(*fromnext
)->next
;
54 bool typesafe_dlist_member(const struct dlist_head
*head
,
55 const struct dlist_item
*item
)
57 const struct dlist_item
*fromhead
= head
->hitem
.next
;
58 const struct dlist_item
*fromitem
= item
->next
;
60 if (!item
->prev
|| !item
->next
)
63 while (fromhead
!= &head
->hitem
&& fromitem
!= item
) {
64 if (fromitem
== &head
->hitem
|| fromhead
== item
)
66 fromhead
= fromhead
->next
;
67 fromitem
= fromitem
->next
;
74 static void hash_consistency_check(struct thash_head
*head
)
77 struct thash_item
*item
, *prev
;
79 for (i
= 0; i
< HASH_SIZE(*head
); i
++) {
80 item
= head
->entries
[i
];
83 assert(HASH_KEY(*head
, item
->hashval
) == i
);
84 assert(!prev
|| item
->hashval
>= prev
->hashval
);
91 #define hash_consistency_check(x)
94 void typesafe_hash_grow(struct thash_head
*head
)
96 uint32_t newsize
= head
->count
, i
, j
;
97 uint8_t newshift
, delta
;
99 hash_consistency_check(head
);
101 newsize
|= newsize
>> 1;
102 newsize
|= newsize
>> 2;
103 newsize
|= newsize
>> 4;
104 newsize
|= newsize
>> 8;
105 newsize
|= newsize
>> 16;
107 newshift
= __builtin_ctz(newsize
) + 1;
109 if (head
->maxshift
&& newshift
> head
->maxshift
)
110 newshift
= head
->maxshift
;
111 if (newshift
== head
->tabshift
)
113 newsize
= _HASH_SIZE(newshift
);
115 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
116 sizeof(head
->entries
[0]) * newsize
);
117 memset(head
->entries
+ HASH_SIZE(*head
), 0,
118 sizeof(head
->entries
[0]) *
119 (newsize
- HASH_SIZE(*head
)));
121 delta
= newshift
- head
->tabshift
;
123 i
= HASH_SIZE(*head
);
127 struct thash_item
**apos
, *item
;
130 apos
= &head
->entries
[i
];
132 for (j
= 0; j
< (1U << delta
); j
++) {
136 head
->entries
[(i
<< delta
) + j
] = item
;
137 apos
= &head
->entries
[(i
<< delta
) + j
];
139 while ((item
= *apos
)) {
141 midbits
= _HASH_KEY(newshift
, item
->hashval
);
142 midbits
&= (1 << delta
) - 1;
151 head
->tabshift
= newshift
;
152 hash_consistency_check(head
);
155 void typesafe_hash_shrink(struct thash_head
*head
)
157 uint32_t newsize
= head
->count
, i
, j
;
158 uint8_t newshift
, delta
;
160 hash_consistency_check(head
);
163 XFREE(MTYPE_TYPEDHASH_BUCKET
, head
->entries
);
168 newsize
|= newsize
>> 1;
169 newsize
|= newsize
>> 2;
170 newsize
|= newsize
>> 4;
171 newsize
|= newsize
>> 8;
172 newsize
|= newsize
>> 16;
174 newshift
= __builtin_ctz(newsize
) + 1;
176 if (head
->minshift
&& newshift
< head
->minshift
)
177 newshift
= head
->minshift
;
178 if (newshift
== head
->tabshift
)
180 newsize
= _HASH_SIZE(newshift
);
182 delta
= head
->tabshift
- newshift
;
184 for (i
= 0; i
< newsize
; i
++) {
185 struct thash_item
**apos
= &head
->entries
[i
];
187 for (j
= 0; j
< (1U << delta
); j
++) {
188 *apos
= head
->entries
[(i
<< delta
) + j
];
190 apos
= &(*apos
)->next
;
193 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
194 sizeof(head
->entries
[0]) * newsize
);
195 head
->tabshift
= newshift
;
197 hash_consistency_check(head
);
202 static inline struct sskip_item
*sl_level_get(const struct sskip_item
*item
,
205 if (level
< SKIPLIST_OVERFLOW
)
206 return item
->next
[level
];
207 if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
208 return item
->next
[level
];
210 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
211 ptrval
&= UINTPTR_MAX
- 3;
212 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
213 return oflow
->next
[level
- SKIPLIST_OVERFLOW
];
216 static inline void sl_level_set(struct sskip_item
*item
, size_t level
,
217 struct sskip_item
*value
)
219 if (level
< SKIPLIST_OVERFLOW
)
220 item
->next
[level
] = value
;
221 else if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
222 item
->next
[level
] = value
;
224 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
225 ptrval
&= UINTPTR_MAX
- 3;
226 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
227 oflow
->next
[level
- SKIPLIST_OVERFLOW
] = value
;
231 struct sskip_item
*typesafe_skiplist_add(struct sskip_head
*head
,
232 struct sskip_item
*item
,
233 int (*cmpfn
)(const struct sskip_item
*a
,
234 const struct sskip_item
*b
))
236 size_t level
= SKIPLIST_MAXDEPTH
, newlevel
, auxlevel
;
237 struct sskip_item
*prev
= &head
->hitem
, *next
, *auxprev
, *auxnext
;
240 /* level / newlevel are 1-counted here */
241 newlevel
= __builtin_ctz(frr_weak_random()) + 1;
242 if (newlevel
> SKIPLIST_MAXDEPTH
)
243 newlevel
= SKIPLIST_MAXDEPTH
;
246 while (level
>= newlevel
) {
247 next
= sl_level_get(prev
, level
- 1);
252 cmpval
= cmpfn(next
, item
);
256 } else if (cmpval
== 0) {
262 /* check for duplicate item - could be removed if code doesn't rely
263 * on it, but not really work the complication. */
268 auxnext
= sl_level_get(auxprev
, auxlevel
);
270 while (auxnext
&& (cmpval
= cmpfn(auxnext
, item
)) < 0) {
272 auxnext
= sl_level_get(auxprev
, auxlevel
);
279 memset(item
, 0, sizeof(*item
));
280 if (newlevel
> SKIPLIST_EMBED
) {
281 struct sskip_overflow
*oflow
;
282 oflow
= XMALLOC(MTYPE_SKIPLIST_OFLOW
, sizeof(void *)
283 * (newlevel
- SKIPLIST_OVERFLOW
));
284 item
->next
[SKIPLIST_OVERFLOW
] = (struct sskip_item
*)
285 ((uintptr_t)oflow
| 1);
288 sl_level_set(item
, level
, next
);
289 sl_level_set(prev
, level
, item
);
290 /* level is now 0-counted and < newlevel*/
293 next
= sl_level_get(prev
, level
);
294 while (next
&& cmpfn(next
, item
) < 0) {
296 next
= sl_level_get(prev
, level
);
299 sl_level_set(item
, level
, next
);
300 sl_level_set(prev
, level
, item
);
305 /* NOTE: level counting below is 1-based since that makes the code simpler! */
307 const struct sskip_item
*typesafe_skiplist_find(
308 const struct sskip_head
*head
,
309 const struct sskip_item
*item
, int (*cmpfn
)(
310 const struct sskip_item
*a
,
311 const struct sskip_item
*b
))
313 size_t level
= SKIPLIST_MAXDEPTH
;
314 const struct sskip_item
*prev
= &head
->hitem
, *next
;
318 next
= sl_level_get(prev
, level
- 1);
323 cmpval
= cmpfn(next
, item
);
335 const struct sskip_item
*typesafe_skiplist_find_gteq(
336 const struct sskip_head
*head
,
337 const struct sskip_item
*item
, int (*cmpfn
)(
338 const struct sskip_item
*a
,
339 const struct sskip_item
*b
))
341 size_t level
= SKIPLIST_MAXDEPTH
;
342 const struct sskip_item
*prev
= &head
->hitem
, *next
;
346 next
= sl_level_get(prev
, level
- 1);
351 cmpval
= cmpfn(next
, item
);
363 const struct sskip_item
*typesafe_skiplist_find_lt(
364 const struct sskip_head
*head
,
365 const struct sskip_item
*item
, int (*cmpfn
)(
366 const struct sskip_item
*a
,
367 const struct sskip_item
*b
))
369 size_t level
= SKIPLIST_MAXDEPTH
;
370 const struct sskip_item
*prev
= &head
->hitem
, *next
, *best
= NULL
;
374 next
= sl_level_get(prev
, level
- 1);
379 cmpval
= cmpfn(next
, item
);
389 struct sskip_item
*typesafe_skiplist_del(
390 struct sskip_head
*head
, struct sskip_item
*item
,
391 int (*cmpfn
)(const struct sskip_item
*a
, const struct sskip_item
*b
))
393 size_t level
= SKIPLIST_MAXDEPTH
;
394 struct sskip_item
*prev
= &head
->hitem
, *next
;
399 next
= sl_level_get(prev
, level
- 1);
405 sl_level_set(prev
, level
- 1,
406 sl_level_get(item
, level
- 1));
411 cmpval
= cmpfn(next
, item
);
422 /* TBD: assert when trying to remove non-existing item? */
425 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
426 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
427 ptrval
&= UINTPTR_MAX
- 3;
428 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
429 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
431 memset(item
, 0, sizeof(*item
));
436 struct sskip_item
*typesafe_skiplist_pop(struct sskip_head
*head
)
438 size_t level
= SKIPLIST_MAXDEPTH
;
439 struct sskip_item
*prev
= &head
->hitem
, *next
, *item
;
441 item
= sl_level_get(prev
, 0);
448 next
= sl_level_get(prev
, level
);
452 sl_level_set(prev
, level
, sl_level_get(item
, level
));
457 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
458 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
459 ptrval
&= UINTPTR_MAX
- 3;
460 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
461 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
463 memset(item
, 0, sizeof(*item
));
471 static void heap_consistency_check(struct heap_head
*head
,
472 int (*cmpfn
)(const struct heap_item
*a
,
473 const struct heap_item
*b
),
476 uint32_t rghtpos
= pos
+ 1;
477 uint32_t downpos
= HEAP_NARY
* (pos
+ 1);
479 if (pos
+ 1 > ~0U / HEAP_NARY
)
482 if ((pos
& (HEAP_NARY
- 1)) != HEAP_NARY
- 1 && rghtpos
< head
->count
) {
483 assert(cmpfn(head
->array
[rghtpos
], head
->array
[pos
]) >= 0);
484 heap_consistency_check(head
, cmpfn
, rghtpos
);
486 if (downpos
< head
->count
) {
487 assert(cmpfn(head
->array
[downpos
], head
->array
[pos
]) >= 0);
488 heap_consistency_check(head
, cmpfn
, downpos
);
492 #define heap_consistency_check(head, cmpfn, pos)
495 void typesafe_heap_resize(struct heap_head
*head
, bool grow
)
500 newsize
= head
->arraysz
;
503 else if (newsize
< 262144)
504 newsize
+= newsize
/ 2;
505 else if (newsize
< 0xaaaa0000)
506 newsize
+= newsize
/ 3;
509 } else if (head
->count
> 0) {
510 newsize
= head
->count
;
512 XFREE(MTYPE_HEAP_ARRAY
, head
->array
);
517 newsize
+= HEAP_NARY
- 1;
518 newsize
&= ~(HEAP_NARY
- 1);
519 if (newsize
== head
->arraysz
)
522 head
->array
= XREALLOC(MTYPE_HEAP_ARRAY
, head
->array
,
523 newsize
* sizeof(struct heap_item
*));
524 head
->arraysz
= newsize
;
527 void typesafe_heap_pushdown(struct heap_head
*head
, uint32_t pos
,
528 struct heap_item
*item
,
529 int (*cmpfn
)(const struct heap_item
*a
,
530 const struct heap_item
*b
))
532 uint32_t rghtpos
, downpos
, moveto
;
535 /* rghtpos: neighbor to the "right", inside block of NARY.
536 * may be invalid if last in block, check nary_last()
537 * downpos: first neighbor in the "downwards" block further
542 /* make sure we can use the full 4G items */
543 downpos
= HEAP_NARY
* (pos
+ 1);
544 if (pos
+ 1 > ~0U / HEAP_NARY
)
545 /* multiplication overflowed. ~0U is guaranteed
546 * to be an invalid index; size limit is enforced in
551 /* only used on break */
554 #define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1)
555 if (downpos
>= head
->count
556 || cmpfn(head
->array
[downpos
], item
) >= 0) {
557 /* not moving down; either at end or down is >= item */
558 if (nary_last(pos
) || rghtpos
>= head
->count
559 || cmpfn(head
->array
[rghtpos
], item
) >= 0)
560 /* not moving right either - got our spot */
565 /* else: downpos is valid and < item. choose between down
566 * or right (if the latter is an option) */
567 } else if (nary_last(pos
) || cmpfn(head
->array
[rghtpos
],
568 head
->array
[downpos
]) >= 0)
574 head
->array
[pos
] = head
->array
[moveto
];
575 head
->array
[pos
]->index
= pos
;
579 head
->array
[moveto
] = item
;
580 item
->index
= moveto
;
582 heap_consistency_check(head
, cmpfn
, 0);
585 void typesafe_heap_pullup(struct heap_head
*head
, uint32_t pos
,
586 struct heap_item
*item
,
587 int (*cmpfn
)(const struct heap_item
*a
,
588 const struct heap_item
*b
))
593 if ((pos
& (HEAP_NARY
- 1)) == 0)
594 moveto
= pos
/ HEAP_NARY
- 1;
598 if (cmpfn(head
->array
[moveto
], item
) <= 0)
601 head
->array
[pos
] = head
->array
[moveto
];
602 head
->array
[pos
]->index
= pos
;
607 head
->array
[pos
] = item
;
610 heap_consistency_check(head
, cmpfn
, 0);