]>
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.
23 DEFINE_MTYPE_STATIC(LIB
, TYPEDHASH_BUCKET
, "Typed-hash bucket")
24 DEFINE_MTYPE_STATIC(LIB
, SKIPLIST_OFLOW
, "Skiplist overflow")
25 DEFINE_MTYPE_STATIC(LIB
, HEAP_ARRAY
, "Typed-heap array")
28 static void hash_consistency_check(struct thash_head
*head
)
31 struct thash_item
*item
, *prev
;
33 for (i
= 0; i
< HASH_SIZE(*head
); i
++) {
34 item
= head
->entries
[i
];
37 assert(HASH_KEY(*head
, item
->hashval
) == i
);
38 assert(!prev
|| item
->hashval
>= prev
->hashval
);
45 #define hash_consistency_check(x)
48 void typesafe_hash_grow(struct thash_head
*head
)
50 uint32_t newsize
= head
->count
, i
, j
;
51 uint8_t newshift
, delta
;
53 hash_consistency_check(head
);
55 newsize
|= newsize
>> 1;
56 newsize
|= newsize
>> 2;
57 newsize
|= newsize
>> 4;
58 newsize
|= newsize
>> 8;
59 newsize
|= newsize
>> 16;
61 newshift
= __builtin_ctz(newsize
) + 1;
63 if (head
->maxshift
&& newshift
> head
->maxshift
)
64 newshift
= head
->maxshift
;
65 if (newshift
== head
->tabshift
)
67 newsize
= _HASH_SIZE(newshift
);
69 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
70 sizeof(head
->entries
[0]) * newsize
);
71 memset(head
->entries
+ HASH_SIZE(*head
), 0,
72 sizeof(head
->entries
[0]) *
73 (newsize
- HASH_SIZE(*head
)));
75 delta
= newshift
- head
->tabshift
;
81 struct thash_item
**apos
, *item
;
84 apos
= &head
->entries
[i
];
86 for (j
= 0; j
< (1U << delta
); j
++) {
90 head
->entries
[(i
<< delta
) + j
] = item
;
91 apos
= &head
->entries
[(i
<< delta
) + j
];
93 while ((item
= *apos
)) {
95 midbits
= _HASH_KEY(newshift
, item
->hashval
);
96 midbits
&= (1 << delta
) - 1;
105 head
->tabshift
= newshift
;
106 hash_consistency_check(head
);
109 void typesafe_hash_shrink(struct thash_head
*head
)
111 uint32_t newsize
= head
->count
, i
, j
;
112 uint8_t newshift
, delta
;
114 hash_consistency_check(head
);
117 XFREE(MTYPE_TYPEDHASH_BUCKET
, head
->entries
);
122 newsize
|= newsize
>> 1;
123 newsize
|= newsize
>> 2;
124 newsize
|= newsize
>> 4;
125 newsize
|= newsize
>> 8;
126 newsize
|= newsize
>> 16;
128 newshift
= __builtin_ctz(newsize
) + 1;
130 if (head
->minshift
&& newshift
< head
->minshift
)
131 newshift
= head
->minshift
;
132 if (newshift
== head
->tabshift
)
134 newsize
= _HASH_SIZE(newshift
);
136 delta
= head
->tabshift
- newshift
;
138 for (i
= 0; i
< newsize
; i
++) {
139 struct thash_item
**apos
= &head
->entries
[i
];
141 for (j
= 0; j
< (1U << delta
); j
++) {
142 *apos
= head
->entries
[(i
<< delta
) + j
];
144 apos
= &(*apos
)->next
;
147 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
148 sizeof(head
->entries
[0]) * newsize
);
149 head
->tabshift
= newshift
;
151 hash_consistency_check(head
);
156 static inline struct sskip_item
*sl_level_get(struct sskip_item
*item
,
159 if (level
< SKIPLIST_OVERFLOW
)
160 return item
->next
[level
];
161 if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
162 return item
->next
[level
];
164 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
165 ptrval
&= UINTPTR_MAX
- 3;
166 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
167 return oflow
->next
[level
- SKIPLIST_OVERFLOW
];
170 static inline void sl_level_set(struct sskip_item
*item
, size_t level
,
171 struct sskip_item
*value
)
173 if (level
< SKIPLIST_OVERFLOW
)
174 item
->next
[level
] = value
;
175 else if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
176 item
->next
[level
] = value
;
178 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
179 ptrval
&= UINTPTR_MAX
- 3;
180 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
181 oflow
->next
[level
- SKIPLIST_OVERFLOW
] = value
;
185 struct sskip_item
*typesafe_skiplist_add(struct sskip_head
*head
,
186 struct sskip_item
*item
,
187 int (*cmpfn
)(const struct sskip_item
*a
,
188 const struct sskip_item
*b
))
190 size_t level
= SKIPLIST_MAXDEPTH
, newlevel
, auxlevel
;
191 struct sskip_item
*prev
= &head
->hitem
, *next
, *auxprev
, *auxnext
;
194 /* level / newlevel are 1-counted here */
195 newlevel
= __builtin_ctz(random()) + 1;
196 if (newlevel
> SKIPLIST_MAXDEPTH
)
197 newlevel
= SKIPLIST_MAXDEPTH
;
200 while (level
>= newlevel
) {
201 next
= sl_level_get(prev
, level
- 1);
206 cmpval
= cmpfn(next
, item
);
210 } else if (cmpval
== 0) {
216 /* check for duplicate item - could be removed if code doesn't rely
217 * on it, but not really work the complication. */
222 auxnext
= sl_level_get(auxprev
, auxlevel
);
224 while (auxnext
&& (cmpval
= cmpfn(auxnext
, item
)) < 0) {
226 auxnext
= sl_level_get(auxprev
, auxlevel
);
233 memset(item
, 0, sizeof(*item
));
234 if (newlevel
> SKIPLIST_EMBED
) {
235 struct sskip_overflow
*oflow
;
236 oflow
= XMALLOC(MTYPE_SKIPLIST_OFLOW
, sizeof(void *)
237 * (newlevel
- SKIPLIST_OVERFLOW
));
238 item
->next
[SKIPLIST_OVERFLOW
] = (struct sskip_item
*)
239 ((uintptr_t)oflow
| 1);
242 sl_level_set(item
, level
, next
);
243 sl_level_set(prev
, level
, item
);
244 /* level is now 0-counted and < newlevel*/
247 next
= sl_level_get(prev
, level
);
248 while (next
&& cmpfn(next
, item
) < 0) {
250 next
= sl_level_get(prev
, level
);
253 sl_level_set(item
, level
, next
);
254 sl_level_set(prev
, level
, item
);
259 /* NOTE: level counting below is 1-based since that makes the code simpler! */
261 struct sskip_item
*typesafe_skiplist_find(struct sskip_head
*head
,
262 const struct sskip_item
*item
, int (*cmpfn
)(
263 const struct sskip_item
*a
,
264 const struct sskip_item
*b
))
266 size_t level
= SKIPLIST_MAXDEPTH
;
267 struct sskip_item
*prev
= &head
->hitem
, *next
;
271 next
= sl_level_get(prev
, level
- 1);
276 cmpval
= cmpfn(next
, item
);
288 struct sskip_item
*typesafe_skiplist_find_gteq(struct sskip_head
*head
,
289 const struct sskip_item
*item
, int (*cmpfn
)(
290 const struct sskip_item
*a
,
291 const struct sskip_item
*b
))
293 size_t level
= SKIPLIST_MAXDEPTH
;
294 struct sskip_item
*prev
= &head
->hitem
, *next
;
298 next
= sl_level_get(prev
, level
- 1);
303 cmpval
= cmpfn(next
, item
);
315 struct sskip_item
*typesafe_skiplist_find_lt(struct sskip_head
*head
,
316 const struct sskip_item
*item
, int (*cmpfn
)(
317 const struct sskip_item
*a
,
318 const struct sskip_item
*b
))
320 size_t level
= SKIPLIST_MAXDEPTH
;
321 struct sskip_item
*prev
= &head
->hitem
, *next
, *best
= NULL
;
325 next
= sl_level_get(prev
, level
- 1);
330 cmpval
= cmpfn(next
, item
);
340 void typesafe_skiplist_del(struct sskip_head
*head
, struct sskip_item
*item
,
341 int (*cmpfn
)(const struct sskip_item
*a
,
342 const struct sskip_item
*b
))
344 size_t level
= SKIPLIST_MAXDEPTH
;
345 struct sskip_item
*prev
= &head
->hitem
, *next
;
349 next
= sl_level_get(prev
, level
- 1);
355 sl_level_set(prev
, level
- 1,
356 sl_level_get(item
, level
- 1));
360 cmpval
= cmpfn(next
, item
);
368 /* TBD: assert when trying to remove non-existing item? */
371 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
372 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
373 ptrval
&= UINTPTR_MAX
- 3;
374 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
375 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
377 memset(item
, 0, sizeof(*item
));
380 struct sskip_item
*typesafe_skiplist_pop(struct sskip_head
*head
)
382 size_t level
= SKIPLIST_MAXDEPTH
;
383 struct sskip_item
*prev
= &head
->hitem
, *next
, *item
;
385 item
= sl_level_get(prev
, 0);
392 next
= sl_level_get(prev
, level
);
396 sl_level_set(prev
, level
, sl_level_get(item
, level
));
401 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
402 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
403 ptrval
&= UINTPTR_MAX
- 3;
404 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
405 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
407 memset(item
, 0, sizeof(*item
));
415 static void heap_consistency_check(struct heap_head
*head
,
416 int (*cmpfn
)(const struct heap_item
*a
,
417 const struct heap_item
*b
),
420 uint32_t rghtpos
= pos
+ 1;
421 uint32_t downpos
= HEAP_NARY
* (pos
+ 1);
423 if (pos
+ 1 > ~0U / HEAP_NARY
)
426 if ((pos
& (HEAP_NARY
- 1)) != HEAP_NARY
- 1 && rghtpos
< head
->count
) {
427 assert(cmpfn(head
->array
[rghtpos
], head
->array
[pos
]) >= 0);
428 heap_consistency_check(head
, cmpfn
, rghtpos
);
430 if (downpos
< head
->count
) {
431 assert(cmpfn(head
->array
[downpos
], head
->array
[pos
]) >= 0);
432 heap_consistency_check(head
, cmpfn
, downpos
);
436 #define heap_consistency_check(head, cmpfn, pos)
439 void typesafe_heap_resize(struct heap_head
*head
, bool grow
)
444 newsize
= head
->arraysz
;
447 else if (newsize
< 262144)
448 newsize
+= newsize
/ 2;
449 else if (newsize
< 0xaaaa0000)
450 newsize
+= newsize
/ 3;
453 } else if (head
->count
> 0) {
454 newsize
= head
->count
;
456 XFREE(MTYPE_HEAP_ARRAY
, head
->array
);
461 newsize
+= HEAP_NARY
- 1;
462 newsize
&= ~(HEAP_NARY
- 1);
463 if (newsize
== head
->arraysz
)
466 head
->array
= XREALLOC(MTYPE_HEAP_ARRAY
, head
->array
,
467 newsize
* sizeof(struct heap_item
*));
468 head
->arraysz
= newsize
;
471 void typesafe_heap_pushdown(struct heap_head
*head
, uint32_t pos
,
472 struct heap_item
*item
,
473 int (*cmpfn
)(const struct heap_item
*a
,
474 const struct heap_item
*b
))
476 uint32_t rghtpos
, downpos
, moveto
;
479 /* rghtpos: neighbor to the "right", inside block of NARY.
480 * may be invalid if last in block, check nary_last()
481 * downpos: first neighbor in the "downwards" block further
486 /* make sure we can use the full 4G items */
487 downpos
= HEAP_NARY
* (pos
+ 1);
488 if (pos
+ 1 > ~0U / HEAP_NARY
)
489 /* multiplication overflowed. ~0U is guaranteed
490 * to be an invalid index; size limit is enforced in
495 /* only used on break */
498 #define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1)
499 if (downpos
>= head
->count
500 || cmpfn(head
->array
[downpos
], item
) >= 0) {
501 /* not moving down; either at end or down is >= item */
502 if (nary_last(pos
) || rghtpos
>= head
->count
503 || cmpfn(head
->array
[rghtpos
], item
) >= 0)
504 /* not moving right either - got our spot */
509 /* else: downpos is valid and < item. choose between down
510 * or right (if the latter is an option) */
511 } else if (nary_last(pos
) || cmpfn(head
->array
[rghtpos
],
512 head
->array
[downpos
]) >= 0)
518 head
->array
[pos
] = head
->array
[moveto
];
519 head
->array
[pos
]->index
= pos
;
523 head
->array
[moveto
] = item
;
524 item
->index
= moveto
;
526 heap_consistency_check(head
, cmpfn
, 0);
529 void typesafe_heap_pullup(struct heap_head
*head
, uint32_t pos
,
530 struct heap_item
*item
,
531 int (*cmpfn
)(const struct heap_item
*a
,
532 const struct heap_item
*b
))
537 if ((pos
& (HEAP_NARY
- 1)) == 0)
538 moveto
= pos
/ HEAP_NARY
- 1;
542 if (cmpfn(head
->array
[moveto
], item
) <= 0)
545 head
->array
[pos
] = head
->array
[moveto
];
546 head
->array
[pos
]->index
= pos
;
551 head
->array
[pos
] = item
;
554 heap_consistency_check(head
, cmpfn
, 0);