src/xbt/dict.c

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