1 /* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl>
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.
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.
16 #ifndef UV_SRC_HEAP_H_
17 #define UV_SRC_HEAP_H_
19 #include <stddef.h> /* NULL */
22 # define HEAP_EXPORT(declaration) __attribute__((unused)) static declaration
24 # define HEAP_EXPORT(declaration) static declaration
28 struct heap_node* left;
29 struct heap_node* right;
30 struct heap_node* parent;
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.
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.
41 struct heap_node* min;
45 /* Return non-zero if a < b. */
46 typedef int (*heap_compare_fn)(const struct heap_node* a,
47 const struct heap_node* b);
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));
60 /* Implementation follows. */
62 HEAP_EXPORT(void heap_init(struct heap* heap)) {
67 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
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;
82 parent->parent = child;
83 if (child->left == child) {
85 sibling = child->right;
87 child->right = parent;
88 sibling = child->left;
91 sibling->parent = child;
93 if (parent->left != NULL)
94 parent->left->parent = parent;
95 if (parent->right != NULL)
96 parent->right->parent = parent;
98 if (child->parent == NULL)
100 else if (child->parent->left == parent)
101 child->parent->left = child;
103 child->parent->right = child;
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;
115 newnode->left = NULL;
116 newnode->right = NULL;
117 newnode->parent = NULL;
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.
123 for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
124 path = (path << 1) | (n & 1);
126 /* Now traverse the heap using the path we calculated in the previous step. */
127 parent = child = &heap->min;
131 child = &(*child)->right;
133 child = &(*child)->left;
138 /* Insert the new node. */
139 newnode->parent = *parent;
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.
146 while (newnode->parent != NULL && less_than(newnode, newnode->parent))
147 heap_node_swap(heap, newnode->parent, newnode);
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;
160 if (heap->nelts == 0)
163 /* Calculate the path from the min (the root) to the max, the left-most node
167 for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
168 path = (path << 1) | (n & 1);
170 /* Now traverse the heap using the path we calculated in the previous step. */
174 max = &(*max)->right;
183 /* Unlink the max node. */
188 /* We're removing either the max or the last node in the tree. */
189 if (child == heap->min) {
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;
200 if (child->left != NULL) {
201 child->left->parent = child;
204 if (child->right != NULL) {
205 child->right->parent = child;
208 if (node->parent == NULL) {
210 } else if (node->parent->left == node) {
211 node->parent->left = child;
213 node->parent->right = child;
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.
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)
228 heap_node_swap(heap, child, smallest);
232 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
233 heap_remove(heap, heap->min, less_than);
238 #endif /* UV_SRC_HEAP_H_ */