git.ozlabs.org Git - ccan/blob - ccan/btree/test/run-random-access.c

   1 /* Include the main header first, to test it works */
   2 #include <ccan/btree/btree.h>
   3 /* Include the C files directly. */
   4 #include <ccan/btree/btree.c>
   5 #include <ccan/tap/tap.h>
   6
   7 #include <stdint.h>
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11
  12 static uint32_t rand32_state = 0;
  13
  14 /*
  15  * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
  16  * Uses the BCPL linear congruential generator method.
  17  */
  18 static uint32_t rand32(void)
  19 {
  20         rand32_state *= (uint32_t)0x7FF8A3ED;
  21         rand32_state += (uint32_t)0x2AA01D31;
  22         return rand32_state;
  23 }
  24
  25 /*
  26  * Whether or not to add/remove multiple equal keys to the tree.
  27  *
  28  * Tests are run with multi set to 0 and 1.
  29  */
  30 static int multi = 0;
  31
  32 static struct {
  33         struct {
  34                 size_t success;
  35                 size_t failure;
  36         } insert, remove, find, traverse;
  37 } stats;
  38
  39 static int check_stats(void) {
  40         return
  41                 stats.insert.failure == 0 &&
  42                 stats.remove.failure == 0 &&
  43                 stats.find.failure == 0 &&
  44                 stats.traverse.failure == 0;
  45 }
  46
  47 static int print_stats(void) {
  48         printf("Insert:  %zu succeeded, %zu failed\n",
  49                 stats.insert.success, stats.insert.failure);
  50
  51         printf("Remove:  %zu succeeded, %zu failed\n",
  52                 stats.remove.success, stats.remove.failure);
  53
  54         printf("Find:  %zu succeeded, %zu failed\n",
  55                 stats.find.success, stats.find.failure);
  56
  57         printf("Traverse:  %zu succeeded, %zu failed\n",
  58                 stats.traverse.success, stats.traverse.failure);
  59
  60         return check_stats();
  61 }
  62
  63 static void clear_stats(void)
  64 {
  65         memset(&stats, 0, sizeof(stats));
  66 }
  67
  68 static int test_node_consistency(struct btree_node *node, struct btree_node *parent, size_t *count)
  69 {
  70         unsigned int i, j, e = node->count;
  71
  72         /* Verify parent, depth, and k */
  73         if (node->parent != parent)
  74                 return 0;
  75         if (parent) {
  76                 if (node->depth != parent->depth - 1)
  77                         return 0;
  78                 if (node != parent->branch[node->k])
  79                         return 0;
  80         }
  81
  82         /* Nodes must not be empty (unless the entire tree is empty). */
  83         if (e == 0)
  84                 return 0;
  85
  86         if (node->depth) {
  87                 /* Make sure child branches aren't duplicated or NULL. */
  88                 for (i=0; i<=e; i++) {
  89                         if (node->branch[i] == NULL)
  90                                 return 0;
  91                         for (j=i+1; j<=e; j++)
  92                                 if (node->branch[i] == node->branch[j])
  93                                         return 0;
  94                 }
  95
  96                 /* Recursively check children. */
  97                 for (i=0; i<=e; i++) {
  98                         if (!test_node_consistency(node->branch[i], node, count))
  99                                 return 0;
 100                 }
 101         }
 102
 103         *count += node->count;
 104         return 1;
 105 }
 106
 107 static int test_consistency(const struct btree *btree)
 108 {
 109         size_t count = 0;
 110         if (!btree->root)
 111                 return 0;
 112         if (btree->root->count == 0) {
 113                 if (btree->count != 0)
 114                         return 0;
 115                 return 1;
 116         }
 117         if (btree->count == 0)
 118                 return 0;
 119         if (!test_node_consistency(btree->root, NULL, &count))
 120                 return 0;
 121         if (btree->count != count)
 122                 return 0;
 123         return 1;
 124 }
 125
 126 static int test_traverse(struct btree *btree, size_t key[], size_t count)
 127 {
 128         btree_iterator iter;
 129         size_t i, j;
 130
 131         if (!test_consistency(btree))
 132                 return 0;
 133
 134         /* Forward */
 135         i = 0;
 136         btree_begin(btree, iter);
 137         for (;;) {
 138                 while (i < count && key[i] == 0)
 139                         i++;
 140                 if (i >= count) {
 141                         if (btree_next(iter))
 142                                 return 0;
 143                         break;
 144                 }
 145                 for (j = 0; j < key[i] && btree_next(iter); j++) {
 146                         if (iter->item != &key[i])
 147                                 return 0;
 148                 }
 149                 if (j != key[i])
 150                         return 0;
 151                 i++;
 152         }
 153
 154         /* Backward */
 155         i = count;
 156         btree_end(btree, iter);
 157         for (;;) {
 158                 while (i > 0 && key[i-1] == 0)
 159                         i--;
 160                 if (i <= 0) {
 161                         if (btree_prev(iter))
 162                                 return 0;
 163                         break;
 164                 }
 165                 for (j = 0; j < key[i-1] && btree_prev(iter); j++) {
 166                         if (iter->item != &key[i-1])
 167                                 return 0;
 168                 }
 169                 if (j != key[i-1])
 170                         return 0;
 171                 i--;
 172         }
 173
 174         return 1;
 175 }
 176
 177 /*
 178  * Finds and counts items matching &key[k], then makes sure the count
 179  * equals key[k].  Also verifies that btree_find_... work as advertised.
 180  */
 181 static int find(struct btree *btree, size_t key[], size_t k)
 182 {
 183         btree_iterator iter, tmp;
 184         size_t count;
 185         int found;
 186
 187         memset(iter, 0, sizeof(iter));
 188         memset(tmp, 0, sizeof(tmp));
 189
 190         found = btree_find_first(btree, &key[k], iter);
 191         if (iter->btree != btree)
 192                 return 0;
 193         if (found != !!key[k])
 194                 return 0;
 195         if (key[k] && iter->item != &key[k])
 196                 return 0;
 197
 198         /* Make sure btree_find works exactly the same as btree_find_first. */
 199         if (btree_find(btree, &key[k], tmp) != found)
 200                 return 0;
 201         if (memcmp(iter, tmp, sizeof(*iter)))
 202                 return 0;
 203
 204         /* Make sure previous item doesn't match. */
 205         *tmp = *iter;
 206         if (btree_prev(tmp)) {
 207                 if (tmp->item == &key[k])
 208                         return 0;
 209         }
 210
 211         /* Count going forward. */
 212         for (count=0; btree_deref(iter) && iter->item == &key[k]; count++, btree_next(iter))
 213                 {}
 214         if (count != key[k])
 215                 return 0;
 216
 217         /* Make sure next item doesn't match. */
 218         *tmp = *iter;
 219         if (btree_deref(tmp)) {
 220                 if (tmp->item == &key[k])
 221                         return 0;
 222         }
 223
 224         /* Make sure iter is now equal to the end of matching items. */
 225         btree_find_last(btree, &key[k], tmp);
 226         if (tmp->btree != btree)
 227                 return 0;
 228         if (btree_cmp_iters(iter, tmp))
 229                 return 0;
 230
 231         /* Count going backward. */
 232         for (count=0; btree_prev(iter); count++) {
 233                 if (iter->item != &key[k]) {
 234                         btree_next(iter);
 235                         break;
 236                 }
 237         }
 238         if (count != key[k])
 239                 return 0;
 240
 241         /* Make sure iter is now equal to the beginning of matching items. */
 242         btree_find_first(btree, &key[k], tmp);
 243         if (tmp->btree != btree)
 244                 return 0;
 245         if (btree_cmp_iters(iter, tmp))
 246                 return 0;
 247
 248         return 1;
 249 }
 250
 251 static int test_find(struct btree *btree, size_t key[], size_t count)
 252 {
 253         size_t k = rand32() % count;
 254         return find(btree, key, k);
 255 }
 256
 257 static int test_remove(struct btree *btree, size_t key[], size_t count)
 258 {
 259         size_t prev_count = btree->count;
 260         size_t k = rand32() % count;
 261         btree_iterator iter;
 262
 263         if (!find(btree, key, k))
 264                 return 0;
 265
 266         btree_find(btree, &key[k], iter);
 267
 268         //remove (if present), and make sure removal status is correct
 269         if (key[k]) {
 270                 if (btree_remove_at(iter) != 1)
 271                         return 0;
 272                 if (btree->count != prev_count - 1)
 273                         return 0;
 274                 key[k]--;
 275
 276                 if (!find(btree, key, k))
 277                         return 0;
 278         }
 279
 280         return 1;
 281 }
 282
 283 static int test_insert(struct btree *btree, size_t key[], size_t count)
 284 {
 285         size_t k = rand32() % count;
 286         btree_iterator iter;
 287         size_t prev_count = btree->count;
 288         int found;
 289
 290         if (!find(btree, key, k))
 291                 return 0;
 292
 293         /* Make sure key's presence is consistent with our array. */
 294         found = btree_find_first(btree, &key[k], iter);
 295         if (key[k]) {
 296                 if (!found || iter->item != &key[k])
 297                         return 0;
 298                 if (!btree_deref(iter))
 299                         return 0;
 300                 if (iter->k >= iter->node->count || iter->node->item[iter->k] != &key[k])
 301                         return 0;
 302         } else {
 303                 if (found)
 304                         return 0;
 305         }
 306
 307         /* Insert if item hasn't been yet (or if we're in multi mode). */
 308         if (!key[k] || multi) {
 309                 btree_insert_at(iter, &key[k]);
 310                 key[k]++;
 311                 if (btree->count != prev_count + 1)
 312                         return 0;
 313         }
 314
 315         /* Check result iterator's ->item field. */
 316         if (iter->item != &key[k])
 317                 return 0;
 318
 319         if (!find(btree, key, k))
 320                 return 0;
 321
 322         /* Make sure key is present and correct now. */
 323         found = btree_find_first(btree, &key[k], iter);
 324         if (!found || iter->item != &key[k])
 325                 return 0;
 326
 327         return 1;
 328 }
 329
 330 static btree_search_implement(order_by_ptr, size_t*, , a == b, a < b)
 331
 332 static void stress(size_t count, size_t trials)
 333 {
 334         struct btree *btree = btree_new(order_by_ptr);
 335         size_t *key = calloc(count, sizeof(*key));
 336         size_t i;
 337
 338         clear_stats();
 339
 340         for (i=0; i<trials; i++) {
 341                 unsigned int n = rand32() % 65536;
 342                 unsigned int rib = btree->count * 43688 / count;
 343                         //remove/insert boundary
 344                 if (n >= 65534) {
 345                         if (test_traverse(btree, key, count))
 346                                 stats.traverse.success++;
 347                         else
 348                                 stats.traverse.failure++;
 349                 } else if (n >= 46388) {
 350                         if (test_find(btree, key, count))
 351                                 stats.find.success++;
 352                         else
 353                                 stats.find.failure++;
 354                 } else if (n < rib) {
 355                         if (test_remove(btree, key, count))
 356                                 stats.remove.success++;
 357                         else
 358                                 stats.remove.failure++;
 359                 } else {
 360                         if (test_insert(btree, key, count))
 361                                 stats.insert.success++;
 362                         else
 363                                 stats.insert.failure++;
 364                 }
 365         }
 366
 367         free(key);
 368         btree_delete(btree);
 369
 370         print_stats();
 371         ok1(check_stats());
 372 }
 373
 374 int main(void)
 375 {
 376         plan_tests(2);
 377
 378         multi = 0;
 379         printf("Running with multi = %d\n", multi);
 380         stress(100000, 500000);
 381
 382         multi = 1;
 383         printf("Running with multi = %d\n", multi);
 384         stress(100000, 500000);
 385
 386         return exit_status();
 387 }