src/dict_unit.c

   1 /*******************************/
   2 /* GENERATED FILE, DO NOT EDIT */
   3 /*******************************/
   4
   5 #include <stdio.h>
   6 #include "xbt.h"
   7 /*******************************/
   8 /* GENERATED FILE, DO NOT EDIT */
   9 /*******************************/
  10
  11 #line 810 "xbt/dict.c"
  12 #include "xbt.h"
  13 #include "xbt/ex.h"
  14 #include "portable.h"
  15
  16 XBT_LOG_EXTERNAL_CATEGORY(xbt_dict);
  17 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict, xbt,
  18                                 "Dictionaries provide the same functionalities than hash tables");
  19
  20
  21 static void print_str(void *str)
  22 {
  23   printf("%s", (char *) PRINTF_STR(str));
  24 }
  25
  26 static void debuged_add_ext(xbt_dict_t head, const char *key,
  27                             const char *data_to_fill)
  28 {
  29   char *data = xbt_strdup(data_to_fill);
  30
  31   xbt_test_log2("Add %s under %s", PRINTF_STR(data_to_fill), PRINTF_STR(key));
  32
  33   xbt_dict_set(head, key, data, &free);
  34   if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) {
  35     xbt_dict_dump(head, (void (*)(void *)) &printf);
  36     fflush(stdout);
  37   }
  38 }
  39
  40 static void debuged_add(xbt_dict_t head, const char *key)
  41 {
  42   debuged_add_ext(head, key, key);
  43 }
  44
  45 static void fill(xbt_dict_t * head)
  46 {
  47   xbt_test_add0("Fill in the dictionnary");
  48
  49   *head = xbt_dict_new();
  50   debuged_add(*head, "12");
  51   debuged_add(*head, "12a");
  52   debuged_add(*head, "12b");
  53   debuged_add(*head, "123");
  54   debuged_add(*head, "123456");
  55   /* Child becomes child of what to add */
  56   debuged_add(*head, "1234");
  57   /* Need of common ancestor */
  58   debuged_add(*head, "123457");
  59 }
  60
  61
  62 static void search_ext(xbt_dict_t head, const char *key, const char *data)
  63 {
  64   void *found;
  65
  66   xbt_test_add1("Search %s", key);
  67   found = xbt_dict_get(head, key);
  68   xbt_test_log1("Found %s", (char *) found);
  69   if (data)
  70     xbt_test_assert1(found,
  71                      "data do not match expectations: found NULL while searching for %s",
  72                      data);
  73   if (found)
  74     xbt_test_assert2(!strcmp((char *) data, found),
  75                      "data do not match expectations: found %s while searching for %s",
  76                      (char *) found, data);
  77 }
  78
  79 static void search(xbt_dict_t head, const char *key)
  80 {
  81   search_ext(head, key, key);
  82 }
  83
  84 static void debuged_remove(xbt_dict_t head, const char *key)
  85 {
  86
  87   xbt_test_add1("Remove '%s'", PRINTF_STR(key));
  88   xbt_dict_remove(head, key);
  89   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
  90 }
  91
  92
  93 static void traverse(xbt_dict_t head)
  94 {
  95   xbt_dict_cursor_t cursor = NULL;
  96   char *key;
  97   char *data;
  98   int i = 0;
  99
 100   xbt_dict_foreach(head, cursor, key, data) {
 101     if (!key || !data || strcmp(key, data)) {
 102       xbt_test_log3("Seen #%d:  %s->%s", ++i, PRINTF_STR(key),
 103                     PRINTF_STR(data));
 104     } else {
 105       xbt_test_log2("Seen #%d:  %s", ++i, PRINTF_STR(key));
 106     }
 107     xbt_test_assert2(!data || !strcmp(key, data),
 108                      "Key(%s) != value(%s). Aborting", key, data);
 109   }
 110 }
 111
 112 static void search_not_found(xbt_dict_t head, const char *data)
 113 {
 114   int ok = 0;
 115   xbt_ex_t e;
 116
 117   xbt_test_add1("Search %s (expected not to be found)", data);
 118
 119   TRY {
 120     data = xbt_dict_get(head, data);
 121     THROW1(unknown_error, 0, "Found something which shouldn't be there (%s)",
 122            data);
 123   } CATCH(e) {
 124     if (e.category != not_found_error)
 125       xbt_test_exception(e);
 126     xbt_ex_free(e);
 127     ok = 1;
 128   }
 129   xbt_test_assert0(ok, "Exception not raised");
 130 }
 131
 132 static void count(xbt_dict_t dict, int length)
 133 {
 134   xbt_dict_cursor_t cursor;
 135   char *key;
 136   void *data;
 137   int effective = 0;
 138
 139
 140   xbt_test_add1("Count elements (expecting %d)", length);
 141   xbt_test_assert2(xbt_dict_length(dict) == length,
 142                    "Announced length(%d) != %d.", xbt_dict_length(dict),
 143                    length);
 144
 145   xbt_dict_foreach(dict, cursor, key, data)
 146     effective++;
 147
 148   xbt_test_assert2(effective == length, "Effective length(%d) != %d.",
 149                    effective, length);
 150
 151 }
 152
 153 static void count_check_get_key(xbt_dict_t dict, int length)
 154 {
 155   xbt_dict_cursor_t cursor;
 156   char *key,*key2;
 157   void *data;
 158   int effective = 0;
 159
 160
 161   xbt_test_add1("Count elements (expecting %d), and test the getkey function", length);
 162   xbt_test_assert2(xbt_dict_length(dict) == length,
 163                    "Announced length(%d) != %d.", xbt_dict_length(dict),
 164                    length);
 165
 166   xbt_dict_foreach(dict, cursor, key, data) {
 167     effective++;
 168     key2 = xbt_dict_get_key(dict,data);
 169     xbt_assert2(!strcmp(key,key2),
 170           "The data was registered under %s instead of %s as expected",key2,key);
 171   }
 172
 173   xbt_test_assert2(effective == length, "Effective length(%d) != %d.",
 174                    effective, length);
 175
 176 }
 177
 178 xbt_ex_t e;
 179 xbt_dict_t head = NULL;
 180 char *data;
 181
 182
 183 XBT_TEST_UNIT("basic", test_dict_basic,"Basic usage: change, retrieve, traverse")
 184 {
 185   xbt_test_add0("Traversal the null dictionary");
 186   traverse(head);
 187
 188   xbt_test_add0("Traversal and search the empty dictionary");
 189   head = xbt_dict_new();
 190   traverse(head);
 191   TRY {
 192     debuged_remove(head, "12346");
 193   } CATCH(e) {
 194     if (e.category != not_found_error)
 195       xbt_test_exception(e);
 196     xbt_ex_free(e);
 197   }
 198   xbt_dict_free(&head);
 199
 200   xbt_test_add0("Traverse the full dictionary");
 201   fill(&head);
 202   count_check_get_key(head, 7);
 203
 204   debuged_add_ext(head, "toto", "tutu");
 205   search_ext(head, "toto", "tutu");
 206   debuged_remove(head, "toto");
 207
 208   search(head, "12a");
 209   traverse(head);
 210
 211   xbt_test_add0("Free the dictionary (twice)");
 212   xbt_dict_free(&head);
 213   xbt_dict_free(&head);
 214
 215   /* CHANGING */
 216   fill(&head);
 217   count_check_get_key(head, 7);
 218   xbt_test_add0("Change 123 to 'Changed 123'");
 219   xbt_dict_set(head, "123", strdup("Changed 123"), &free);
 220   count_check_get_key(head, 7);
 221
 222   xbt_test_add0("Change 123 back to '123'");
 223   xbt_dict_set(head, "123", strdup("123"), &free);
 224   count_check_get_key(head, 7);
 225
 226   xbt_test_add0("Change 12a to 'Dummy 12a'");
 227   xbt_dict_set(head, "12a", strdup("Dummy 12a"), &free);
 228   count_check_get_key(head, 7);
 229
 230   xbt_test_add0("Change 12a to '12a'");
 231   xbt_dict_set(head, "12a", strdup("12a"), &free);
 232   count_check_get_key(head, 7);
 233
 234   xbt_test_add0("Traverse the resulting dictionary");
 235   traverse(head);
 236
 237   /* RETRIEVE */
 238   xbt_test_add0("Search 123");
 239   data = xbt_dict_get(head, "123");
 240   xbt_test_assert(data);
 241   xbt_test_assert(!strcmp("123", data));
 242
 243   search_not_found(head, "Can't be found");
 244   search_not_found(head, "123 Can't be found");
 245   search_not_found(head, "12345678 NOT");
 246
 247   search(head, "12a");
 248   search(head, "12b");
 249   search(head, "12");
 250   search(head, "123456");
 251   search(head, "1234");
 252   search(head, "123457");
 253
 254   xbt_test_add0("Traverse the resulting dictionary");
 255   traverse(head);
 256
 257   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
 258
 259   xbt_test_add0("Free the dictionary twice");
 260   xbt_dict_free(&head);
 261   xbt_dict_free(&head);
 262
 263   xbt_test_add0("Traverse the resulting dictionary");
 264   traverse(head);
 265 }
 266
 267 XBT_TEST_UNIT("remove", test_dict_remove, "Removing some values")
 268 {
 269   fill(&head);
 270   count(head, 7);
 271   xbt_test_add0("Remove non existing data");
 272   TRY {
 273     debuged_remove(head, "Does not exist");
 274   }
 275   CATCH(e) {
 276     if (e.category != not_found_error)
 277       xbt_test_exception(e);
 278     xbt_ex_free(e);
 279   }
 280   traverse(head);
 281
 282   xbt_dict_free(&head);
 283
 284   xbt_test_add0
 285     ("Remove each data manually (traversing the resulting dictionary each time)");
 286   fill(&head);
 287   debuged_remove(head, "12a");
 288   traverse(head);
 289   count(head, 6);
 290   debuged_remove(head, "12b");
 291   traverse(head);
 292   count(head, 5);
 293   debuged_remove(head, "12");
 294   traverse(head);
 295   count(head, 4);
 296   debuged_remove(head, "123456");
 297   traverse(head);
 298   count(head, 3);
 299   TRY {
 300     debuged_remove(head, "12346");
 301   }
 302   CATCH(e) {
 303     if (e.category != not_found_error)
 304       xbt_test_exception(e);
 305     xbt_ex_free(e);
 306     traverse(head);
 307   }
 308   debuged_remove(head, "1234");
 309   traverse(head);
 310   debuged_remove(head, "123457");
 311   traverse(head);
 312   debuged_remove(head, "123");
 313   traverse(head);
 314   TRY {
 315     debuged_remove(head, "12346");
 316   }
 317   CATCH(e) {
 318     if (e.category != not_found_error)
 319       xbt_test_exception(e);
 320     xbt_ex_free(e);
 321   }
 322   traverse(head);
 323
 324   xbt_test_add0("Free dict, create new fresh one, and then reset the dict");
 325   xbt_dict_free(&head);
 326   fill(&head);
 327   xbt_dict_reset(head);
 328   count(head, 0);
 329   traverse(head);
 330
 331   xbt_test_add0("Free the dictionary twice");
 332   xbt_dict_free(&head);
 333   xbt_dict_free(&head);
 334 }
 335
 336 XBT_TEST_UNIT("nulldata", test_dict_nulldata, "NULL data management")
 337 {
 338   fill(&head);
 339
 340   xbt_test_add0("Store NULL under 'null'");
 341   xbt_dict_set(head, "null", NULL, NULL);
 342   search_ext(head, "null", NULL);
 343
 344   xbt_test_add0("Check whether I see it while traversing...");
 345   {
 346     xbt_dict_cursor_t cursor = NULL;
 347     char *key;
 348     int found = 0;
 349
 350     xbt_dict_foreach(head, cursor, key, data) {
 351       if (!key || !data || strcmp(key, data)) {
 352         xbt_test_log2("Seen:  %s->%s", PRINTF_STR(key), PRINTF_STR(data));
 353       } else {
 354         xbt_test_log1("Seen:  %s", PRINTF_STR(key));
 355       }
 356
 357       if (!strcmp(key, "null"))
 358         found = 1;
 359     }
 360     xbt_test_assert0(found,
 361                      "the key 'null', associated to NULL is not found");
 362   }
 363   xbt_dict_free(&head);
 364 }
 365
 366 static void debuged_addi(xbt_dict_t head, uintptr_t key, uintptr_t data) {
 367         uintptr_t stored_data = 0;
 368   xbt_test_log2("Add %zu under %zu", data, key);
 369
 370   xbt_dicti_set(head, key, data);
 371   if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) {
 372     xbt_dict_dump(head, (void (*)(void *)) &printf);
 373     fflush(stdout);
 374   }
 375   stored_data = xbt_dicti_get(head, key);
 376   xbt_test_assert3(stored_data==data,
 377       "Retrieved data (%zu) is not what I just stored (%zu) under key %zu",stored_data,data,key);
 378 }
 379
 380 XBT_TEST_UNIT("dicti", test_dict_scalar, "Scalar data and key management")
 381 {
 382   xbt_test_add0("Fill in the dictionnary");
 383
 384   head = xbt_dict_new();
 385   debuged_addi(head, 12, 12);
 386   debuged_addi(head, 13, 13);
 387   debuged_addi(head, 14, 14);
 388   debuged_addi(head, 15, 15);
 389   /* Change values */
 390   debuged_addi(head, 12, 15);
 391   debuged_addi(head, 15, 2000);
 392   debuged_addi(head, 15, 3000);
 393   /* 0 as key */
 394   debuged_addi(head, 0, 1000);
 395   debuged_addi(head, 0, 2000);
 396   debuged_addi(head, 0, 3000);
 397   /* 0 as value */
 398   debuged_addi(head, 12, 0);
 399   debuged_addi(head, 13, 0);
 400   debuged_addi(head, 12, 0);
 401   debuged_addi(head, 0, 0);
 402
 403   xbt_dict_free(&head);
 404 }
 405
 406 #define NB_ELM 20000
 407 #define SIZEOFKEY 1024
 408 static int countelems(xbt_dict_t head)
 409 {
 410   xbt_dict_cursor_t cursor;
 411   char *key;
 412   void *data;
 413   int res = 0;
 414
 415   xbt_dict_foreach(head, cursor, key, data) {
 416     res++;
 417   }
 418   return res;
 419 }
 420
 421 XBT_TEST_UNIT("crash", test_dict_crash, "Crash test")
 422 {
 423   xbt_dict_t head = NULL;
 424   int i, j, k, nb;
 425   char *key;
 426   void *data;
 427
 428   srand((unsigned int) time(NULL));
 429
 430   for (i = 0; i < 10; i++) {
 431     xbt_test_add2("CRASH test number %d (%d to go)", i + 1, 10 - i - 1);
 432     xbt_test_log0("Fill the struct, count its elems and frees the structure");
 433     xbt_test_log1("using 1000 elements with %d chars long randomized keys.",
 434                   SIZEOFKEY);
 435     head = xbt_dict_new();
 436     /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
 437     nb = 0;
 438     for (j = 0; j < 1000; j++) {
 439       char *data = NULL;
 440       key = xbt_malloc(SIZEOFKEY);
 441
 442       do {
 443         for (k = 0; k < SIZEOFKEY - 1; k++)
 444           key[k] = rand() % ('z' - 'a') + 'a';
 445         key[k] = '\0';
 446         /*      printf("[%d %s]\n",j,key); */
 447         data = xbt_dict_get_or_null(head, key);
 448       } while (data != NULL);
 449
 450       xbt_dict_set(head, key, key, &free);
 451       data = xbt_dict_get(head, key);
 452       xbt_test_assert2(!strcmp(key, data),
 453                        "Retrieved value (%s) != Injected value (%s)", key,
 454                        data);
 455
 456       count(head, j + 1);
 457     }
 458     /*    xbt_dict_dump(head,(void (*)(void*))&printf); */
 459     traverse(head);
 460     xbt_dict_free(&head);
 461     xbt_dict_free(&head);
 462   }
 463
 464
 465   head = xbt_dict_new();
 466   xbt_test_add1("Fill %d elements, with keys being the number of element",
 467                 NB_ELM);
 468   for (j = 0; j < NB_ELM; j++) {
 469     /* if (!(j%1000)) { printf("."); fflush(stdout); } */
 470
 471     key = xbt_malloc(10);
 472
 473     sprintf(key, "%d", j);
 474     xbt_dict_set(head, key, key, &free);
 475   }
 476   /*xbt_dict_dump(head,(void (*)(void*))&printf); */
 477
 478   xbt_test_add0("Count the elements (retrieving the key and data for each)");
 479   i = countelems(head);
 480   xbt_test_log1("There is %d elements", i);
 481
 482   xbt_test_add1("Search my %d elements 20 times", NB_ELM);
 483   key = xbt_malloc(10);
 484   for (i = 0; i < 20; i++) {
 485     /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
 486     for (j = 0; j < NB_ELM; j++) {
 487
 488       sprintf(key, "%d", j);
 489       data = xbt_dict_get(head, key);
 490       xbt_test_assert2(!strcmp(key, (char *) data),
 491                        "with get, key=%s != data=%s", key, (char *) data);
 492       data = xbt_dict_get_ext(head, key, strlen(key));
 493       xbt_test_assert2(!strcmp(key, (char *) data),
 494                        "with get_ext, key=%s != data=%s", key, (char *) data);
 495     }
 496   }
 497   free(key);
 498
 499   xbt_test_add1("Remove my %d elements", NB_ELM);
 500   key = xbt_malloc(10);
 501   for (j = 0; j < NB_ELM; j++) {
 502     /* if (!(j%10000)) printf("."); fflush(stdout); */
 503
 504     sprintf(key, "%d", j);
 505     xbt_dict_remove(head, key);
 506   }
 507   free(key);
 508
 509
 510   xbt_test_add0("Free the structure (twice)");
 511   xbt_dict_free(&head);
 512   xbt_dict_free(&head);
 513 }
 514
 515 static void str_free(void *s)
 516 {
 517   char *c = *(char **) s;
 518   free(c);
 519 }
 520
 521 XBT_TEST_UNIT("multicrash", test_dict_multicrash, "Multi-dict crash test")
 522 {
 523
 524 #undef NB_ELM
 525 #define NB_ELM 100              /*00 */
 526 #define DEPTH 5
 527 #define KEY_SIZE 512
 528 #define NB_TEST 20              /*20 */
 529   int verbose = 0;
 530
 531   xbt_dict_t mdict = NULL;
 532   int i, j, k, l;
 533   xbt_dynar_t keys = xbt_dynar_new(sizeof(char *), str_free);
 534   void *data;
 535   char *key;
 536
 537
 538   xbt_test_add0("Generic multicache CRASH test");
 539   xbt_test_log4(" Fill the struct and frees it %d times, using %d elements, "
 540                 "depth of multicache=%d, key size=%d",
 541                 NB_TEST, NB_ELM, DEPTH, KEY_SIZE);
 542
 543   for (l = 0; l < DEPTH; l++) {
 544     key = xbt_malloc(KEY_SIZE);
 545     xbt_dynar_push(keys, &key);
 546   }
 547
 548   for (i = 0; i < NB_TEST; i++) {
 549     mdict = xbt_dict_new();
 550     VERB1("mdict=%p", mdict);
 551     if (verbose > 0)
 552       printf("Test %d\n", i);
 553     /* else if (i%10) printf("."); else printf("%d",i/10); */
 554
 555     for (j = 0; j < NB_ELM; j++) {
 556       if (verbose > 0)
 557         printf("  Add {");
 558
 559       for (l = 0; l < DEPTH; l++) {
 560         key = *(char **) xbt_dynar_get_ptr(keys, l);
 561
 562         for (k = 0; k < KEY_SIZE - 1; k++)
 563           key[k] = rand() % ('z' - 'a') + 'a';
 564
 565         key[k] = '\0';
 566
 567         if (verbose > 0)
 568           printf("%p=%s %s ", key, key, (l < DEPTH - 1 ? ";" : "}"));
 569       }
 570       if (verbose > 0)
 571         printf("in multitree %p.\n", mdict);
 572
 573       xbt_multidict_set(mdict, keys, xbt_strdup(key), free);
 574
 575       data = xbt_multidict_get(mdict, keys);
 576
 577       xbt_test_assert2(data && !strcmp((char *) data, key),
 578                        "Retrieved value (%s) does not match the given one (%s)\n",
 579                        (char *) data, key);
 580     }
 581     xbt_dict_free(&mdict);
 582   }
 583
 584   xbt_dynar_free(&keys);
 585
 586   /*  if (verbose>0)
 587      xbt_dict_dump(mdict,&xbt_dict_print); */
 588
 589   xbt_dict_free(&mdict);
 590   xbt_dynar_free(&keys);
 591
 592 }
 593 /*******************************/
 594 /* GENERATED FILE, DO NOT EDIT */
 595 /*******************************/
 596