src/xbt/dict.c

   1 /* $Id$ */
   2
   3 /* dict - a generic dictionary, variation over the B-tree concept          */
   4
   5 /* Copyright (c) 2003,2004 Martin Quinson. All rights reserved.             */
   6
   7 /* This program is free software; you can redistribute it and/or modify it
   8  * under the terms of the license (GNU LGPL) which comes with this package. */
   9
  10 #define DJB2_HASH_FUNCTION
  11 //#define FNV_HASH_FUNCTION
  12
  13 #include <string.h>
  14 #include <stdio.h>
  15 #include "xbt/ex.h"
  16 #include "xbt/log.h"
  17 #include "xbt/mallocator.h"
  18 #include "xbt_modinter.h"
  19 #include "dict_private.h"
  20
  21 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict, xbt,
  22                                 "Dictionaries provide the same functionalities than hash tables");
  23 /*####[ Private prototypes ]#################################################*/
  24
  25 static xbt_mallocator_t dict_mallocator = NULL;
  26 static void *dict_mallocator_new_f(void);
  27 static void dict_mallocator_free_f(void *dict);
  28 static void dict_mallocator_reset_f(void *dict);
  29
  30
  31 /*####[ Code ]###############################################################*/
  32
  33 /**
  34  * \brief Constructor
  35  * \return pointer to the destination
  36  * \see xbt_dict_new_ext(), xbt_dict_free()
  37  *
  38  * Creates and initialize a new dictionary with a default hashtable size.
  39  */
  40 xbt_dict_t xbt_dict_new(void)
  41 {
  42   xbt_dict_t dict;
  43
  44   if (dict_mallocator == NULL) {
  45     /* first run */
  46     dict_mallocator = xbt_mallocator_new(256,
  47                                          dict_mallocator_new_f,
  48                                          dict_mallocator_free_f,
  49                                          dict_mallocator_reset_f);
  50     dict_elm_mallocator = xbt_mallocator_new(256,
  51                                              dict_elm_mallocator_new_f,
  52                                              dict_elm_mallocator_free_f,
  53                                              dict_elm_mallocator_reset_f);
  54   }
  55
  56   dict = xbt_mallocator_get(dict_mallocator);
  57   dict->table_size = 127;
  58   dict->table = xbt_new0(xbt_dictelm_t, dict->table_size + 1);
  59   dict->count = 0;
  60   dict->fill = 0;
  61
  62   return dict;
  63 }
  64
  65 /**
  66  * \brief Destructor
  67  * \param dict the dictionary to be freed
  68  *
  69  * Frees a dictionary with all the data
  70  */
  71 void xbt_dict_free(xbt_dict_t * dict)
  72 {
  73   int i;
  74   xbt_dictelm_t current, previous;
  75   int table_size;
  76   xbt_dictelm_t *table;
  77
  78   //  if ( *dict )  xbt_dict_dump_sizes(*dict);
  79
  80   if (dict != NULL && *dict != NULL) {
  81     table_size = (*dict)->table_size;
  82     table = (*dict)->table;
  83     /* Warning: the size of the table is 'table_size+1'...
  84      * This is because table_size is used as a binary mask in xbt_dict_rehash */
  85     for (i = 0; (*dict)->count && i <= table_size; i++) {
  86       current = table[i];
  87       while (current != NULL) {
  88         previous = current;
  89         current = current->next;
  90         xbt_dictelm_free(previous);
  91         (*dict)->count--;
  92       }
  93     }
  94     xbt_free(table);
  95     xbt_mallocator_release(dict_mallocator, *dict);
  96     *dict = NULL;
  97   }
  98 }
  99
 100 /**
 101  * Returns the amount of elements in the dict
 102  */
 103 XBT_INLINE unsigned int xbt_dict_size(xbt_dict_t dict)
 104 {
 105   return dict->count;
 106 }
 107
 108 /**
 109  * Returns the hash code of a string.
 110  */
 111 static XBT_INLINE unsigned int xbt_dict_hash_ext(const char *str, int str_len)
 112 {
 113
 114
 115 #ifdef DJB2_HASH_FUNCTION
 116   /* fast implementation of djb2 algorithm */
 117   int c;
 118   register unsigned int hash = 5381;
 119
 120   while (str_len--) {
 121     c = *str++;
 122     hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
 123   }
 124 # elif defined(FNV_HASH_FUNCTION)
 125   register unsigned int hash = 0x811c9dc5;
 126   unsigned char *bp = (unsigned char *) str;    /* start of buffer */
 127   unsigned char *be = bp + str_len;     /* beyond end of buffer */
 128
 129   while (bp < be) {
 130     /* multiply by the 32 bit FNV magic prime mod 2^32 */
 131     hash +=
 132       (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24);
 133
 134     /* xor the bottom with the current octet */
 135     hash ^= (unsigned int) *bp++;
 136   }
 137
 138 # else
 139   register unsigned int hash = 0;
 140
 141   while (str_len--) {
 142     hash += (*str) * (*str);
 143     str++;
 144   }
 145 #endif
 146
 147   return hash;
 148 }
 149
 150 static XBT_INLINE unsigned int xbt_dict_hash(const char *str)
 151 {
 152 #ifdef DJB2_HASH_FUNCTION
 153   /* fast implementation of djb2 algorithm */
 154   int c;
 155   register unsigned int hash = 5381;
 156
 157   while ((c = *str++)) {
 158     hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */
 159   }
 160
 161 # elif defined(FNV_HASH_FUNCTION)
 162   register unsigned int hash = 0x811c9dc5;
 163
 164   while (*str) {
 165     /* multiply by the 32 bit FNV magic prime mod 2^32 */
 166     hash +=
 167       (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24);
 168
 169     /* xor the bottom with the current byte */
 170     hash ^= (unsigned int) *str++;
 171   }
 172
 173 # else
 174   register unsigned int hash = 0;
 175
 176   while (*str) {
 177     hash += (*str) * (*str);
 178     str++;
 179   }
 180 #endif
 181   return hash;
 182 }
 183
 184 /* Expend the size of the dict */
 185 static void xbt_dict_rehash(xbt_dict_t dict)
 186 {
 187   const int oldsize = dict->table_size + 1;
 188   register int newsize = oldsize * 2;
 189   register int i;
 190   register xbt_dictelm_t *currcell;
 191   register xbt_dictelm_t *twincell;
 192   register xbt_dictelm_t bucklet;
 193   register xbt_dictelm_t *pprev;
 194
 195   currcell =
 196     (xbt_dictelm_t *) xbt_realloc((char *) dict->table,
 197                                   newsize * sizeof(xbt_dictelm_t));
 198   memset(&currcell[oldsize], 0, oldsize * sizeof(xbt_dictelm_t));       /* zero second half */
 199   dict->table_size = --newsize;
 200   dict->table = currcell;
 201   DEBUG2("REHASH (%d->%d)", oldsize, newsize);
 202
 203   for (i = 0; i < oldsize; i++, currcell++) {
 204     if (!*currcell)             /* empty cell */
 205       continue;
 206     twincell = currcell + oldsize;
 207     for (pprev = currcell, bucklet = *currcell; bucklet; bucklet = *pprev) {
 208       /* Since we use "& size" instead of "%size" and since the size was doubled,
 209          each bucklet of this cell must either :
 210          - stay  in  cell i (ie, currcell)
 211          - go to the cell i+oldsize (ie, twincell) */
 212       if ((bucklet->hash_code & newsize) != i) {        /* Move to b */
 213         *pprev = bucklet->next;
 214         bucklet->next = *twincell;
 215         if (!*twincell)
 216           dict->fill++;
 217         *twincell = bucklet;
 218         continue;
 219       } else {
 220         pprev = &bucklet->next;
 221       }
 222
 223     }
 224
 225     if (!*currcell)             /* everything moved */
 226       dict->fill--;
 227   }
 228 }
 229
 230 /**
 231  * \brief Add data to the dict (arbitrary key)
 232  * \param dict the container
 233  * \param key the key to set the new data
 234  * \param key_len the size of the \a key
 235  * \param data the data to add in the dict
 236  * \param free_ctn function to call with (\a key as argument) when
 237  *        \a key is removed from the dictionary
 238  *
 239  * Set the \a data in the structure under the \a key, which can be any kind
 240  * of data, as long as its length is provided in \a key_len.
 241  */
 242 XBT_INLINE void xbt_dict_set_ext(xbt_dict_t dict,
 243                                  const char *key, int key_len,
 244                                  void *data, void_f_pvoid_t free_ctn)
 245 {
 246
 247   unsigned int hash_code = xbt_dict_hash_ext(key, key_len);
 248
 249   xbt_dictelm_t current, previous = NULL;
 250   xbt_assert(dict);
 251
 252   DEBUG5("ADD %.*s hash = %d, size = %d, & = %d", key_len, key, hash_code,
 253          dict->table_size, hash_code & dict->table_size);
 254   current = dict->table[hash_code & dict->table_size];
 255   while (current != NULL &&
 256          (hash_code != current->hash_code || key_len != current->key_len
 257           || memcmp(key, current->key, key_len))) {
 258     previous = current;
 259     current = current->next;
 260   }
 261
 262   if (current == NULL) {
 263     /* this key doesn't exist yet */
 264     current = xbt_dictelm_new(key, key_len, hash_code, data, free_ctn);
 265     dict->count++;
 266     if (previous == NULL) {
 267       dict->table[hash_code & dict->table_size] = current;
 268       dict->fill++;
 269       if ((dict->fill * 100) / (dict->table_size + 1) > MAX_FILL_PERCENT)
 270         xbt_dict_rehash(dict);
 271     } else {
 272       previous->next = current;
 273     }
 274   } else {
 275
 276     DEBUG6("Replace %.*s by %.*s under key %.*s",
 277            key_len, (char *) current->content,
 278            key_len, (char *) data, key_len, (char *) key);
 279     /* there is already an element with the same key: overwrite it */
 280     if (current->content != NULL && current->free_f != NULL) {
 281       current->free_f(current->content);
 282     }
 283     current->content = data;
 284     current->free_f = free_ctn;
 285   }
 286 }
 287
 288 /**
 289  * \brief Add data to the dict (null-terminated key)
 290  *
 291  * \param dict the dict
 292  * \param key the key to set the new data
 293  * \param data the data to add in the dict
 294  * \param free_ctn function to call with (\a key as argument) when
 295  *        \a key is removed from the dictionary
 296  *
 297  * set the \a data in the structure under the \a key, which is a
 298  * null terminated string.
 299  */
 300 XBT_INLINE void xbt_dict_set(xbt_dict_t dict,
 301                   const char *key, void *data, void_f_pvoid_t free_ctn)
 302 {
 303
 304   xbt_dict_set_ext(dict, key, strlen(key), data, free_ctn);
 305 }
 306
 307 /**
 308  * \brief Retrieve data from the dict (arbitrary key)
 309  *
 310  * \param dict the dealer of data
 311  * \param key the key to find data
 312  * \param key_len the size of the \a key
 313  * \return the data that we are looking for
 314  *
 315  * Search the given \a key. Throws not_found_error when not found.
 316  */
 317 XBT_INLINE void *xbt_dict_get_ext(xbt_dict_t dict, const char *key, int key_len)
 318 {
 319
 320
 321   unsigned int hash_code = xbt_dict_hash_ext(key, key_len);
 322   xbt_dictelm_t current;
 323
 324   xbt_assert(dict);
 325
 326   current = dict->table[hash_code & dict->table_size];
 327   while (current != NULL &&
 328          (hash_code != current->hash_code || key_len != current->key_len
 329           || memcmp(key, current->key, key_len))) {
 330     current = current->next;
 331   }
 332
 333   if (current == NULL)
 334     THROW2(not_found_error, 0, "key %.*s not found", key_len, key);
 335
 336   return current->content;
 337 }
 338
 339 /**
 340  * \brief like xbt_dict_get_ext(), but returning NULL when not found
 341  */
 342 void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key, int key_len)
 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  * \brief Remove data from the dict (null-terminated key)
 481  *
 482  * \param dict the dict
 483  * \param key the key of the data to be removed
 484  *
 485  * Remove the entry associated with the given \a key
 486  */
 487 XBT_INLINE void xbt_dict_remove(xbt_dict_t dict, const char *key)
 488 {
 489   xbt_dict_remove_ext(dict, key, strlen(key));
 490 }
 491
 492 /**
 493  * \brief Remove all data from the dict
 494  * \param dict the dict
 495  */
 496 void xbt_dict_reset(xbt_dict_t dict)
 497 {
 498
 499   int i;
 500   xbt_dictelm_t current, previous = NULL;
 501
 502   xbt_assert(dict);
 503
 504   if (dict->count == 0)
 505     return;
 506
 507   for (i = 0; i <= dict->table_size; i++) {
 508     current = dict->table[i];
 509     while (current != NULL) {
 510       previous = current;
 511       current = current->next;
 512       xbt_dictelm_free(previous);
 513     }
 514     dict->table[i] = NULL;
 515   }
 516
 517   dict->count = 0;
 518   dict->fill = 0;
 519 }
 520
 521 /**
 522  * \brief Return the number of elements in the dict.
 523  * \param dict a dictionary
 524  */
 525 XBT_INLINE int xbt_dict_length(xbt_dict_t dict)
 526 {
 527   xbt_assert(dict);
 528
 529   return dict->count;
 530 }
 531
 532 /** @brief function to be used in xbt_dict_dump as long as the stored values are strings */
 533 void xbt_dict_dump_output_string(void *s)
 534 {
 535   fputs(s, stdout);
 536 }
 537
 538
 539 /**
 540  * \brief Outputs the content of the structure (debugging purpose)
 541  *
 542  * \param dict the exibitionist
 543  * \param output a function to dump each data in the tree (check @ref xbt_dict_dump_output_string)
 544  *
 545  * Outputs the content of the structure. (for debugging purpose). \a output is a
 546  * function to output the data. If NULL, data won't be displayed.
 547  */
 548
 549 void xbt_dict_dump(xbt_dict_t dict, void_f_pvoid_t output)
 550 {
 551   int i;
 552   xbt_dictelm_t element;
 553   printf("Dict %p:\n", dict);
 554   if (dict != NULL) {
 555     for (i = 0; i < dict->table_size; i++) {
 556       element = dict->table[i];
 557       if (element) {
 558         printf("[\n");
 559         while (element != NULL) {
 560           printf(" %s -> '", element->key);
 561           if (output != NULL) {
 562             (*output) (element->content);
 563           }
 564           printf("'\n");
 565           element = element->next;
 566         }
 567         printf("]\n");
 568       } else {
 569         printf("[]\n");
 570       }
 571     }
 572   }
 573 }
 574
 575 xbt_dynar_t all_sizes = NULL;
 576 /** @brief shows some debugging info about the bucklet repartition */
 577 void xbt_dict_dump_sizes(xbt_dict_t dict)
 578 {
 579
 580   int i;
 581   unsigned int count;
 582   unsigned int size;
 583   xbt_dictelm_t element;
 584   xbt_dynar_t sizes = xbt_dynar_new(sizeof(int), NULL);
 585
 586   printf("Dict %p: %d bucklets, %d used cells (of %d) ", dict, dict->count,
 587          dict->fill, dict->table_size);
 588   if (dict != NULL) {
 589     for (i = 0; i < dict->table_size; i++) {
 590       element = dict->table[i];
 591       size = 0;
 592       if (element) {
 593         while (element != NULL) {
 594           size++;
 595           element = element->next;
 596         }
 597       }
 598       if (xbt_dynar_length(sizes) <= size) {
 599         int prevsize = 1;
 600         xbt_dynar_set(sizes, size, &prevsize);
 601       } else {
 602         int prevsize;
 603         xbt_dynar_get_cpy(sizes, size, &prevsize);
 604         prevsize++;
 605         xbt_dynar_set(sizes, size, &prevsize);
 606       }
 607     }
 608     if (!all_sizes)
 609       all_sizes = xbt_dynar_new(sizeof(int), NULL);
 610
 611     xbt_dynar_foreach(sizes, count, size) {
 612       /* Copy values of this one into all_sizes */
 613       int prevcount;
 614       if (xbt_dynar_length(all_sizes) <= count) {
 615         prevcount = size;
 616         xbt_dynar_set(all_sizes, count, &prevcount);
 617       } else {
 618         xbt_dynar_get_cpy(all_sizes, count, &prevcount);
 619         prevcount += size;
 620         xbt_dynar_set(all_sizes, count, &prevcount);
 621       }
 622
 623       /* Report current sizes */
 624       if (count == 0)
 625         continue;
 626       if (size == 0)
 627         continue;
 628       printf("%delm x %u cells; ", count, size);
 629     }
 630   }
 631   printf("\n");
 632   xbt_dynar_free(&sizes);
 633 }
 634
 635 /**
 636  * Destroy the dict mallocators.
 637  * This is an internal XBT function called by xbt_exit().
 638  */
 639 void xbt_dict_exit(void)
 640 {
 641   if (dict_mallocator != NULL) {
 642     xbt_mallocator_free(dict_mallocator);
 643     dict_mallocator = NULL;
 644     xbt_mallocator_free(dict_elm_mallocator);
 645     dict_elm_mallocator = NULL;
 646   }
 647   if (all_sizes) {
 648     unsigned int count;
 649     int size;
 650     double avg = 0;
 651     int total_count = 0;
 652     printf("Overall stats:");
 653     xbt_dynar_foreach(all_sizes, count, size) {
 654       if (count == 0)
 655         continue;
 656       if (size == 0)
 657         continue;
 658       printf("%delm x %d cells; ", count, size);
 659       avg += count * size;
 660       total_count += size;
 661     }
 662     printf("; %f elm per cell\n", avg / (double) total_count);
 663   }
 664 }
 665
 666 static void *dict_mallocator_new_f(void)
 667 {
 668   return xbt_new(s_xbt_dict_t, 1);
 669 }
 670
 671 static void dict_mallocator_free_f(void *dict)
 672 {
 673   xbt_free(dict);
 674 }
 675
 676 static void dict_mallocator_reset_f(void *dict)
 677 {
 678   /* nothing to do because all fields are
 679    * initialized in xbt_dict_new
 680    */
 681 }
 682
 683 #ifdef SIMGRID_TEST
 684 #include "xbt.h"
 685 #include "xbt/ex.h"
 686 #include "portable.h"
 687
 688 XBT_LOG_EXTERNAL_CATEGORY(xbt_dict);
 689 XBT_LOG_DEFAULT_CATEGORY(xbt_dict);
 690
 691 XBT_TEST_SUITE("dict", "Dict data container");
 692
 693 static void print_str(void *str)
 694 {
 695   printf("%s", (char *) PRINTF_STR(str));
 696 }
 697
 698 static void debuged_add_ext(xbt_dict_t head, const char *key,
 699                             const char *data_to_fill)
 700 {
 701   char *data = xbt_strdup(data_to_fill);
 702
 703   xbt_test_log2("Add %s under %s", PRINTF_STR(data_to_fill), PRINTF_STR(key));
 704
 705   xbt_dict_set(head, key, data, &free);
 706   if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) {
 707     xbt_dict_dump(head, (void (*)(void *)) &printf);
 708     fflush(stdout);
 709   }
 710 }
 711
 712 static void debuged_add(xbt_dict_t head, const char *key)
 713 {
 714   debuged_add_ext(head, key, key);
 715 }
 716
 717 static void fill(xbt_dict_t * head)
 718 {
 719   xbt_test_add0("Fill in the dictionnary");
 720
 721   *head = xbt_dict_new();
 722   debuged_add(*head, "12");
 723   debuged_add(*head, "12a");
 724   debuged_add(*head, "12b");
 725   debuged_add(*head, "123");
 726   debuged_add(*head, "123456");
 727   /* Child becomes child of what to add */
 728   debuged_add(*head, "1234");
 729   /* Need of common ancestor */
 730   debuged_add(*head, "123457");
 731 }
 732
 733
 734 static void search_ext(xbt_dict_t head, const char *key, const char *data)
 735 {
 736   void *found;
 737
 738   xbt_test_add1("Search %s", key);
 739   found = xbt_dict_get(head, key);
 740   xbt_test_log1("Found %s", (char *) found);
 741   if (data)
 742     xbt_test_assert1(found,
 743                      "data do not match expectations: found NULL while searching for %s",
 744                      data);
 745   if (found)
 746     xbt_test_assert2(!strcmp((char *) data, found),
 747                      "data do not match expectations: found %s while searching for %s",
 748                      (char *) found, data);
 749 }
 750
 751 static void search(xbt_dict_t head, const char *key)
 752 {
 753   search_ext(head, key, key);
 754 }
 755
 756 static void debuged_remove(xbt_dict_t head, const char *key)
 757 {
 758
 759   xbt_test_add1("Remove '%s'", PRINTF_STR(key));
 760   xbt_dict_remove(head, key);
 761   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
 762 }
 763
 764
 765 static void traverse(xbt_dict_t head)
 766 {
 767   xbt_dict_cursor_t cursor = NULL;
 768   char *key;
 769   char *data;
 770   int i = 0;
 771
 772   xbt_dict_foreach(head, cursor, key, data) {
 773     if (!key || !data || strcmp(key, data)) {
 774       xbt_test_log3("Seen #%d:  %s->%s", ++i, PRINTF_STR(key),
 775                     PRINTF_STR(data));
 776     } else {
 777       xbt_test_log2("Seen #%d:  %s", ++i, PRINTF_STR(key));
 778     }
 779     xbt_test_assert2(!data || !strcmp(key, data),
 780                      "Key(%s) != value(%s). Aborting", key, data);
 781   }
 782 }
 783
 784 static void search_not_found(xbt_dict_t head, const char *data)
 785 {
 786   int ok = 0;
 787   xbt_ex_t e;
 788
 789   xbt_test_add1("Search %s (expected not to be found)", data);
 790
 791   TRY {
 792     data = xbt_dict_get(head, data);
 793     THROW1(unknown_error, 0, "Found something which shouldn't be there (%s)",
 794            data);
 795   } CATCH(e) {
 796     if (e.category != not_found_error)
 797       xbt_test_exception(e);
 798     xbt_ex_free(e);
 799     ok = 1;
 800   }
 801   xbt_test_assert0(ok, "Exception not raised");
 802 }
 803
 804 static void count(xbt_dict_t dict, int length)
 805 {
 806   xbt_dict_cursor_t cursor;
 807   char *key;
 808   void *data;
 809   int effective = 0;
 810
 811
 812   xbt_test_add1("Count elements (expecting %d)", length);
 813   xbt_test_assert2(xbt_dict_length(dict) == length,
 814                    "Announced length(%d) != %d.", xbt_dict_length(dict),
 815                    length);
 816
 817   xbt_dict_foreach(dict, cursor, key, data)
 818     effective++;
 819
 820   xbt_test_assert2(effective == length, "Effective length(%d) != %d.",
 821                    effective, length);
 822
 823 }
 824
 825 static void count_check_get_key(xbt_dict_t dict, int length)
 826 {
 827   xbt_dict_cursor_t cursor;
 828   char *key,*key2;
 829   void *data;
 830   int effective = 0;
 831
 832
 833   xbt_test_add1("Count elements (expecting %d), and test the getkey function", length);
 834   xbt_test_assert2(xbt_dict_length(dict) == length,
 835                    "Announced length(%d) != %d.", xbt_dict_length(dict),
 836                    length);
 837
 838   xbt_dict_foreach(dict, cursor, key, data) {
 839     effective++;
 840     key2 = xbt_dict_get_key(dict,data);
 841     xbt_assert2(!strcmp(key,key2),
 842           "The data was registered under %s instead of %s as expected",key2,key);
 843   }
 844
 845   xbt_test_assert2(effective == length, "Effective length(%d) != %d.",
 846                    effective, length);
 847
 848 }
 849
 850 xbt_ex_t e;
 851 xbt_dict_t head = NULL;
 852 char *data;
 853
 854
 855 XBT_TEST_UNIT("basic", test_dict_basic,"Basic usage: change, retrieve, traverse")
 856 {
 857   xbt_test_add0("Traversal the null dictionary");
 858   traverse(head);
 859
 860   xbt_test_add0("Traversal and search the empty dictionary");
 861   head = xbt_dict_new();
 862   traverse(head);
 863   TRY {
 864     debuged_remove(head, "12346");
 865   } CATCH(e) {
 866     if (e.category != not_found_error)
 867       xbt_test_exception(e);
 868     xbt_ex_free(e);
 869   }
 870   xbt_dict_free(&head);
 871
 872   xbt_test_add0("Traverse the full dictionary");
 873   fill(&head);
 874   count_check_get_key(head, 7);
 875
 876   debuged_add_ext(head, "toto", "tutu");
 877   search_ext(head, "toto", "tutu");
 878   debuged_remove(head, "toto");
 879
 880   search(head, "12a");
 881   traverse(head);
 882
 883   xbt_test_add0("Free the dictionary (twice)");
 884   xbt_dict_free(&head);
 885   xbt_dict_free(&head);
 886
 887   /* CHANGING */
 888   fill(&head);
 889   count_check_get_key(head, 7);
 890   xbt_test_add0("Change 123 to 'Changed 123'");
 891   xbt_dict_set(head, "123", strdup("Changed 123"), &free);
 892   count_check_get_key(head, 7);
 893
 894   xbt_test_add0("Change 123 back to '123'");
 895   xbt_dict_set(head, "123", strdup("123"), &free);
 896   count_check_get_key(head, 7);
 897
 898   xbt_test_add0("Change 12a to 'Dummy 12a'");
 899   xbt_dict_set(head, "12a", strdup("Dummy 12a"), &free);
 900   count_check_get_key(head, 7);
 901
 902   xbt_test_add0("Change 12a to '12a'");
 903   xbt_dict_set(head, "12a", strdup("12a"), &free);
 904   count_check_get_key(head, 7);
 905
 906   xbt_test_add0("Traverse the resulting dictionary");
 907   traverse(head);
 908
 909   /* RETRIEVE */
 910   xbt_test_add0("Search 123");
 911   data = xbt_dict_get(head, "123");
 912   xbt_test_assert(data);
 913   xbt_test_assert(!strcmp("123", data));
 914
 915   search_not_found(head, "Can't be found");
 916   search_not_found(head, "123 Can't be found");
 917   search_not_found(head, "12345678 NOT");
 918
 919   search(head, "12a");
 920   search(head, "12b");
 921   search(head, "12");
 922   search(head, "123456");
 923   search(head, "1234");
 924   search(head, "123457");
 925
 926   xbt_test_add0("Traverse the resulting dictionary");
 927   traverse(head);
 928
 929   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
 930
 931   xbt_test_add0("Free the dictionary twice");
 932   xbt_dict_free(&head);
 933   xbt_dict_free(&head);
 934
 935   xbt_test_add0("Traverse the resulting dictionary");
 936   traverse(head);
 937 }
 938
 939 XBT_TEST_UNIT("remove", test_dict_remove, "Removing some values")
 940 {
 941   fill(&head);
 942   count(head, 7);
 943   xbt_test_add0("Remove non existing data");
 944   TRY {
 945     debuged_remove(head, "Does not exist");
 946   }
 947   CATCH(e) {
 948     if (e.category != not_found_error)
 949       xbt_test_exception(e);
 950     xbt_ex_free(e);
 951   }
 952   traverse(head);
 953
 954   xbt_dict_free(&head);
 955
 956   xbt_test_add0
 957     ("Remove each data manually (traversing the resulting dictionary each time)");
 958   fill(&head);
 959   debuged_remove(head, "12a");
 960   traverse(head);
 961   count(head, 6);
 962   debuged_remove(head, "12b");
 963   traverse(head);
 964   count(head, 5);
 965   debuged_remove(head, "12");
 966   traverse(head);
 967   count(head, 4);
 968   debuged_remove(head, "123456");
 969   traverse(head);
 970   count(head, 3);
 971   TRY {
 972     debuged_remove(head, "12346");
 973   }
 974   CATCH(e) {
 975     if (e.category != not_found_error)
 976       xbt_test_exception(e);
 977     xbt_ex_free(e);
 978     traverse(head);
 979   }
 980   debuged_remove(head, "1234");
 981   traverse(head);
 982   debuged_remove(head, "123457");
 983   traverse(head);
 984   debuged_remove(head, "123");
 985   traverse(head);
 986   TRY {
 987     debuged_remove(head, "12346");
 988   }
 989   CATCH(e) {
 990     if (e.category != not_found_error)
 991       xbt_test_exception(e);
 992     xbt_ex_free(e);
 993   }
 994   traverse(head);
 995
 996   xbt_test_add0("Free dict, create new fresh one, and then reset the dict");
 997   xbt_dict_free(&head);
 998   fill(&head);
 999   xbt_dict_reset(head);
1000   count(head, 0);
1001   traverse(head);
1002
1003   xbt_test_add0("Free the dictionary twice");
1004   xbt_dict_free(&head);
1005   xbt_dict_free(&head);
1006 }
1007
1008 XBT_TEST_UNIT("nulldata", test_dict_nulldata, "NULL data management")
1009 {
1010   fill(&head);
1011
1012   xbt_test_add0("Store NULL under 'null'");
1013   xbt_dict_set(head, "null", NULL, NULL);
1014   search_ext(head, "null", NULL);
1015
1016   xbt_test_add0("Check whether I see it while traversing...");
1017   {
1018     xbt_dict_cursor_t cursor = NULL;
1019     char *key;
1020     int found = 0;
1021
1022     xbt_dict_foreach(head, cursor, key, data) {
1023       if (!key || !data || strcmp(key, data)) {
1024         xbt_test_log2("Seen:  %s->%s", PRINTF_STR(key), PRINTF_STR(data));
1025       } else {
1026         xbt_test_log1("Seen:  %s", PRINTF_STR(key));
1027       }
1028
1029       if (!strcmp(key, "null"))
1030         found = 1;
1031     }
1032     xbt_test_assert0(found,
1033                      "the key 'null', associated to NULL is not found");
1034   }
1035   xbt_dict_free(&head);
1036 }
1037
1038 #define NB_ELM 20000
1039 #define SIZEOFKEY 1024
1040 static int countelems(xbt_dict_t head)
1041 {
1042   xbt_dict_cursor_t cursor;
1043   char *key;
1044   void *data;
1045   int res = 0;
1046
1047   xbt_dict_foreach(head, cursor, key, data) {
1048     res++;
1049   }
1050   return res;
1051 }
1052
1053 XBT_TEST_UNIT("crash", test_dict_crash, "Crash test")
1054 {
1055   xbt_dict_t head = NULL;
1056   int i, j, k, nb;
1057   char *key;
1058   void *data;
1059
1060   srand((unsigned int) time(NULL));
1061
1062   for (i = 0; i < 10; i++) {
1063     xbt_test_add2("CRASH test number %d (%d to go)", i + 1, 10 - i - 1);
1064     xbt_test_log0("Fill the struct, count its elems and frees the structure");
1065     xbt_test_log1("using 1000 elements with %d chars long randomized keys.",
1066                   SIZEOFKEY);
1067     head = xbt_dict_new();
1068     /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
1069     nb = 0;
1070     for (j = 0; j < 1000; j++) {
1071       char *data = NULL;
1072       key = xbt_malloc(SIZEOFKEY);
1073
1074       do {
1075         for (k = 0; k < SIZEOFKEY - 1; k++)
1076           key[k] = rand() % ('z' - 'a') + 'a';
1077         key[k] = '\0';
1078         /*      printf("[%d %s]\n",j,key); */
1079         data = xbt_dict_get_or_null(head, key);
1080       } while (data != NULL);
1081
1082       xbt_dict_set(head, key, key, &free);
1083       data = xbt_dict_get(head, key);
1084       xbt_test_assert2(!strcmp(key, data),
1085                        "Retrieved value (%s) != Injected value (%s)", key,
1086                        data);
1087
1088       count(head, j + 1);
1089     }
1090     /*    xbt_dict_dump(head,(void (*)(void*))&printf); */
1091     traverse(head);
1092     xbt_dict_free(&head);
1093     xbt_dict_free(&head);
1094   }
1095
1096
1097   head = xbt_dict_new();
1098   xbt_test_add1("Fill %d elements, with keys being the number of element",
1099                 NB_ELM);
1100   for (j = 0; j < NB_ELM; j++) {
1101     /* if (!(j%1000)) { printf("."); fflush(stdout); } */
1102
1103     key = xbt_malloc(10);
1104
1105     sprintf(key, "%d", j);
1106     xbt_dict_set(head, key, key, &free);
1107   }
1108   /*xbt_dict_dump(head,(void (*)(void*))&printf); */
1109
1110   xbt_test_add0("Count the elements (retrieving the key and data for each)");
1111   i = countelems(head);
1112   xbt_test_log1("There is %d elements", i);
1113
1114   xbt_test_add1("Search my %d elements 20 times", NB_ELM);
1115   key = xbt_malloc(10);
1116   for (i = 0; i < 20; i++) {
1117     /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
1118     for (j = 0; j < NB_ELM; j++) {
1119
1120       sprintf(key, "%d", j);
1121       data = xbt_dict_get(head, key);
1122       xbt_test_assert2(!strcmp(key, (char *) data),
1123                        "with get, key=%s != data=%s", key, (char *) data);
1124       data = xbt_dict_get_ext(head, key, strlen(key));
1125       xbt_test_assert2(!strcmp(key, (char *) data),
1126                        "with get_ext, key=%s != data=%s", key, (char *) data);
1127     }
1128   }
1129   free(key);
1130
1131   xbt_test_add1("Remove my %d elements", NB_ELM);
1132   key = xbt_malloc(10);
1133   for (j = 0; j < NB_ELM; j++) {
1134     /* if (!(j%10000)) printf("."); fflush(stdout); */
1135
1136     sprintf(key, "%d", j);
1137     xbt_dict_remove(head, key);
1138   }
1139   free(key);
1140
1141
1142   xbt_test_add0("Free the structure (twice)");
1143   xbt_dict_free(&head);
1144   xbt_dict_free(&head);
1145 }
1146
1147 static void str_free(void *s)
1148 {
1149   char *c = *(char **) s;
1150   free(c);
1151 }
1152
1153 XBT_TEST_UNIT("multicrash", test_dict_multicrash, "Multi-dict crash test")
1154 {
1155
1156 #undef NB_ELM
1157 #define NB_ELM 100              /*00 */
1158 #define DEPTH 5
1159 #define KEY_SIZE 512
1160 #define NB_TEST 20              /*20 */
1161   int verbose = 0;
1162
1163   xbt_dict_t mdict = NULL;
1164   int i, j, k, l;
1165   xbt_dynar_t keys = xbt_dynar_new(sizeof(char *), str_free);
1166   void *data;
1167   char *key;
1168
1169
1170   xbt_test_add0("Generic multicache CRASH test");
1171   xbt_test_log4(" Fill the struct and frees it %d times, using %d elements, "
1172                 "depth of multicache=%d, key size=%d",
1173                 NB_TEST, NB_ELM, DEPTH, KEY_SIZE);
1174
1175   for (l = 0; l < DEPTH; l++) {
1176     key = xbt_malloc(KEY_SIZE);
1177     xbt_dynar_push(keys, &key);
1178   }
1179
1180   for (i = 0; i < NB_TEST; i++) {
1181     mdict = xbt_dict_new();
1182     VERB1("mdict=%p", mdict);
1183     if (verbose > 0)
1184       printf("Test %d\n", i);
1185     /* else if (i%10) printf("."); else printf("%d",i/10); */
1186
1187     for (j = 0; j < NB_ELM; j++) {
1188       if (verbose > 0)
1189         printf("  Add {");
1190
1191       for (l = 0; l < DEPTH; l++) {
1192         key = *(char **) xbt_dynar_get_ptr(keys, l);
1193
1194         for (k = 0; k < KEY_SIZE - 1; k++)
1195           key[k] = rand() % ('z' - 'a') + 'a';
1196
1197         key[k] = '\0';
1198
1199         if (verbose > 0)
1200           printf("%p=%s %s ", key, key, (l < DEPTH - 1 ? ";" : "}"));
1201       }
1202       if (verbose > 0)
1203         printf("in multitree %p.\n", mdict);
1204
1205       xbt_multidict_set(mdict, keys, xbt_strdup(key), free);
1206
1207       data = xbt_multidict_get(mdict, keys);
1208
1209       xbt_test_assert2(data && !strcmp((char *) data, key),
1210                        "Retrieved value (%s) does not match the given one (%s)\n",
1211                        (char *) data, key);
1212     }
1213     xbt_dict_free(&mdict);
1214   }
1215
1216   xbt_dynar_free(&keys);
1217
1218   /*  if (verbose>0)
1219      xbt_dict_dump(mdict,&xbt_dict_print); */
1220
1221   xbt_dict_free(&mdict);
1222   xbt_dynar_free(&keys);
1223
1224 }
1225 #endif /* SIMGRID_TEST */