test/core/avl/avl_test.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 "src/core/lib/avl/avl.h"
  20
  21 #include <stdio.h>
  22 #include <string.h>
  23
  24 #include <grpc/support/alloc.h>
  25 #include <grpc/support/log.h>
  26
  27 #include "src/core/lib/gpr/useful.h"
  28 #include "test/core/util/test_config.h"
  29
  30 static int* box(int x) {
  31   int* b = static_cast<int*>(gpr_malloc(sizeof(*b)));
  32   *b = x;
  33   return b;
  34 }
  35
  36 static long int_compare(void* int1, void* int2, void* unused) {
  37   return (*static_cast<int*>(int1)) - (*static_cast<int*>(int2));
  38 }
  39 static void* int_copy(void* p, void* unused) {
  40   return box(*static_cast<int*>(p));
  41 }
  42
  43 static void destroy(void* p, void* unused) { gpr_free(p); }
  44
  45 static const grpc_avl_vtable int_int_vtable = {destroy, int_copy, int_compare,
  46                                                destroy, int_copy};
  47
  48 static void check_get(grpc_avl avl, int key, int value) {
  49   int* k = box(key);
  50   GPR_ASSERT(*(int*)grpc_avl_get(avl, k, nullptr) == value);
  51   gpr_free(k);
  52 }
  53
  54 static void check_negget(grpc_avl avl, int key) {
  55   int* k = box(key);
  56   GPR_ASSERT(grpc_avl_get(avl, k, nullptr) == nullptr);
  57   gpr_free(k);
  58 }
  59
  60 static grpc_avl remove_int(grpc_avl avl, int key) {
  61   int* k = box(key);
  62   avl = grpc_avl_remove(avl, k, nullptr);
  63   gpr_free(k);
  64   return avl;
  65 }
  66
  67 static void test_get(void) {
  68   grpc_avl avl;
  69   gpr_log(GPR_DEBUG, "test_get");
  70   avl = grpc_avl_create(&int_int_vtable);
  71   avl = grpc_avl_add(avl, box(1), box(11), nullptr);
  72   avl = grpc_avl_add(avl, box(2), box(22), nullptr);
  73   avl = grpc_avl_add(avl, box(3), box(33), nullptr);
  74   check_get(avl, 1, 11);
  75   check_get(avl, 2, 22);
  76   check_get(avl, 3, 33);
  77   check_negget(avl, 4);
  78   grpc_avl_unref(avl, nullptr);
  79 }
  80
  81 static void test_ll(void) {
  82   grpc_avl avl;
  83   gpr_log(GPR_DEBUG, "test_ll");
  84   avl = grpc_avl_create(&int_int_vtable);
  85   avl = grpc_avl_add(avl, box(5), box(1), nullptr);
  86   avl = grpc_avl_add(avl, box(4), box(2), nullptr);
  87   avl = grpc_avl_add(avl, box(3), box(3), nullptr);
  88   GPR_ASSERT(*(int*)avl.root->key == 4);
  89   GPR_ASSERT(*(int*)avl.root->left->key == 3);
  90   GPR_ASSERT(*(int*)avl.root->right->key == 5);
  91   grpc_avl_unref(avl, nullptr);
  92 }
  93
  94 static void test_lr(void) {
  95   grpc_avl avl;
  96   gpr_log(GPR_DEBUG, "test_lr");
  97   avl = grpc_avl_create(&int_int_vtable);
  98   avl = grpc_avl_add(avl, box(5), box(1), nullptr);
  99   avl = grpc_avl_add(avl, box(3), box(2), nullptr);
 100   avl = grpc_avl_add(avl, box(4), box(3), nullptr);
 101   GPR_ASSERT(*(int*)avl.root->key == 4);
 102   GPR_ASSERT(*(int*)avl.root->left->key == 3);
 103   GPR_ASSERT(*(int*)avl.root->right->key == 5);
 104   grpc_avl_unref(avl, nullptr);
 105 }
 106
 107 static void test_rr(void) {
 108   grpc_avl avl;
 109   gpr_log(GPR_DEBUG, "test_rr");
 110   avl = grpc_avl_create(&int_int_vtable);
 111   avl = grpc_avl_add(avl, box(3), box(1), nullptr);
 112   avl = grpc_avl_add(avl, box(4), box(2), nullptr);
 113   avl = grpc_avl_add(avl, box(5), box(3), nullptr);
 114   GPR_ASSERT(*(int*)avl.root->key == 4);
 115   GPR_ASSERT(*(int*)avl.root->left->key == 3);
 116   GPR_ASSERT(*(int*)avl.root->right->key == 5);
 117   grpc_avl_unref(avl, nullptr);
 118 }
 119
 120 static void test_rl(void) {
 121   grpc_avl avl;
 122   gpr_log(GPR_DEBUG, "test_rl");
 123   avl = grpc_avl_create(&int_int_vtable);
 124   avl = grpc_avl_add(avl, box(3), box(1), nullptr);
 125   avl = grpc_avl_add(avl, box(5), box(2), nullptr);
 126   avl = grpc_avl_add(avl, box(4), box(3), nullptr);
 127   GPR_ASSERT(*(int*)avl.root->key == 4);
 128   GPR_ASSERT(*(int*)avl.root->left->key == 3);
 129   GPR_ASSERT(*(int*)avl.root->right->key == 5);
 130   grpc_avl_unref(avl, nullptr);
 131 }
 132
 133 static void test_unbalanced(void) {
 134   grpc_avl avl;
 135   gpr_log(GPR_DEBUG, "test_unbalanced");
 136   avl = grpc_avl_create(&int_int_vtable);
 137   avl = grpc_avl_add(avl, box(5), box(1), nullptr);
 138   avl = grpc_avl_add(avl, box(4), box(2), nullptr);
 139   avl = grpc_avl_add(avl, box(3), box(3), nullptr);
 140   avl = grpc_avl_add(avl, box(2), box(4), nullptr);
 141   avl = grpc_avl_add(avl, box(1), box(5), nullptr);
 142   GPR_ASSERT(*(int*)avl.root->key == 4);
 143   GPR_ASSERT(*(int*)avl.root->left->key == 2);
 144   GPR_ASSERT(*(int*)avl.root->left->left->key == 1);
 145   GPR_ASSERT(*(int*)avl.root->left->right->key == 3);
 146   GPR_ASSERT(*(int*)avl.root->right->key == 5);
 147   grpc_avl_unref(avl, nullptr);
 148 }
 149
 150 static void test_replace(void) {
 151   grpc_avl avl;
 152   gpr_log(GPR_DEBUG, "test_replace");
 153   avl = grpc_avl_create(&int_int_vtable);
 154   avl = grpc_avl_add(avl, box(1), box(1), nullptr);
 155   avl = grpc_avl_add(avl, box(1), box(2), nullptr);
 156   check_get(avl, 1, 2);
 157   check_negget(avl, 2);
 158   grpc_avl_unref(avl, nullptr);
 159 }
 160
 161 static void test_remove(void) {
 162   grpc_avl avl;
 163   grpc_avl avl3, avl4, avl5, avln;
 164   gpr_log(GPR_DEBUG, "test_remove");
 165   avl = grpc_avl_create(&int_int_vtable);
 166   avl = grpc_avl_add(avl, box(3), box(1), nullptr);
 167   avl = grpc_avl_add(avl, box(4), box(2), nullptr);
 168   avl = grpc_avl_add(avl, box(5), box(3), nullptr);
 169
 170   avl3 = remove_int(grpc_avl_ref(avl, nullptr), 3);
 171   avl4 = remove_int(grpc_avl_ref(avl, nullptr), 4);
 172   avl5 = remove_int(grpc_avl_ref(avl, nullptr), 5);
 173   avln = remove_int(grpc_avl_ref(avl, nullptr), 1);
 174
 175   grpc_avl_unref(avl, nullptr);
 176
 177   check_negget(avl3, 3);
 178   check_get(avl3, 4, 2);
 179   check_get(avl3, 5, 3);
 180   grpc_avl_unref(avl3, nullptr);
 181
 182   check_get(avl4, 3, 1);
 183   check_negget(avl4, 4);
 184   check_get(avl4, 5, 3);
 185   grpc_avl_unref(avl4, nullptr);
 186
 187   check_get(avl5, 3, 1);
 188   check_get(avl5, 4, 2);
 189   check_negget(avl5, 5);
 190   grpc_avl_unref(avl5, nullptr);
 191
 192   check_get(avln, 3, 1);
 193   check_get(avln, 4, 2);
 194   check_get(avln, 5, 3);
 195   grpc_avl_unref(avln, nullptr);
 196 }
 197
 198 static void test_badcase1(void) {
 199   grpc_avl avl;
 200
 201   gpr_log(GPR_DEBUG, "test_badcase1");
 202
 203   avl = grpc_avl_create(&int_int_vtable);
 204   avl = grpc_avl_add(avl, box(88), box(1), nullptr);
 205   avl = remove_int(avl, 643);
 206   avl = remove_int(avl, 983);
 207   avl = grpc_avl_add(avl, box(985), box(4), nullptr);
 208   avl = grpc_avl_add(avl, box(640), box(5), nullptr);
 209   avl = grpc_avl_add(avl, box(41), box(6), nullptr);
 210   avl = grpc_avl_add(avl, box(112), box(7), nullptr);
 211   avl = grpc_avl_add(avl, box(342), box(8), nullptr);
 212   avl = remove_int(avl, 1013);
 213   avl = grpc_avl_add(avl, box(434), box(10), nullptr);
 214   avl = grpc_avl_add(avl, box(520), box(11), nullptr);
 215   avl = grpc_avl_add(avl, box(231), box(12), nullptr);
 216   avl = grpc_avl_add(avl, box(852), box(13), nullptr);
 217   avl = remove_int(avl, 461);
 218   avl = grpc_avl_add(avl, box(108), box(15), nullptr);
 219   avl = grpc_avl_add(avl, box(806), box(16), nullptr);
 220   avl = grpc_avl_add(avl, box(827), box(17), nullptr);
 221   avl = remove_int(avl, 796);
 222   avl = grpc_avl_add(avl, box(340), box(19), nullptr);
 223   avl = grpc_avl_add(avl, box(498), box(20), nullptr);
 224   avl = grpc_avl_add(avl, box(203), box(21), nullptr);
 225   avl = grpc_avl_add(avl, box(751), box(22), nullptr);
 226   avl = grpc_avl_add(avl, box(150), box(23), nullptr);
 227   avl = remove_int(avl, 237);
 228   avl = grpc_avl_add(avl, box(830), box(25), nullptr);
 229   avl = remove_int(avl, 1007);
 230   avl = remove_int(avl, 394);
 231   avl = grpc_avl_add(avl, box(65), box(28), nullptr);
 232   avl = remove_int(avl, 904);
 233   avl = remove_int(avl, 123);
 234   avl = grpc_avl_add(avl, box(238), box(31), nullptr);
 235   avl = grpc_avl_add(avl, box(184), box(32), nullptr);
 236   avl = remove_int(avl, 331);
 237   avl = grpc_avl_add(avl, box(827), box(34), nullptr);
 238
 239   check_get(avl, 830, 25);
 240
 241   grpc_avl_unref(avl, nullptr);
 242 }
 243
 244 static void test_stress(int amount_of_stress) {
 245   int added[1024];
 246   int i, j;
 247   int deletions = 0;
 248   grpc_avl avl;
 249
 250   unsigned seed = static_cast<unsigned>(time(nullptr));
 251
 252   gpr_log(GPR_DEBUG, "test_stress amount=%d seed=%u", amount_of_stress, seed);
 253
 254   srand(static_cast<unsigned>(time(nullptr)));
 255   avl = grpc_avl_create(&int_int_vtable);
 256
 257   memset(added, 0, sizeof(added));
 258
 259   for (i = 1; deletions < amount_of_stress; i++) {
 260     int idx = rand() % static_cast<int> GPR_ARRAY_SIZE(added);
 261     GPR_ASSERT(i);
 262     if (rand() < RAND_MAX / 2) {
 263       added[idx] = i;
 264       printf("avl = grpc_avl_add(avl, box(%d), box(%d), NULL); /* d=%d */\n",
 265              idx, i, deletions);
 266       avl = grpc_avl_add(avl, box(idx), box(i), nullptr);
 267     } else {
 268       deletions += (added[idx] != 0);
 269       added[idx] = 0;
 270       printf("avl = remove_int(avl, %d); /* d=%d */\n", idx, deletions);
 271       avl = remove_int(avl, idx);
 272     }
 273     for (j = 0; j < static_cast<int> GPR_ARRAY_SIZE(added); j++) {
 274       if (added[j] != 0) {
 275         check_get(avl, j, added[j]);
 276       } else {
 277         check_negget(avl, j);
 278       }
 279     }
 280   }
 281
 282   grpc_avl_unref(avl, nullptr);
 283 }
 284
 285 int main(int argc, char* argv[]) {
 286   grpc::testing::TestEnvironment env(argc, argv);
 287
 288   test_get();
 289   test_ll();
 290   test_lr();
 291   test_rr();
 292   test_rl();
 293   test_unbalanced();
 294   test_replace();
 295   test_remove();
 296   test_badcase1();
 297   test_stress(10);
 298
 299   return 0;
 300 }