tests/virhashtest.c

   1 #include <config.h>
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6 #include <time.h>
   7
   8 #include "internal.h"
   9 #include "virhash.h"
  10 #include "virhashdata.h"
  11 #include "testutils.h"
  12 #include "viralloc.h"
  13 #include "virlog.h"
  14 #include "virstring.h"
  15
  16 #define VIR_FROM_THIS VIR_FROM_NONE
  17
  18 VIR_LOG_INIT("tests.hashtest");
  19
  20 #define testError(...)                                          \
  21     do {                                                        \
  22         char *str;                                              \
  23         if (virAsprintfQuiet(&str, __VA_ARGS__) >= 0) {         \
  24             fprintf(stderr, "%s", str);                         \
  25             VIR_FREE(str);                                      \
  26         }                                                       \
  27         /* Pad to line up with test name ... in virTestRun */   \
  28         fprintf(stderr, "%74s", "... ");                        \
  29     } while (0)
  30
  31
  32 static virHashTablePtr
  33 testHashInit(int size)
  34 {
  35     virHashTablePtr hash;
  36     ssize_t i;
  37
  38     if (!(hash = virHashCreate(size, NULL)))
  39         return NULL;
  40
  41     /* entires are added in reverse order so that they will be linked in
  42      * collision list in the same order as in the uuids array
  43      */
  44     for (i = ARRAY_CARDINALITY(uuids) - 1; i >= 0; i--) {
  45         ssize_t oldsize = virHashTableSize(hash);
  46         if (virHashAddEntry(hash, uuids[i], (void *) uuids[i]) < 0) {
  47             virHashFree(hash);
  48             return NULL;
  49         }
  50
  51         if (virHashTableSize(hash) != oldsize && virTestGetDebug()) {
  52             VIR_WARN("hash grown from %zd to %zd",
  53                      (size_t)oldsize, (size_t)virHashTableSize(hash));
  54         }
  55     }
  56
  57     for (i = 0; i < ARRAY_CARDINALITY(uuids); i++) {
  58         if (!virHashLookup(hash, uuids[i])) {
  59             if (virTestGetVerbose()) {
  60                 VIR_WARN("\nentry \"%s\" could not be found\n",
  61                          uuids[i]);
  62             }
  63             virHashFree(hash);
  64             return NULL;
  65         }
  66     }
  67
  68     if (size && size != virHashTableSize(hash) && virTestGetDebug())
  69         fprintf(stderr, "\n");
  70
  71     return hash;
  72 }
  73
  74 static void
  75 testHashCheckForEachCount(void *payload ATTRIBUTE_UNUSED,
  76                           const void *name ATTRIBUTE_UNUSED,
  77                           void *data ATTRIBUTE_UNUSED)
  78 {
  79 }
  80
  81 static int
  82 testHashCheckCount(virHashTablePtr hash, size_t count)
  83 {
  84     ssize_t iter_count = 0;
  85
  86     if (virHashSize(hash) != count) {
  87         testError("\nhash contains %zu instead of %zu elements\n",
  88                   (size_t)virHashSize(hash), count);
  89         return -1;
  90     }
  91
  92     iter_count = virHashForEach(hash, testHashCheckForEachCount, NULL);
  93     if (count != iter_count) {
  94         testError("\nhash claims to have %zu elements but iteration finds %zu\n",
  95                   count, (size_t)iter_count);
  96         return -1;
  97     }
  98
  99     return 0;
 100 }
 101
 102
 103 struct testInfo {
 104     void *data;
 105     size_t count;
 106 };
 107
 108
 109 static int
 110 testHashGrow(const void *data)
 111 {
 112     const struct testInfo *info = data;
 113     virHashTablePtr hash;
 114     int ret = -1;
 115
 116     if (!(hash = testHashInit(info->count)))
 117         return -1;
 118
 119     if (testHashCheckCount(hash, ARRAY_CARDINALITY(uuids)) < 0)
 120         goto cleanup;
 121
 122     ret = 0;
 123
 124  cleanup:
 125     virHashFree(hash);
 126     return ret;
 127 }
 128
 129
 130 static int
 131 testHashUpdate(const void *data ATTRIBUTE_UNUSED)
 132 {
 133     int count = ARRAY_CARDINALITY(uuids) + ARRAY_CARDINALITY(uuids_new);
 134     virHashTablePtr hash;
 135     size_t i;
 136     int ret = -1;
 137
 138     if (!(hash = testHashInit(0)))
 139         return -1;
 140
 141     for (i = 0; i < ARRAY_CARDINALITY(uuids_subset); i++) {
 142         if (virHashUpdateEntry(hash, uuids_subset[i], (void *) 1) < 0) {
 143             if (virTestGetVerbose()) {
 144                 fprintf(stderr, "\nentry \"%s\" could not be updated\n",
 145                         uuids_subset[i]);
 146             }
 147             goto cleanup;
 148         }
 149     }
 150
 151     for (i = 0; i < ARRAY_CARDINALITY(uuids_new); i++) {
 152         if (virHashUpdateEntry(hash, uuids_new[i], (void *) 1) < 0) {
 153             if (virTestGetVerbose()) {
 154                 fprintf(stderr, "\nnew entry \"%s\" could not be updated\n",
 155                         uuids_new[i]);
 156             }
 157             goto cleanup;
 158         }
 159     }
 160
 161     if (testHashCheckCount(hash, count) < 0)
 162         goto cleanup;
 163
 164     ret = 0;
 165
 166  cleanup:
 167     virHashFree(hash);
 168     return ret;
 169 }
 170
 171
 172 static int
 173 testHashRemove(const void *data ATTRIBUTE_UNUSED)
 174 {
 175     int count = ARRAY_CARDINALITY(uuids) - ARRAY_CARDINALITY(uuids_subset);
 176     virHashTablePtr hash;
 177     size_t i;
 178     int ret = -1;
 179
 180     if (!(hash = testHashInit(0)))
 181         return -1;
 182
 183     for (i = 0; i < ARRAY_CARDINALITY(uuids_subset); i++) {
 184         if (virHashRemoveEntry(hash, uuids_subset[i]) < 0) {
 185             if (virTestGetVerbose()) {
 186                 fprintf(stderr, "\nentry \"%s\" could not be removed\n",
 187                         uuids_subset[i]);
 188             }
 189             goto cleanup;
 190         }
 191     }
 192
 193     if (testHashCheckCount(hash, count) < 0)
 194         goto cleanup;
 195
 196     ret = 0;
 197
 198  cleanup:
 199     virHashFree(hash);
 200     return ret;
 201 }
 202
 203
 204 const int testHashCountRemoveForEachSome =
 205     ARRAY_CARDINALITY(uuids) - ARRAY_CARDINALITY(uuids_subset);
 206
 207 static void
 208 testHashRemoveForEachSome(void *payload ATTRIBUTE_UNUSED,
 209                           const void *name,
 210                           void *data)
 211 {
 212     virHashTablePtr hash = data;
 213     size_t i;
 214
 215     for (i = 0; i < ARRAY_CARDINALITY(uuids_subset); i++) {
 216         if (STREQ(uuids_subset[i], name)) {
 217             if (virHashRemoveEntry(hash, name) < 0 && virTestGetVerbose()) {
 218                 fprintf(stderr, "\nentry \"%s\" could not be removed",
 219                         uuids_subset[i]);
 220             }
 221             break;
 222         }
 223     }
 224 }
 225
 226
 227 const int testHashCountRemoveForEachAll = 0;
 228
 229 static void
 230 testHashRemoveForEachAll(void *payload ATTRIBUTE_UNUSED,
 231                          const void *name,
 232                          void *data)
 233 {
 234     virHashTablePtr hash = data;
 235
 236     virHashRemoveEntry(hash, name);
 237 }
 238
 239
 240 const int testHashCountRemoveForEachForbidden = ARRAY_CARDINALITY(uuids);
 241
 242 static void
 243 testHashRemoveForEachForbidden(void *payload ATTRIBUTE_UNUSED,
 244                                const void *name,
 245                                void *data)
 246 {
 247     virHashTablePtr hash = data;
 248     size_t i;
 249
 250     for (i = 0; i < ARRAY_CARDINALITY(uuids_subset); i++) {
 251         if (STREQ(uuids_subset[i], name)) {
 252             int next = (i + 1) % ARRAY_CARDINALITY(uuids_subset);
 253
 254             if (virHashRemoveEntry(hash, uuids_subset[next]) == 0 &&
 255                 virTestGetVerbose()) {
 256                 fprintf(stderr,
 257                         "\nentry \"%s\" should not be allowed to be removed",
 258                         uuids_subset[next]);
 259             }
 260             break;
 261         }
 262     }
 263 }
 264
 265
 266 static int
 267 testHashRemoveForEach(const void *data)
 268 {
 269     const struct testInfo *info = data;
 270     virHashTablePtr hash;
 271     int count;
 272     int ret = -1;
 273
 274     if (!(hash = testHashInit(0)))
 275         return -1;
 276
 277     count = virHashForEach(hash, (virHashIterator) info->data, hash);
 278
 279     if (count != ARRAY_CARDINALITY(uuids)) {
 280         if (virTestGetVerbose()) {
 281             testError("\nvirHashForEach didn't go through all entries,"
 282                       " %d != %zu\n",
 283                       count, ARRAY_CARDINALITY(uuids));
 284         }
 285         goto cleanup;
 286     }
 287
 288     if (testHashCheckCount(hash, info->count) < 0)
 289         goto cleanup;
 290
 291     ret = 0;
 292
 293  cleanup:
 294     virHashFree(hash);
 295     return ret;
 296 }
 297
 298
 299 static int
 300 testHashSteal(const void *data ATTRIBUTE_UNUSED)
 301 {
 302     int count = ARRAY_CARDINALITY(uuids) - ARRAY_CARDINALITY(uuids_subset);
 303     virHashTablePtr hash;
 304     size_t i;
 305     int ret = -1;
 306
 307     if (!(hash = testHashInit(0)))
 308         return -1;
 309
 310     for (i = 0; i < ARRAY_CARDINALITY(uuids_subset); i++) {
 311         if (!virHashSteal(hash, uuids_subset[i])) {
 312             if (virTestGetVerbose()) {
 313                 fprintf(stderr, "\nentry \"%s\" could not be stolen\n",
 314                         uuids_subset[i]);
 315             }
 316             goto cleanup;
 317         }
 318     }
 319
 320     if (testHashCheckCount(hash, count) < 0)
 321         goto cleanup;
 322
 323     ret = 0;
 324
 325  cleanup:
 326     virHashFree(hash);
 327     return ret;
 328 }
 329
 330
 331 static void
 332 testHashIter(void *payload ATTRIBUTE_UNUSED,
 333              const void *name ATTRIBUTE_UNUSED,
 334              void *data ATTRIBUTE_UNUSED)
 335 {
 336     return;
 337 }
 338
 339 static void
 340 testHashForEachIter(void *payload ATTRIBUTE_UNUSED,
 341                     const void *name ATTRIBUTE_UNUSED,
 342                     void *data)
 343 {
 344     virHashTablePtr hash = data;
 345
 346     if (virHashAddEntry(hash, uuids_new[0], NULL) == 0 &&
 347         virTestGetVerbose()) {
 348         fprintf(stderr, "\nadding entries in ForEach should be forbidden");
 349     }
 350
 351     if (virHashUpdateEntry(hash, uuids_new[0], NULL) == 0 &&
 352         virTestGetVerbose()) {
 353         fprintf(stderr, "\nupdating entries in ForEach should be forbidden");
 354     }
 355
 356     if (virHashSteal(hash, uuids_new[0]) != NULL &&
 357         virTestGetVerbose()) {
 358         fprintf(stderr, "\nstealing entries in ForEach should be forbidden");
 359     }
 360
 361     if (virHashSteal(hash, uuids_new[0]) != NULL &&
 362         virTestGetVerbose()) {
 363         fprintf(stderr, "\nstealing entries in ForEach should be forbidden");
 364     }
 365
 366     if (virHashForEach(hash, testHashIter, NULL) >= 0 &&
 367         virTestGetVerbose()) {
 368         fprintf(stderr, "\niterating through hash in ForEach"
 369                 " should be forbidden");
 370     }
 371 }
 372
 373 static int
 374 testHashForEach(const void *data ATTRIBUTE_UNUSED)
 375 {
 376     virHashTablePtr hash;
 377     int count;
 378     int ret = -1;
 379
 380     if (!(hash = testHashInit(0)))
 381         return -1;
 382
 383     count = virHashForEach(hash, testHashForEachIter, hash);
 384
 385     if (count != ARRAY_CARDINALITY(uuids)) {
 386         if (virTestGetVerbose()) {
 387             testError("\nvirHashForEach didn't go through all entries,"
 388                       " %d != %zu\n",
 389                       count, ARRAY_CARDINALITY(uuids));
 390         }
 391         goto cleanup;
 392     }
 393
 394     ret = 0;
 395
 396  cleanup:
 397     virHashFree(hash);
 398     return ret;
 399 }
 400
 401
 402 static int
 403 testHashRemoveSetIter(const void *payload ATTRIBUTE_UNUSED,
 404                       const void *name,
 405                       const void *data)
 406 {
 407     int *count = (int *) data;
 408     bool rem = false;
 409     size_t i;
 410
 411     for (i = 0; i < ARRAY_CARDINALITY(uuids_subset); i++) {
 412         if (STREQ(uuids_subset[i], name)) {
 413             rem = true;
 414             break;
 415         }
 416     }
 417
 418     if (rem || rand() % 2) {
 419         (*count)++;
 420         return 1;
 421     } else {
 422         return 0;
 423     }
 424 }
 425
 426 static int
 427 testHashRemoveSet(const void *data ATTRIBUTE_UNUSED)
 428 {
 429     virHashTablePtr hash;
 430     int count = 0;
 431     int rcount;
 432     int ret = -1;
 433
 434     if (!(hash = testHashInit(0)))
 435         return -1;
 436
 437     /* seed the generator so that rand() provides reproducible sequence */
 438     srand(9000);
 439
 440     rcount = virHashRemoveSet(hash, testHashRemoveSetIter, &count);
 441
 442     if (count != rcount) {
 443         if (virTestGetVerbose()) {
 444             testError("\nvirHashRemoveSet didn't remove expected number of"
 445                       " entries, %d != %u\n",
 446                       rcount, count);
 447         }
 448         goto cleanup;
 449     }
 450
 451     if (testHashCheckCount(hash, ARRAY_CARDINALITY(uuids) - count) < 0)
 452         goto cleanup;
 453
 454     ret = 0;
 455
 456  cleanup:
 457     virHashFree(hash);
 458     return ret;
 459 }
 460
 461
 462 const int testSearchIndex = ARRAY_CARDINALITY(uuids_subset) / 2;
 463
 464 static int
 465 testHashSearchIter(const void *payload ATTRIBUTE_UNUSED,
 466                    const void *name,
 467                    const void *data ATTRIBUTE_UNUSED)
 468 {
 469     return STREQ(uuids_subset[testSearchIndex], name);
 470 }
 471
 472 static int
 473 testHashSearch(const void *data ATTRIBUTE_UNUSED)
 474 {
 475     virHashTablePtr hash;
 476     void *entry;
 477     int ret = -1;
 478
 479     if (!(hash = testHashInit(0)))
 480         return -1;
 481
 482     entry = virHashSearch(hash, testHashSearchIter, NULL);
 483
 484     if (!entry || STRNEQ(uuids_subset[testSearchIndex], entry)) {
 485         if (virTestGetVerbose()) {
 486             testError("\nvirHashSearch didn't find entry '%s'\n",
 487                       uuids_subset[testSearchIndex]);
 488         }
 489         goto cleanup;
 490     }
 491
 492     if (testHashCheckCount(hash, ARRAY_CARDINALITY(uuids)) < 0)
 493         goto cleanup;
 494
 495     ret = 0;
 496
 497  cleanup:
 498     virHashFree(hash);
 499     return ret;
 500 }
 501
 502
 503 static int
 504 testHashGetItemsCompKey(const virHashKeyValuePair *a,
 505                         const virHashKeyValuePair *b)
 506 {
 507     return strcmp(a->key, b->key);
 508 }
 509
 510 static int
 511 testHashGetItemsCompValue(const virHashKeyValuePair *a,
 512                           const virHashKeyValuePair *b)
 513 {
 514     return strcmp(a->value, b->value);
 515 }
 516
 517 static int
 518 testHashGetItems(const void *data ATTRIBUTE_UNUSED)
 519 {
 520     virHashTablePtr hash;
 521     virHashKeyValuePairPtr array = NULL;
 522     int ret = -1;
 523     char keya[] = "a";
 524     char keyb[] = "b";
 525     char keyc[] = "c";
 526     char value1[] = "1";
 527     char value2[] = "2";
 528     char value3[] = "3";
 529
 530     if (!(hash = virHashCreate(0, NULL)) ||
 531         virHashAddEntry(hash, keya, value3) < 0 ||
 532         virHashAddEntry(hash, keyc, value1) < 0 ||
 533         virHashAddEntry(hash, keyb, value2) < 0) {
 534         if (virTestGetVerbose()) {
 535             testError("\nfailed to create hash");
 536         }
 537         goto cleanup;
 538     }
 539
 540     if (!(array = virHashGetItems(hash, NULL)) ||
 541         array[3].key || array[3].value) {
 542         if (virTestGetVerbose()) {
 543             testError("\nfailed to get items with NULL sort");
 544         }
 545         goto cleanup;
 546     }
 547     VIR_FREE(array);
 548
 549     if (!(array = virHashGetItems(hash, testHashGetItemsCompKey)) ||
 550         STRNEQ(array[0].key, "a") ||
 551         STRNEQ(array[0].value, "3") ||
 552         STRNEQ(array[1].key, "b") ||
 553         STRNEQ(array[1].value, "2") ||
 554         STRNEQ(array[2].key, "c") ||
 555         STRNEQ(array[2].value, "1") ||
 556         array[3].key || array[3].value) {
 557         if (virTestGetVerbose()) {
 558             testError("\nfailed to get items with key sort");
 559         }
 560         goto cleanup;
 561     }
 562     VIR_FREE(array);
 563
 564     if (!(array = virHashGetItems(hash, testHashGetItemsCompValue)) ||
 565         STRNEQ(array[0].key, "c") ||
 566         STRNEQ(array[0].value, "1") ||
 567         STRNEQ(array[1].key, "b") ||
 568         STRNEQ(array[1].value, "2") ||
 569         STRNEQ(array[2].key, "a") ||
 570         STRNEQ(array[2].value, "3") ||
 571         array[3].key || array[3].value) {
 572         if (virTestGetVerbose()) {
 573             testError("\nfailed to get items with value sort");
 574         }
 575         goto cleanup;
 576     }
 577
 578     ret = 0;
 579
 580  cleanup:
 581     VIR_FREE(array);
 582     virHashFree(hash);
 583     return ret;
 584 }
 585
 586 static int
 587 testHashEqualCompValue(const void *value1, const void *value2)
 588 {
 589     return c_strcasecmp(value1, value2);
 590 }
 591
 592 static int
 593 testHashEqual(const void *data ATTRIBUTE_UNUSED)
 594 {
 595     virHashTablePtr hash1, hash2 = NULL;
 596     int ret = -1;
 597     char keya[] = "a";
 598     char keyb[] = "b";
 599     char keyc[] = "c";
 600     char value1_l[] = "m";
 601     char value2_l[] = "n";
 602     char value3_l[] = "o";
 603     char value1_u[] = "M";
 604     char value2_u[] = "N";
 605     char value3_u[] = "O";
 606     char value4_u[] = "P";
 607
 608     if (!(hash1 = virHashCreate(0, NULL)) ||
 609         !(hash2 = virHashCreate(0, NULL)) ||
 610         virHashAddEntry(hash1, keya, value1_l) < 0 ||
 611         virHashAddEntry(hash1, keyb, value2_l) < 0 ||
 612         virHashAddEntry(hash1, keyc, value3_l) < 0 ||
 613         virHashAddEntry(hash2, keya, value1_u) < 0 ||
 614         virHashAddEntry(hash2, keyb, value2_u) < 0) {
 615         if (virTestGetVerbose()) {
 616             testError("\nfailed to create hashes");
 617         }
 618         goto cleanup;
 619     }
 620
 621     if (virHashEqual(hash1, hash2, testHashEqualCompValue)) {
 622         if (virTestGetVerbose()) {
 623             testError("\nfailed equal test for different number of elements");
 624         }
 625         goto cleanup;
 626     }
 627
 628     if (virHashAddEntry(hash2, keyc, value4_u) < 0) {
 629         if (virTestGetVerbose()) {
 630             testError("\nfailed to add element to hash2");
 631         }
 632         goto cleanup;
 633     }
 634
 635     if (virHashEqual(hash1, hash2, testHashEqualCompValue)) {
 636         if (virTestGetVerbose()) {
 637             testError("\nfailed equal test for same number of elements");
 638         }
 639         goto cleanup;
 640     }
 641
 642     if (virHashUpdateEntry(hash2, keyc, value3_u) < 0) {
 643         if (virTestGetVerbose()) {
 644             testError("\nfailed to update element in hash2");
 645         }
 646         goto cleanup;
 647     }
 648
 649     if (!virHashEqual(hash1, hash2, testHashEqualCompValue)) {
 650         if (virTestGetVerbose()) {
 651             testError("\nfailed equal test for equal hash tables");
 652         }
 653         goto cleanup;
 654     }
 655
 656     ret = 0;
 657
 658  cleanup:
 659     virHashFree(hash1);
 660     virHashFree(hash2);
 661     return ret;
 662 }
 663
 664
 665 static int
 666 mymain(void)
 667 {
 668     int ret = 0;
 669
 670 #define DO_TEST_FULL(name, cmd, data, count)                        \
 671     do {                                                            \
 672         struct testInfo info = { data, count };                     \
 673         if (virtTestRun(name, testHash ## cmd, &info) < 0)          \
 674             ret = -1;                                               \
 675     } while (0)
 676
 677 #define DO_TEST_DATA(name, cmd, data)                               \
 678     DO_TEST_FULL(name "(" #data ")",                                \
 679                  cmd,                                               \
 680                  testHash ## cmd ## data,                           \
 681                  testHashCount ## cmd ## data)
 682
 683 #define DO_TEST_COUNT(name, cmd, count)                             \
 684     DO_TEST_FULL(name "(" #count ")", cmd, NULL, count)
 685
 686 #define DO_TEST(name, cmd)                                          \
 687     DO_TEST_FULL(name, cmd, NULL, -1)
 688
 689     DO_TEST_COUNT("Grow", Grow, 1);
 690     DO_TEST_COUNT("Grow", Grow, 10);
 691     DO_TEST_COUNT("Grow", Grow, 42);
 692     DO_TEST("Update", Update);
 693     DO_TEST("Remove", Remove);
 694     DO_TEST_DATA("Remove in ForEach", RemoveForEach, Some);
 695     DO_TEST_DATA("Remove in ForEach", RemoveForEach, All);
 696     DO_TEST_DATA("Remove in ForEach", RemoveForEach, Forbidden);
 697     DO_TEST("Steal", Steal);
 698     DO_TEST("Forbidden ops in ForEach", ForEach);
 699     DO_TEST("RemoveSet", RemoveSet);
 700     DO_TEST("Search", Search);
 701     DO_TEST("GetItems", GetItems);
 702     DO_TEST("Equal", Equal);
 703
 704     return (ret == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
 705 }
 706
 707 VIRT_TEST_MAIN(mymain)