hrtimer: optimize the softirq time optimization
[linux-2.6/zen-sources.git] / lib / prio_heap.c
blob471944a54e23ecb964397a76716ea60236c5fdf3
1 /*
2 * Simple insertion-only static-sized priority heap containing
3 * pointers, based on CLR, chapter 7
4 */
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);
13 if (!heap->ptrs)
14 return -ENOMEM;
15 heap->size = 0;
16 heap->max = size / sizeof(void *);
17 heap->gt = gt;
18 return 0;
21 void heap_free(struct ptr_heap *heap)
23 kfree(heap->ptrs);
26 void *heap_insert(struct ptr_heap *heap, void *p)
28 void *res;
29 void **ptrs = heap->ptrs;
30 int pos;
32 if (heap->size < heap->max) {
33 /* Heap insertion */
34 int pos = heap->size++;
35 while (pos > 0 && heap->gt(p, ptrs[(pos-1)/2])) {
36 ptrs[pos] = ptrs[(pos-1)/2];
37 pos = (pos-1)/2;
39 ptrs[pos] = p;
40 return NULL;
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]))
47 return p;
49 /* Replace the current max and heapify */
50 res = ptrs[0];
51 ptrs[0] = p;
52 pos = 0;
54 while (1) {
55 int left = 2 * pos + 1;
56 int right = 2 * pos + 2;
57 int largest = pos;
58 if (left < heap->size && heap->gt(ptrs[left], p))
59 largest = left;
60 if (right < heap->size && heap->gt(ptrs[right], ptrs[largest]))
61 largest = right;
62 if (largest == pos)
63 break;
64 /* Push p down the heap one level and bump one up */
65 ptrs[pos] = ptrs[largest];
66 ptrs[largest] = p;
67 pos = largest;
69 return res;