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