src/xbt/dict.c

   1 /* dict - a generic dictionary, variation over hash table                   */
   2
   3 /* Copyright (c) 2004-2011. 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 #define DJB2_HASH_FUNCTION
  10 //#define FNV_HASH_FUNCTION
  11
  12 #include <string.h>
  13 #include <stdio.h>
  14 #include "xbt/ex.h"
  15 #include "xbt/log.h"
  16 #include "xbt/mallocator.h"
  17 #include "xbt_modinter.h"
  18 #include "dict_private.h"
  19
  20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict, xbt,
  21                                 "Dictionaries provide the same functionalities than hash tables");
  22
  23 /**
  24  * \brief Constructor
  25  * \return pointer to the destination
  26  * \see xbt_dict_free()
  27  *
  28  * Creates and initialize a new dictionary with a default hashtable size.
  29  */
  30 xbt_dict_t xbt_dict_new(void)
  31 {
  32   xbt_dict_t dict;
  33
  34   dict = xbt_new(s_xbt_dict_t, 1);
  35   dict->table_size = 127;
  36   dict->table = xbt_new0(xbt_dictelm_t, dict->table_size + 1);
  37   dict->count = 0;
  38   dict->fill = 0;
  39
  40   return dict;
  41 }
  42
  43 /**
  44  * \brief Destructor
  45  * \param dict the dictionary to be freed
  46  *
  47  * Frees a dictionary with all the data
  48  */
  49 void xbt_dict_free(xbt_dict_t * dict)
  50 {
  51   int i;
  52   xbt_dictelm_t current, previous;
  53   int table_size;
  54   xbt_dictelm_t *table;
  55
  56   //  if ( *dict )  xbt_dict_dump_sizes(*dict);
  57
  58   if (dict != NULL && *dict != NULL) {
  59     table_size = (*dict)->table_size;
  60     table = (*dict)->table;
  61     /* Warning: the size of the table is 'table_size+1'...
  62      * This is because table_size is used as a binary mask in xbt_dict_rehash */
  63     for (i = 0; (*dict)->count && i <= table_size; i++) {
  64       current = table[i];
  65       while (current != NULL) {
  66         previous = current;
  67         current = current->next;
  68         xbt_dictelm_free(previous);
  69         (*dict)->count--;
  70       }
  71     }
  72     xbt_free(table);
  73     xbt_free(*dict);
  74     *dict = NULL;
  75   }
  76 }
  77
  78 /**
  79  * Returns the amount of elements in the dict
  80  */
  81 XBT_INLINE unsigned int xbt_dict_size(xbt_dict_t dict)
  82 {
  83   return (dict ? (unsigned int) dict->count : (unsigned int) 0);
  84 }
  85
  86 /**
  87  * Returns the hash code of a string.
  88  */
  89 static XBT_INLINE unsigned int xbt_dict_hash_ext(const char *str,
  90                                                  int str_len)
  91 {
  92
  93
  94 #ifdef DJB2_HASH_FUNCTION
  95   /* fast implementation of djb2 algorithm */
  96   int c;
  97   register unsigned int hash = 5381;
  98
  99   while (str_len--) {
 100     c = *str++;
 101     hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
 102   }
 103 # elif defined(FNV_HASH_FUNCTION)
 104   register unsigned int hash = 0x811c9dc5;
 105   unsigned char *bp = (unsigned char *) str;    /* start of buffer */
 106   unsigned char *be = bp + str_len;     /* beyond end of buffer */
 107
 108   while (bp < be) {
 109     /* multiply by the 32 bit FNV magic prime mod 2^32 */
 110     hash +=
 111         (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
 112         (hash << 24);
 113
 114     /* xor the bottom with the current octet */
 115     hash ^= (unsigned int) *bp++;
 116   }
 117
 118 # else
 119   register unsigned int hash = 0;
 120
 121   while (str_len--) {
 122     hash += (*str) * (*str);
 123     str++;
 124   }
 125 #endif
 126
 127   return hash;
 128 }
 129
 130 static XBT_INLINE unsigned int xbt_dict_hash(const char *str)
 131 {
 132 #ifdef DJB2_HASH_FUNCTION
 133   /* fast implementation of djb2 algorithm */
 134   int c;
 135   register unsigned int hash = 5381;
 136
 137   while ((c = *str++)) {
 138     hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
 139   }
 140
 141 # elif defined(FNV_HASH_FUNCTION)
 142   register unsigned int hash = 0x811c9dc5;
 143
 144   while (*str) {
 145     /* multiply by the 32 bit FNV magic prime mod 2^32 */
 146     hash +=
 147         (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) +
 148         (hash << 24);
 149
 150     /* xor the bottom with the current byte */
 151     hash ^= (unsigned int) *str++;
 152   }
 153
 154 # else
 155   register unsigned int hash = 0;
 156
 157   while (*str) {
 158     hash += (*str) * (*str);
 159     str++;
 160   }
 161 #endif
 162   return hash;
 163 }
 164
 165 /* Expend the size of the dict */
 166 static void xbt_dict_rehash(xbt_dict_t dict)
 167 {
 168   const int oldsize = dict->table_size + 1;
 169   register int newsize = oldsize * 2;
 170   register int i;
 171   register xbt_dictelm_t *currcell;
 172   register xbt_dictelm_t *twincell;
 173   register xbt_dictelm_t bucklet;
 174   register xbt_dictelm_t *pprev;
 175
 176   currcell =
 177       (xbt_dictelm_t *) xbt_realloc((char *) dict->table,
 178                                     newsize * sizeof(xbt_dictelm_t));
 179   memset(&currcell[oldsize], 0, oldsize * sizeof(xbt_dictelm_t));       /* zero second half */
 180   dict->table_size = --newsize;
 181   dict->table = currcell;
 182   XBT_DEBUG("REHASH (%d->%d)", oldsize, newsize);
 183
 184   for (i = 0; i < oldsize; i++, currcell++) {
 185     if (!*currcell)             /* empty cell */
 186       continue;
 187     twincell = currcell + oldsize;
 188     for (pprev = currcell, bucklet = *currcell; bucklet; bucklet = *pprev) {
 189       /* Since we use "& size" instead of "%size" and since the size was doubled,
 190          each bucklet of this cell must either :
 191          - stay  in  cell i (ie, currcell)
 192          - go to the cell i+oldsize (ie, twincell) */
 193       if ((bucklet->hash_code & newsize) != i) {        /* Move to b */
 194         *pprev = bucklet->next;
 195         bucklet->next = *twincell;
 196         if (!*twincell)
 197           dict->fill++;
 198         *twincell = bucklet;
 199         continue;
 200       } else {
 201         pprev = &bucklet->next;
 202       }
 203
 204     }
 205
 206     if (!*currcell)             /* everything moved */
 207       dict->fill--;
 208   }
 209 }
 210
 211 /**
 212  * \brief Add data to the dict (arbitrary key)
 213  * \param dict the container
 214  * \param key the key to set the new data
 215  * \param key_len the size of the \a key
 216  * \param data the data to add in the dict
 217  * \param free_ctn function to call with (\a data as argument) when
 218  *        \a data is removed from the dictionary
 219  *
 220  * Set the \a data in the structure under the \a key, which can be any kind
 221  * of data, as long as its length is provided in \a key_len.
 222  */
 223 XBT_INLINE void xbt_dict_set_ext(xbt_dict_t dict,
 224                                  const char *key, int key_len,
 225                                  void *data, void_f_pvoid_t free_ctn)
 226 {
 227
 228   unsigned int hash_code = xbt_dict_hash_ext(key, key_len);
 229
 230   xbt_dictelm_t current, previous = NULL;
 231   xbt_assert(dict);
 232
 233   XBT_DEBUG("ADD %.*s hash = %d, size = %d, & = %d", key_len, key, hash_code,
 234          dict->table_size, hash_code & dict->table_size);
 235   current = dict->table[hash_code & dict->table_size];
 236   while (current != NULL &&
 237          (hash_code != current->hash_code || key_len != current->key_len
 238           || memcmp(key, current->key, key_len))) {
 239     previous = current;
 240     current = current->next;
 241   }
 242
 243   if (current == NULL) {
 244     /* this key doesn't exist yet */
 245     current = xbt_dictelm_new(key, key_len, hash_code, data, free_ctn);
 246     dict->count++;
 247     if (previous == NULL) {
 248       dict->table[hash_code & dict->table_size] = current;
 249       dict->fill++;
 250       if ((dict->fill * 100) / (dict->table_size + 1) > MAX_FILL_PERCENT)
 251         xbt_dict_rehash(dict);
 252     } else {
 253       previous->next = current;
 254     }
 255   } else {
 256
 257     XBT_DEBUG("Replace %.*s by %.*s under key %.*s",
 258            key_len, (char *) current->content,
 259            key_len, (char *) data, key_len, (char *) key);
 260     /* there is already an element with the same key: overwrite it */
 261     if (current->content != NULL && current->free_f != NULL) {
 262       current->free_f(current->content);
 263     }
 264     current->content = data;
 265     current->free_f = free_ctn;
 266   }
 267 }
 268
 269 /**
 270  * \brief Add data to the dict (null-terminated key)
 271  *
 272  * \param dict the dict
 273  * \param key the key to set the new data
 274  * \param data the data to add in the dict
 275  * \param free_ctn function to call with (\a data as argument) when
 276  *        \a data is removed from the dictionary
 277  *
 278  * set the \a data in the structure under the \a key, which is a
 279  * null terminated string.
 280  */
 281 XBT_INLINE void xbt_dict_set(xbt_dict_t dict,
 282                              const char *key, void *data,
 283                              void_f_pvoid_t free_ctn)
 284 {
 285
 286   xbt_dict_set_ext(dict, key, strlen(key), data, free_ctn);
 287 }
 288
 289 /**
 290  * \brief Retrieve data from the dict (arbitrary key)
 291  *
 292  * \param dict the dealer of data
 293  * \param key the key to find data
 294  * \param key_len the size of the \a key
 295  * \return the data that we are looking for
 296  *
 297  * Search the given \a key. Throws not_found_error when not found.
 298  */
 299 XBT_INLINE void *xbt_dict_get_ext(xbt_dict_t dict, const char *key,
 300                                   int key_len)
 301 {
 302
 303
 304   unsigned int hash_code = xbt_dict_hash_ext(key, key_len);
 305   xbt_dictelm_t current;
 306
 307   xbt_assert(dict);
 308
 309   current = dict->table[hash_code & dict->table_size];
 310   while (current != NULL &&
 311          (hash_code != current->hash_code || key_len != current->key_len
 312           || memcmp(key, current->key, key_len))) {
 313     current = current->next;
 314   }
 315
 316   if (current == NULL)
 317     THROWF(not_found_error, 0, "key %.*s not found", key_len, key);
 318
 319   return current->content;
 320 }
 321
 322 /**
 323  * \brief like xbt_dict_get_ext(), but returning NULL when not found
 324  */
 325 void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key,
 326                                int key_len)
 327 {
 328
 329   unsigned int hash_code = xbt_dict_hash_ext(key, key_len);
 330   xbt_dictelm_t current;
 331
 332   xbt_assert(dict);
 333
 334   current = dict->table[hash_code & dict->table_size];
 335   while (current != NULL &&
 336          (hash_code != current->hash_code || key_len != current->key_len
 337           || memcmp(key, current->key, key_len))) {
 338     current = current->next;
 339   }
 340
 341   if (current == NULL)
 342     return NULL;
 343
 344   return current->content;
 345 }
 346
 347 /**
 348  * @brief retrieve the key associated to that object. Warning, that's a linear search
 349  *
 350  * Returns NULL if the object cannot be found
 351  */
 352 char *xbt_dict_get_key(xbt_dict_t dict, const void *data)
 353 {
 354   int i;
 355   xbt_dictelm_t current;
 356
 357
 358   for (i = 0; i <= dict->table_size; i++) {
 359     current = dict->table[i];
 360     while (current != NULL) {
 361       if (current->content == data)
 362         return current->key;
 363       current = current->next;
 364     }
 365   }
 366
 367   return NULL;
 368 }
 369
 370 /**
 371  * \brief Retrieve data from the dict (null-terminated key)
 372  *
 373  * \param dict the dealer of data
 374  * \param key the key to find data
 375  * \return the data that we are looking for
 376  *
 377  * Search the given \a key. Throws not_found_error when not found.
 378  * Check xbt_dict_get_or_null() for a version returning NULL without exception when
 379  * not found.
 380  */
 381 XBT_INLINE void *xbt_dict_get(xbt_dict_t dict, const char *key)
 382 {
 383
 384   unsigned int hash_code = xbt_dict_hash(key);
 385   xbt_dictelm_t current;
 386
 387   xbt_assert(dict);
 388
 389   current = dict->table[hash_code & dict->table_size];
 390   while (current != NULL
 391          && (hash_code != current->hash_code || strcmp(key, current->key)))
 392     current = current->next;
 393
 394   if (current == NULL)
 395     THROWF(not_found_error, 0, "key %s not found", key);
 396
 397   return current->content;
 398 }
 399
 400 /**
 401  * \brief like xbt_dict_get(), but returning NULL when not found
 402  */
 403 XBT_INLINE void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key)
 404 {
 405   unsigned int hash_code = xbt_dict_hash(key);
 406   xbt_dictelm_t current;
 407
 408   xbt_assert(dict);
 409
 410   current = dict->table[hash_code & dict->table_size];
 411   while (current != NULL &&
 412          (hash_code != current->hash_code || strcmp(key, current->key)))
 413     current = current->next;
 414
 415   if (current == NULL)
 416     return NULL;
 417
 418   return current->content;
 419 }
 420
 421
 422 /**
 423  * \brief Remove data from the dict (arbitrary key)
 424  *
 425  * \param dict the trash can
 426  * \param key the key of the data to be removed
 427  * \param key_len the size of the \a key
 428  *
 429  * Remove the entry associated with the given \a key (throws not_found)
 430  */
 431 XBT_INLINE void xbt_dict_remove_ext(xbt_dict_t dict, const char *key,
 432                                     int key_len)
 433 {
 434
 435
 436   unsigned int hash_code = xbt_dict_hash_ext(key, key_len);
 437   xbt_dictelm_t current, previous = NULL;
 438
 439   xbt_assert(dict);
 440
 441   //  fprintf(stderr,"RM %.*s hash = %d, size = %d, & = %d\n",key_len,key,hash_code, dict->table_size, hash_code & dict->table_size);
 442   current = dict->table[hash_code & dict->table_size];
 443   while (current != NULL &&
 444          (hash_code != current->hash_code || key_len != current->key_len
 445           || strncmp(key, current->key, key_len))) {
 446     previous = current;         /* save the previous node */
 447     current = current->next;
 448   }
 449
 450   if (current == NULL)
 451     THROWF(not_found_error, 0, "key %.*s not found", key_len, key);
 452
 453   if (previous != NULL) {
 454     previous->next = current->next;
 455   } else {
 456     dict->table[hash_code & dict->table_size] = current->next;
 457   }
 458
 459   if (!dict->table[hash_code & dict->table_size])
 460     dict->fill--;
 461
 462   xbt_dictelm_free(current);
 463   dict->count--;
 464 }
 465
 466
 467
 468 /**
 469  * \brief Remove data from the dict (null-terminated key)
 470  *
 471  * \param dict the dict
 472  * \param key the key of the data to be removed
 473  *
 474  * Remove the entry associated with the given \a key
 475  */
 476 XBT_INLINE void xbt_dict_remove(xbt_dict_t dict, const char *key)
 477 {
 478   xbt_dict_remove_ext(dict, key, strlen(key));
 479 }
 480
 481 /**
 482  * \brief Add data to the dict (arbitrary key)
 483  * \param dict the container
 484  * \param key the key to set the new data
 485  * \param data the data to add in the dict
 486  *
 487  * Set the \a data in the structure under the \a key.
 488  * Both \a data and \a key are considered as uintptr_t.
 489  */
 490 XBT_INLINE void xbt_dicti_set(xbt_dict_t dict,
 491                               uintptr_t key, uintptr_t data)
 492 {
 493
 494   unsigned int hash_code =
 495       xbt_dict_hash_ext((void *) &key, sizeof(uintptr_t));
 496
 497   xbt_dictelm_t current, previous = NULL;
 498   xbt_assert(dict);
 499
 500   XBT_DEBUG("ADD %zu->%zu; hash = %d, size = %d, & = %d", key, data,
 501          hash_code, dict->table_size, hash_code & dict->table_size);
 502   current = dict->table[hash_code & dict->table_size];
 503   while (current != NULL &&
 504          (hash_code != current->hash_code
 505           || sizeof(uintptr_t) != current->key_len
 506           || (((uintptr_t) key) != ((uintptr_t) current->key)))) {
 507     previous = current;
 508     current = current->next;
 509   }
 510
 511   if (current == NULL) {
 512     /* this key doesn't exist yet */
 513     current = xbt_dictielm_new(key, hash_code, data);
 514     dict->count++;
 515     if (previous == NULL) {
 516       dict->table[hash_code & dict->table_size] = current;
 517       dict->fill++;
 518       if ((dict->fill * 100) / (dict->table_size + 1) > MAX_FILL_PERCENT)
 519         xbt_dict_rehash(dict);
 520     } else {
 521       previous->next = current;
 522     }
 523   } else {
 524
 525     /* there is already an element with the same key: overwrite it */
 526     if (current->content != NULL && current->free_f != NULL) {
 527       current->free_f(current->content);
 528     }
 529     current->content = (void *) data;
 530     current->free_f = NULL;
 531   }
 532 }
 533
 534 /**
 535  * \brief Retrieve data from the dict (key considered as a uintptr_t)
 536  *
 537  * \param dict the dealer of data
 538  * \param key the key to find data
 539  * \return the data that we are looking for (or 0 if not found)
 540  *
 541  * Mixing uintptr_t keys with regular keys in the same dict is discouraged
 542  */
 543 XBT_INLINE uintptr_t xbt_dicti_get(xbt_dict_t dict, uintptr_t key)
 544 {
 545
 546   unsigned int hash_code =
 547       xbt_dict_hash_ext(((void *) &key), sizeof(uintptr_t));
 548   xbt_dictelm_t current;
 549
 550   xbt_assert(dict);
 551
 552   current = dict->table[hash_code & dict->table_size];
 553   while (current != NULL &&
 554          (hash_code != current->hash_code
 555           || sizeof(uintptr_t) != current->key_len
 556           || (((uintptr_t) key) != ((uintptr_t) current->key)))) {
 557     current = current->next;
 558   }
 559
 560   if (current == NULL)
 561     return 0;
 562
 563   return (uintptr_t) (current->content);
 564 }
 565
 566 /** Remove a uintptr_t key from the dict */
 567 XBT_INLINE void xbt_dicti_remove(xbt_dict_t dict, uintptr_t key)
 568 {
 569
 570   unsigned int hash_code =
 571       xbt_dict_hash_ext(((void *) &key), sizeof(uintptr_t));
 572   xbt_dictelm_t current, previous = NULL;
 573
 574
 575   current = dict->table[hash_code & dict->table_size];
 576   while (current != NULL &&
 577          (hash_code != current->hash_code
 578           || sizeof(uintptr_t) != current->key_len
 579           || (((uintptr_t) key) != ((uintptr_t) current->key)))) {
 580     previous = current;         /* save the previous node */
 581     current = current->next;
 582   }
 583
 584   if (current == NULL)
 585     THROWF(not_found_error, 0, "key %zu not found", key);
 586
 587   if (previous != NULL) {
 588     previous->next = current->next;
 589   } else {
 590     dict->table[hash_code & dict->table_size] = current->next;
 591   }
 592
 593   if (!dict->table[hash_code & dict->table_size])
 594     dict->fill--;
 595
 596   xbt_dictelm_free(current);
 597   dict->count--;
 598 }
 599
 600
 601 /**
 602  * \brief Remove all data from the dict
 603  * \param dict the dict
 604  */
 605 void xbt_dict_reset(xbt_dict_t dict)
 606 {
 607
 608   int i;
 609   xbt_dictelm_t current, previous = NULL;
 610
 611   xbt_assert(dict);
 612
 613   if (dict->count == 0)
 614     return;
 615
 616   for (i = 0; i <= dict->table_size; i++) {
 617     current = dict->table[i];
 618     while (current != NULL) {
 619       previous = current;
 620       current = current->next;
 621       xbt_dictelm_free(previous);
 622     }
 623     dict->table[i] = NULL;
 624   }
 625
 626   dict->count = 0;
 627   dict->fill = 0;
 628 }
 629
 630 /**
 631  * \brief Return the number of elements in the dict.
 632  * \param dict a dictionary
 633  */
 634 XBT_INLINE int xbt_dict_length(xbt_dict_t dict)
 635 {
 636   xbt_assert(dict);
 637
 638   return dict->count;
 639 }
 640
 641 /** @brief function to be used in xbt_dict_dump as long as the stored values are strings */
 642 void xbt_dict_dump_output_string(void *s)
 643 {
 644   fputs(s, stdout);
 645 }
 646
 647 /**
 648  * \brief test if the dict is empty or not
 649  */
 650 XBT_INLINE int xbt_dict_is_empty(xbt_dict_t dict)
 651 {
 652   return !dict || (xbt_dict_length(dict) == 0);
 653 }
 654
 655 /**
 656  * \brief Outputs the content of the structure (debugging purpose)
 657  *
 658  * \param dict the exibitionist
 659  * \param output a function to dump each data in the tree (check @ref xbt_dict_dump_output_string)
 660  *
 661  * Outputs the content of the structure. (for debugging purpose). \a output is a
 662  * function to output the data. If NULL, data won't be displayed.
 663  */
 664
 665 void xbt_dict_dump(xbt_dict_t dict, void_f_pvoid_t output)
 666 {
 667   int i;
 668   xbt_dictelm_t element;
 669   printf("Dict %p:\n", dict);
 670   if (dict != NULL) {
 671     for (i = 0; i < dict->table_size; i++) {
 672       element = dict->table[i];
 673       if (element) {
 674         printf("[\n");
 675         while (element != NULL) {
 676           printf(" %s -> '", element->key);
 677           if (output != NULL) {
 678             output(element->content);
 679           }
 680           printf("'\n");
 681           element = element->next;
 682         }
 683         printf("]\n");
 684       } else {
 685         printf("[]\n");
 686       }
 687     }
 688   }
 689 }
 690
 691 xbt_dynar_t all_sizes = NULL;
 692 /** @brief shows some debugging info about the bucklet repartition */
 693 void xbt_dict_dump_sizes(xbt_dict_t dict)
 694 {
 695
 696   int i;
 697   unsigned int count;
 698   unsigned int size;
 699   xbt_dictelm_t element;
 700   xbt_dynar_t sizes = xbt_dynar_new(sizeof(int), NULL);
 701
 702   printf("Dict %p: %d bucklets, %d used cells (of %d) ", dict, dict->count,
 703          dict->fill, dict->table_size);
 704   if (dict != NULL) {
 705     for (i = 0; i < dict->table_size; i++) {
 706       element = dict->table[i];
 707       size = 0;
 708       if (element) {
 709         while (element != NULL) {
 710           size++;
 711           element = element->next;
 712         }
 713       }
 714       if (xbt_dynar_length(sizes) <= size) {
 715         int prevsize = 1;
 716         xbt_dynar_set(sizes, size, &prevsize);
 717       } else {
 718         int prevsize;
 719         xbt_dynar_get_cpy(sizes, size, &prevsize);
 720         prevsize++;
 721         xbt_dynar_set(sizes, size, &prevsize);
 722       }
 723     }
 724     if (!all_sizes)
 725       all_sizes = xbt_dynar_new(sizeof(int), NULL);
 726
 727     xbt_dynar_foreach(sizes, count, size) {
 728       /* Copy values of this one into all_sizes */
 729       int prevcount;
 730       if (xbt_dynar_length(all_sizes) <= count) {
 731         prevcount = size;
 732         xbt_dynar_set(all_sizes, count, &prevcount);
 733       } else {
 734         xbt_dynar_get_cpy(all_sizes, count, &prevcount);
 735         prevcount += size;
 736         xbt_dynar_set(all_sizes, count, &prevcount);
 737       }
 738
 739       /* Report current sizes */
 740       if (count == 0)
 741         continue;
 742       if (size == 0)
 743         continue;
 744       printf("%delm x %u cells; ", count, size);
 745     }
 746   }
 747   printf("\n");
 748   xbt_dynar_free(&sizes);
 749 }
 750
 751 /**
 752  * Create the dict mallocators.
 753  * This is an internal XBT function called during the lib initialization.
 754  * It can be used several times to recreate the mallocator, for example when you switch to MC mode
 755  */
 756 void xbt_dict_preinit(void)
 757 {
 758   if (dict_elm_mallocator != NULL) {
 759     /* Already created. I guess we want to switch to MC mode, so kill the previously created mallocator */
 760     xbt_mallocator_free(dict_elm_mallocator);
 761   }
 762
 763   dict_elm_mallocator = xbt_mallocator_new(256,
 764                                            dict_elm_mallocator_new_f,
 765                                            dict_elm_mallocator_free_f,
 766                                            dict_elm_mallocator_reset_f);
 767 }
 768
 769 /**
 770  * Destroy the dict mallocators.
 771  * This is an internal XBT function during the lib initialization
 772  */
 773 void xbt_dict_postexit(void)
 774 {
 775   if (dict_elm_mallocator != NULL) {
 776     xbt_mallocator_free(dict_elm_mallocator);
 777     dict_elm_mallocator = NULL;
 778   }
 779   if (all_sizes) {
 780     unsigned int count;
 781     int size;
 782     double avg = 0;
 783     int total_count = 0;
 784     printf("Overall stats:");
 785     xbt_dynar_foreach(all_sizes, count, size) {
 786       if (count == 0)
 787         continue;
 788       if (size == 0)
 789         continue;
 790       printf("%delm x %d cells; ", count, size);
 791       avg += count * size;
 792       total_count += size;
 793     }
 794     printf("; %f elm per cell\n", avg / (double) total_count);
 795   }
 796 }
 797
 798 #ifdef SIMGRID_TEST
 799 #include "xbt.h"
 800 #include "xbt/ex.h"
 801 #include "portable.h"
 802
 803 XBT_LOG_EXTERNAL_CATEGORY(xbt_dict);
 804 XBT_LOG_DEFAULT_CATEGORY(xbt_dict);
 805
 806 XBT_TEST_SUITE("dict", "Dict data container");
 807
 808 static void print_str(void *str)
 809 {
 810   printf("%s", (char *) PRINTF_STR(str));
 811 }
 812
 813 static void debuged_add_ext(xbt_dict_t head, const char *key,
 814                             const char *data_to_fill)
 815 {
 816   char *data = xbt_strdup(data_to_fill);
 817
 818   xbt_test_log("Add %s under %s", PRINTF_STR(data_to_fill),
 819                 PRINTF_STR(key));
 820
 821   xbt_dict_set(head, key, data, &free);
 822   if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) {
 823     xbt_dict_dump(head, (void (*)(void *)) &printf);
 824     fflush(stdout);
 825   }
 826 }
 827
 828 static void debuged_add(xbt_dict_t head, const char *key)
 829 {
 830   debuged_add_ext(head, key, key);
 831 }
 832
 833 static void fill(xbt_dict_t * head)
 834 {
 835   xbt_test_add("Fill in the dictionnary");
 836
 837   *head = xbt_dict_new();
 838   debuged_add(*head, "12");
 839   debuged_add(*head, "12a");
 840   debuged_add(*head, "12b");
 841   debuged_add(*head, "123");
 842   debuged_add(*head, "123456");
 843   /* Child becomes child of what to add */
 844   debuged_add(*head, "1234");
 845   /* Need of common ancestor */
 846   debuged_add(*head, "123457");
 847 }
 848
 849
 850 static void search_ext(xbt_dict_t head, const char *key, const char *data)
 851 {
 852   void *found;
 853
 854   xbt_test_add("Search %s", key);
 855   found = xbt_dict_get(head, key);
 856   xbt_test_log("Found %s", (char *) found);
 857   if (data)
 858     xbt_test_assert(found,
 859                      "data do not match expectations: found NULL while searching for %s",
 860                      data);
 861   if (found)
 862     xbt_test_assert(!strcmp((char *) data, found),
 863                      "data do not match expectations: found %s while searching for %s",
 864                      (char *) found, data);
 865 }
 866
 867 static void search(xbt_dict_t head, const char *key)
 868 {
 869   search_ext(head, key, key);
 870 }
 871
 872 static void debuged_remove(xbt_dict_t head, const char *key)
 873 {
 874
 875   xbt_test_add("Remove '%s'", PRINTF_STR(key));
 876   xbt_dict_remove(head, key);
 877   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
 878 }
 879
 880
 881 static void traverse(xbt_dict_t head)
 882 {
 883   xbt_dict_cursor_t cursor = NULL;
 884   char *key;
 885   char *data;
 886   int i = 0;
 887
 888   xbt_dict_foreach(head, cursor, key, data) {
 889     if (!key || !data || strcmp(key, data)) {
 890       xbt_test_log("Seen #%d:  %s->%s", ++i, PRINTF_STR(key),
 891                     PRINTF_STR(data));
 892     } else {
 893       xbt_test_log("Seen #%d:  %s", ++i, PRINTF_STR(key));
 894     }
 895     xbt_test_assert(!data || !strcmp(key, data),
 896                      "Key(%s) != value(%s). Aborting", key, data);
 897   }
 898 }
 899
 900 static void search_not_found(xbt_dict_t head, const char *data)
 901 {
 902   int ok = 0;
 903   xbt_ex_t e;
 904
 905   xbt_test_add("Search %s (expected not to be found)", data);
 906
 907   TRY {
 908     data = xbt_dict_get(head, data);
 909     THROWF(unknown_error, 0,
 910            "Found something which shouldn't be there (%s)", data);
 911   }
 912   CATCH(e) {
 913     if (e.category != not_found_error)
 914       xbt_test_exception(e);
 915     xbt_ex_free(e);
 916     ok = 1;
 917   }
 918   xbt_test_assert(ok, "Exception not raised");
 919 }
 920
 921 static void count(xbt_dict_t dict, int length)
 922 {
 923   xbt_dict_cursor_t cursor;
 924   char *key;
 925   void *data;
 926   int effective = 0;
 927
 928
 929   xbt_test_add("Count elements (expecting %d)", length);
 930   xbt_test_assert(xbt_dict_length(dict) == length,
 931                    "Announced length(%d) != %d.", xbt_dict_length(dict),
 932                    length);
 933
 934   xbt_dict_foreach(dict, cursor, key, data)
 935       effective++;
 936
 937   xbt_test_assert(effective == length, "Effective length(%d) != %d.",
 938                    effective, length);
 939
 940 }
 941
 942 static void count_check_get_key(xbt_dict_t dict, int length)
 943 {
 944   xbt_dict_cursor_t cursor;
 945   char *key;
 946   _XBT_GNUC_UNUSED char *key2;
 947   void *data;
 948   int effective = 0;
 949
 950
 951   xbt_test_add
 952       ("Count elements (expecting %d), and test the getkey function",
 953        length);
 954   xbt_test_assert(xbt_dict_length(dict) == length,
 955                    "Announced length(%d) != %d.", xbt_dict_length(dict),
 956                    length);
 957
 958   xbt_dict_foreach(dict, cursor, key, data) {
 959     effective++;
 960     key2 = xbt_dict_get_key(dict, data);
 961     xbt_assert(!strcmp(key, key2),
 962                 "The data was registered under %s instead of %s as expected",
 963                 key2, key);
 964   }
 965
 966   xbt_test_assert(effective == length, "Effective length(%d) != %d.",
 967                    effective, length);
 968
 969 }
 970
 971 xbt_ex_t e;
 972 xbt_dict_t head = NULL;
 973 char *data;
 974
 975
 976 XBT_TEST_UNIT("basic", test_dict_basic, "Basic usage: change, retrieve, traverse")
 977 {
 978   xbt_test_add("Traversal the null dictionary");
 979   traverse(head);
 980
 981   xbt_test_add("Traversal and search the empty dictionary");
 982   head = xbt_dict_new();
 983   traverse(head);
 984   TRY {
 985     debuged_remove(head, "12346");
 986   }
 987   CATCH(e) {
 988     if (e.category != not_found_error)
 989       xbt_test_exception(e);
 990     xbt_ex_free(e);
 991   }
 992   xbt_dict_free(&head);
 993
 994   xbt_test_add("Traverse the full dictionary");
 995   fill(&head);
 996   count_check_get_key(head, 7);
 997
 998   debuged_add_ext(head, "toto", "tutu");
 999   search_ext(head, "toto", "tutu");
1000   debuged_remove(head, "toto");
1001
1002   search(head, "12a");
1003   traverse(head);
1004
1005   xbt_test_add("Free the dictionary (twice)");
1006   xbt_dict_free(&head);
1007   xbt_dict_free(&head);
1008
1009   /* CHANGING */
1010   fill(&head);
1011   count_check_get_key(head, 7);
1012   xbt_test_add("Change 123 to 'Changed 123'");
1013   xbt_dict_set(head, "123", strdup("Changed 123"), &free);
1014   count_check_get_key(head, 7);
1015
1016   xbt_test_add("Change 123 back to '123'");
1017   xbt_dict_set(head, "123", strdup("123"), &free);
1018   count_check_get_key(head, 7);
1019
1020   xbt_test_add("Change 12a to 'Dummy 12a'");
1021   xbt_dict_set(head, "12a", strdup("Dummy 12a"), &free);
1022   count_check_get_key(head, 7);
1023
1024   xbt_test_add("Change 12a to '12a'");
1025   xbt_dict_set(head, "12a", strdup("12a"), &free);
1026   count_check_get_key(head, 7);
1027
1028   xbt_test_add("Traverse the resulting dictionary");
1029   traverse(head);
1030
1031   /* RETRIEVE */
1032   xbt_test_add("Search 123");
1033   data = xbt_dict_get(head, "123");
1034   xbt_test_assert(data);
1035   xbt_test_assert(!strcmp("123", data));
1036
1037   search_not_found(head, "Can't be found");
1038   search_not_found(head, "123 Can't be found");
1039   search_not_found(head, "12345678 NOT");
1040
1041   search(head, "12a");
1042   search(head, "12b");
1043   search(head, "12");
1044   search(head, "123456");
1045   search(head, "1234");
1046   search(head, "123457");
1047
1048   xbt_test_add("Traverse the resulting dictionary");
1049   traverse(head);
1050
1051   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
1052
1053   xbt_test_add("Free the dictionary twice");
1054   xbt_dict_free(&head);
1055   xbt_dict_free(&head);
1056
1057   xbt_test_add("Traverse the resulting dictionary");
1058   traverse(head);
1059 }
1060
1061 XBT_TEST_UNIT("remove", test_dict_remove, "Removing some values")
1062 {
1063   fill(&head);
1064   count(head, 7);
1065   xbt_test_add("Remove non existing data");
1066   TRY {
1067     debuged_remove(head, "Does not exist");
1068   }
1069   CATCH(e) {
1070     if (e.category != not_found_error)
1071       xbt_test_exception(e);
1072     xbt_ex_free(e);
1073   }
1074   traverse(head);
1075
1076   xbt_dict_free(&head);
1077
1078   xbt_test_add
1079       ("Remove each data manually (traversing the resulting dictionary each time)");
1080   fill(&head);
1081   debuged_remove(head, "12a");
1082   traverse(head);
1083   count(head, 6);
1084   debuged_remove(head, "12b");
1085   traverse(head);
1086   count(head, 5);
1087   debuged_remove(head, "12");
1088   traverse(head);
1089   count(head, 4);
1090   debuged_remove(head, "123456");
1091   traverse(head);
1092   count(head, 3);
1093   TRY {
1094     debuged_remove(head, "12346");
1095   }
1096   CATCH(e) {
1097     if (e.category != not_found_error)
1098       xbt_test_exception(e);
1099     xbt_ex_free(e);
1100     traverse(head);
1101   }
1102   debuged_remove(head, "1234");
1103   traverse(head);
1104   debuged_remove(head, "123457");
1105   traverse(head);
1106   debuged_remove(head, "123");
1107   traverse(head);
1108   TRY {
1109     debuged_remove(head, "12346");
1110   }
1111   CATCH(e) {
1112     if (e.category != not_found_error)
1113       xbt_test_exception(e);
1114     xbt_ex_free(e);
1115   }
1116   traverse(head);
1117
1118   xbt_test_add
1119       ("Free dict, create new fresh one, and then reset the dict");
1120   xbt_dict_free(&head);
1121   fill(&head);
1122   xbt_dict_reset(head);
1123   count(head, 0);
1124   traverse(head);
1125
1126   xbt_test_add("Free the dictionary twice");
1127   xbt_dict_free(&head);
1128   xbt_dict_free(&head);
1129 }
1130
1131 XBT_TEST_UNIT("nulldata", test_dict_nulldata, "NULL data management")
1132 {
1133   fill(&head);
1134
1135   xbt_test_add("Store NULL under 'null'");
1136   xbt_dict_set(head, "null", NULL, NULL);
1137   search_ext(head, "null", NULL);
1138
1139   xbt_test_add("Check whether I see it while traversing...");
1140   {
1141     xbt_dict_cursor_t cursor = NULL;
1142     char *key;
1143     int found = 0;
1144
1145     xbt_dict_foreach(head, cursor, key, data) {
1146       if (!key || !data || strcmp(key, data)) {
1147         xbt_test_log("Seen:  %s->%s", PRINTF_STR(key), PRINTF_STR(data));
1148       } else {
1149         xbt_test_log("Seen:  %s", PRINTF_STR(key));
1150       }
1151
1152       if (!strcmp(key, "null"))
1153         found = 1;
1154     }
1155     xbt_test_assert(found,
1156                      "the key 'null', associated to NULL is not found");
1157   }
1158   xbt_dict_free(&head);
1159 }
1160
1161 static void debuged_addi(xbt_dict_t head, uintptr_t key, uintptr_t data)
1162 {
1163   uintptr_t stored_data = 0;
1164   xbt_test_log("Add %zu under %zu", data, key);
1165
1166   xbt_dicti_set(head, key, data);
1167   if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) {
1168     xbt_dict_dump(head, (void (*)(void *)) &printf);
1169     fflush(stdout);
1170   }
1171   stored_data = xbt_dicti_get(head, key);
1172   xbt_test_assert(stored_data == data,
1173                    "Retrieved data (%zu) is not what I just stored (%zu) under key %zu",
1174                    stored_data, data, key);
1175 }
1176
1177 XBT_TEST_UNIT("dicti", test_dict_scalar, "Scalar data and key management")
1178 {
1179   xbt_test_add("Fill in the dictionnary");
1180
1181   head = xbt_dict_new();
1182   debuged_addi(head, 12, 12);
1183   debuged_addi(head, 13, 13);
1184   debuged_addi(head, 14, 14);
1185   debuged_addi(head, 15, 15);
1186   /* Change values */
1187   debuged_addi(head, 12, 15);
1188   debuged_addi(head, 15, 2000);
1189   debuged_addi(head, 15, 3000);
1190   /* 0 as key */
1191   debuged_addi(head, 0, 1000);
1192   debuged_addi(head, 0, 2000);
1193   debuged_addi(head, 0, 3000);
1194   /* 0 as value */
1195   debuged_addi(head, 12, 0);
1196   debuged_addi(head, 13, 0);
1197   debuged_addi(head, 12, 0);
1198   debuged_addi(head, 0, 0);
1199
1200   xbt_dict_free(&head);
1201 }
1202
1203 #define NB_ELM 20000
1204 #define SIZEOFKEY 1024
1205 static int countelems(xbt_dict_t head)
1206 {
1207   xbt_dict_cursor_t cursor;
1208   char *key;
1209   void *data;
1210   int res = 0;
1211
1212   xbt_dict_foreach(head, cursor, key, data) {
1213     res++;
1214   }
1215   return res;
1216 }
1217
1218 XBT_TEST_UNIT("crash", test_dict_crash, "Crash test")
1219 {
1220   xbt_dict_t head = NULL;
1221   int i, j, k;
1222   char *key;
1223   void *data;
1224
1225   srand((unsigned int) time(NULL));
1226
1227   for (i = 0; i < 10; i++) {
1228     xbt_test_add("CRASH test number %d (%d to go)", i + 1, 10 - i - 1);
1229     xbt_test_log
1230         ("Fill the struct, count its elems and frees the structure");
1231     xbt_test_log
1232         ("using 1000 elements with %d chars long randomized keys.",
1233          SIZEOFKEY);
1234     head = xbt_dict_new();
1235     /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
1236     for (j = 0; j < 1000; j++) {
1237       char *data = NULL;
1238       key = xbt_malloc(SIZEOFKEY);
1239
1240       do {
1241         for (k = 0; k < SIZEOFKEY - 1; k++)
1242           key[k] = rand() % ('z' - 'a') + 'a';
1243         key[k] = '\0';
1244         /*      printf("[%d %s]\n",j,key); */
1245         data = xbt_dict_get_or_null(head, key);
1246       } while (data != NULL);
1247
1248       xbt_dict_set(head, key, key, &free);
1249       data = xbt_dict_get(head, key);
1250       xbt_test_assert(!strcmp(key, data),
1251                        "Retrieved value (%s) != Injected value (%s)", key,
1252                        data);
1253
1254       count(head, j + 1);
1255     }
1256     /*    xbt_dict_dump(head,(void (*)(void*))&printf); */
1257     traverse(head);
1258     xbt_dict_free(&head);
1259     xbt_dict_free(&head);
1260   }
1261
1262
1263   head = xbt_dict_new();
1264   xbt_test_add("Fill %d elements, with keys being the number of element",
1265                 NB_ELM);
1266   for (j = 0; j < NB_ELM; j++) {
1267     /* if (!(j%1000)) { printf("."); fflush(stdout); } */
1268
1269     key = xbt_malloc(10);
1270
1271     sprintf(key, "%d", j);
1272     xbt_dict_set(head, key, key, &free);
1273   }
1274   /*xbt_dict_dump(head,(void (*)(void*))&printf); */
1275
1276   xbt_test_add
1277       ("Count the elements (retrieving the key and data for each)");
1278   i = countelems(head);
1279   xbt_test_log("There is %d elements", i);
1280
1281   xbt_test_add("Search my %d elements 20 times", NB_ELM);
1282   key = xbt_malloc(10);
1283   for (i = 0; i < 20; i++) {
1284     /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
1285     for (j = 0; j < NB_ELM; j++) {
1286
1287       sprintf(key, "%d", j);
1288       data = xbt_dict_get(head, key);
1289       xbt_test_assert(!strcmp(key, (char *) data),
1290                        "with get, key=%s != data=%s", key, (char *) data);
1291       data = xbt_dict_get_ext(head, key, strlen(key));
1292       xbt_test_assert(!strcmp(key, (char *) data),
1293                        "with get_ext, key=%s != data=%s", key,
1294                        (char *) data);
1295     }
1296   }
1297   free(key);
1298
1299   xbt_test_add("Remove my %d elements", NB_ELM);
1300   key = xbt_malloc(10);
1301   for (j = 0; j < NB_ELM; j++) {
1302     /* if (!(j%10000)) printf("."); fflush(stdout); */
1303
1304     sprintf(key, "%d", j);
1305     xbt_dict_remove(head, key);
1306   }
1307   free(key);
1308
1309
1310   xbt_test_add("Free the structure (twice)");
1311   xbt_dict_free(&head);
1312   xbt_dict_free(&head);
1313 }
1314
1315 static void str_free(void *s)
1316 {
1317   char *c = *(char **) s;
1318   free(c);
1319 }
1320
1321 XBT_TEST_UNIT("multicrash", test_dict_multicrash, "Multi-dict crash test")
1322 {
1323
1324 #undef NB_ELM
1325 #define NB_ELM 100              /*00 */
1326 #define DEPTH 5
1327 #define KEY_SIZE 512
1328 #define NB_TEST 20              /*20 */
1329   int verbose = 0;
1330
1331   xbt_dict_t mdict = NULL;
1332   int i, j, k, l;
1333   xbt_dynar_t keys = xbt_dynar_new(sizeof(char *), str_free);
1334   void *data;
1335   char *key;
1336
1337
1338   xbt_test_add("Generic multicache CRASH test");
1339   xbt_test_log
1340       (" Fill the struct and frees it %d times, using %d elements, "
1341        "depth of multicache=%d, key size=%d", NB_TEST, NB_ELM, DEPTH,
1342        KEY_SIZE);
1343
1344   for (l = 0; l < DEPTH; l++) {
1345     key = xbt_malloc(KEY_SIZE);
1346     xbt_dynar_push(keys, &key);
1347   }
1348
1349   for (i = 0; i < NB_TEST; i++) {
1350     mdict = xbt_dict_new();
1351     XBT_VERB("mdict=%p", mdict);
1352     if (verbose > 0)
1353       printf("Test %d\n", i);
1354     /* else if (i%10) printf("."); else printf("%d",i/10); */
1355
1356     for (j = 0; j < NB_ELM; j++) {
1357       if (verbose > 0)
1358         printf("  Add {");
1359
1360       for (l = 0; l < DEPTH; l++) {
1361         key = *(char **) xbt_dynar_get_ptr(keys, l);
1362
1363         for (k = 0; k < KEY_SIZE - 1; k++)
1364           key[k] = rand() % ('z' - 'a') + 'a';
1365
1366         key[k] = '\0';
1367
1368         if (verbose > 0)
1369           printf("%p=%s %s ", key, key, (l < DEPTH - 1 ? ";" : "}"));
1370       }
1371       if (verbose > 0)
1372         printf("in multitree %p.\n", mdict);
1373
1374       xbt_multidict_set(mdict, keys, xbt_strdup(key), free);
1375
1376       data = xbt_multidict_get(mdict, keys);
1377
1378       xbt_test_assert(data && !strcmp((char *) data, key),
1379                        "Retrieved value (%s) does not match the given one (%s)\n",
1380                        (char *) data, key);
1381     }
1382     xbt_dict_free(&mdict);
1383   }
1384
1385   xbt_dynar_free(&keys);
1386
1387   /*  if (verbose>0)
1388      xbt_dict_dump(mdict,&xbt_dict_print); */
1389
1390   xbt_dict_free(&mdict);
1391   xbt_dynar_free(&keys);
1392
1393 }
1394 #endif                          /* SIMGRID_TEST */