| Paul Menage | 8707d8b | 2007-10-18 23:40:22 -0700 | [diff] [blame] | 1 | #ifndef _LINUX_PRIO_HEAP_H |
| 2 | #define _LINUX_PRIO_HEAP_H |
| 3 | |
| 4 | /* |
| 5 | * Simple insertion-only static-sized priority heap containing |
| 6 | * pointers, based on CLR, chapter 7 |
| 7 | */ |
| 8 | |
| 9 | #include <linux/gfp.h> |
| 10 | |
| 11 | /** |
| 12 | * struct ptr_heap - simple static-sized priority heap |
| 13 | * @ptrs - pointer to data area |
| 14 | * @max - max number of elements that can be stored in @ptrs |
| 15 | * @size - current number of valid elements in @ptrs (in the range 0..@size-1 |
| 16 | * @gt: comparison operator, which should implement "greater than" |
| 17 | */ |
| 18 | struct ptr_heap { |
| 19 | void **ptrs; |
| 20 | int max; |
| 21 | int size; |
| 22 | int (*gt)(void *, void *); |
| 23 | }; |
| 24 | |
| 25 | /** |
| 26 | * heap_init - initialize an empty heap with a given memory size |
| 27 | * @heap: the heap structure to be initialized |
| 28 | * @size: amount of memory to use in bytes |
| 29 | * @gfp_mask: mask to pass to kmalloc() |
| 30 | * @gt: comparison operator, which should implement "greater than" |
| 31 | */ |
| 32 | extern int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask, |
| 33 | int (*gt)(void *, void *)); |
| 34 | |
| 35 | /** |
| 36 | * heap_free - release a heap's storage |
| 37 | * @heap: the heap structure whose data should be released |
| 38 | */ |
| 39 | void heap_free(struct ptr_heap *heap); |
| 40 | |
| 41 | /** |
| 42 | * heap_insert - insert a value into the heap and return any overflowed value |
| 43 | * @heap: the heap to be operated on |
| 44 | * @p: the pointer to be inserted |
| 45 | * |
| 46 | * Attempts to insert the given value into the priority heap. If the |
| 47 | * heap is full prior to the insertion, then the resulting heap will |
| 48 | * consist of the smallest @max elements of the original heap and the |
| 49 | * new element; the greatest element will be removed from the heap and |
| 50 | * returned. Note that the returned element will be the new element |
| 51 | * (i.e. no change to the heap) if the new element is greater than all |
| 52 | * elements currently in the heap. |
| 53 | */ |
| 54 | extern void *heap_insert(struct ptr_heap *heap, void *p); |
| 55 | |
| 56 | |
| 57 | |
| 58 | #endif /* _LINUX_PRIO_HEAP_H */ |