Commit | Line | Data |
---|---|---|
8707d8b8 PM |
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 */ |