Mercurial > hg > Members > anatofuz > MoarVM

annotate 3rdparty/libuv/src/heap-inl.h @ 64:da6d6597bd69 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rollback
author anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
date Fri, 15 Feb 2019 20:51:54 +0900
parents 2cf249471370
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl>
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 *
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 * Permission to use, copy, modify, and/or distribute this software for any
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 * purpose with or without fee is hereby granted, provided that the above
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 * copyright notice and this permission notice appear in all copies.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 *
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 #ifndef UV_SRC_HEAP_H_
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 #define UV_SRC_HEAP_H_
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 #include <stddef.h> /* NULL */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 #if defined(__GNUC__)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 # define HEAP_EXPORT(declaration) __attribute__((unused)) static declaration
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 #else
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 # define HEAP_EXPORT(declaration) static declaration
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 #endif
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 struct heap_node {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 struct heap_node* left;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 struct heap_node* right;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 struct heap_node* parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 };
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 /* A binary min heap. The usual properties hold: the root is the lowest
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 * element in the set, the height of the tree is at most log2(nodes) and
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 * it's always a complete binary tree.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 *
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 * The heap function try hard to detect corrupted tree nodes at the cost
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 * of a minor reduction in performance. Compile with -DNDEBUG to disable.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 struct heap {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 struct heap_node* min;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 unsigned int nelts;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 };
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 /* Return non-zero if a < b. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 typedef int (*heap_compare_fn)(const struct heap_node* a,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 const struct heap_node* b);
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 /* Public functions. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 HEAP_EXPORT(void heap_init(struct heap* heap));
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 HEAP_EXPORT(void heap_insert(struct heap* heap,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 struct heap_node* newnode,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 heap_compare_fn less_than));
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 HEAP_EXPORT(void heap_remove(struct heap* heap,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 struct heap_node* node,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 heap_compare_fn less_than));
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 /* Implementation follows. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 HEAP_EXPORT(void heap_init(struct heap* heap)) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 heap->min = NULL;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 heap->nelts = 0;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 return heap->min;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 /* Swap parent with child. Child moves closer to the root, parent moves away. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 static void heap_node_swap(struct heap* heap,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 struct heap_node* parent,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 struct heap_node* child) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 struct heap_node* sibling;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 struct heap_node t;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 t = *parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 *parent = *child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 *child = t;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
81
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 parent->parent = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 if (child->left == child) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 child->left = parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 sibling = child->right;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 } else {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 child->right = parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 sibling = child->left;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 if (sibling != NULL)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 sibling->parent = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 if (parent->left != NULL)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 parent->left->parent = parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 if (parent->right != NULL)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 parent->right->parent = parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
97
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 if (child->parent == NULL)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 heap->min = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 else if (child->parent->left == parent)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 child->parent->left = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 else
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 child->parent->right = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
105
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 HEAP_EXPORT(void heap_insert(struct heap* heap,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 struct heap_node* newnode,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 heap_compare_fn less_than)) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 struct heap_node** parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 struct heap_node** child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 unsigned int path;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 unsigned int n;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 unsigned int k;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
114
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 newnode->left = NULL;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 newnode->right = NULL;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 newnode->parent = NULL;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
118
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 /* Calculate the path from the root to the insertion point. This is a min
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 * heap so we always insert at the left-most free node of the bottom row.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 path = 0;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 path = (path << 1) | (n & 1);
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
125
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 /* Now traverse the heap using the path we calculated in the previous step. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 parent = child = &heap->min;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 while (k > 0) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 parent = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 if (path & 1)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 child = &(*child)->right;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 else
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 child = &(*child)->left;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 path >>= 1;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 k -= 1;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
136 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
137
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 /* Insert the new node. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 newnode->parent = *parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 *child = newnode;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 heap->nelts += 1;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
142
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 /* Walk up the tree and check at each node if the heap property holds.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 * It's a min heap so parent < child must be true.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 while (newnode->parent != NULL && less_than(newnode, newnode->parent))
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 heap_node_swap(heap, newnode->parent, newnode);
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
149
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 HEAP_EXPORT(void heap_remove(struct heap* heap,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 struct heap_node* node,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 heap_compare_fn less_than)) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 struct heap_node* smallest;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 struct heap_node** max;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 struct heap_node* child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
156 unsigned int path;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 unsigned int k;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 unsigned int n;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
159
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 if (heap->nelts == 0)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 return;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
162
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 /* Calculate the path from the min (the root) to the max, the left-most node
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 * of the bottom row.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
165 */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 path = 0;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 path = (path << 1) | (n & 1);
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
169
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 /* Now traverse the heap using the path we calculated in the previous step. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 max = &heap->min;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 while (k > 0) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 if (path & 1)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
174 max = &(*max)->right;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
175 else
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 max = &(*max)->left;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 path >>= 1;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
178 k -= 1;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
180
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
181 heap->nelts -= 1;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
182
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
183 /* Unlink the max node. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 child = *max;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
185 *max = NULL;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
186
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 if (child == node) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 /* We're removing either the max or the last node in the tree. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 if (child == heap->min) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
190 heap->min = NULL;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
192 return;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 /* Replace the to be deleted node with the max node. */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
196 child->left = node->left;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
197 child->right = node->right;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 child->parent = node->parent;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
199
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
200 if (child->left != NULL) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 child->left->parent = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
203
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 if (child->right != NULL) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 child->right->parent = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
207
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 if (node->parent == NULL) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 heap->min = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 } else if (node->parent->left == node) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
211 node->parent->left = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 } else {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
213 node->parent->right = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
214 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
215
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 /* Walk down the subtree and check at each node if the heap property holds.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 * It's a min heap so parent < child must be true. If the parent is bigger,
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
218 * swap it with the smallest child.
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
219 */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
220 for (;;) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 smallest = child;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 if (child->left != NULL && less_than(child->left, smallest))
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
223 smallest = child->left;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
224 if (child->right != NULL && less_than(child->right, smallest))
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 smallest = child->right;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
226 if (smallest == child)
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
227 break;
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 heap_node_swap(heap, child, smallest);
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
229 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
230
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
231 /* Walk up the subtree and check that each parent is less than the node
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 * this is required, because `max` node is not guaranteed to be the
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
233 * actual maximum in tree
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
234 */
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
235 while (child->parent != NULL && less_than(child, child->parent))
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 heap_node_swap(heap, child->parent, child);
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
237 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
238
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
239 HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
240 heap_remove(heap, heap->min, less_than);
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 }
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
242
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
243 #undef HEAP_EXPORT
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
244
2cf249471370 convert mercurial for git
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
245 #endif /* UV_SRC_HEAP_H_ */