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