xref: /third_party/node/deps/uv/src/heap-inl.h (revision 1cb0ef41) 
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
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
27struct 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 */
40struct heap {
41  struct heap_node* min;
42  unsigned int nelts;
43};
44
45/* Return non-zero if a < b. */
46typedef int (*heap_compare_fn)(const struct heap_node* a,
47                               const struct heap_node* b);
48
49/* Public functions. */
50HEAP_EXPORT(void heap_init(struct heap* heap));
51HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
52HEAP_EXPORT(void heap_insert(struct heap* heap,
53                             struct heap_node* newnode,
54                             heap_compare_fn less_than));
55HEAP_EXPORT(void heap_remove(struct heap* heap,
56                             struct heap_node* node,
57                             heap_compare_fn less_than));
58HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));
59
60/* Implementation follows. */
61
62HEAP_EXPORT(void heap_init(struct heap* heap)) {
63  heap->min = NULL;
64  heap->nelts = 0;
65}
66
67HEAP_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. */
72static 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
106HEAP_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
150HEAP_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
239HEAP_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_ */
246