1 /* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl>
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 #include "uv_log.h"
21
22 #if defined(__GNUC__)
23 # define HEAP_EXPORT(declaration) __attribute__((unused)) static declaration
24 #else
25 # define HEAP_EXPORT(declaration) static declaration
26 #endif
27
28 struct heap_node {
29 struct heap_node* left;
30 struct heap_node* right;
31 struct heap_node* parent;
32 };
33
34 /* A binary min heap. The usual properties hold: the root is the lowest
35 * element in the set, the height of the tree is at most log2(nodes) and
36 * it's always a complete binary tree.
37 *
38 * The heap function try hard to detect corrupted tree nodes at the cost
39 * of a minor reduction in performance. Compile with -DNDEBUG to disable.
40 */
41 struct heap {
42 struct heap_node* min;
43 unsigned int nelts;
44 };
45
46 /* Return non-zero if a < b. */
47 typedef int (*heap_compare_fn)(const struct heap_node* a,
48 const struct heap_node* b);
49
50 /* Public functions. */
51 HEAP_EXPORT(void heap_init(struct heap* heap));
52 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
53 HEAP_EXPORT(void heap_insert(struct heap* heap,
54 struct heap_node* newnode,
55 heap_compare_fn less_than));
56 HEAP_EXPORT(void heap_remove(struct heap* heap,
57 struct heap_node* node,
58 heap_compare_fn less_than));
59 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));
60
61 /* Implementation follows. */
62
HEAP_EXPORT(void heap_init (struct heap * heap))63 HEAP_EXPORT(void heap_init(struct heap* heap)) {
64 heap->min = NULL;
65 heap->nelts = 0;
66 }
67
HEAP_EXPORT(struct heap_node * heap_min (const struct heap * heap))68 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
69 return heap->min;
70 }
71
72 /* Swap parent with child. Child moves closer to the root, parent moves away. */
heap_node_swap(struct heap * heap,struct heap_node * parent,struct heap_node * child)73 static void heap_node_swap(struct heap* heap,
74 struct heap_node* parent,
75 struct heap_node* child) {
76 struct heap_node* sibling;
77 struct heap_node t;
78
79 t = *parent;
80 *parent = *child;
81 *child = t;
82
83 parent->parent = child;
84 if (child->left == child) {
85 child->left = parent;
86 sibling = child->right;
87 } else {
88 child->right = parent;
89 sibling = child->left;
90 }
91 if (sibling != NULL)
92 sibling->parent = child;
93
94 if (parent->left != NULL)
95 parent->left->parent = parent;
96 if (parent->right != NULL)
97 parent->right->parent = parent;
98
99 if (child->parent == NULL)
100 heap->min = child;
101 else if (child->parent->left == parent)
102 child->parent->left = child;
103 else
104 child->parent->right = child;
105 }
106
HEAP_EXPORT(void heap_insert (struct heap * heap,struct heap_node * newnode,heap_compare_fn less_than))107 HEAP_EXPORT(void heap_insert(struct heap* heap,
108 struct heap_node* newnode,
109 heap_compare_fn less_than)) {
110 struct heap_node** parent;
111 struct heap_node** child;
112 unsigned int path;
113 unsigned int n;
114 unsigned int k;
115
116 newnode->left = NULL;
117 newnode->right = NULL;
118 newnode->parent = NULL;
119
120 /* Calculate the path from the root to the insertion point. This is a min
121 * heap so we always insert at the left-most free node of the bottom row.
122 */
123 path = 0;
124 for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
125 path = (path << 1) | (n & 1);
126
127 /* Now traverse the heap using the path we calculated in the previous step. */
128 parent = child = &heap->min;
129 while (k > 0) {
130 parent = child;
131 if (path & 1)
132 child = &(*child)->right;
133 else
134 child = &(*child)->left;
135 path >>= 1;
136 k -= 1;
137 }
138
139 /* Insert the new node. */
140 newnode->parent = *parent;
141 *child = newnode;
142 heap->nelts += 1;
143
144 /* Walk up the tree and check at each node if the heap property holds.
145 * It's a min heap so parent < child must be true.
146 */
147 while (newnode->parent != NULL && less_than(newnode, newnode->parent))
148 heap_node_swap(heap, newnode->parent, newnode);
149 }
150
HEAP_EXPORT(void heap_remove (struct heap * heap,struct heap_node * node,heap_compare_fn less_than))151 HEAP_EXPORT(void heap_remove(struct heap* heap,
152 struct heap_node* node,
153 heap_compare_fn less_than)) {
154 struct heap_node* smallest;
155 struct heap_node** max;
156 struct heap_node* child;
157 unsigned int path;
158 unsigned int k;
159 unsigned int n;
160
161 if (heap->nelts == 0)
162 return;
163
164 /* Calculate the path from the min (the root) to the max, the left-most node
165 * of the bottom row.
166 */
167 path = 0;
168 for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
169 path = (path << 1) | (n & 1);
170
171 /* Now traverse the heap using the path we calculated in the previous step. */
172 max = &heap->min;
173 while (k > 0) {
174 if (path & 1)
175 max = &(*max)->right;
176 else
177 max = &(*max)->left;
178 path >>= 1;
179 k -= 1;
180 }
181
182
183 /* Unlink the max node. */
184 child = *max;
185 *max = NULL;
186 #ifdef USE_OHOS_DFX
187 if (child == NULL) {
188 UV_LOGF("Child is NULL, this may be due to multi-threaded calls.");
189 return;
190 }
191 #endif
192 heap->nelts -= 1;
193
194 if (child == node) {
195 /* We're removing either the max or the last node in the tree. */
196 if (child == heap->min) {
197 heap->min = NULL;
198 }
199 return;
200 }
201
202 /* Replace the to be deleted node with the max node. */
203 child->left = node->left;
204 child->right = node->right;
205 child->parent = node->parent;
206
207 if (child->left != NULL) {
208 child->left->parent = child;
209 }
210
211 if (child->right != NULL) {
212 child->right->parent = child;
213 }
214
215 if (node->parent == NULL) {
216 heap->min = child;
217 } else if (node->parent->left == node) {
218 node->parent->left = child;
219 } else {
220 node->parent->right = child;
221 }
222
223 /* Walk down the subtree and check at each node if the heap property holds.
224 * It's a min heap so parent < child must be true. If the parent is bigger,
225 * swap it with the smallest child.
226 */
227 for (;;) {
228 smallest = child;
229 if (child->left != NULL && less_than(child->left, smallest))
230 smallest = child->left;
231 if (child->right != NULL && less_than(child->right, smallest))
232 smallest = child->right;
233 if (smallest == child)
234 break;
235 heap_node_swap(heap, child, smallest);
236 }
237
238 /* Walk up the subtree and check that each parent is less than the node
239 * this is required, because `max` node is not guaranteed to be the
240 * actual maximum in tree
241 */
242 while (child->parent != NULL && less_than(child, child->parent))
243 heap_node_swap(heap, child->parent, child);
244 }
245
HEAP_EXPORT(void heap_dequeue (struct heap * heap,heap_compare_fn less_than))246 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
247 heap_remove(heap, heap->min, less_than);
248 }
249
250 #undef HEAP_EXPORT
251
252 #endif /* UV_SRC_HEAP_H_ */
253