aboutsummaryrefslogtreecommitdiffstats
path: root/include/litmus/heap.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/litmus/heap.h')
-rw-r--r--include/litmus/heap.h77
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
11struct 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
21struct 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
29typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b);
30
31void heap_init(struct heap* heap);
32void heap_node_init(struct heap_node** ref_to_heap_node_ptr, void* value);
33
34static inline int heap_node_in_heap(struct heap_node* h)
35{
36 return h->degree != NOT_IN_HEAP;
37}
38
39static 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 */
45void heap_insert(heap_prio_t higher_prio,
46 struct heap* heap,
47 struct heap_node* node);
48
49/* merge addition into target */
50void heap_union(heap_prio_t higher_prio,
51 struct heap* target,
52 struct heap* addition);
53
54struct heap_node* heap_peek(heap_prio_t higher_prio,
55 struct heap* heap);
56
57struct heap_node* heap_take(heap_prio_t higher_prio,
58 struct heap* heap);
59
60void heap_uncache_min(heap_prio_t higher_prio, struct heap* heap);
61int heap_decrease(heap_prio_t higher_prio, struct heap_node* node);
62
63void heap_delete(heap_prio_t higher_prio,
64 struct heap* heap,
65 struct heap_node* node);
66
67/* allocate from memcache */
68struct heap_node* heap_node_alloc(int gfp_flags);
69void heap_node_free(struct heap_node* hn);
70
71/* allocate a heap node for value and insert into the heap */
72int heap_add(heap_prio_t higher_prio, struct heap* heap,
73 void* value, int gfp_flags);
74
75void* heap_take_del(heap_prio_t higher_prio,
76 struct heap* heap);
77#endif