xref: /third_party/libuv/src/heap-inl.h (revision e66f31c5) 
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
28struct 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 */
41struct heap {
42  struct heap_node* min;
43  unsigned int nelts;
44};
45
46/* Return non-zero if a < b. */
47typedef int (*heap_compare_fn)(const struct heap_node* a,
48                               const struct heap_node* b);
49
50/* Public functions. */
51HEAP_EXPORT(void heap_init(struct heap* heap));
52HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
53HEAP_EXPORT(void heap_insert(struct heap* heap,
54                             struct heap_node* newnode,
55                             heap_compare_fn less_than));
56HEAP_EXPORT(void heap_remove(struct heap* heap,
57                             struct heap_node* node,
58                             heap_compare_fn less_than));
59HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));
60
61/* Implementation follows. */
62
63HEAP_EXPORT(void heap_init(struct heap* heap)) {
64  heap->min = NULL;
65  heap->nelts = 0;
66}
67
68HEAP_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. */
73static 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
107HEAP_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
151HEAP_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  /* Unlink the max node. */
183  child = *max;
184  *max = NULL;
185
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
246HEAP_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