diff options
Diffstat (limited to 'include/litmus/heap.h')
-rw-r--r-- | include/litmus/heap.h | 77 |
1 files changed, 0 insertions, 77 deletions
diff --git a/include/litmus/heap.h b/include/litmus/heap.h deleted file mode 100644 index da959b0bec9c..000000000000 --- a/include/litmus/heap.h +++ /dev/null | |||
@@ -1,77 +0,0 @@ | |||
1 | /* heaps.h -- Binomial Heaps | ||
2 | * | ||
3 | * (c) 2008, 2009 Bjoern Brandenburg | ||
4 | */ | ||
5 | |||
6 | #ifndef HEAP_H | ||
7 | #define HEAP_H | ||
8 | |||
9 | #define NOT_IN_HEAP UINT_MAX | ||
10 | |||
11 | struct heap_node { | ||
12 | struct heap_node* parent; | ||
13 | struct heap_node* next; | ||
14 | struct heap_node* child; | ||
15 | |||
16 | unsigned int degree; | ||
17 | void* value; | ||
18 | struct heap_node** ref; | ||
19 | }; | ||
20 | |||
21 | struct heap { | ||
22 | struct heap_node* head; | ||
23 | /* We cache the minimum of the heap. | ||
24 | * This speeds up repeated peek operations. | ||
25 | */ | ||
26 | struct heap_node* min; | ||
27 | }; | ||
28 | |||
29 | typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b); | ||
30 | |||
31 | void heap_init(struct heap* heap); | ||
32 | void heap_node_init(struct heap_node** ref_to_heap_node_ptr, void* value); | ||
33 | |||
34 | static inline int heap_node_in_heap(struct heap_node* h) | ||
35 | { | ||
36 | return h->degree != NOT_IN_HEAP; | ||
37 | } | ||
38 | |||
39 | static inline int heap_empty(struct heap* heap) | ||
40 | { | ||
41 | return heap->head == NULL && heap->min == NULL; | ||
42 | } | ||
43 | |||
44 | /* insert (and reinitialize) a node into the heap */ | ||
45 | void heap_insert(heap_prio_t higher_prio, | ||
46 | struct heap* heap, | ||
47 | struct heap_node* node); | ||
48 | |||
49 | /* merge addition into target */ | ||
50 | void heap_union(heap_prio_t higher_prio, | ||
51 | struct heap* target, | ||
52 | struct heap* addition); | ||
53 | |||
54 | struct heap_node* heap_peek(heap_prio_t higher_prio, | ||
55 | struct heap* heap); | ||
56 | |||
57 | struct heap_node* heap_take(heap_prio_t higher_prio, | ||
58 | struct heap* heap); | ||
59 | |||
60 | void heap_uncache_min(heap_prio_t higher_prio, struct heap* heap); | ||
61 | int heap_decrease(heap_prio_t higher_prio, struct heap_node* node); | ||
62 | |||
63 | void heap_delete(heap_prio_t higher_prio, | ||
64 | struct heap* heap, | ||
65 | struct heap_node* node); | ||
66 | |||
67 | /* allocate from memcache */ | ||
68 | struct heap_node* heap_node_alloc(int gfp_flags); | ||
69 | void heap_node_free(struct heap_node* hn); | ||
70 | |||
71 | /* allocate a heap node for value and insert into the heap */ | ||
72 | int heap_add(heap_prio_t higher_prio, struct heap* heap, | ||
73 | void* value, int gfp_flags); | ||
74 | |||
75 | void* heap_take_del(heap_prio_t higher_prio, | ||
76 | struct heap* heap); | ||
77 | #endif | ||