2 * LICENSING: this file is copied from the Linux kernel. We should therefore
3 * assume a GPLv2 license for the code that comes from the Linux mainline.
7 * Static-sized priority heap containing pointers. Based on CLR, chapter 7.
10 #include <linux/slab.h>
11 #include <linux/prio_heap.h>
13 int heap_init(struct ptr_heap
*heap
, size_t size
, gfp_t gfp_mask
,
14 int (*gt
)(void *, void *))
16 heap
->ptrs
= kmalloc(size
, gfp_mask
);
20 heap
->max
= size
/ sizeof(void *);
25 void heap_free(struct ptr_heap
*heap
)
30 static void heapify(struct ptr_heap
*heap
, int pos
)
32 void **ptrs
= heap
->ptrs
;
36 int left
= 2 * pos
+ 1;
37 int right
= 2 * pos
+ 2;
39 if (left
< heap
->size
&& heap
->gt(ptrs
[left
], p
))
41 if (right
< heap
->size
&& heap
->gt(ptrs
[right
], ptrs
[largest
]))
45 /* Push p down the heap one level and bump one up */
46 ptrs
[pos
] = ptrs
[largest
];
52 void *heap_replace_max(struct ptr_heap
*heap
, void *p
)
55 void **ptrs
= heap
->ptrs
;
63 /* Replace the current max and heapify */
70 void *heap_insert(struct ptr_heap
*heap
, void *p
)
72 void **ptrs
= heap
->ptrs
;
75 if (heap
->size
< heap
->max
) {
78 while (pos
> 0 && heap
->gt(p
, ptrs
[(pos
-1)/2])) {
79 ptrs
[pos
] = ptrs
[(pos
-1)/2];
86 /* The heap is full, so something will have to be dropped */
88 /* If the new pointer is greater than the current max, drop it */
89 if (heap
->gt(p
, ptrs
[0]))
92 /* Replace the current max and heapify */
93 return heap_replace_max(heap
, p
);
96 void *heap_remove(struct ptr_heap
*heap
)
98 void **ptrs
= heap
->ptrs
;
100 switch (heap
->size
) {
108 /* Shrink, replace the current max by previous last entry and heapify */
109 return heap_replace_max(heap
, ptrs
[--heap
->size
]);
112 void *heap_cherrypick(struct ptr_heap
*heap
, void *p
)
114 void **ptrs
= heap
->ptrs
;
115 size_t pos
, size
= heap
->size
;
117 for (pos
= 0; pos
< size
; pos
++)
122 if (heap
->size
== 1) {
127 * Replace p with previous last entry and heapify.
129 ptrs
[pos
] = ptrs
[--heap
->size
];
This page took 0.034369 seconds and 5 git commands to generate.