]>
git.proxmox.com Git - mirror_frr.git/blob - lib/typesafe.c
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.
27 DEFINE_MTYPE_STATIC(LIB
, TYPEDHASH_BUCKET
, "Typed-hash bucket")
28 DEFINE_MTYPE_STATIC(LIB
, SKIPLIST_OFLOW
, "Skiplist overflow")
29 DEFINE_MTYPE_STATIC(LIB
, HEAP_ARRAY
, "Typed-heap array")
32 static void hash_consistency_check(struct thash_head
*head
)
35 struct thash_item
*item
, *prev
;
37 for (i
= 0; i
< HASH_SIZE(*head
); i
++) {
38 item
= head
->entries
[i
];
41 assert(HASH_KEY(*head
, item
->hashval
) == i
);
42 assert(!prev
|| item
->hashval
>= prev
->hashval
);
49 #define hash_consistency_check(x)
52 void typesafe_hash_grow(struct thash_head
*head
)
54 uint32_t newsize
= head
->count
, i
, j
;
55 uint8_t newshift
, delta
;
57 hash_consistency_check(head
);
59 newsize
|= newsize
>> 1;
60 newsize
|= newsize
>> 2;
61 newsize
|= newsize
>> 4;
62 newsize
|= newsize
>> 8;
63 newsize
|= newsize
>> 16;
65 newshift
= __builtin_ctz(newsize
) + 1;
67 if (head
->maxshift
&& newshift
> head
->maxshift
)
68 newshift
= head
->maxshift
;
69 if (newshift
== head
->tabshift
)
71 newsize
= _HASH_SIZE(newshift
);
73 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
74 sizeof(head
->entries
[0]) * newsize
);
75 memset(head
->entries
+ HASH_SIZE(*head
), 0,
76 sizeof(head
->entries
[0]) *
77 (newsize
- HASH_SIZE(*head
)));
79 delta
= newshift
- head
->tabshift
;
85 struct thash_item
**apos
, *item
;
88 apos
= &head
->entries
[i
];
90 for (j
= 0; j
< (1U << delta
); j
++) {
94 head
->entries
[(i
<< delta
) + j
] = item
;
95 apos
= &head
->entries
[(i
<< delta
) + j
];
97 while ((item
= *apos
)) {
99 midbits
= _HASH_KEY(newshift
, item
->hashval
);
100 midbits
&= (1 << delta
) - 1;
109 head
->tabshift
= newshift
;
110 hash_consistency_check(head
);
113 void typesafe_hash_shrink(struct thash_head
*head
)
115 uint32_t newsize
= head
->count
, i
, j
;
116 uint8_t newshift
, delta
;
118 hash_consistency_check(head
);
121 XFREE(MTYPE_TYPEDHASH_BUCKET
, head
->entries
);
126 newsize
|= newsize
>> 1;
127 newsize
|= newsize
>> 2;
128 newsize
|= newsize
>> 4;
129 newsize
|= newsize
>> 8;
130 newsize
|= newsize
>> 16;
132 newshift
= __builtin_ctz(newsize
) + 1;
134 if (head
->minshift
&& newshift
< head
->minshift
)
135 newshift
= head
->minshift
;
136 if (newshift
== head
->tabshift
)
138 newsize
= _HASH_SIZE(newshift
);
140 delta
= head
->tabshift
- newshift
;
142 for (i
= 0; i
< newsize
; i
++) {
143 struct thash_item
**apos
= &head
->entries
[i
];
145 for (j
= 0; j
< (1U << delta
); j
++) {
146 *apos
= head
->entries
[(i
<< delta
) + j
];
148 apos
= &(*apos
)->next
;
151 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
152 sizeof(head
->entries
[0]) * newsize
);
153 head
->tabshift
= newshift
;
155 hash_consistency_check(head
);
160 static inline struct sskip_item
*sl_level_get(struct sskip_item
*item
,
163 if (level
< SKIPLIST_OVERFLOW
)
164 return item
->next
[level
];
165 if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
166 return item
->next
[level
];
168 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
169 ptrval
&= UINTPTR_MAX
- 3;
170 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
171 return oflow
->next
[level
- SKIPLIST_OVERFLOW
];
174 static inline void sl_level_set(struct sskip_item
*item
, size_t level
,
175 struct sskip_item
*value
)
177 if (level
< SKIPLIST_OVERFLOW
)
178 item
->next
[level
] = value
;
179 else if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
180 item
->next
[level
] = value
;
182 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
183 ptrval
&= UINTPTR_MAX
- 3;
184 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
185 oflow
->next
[level
- SKIPLIST_OVERFLOW
] = value
;
189 struct sskip_item
*typesafe_skiplist_add(struct sskip_head
*head
,
190 struct sskip_item
*item
,
191 int (*cmpfn
)(const struct sskip_item
*a
,
192 const struct sskip_item
*b
))
194 size_t level
= SKIPLIST_MAXDEPTH
, newlevel
, auxlevel
;
195 struct sskip_item
*prev
= &head
->hitem
, *next
, *auxprev
, *auxnext
;
198 /* level / newlevel are 1-counted here */
199 newlevel
= __builtin_ctz(random()) + 1;
200 if (newlevel
> SKIPLIST_MAXDEPTH
)
201 newlevel
= SKIPLIST_MAXDEPTH
;
204 while (level
>= newlevel
) {
205 next
= sl_level_get(prev
, level
- 1);
210 cmpval
= cmpfn(next
, item
);
214 } else if (cmpval
== 0) {
220 /* check for duplicate item - could be removed if code doesn't rely
221 * on it, but not really work the complication. */
226 auxnext
= sl_level_get(auxprev
, auxlevel
);
228 while (auxnext
&& (cmpval
= cmpfn(auxnext
, item
)) < 0) {
230 auxnext
= sl_level_get(auxprev
, auxlevel
);
237 memset(item
, 0, sizeof(*item
));
238 if (newlevel
> SKIPLIST_EMBED
) {
239 struct sskip_overflow
*oflow
;
240 oflow
= XMALLOC(MTYPE_SKIPLIST_OFLOW
, sizeof(void *)
241 * (newlevel
- SKIPLIST_OVERFLOW
));
242 item
->next
[SKIPLIST_OVERFLOW
] = (struct sskip_item
*)
243 ((uintptr_t)oflow
| 1);
246 sl_level_set(item
, level
, next
);
247 sl_level_set(prev
, level
, item
);
248 /* level is now 0-counted and < newlevel*/
251 next
= sl_level_get(prev
, level
);
252 while (next
&& cmpfn(next
, item
) < 0) {
254 next
= sl_level_get(prev
, level
);
257 sl_level_set(item
, level
, next
);
258 sl_level_set(prev
, level
, item
);
263 /* NOTE: level counting below is 1-based since that makes the code simpler! */
265 struct sskip_item
*typesafe_skiplist_find(struct sskip_head
*head
,
266 const struct sskip_item
*item
, int (*cmpfn
)(
267 const struct sskip_item
*a
,
268 const struct sskip_item
*b
))
270 size_t level
= SKIPLIST_MAXDEPTH
;
271 struct sskip_item
*prev
= &head
->hitem
, *next
;
275 next
= sl_level_get(prev
, level
- 1);
280 cmpval
= cmpfn(next
, item
);
292 struct sskip_item
*typesafe_skiplist_find_gteq(struct sskip_head
*head
,
293 const struct sskip_item
*item
, int (*cmpfn
)(
294 const struct sskip_item
*a
,
295 const struct sskip_item
*b
))
297 size_t level
= SKIPLIST_MAXDEPTH
;
298 struct sskip_item
*prev
= &head
->hitem
, *next
;
302 next
= sl_level_get(prev
, level
- 1);
307 cmpval
= cmpfn(next
, item
);
319 struct sskip_item
*typesafe_skiplist_find_lt(struct sskip_head
*head
,
320 const struct sskip_item
*item
, int (*cmpfn
)(
321 const struct sskip_item
*a
,
322 const struct sskip_item
*b
))
324 size_t level
= SKIPLIST_MAXDEPTH
;
325 struct sskip_item
*prev
= &head
->hitem
, *next
, *best
= NULL
;
329 next
= sl_level_get(prev
, level
- 1);
334 cmpval
= cmpfn(next
, item
);
344 struct sskip_item
*typesafe_skiplist_del(
345 struct sskip_head
*head
, struct sskip_item
*item
,
346 int (*cmpfn
)(const struct sskip_item
*a
, const struct sskip_item
*b
))
348 size_t level
= SKIPLIST_MAXDEPTH
;
349 struct sskip_item
*prev
= &head
->hitem
, *next
;
354 next
= sl_level_get(prev
, level
- 1);
360 sl_level_set(prev
, level
- 1,
361 sl_level_get(item
, level
- 1));
366 cmpval
= cmpfn(next
, item
);
377 /* TBD: assert when trying to remove non-existing item? */
380 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
381 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
382 ptrval
&= UINTPTR_MAX
- 3;
383 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
384 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
386 memset(item
, 0, sizeof(*item
));
391 struct sskip_item
*typesafe_skiplist_pop(struct sskip_head
*head
)
393 size_t level
= SKIPLIST_MAXDEPTH
;
394 struct sskip_item
*prev
= &head
->hitem
, *next
, *item
;
396 item
= sl_level_get(prev
, 0);
403 next
= sl_level_get(prev
, level
);
407 sl_level_set(prev
, level
, sl_level_get(item
, level
));
412 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
413 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
414 ptrval
&= UINTPTR_MAX
- 3;
415 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
416 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
418 memset(item
, 0, sizeof(*item
));
426 static void heap_consistency_check(struct heap_head
*head
,
427 int (*cmpfn
)(const struct heap_item
*a
,
428 const struct heap_item
*b
),
431 uint32_t rghtpos
= pos
+ 1;
432 uint32_t downpos
= HEAP_NARY
* (pos
+ 1);
434 if (pos
+ 1 > ~0U / HEAP_NARY
)
437 if ((pos
& (HEAP_NARY
- 1)) != HEAP_NARY
- 1 && rghtpos
< head
->count
) {
438 assert(cmpfn(head
->array
[rghtpos
], head
->array
[pos
]) >= 0);
439 heap_consistency_check(head
, cmpfn
, rghtpos
);
441 if (downpos
< head
->count
) {
442 assert(cmpfn(head
->array
[downpos
], head
->array
[pos
]) >= 0);
443 heap_consistency_check(head
, cmpfn
, downpos
);
447 #define heap_consistency_check(head, cmpfn, pos)
450 void typesafe_heap_resize(struct heap_head
*head
, bool grow
)
455 newsize
= head
->arraysz
;
458 else if (newsize
< 262144)
459 newsize
+= newsize
/ 2;
460 else if (newsize
< 0xaaaa0000)
461 newsize
+= newsize
/ 3;
464 } else if (head
->count
> 0) {
465 newsize
= head
->count
;
467 XFREE(MTYPE_HEAP_ARRAY
, head
->array
);
472 newsize
+= HEAP_NARY
- 1;
473 newsize
&= ~(HEAP_NARY
- 1);
474 if (newsize
== head
->arraysz
)
477 head
->array
= XREALLOC(MTYPE_HEAP_ARRAY
, head
->array
,
478 newsize
* sizeof(struct heap_item
*));
479 head
->arraysz
= newsize
;
482 void typesafe_heap_pushdown(struct heap_head
*head
, uint32_t pos
,
483 struct heap_item
*item
,
484 int (*cmpfn
)(const struct heap_item
*a
,
485 const struct heap_item
*b
))
487 uint32_t rghtpos
, downpos
, moveto
;
490 /* rghtpos: neighbor to the "right", inside block of NARY.
491 * may be invalid if last in block, check nary_last()
492 * downpos: first neighbor in the "downwards" block further
497 /* make sure we can use the full 4G items */
498 downpos
= HEAP_NARY
* (pos
+ 1);
499 if (pos
+ 1 > ~0U / HEAP_NARY
)
500 /* multiplication overflowed. ~0U is guaranteed
501 * to be an invalid index; size limit is enforced in
506 /* only used on break */
509 #define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1)
510 if (downpos
>= head
->count
511 || cmpfn(head
->array
[downpos
], item
) >= 0) {
512 /* not moving down; either at end or down is >= item */
513 if (nary_last(pos
) || rghtpos
>= head
->count
514 || cmpfn(head
->array
[rghtpos
], item
) >= 0)
515 /* not moving right either - got our spot */
520 /* else: downpos is valid and < item. choose between down
521 * or right (if the latter is an option) */
522 } else if (nary_last(pos
) || cmpfn(head
->array
[rghtpos
],
523 head
->array
[downpos
]) >= 0)
529 head
->array
[pos
] = head
->array
[moveto
];
530 head
->array
[pos
]->index
= pos
;
534 head
->array
[moveto
] = item
;
535 item
->index
= moveto
;
537 heap_consistency_check(head
, cmpfn
, 0);
540 void typesafe_heap_pullup(struct heap_head
*head
, uint32_t pos
,
541 struct heap_item
*item
,
542 int (*cmpfn
)(const struct heap_item
*a
,
543 const struct heap_item
*b
))
548 if ((pos
& (HEAP_NARY
- 1)) == 0)
549 moveto
= pos
/ HEAP_NARY
- 1;
553 if (cmpfn(head
->array
[moveto
], item
) <= 0)
556 head
->array
[pos
] = head
->array
[moveto
];
557 head
->array
[pos
]->index
= pos
;
562 head
->array
[pos
] = item
;
565 heap_consistency_check(head
, cmpfn
, 0);