/src/freeradius-server/src/lib/util/heap.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * This program is free software; you can redistribute it and/or modify |
3 | | * it under the terms of the GNU General Public License as published by |
4 | | * the Free Software Foundation; either version 2 of the License, or |
5 | | * (at your option) any later version. |
6 | | * |
7 | | * This program is distributed in the hope that it will be useful, |
8 | | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
9 | | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
10 | | * GNU General Public License for more details. |
11 | | * |
12 | | * You should have received a copy of the GNU General Public License |
13 | | * along with this program; if not, write to the Free Software |
14 | | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA |
15 | | */ |
16 | | |
17 | | /** Functions for a basic binary heaps |
18 | | * |
19 | | * @file src/lib/util/heap.c |
20 | | * |
21 | | * @copyright 2005,2006 The FreeRADIUS server project |
22 | | */ |
23 | | RCSID("$Id: 2e4c500dc484a79b6673fbd84284744521ecd5e3 $") |
24 | | |
25 | | #define _HEAP_PRIVATE 1 |
26 | | #include <freeradius-devel/util/debug.h> |
27 | | #include <freeradius-devel/util/heap.h> |
28 | | #include <freeradius-devel/util/misc.h> |
29 | | #include <freeradius-devel/util/strerror.h> |
30 | | |
31 | 0 | #define INITIAL_CAPACITY 2048 |
32 | | |
33 | | /* |
34 | | * First node in a heap is element 1. Children of i are 2i and |
35 | | * 2i+1. These macros wrap the logic, so the code is more |
36 | | * descriptive. |
37 | | */ |
38 | 0 | #define HEAP_PARENT(_x) ((_x) >> 1) |
39 | 0 | #define HEAP_LEFT(_x) (2 * (_x)) |
40 | 0 | #define HEAP_RIGHT(_x) (2 * (_x) + 1 ) |
41 | 0 | #define HEAP_SWAP(_a, _b) do { void *_tmp = _a; _a = _b; _b = _tmp; } while (0) |
42 | | |
43 | | static void fr_heap_bubble(fr_heap_t *h, fr_heap_index_t child); |
44 | | |
45 | | /** Return how many bytes need to be allocated to hold a heap of a given size |
46 | | * |
47 | | * This is useful for passing to talloc[_zero]_pooled_object to avoid additional mallocs. |
48 | | * |
49 | | * @param[in] count The initial element count. |
50 | | * @return The number of bytes to pre-allocate. |
51 | | */ |
52 | | size_t fr_heap_pre_alloc_size(unsigned int count) |
53 | 0 | { |
54 | 0 | return sizeof(fr_heap_t) + sizeof(void *) * count; |
55 | 0 | } |
56 | | |
57 | | fr_heap_t *_fr_heap_alloc(TALLOC_CTX *ctx, fr_heap_cmp_t cmp, char const *type, size_t offset, unsigned int init) |
58 | 0 | { |
59 | 0 | fr_heap_t *h; |
60 | |
|
61 | 0 | if (!init) init = INITIAL_CAPACITY; |
62 | | |
63 | | /* |
64 | | * For small heaps (< 40 elements) the |
65 | | * increase in memory locality gives us |
66 | | * a 100% performance increase |
67 | | * (talloc headers are big); |
68 | | */ |
69 | 0 | h = (fr_heap_t *)talloc_array(ctx, uint8_t, sizeof(fr_heap_t) + (sizeof(void *) * (init + 1))); |
70 | 0 | if (unlikely(!h)) return NULL; |
71 | 0 | talloc_set_type(h, fr_heap_t); |
72 | |
|
73 | 0 | *h = (fr_heap_t){ |
74 | 0 | .size = init, |
75 | 0 | .min = init, |
76 | 0 | .type = type, |
77 | 0 | .cmp = cmp, |
78 | 0 | .offset = offset |
79 | 0 | }; |
80 | | |
81 | | /* |
82 | | * As we're using unsigned index values |
83 | | * index 0 is a special value meaning |
84 | | * that the data isn't currently inserted |
85 | | * into the heap. |
86 | | */ |
87 | 0 | h->p[0] = (void *)UINTPTR_MAX; |
88 | |
|
89 | 0 | return h; |
90 | 0 | } |
91 | | |
92 | | static inline CC_HINT(always_inline, nonnull) fr_heap_index_t index_get(fr_heap_t *h, void *data) |
93 | 0 | { |
94 | 0 | return *((fr_heap_index_t const *)(((uint8_t const *)data) + h->offset)); |
95 | 0 | } |
96 | | |
97 | | static inline CC_HINT(always_inline, nonnull) void index_set(fr_heap_t *h, void *data, fr_heap_index_t idx) |
98 | 0 | { |
99 | 0 | *((fr_heap_index_t *)(((uint8_t *)data) + h->offset)) = idx; |
100 | 0 | } |
101 | | |
102 | 0 | #define OFFSET_SET(_heap, _idx) index_set(_heap, _heap->p[_idx], _idx) |
103 | 0 | #define OFFSET_RESET(_heap, _idx) index_set(_heap, _heap->p[_idx], 0) |
104 | | |
105 | | static inline CC_HINT(always_inline) |
106 | | int realloc_heap(fr_heap_t **hp, unsigned int n_size) |
107 | 0 | { |
108 | 0 | fr_heap_t *h = *hp; |
109 | |
|
110 | 0 | h = (fr_heap_t *)talloc_realloc(hp, h, uint8_t, sizeof(fr_heap_t) + (sizeof(void *) * (n_size + 1))); |
111 | 0 | if (unlikely(!h)) { |
112 | 0 | fr_strerror_printf("Failed expanding heap to %u elements (%u bytes)", |
113 | 0 | n_size, (n_size * (unsigned int)sizeof(void *))); |
114 | 0 | return -1; |
115 | 0 | } |
116 | 0 | talloc_set_type(h, fr_heap_t); |
117 | 0 | h->size = n_size; |
118 | |
|
119 | 0 | *hp = h; |
120 | |
|
121 | 0 | return 0; |
122 | 0 | } |
123 | | |
124 | | |
125 | | /** Insert a new element into the heap |
126 | | * |
127 | | * Insert element in heap. Normally, p != NULL, we insert p in a |
128 | | * new position and bubble up. If p == NULL, then the element is |
129 | | * already in place, and key is the position where to start the |
130 | | * bubble-up. |
131 | | * |
132 | | * Returns -1 on failure (cannot allocate new heap entry) |
133 | | * |
134 | | * If offset > 0 the position (index, int) of the element in the |
135 | | * heap is also stored in the element itself at the given offset |
136 | | * in bytes. |
137 | | * |
138 | | * @param[in,out] hp The heap to extract an element from. |
139 | | * A new pointer value will be written to hp |
140 | | * if the heap is resized. |
141 | | * @param[in] data Data to insert into the heap. |
142 | | * @return |
143 | | * - 0 on success. |
144 | | * - -1 on failure (heap full or malloc error). |
145 | | */ |
146 | | int fr_heap_insert(fr_heap_t **hp, void *data) |
147 | 0 | { |
148 | 0 | fr_heap_t *h = *hp; |
149 | 0 | fr_heap_index_t child; |
150 | |
|
151 | 0 | if (unlikely(h == NULL)) { |
152 | 0 | fr_strerror_const("Heap pointer was NULL"); |
153 | 0 | return -1; |
154 | 0 | } |
155 | | |
156 | 0 | child = index_get(h, data); |
157 | 0 | if (fr_heap_entry_inserted(child)) { |
158 | 0 | fr_strerror_const("Node is already in the heap"); |
159 | 0 | return -1; |
160 | 0 | } |
161 | | |
162 | 0 | child = h->num_elements + 1; /* Avoid using index 0 */ |
163 | |
|
164 | 0 | #ifndef TALLOC_GET_TYPE_ABORT_NOOP |
165 | 0 | if (h->type) (void)_talloc_get_type_abort(data, h->type, __location__); |
166 | 0 | #endif |
167 | | |
168 | | /* |
169 | | * Heap is full. Double it's size. |
170 | | */ |
171 | 0 | if (child > h->size) { |
172 | 0 | unsigned int n_size; |
173 | | |
174 | | /* |
175 | | * heap_id is a 32-bit unsigned integer. If the heap will |
176 | | * grow to contain more than 4B elements, disallow |
177 | | * integer overflow. Tho TBH, that should really never |
178 | | * happen. |
179 | | */ |
180 | 0 | if (unlikely(h->size > (UINT_MAX - h->size))) { |
181 | 0 | if (h->size == UINT_MAX) { |
182 | 0 | fr_strerror_const("Heap is full"); |
183 | 0 | return -1; |
184 | 0 | } else { |
185 | 0 | n_size = UINT_MAX; |
186 | 0 | } |
187 | 0 | } else { |
188 | 0 | n_size = h->size * 2; |
189 | 0 | } |
190 | | |
191 | 0 | if (realloc_heap(&h, n_size) < 0) return -1; |
192 | | |
193 | 0 | *hp = h; |
194 | 0 | } |
195 | | |
196 | 0 | h->p[child] = data; |
197 | 0 | h->num_elements++; |
198 | |
|
199 | 0 | fr_heap_bubble(h, child); |
200 | |
|
201 | 0 | return 0; |
202 | 0 | } |
203 | | |
204 | | static inline CC_HINT(always_inline) void fr_heap_bubble(fr_heap_t *h, fr_heap_index_t child) |
205 | 0 | { |
206 | 0 | if (!fr_cond_assert(child != FR_HEAP_INDEX_INVALID)) return; |
207 | | |
208 | | /* |
209 | | * Bubble up the element. |
210 | | */ |
211 | 0 | while (child > 1) { |
212 | 0 | fr_heap_index_t parent = HEAP_PARENT(child); |
213 | | |
214 | | /* |
215 | | * Parent is smaller than the child. We're done. |
216 | | */ |
217 | 0 | if (h->cmp(h->p[parent], h->p[child]) < 0) break; |
218 | | |
219 | | /* |
220 | | * Child is smaller than the parent, repeat. |
221 | | */ |
222 | 0 | HEAP_SWAP(h->p[child], h->p[parent]); |
223 | 0 | OFFSET_SET(h, child); |
224 | 0 | child = parent; |
225 | 0 | } |
226 | 0 | OFFSET_SET(h, child); |
227 | 0 | } |
228 | | |
229 | | /** Remove a node from the heap |
230 | | * |
231 | | * @param[in,out] hp The heap to extract an element from. |
232 | | * A new pointer value will be written to hp |
233 | | * if the heap is resized. |
234 | | * @param[in] data Data to extract from the heap. |
235 | | * @return |
236 | | * - 0 on success. |
237 | | * - -1 on failure (no elements or data not found). |
238 | | */ |
239 | | int fr_heap_extract(fr_heap_t **hp, void *data) |
240 | 0 | { |
241 | 0 | fr_heap_t *h = *hp; |
242 | 0 | fr_heap_index_t parent, child, max; |
243 | |
|
244 | 0 | if (unlikely(h == NULL)) { |
245 | 0 | fr_strerror_const("Heap pointer was NULL"); |
246 | 0 | return -1; |
247 | 0 | } |
248 | | |
249 | | /* |
250 | | * Extract element. |
251 | | */ |
252 | 0 | parent = index_get(h, data); |
253 | | |
254 | | /* |
255 | | * Out of bounds. |
256 | | */ |
257 | 0 | if (unlikely((parent == 0) || (parent > h->num_elements))) { |
258 | 0 | fr_strerror_printf("Heap parent (%i) out of bounds (0-%i)", parent, h->num_elements); |
259 | 0 | return -1; |
260 | 0 | } |
261 | | |
262 | 0 | if (unlikely(data != h->p[parent])) { |
263 | 0 | fr_strerror_printf("Invalid heap index. Expected data %p at offset %i, got %p", data, |
264 | 0 | parent, h->p[parent]); |
265 | 0 | return -1; |
266 | 0 | } |
267 | 0 | max = h->num_elements; |
268 | |
|
269 | 0 | child = HEAP_LEFT(parent); |
270 | 0 | OFFSET_RESET(h, parent); |
271 | 0 | while (child <= max) { |
272 | | /* |
273 | | * Maybe take the right child. |
274 | | */ |
275 | 0 | if ((child != max) && |
276 | 0 | (h->cmp(h->p[child + 1], h->p[child]) < 0)) { |
277 | 0 | child = child + 1; |
278 | 0 | } |
279 | 0 | h->p[parent] = h->p[child]; |
280 | 0 | OFFSET_SET(h, parent); |
281 | 0 | parent = child; |
282 | 0 | child = HEAP_LEFT(child); |
283 | 0 | } |
284 | 0 | h->num_elements--; |
285 | | |
286 | | /* |
287 | | * If the number of elements in the heap is half |
288 | | * what we need, shrink the heap back. |
289 | | */ |
290 | 0 | if ((h->num_elements * 2) < h->size) { |
291 | 0 | unsigned int n_size = ROUND_UP_DIV(h->size, 2); |
292 | |
|
293 | 0 | if ((n_size > h->min) && (realloc_heap(&h, n_size)) == 0) *hp = h; |
294 | 0 | } |
295 | | |
296 | | /* |
297 | | * We didn't end up at the last element in the heap. |
298 | | * This element has to be re-inserted. |
299 | | */ |
300 | 0 | if (parent != max) { |
301 | | /* |
302 | | * Fill hole with last entry and bubble up, |
303 | | * reusing the insert code |
304 | | */ |
305 | 0 | h->p[parent] = h->p[max]; |
306 | |
|
307 | 0 | fr_heap_bubble(h, parent); |
308 | 0 | } |
309 | |
|
310 | 0 | return 0; |
311 | 0 | } |
312 | | |
313 | | /** Remove a node from the heap |
314 | | * |
315 | | * @param[in,out] hp The heap to pop an element from. |
316 | | * A new pointer value will be written to hp |
317 | | * if the heap is resized. |
318 | | * @return |
319 | | * - The item that was popped. |
320 | | * - NULL on error. |
321 | | */ |
322 | | void *fr_heap_pop(fr_heap_t **hp) |
323 | 0 | { |
324 | 0 | fr_heap_t *h = *hp; |
325 | 0 | void *data; |
326 | |
|
327 | 0 | if (unlikely(h == NULL)) { |
328 | 0 | fr_strerror_const("Heap pointer was NULL"); |
329 | 0 | return NULL; |
330 | 0 | } |
331 | | |
332 | 0 | if (h->num_elements == 0) return NULL; |
333 | | |
334 | 0 | data = h->p[1]; |
335 | 0 | if (unlikely(fr_heap_extract(hp, data) < 0)) return NULL; |
336 | | |
337 | 0 | return data; |
338 | 0 | } |
339 | | |
340 | | /** Iterate over entries in heap |
341 | | * |
342 | | * @note If the heap is modified the iterator should be considered invalidated. |
343 | | * |
344 | | * @param[in] h to iterate over. |
345 | | * @param[in] iter Pointer to an iterator struct, used to maintain |
346 | | * state between calls. |
347 | | * @return |
348 | | * - User data. |
349 | | * - NULL if at the end of the list. |
350 | | */ |
351 | | void *fr_heap_iter_init(fr_heap_t *h, fr_heap_iter_t *iter) |
352 | 0 | { |
353 | 0 | *iter = 1; |
354 | |
|
355 | 0 | if (h->num_elements == 0) return NULL; |
356 | | |
357 | 0 | return h->p[1]; |
358 | 0 | } |
359 | | |
360 | | /** Get the next entry in a heap |
361 | | * |
362 | | * @note If the heap is modified the iterator should be considered invalidated. |
363 | | * |
364 | | * @param[in] h to iterate over. |
365 | | * @param[in] iter Pointer to an iterator struct, used to maintain |
366 | | * state between calls. |
367 | | * @return |
368 | | * - User data. |
369 | | * - NULL if at the end of the list. |
370 | | */ |
371 | | void *fr_heap_iter_next(fr_heap_t *h, fr_heap_iter_t *iter) |
372 | 0 | { |
373 | 0 | if ((*iter + 1) > h->num_elements) return NULL; |
374 | 0 | *iter += 1; |
375 | |
|
376 | 0 | return h->p[*iter]; |
377 | 0 | } |
378 | | |
379 | | #ifndef TALLOC_GET_TYPE_ABORT_NOOP |
380 | | void fr_heap_verify(char const *file, int line, fr_heap_t *h) |
381 | 0 | { |
382 | 0 | fr_fatal_assert_msg(h, "CONSISTENCY CHECK FAILED %s[%i]: fr_heap_t pointer was NULL", file, line); |
383 | 0 | (void) talloc_get_type_abort(h, fr_heap_t); |
384 | | |
385 | | /* |
386 | | * Allocating the heap structure and the array holding the heap as described in data structure |
387 | | * texts together is a respectable savings, but it means adding a level of indirection so the |
388 | | * fr_heap_t * isn't realloc()ed out from under the user, hence the following (and the use of h |
389 | | * rather than hp to access anything in the heap structure). |
390 | | */ |
391 | 0 | fr_fatal_assert_msg(h, "CONSISTENCY CHECK FAILED %s[%i]: heap_t pointer was NULL", file, line); |
392 | 0 | (void) talloc_get_type_abort(h, fr_heap_t); |
393 | |
|
394 | 0 | fr_fatal_assert_msg(h->num_elements <= h->size, |
395 | 0 | "CONSISTENCY CHECK FAILED %s[%i]: num_elements exceeds size", file, line); |
396 | |
|
397 | 0 | fr_fatal_assert_msg(h->p[0] == (void *)UINTPTR_MAX, |
398 | 0 | "CONSISTENCY CHECK FAILED %s[%i]: zeroeth element special value overwritten", file, line); |
399 | |
|
400 | 0 | for (unsigned int i = 1; i <= h->num_elements; i++) { |
401 | 0 | void *data = h->p[i]; |
402 | |
|
403 | 0 | fr_fatal_assert_msg(data, "CONSISTENCY CHECK FAILED %s[%i]: node %u was NULL", file, line, i); |
404 | 0 | if (h->type) (void)_talloc_get_type_abort(data, h->type, __location__); |
405 | 0 | fr_fatal_assert_msg(index_get(h, data) == i, |
406 | 0 | "CONSISTENCY CHECK FAILED %s[%i]: node %u index != %u", file, line, i, i); |
407 | 0 | } |
408 | 0 | for (unsigned int i = 1; ; i++) { |
409 | 0 | if (HEAP_LEFT(i) > h->num_elements) break; |
410 | 0 | fr_fatal_assert_msg(h->cmp(h->p[i], h->p[HEAP_LEFT(i)]) <= 0, |
411 | 0 | "CONSISTENCY_CHECK_FAILED %s[%i]: node %u > left child", file, line, i); |
412 | 0 | if (HEAP_RIGHT(i) > h->num_elements) break; |
413 | 0 | fr_fatal_assert_msg(h->cmp(h->p[i], h->p[HEAP_RIGHT(i)]) <= 0, |
414 | 0 | "CONSISTENCY_CHECK_FAILED %s[%i]: node %u > right child", file, line, i); |
415 | 0 | } |
416 | 0 | } |
417 | | #endif |