]>
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")
27 static void hash_consistency_check(struct thash_head
*head
)
30 struct thash_item
*item
, *prev
;
32 for (i
= 0; i
< HASH_SIZE(*head
); i
++) {
33 item
= head
->entries
[i
];
36 assert(HASH_KEY(*head
, item
->hashval
) == i
);
37 assert(!prev
|| item
->hashval
>= prev
->hashval
);
44 #define hash_consistency_check(x)
47 void typesafe_hash_grow(struct thash_head
*head
)
49 uint32_t newsize
= head
->count
, i
, j
;
50 uint8_t newshift
, delta
;
52 hash_consistency_check(head
);
54 newsize
|= newsize
>> 1;
55 newsize
|= newsize
>> 2;
56 newsize
|= newsize
>> 4;
57 newsize
|= newsize
>> 8;
58 newsize
|= newsize
>> 16;
60 newshift
= __builtin_ctz(newsize
) + 1;
62 if (head
->maxshift
&& newshift
> head
->maxshift
)
63 newshift
= head
->maxshift
;
64 if (newshift
== head
->tabshift
)
66 newsize
= _HASH_SIZE(newshift
);
68 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
69 sizeof(head
->entries
[0]) * newsize
);
70 memset(head
->entries
+ HASH_SIZE(*head
), 0,
71 sizeof(head
->entries
[0]) *
72 (newsize
- HASH_SIZE(*head
)));
74 delta
= newshift
- head
->tabshift
;
80 struct thash_item
**apos
, *item
;
83 apos
= &head
->entries
[i
];
85 for (j
= 0; j
< (1U << delta
); j
++) {
89 head
->entries
[(i
<< delta
) + j
] = item
;
90 apos
= &head
->entries
[(i
<< delta
) + j
];
92 while ((item
= *apos
)) {
94 midbits
= _HASH_KEY(newshift
, item
->hashval
);
95 midbits
&= (1 << delta
) - 1;
104 head
->tabshift
= newshift
;
105 hash_consistency_check(head
);
108 void typesafe_hash_shrink(struct thash_head
*head
)
110 uint32_t newsize
= head
->count
, i
, j
;
111 uint8_t newshift
, delta
;
113 hash_consistency_check(head
);
116 XFREE(MTYPE_TYPEDHASH_BUCKET
, head
->entries
);
121 newsize
|= newsize
>> 1;
122 newsize
|= newsize
>> 2;
123 newsize
|= newsize
>> 4;
124 newsize
|= newsize
>> 8;
125 newsize
|= newsize
>> 16;
127 newshift
= __builtin_ctz(newsize
) + 1;
129 if (head
->minshift
&& newshift
< head
->minshift
)
130 newshift
= head
->minshift
;
131 if (newshift
== head
->tabshift
)
133 newsize
= _HASH_SIZE(newshift
);
135 delta
= head
->tabshift
- newshift
;
137 for (i
= 0; i
< newsize
; i
++) {
138 struct thash_item
**apos
= &head
->entries
[i
];
140 for (j
= 0; j
< (1U << delta
); j
++) {
141 *apos
= head
->entries
[(i
<< delta
) + j
];
143 apos
= &(*apos
)->next
;
146 head
->entries
= XREALLOC(MTYPE_TYPEDHASH_BUCKET
, head
->entries
,
147 sizeof(head
->entries
[0]) * newsize
);
148 head
->tabshift
= newshift
;
150 hash_consistency_check(head
);
155 static inline struct sskip_item
*sl_level_get(struct sskip_item
*item
,
158 if (level
< SKIPLIST_OVERFLOW
)
159 return item
->next
[level
];
160 if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
161 return item
->next
[level
];
163 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
164 ptrval
&= UINTPTR_MAX
- 3;
165 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
166 return oflow
->next
[level
- SKIPLIST_OVERFLOW
];
169 static inline void sl_level_set(struct sskip_item
*item
, size_t level
,
170 struct sskip_item
*value
)
172 if (level
< SKIPLIST_OVERFLOW
)
173 item
->next
[level
] = value
;
174 else if (level
== SKIPLIST_OVERFLOW
&& !((uintptr_t)item
->next
[level
] & 1))
175 item
->next
[level
] = value
;
177 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
178 ptrval
&= UINTPTR_MAX
- 3;
179 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
180 oflow
->next
[level
- SKIPLIST_OVERFLOW
] = value
;
184 struct sskip_item
*typesafe_skiplist_add(struct sskip_head
*head
,
185 struct sskip_item
*item
,
186 int (*cmpfn
)(const struct sskip_item
*a
,
187 const struct sskip_item
*b
))
189 size_t level
= SKIPLIST_MAXDEPTH
, newlevel
, auxlevel
;
190 struct sskip_item
*prev
= &head
->hitem
, *next
, *auxprev
, *auxnext
;
193 /* level / newlevel are 1-counted here */
194 newlevel
= __builtin_ctz(random()) + 1;
195 if (newlevel
> SKIPLIST_MAXDEPTH
)
196 newlevel
= SKIPLIST_MAXDEPTH
;
199 while (level
>= newlevel
) {
200 next
= sl_level_get(prev
, level
- 1);
205 cmpval
= cmpfn(next
, item
);
209 } else if (cmpval
== 0) {
215 /* check for duplicate item - could be removed if code doesn't rely
216 * on it, but not really work the complication. */
221 auxnext
= sl_level_get(auxprev
, auxlevel
);
223 while (auxnext
&& (cmpval
= cmpfn(auxnext
, item
)) < 0) {
225 auxnext
= sl_level_get(auxprev
, auxlevel
);
232 memset(item
, 0, sizeof(*item
));
233 if (newlevel
> SKIPLIST_EMBED
) {
234 struct sskip_overflow
*oflow
;
235 oflow
= XMALLOC(MTYPE_SKIPLIST_OFLOW
, sizeof(void *)
236 * (newlevel
- SKIPLIST_OVERFLOW
));
237 item
->next
[SKIPLIST_OVERFLOW
] = (struct sskip_item
*)
238 ((uintptr_t)oflow
| 1);
241 sl_level_set(item
, level
, next
);
242 sl_level_set(prev
, level
, item
);
243 /* level is now 0-counted and < newlevel*/
246 next
= sl_level_get(prev
, level
);
247 while (next
&& cmpfn(next
, item
) < 0) {
249 next
= sl_level_get(prev
, level
);
252 sl_level_set(item
, level
, next
);
253 sl_level_set(prev
, level
, item
);
258 /* NOTE: level counting below is 1-based since that makes the code simpler! */
260 struct sskip_item
*typesafe_skiplist_find(struct sskip_head
*head
,
261 const struct sskip_item
*item
, int (*cmpfn
)(
262 const struct sskip_item
*a
,
263 const struct sskip_item
*b
))
265 size_t level
= SKIPLIST_MAXDEPTH
;
266 struct sskip_item
*prev
= &head
->hitem
, *next
;
270 next
= sl_level_get(prev
, level
- 1);
275 cmpval
= cmpfn(next
, item
);
287 struct sskip_item
*typesafe_skiplist_find_gteq(struct sskip_head
*head
,
288 const struct sskip_item
*item
, int (*cmpfn
)(
289 const struct sskip_item
*a
,
290 const struct sskip_item
*b
))
292 size_t level
= SKIPLIST_MAXDEPTH
;
293 struct sskip_item
*prev
= &head
->hitem
, *next
;
297 next
= sl_level_get(prev
, level
- 1);
302 cmpval
= cmpfn(next
, item
);
314 struct sskip_item
*typesafe_skiplist_find_lt(struct sskip_head
*head
,
315 const struct sskip_item
*item
, int (*cmpfn
)(
316 const struct sskip_item
*a
,
317 const struct sskip_item
*b
))
319 size_t level
= SKIPLIST_MAXDEPTH
;
320 struct sskip_item
*prev
= &head
->hitem
, *next
, *best
= NULL
;
324 next
= sl_level_get(prev
, level
- 1);
329 cmpval
= cmpfn(next
, item
);
339 void typesafe_skiplist_del(struct sskip_head
*head
, struct sskip_item
*item
,
340 int (*cmpfn
)(const struct sskip_item
*a
,
341 const struct sskip_item
*b
))
343 size_t level
= SKIPLIST_MAXDEPTH
;
344 struct sskip_item
*prev
= &head
->hitem
, *next
;
348 next
= sl_level_get(prev
, level
- 1);
354 sl_level_set(prev
, level
- 1,
355 sl_level_get(item
, level
- 1));
359 cmpval
= cmpfn(next
, item
);
367 /* TBD: assert when trying to remove non-existing item? */
370 if ((uintptr_t)item
->next
[SKIPLIST_OVERFLOW
] & 1) {
371 uintptr_t ptrval
= (uintptr_t)item
->next
[SKIPLIST_OVERFLOW
];
372 ptrval
&= UINTPTR_MAX
- 3;
373 struct sskip_overflow
*oflow
= (struct sskip_overflow
*)ptrval
;
374 XFREE(MTYPE_SKIPLIST_OFLOW
, oflow
);
376 memset(item
, 0, sizeof(*item
));