Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include <grpc/support/avl.h>
35 :
36 : #include <assert.h>
37 : #include <stdlib.h>
38 :
39 : #include <grpc/support/alloc.h>
40 : #include <grpc/support/string_util.h>
41 : #include <grpc/support/useful.h>
42 :
43 12 : gpr_avl gpr_avl_create(const gpr_avl_vtable *vtable) {
44 : gpr_avl out;
45 12 : out.vtable = vtable;
46 12 : out.root = NULL;
47 12 : return out;
48 : }
49 :
50 74111 : static gpr_avl_node *ref_node(gpr_avl_node *node) {
51 74111 : if (node) {
52 62763 : gpr_ref(&node->refs);
53 : }
54 74111 : return node;
55 : }
56 :
57 154859 : static void unref_node(const gpr_avl_vtable *vtable, gpr_avl_node *node) {
58 154859 : if (node == NULL) {
59 174521 : return;
60 : }
61 135197 : if (gpr_unref(&node->refs)) {
62 72434 : vtable->destroy_key(node->key);
63 72434 : vtable->destroy_value(node->value);
64 72434 : unref_node(vtable, node->left);
65 72434 : unref_node(vtable, node->right);
66 72434 : gpr_free(node);
67 : }
68 : }
69 :
70 30350742 : static long node_height(gpr_avl_node *node) {
71 30350742 : return node == NULL ? 0 : node->height;
72 : }
73 :
74 : #ifndef NDEBUG
75 2583650528 : static long calculate_height(gpr_avl_node *node) {
76 2583650528 : return node == NULL ? 0 : 1 + GPR_MAX(calculate_height(node->left),
77 : calculate_height(node->right));
78 : }
79 :
80 30217709 : static gpr_avl_node *assert_invariants(gpr_avl_node *n) {
81 30217709 : if (n == NULL) return NULL;
82 14999198 : assert_invariants(n->left);
83 14999198 : assert_invariants(n->right);
84 14999198 : assert(calculate_height(n) == n->height);
85 14999198 : assert(labs(node_height(n->left) - node_height(n->right)) <= 1);
86 14999198 : return n;
87 : }
88 : #else
89 : static gpr_avl_node *assert_invariants(gpr_avl_node *n) { return n; }
90 : #endif
91 :
92 72434 : gpr_avl_node *new_node(void *key, void *value, gpr_avl_node *left,
93 : gpr_avl_node *right) {
94 72434 : gpr_avl_node *node = gpr_malloc(sizeof(*node));
95 72434 : gpr_ref_init(&node->refs, 1);
96 72434 : node->key = key;
97 72434 : node->value = value;
98 72434 : node->left = assert_invariants(left);
99 72434 : node->right = assert_invariants(right);
100 72434 : node->height = 1 + GPR_MAX(node_height(left), node_height(right));
101 72434 : return node;
102 : }
103 :
104 45902674 : static gpr_avl_node *get(const gpr_avl_vtable *vtable, gpr_avl_node *node,
105 : void *key) {
106 : long cmp;
107 :
108 45902674 : if (node == NULL) {
109 3087445 : return NULL;
110 : }
111 :
112 42815229 : cmp = vtable->compare_keys(node->key, key);
113 42815229 : if (cmp == 0) {
114 2080702 : return node;
115 40734527 : } else if (cmp > 0) {
116 20385262 : return get(vtable, node->left, key);
117 : } else {
118 20349265 : return get(vtable, node->right, key);
119 : }
120 : }
121 :
122 5168147 : void *gpr_avl_get(gpr_avl avl, void *key) {
123 5168147 : gpr_avl_node *node = get(avl.vtable, avl.root, key);
124 5168147 : return node ? node->value : NULL;
125 : }
126 :
127 399 : static gpr_avl_node *rotate_left(const gpr_avl_vtable *vtable, void *key,
128 : void *value, gpr_avl_node *left,
129 : gpr_avl_node *right) {
130 399 : gpr_avl_node *n =
131 798 : new_node(vtable->copy_key(right->key), vtable->copy_value(right->value),
132 399 : new_node(key, value, left, ref_node(right->left)),
133 399 : ref_node(right->right));
134 399 : unref_node(vtable, right);
135 399 : return n;
136 : }
137 :
138 452 : static gpr_avl_node *rotate_right(const gpr_avl_vtable *vtable, void *key,
139 : void *value, gpr_avl_node *left,
140 : gpr_avl_node *right) {
141 1808 : gpr_avl_node *n = new_node(
142 904 : vtable->copy_key(left->key), vtable->copy_value(left->value),
143 904 : ref_node(left->left), new_node(key, value, ref_node(left->right), right));
144 452 : unref_node(vtable, left);
145 452 : return n;
146 : }
147 :
148 324 : static gpr_avl_node *rotate_left_right(const gpr_avl_vtable *vtable, void *key,
149 : void *value, gpr_avl_node *left,
150 : gpr_avl_node *right) {
151 : /* rotate_right(..., rotate_left(left), right) */
152 2268 : gpr_avl_node *n = new_node(
153 324 : vtable->copy_key(left->right->key),
154 324 : vtable->copy_value(left->right->value),
155 648 : new_node(vtable->copy_key(left->key), vtable->copy_value(left->value),
156 648 : ref_node(left->left), ref_node(left->right->left)),
157 324 : new_node(key, value, ref_node(left->right->right), right));
158 324 : unref_node(vtable, left);
159 324 : return n;
160 : }
161 :
162 351 : static gpr_avl_node *rotate_right_left(const gpr_avl_vtable *vtable, void *key,
163 : void *value, gpr_avl_node *left,
164 : gpr_avl_node *right) {
165 : /* rotate_left(..., left, rotate_right(right)) */
166 2457 : gpr_avl_node *n = new_node(
167 351 : vtable->copy_key(right->left->key),
168 351 : vtable->copy_value(right->left->value),
169 351 : new_node(key, value, left, ref_node(right->left->left)),
170 702 : new_node(vtable->copy_key(right->key), vtable->copy_key(right->value),
171 702 : ref_node(right->left->right), ref_node(right->right)));
172 351 : unref_node(vtable, right);
173 351 : return n;
174 : }
175 :
176 65996 : static gpr_avl_node *rebalance(const gpr_avl_vtable *vtable, void *key,
177 : void *value, gpr_avl_node *left,
178 : gpr_avl_node *right) {
179 65996 : switch (node_height(left) - node_height(right)) {
180 : case 2:
181 776 : if (node_height(left->left) - node_height(left->right) == -1) {
182 324 : return assert_invariants(
183 : rotate_left_right(vtable, key, value, left, right));
184 : } else {
185 452 : return assert_invariants(rotate_right(vtable, key, value, left, right));
186 : }
187 : case -2:
188 750 : if (node_height(right->left) - node_height(right->right) == 1) {
189 351 : return assert_invariants(
190 : rotate_right_left(vtable, key, value, left, right));
191 : } else {
192 399 : return assert_invariants(rotate_left(vtable, key, value, left, right));
193 : }
194 : default:
195 64470 : return assert_invariants(new_node(key, value, left, right));
196 : }
197 : }
198 :
199 36529 : static gpr_avl_node *add(const gpr_avl_vtable *vtable, gpr_avl_node *node,
200 : void *key, void *value) {
201 : long cmp;
202 36529 : if (node == NULL) {
203 2773 : return new_node(key, value, NULL, NULL);
204 : }
205 33756 : cmp = vtable->compare_keys(node->key, key);
206 33756 : if (cmp == 0) {
207 1464 : return new_node(key, value, ref_node(node->left), ref_node(node->right));
208 32292 : } else if (cmp > 0) {
209 64852 : return rebalance(
210 32426 : vtable, vtable->copy_key(node->key), vtable->copy_value(node->value),
211 32426 : add(vtable, node->left, key, value), ref_node(node->right));
212 : } else {
213 48237 : return rebalance(vtable, vtable->copy_key(node->key),
214 32158 : vtable->copy_value(node->value), ref_node(node->left),
215 16079 : add(vtable, node->right, key, value));
216 : }
217 : }
218 :
219 4237 : gpr_avl gpr_avl_add(gpr_avl avl, void *key, void *value) {
220 4237 : gpr_avl_node *old_root = avl.root;
221 4237 : avl.root = add(avl.vtable, avl.root, key, value);
222 4237 : assert_invariants(avl.root);
223 4237 : unref_node(avl.vtable, old_root);
224 4237 : return avl;
225 : }
226 :
227 123 : static gpr_avl_node *in_order_head(gpr_avl_node *node) {
228 446 : while (node->left != NULL) {
229 200 : node = node->left;
230 : }
231 123 : return node;
232 : }
233 :
234 521 : static gpr_avl_node *in_order_tail(gpr_avl_node *node) {
235 1651 : while (node->right != NULL) {
236 609 : node = node->right;
237 : }
238 521 : return node;
239 : }
240 :
241 37916 : static gpr_avl_node *remove(const gpr_avl_vtable *vtable, gpr_avl_node *node,
242 : void *key) {
243 : long cmp;
244 37916 : if (node == NULL) {
245 2756 : return NULL;
246 : }
247 35160 : cmp = vtable->compare_keys(node->key, key);
248 35160 : if (cmp == 0) {
249 2100 : if (node->left == NULL) {
250 1261 : return ref_node(node->right);
251 839 : } else if (node->right == NULL) {
252 195 : return ref_node(node->left);
253 644 : } else if (node->left->height < node->right->height) {
254 123 : gpr_avl_node *h = in_order_head(node->right);
255 492 : return rebalance(vtable, vtable->copy_key(h->key),
256 246 : vtable->copy_value(h->value), ref_node(node->left),
257 123 : remove(vtable, node->right, h->key));
258 : } else {
259 521 : gpr_avl_node *h = in_order_tail(node->left);
260 2084 : return rebalance(
261 1042 : vtable, vtable->copy_key(h->key), vtable->copy_value(h->value),
262 1042 : remove(vtable, node->left, h->key), ref_node(node->right));
263 : }
264 33060 : } else if (cmp > 0) {
265 49230 : return rebalance(vtable, vtable->copy_key(node->key),
266 16410 : vtable->copy_value(node->value),
267 32820 : remove(vtable, node->left, key), ref_node(node->right));
268 : } else {
269 49950 : return rebalance(vtable, vtable->copy_key(node->key),
270 33300 : vtable->copy_value(node->value), ref_node(node->left),
271 16650 : remove(vtable, node->right, key));
272 : }
273 : }
274 :
275 4212 : gpr_avl gpr_avl_remove(gpr_avl avl, void *key) {
276 4212 : gpr_avl_node *old_root = avl.root;
277 4212 : avl.root = remove(avl.vtable, avl.root, key);
278 4212 : assert_invariants(avl.root);
279 4212 : unref_node(avl.vtable, old_root);
280 4212 : return avl;
281 : }
282 :
283 4 : gpr_avl gpr_avl_ref(gpr_avl avl) {
284 4 : ref_node(avl.root);
285 4 : return avl;
286 : }
287 :
288 16 : void gpr_avl_unref(gpr_avl avl) { unref_node(avl.vtable, avl.root); }
|
