src/xbt/dict.c

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