Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Make dictionary internal table dynamic (and automatically resized).
[simgrid.git] / 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 */