src/xbt/dict.cpp

   1 /* dict - a generic dictionary, variation over hash table                   */
   2
   3 /* Copyright (c) 2004-2018. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include <cstdio>
  10 #include <cstring>
  11
  12 #include "xbt/dict.h"
  13 #include "xbt/ex.h"
  14 #include <xbt/ex.hpp>
  15 #include "xbt/log.h"
  16 #include "xbt/mallocator.h"
  17 #include "src/xbt_modinter.h"
  18 #include "xbt/str.h"
  19 #include "dict_private.h"
  20
  21 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict, xbt, "Dictionaries provide the same functionalities as hash tables");
  22
  23 /**
  24  * \brief Constructor
  25  * \param free_ctn function to call with (\a data as argument) when \a data is removed from the dictionary
  26  * \return pointer to the destination
  27  * \see xbt_dict_free()
  28  *
  29  * Creates and initialize a new dictionary with a default hashtable size.
  30  * The dictionary is homogeneous: each element share the same free function.
  31  */
  32 xbt_dict_t xbt_dict_new_homogeneous(void_f_pvoid_t free_ctn)
  33 {
  34   if (dict_elm_mallocator == nullptr)
  35     xbt_dict_preinit();
  36
  37   xbt_dict_t dict;
  38
  39   dict = xbt_new(s_xbt_dict_t, 1);
  40   dict->free_f = free_ctn;
  41   dict->table_size = 127;
  42   dict->table = xbt_new0(xbt_dictelm_t, dict->table_size + 1);
  43   dict->count = 0;
  44   dict->fill = 0;
  45
  46   return dict;
  47 }
  48
  49 /**
  50  * \brief Destructor
  51  * \param dict the dictionary to be freed
  52  *
  53  * Frees a dictionary with all the data
  54  */
  55 void xbt_dict_free(xbt_dict_t * dict)
  56 {
  57   if (dict != nullptr && *dict != nullptr) {
  58     int table_size       = (*dict)->table_size;
  59     xbt_dictelm_t* table = (*dict)->table;
  60     /* Warning: the size of the table is 'table_size+1'...
  61      * This is because table_size is used as a binary mask in xbt_dict_rehash */
  62     for (int i = 0; (*dict)->count && i <= table_size; i++) {
  63       xbt_dictelm_t current = table[i];
  64       xbt_dictelm_t previous;
  65
  66       while (current != nullptr) {
  67         previous = current;
  68         current = current->next;
  69         xbt_dictelm_free(*dict, previous);
  70         (*dict)->count--;
  71       }
  72     }
  73     xbt_free(table);
  74     xbt_free(*dict);
  75     *dict = nullptr;
  76   }
  77 }
  78
  79 /** Returns the amount of elements in the dict */
  80 unsigned int xbt_dict_size(xbt_dict_t dict)
  81 {
  82   return (dict != nullptr ? static_cast<unsigned int>(dict->count) : static_cast<unsigned int>(0));
  83 }
  84
  85 /* Expend the size of the dict */
  86 static void xbt_dict_rehash(xbt_dict_t dict)
  87 {
  88   const unsigned oldsize = dict->table_size + 1;
  89   unsigned newsize = oldsize * 2;
  90
  91   xbt_dictelm_t *currcell = (xbt_dictelm_t *) xbt_realloc((char *) dict->table, newsize * sizeof(xbt_dictelm_t));
  92   memset(&currcell[oldsize], 0, oldsize * sizeof(xbt_dictelm_t));       /* zero second half */
  93   newsize--;
  94   dict->table_size = newsize;
  95   dict->table = currcell;
  96   XBT_DEBUG("REHASH (%u->%u)", oldsize, newsize);
  97
  98   for (unsigned i = 0; i < oldsize; i++, currcell++) {
  99     if (*currcell == nullptr) /* empty cell */
 100       continue;
 101
 102     xbt_dictelm_t *twincell = currcell + oldsize;
 103     xbt_dictelm_t *pprev = currcell;
 104     xbt_dictelm_t bucklet = *currcell;
 105     for (; bucklet != nullptr; bucklet = *pprev) {
 106       /* Since we use "& size" instead of "%size" and since the size was doubled, each bucklet of this cell must either:
 107          - stay  in  cell i (ie, currcell)
 108          - go to the cell i+oldsize (ie, twincell) */
 109       if ((bucklet->hash_code & newsize) != i) {        /* Move to b */
 110         *pprev = bucklet->next;
 111         bucklet->next = *twincell;
 112         if (*twincell == nullptr)
 113           dict->fill++;
 114         *twincell = bucklet;
 115       } else {
 116         pprev = &bucklet->next;
 117       }
 118     }
 119
 120     if (*currcell == nullptr) /* everything moved */
 121       dict->fill--;
 122   }
 123 }
 124
 125 /**
 126  * \brief Add data to the dict (arbitrary key)
 127  * \param dict the container
 128  * \param key the key to set the new data
 129  * \param key_len the size of the \a key
 130  * \param data the data to add in the dict
 131  * \param free_ctn unused parameter (kept for compatibility)
 132  *
 133  * Set the \a data in the structure under the \a key, which can be any kind of data, as long as its length is provided
 134  * in \a key_len.
 135  */
 136 void xbt_dict_set_ext(xbt_dict_t dict, const char* key, int key_len, void* data,
 137                       XBT_ATTRIB_UNUSED void_f_pvoid_t free_ctn)
 138 {
 139   unsigned int hash_code = xbt_str_hash_ext(key, key_len);
 140
 141   xbt_dictelm_t current;
 142   xbt_dictelm_t previous = nullptr;
 143
 144   XBT_CDEBUG(xbt_dict, "ADD %.*s hash = %u, size = %d, & = %u", key_len, key, hash_code,
 145              dict->table_size, hash_code & dict->table_size);
 146   current = dict->table[hash_code & dict->table_size];
 147   while (current != nullptr && (hash_code != current->hash_code || key_len != current->key_len
 148           || memcmp(key, current->key, key_len))) {
 149     previous = current;
 150     current = current->next;
 151   }
 152
 153   if (current == nullptr) {
 154     /* this key doesn't exist yet */
 155     current = xbt_dictelm_new(key, key_len, hash_code, data);
 156     dict->count++;
 157     if (previous == nullptr) {
 158       dict->table[hash_code & dict->table_size] = current;
 159       dict->fill++;
 160       if ((dict->fill * 100) / (dict->table_size + 1) > MAX_FILL_PERCENT)
 161         xbt_dict_rehash(dict);
 162     } else {
 163       previous->next = current;
 164     }
 165   } else {
 166     XBT_CDEBUG(xbt_dict, "Replace %.*s by %.*s under key %.*s",
 167                key_len, (char *) current->content, key_len, (char *) data, key_len, (char *) key);
 168     /* there is already an element with the same key: overwrite it */
 169     xbt_dictelm_set_data(dict, current, data);
 170   }
 171 }
 172
 173 /**
 174  * \brief Add data to the dict (null-terminated key)
 175  *
 176  * \param dict the dict
 177  * \param key the key to set the new data
 178  * \param data the data to add in the dict
 179  * \param free_ctn unused parameter (kept for compatibility)
 180  *
 181  * set the \a data in the structure under the \a key, which is anull terminated string.
 182  */
 183 void xbt_dict_set(xbt_dict_t dict, const char *key, void *data, void_f_pvoid_t free_ctn)
 184 {
 185   xbt_dict_set_ext(dict, key, strlen(key), data, free_ctn);
 186 }
 187
 188 /**
 189  * \brief Retrieve data from the dict (arbitrary key)
 190  *
 191  * \param dict the dealer of data
 192  * \param key the key to find data
 193  * \param key_len the size of the \a key
 194  * \return the data that we are looking for
 195  *
 196  * Search the given \a key. Throws not_found_error when not found.
 197  */
 198 void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len)
 199 {
 200   unsigned int hash_code = xbt_str_hash_ext(key, key_len);
 201   xbt_dictelm_t current = dict->table[hash_code & dict->table_size];
 202
 203   while (current != nullptr && (hash_code != current->hash_code || key_len != current->key_len
 204           || memcmp(key, current->key, key_len))) {
 205     current = current->next;
 206   }
 207
 208   if (current == nullptr)
 209     THROWF(not_found_error, 0, "key %.*s not found", key_len, key);
 210
 211   return current->content;
 212 }
 213
 214 /** @brief like xbt_dict_get_ext(), but returning nullptr when not found */
 215 void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key, int key_len)
 216 {
 217   unsigned int hash_code = xbt_str_hash_ext(key, key_len);
 218   xbt_dictelm_t current = dict->table[hash_code & dict->table_size];
 219
 220   while (current != nullptr && (hash_code != current->hash_code || key_len != current->key_len
 221           || memcmp(key, current->key, key_len))) {
 222     current = current->next;
 223   }
 224
 225   if (current == nullptr)
 226     return nullptr;
 227
 228   return current->content;
 229 }
 230
 231 /**
 232  * @brief retrieve the key associated to that object. Warning, that's a linear search
 233  *
 234  * Returns nullptr if the object cannot be found
 235  */
 236 char *xbt_dict_get_key(xbt_dict_t dict, const void *data)
 237 {
 238   for (int i = 0; i <= dict->table_size; i++) {
 239     xbt_dictelm_t current = dict->table[i];
 240     while (current != nullptr) {
 241       if (current->content == data)
 242         return current->key;
 243       current = current->next;
 244     }
 245   }
 246   return nullptr;
 247 }
 248
 249 /**
 250  * \brief Retrieve data from the dict (null-terminated key)
 251  *
 252  * \param dict the dealer of data
 253  * \param key the key to find data
 254  * \return the data that we are looking for
 255  *
 256  * Search the given \a key. Throws not_found_error when not found.
 257  * Check xbt_dict_get_or_null() for a version returning nullptr without exception when not found.
 258  */
 259 void *xbt_dict_get(xbt_dict_t dict, const char *key)
 260 {
 261   return xbt_dict_get_elm(dict, key)->content;
 262 }
 263
 264 /**
 265  * \brief Retrieve element from the dict (null-terminated key)
 266  *
 267  * \param dict the dealer of data
 268  * \param key the key to find data
 269  * \return the s_xbt_dictelm_t that we are looking for
 270  *
 271  * Search the given \a key. Throws not_found_error when not found.
 272  * Check xbt_dict_get_or_null() for a version returning nullptr without exception when not found.
 273  */
 274 xbt_dictelm_t xbt_dict_get_elm(xbt_dict_t dict, const char *key)
 275 {
 276   xbt_dictelm_t current = xbt_dict_get_elm_or_null(dict, key);
 277
 278   if (current == nullptr)
 279     THROWF(not_found_error, 0, "key %s not found", key);
 280
 281   return current;
 282 }
 283
 284 /**
 285  * \brief like xbt_dict_get(), but returning nullptr when not found
 286  */
 287 void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key)
 288 {
 289   xbt_dictelm_t current = xbt_dict_get_elm_or_null(dict, key);
 290
 291   if (current == nullptr)
 292     return nullptr;
 293
 294   return current->content;
 295 }
 296
 297 /**
 298  * \brief like xbt_dict_get_elm(), but returning nullptr when not found
 299  */
 300 xbt_dictelm_t xbt_dict_get_elm_or_null(xbt_dict_t dict, const char *key)
 301 {
 302   unsigned int hash_code = xbt_str_hash(key);
 303   xbt_dictelm_t current = dict->table[hash_code & dict->table_size];
 304
 305   while (current != nullptr && (hash_code != current->hash_code || strcmp(key, current->key)))
 306     current = current->next;
 307   return current;
 308 }
 309
 310 /**
 311  * \brief Remove data from the dict (arbitrary key)
 312  *
 313  * \param dict the trash can
 314  * \param key the key of the data to be removed
 315  * \param key_len the size of the \a key
 316  *
 317  * Remove the entry associated with the given \a key (throws not_found)
 318  */
 319 void xbt_dict_remove_ext(xbt_dict_t dict, const char *key, int key_len)
 320 {
 321   unsigned int hash_code = xbt_str_hash_ext(key, key_len);
 322   xbt_dictelm_t previous = nullptr;
 323   xbt_dictelm_t current = dict->table[hash_code & dict->table_size];
 324
 325   while (current != nullptr && (hash_code != current->hash_code || key_len != current->key_len
 326           || strncmp(key, current->key, key_len))) {
 327     previous = current;         /* save the previous node */
 328     current = current->next;
 329   }
 330
 331   if (current == nullptr)
 332     THROWF(not_found_error, 0, "key %.*s not found", key_len, key);
 333   else {
 334     if (previous != nullptr) {
 335       previous->next = current->next;
 336     } else {
 337       dict->table[hash_code & dict->table_size] = current->next;
 338     }
 339   }
 340
 341   if (not dict->table[hash_code & dict->table_size])
 342     dict->fill--;
 343
 344   xbt_dictelm_free(dict, current);
 345   dict->count--;
 346 }
 347
 348 /**
 349  * \brief Remove data from the dict (null-terminated key)
 350  *
 351  * \param dict the dict
 352  * \param key the key of the data to be removed
 353  *
 354  * Remove the entry associated with the given \a key
 355  */
 356 void xbt_dict_remove(xbt_dict_t dict, const char *key)
 357 {
 358   xbt_dict_remove_ext(dict, key, strlen(key));
 359 }
 360
 361 /** @brief Remove all data from the dict */
 362 void xbt_dict_reset(xbt_dict_t dict)
 363 {
 364   if (dict->count == 0)
 365     return;
 366
 367   for (int i = 0; i <= dict->table_size; i++) {
 368     xbt_dictelm_t previous = nullptr;
 369     xbt_dictelm_t current = dict->table[i];
 370     while (current != nullptr) {
 371       previous = current;
 372       current = current->next;
 373       xbt_dictelm_free(dict, previous);
 374     }
 375     dict->table[i] = nullptr;
 376   }
 377
 378   dict->count = 0;
 379   dict->fill = 0;
 380 }
 381
 382 /**
 383  * \brief Return the number of elements in the dict.
 384  * \param dict a dictionary
 385  */
 386 int xbt_dict_length(xbt_dict_t dict)
 387 {
 388   return dict->count;
 389 }
 390
 391 /**
 392  * \brief test if the dict is empty or not
 393  */
 394 int xbt_dict_is_empty(xbt_dict_t dict)
 395 {
 396   return not dict || (xbt_dict_length(dict) == 0);
 397 }
 398
 399 /**
 400  * \brief Outputs the content of the structure (debugging purpose)
 401  *
 402  * \param dict the exibitionist
 403  * \param output a function to dump each data in the tree (check @ref xbt_dict_dump_output_string)
 404  *
 405  * Outputs the content of the structure. (for debugging purpose). \a output is a function to output the data. If nullptr,
 406  * data won't be displayed.
 407  */
 408 void xbt_dict_dump(xbt_dict_t dict, void_f_pvoid_t output)
 409 {
 410   xbt_dictelm_t element;
 411   printf("Dict %p:\n", dict);
 412   if (dict != nullptr) {
 413     for (int i = 0; i < dict->table_size; i++) {
 414       element = dict->table[i];
 415       if (element) {
 416         printf("[\n");
 417         while (element != nullptr) {
 418           printf(" %s -> '", element->key);
 419           if (output != nullptr) {
 420             output(element->content);
 421           }
 422           printf("'\n");
 423           element = element->next;
 424         }
 425         printf("]\n");
 426       } else {
 427         printf("[]\n");
 428       }
 429     }
 430   }
 431 }
 432
 433 /**
 434  * Create the dict mallocators.
 435  * This is an internal XBT function called during the lib initialization.
 436  * It can be used several times to recreate the mallocator, for example when you switch to MC mode
 437  */
 438 void xbt_dict_preinit()
 439 {
 440   if (dict_elm_mallocator == nullptr)
 441     dict_elm_mallocator = xbt_mallocator_new(256, dict_elm_mallocator_new_f, dict_elm_mallocator_free_f,
 442       dict_elm_mallocator_reset_f);
 443 }
 444
 445 /**
 446  * Destroy the dict mallocators.
 447  * This is an internal XBT function during the lib initialization
 448  */
 449 void xbt_dict_postexit()
 450 {
 451   if (dict_elm_mallocator != nullptr) {
 452     xbt_mallocator_free(dict_elm_mallocator);
 453     dict_elm_mallocator = nullptr;
 454   }
 455 }
 456
 457 #ifdef SIMGRID_TEST
 458 #include "src/internal_config.h"
 459 #include "xbt.h"
 460 #include "xbt/ex.h"
 461 #include <ctime>
 462 #include <xbt/ex.hpp>
 463
 464 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(xbt_dict);
 465
 466 XBT_TEST_SUITE("dict", "Dict data container");
 467
 468 static void debugged_add_ext(xbt_dict_t head, const char* key, const char* data_to_fill)
 469 {
 470   char *data = xbt_strdup(data_to_fill);
 471
 472   xbt_test_log("Add %s under %s", data_to_fill, key);
 473
 474   xbt_dict_set(head, key, data, nullptr);
 475   if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) {
 476     xbt_dict_dump(head, [](void* s) { fputs((char*)s, stdout); });
 477     fflush(stdout);
 478   }
 479 }
 480
 481 static void debugged_add(xbt_dict_t head, const char* key)
 482 {
 483   debugged_add_ext(head, key, key);
 484 }
 485
 486 static xbt_dict_t new_fixture()
 487 {
 488   xbt_test_add("Fill in the dictionnary");
 489
 490   xbt_dict_t head = xbt_dict_new_homogeneous(&free);
 491   debugged_add(head, "12");
 492   debugged_add(head, "12a");
 493   debugged_add(head, "12b");
 494   debugged_add(head, "123");
 495   debugged_add(head, "123456");
 496   debugged_add(head, "1234");
 497   debugged_add(head, "123457");
 498
 499   return head;
 500 }
 501
 502 static void search_ext(xbt_dict_t head, const char *key, const char *data)
 503 {
 504   xbt_test_add("Search %s", key);
 505   char *found = (char*) xbt_dict_get(head, key);
 506   xbt_test_log("Found %s", found);
 507   if (data) {
 508     xbt_test_assert(found, "data do not match expectations: found nullptr while searching for %s", data);
 509     if (found)
 510       xbt_test_assert(not strcmp(data, found), "data do not match expectations: found %s while searching for %s", found,
 511                       data);
 512   } else {
 513     xbt_test_assert(not found, "data do not match expectations: found %s while searching for nullptr", found);
 514   }
 515 }
 516
 517 static void search(xbt_dict_t head, const char *key)
 518 {
 519   search_ext(head, key, key);
 520 }
 521
 522 static void debugged_remove(xbt_dict_t head, const char* key)
 523 {
 524   xbt_test_add("Remove '%s'", key);
 525   xbt_dict_remove(head, key);
 526 }
 527
 528 static void traverse(xbt_dict_t head)
 529 {
 530   xbt_dict_cursor_t cursor = nullptr;
 531   char *key;
 532   char *data;
 533   int i = 0;
 534
 535   xbt_dict_foreach(head, cursor, key, data) {
 536     if (not key || not data || strcmp(key, data)) {
 537       xbt_test_log("Seen #%d:  %s->%s", ++i, key, data);
 538     } else {
 539       xbt_test_log("Seen #%d:  %s", ++i, key);
 540     }
 541     xbt_test_assert(key && data && strcmp(key, data) == 0, "Key(%s) != value(%s). Aborting", key, data);
 542   }
 543 }
 544
 545 static void search_not_found(xbt_dict_t head, const char *data)
 546 {
 547   int ok = 0;
 548   xbt_test_add("Search %s (expected not to be found)", data);
 549
 550   try {
 551     data = (const char*) xbt_dict_get(head, data);
 552     THROWF(unknown_error, 0, "Found something which shouldn't be there (%s)", data);
 553   }
 554   catch(xbt_ex& e) {
 555     if (e.category != not_found_error)
 556       xbt_test_exception(e);
 557     ok = 1;
 558   }
 559   xbt_test_assert(ok, "Exception not raised");
 560 }
 561
 562 static void count(xbt_dict_t dict, int length)
 563 {
 564   xbt_test_add("Count elements (expecting %d)", length);
 565   xbt_test_assert(xbt_dict_length(dict) == length, "Announced length(%d) != %d.", xbt_dict_length(dict), length);
 566
 567   xbt_dict_cursor_t cursor;
 568   char *key;
 569   void *data;
 570   int effective = 0;
 571   xbt_dict_foreach(dict, cursor, key, data)
 572       effective++;
 573
 574   xbt_test_assert(effective == length, "Effective length(%d) != %d.", effective, length);
 575 }
 576
 577 static void count_check_get_key(xbt_dict_t dict, int length)
 578 {
 579   xbt_dict_cursor_t cursor;
 580   char *key;
 581   void *data;
 582   int effective = 0;
 583
 584   xbt_test_add("Count elements (expecting %d), and test the getkey function", length);
 585   xbt_test_assert(xbt_dict_length(dict) == length, "Announced length(%d) != %d.", xbt_dict_length(dict), length);
 586
 587   xbt_dict_foreach(dict, cursor, key, data) {
 588     effective++;
 589     char* key2 = xbt_dict_get_key(dict, data);
 590     xbt_assert(not strcmp(key, key2), "The data was registered under %s instead of %s as expected", key2, key);
 591   }
 592
 593   xbt_test_assert(effective == length, "Effective length(%d) != %d.", effective, length);
 594 }
 595
 596 XBT_TEST_UNIT("basic", test_dict_basic, "Basic usage: change, retrieve and traverse homogeneous dicts")
 597 {
 598   xbt_test_add("Traversal the null dictionary");
 599   traverse(nullptr);
 600
 601   xbt_test_add("Traversal and search the empty dictionary");
 602   xbt_dict_t head = xbt_dict_new_homogeneous(&free);
 603   traverse(head);
 604   try {
 605     debugged_remove(head, "12346");
 606   }
 607   catch(xbt_ex& e) {
 608     if (e.category != not_found_error)
 609       xbt_test_exception(e);
 610   }
 611   xbt_dict_free(&head);
 612
 613   xbt_test_add("Traverse the full dictionary");
 614   head = new_fixture();
 615   count_check_get_key(head, 7);
 616
 617   debugged_add_ext(head, "toto", "tutu");
 618   search_ext(head, "toto", "tutu");
 619   debugged_remove(head, "toto");
 620
 621   search(head, "12a");
 622   traverse(head);
 623
 624   xbt_test_add("Free the dictionary (twice)");
 625   xbt_dict_free(&head);
 626   xbt_dict_free(&head);
 627
 628   /* CHANGING */
 629   head = new_fixture();
 630   count_check_get_key(head, 7);
 631   xbt_test_add("Change 123 to 'Changed 123'");
 632   xbt_dict_set(head, "123", xbt_strdup("Changed 123"), nullptr);
 633   count_check_get_key(head, 7);
 634
 635   xbt_test_add("Change 123 back to '123'");
 636   xbt_dict_set(head, "123", xbt_strdup("123"), nullptr);
 637   count_check_get_key(head, 7);
 638
 639   xbt_test_add("Change 12a to 'Dummy 12a'");
 640   xbt_dict_set(head, "12a", xbt_strdup("Dummy 12a"), nullptr);
 641   count_check_get_key(head, 7);
 642
 643   xbt_test_add("Change 12a to '12a'");
 644   xbt_dict_set(head, "12a", xbt_strdup("12a"), nullptr);
 645   count_check_get_key(head, 7);
 646
 647   xbt_test_add("Traverse the resulting dictionary");
 648   traverse(head);
 649
 650   /* RETRIEVE */
 651   xbt_test_add("Search 123");
 652   char* data = (char*)xbt_dict_get(head, "123");
 653   xbt_test_assert(data && strcmp("123", data) == 0);
 654
 655   search_not_found(head, "Can't be found");
 656   search_not_found(head, "123 Can't be found");
 657   search_not_found(head, "12345678 NOT");
 658
 659   search(head, "12a");
 660   search(head, "12b");
 661   search(head, "12");
 662   search(head, "123456");
 663   search(head, "1234");
 664   search(head, "123457");
 665
 666   xbt_test_add("Traverse the resulting dictionary");
 667   traverse(head);
 668
 669   xbt_test_add("Free the dictionary twice");
 670   xbt_dict_free(&head);
 671   xbt_dict_free(&head);
 672
 673   xbt_test_add("Traverse the resulting dictionary");
 674   traverse(head);
 675 }
 676
 677 XBT_TEST_UNIT("remove_homogeneous", test_dict_remove, "Removing some values from homogeneous dicts")
 678 {
 679   xbt_dict_t head = new_fixture();
 680   count(head, 7);
 681   xbt_test_add("Remove non existing data");
 682   try {
 683     debugged_remove(head, "Does not exist");
 684   }
 685   catch(xbt_ex& e) {
 686     if (e.category != not_found_error)
 687       xbt_test_exception(e);
 688   }
 689   traverse(head);
 690
 691   xbt_dict_free(&head);
 692
 693   xbt_test_add("Remove each data manually (traversing the resulting dictionary each time)");
 694   head = new_fixture();
 695   debugged_remove(head, "12a");
 696   traverse(head);
 697   count(head, 6);
 698   debugged_remove(head, "12b");
 699   traverse(head);
 700   count(head, 5);
 701   debugged_remove(head, "12");
 702   traverse(head);
 703   count(head, 4);
 704   debugged_remove(head, "123456");
 705   traverse(head);
 706   count(head, 3);
 707   try {
 708     debugged_remove(head, "12346");
 709   }
 710   catch(xbt_ex& e) {
 711     if (e.category != not_found_error)
 712       xbt_test_exception(e);
 713     traverse(head);
 714   }
 715   debugged_remove(head, "1234");
 716   traverse(head);
 717   debugged_remove(head, "123457");
 718   traverse(head);
 719   debugged_remove(head, "123");
 720   traverse(head);
 721   try {
 722     debugged_remove(head, "12346");
 723   }
 724   catch(xbt_ex& e) {
 725     if (e.category != not_found_error)
 726       xbt_test_exception(e);
 727   }
 728   traverse(head);
 729
 730   xbt_test_add("Free dict, create new fresh one, and then reset the dict");
 731   xbt_dict_free(&head);
 732   head = new_fixture();
 733   xbt_dict_reset(head);
 734   count(head, 0);
 735   traverse(head);
 736
 737   xbt_test_add("Free the dictionary twice");
 738   xbt_dict_free(&head);
 739   xbt_dict_free(&head);
 740 }
 741
 742 XBT_TEST_UNIT("nulldata", test_dict_nulldata, "nullptr data management")
 743 {
 744   xbt_dict_t head = new_fixture();
 745
 746   xbt_test_add("Store nullptr under 'null'");
 747   xbt_dict_set(head, "null", nullptr, nullptr);
 748   search_ext(head, "null", nullptr);
 749
 750   xbt_test_add("Check whether I see it while traversing...");
 751   {
 752     xbt_dict_cursor_t cursor = nullptr;
 753     char *key;
 754     int found = 0;
 755     char* data;
 756
 757     xbt_dict_foreach(head, cursor, key, data) {
 758       if (not key || not data || strcmp(key, data)) {
 759         xbt_test_log("Seen:  %s->%s", key, data);
 760       } else {
 761         xbt_test_log("Seen:  %s", key);
 762       }
 763
 764       if (key && strcmp(key, "null") == 0)
 765         found = 1;
 766     }
 767     xbt_test_assert(found, "the key 'null', associated to nullptr is not found");
 768   }
 769   xbt_dict_free(&head);
 770 }
 771
 772 #define NB_ELM 20000
 773 #define SIZEOFKEY 1024
 774 static int countelems(xbt_dict_t head)
 775 {
 776   xbt_dict_cursor_t cursor;
 777   char *key;
 778   void *data;
 779   int res = 0;
 780
 781   xbt_dict_foreach(head, cursor, key, data) {
 782     res++;
 783   }
 784   return res;
 785 }
 786
 787 XBT_TEST_UNIT("crash", test_dict_crash, "Crash test")
 788 {
 789   srand((unsigned int) time(nullptr));
 790
 791   for (int i = 0; i < 10; i++) {
 792     xbt_test_add("CRASH test number %d (%d to go)", i + 1, 10 - i - 1);
 793     xbt_test_log("Fill the struct, count its elems and frees the structure");
 794     xbt_test_log("using 1000 elements with %d chars long randomized keys.", SIZEOFKEY);
 795     xbt_dict_t head = xbt_dict_new_homogeneous(free);
 796     for (int j = 0; j < 1000; j++) {
 797       char* data = nullptr;
 798       char* key  = (char*)xbt_malloc(SIZEOFKEY);
 799
 800       do {
 801         for (int k         = 0; k < SIZEOFKEY - 1; k++)
 802           key[k] = rand() % ('z' - 'a') + 'a';
 803         key[SIZEOFKEY - 1] = '\0';
 804         data = (char*) xbt_dict_get_or_null(head, key);
 805       } while (data != nullptr);
 806
 807       xbt_dict_set(head, key, key, nullptr);
 808       data = (char*) xbt_dict_get(head, key);
 809       xbt_test_assert(not strcmp(key, data), "Retrieved value (%s) != Injected value (%s)", key, data);
 810
 811       count(head, j + 1);
 812     }
 813     traverse(head);
 814     xbt_dict_free(&head);
 815     xbt_dict_free(&head);
 816   }
 817
 818   xbt_dict_t head = xbt_dict_new_homogeneous(&free);
 819   xbt_test_add("Fill %d elements, with keys being the number of element", NB_ELM);
 820   for (int j = 0; j < NB_ELM; j++) {
 821     char* key = (char*)xbt_malloc(10);
 822
 823     snprintf(key,10, "%d", j);
 824     xbt_dict_set(head, key, key, nullptr);
 825   }
 826
 827   xbt_test_add("Count the elements (retrieving the key and data for each)");
 828   xbt_test_log("There is %d elements", countelems(head));
 829
 830   xbt_test_add("Search my %d elements 20 times", NB_ELM);
 831   char* key = (char*)xbt_malloc(10);
 832   for (int i = 0; i < 20; i++) {
 833     for (int j = 0; j < NB_ELM; j++) {
 834       snprintf(key,10, "%d", j);
 835       void* data = xbt_dict_get(head, key);
 836       xbt_test_assert(not strcmp(key, (char*)data), "with get, key=%s != data=%s", key, (char*)data);
 837       data = xbt_dict_get_ext(head, key, strlen(key));
 838       xbt_test_assert(not strcmp(key, (char*)data), "with get_ext, key=%s != data=%s", key, (char*)data);
 839     }
 840   }
 841   free(key);
 842
 843   xbt_test_add("Remove my %d elements", NB_ELM);
 844   key = (char*) xbt_malloc(10);
 845   for (int j = 0; j < NB_ELM; j++) {
 846     snprintf(key,10, "%d", j);
 847     xbt_dict_remove(head, key);
 848   }
 849   free(key);
 850
 851   xbt_test_add("Free the object (twice)");
 852   xbt_dict_free(&head);
 853   xbt_dict_free(&head);
 854 }
 855
 856 XBT_TEST_UNIT("ext", test_dict_int, "Test dictionnary with int keys")
 857 {
 858   xbt_dict_t dict = xbt_dict_new_homogeneous(nullptr);
 859   int count = 500;
 860
 861   xbt_test_add("Insert elements");
 862   for (int i = 0; i < count; ++i)
 863     xbt_dict_set_ext(dict, (char*) &i, sizeof(i), (void*) (intptr_t) i, nullptr);
 864   xbt_test_assert(xbt_dict_size(dict) == (unsigned) count, "Bad number of elements in the dictionnary");
 865
 866   xbt_test_add("Check elements");
 867   for (int i = 0; i < count; ++i) {
 868     int res = (int) (intptr_t) xbt_dict_get_ext(dict, (char*) &i, sizeof(i));
 869     xbt_test_assert(xbt_dict_size(dict) == (unsigned) count, "Unexpected value at index %i, expected %i but was %i", i, i, res);
 870   }
 871
 872   xbt_test_add("Free the array");
 873   xbt_dict_free(&dict);
 874 }
 875 #endif                          /* SIMGRID_TEST */