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 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 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 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 59 static long node_height(grpc_avl_node* node) { 60 return node == nullptr ? 0 : node->height; 61 } 62 63 #ifndef NDEBUG 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 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 79 static grpc_avl_node* assert_invariants(grpc_avl_node* n) { return n; } 80 #endif 81 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 297 grpc_avl grpc_avl_ref(grpc_avl avl, void* user_data) { 298 ref_node(avl.root); 299 return avl; 300 } 301 302 void grpc_avl_unref(grpc_avl avl, void* user_data) { 303 unref_node(avl.vtable, avl.root, user_data); 304 } 305 306 int grpc_avl_is_empty(grpc_avl avl) { return avl.root == nullptr; } 307
