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
) {
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
];
This page took 0.030328 seconds and 5 git commands to generate.