1 // util/heap.h -- A heap-based priority queue implementation
3 // This software is copyright (c) 2006 Scott Wood <scott@buserror.net>.
5 // Permission is hereby granted, free of charge, to any person obtaining a copy of
6 // this software and associated documentation files (the "Software"), to deal with
7 // the Software without restriction, including without limitation the rights to
8 // use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
9 // of the Software, and to permit persons to whom the Software is furnished to do
10 // so, subject to the following conditions:
12 // * Redistributions of source code must retain the above copyright notice,
13 // this list of conditions and the following disclaimers.
15 // * Redistributions in binary form must reproduce the above copyright notice,
16 // this list of conditions and the following disclaimers in the
17 // documentation and/or other materials provided with the distribution.
19 // * The names of the Software's authors and/or contributors
20 // may not be used to endorse or promote products derived from
21 // this Software without specific prior written permission.
23 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
25 // FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 // CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
37 #include <lowlevel/bitops.h>
40 // T must support operator < for key ordering, and
41 // have a Heap<T>::Node member called heap_node.
47 Node *parent, *left, *right;
49 // A pointer to the parent's left or right pointer
50 // (whichever side this node is on). This is also
51 // used for sanity checks (it is NULL for nodes not
58 parent = left = right = NULL;
64 return parentlink != NULL;
72 T *node_to_type(Node *n)
74 return reinterpret_cast<T *>(reinterpret_cast<uintptr_t>(n) -
75 offsetof(T, heap_node));
78 // Swap n with its parent
84 n->parent = p->parent;
87 Node **plink = p->parentlink;
89 if (n->parentlink == &p->left) {
99 p->parentlink = &n->left;
102 n->right->parent = n;
103 n->right->parentlink = &n->right;
106 assert(n->parentlink == &p->right);
107 assert(p->right == n);
116 p->parentlink = &n->right;
120 n->left->parentlink = &n->left;
126 p->left->parentlink = &p->left;
129 p->right->parent = p;
130 p->right->parentlink = &p->right;
136 n->parentlink = plink;
139 // Restore heap condition by moving n towards the root,
144 T *n_type = node_to_type(n);
146 assert(!n->left || !(*node_to_type(n->left) < *n_type));
147 assert(!n->right || !(*node_to_type(n->right) < *n_type));
149 while (n->parent && *n_type < *node_to_type(n->parent)) {
150 assert(!n->left || !(*node_to_type(n->left) < *n_type));
151 assert(!n->right || !(*node_to_type(n->right) < *n_type));
156 assert(!n->left || !(*node_to_type(n->left) < *n_type));
157 assert(!n->right || !(*node_to_type(n->right) < *n_type));
160 // Restore heap condition by moving n towards the leaves,
165 T *n_type = node_to_type(n);
167 assert(!n->parent || !(*n_type < *node_to_type(n->parent)));
169 // If n has a right, it'll have a left.
171 assert(!n->parent || !(*n_type < *node_to_type(n->parent)));
172 Node *child = n->left;
175 *node_to_type(n->right) < *node_to_type(n->left))
178 if (*node_to_type(child) < *n_type)
184 assert(!n->parent || !(*n_type < *node_to_type(n->parent)));
187 Node *get_by_index(size_t num, Node **parent, Node ***link)
189 assert(num_nodes == 0 || top);
190 assert(num <= num_nodes);
192 // It's easier to use 1-based indices, so that the high set bit
193 // perfectly indicates which level the node is on.
198 size_t bit = 1 << ll_get_order_round_down(num);
200 Node **nextlink = ⊤
210 nextlink = &n->right;
227 return num_nodes == 0;
235 return node_to_type(top);
240 Node *n = &t->heap_node;
241 assert(!n->is_on_heap());
243 Node *ret = get_by_index(num_nodes, &n->parent, &n->parentlink);
246 assert(num_nodes == 0 || n->parent);
250 n->left = n->right = NULL;
257 Node *n = &t->heap_node;
258 assert(*n->parentlink == n);
260 if (--num_nodes == 0) {
262 n->parentlink = NULL;
266 Node *parent, **link;
267 Node *last = get_by_index(num_nodes, &parent, &link);
269 assert(last->parent);
270 assert(last->is_on_heap());
272 assert(!last->right);
275 *n->parentlink = last;
277 n->parentlink = NULL;
280 last->left->parent = last;
281 last->left->parentlink = &last->left;
285 last->right->parent = last;
286 last->right->parentlink = &last->right;
293 Node *n = &t->heap_node;
294 assert(*n->parentlink == n);
296 if (!n->parent || *node_to_type(n->parent) < *t)