Blame view
lib/prio_heap.c
1.44 KB
8707d8b8c Fix cpusets updat... |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
/* * Simple insertion-only static-sized priority heap containing * pointers, based on CLR, chapter 7 */ #include <linux/slab.h> #include <linux/prio_heap.h> int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask, int (*gt)(void *, void *)) { heap->ptrs = kmalloc(size, gfp_mask); if (!heap->ptrs) return -ENOMEM; heap->size = 0; heap->max = size / sizeof(void *); heap->gt = gt; return 0; } void heap_free(struct ptr_heap *heap) { kfree(heap->ptrs); } void *heap_insert(struct ptr_heap *heap, void *p) { void *res; void **ptrs = heap->ptrs; int pos; if (heap->size < heap->max) { /* Heap insertion */ |
40bc1f2db lib: fix sparse s... |
34 |
pos = heap->size++; |
8707d8b8c Fix cpusets updat... |
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
while (pos > 0 && heap->gt(p, ptrs[(pos-1)/2])) { ptrs[pos] = ptrs[(pos-1)/2]; pos = (pos-1)/2; } ptrs[pos] = p; return NULL; } /* The heap is full, so something will have to be dropped */ /* If the new pointer is greater than the current max, drop it */ if (heap->gt(p, ptrs[0])) return p; /* Replace the current max and heapify */ res = ptrs[0]; ptrs[0] = p; pos = 0; while (1) { int left = 2 * pos + 1; int right = 2 * pos + 2; int largest = pos; if (left < heap->size && heap->gt(ptrs[left], p)) largest = left; if (right < heap->size && heap->gt(ptrs[right], ptrs[largest])) largest = right; if (largest == pos) break; /* Push p down the heap one level and bump one up */ ptrs[pos] = ptrs[largest]; ptrs[largest] = p; pos = largest; } return res; } |