Root/
1 | /* |
2 | * Simple insertion-only static-sized priority heap containing |
3 | * pointers, based on CLR, chapter 7 |
4 | */ |
5 | |
6 | #include <linux/slab.h> |
7 | #include <linux/prio_heap.h> |
8 | |
9 | int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask, |
10 | int (*gt)(void *, void *)) |
11 | { |
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; |
19 | } |
20 | |
21 | void heap_free(struct ptr_heap *heap) |
22 | { |
23 | kfree(heap->ptrs); |
24 | } |
25 | |
26 | void *heap_insert(struct ptr_heap *heap, void *p) |
27 | { |
28 | void *res; |
29 | void **ptrs = heap->ptrs; |
30 | int pos; |
31 | |
32 | if (heap->size < heap->max) { |
33 | /* Heap insertion */ |
34 | 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; |
38 | } |
39 | ptrs[pos] = p; |
40 | return NULL; |
41 | } |
42 | |
43 | /* The heap is full, so something will have to be dropped */ |
44 | |
45 | /* If the new pointer is greater than the current max, drop it */ |
46 | if (heap->gt(p, ptrs[0])) |
47 | return p; |
48 | |
49 | /* Replace the current max and heapify */ |
50 | res = ptrs[0]; |
51 | ptrs[0] = p; |
52 | pos = 0; |
53 | |
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; |
68 | } |
69 | return res; |
70 | } |
71 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9