• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  *
3  * Copyright 2015 gRPC authors.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  *     http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17  */
18 
19 #include <grpc/support/port_platform.h>
20 
21 #include "src/core/lib/avl/avl.h"
22 
23 #include <assert.h>
24 #include <stdlib.h>
25 
26 #include <grpc/support/alloc.h>
27 #include <grpc/support/string_util.h>
28 
29 #include "src/core/lib/gpr/useful.h"
30 
grpc_avl_create(const grpc_avl_vtable * vtable)31 grpc_avl grpc_avl_create(const grpc_avl_vtable* vtable) {
32   grpc_avl out;
33   out.vtable = vtable;
34   out.root = nullptr;
35   return out;
36 }
37 
ref_node(grpc_avl_node * node)38 static grpc_avl_node* ref_node(grpc_avl_node* node) {
39   if (node) {
40     gpr_ref(&node->refs);
41   }
42   return node;
43 }
44 
unref_node(const grpc_avl_vtable * vtable,grpc_avl_node * node,void * user_data)45 static void unref_node(const grpc_avl_vtable* vtable, grpc_avl_node* node,
46                        void* user_data) {
47   if (node == nullptr) {
48     return;
49   }
50   if (gpr_unref(&node->refs)) {
51     vtable->destroy_key(node->key, user_data);
52     vtable->destroy_value(node->value, user_data);
53     unref_node(vtable, node->left, user_data);
54     unref_node(vtable, node->right, user_data);
55     gpr_free(node);
56   }
57 }
58 
node_height(grpc_avl_node * node)59 static long node_height(grpc_avl_node* node) {
60   return node == nullptr ? 0 : node->height;
61 }
62 
63 #ifndef NDEBUG
calculate_height(grpc_avl_node * node)64 static long calculate_height(grpc_avl_node* node) {
65   return node == nullptr ? 0
66                          : 1 + GPR_MAX(calculate_height(node->left),
67                                        calculate_height(node->right));
68 }
69 
assert_invariants(grpc_avl_node * n)70 static grpc_avl_node* assert_invariants(grpc_avl_node* n) {
71   if (n == nullptr) return nullptr;
72   assert_invariants(n->left);
73   assert_invariants(n->right);
74   assert(calculate_height(n) == n->height);
75   assert(labs(node_height(n->left) - node_height(n->right)) <= 1);
76   return n;
77 }
78 #else
assert_invariants(grpc_avl_node * n)79 static grpc_avl_node* assert_invariants(grpc_avl_node* n) { return n; }
80 #endif
81 
new_node(void * key,void * value,grpc_avl_node * left,grpc_avl_node * right)82 grpc_avl_node* new_node(void* key, void* value, grpc_avl_node* left,
83                         grpc_avl_node* right) {
84   grpc_avl_node* node = static_cast<grpc_avl_node*>(gpr_malloc(sizeof(*node)));
85   gpr_ref_init(&node->refs, 1);
86   node->key = key;
87   node->value = value;
88   node->left = assert_invariants(left);
89   node->right = assert_invariants(right);
90   node->height = 1 + GPR_MAX(node_height(left), node_height(right));
91   return node;
92 }
93 
get(const grpc_avl_vtable * vtable,grpc_avl_node * node,void * key,void * user_data)94 static grpc_avl_node* get(const grpc_avl_vtable* vtable, grpc_avl_node* node,
95                           void* key, void* user_data) {
96   long cmp;
97 
98   if (node == nullptr) {
99     return nullptr;
100   }
101 
102   cmp = vtable->compare_keys(node->key, key, user_data);
103   if (cmp == 0) {
104     return node;
105   } else if (cmp > 0) {
106     return get(vtable, node->left, key, user_data);
107   } else {
108     return get(vtable, node->right, key, user_data);
109   }
110 }
111 
grpc_avl_get(grpc_avl avl,void * key,void * user_data)112 void* grpc_avl_get(grpc_avl avl, void* key, void* user_data) {
113   grpc_avl_node* node = get(avl.vtable, avl.root, key, user_data);
114   return node ? node->value : nullptr;
115 }
116 
grpc_avl_maybe_get(grpc_avl avl,void * key,void ** value,void * user_data)117 int grpc_avl_maybe_get(grpc_avl avl, void* key, void** value, void* user_data) {
118   grpc_avl_node* node = get(avl.vtable, avl.root, key, user_data);
119   if (node != nullptr) {
120     *value = node->value;
121     return 1;
122   }
123   return 0;
124 }
125 
rotate_left(const grpc_avl_vtable * vtable,void * key,void * value,grpc_avl_node * left,grpc_avl_node * right,void * user_data)126 static grpc_avl_node* rotate_left(const grpc_avl_vtable* vtable, void* key,
127                                   void* value, grpc_avl_node* left,
128                                   grpc_avl_node* right, void* user_data) {
129   grpc_avl_node* n = new_node(vtable->copy_key(right->key, user_data),
130                               vtable->copy_value(right->value, user_data),
131                               new_node(key, value, left, ref_node(right->left)),
132                               ref_node(right->right));
133   unref_node(vtable, right, user_data);
134   return n;
135 }
136 
rotate_right(const grpc_avl_vtable * vtable,void * key,void * value,grpc_avl_node * left,grpc_avl_node * right,void * user_data)137 static grpc_avl_node* rotate_right(const grpc_avl_vtable* vtable, void* key,
138                                    void* value, grpc_avl_node* left,
139                                    grpc_avl_node* right, void* user_data) {
140   grpc_avl_node* n =
141       new_node(vtable->copy_key(left->key, user_data),
142                vtable->copy_value(left->value, user_data), ref_node(left->left),
143                new_node(key, value, ref_node(left->right), right));
144   unref_node(vtable, left, user_data);
145   return n;
146 }
147 
rotate_left_right(const grpc_avl_vtable * vtable,void * key,void * value,grpc_avl_node * left,grpc_avl_node * right,void * user_data)148 static grpc_avl_node* rotate_left_right(const grpc_avl_vtable* vtable,
149                                         void* key, void* value,
150                                         grpc_avl_node* left,
151                                         grpc_avl_node* right, void* user_data) {
152   /* rotate_right(..., rotate_left(left), right) */
153   grpc_avl_node* n =
154       new_node(vtable->copy_key(left->right->key, user_data),
155                vtable->copy_value(left->right->value, user_data),
156                new_node(vtable->copy_key(left->key, user_data),
157                         vtable->copy_value(left->value, user_data),
158                         ref_node(left->left), ref_node(left->right->left)),
159                new_node(key, value, ref_node(left->right->right), right));
160   unref_node(vtable, left, user_data);
161   return n;
162 }
163 
rotate_right_left(const grpc_avl_vtable * vtable,void * key,void * value,grpc_avl_node * left,grpc_avl_node * right,void * user_data)164 static grpc_avl_node* rotate_right_left(const grpc_avl_vtable* vtable,
165                                         void* key, void* value,
166                                         grpc_avl_node* left,
167                                         grpc_avl_node* right, void* user_data) {
168   /* rotate_left(..., left, rotate_right(right)) */
169   grpc_avl_node* n =
170       new_node(vtable->copy_key(right->left->key, user_data),
171                vtable->copy_value(right->left->value, user_data),
172                new_node(key, value, left, ref_node(right->left->left)),
173                new_node(vtable->copy_key(right->key, user_data),
174                         vtable->copy_value(right->value, user_data),
175                         ref_node(right->left->right), ref_node(right->right)));
176   unref_node(vtable, right, user_data);
177   return n;
178 }
179 
rebalance(const grpc_avl_vtable * vtable,void * key,void * value,grpc_avl_node * left,grpc_avl_node * right,void * user_data)180 static grpc_avl_node* rebalance(const grpc_avl_vtable* vtable, void* key,
181                                 void* value, grpc_avl_node* left,
182                                 grpc_avl_node* right, void* user_data) {
183   switch (node_height(left) - node_height(right)) {
184     case 2:
185       if (node_height(left->left) - node_height(left->right) == -1) {
186         return assert_invariants(
187             rotate_left_right(vtable, key, value, left, right, user_data));
188       } else {
189         return assert_invariants(
190             rotate_right(vtable, key, value, left, right, user_data));
191       }
192     case -2:
193       if (node_height(right->left) - node_height(right->right) == 1) {
194         return assert_invariants(
195             rotate_right_left(vtable, key, value, left, right, user_data));
196       } else {
197         return assert_invariants(
198             rotate_left(vtable, key, value, left, right, user_data));
199       }
200     default:
201       return assert_invariants(new_node(key, value, left, right));
202   }
203 }
204 
add_key(const grpc_avl_vtable * vtable,grpc_avl_node * node,void * key,void * value,void * user_data)205 static grpc_avl_node* add_key(const grpc_avl_vtable* vtable,
206                               grpc_avl_node* node, void* key, void* value,
207                               void* user_data) {
208   long cmp;
209   if (node == nullptr) {
210     return new_node(key, value, nullptr, nullptr);
211   }
212   cmp = vtable->compare_keys(node->key, key, user_data);
213   if (cmp == 0) {
214     return new_node(key, value, ref_node(node->left), ref_node(node->right));
215   } else if (cmp > 0) {
216     return rebalance(vtable, vtable->copy_key(node->key, user_data),
217                      vtable->copy_value(node->value, user_data),
218                      add_key(vtable, node->left, key, value, user_data),
219                      ref_node(node->right), user_data);
220   } else {
221     return rebalance(
222         vtable, vtable->copy_key(node->key, user_data),
223         vtable->copy_value(node->value, user_data), ref_node(node->left),
224         add_key(vtable, node->right, key, value, user_data), user_data);
225   }
226 }
227 
grpc_avl_add(grpc_avl avl,void * key,void * value,void * user_data)228 grpc_avl grpc_avl_add(grpc_avl avl, void* key, void* value, void* user_data) {
229   grpc_avl_node* old_root = avl.root;
230   avl.root = add_key(avl.vtable, avl.root, key, value, user_data);
231   assert_invariants(avl.root);
232   unref_node(avl.vtable, old_root, user_data);
233   return avl;
234 }
235 
in_order_head(grpc_avl_node * node)236 static grpc_avl_node* in_order_head(grpc_avl_node* node) {
237   while (node->left != nullptr) {
238     node = node->left;
239   }
240   return node;
241 }
242 
in_order_tail(grpc_avl_node * node)243 static grpc_avl_node* in_order_tail(grpc_avl_node* node) {
244   while (node->right != nullptr) {
245     node = node->right;
246   }
247   return node;
248 }
249 
remove_key(const grpc_avl_vtable * vtable,grpc_avl_node * node,void * key,void * user_data)250 static grpc_avl_node* remove_key(const grpc_avl_vtable* vtable,
251                                  grpc_avl_node* node, void* key,
252                                  void* user_data) {
253   long cmp;
254   if (node == nullptr) {
255     return nullptr;
256   }
257   cmp = vtable->compare_keys(node->key, key, user_data);
258   if (cmp == 0) {
259     if (node->left == nullptr) {
260       return ref_node(node->right);
261     } else if (node->right == nullptr) {
262       return ref_node(node->left);
263     } else if (node->left->height < node->right->height) {
264       grpc_avl_node* h = in_order_head(node->right);
265       return rebalance(
266           vtable, vtable->copy_key(h->key, user_data),
267           vtable->copy_value(h->value, user_data), ref_node(node->left),
268           remove_key(vtable, node->right, h->key, user_data), user_data);
269     } else {
270       grpc_avl_node* h = in_order_tail(node->left);
271       return rebalance(vtable, vtable->copy_key(h->key, user_data),
272                        vtable->copy_value(h->value, user_data),
273                        remove_key(vtable, node->left, h->key, user_data),
274                        ref_node(node->right), user_data);
275     }
276   } else if (cmp > 0) {
277     return rebalance(vtable, vtable->copy_key(node->key, user_data),
278                      vtable->copy_value(node->value, user_data),
279                      remove_key(vtable, node->left, key, user_data),
280                      ref_node(node->right), user_data);
281   } else {
282     return rebalance(
283         vtable, vtable->copy_key(node->key, user_data),
284         vtable->copy_value(node->value, user_data), ref_node(node->left),
285         remove_key(vtable, node->right, key, user_data), user_data);
286   }
287 }
288 
grpc_avl_remove(grpc_avl avl,void * key,void * user_data)289 grpc_avl grpc_avl_remove(grpc_avl avl, void* key, void* user_data) {
290   grpc_avl_node* old_root = avl.root;
291   avl.root = remove_key(avl.vtable, avl.root, key, user_data);
292   assert_invariants(avl.root);
293   unref_node(avl.vtable, old_root, user_data);
294   return avl;
295 }
296 
grpc_avl_ref(grpc_avl avl,void * user_data)297 grpc_avl grpc_avl_ref(grpc_avl avl, void* user_data) {
298   ref_node(avl.root);
299   return avl;
300 }
301 
grpc_avl_unref(grpc_avl avl,void * user_data)302 void grpc_avl_unref(grpc_avl avl, void* user_data) {
303   unref_node(avl.vtable, avl.root, user_data);
304 }
305 
grpc_avl_is_empty(grpc_avl avl)306 int grpc_avl_is_empty(grpc_avl avl) { return avl.root == nullptr; }
307