Debian Codegraph @

staprun/gheap.h

raw
1 #ifndef GHEAP_H
2 #define GHEAP_H
3
4 /*
5 * Generalized heap implementation for C99.
6 *
7 * Don't forget passing -DNDEBUG option to the compiler when creating optimized
8 * builds. This significantly speeds up gheap code by removing debug assertions.
9 *
10 * Author: Aliaksandr Valialkin <[email protected]>.
11 */
12 /*
13 Copyright (c) 2011 Aliaksandr Valialkin <[email protected]>
14 All rights reserved.
15
16 Redistribution and use in source and binary forms, with or without
17 modification, are permitted provided that the following conditions
18 are met:
19 1. Redistributions of source code must retain the above copyright
20 notice, this list of conditions and the following disclaimer.
21 2. Redistributions in binary form must reproduce the above copyright
22 notice, this list of conditions and the following disclaimer in the
23 documentation and/or other materials provided with the distribution.
24
25 THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
26 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
29 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 SUCH DAMAGE.
36 */
37
38
39
40 /*******************************************************************************
41 * Interface.
42 ******************************************************************************/
43
44 #include <stddef.h> /* for size_t */
45 #include <stdint.h> /* for SIZE_MAX */
46
47 /*
48 * Less comparer must return non-zero value if a < b.
49 * ctx is the gheap_ctx->less_comparer_ctx.
50 * Otherwise it must return 0.
51 */
52 typedef int (*gheap_less_comparer_t)(const void *ctx, const void *a,
53 const void *b);
54
55 /*
56 * Moves the item from src to dst.
57 */
58 typedef void (*gheap_item_mover_t)(void *dst, const void *src);
59
60 /*
61 * Gheap context.
62 * This context must be passed to every gheap function.
63 */
64 struct gheap_ctx
65 {
66 /*
67 * How much children each heap item can have.
68 */
69 size_t fanout;
70
71 /*
72 * A chunk is a tuple containing fanout items arranged sequentially in memory.
73 * A page is a subheap containing page_chunks chunks arranged sequentially
74 * in memory.
75 * The number of chunks in a page is an arbitrary integer greater than 0.
76 */
77 size_t page_chunks;
78
79 /*
80 * The size of each item in bytes.
81 */
82 size_t item_size;
83
84 gheap_less_comparer_t less_comparer;
85 const void *less_comparer_ctx;
86
87 gheap_item_mover_t item_mover;
88 };
89
90 /*
91 * Returns parent index for the given child index.
92 * Child index must be greater than 0.
93 * Returns 0 if the parent is root.
94 */
95 static inline size_t gheap_get_parent_index(const struct gheap_ctx *ctx,
96 size_t u);
97
98 /*
99 * Returns the index of the first child for the given parent index.
100 * Parent index must be less than SIZE_MAX.
101 * Returns SIZE_MAX if the index of the first child for the given parent
102 * cannot fit size_t.
103 */
104 static inline size_t gheap_get_child_index(const struct gheap_ctx *ctx,
105 size_t u);
106
107 /*
108 * Returns a pointer to the first non-heap item using less_comparer
109 * for items' comparison.
110 * Returns the index of the first non-heap item.
111 * Returns heap_size if base points to valid max heap with the given size.
112 */
113 static inline size_t gheap_is_heap_until(const struct gheap_ctx *ctx,
114 const void *base, size_t heap_size);
115
116 /*
117 * Returns non-zero if base points to valid max heap. Returns zero otherwise.
118 * Uses less_comparer for items' comparison.
119 */
120 static inline int gheap_is_heap(const struct gheap_ctx *ctx,
121 const void *base, size_t heap_size);
122
123 /*
124 * Makes max heap from items base[0] ... base[heap_size-1].
125 * Uses less_comparer for items' comparison.
126 */
127 static inline void gheap_make_heap(const struct gheap_ctx *ctx,
128 void *base, size_t heap_size);
129
130 /*
131 * Pushes the item base[heap_size-1] into max heap base[0] ... base[heap_size-2]
132 * Uses less_comparer for items' comparison.
133 */
134 static inline void gheap_push_heap(const struct gheap_ctx *ctx,
135 void *base, size_t heap_size);
136
137 /*
138 * Pops the maximum item from max heap base[0] ... base[heap_size-1] into
139 * base[heap_size-1].
140 * Uses less_comparer for items' comparison.
141 */
142 static inline void gheap_pop_heap(const struct gheap_ctx *ctx,
143 void *base, size_t heap_size);
144
145 /*
146 * Sorts items in place of max heap in ascending order.
147 * Uses less_comparer for items' comparison.
148 */
149 static inline void gheap_sort_heap(const struct gheap_ctx *ctx,
150 void *base, size_t heap_size);
151
152 /*
153 * Swaps the item outside the heap with the maximum item inside
154 * the heap and restores heap invariant.
155 */
156 static inline void gheap_swap_max_item(const struct gheap_ctx *const ctx,
157 void *const base, const size_t heap_size, void *item);
158
159 /*
160 * Restores max heap invariant after item's value has been increased,
161 * i.e. less_comparer(old_item, new_item) != 0.
162 */
163 static inline void gheap_restore_heap_after_item_increase(
164 const struct gheap_ctx *ctx,
165 void *base, size_t heap_size, size_t modified_item_index);
166
167 /*
168 * Restores max heap invariant after item's value has been decreased,
169 * i.e. less_comparer(new_item, old_item) != 0.
170 */
171 static inline void gheap_restore_heap_after_item_decrease(
172 const struct gheap_ctx *ctx,
173 void *base, size_t heap_size, size_t modified_item_index);
174
175 /*
176 * Removes the given item from the heap and puts it into base[heap_size-1].
177 * Uses less_comparer for items' comparison.
178 */
179 static inline void gheap_remove_from_heap(const struct gheap_ctx *ctx,
180 void *base, size_t heap_size, size_t item_index);
181
182 /*******************************************************************************
183 * Implementation.
184 *
185 * Define all functions inline, so compiler will be able optimizing out common
186 * args (fanout, page_chunks, item_size, less_comparer and item_mover),
187 * which are usually constants, using contant folding optimization
188 * ( http://en.wikipedia.org/wiki/Constant_folding ).
189 *****************************************************************************/
190
191 #include <assert.h> /* for assert */
192 #include <stddef.h> /* for size_t */
193 #include <stdint.h> /* for uintptr_t, SIZE_MAX and UINTPTR_MAX */
194
195 static inline size_t gheap_get_parent_index(const struct gheap_ctx *const ctx,
196 size_t u)
197 {
198 assert(u > 0);
199
200 const size_t fanout = ctx->fanout;
201 const size_t page_chunks = ctx->page_chunks;
202
203 --u;
204 if (page_chunks == 1) {
205 return u / fanout;
206 }
207
208 if (u < fanout) {
209 /* Parent is root. */
210 return 0;
211 }
212
213 assert(page_chunks <= SIZE_MAX / fanout);
214 const size_t page_size = fanout * page_chunks;
215 size_t v = u % page_size;
216 if (v >= fanout) {
217 /* Fast path. Parent is on the same page as the child. */
218 return u - v + v / fanout;
219 }
220
221 /* Slow path. Parent is on another page. */
222 v = u / page_size - 1;
223 const size_t page_leaves = (fanout - 1) * page_chunks + 1;
224 u = v / page_leaves + 1;
225 return u * page_size + v % page_leaves - page_leaves + 1;
226 }
227
228 static inline size_t gheap_get_child_index(const struct gheap_ctx *const ctx,
229 size_t u)
230 {
231 assert(u < SIZE_MAX);
232
233 const size_t fanout = ctx->fanout;
234 const size_t page_chunks = ctx->page_chunks;
235
236 if (page_chunks == 1) {
237 if (u > (SIZE_MAX - 1) / fanout) {
238 /* Child overflow. */
239 return SIZE_MAX;
240 }
241 return u * fanout + 1;
242 }
243
244 if (u == 0) {
245 /* Root's child is always 1. */
246 return 1;
247 }
248
249 assert(page_chunks <= SIZE_MAX / fanout);
250 const size_t page_size = fanout * page_chunks;
251 --u;
252 size_t v = u % page_size + 1;
253 if (v < page_size / fanout) {
254 /* Fast path. Child is on the same page as the parent. */
255 v *= fanout - 1;
256 if (u > SIZE_MAX - 2 - v) {
257 /* Child overflow. */
258 return SIZE_MAX;
259 }
260 return u + v + 2;
261 }
262
263 /* Slow path. Child is on another page. */
264 const size_t page_leaves = (fanout - 1) * page_chunks + 1;
265 v += (u / page_size + 1) * page_leaves - page_size;
266 if (v > (SIZE_MAX - 1) / page_size) {
267 /* Child overflow. */
268 return SIZE_MAX;
269 }
270 return v * page_size + 1;
271 }
272
273 /* Returns a pointer to base[index]. */
274 static inline void *_gheap_get_item_ptr(const struct gheap_ctx *const ctx,
275 const void *const base, const size_t index)
276 {
277 const size_t item_size = ctx->item_size;
278
279 assert(index <= SIZE_MAX / item_size);
280
281 const size_t offset = item_size * index;
282 assert((uintptr_t)base <= UINTPTR_MAX - offset);
283
284 return ((char *)base) + offset;
285 }
286
287 /*
288 * Sifts the item up in the given sub-heap with the given root_index
289 * starting from the hole_index.
290 */
291 static inline void _gheap_sift_up(const struct gheap_ctx *const ctx,
292 void *const base, const size_t root_index, size_t hole_index,
293 const void *const item)
294 {
295 assert(hole_index >= root_index);
296
297 const gheap_less_comparer_t less_comparer = ctx->less_comparer;
298 const void *const less_comparer_ctx = ctx->less_comparer_ctx;
299 const gheap_item_mover_t item_mover = ctx->item_mover;
300
301 while (hole_index > root_index) {
302 const size_t parent_index = gheap_get_parent_index(ctx, hole_index);
303 assert(parent_index >= root_index);
304 const void *const parent = _gheap_get_item_ptr(ctx, base, parent_index);
305 if (!less_comparer(less_comparer_ctx, parent, item)) {
306 break;
307 }
308 item_mover(_gheap_get_item_ptr(ctx, base, hole_index),
309 parent);
310 hole_index = parent_index;
311 }
312
313 item_mover(_gheap_get_item_ptr(ctx, base, hole_index), item);
314 }
315
316 /*
317 * Moves the max child into the given hole and returns index
318 * of the new hole.
319 */
320 static inline size_t _gheap_move_up_max_child(const struct gheap_ctx *const ctx,
321 void *const base, const size_t children_count,
322 const size_t hole_index, const size_t child_index)
323 {
324 assert(children_count > 0);
325 assert(children_count <= ctx->fanout);
326 assert(child_index == gheap_get_child_index(ctx, hole_index));
327
328 const gheap_less_comparer_t less_comparer = ctx->less_comparer;
329 const void *const less_comparer_ctx = ctx->less_comparer_ctx;
330 const gheap_item_mover_t item_mover = ctx->item_mover;
331
332 size_t max_child_index = child_index;
333 for (size_t i = 1; i < children_count; ++i) {
334 if (!less_comparer(less_comparer_ctx,
335 _gheap_get_item_ptr(ctx, base, child_index + i),
336 _gheap_get_item_ptr(ctx, base, max_child_index))) {
337 max_child_index = child_index + i;
338 }
339 }
340 item_mover(_gheap_get_item_ptr(ctx, base, hole_index),
341 _gheap_get_item_ptr(ctx, base, max_child_index));
342 return max_child_index;
343 }
344
345 /*
346 * Sifts the given item down in the heap of the given size starting
347 * from the hole_index.
348 */
349 static inline void _gheap_sift_down(const struct gheap_ctx *const ctx,
350 void *const base, const size_t heap_size, size_t hole_index,
351 const void *const item)
352 {
353 assert(heap_size > 0);
354 assert(hole_index < heap_size);
355
356 const size_t fanout = ctx->fanout;
357
358 const size_t root_index = hole_index;
359 const size_t last_full_index = heap_size - (heap_size - 1) % fanout;
360 while (1) {
361 const size_t child_index = gheap_get_child_index(ctx, hole_index);
362 if (child_index >= last_full_index) {
363 if (child_index < heap_size) {
364 assert(child_index == last_full_index);
365 hole_index = _gheap_move_up_max_child(ctx, base,
366 heap_size - child_index, hole_index, child_index);
367 }
368 break;
369 }
370 assert(heap_size - child_index >= fanout);
371 hole_index = _gheap_move_up_max_child(ctx, base, fanout, hole_index,
372 child_index);
373 }
374 _gheap_sift_up(ctx, base, root_index, hole_index, item);
375 }
376
377 /*
378 * Pops the maximum item from the heap [base[0] ... base[heap_size-1]]
379 * into base[heap_size].
380 */
381 static inline void _gheap_pop_max_item(const struct gheap_ctx *const ctx,
382 void *const base, const size_t heap_size)
383 {
384 void *const hole = _gheap_get_item_ptr(ctx, base, heap_size);
385 gheap_swap_max_item(ctx, base, heap_size, hole);
386 }
387
388 static inline size_t gheap_is_heap_until(const struct gheap_ctx *const ctx,
389 const void *const base, const size_t heap_size)
390 {
391 const gheap_less_comparer_t less_comparer = ctx->less_comparer;
392 const void *const less_comparer_ctx = ctx->less_comparer_ctx;
393
394 for (size_t u = 1; u < heap_size; ++u) {
395 const size_t v = gheap_get_parent_index(ctx, u);
396 const void *const a = _gheap_get_item_ptr(ctx, base, v);
397 const void *const b = _gheap_get_item_ptr(ctx, base, u);
398 if (less_comparer(less_comparer_ctx, a, b)) {
399 return u;
400 }
401 }
402 return heap_size;
403 }
404
405 static inline int gheap_is_heap(const struct gheap_ctx *const ctx,
406 const void *const base, const size_t heap_size)
407 {
408 return (gheap_is_heap_until(ctx, base, heap_size) == heap_size);
409 }
410
411 static inline void gheap_make_heap(const struct gheap_ctx *const ctx,
412 void *const base, const size_t heap_size)
413 {
414 const size_t fanout = ctx->fanout;
415 const size_t page_chunks = ctx->page_chunks;
416 const size_t item_size = ctx->item_size;
417 const gheap_item_mover_t item_mover = ctx->item_mover;
418
419 if (heap_size > 1) {
420 /* Skip leaf nodes without children. This is easy to do for non-paged heap,
421 * i.e. when page_chunks = 1, but it is difficult for paged heaps.
422 * So leaf nodes in paged heaps are visited anyway.
423 */
424 size_t i = (page_chunks == 1) ? ((heap_size - 2) / fanout) :
425 (heap_size - 2);
426 do {
427 char tmp[item_size];
428 item_mover(tmp, _gheap_get_item_ptr(ctx, base, i));
429 _gheap_sift_down(ctx, base, heap_size, i, tmp);
430 } while (i-- > 0);
431 }
432
433 assert(gheap_is_heap(ctx, base, heap_size));
434 }
435
436 static inline void gheap_push_heap(const struct gheap_ctx *const ctx,
437 void *const base, const size_t heap_size)
438 {
439 assert(heap_size > 0);
440 assert(gheap_is_heap(ctx, base, heap_size - 1));
441
442 const size_t item_size = ctx->item_size;
443 const gheap_item_mover_t item_mover = ctx->item_mover;
444
445 if (heap_size > 1) {
446 const size_t u = heap_size - 1;
447 char tmp[item_size];
448 item_mover(tmp, _gheap_get_item_ptr(ctx, base, u));
449 _gheap_sift_up(ctx, base, 0, u, tmp);
450 }
451
452 assert(gheap_is_heap(ctx, base, heap_size));
453 }
454
455 static inline void gheap_pop_heap(const struct gheap_ctx *const ctx,
456 void *const base, const size_t heap_size)
457 {
458 assert(heap_size > 0);
459 assert(gheap_is_heap(ctx, base, heap_size));
460
461 if (heap_size > 1) {
462 _gheap_pop_max_item(ctx, base, heap_size - 1);
463 }
464
465 assert(gheap_is_heap(ctx, base, heap_size - 1));
466 }
467
468 static inline void gheap_sort_heap(const struct gheap_ctx *const ctx,
469 void *const base, const size_t heap_size)
470 {
471 for (size_t i = heap_size; i > 1; --i) {
472 _gheap_pop_max_item(ctx, base, i - 1);
473 }
474 }
475
476 static inline void gheap_swap_max_item(const struct gheap_ctx *const ctx,
477 void *const base, const size_t heap_size, void *item)
478 {
479 assert(heap_size > 0);
480 assert(gheap_is_heap(ctx, base, heap_size));
481
482 const size_t item_size = ctx->item_size;
483 const gheap_item_mover_t item_mover = ctx->item_mover;
484
485 char tmp[item_size];
486 item_mover(tmp, item);
487 item_mover(item, base);
488 _gheap_sift_down(ctx, base, heap_size, 0, tmp);
489
490 assert(gheap_is_heap(ctx, base, heap_size));
491 }
492
493 static inline void gheap_restore_heap_after_item_increase(
494 const struct gheap_ctx *const ctx,
495 void *const base, const size_t heap_size, size_t modified_item_index)
496 {
497 assert(heap_size > 0);
498 assert(modified_item_index < heap_size);
499 assert(gheap_is_heap(ctx, base, modified_item_index));
500
501 const size_t item_size = ctx->item_size;
502 const gheap_item_mover_t item_mover = ctx->item_mover;
503
504 if (modified_item_index > 0) {
505 char tmp[item_size];
506 item_mover(tmp, _gheap_get_item_ptr(ctx, base, modified_item_index));
507 _gheap_sift_up(ctx, base, 0, modified_item_index, tmp);
508 }
509
510 assert(gheap_is_heap(ctx, base, heap_size));
511 (void)heap_size;
512 }
513
514 static inline void gheap_restore_heap_after_item_decrease(
515 const struct gheap_ctx *const ctx,
516 void *const base, const size_t heap_size, size_t modified_item_index)
517 {
518 assert(heap_size > 0);
519 assert(modified_item_index < heap_size);
520 assert(gheap_is_heap(ctx, base, modified_item_index));
521
522 const size_t item_size = ctx->item_size;
523 const gheap_item_mover_t item_mover = ctx->item_mover;
524
525 char tmp[item_size];
526 item_mover(tmp, _gheap_get_item_ptr(ctx, base, modified_item_index));
527 _gheap_sift_down(ctx, base, heap_size, modified_item_index, tmp);
528
529 assert(gheap_is_heap(ctx, base, heap_size));
530 }
531
532 static inline void gheap_remove_from_heap(const struct gheap_ctx *const ctx,
533 void *const base, const size_t heap_size, size_t item_index)
534 {
535 assert(heap_size > 0);
536 assert(item_index < heap_size);
537 assert(gheap_is_heap(ctx, base, heap_size));
538
539 const size_t item_size = ctx->item_size;
540 const gheap_less_comparer_t less_comparer = ctx->less_comparer;
541 const void *const less_comparer_ctx = ctx->less_comparer_ctx;
542 const gheap_item_mover_t item_mover = ctx->item_mover;
543
544 const size_t new_heap_size = heap_size - 1;
545 if (item_index < new_heap_size) {
546 char tmp[item_size];
547 void *const hole = _gheap_get_item_ptr(ctx, base, new_heap_size);
548 item_mover(tmp, hole);
549 item_mover(hole, _gheap_get_item_ptr(ctx, base, item_index));
550 if (less_comparer(less_comparer_ctx, tmp, hole)) {
551 _gheap_sift_down(ctx, base, new_heap_size, item_index, tmp);
552 }
553 else {
554 _gheap_sift_up(ctx, base, 0, item_index, tmp);
555 }
556 }
557
558 assert(gheap_is_heap(ctx, base, new_heap_size));
559 }
560
561 #endif