1 // util/heap.h -- A heap-based priority queue implementation
3 // This software is copyright (c) 2006 Scott Wood <scott@buserror.net>.
5 // This software is provided 'as-is', without any express or implied warranty.
6 // In no event will the authors or contributors be held liable for any damages
7 // arising from the use of this software.
9 // Permission is hereby granted to everyone, free of charge, to use, copy,
10 // modify, prepare derivative works of, publish, distribute, perform,
11 // sublicense, and/or sell copies of the Software, provided that the above
12 // copyright notice and disclaimer of warranty be included in all copies or
13 // substantial portions of this software.
21 #include <lowlevel/bitops.h>
24 // T must support operator < for key ordering, and
25 // have a Heap<T>::Node member called heap_node.
31 Node *parent, *left, *right;
33 // A pointer to the parent's left or right pointer
34 // (whichever side this node is on). This is also
35 // used for sanity checks (it is NULL for nodes not
42 parent = left = right = NULL;
48 return parentlink != NULL;
56 T *node_to_type(Node *n)
58 return reinterpret_cast<T *>(reinterpret_cast<uintptr_t>(n) -
59 offsetof(T, heap_node));
62 // Swap n with its parent
68 n->parent = p->parent;
71 Node **plink = p->parentlink;
73 if (n->parentlink == &p->left) {
83 p->parentlink = &n->left;
87 n->right->parentlink = &n->right;
90 assert(n->parentlink == &p->right);
91 assert(p->right == n);
100 p->parentlink = &n->right;
104 n->left->parentlink = &n->left;
110 p->left->parentlink = &p->left;
113 p->right->parent = p;
114 p->right->parentlink = &p->right;
120 n->parentlink = plink;
123 // Restore heap condition by moving n towards the root,
128 T *n_type = node_to_type(n);
130 assert(!n->left || !(*node_to_type(n->left) < *n_type));
131 assert(!n->right || !(*node_to_type(n->right) < *n_type));
133 while (n->parent && *n_type < *node_to_type(n->parent)) {
134 assert(!n->left || !(*node_to_type(n->left) < *n_type));
135 assert(!n->right || !(*node_to_type(n->right) < *n_type));
140 assert(!n->left || !(*node_to_type(n->left) < *n_type));
141 assert(!n->right || !(*node_to_type(n->right) < *n_type));
144 // Restore heap condition by moving n towards the leaves,
149 T *n_type = node_to_type(n);
151 assert(!n->parent || !(*n_type < *node_to_type(n->parent)));
153 // If n has a right, it'll have a left.
155 assert(!n->parent || !(*n_type < *node_to_type(n->parent)));
156 Node *child = n->left;
159 *node_to_type(n->right) < *node_to_type(n->left))
162 if (*node_to_type(child) < *n_type)
168 assert(!n->parent || !(*n_type < *node_to_type(n->parent)));
171 Node *get_by_index(size_t num, Node **parent, Node ***link)
173 assert(num_nodes == 0 || top);
174 assert(num <= num_nodes);
176 // It's easier to use 1-based indices, so that the high set bit
177 // perfectly indicates which level the node is on.
182 size_t bit = 1 << ll_get_order_round_down(num);
184 Node **nextlink = ⊤
194 nextlink = &n->right;
211 return num_nodes == 0;
219 return node_to_type(top);
224 Node *n = &t->heap_node;
225 assert(!n->is_on_heap());
227 Node *ret = get_by_index(num_nodes, &n->parent, &n->parentlink);
230 assert(num_nodes == 0 || n->parent);
234 n->left = n->right = NULL;
241 Node *n = &t->heap_node;
242 assert(*n->parentlink == n);
244 if (--num_nodes == 0) {
246 n->parentlink = NULL;
250 Node *parent, **link;
251 Node *last = get_by_index(num_nodes, &parent, &link);
253 assert(last->parent);
254 assert(last->is_on_heap());
256 assert(!last->right);
259 *n->parentlink = last;
261 n->parentlink = NULL;
264 last->left->parent = last;
265 last->left->parentlink = &last->left;
269 last->right->parent = last;
270 last->right->parentlink = &last->right;
277 Node *n = &t->heap_node;
278 assert(*n->parentlink == n);
280 if (!n->parent || *node_to_type(n->parent) < *t)