|
160
|
1 /* Copyright (c) 2013, Ben Noordhuis <[email protected]>
|
|
|
2 *
|
|
|
3 * Permission to use, copy, modify, and/or distribute this software for any
|
|
|
4 * purpose with or without fee is hereby granted, provided that the above
|
|
|
5 * copyright notice and this permission notice appear in all copies.
|
|
|
6 *
|
|
|
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
|
|
|
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
|
|
|
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
|
|
|
10 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
|
|
|
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
|
|
|
12 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
|
|
|
13 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
|
|
|
14 */
|
|
|
15
|
|
|
16 #ifndef UV_SRC_HEAP_H_
|
|
|
17 #define UV_SRC_HEAP_H_
|
|
|
18
|
|
|
19 #include <stddef.h> /* NULL */
|
|
|
20
|
|
|
21 #if defined(__GNUC__)
|
|
|
22 # define HEAP_EXPORT(declaration) __attribute__((unused)) static declaration
|
|
|
23 #else
|
|
|
24 # define HEAP_EXPORT(declaration) static declaration
|
|
|
25 #endif
|
|
|
26
|
|
|
27 struct heap_node {
|
|
|
28 struct heap_node* left;
|
|
|
29 struct heap_node* right;
|
|
|
30 struct heap_node* parent;
|
|
|
31 };
|
|
|
32
|
|
|
33 /* A binary min heap. The usual properties hold: the root is the lowest
|
|
|
34 * element in the set, the height of the tree is at most log2(nodes) and
|
|
|
35 * it's always a complete binary tree.
|
|
|
36 *
|
|
|
37 * The heap function try hard to detect corrupted tree nodes at the cost
|
|
|
38 * of a minor reduction in performance. Compile with -DNDEBUG to disable.
|
|
|
39 */
|
|
|
40 struct heap {
|
|
|
41 struct heap_node* min;
|
|
|
42 unsigned int nelts;
|
|
|
43 };
|
|
|
44
|
|
|
45 /* Return non-zero if a < b. */
|
|
|
46 typedef int (*heap_compare_fn)(const struct heap_node* a,
|
|
|
47 const struct heap_node* b);
|
|
|
48
|
|
|
49 /* Public functions. */
|
|
|
50 HEAP_EXPORT(void heap_init(struct heap* heap));
|
|
|
51 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
|
|
|
52 HEAP_EXPORT(void heap_insert(struct heap* heap,
|
|
|
53 struct heap_node* newnode,
|
|
|
54 heap_compare_fn less_than));
|
|
|
55 HEAP_EXPORT(void heap_remove(struct heap* heap,
|
|
|
56 struct heap_node* node,
|
|
|
57 heap_compare_fn less_than));
|
|
|
58 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));
|
|
|
59
|
|
|
60 /* Implementation follows. */
|
|
|
61
|
|
|
62 HEAP_EXPORT(void heap_init(struct heap* heap)) {
|
|
|
63 heap->min = NULL;
|
|
|
64 heap->nelts = 0;
|
|
|
65 }
|
|
|
66
|
|
|
67 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
|
|
|
68 return heap->min;
|
|
|
69 }
|
|
|
70
|
|
|
71 /* Swap parent with child. Child moves closer to the root, parent moves away. */
|
|
|
72 static void heap_node_swap(struct heap* heap,
|
|
|
73 struct heap_node* parent,
|
|
|
74 struct heap_node* child) {
|
|
|
75 struct heap_node* sibling;
|
|
|
76 struct heap_node t;
|
|
|
77
|
|
|
78 t = *parent;
|
|
|
79 *parent = *child;
|
|
|
80 *child = t;
|
|
|
81
|
|
|
82 parent->parent = child;
|
|
|
83 if (child->left == child) {
|
|
|
84 child->left = parent;
|
|
|
85 sibling = child->right;
|
|
|
86 } else {
|
|
|
87 child->right = parent;
|
|
|
88 sibling = child->left;
|
|
|
89 }
|
|
|
90 if (sibling != NULL)
|
|
|
91 sibling->parent = child;
|
|
|
92
|
|
|
93 if (parent->left != NULL)
|
|
|
94 parent->left->parent = parent;
|
|
|
95 if (parent->right != NULL)
|
|
|
96 parent->right->parent = parent;
|
|
|
97
|
|
|
98 if (child->parent == NULL)
|
|
|
99 heap->min = child;
|
|
|
100 else if (child->parent->left == parent)
|
|
|
101 child->parent->left = child;
|
|
|
102 else
|
|
|
103 child->parent->right = child;
|
|
|
104 }
|
|
|
105
|
|
|
106 HEAP_EXPORT(void heap_insert(struct heap* heap,
|
|
|
107 struct heap_node* newnode,
|
|
|
108 heap_compare_fn less_than)) {
|
|
|
109 struct heap_node** parent;
|
|
|
110 struct heap_node** child;
|
|
|
111 unsigned int path;
|
|
|
112 unsigned int n;
|
|
|
113 unsigned int k;
|
|
|
114
|
|
|
115 newnode->left = NULL;
|
|
|
116 newnode->right = NULL;
|
|
|
117 newnode->parent = NULL;
|
|
|
118
|
|
|
119 /* Calculate the path from the root to the insertion point. This is a min
|
|
|
120 * heap so we always insert at the left-most free node of the bottom row.
|
|
|
121 */
|
|
|
122 path = 0;
|
|
|
123 for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
|
|
|
124 path = (path << 1) | (n & 1);
|
|
|
125
|
|
|
126 /* Now traverse the heap using the path we calculated in the previous step. */
|
|
|
127 parent = child = &heap->min;
|
|
|
128 while (k > 0) {
|
|
|
129 parent = child;
|
|
|
130 if (path & 1)
|
|
|
131 child = &(*child)->right;
|
|
|
132 else
|
|
|
133 child = &(*child)->left;
|
|
|
134 path >>= 1;
|
|
|
135 k -= 1;
|
|
|
136 }
|
|
|
137
|
|
|
138 /* Insert the new node. */
|
|
|
139 newnode->parent = *parent;
|
|
|
140 *child = newnode;
|
|
|
141 heap->nelts += 1;
|
|
|
142
|
|
|
143 /* Walk up the tree and check at each node if the heap property holds.
|
|
|
144 * It's a min heap so parent < child must be true.
|
|
|
145 */
|
|
|
146 while (newnode->parent != NULL && less_than(newnode, newnode->parent))
|
|
|
147 heap_node_swap(heap, newnode->parent, newnode);
|
|
|
148 }
|
|
|
149
|
|
|
150 HEAP_EXPORT(void heap_remove(struct heap* heap,
|
|
|
151 struct heap_node* node,
|
|
|
152 heap_compare_fn less_than)) {
|
|
|
153 struct heap_node* smallest;
|
|
|
154 struct heap_node** max;
|
|
|
155 struct heap_node* child;
|
|
|
156 unsigned int path;
|
|
|
157 unsigned int k;
|
|
|
158 unsigned int n;
|
|
|
159
|
|
|
160 if (heap->nelts == 0)
|
|
|
161 return;
|
|
|
162
|
|
|
163 /* Calculate the path from the min (the root) to the max, the left-most node
|
|
|
164 * of the bottom row.
|
|
|
165 */
|
|
|
166 path = 0;
|
|
|
167 for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
|
|
|
168 path = (path << 1) | (n & 1);
|
|
|
169
|
|
|
170 /* Now traverse the heap using the path we calculated in the previous step. */
|
|
|
171 max = &heap->min;
|
|
|
172 while (k > 0) {
|
|
|
173 if (path & 1)
|
|
|
174 max = &(*max)->right;
|
|
|
175 else
|
|
|
176 max = &(*max)->left;
|
|
|
177 path >>= 1;
|
|
|
178 k -= 1;
|
|
|
179 }
|
|
|
180
|
|
|
181 heap->nelts -= 1;
|
|
|
182
|
|
|
183 /* Unlink the max node. */
|
|
|
184 child = *max;
|
|
|
185 *max = NULL;
|
|
|
186
|
|
|
187 if (child == node) {
|
|
|
188 /* We're removing either the max or the last node in the tree. */
|
|
|
189 if (child == heap->min) {
|
|
|
190 heap->min = NULL;
|
|
|
191 }
|
|
|
192 return;
|
|
|
193 }
|
|
|
194
|
|
|
195 /* Replace the to be deleted node with the max node. */
|
|
|
196 child->left = node->left;
|
|
|
197 child->right = node->right;
|
|
|
198 child->parent = node->parent;
|
|
|
199
|
|
|
200 if (child->left != NULL) {
|
|
|
201 child->left->parent = child;
|
|
|
202 }
|
|
|
203
|
|
|
204 if (child->right != NULL) {
|
|
|
205 child->right->parent = child;
|
|
|
206 }
|
|
|
207
|
|
|
208 if (node->parent == NULL) {
|
|
|
209 heap->min = child;
|
|
|
210 } else if (node->parent->left == node) {
|
|
|
211 node->parent->left = child;
|
|
|
212 } else {
|
|
|
213 node->parent->right = child;
|
|
|
214 }
|
|
|
215
|
|
|
216 /* Walk down the subtree and check at each node if the heap property holds.
|
|
|
217 * It's a min heap so parent < child must be true. If the parent is bigger,
|
|
|
218 * swap it with the smallest child.
|
|
|
219 */
|
|
|
220 for (;;) {
|
|
|
221 smallest = child;
|
|
|
222 if (child->left != NULL && less_than(child->left, smallest))
|
|
|
223 smallest = child->left;
|
|
|
224 if (child->right != NULL && less_than(child->right, smallest))
|
|
|
225 smallest = child->right;
|
|
|
226 if (smallest == child)
|
|
|
227 break;
|
|
|
228 heap_node_swap(heap, child, smallest);
|
|
|
229 }
|
|
|
230
|
|
|
231 /* Walk up the subtree and check that each parent is less than the node
|
|
|
232 * this is required, because `max` node is not guaranteed to be the
|
|
|
233 * actual maximum in tree
|
|
|
234 */
|
|
|
235 while (child->parent != NULL && less_than(child, child->parent))
|
|
|
236 heap_node_swap(heap, child->parent, child);
|
|
|
237 }
|
|
|
238
|
|
|
239 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
|
|
|
240 heap_remove(heap, heap->min, less_than);
|
|
|
241 }
|
|
|
242
|
|
|
243 #undef HEAP_EXPORT
|
|
|
244
|
|
|
245 #endif /* UV_SRC_HEAP_H_ */
|
