blob: 31de626db36b6146324e6ee4843063ead5fa82d2 [file] [log] [blame]
swissChilie4f01992021-02-25 15:38:12 -08001#include "kheap.h"
2#include "log.h"
3
4static void swap_entries(struct heap_entry *a, struct heap_entry *b)
5{
6 // Static to not waste stack space, NOT thread safe
7 static struct heap_entry tmp;
8 tmp = *a;
9 *a = *b;
10 *b = tmp;
11}
12
13int heap_parent(int i)
14{
15 return (i - 1) / 2;
16}
17
18int heap_left(int i)
19{
20 return 2 * i + 1;
21}
22
23int heap_right(int i)
24{
25 return 2 * i + 2;
26}
27
28static void heap_sort(struct min_heap *heap, int i)
29{
30 int l = heap_left(i), r = heap_right(i);
31 int smallest = i;
32 int size = heap->size;
33 struct heap_entry *e = heap->elements;
34
35 if (l < size && e[l].key < e[smallest].key)
36 smallest = l;
37 if (r < size && e[r].key < e[smallest].key)
38 smallest = r;
39
40 if (smallest != i)
41 {
42 swap_entries(&e[i], &e[smallest]);
43 heap_sort(heap, smallest);
44 }
45}
46
47static void heap_delete_root(struct min_heap *heap)
48{
49 if (heap->size <= 0)
50 return;
51 if (heap->size == 1)
52 heap->size--;
53
54 heap->elements[0] = heap->elements[--heap->size];
55 heap_sort(heap, 0);
56}
57
58void heap_decrease(struct min_heap *heap, int i, struct heap_entry to)
59{
60 heap->elements[i] = to;
61 int k = to.key;
62
63 while (i && heap->elements[heap_parent(i)].key > k)
64 {
65 swap_entries(&heap->elements[i], &heap->elements[heap_parent(i)]);
66 i = heap_parent(i);
67 }
68}
69
70void heap_delete(struct min_heap *heap, int i)
71{
72 heap_decrease(heap, i,
73 (struct heap_entry){
74 .key = -1,
75 .address = 0,
76 });
77 heap_delete_root(heap);
78}
79
80void heap_insert(struct min_heap *heap, struct heap_entry e)
81{
82 kassert(heap->size < HEAP_SIZE, "Heap overflow!");
83
84 int i = heap->size++;
85 uint k = e.key;
86 heap->elements[i] = e;
87
88 // While the parent element is GREATER than the child
89 while (i && heap->elements[heap_parent(i)].key > k)
90 {
91 swap_entries(&heap->elements[i], &heap->elements[heap_parent(i)]);
92 i = heap_parent(i);
93 }
94}
95
96struct heap_entry heap_lookup_min(struct min_heap *heap, int min, bool *ok,
97 bool delete, int *i)
98{
99 int j = 0;
100 struct heap_entry *e = heap->elements;
101
102 while (j < heap->size && e[j].key < min)
103 {
104 int left = heap_left(j), right = heap_right(j);
105
106 // If left is invalid, use right, if right is invalid, use left.
107 // If both are valid, chose the smallest one.
108 // In the first case, right may too be invalid, but it will be
109 // sorted out in the while loop (see else clause at end of function).
110
111 if (left >= heap->size)
112 j = right;
113 else if (right >= heap->size)
114 j = left;
115 else
116 j = e[left].key < e[right].key ? left : right;
117 }
118
119 if (j < heap->size)
120 {
121 struct heap_entry val = e[j];
122
123 *ok = true;
124
125 if (i)
126 *i = j;
127
128 if (delete)
129 heap_delete(heap, j);
130
131 return val;
132 }
133 else
134 {
135 *ok = false;
136 return (struct heap_entry){0};
137 }
138}