legacy-libs/grpc/deps/grpc/src/core/lib/avl/avl.cc

   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; }