2 * Simple insertion-only static-sized priority heap containing
3 * pointers, based on CLR, chapter 7
6 #include <linux/slab.h>
7 #include <linux/prio_heap.h>
9 int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask,
10 int (*gt)(void *, void *))
12 heap->ptrs = kmalloc(size, gfp_mask);
16 heap->max = size / sizeof(void *);
21 void heap_free(struct ptr_heap *heap)
26 void *heap_insert(struct ptr_heap *heap, void *p)
29 void **ptrs = heap->ptrs;
32 if (heap->size < heap->max) {
34 int pos = heap->size++;
35 while (pos > 0 && heap->gt(p, ptrs[(pos-1)/2])) {
36 ptrs[pos] = ptrs[(pos-1)/2];
43 /* The heap is full, so something will have to be dropped */
45 /* If the new pointer is greater than the current max, drop it */
46 if (heap->gt(p, ptrs[0]))
49 /* Replace the current max and heapify */
55 int left = 2 * pos + 1;
56 int right = 2 * pos + 2;
58 if (left < heap->size && heap->gt(ptrs[left], p))
60 if (right < heap->size && heap->gt(ptrs[right], ptrs[largest]))
64 /* Push p down the heap one level and bump one up */
65 ptrs[pos] = ptrs[largest];