← Back to branch summary

~webapps/unity-js-scopes/node.js

« back to all changes in this revision

Viewing changes to deps/uv/src/heap-inl.h

  • Committer: Marcus Tomlinson
  • Date: 2015-11-13 07:59:04 UTC
  • Revision ID: marcus.tomlinson@canonical.com-20151113075904-h0swczmoq1rvstfc
Node v4 (stable)

Show diffs side-by-side

added added

removed removed

Lines of Context:
deps/uv/src/heap-inl.h
 
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
 
 
27
struct 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
 */
 
40
struct heap {
 
41
  struct heap_node* min;
 
42
  unsigned int nelts;
 
43
};
 
44
 
 
45
/* Return non-zero if a < b. */
 
46
typedef int (*heap_compare_fn)(const struct heap_node* a,
 
47
                               const struct heap_node* b);
 
48
 
 
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));
 
59
 
 
60
/* Implementation follows. */
 
61
 
 
62
HEAP_EXPORT(void heap_init(struct heap* heap)) {
 
63
  heap->min = NULL;
 
64
  heap->nelts = 0;
 
65
}
 
66
 
 
67
HEAP_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. */
 
72
static 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
 
 
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;
 
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
 
 
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;
 
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
 
 
239
HEAP_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_ */