Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Ensure that the mallocator are really inactive when running MC
[simgrid.git] / src / xbt / dict.c
1 /* dict - a generic dictionary, variation over hash table                   */
2
3 /* Copyright (c) 2004-2011. The SimGrid Team.
4  * All rights reserved.                                                     */
5
6 /* This program is free software; you can redistribute it and/or modify it
7  * under the terms of the license (GNU LGPL) which comes with this package. */
8
9 #include <string.h>
10 #include <stdio.h>
11 #include "xbt/ex.h"
12 #include "xbt/log.h"
13 #include "xbt/mallocator.h"
14 #include "xbt_modinter.h"
15 #include "xbt/str.h"
16 #include "dict_private.h"
17
18 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_dict, xbt,
19                                 "Dictionaries provide the same functionalities than hash tables");
20
21 /**
22  * \brief Constructor
23  * \return pointer to the destination
24  * \see xbt_dict_free()
25  *
26  * Creates and initialize a new dictionary with a default hashtable size.
27  * The dictionary is heterogeneous: each element can have a different free
28  * function.
29  */
30 xbt_dict_t xbt_dict_new(void)
31 {
32   xbt_dict_t dict = xbt_dict_new_homogeneous(NULL);
33   dict->homogeneous = 0;
34
35   return dict;
36 }
37
38 /**
39  * \brief Constructor
40  * \param free_ctn function to call with (\a data as argument) when
41  *        \a data is removed from the dictionary
42  * \return pointer to the destination
43  * \see xbt_dict_new(), xbt_dict_free()
44  *
45  * Creates and initialize a new dictionary with a default hashtable size.
46  * The dictionary is homogeneous: each element share the same free function.
47  */
48 xbt_dict_t xbt_dict_new_homogeneous(void_f_pvoid_t free_ctn)
49 {
50   xbt_dict_t dict;
51
52   dict = xbt_new(s_xbt_dict_t, 1);
53   dict->free_f = free_ctn;
54   dict->table_size = 127;
55   dict->table = xbt_new0(xbt_dictelm_t, dict->table_size + 1);
56   dict->count = 0;
57   dict->fill = 0;
58   dict->homogeneous = 1;
59
60   return dict;
61 }
62
63 /**
64  * \brief Destructor
65  * \param dict the dictionary to be freed
66  *
67  * Frees a dictionary with all the data
68  */
69 void xbt_dict_free(xbt_dict_t * dict)
70 {
71   int i;
72   xbt_dictelm_t current, previous;
73   int table_size;
74   xbt_dictelm_t *table;
75
76   //  if ( *dict )  xbt_dict_dump_sizes(*dict);
77
78   if (dict != NULL && *dict != NULL) {
79     table_size = (*dict)->table_size;
80     table = (*dict)->table;
81     /* Warning: the size of the table is 'table_size+1'...
82      * This is because table_size is used as a binary mask in xbt_dict_rehash */
83     for (i = 0; (*dict)->count && i <= table_size; i++) {
84       current = table[i];
85       while (current != NULL) {
86         previous = current;
87         current = current->next;
88         xbt_dictelm_free(*dict, previous);
89         (*dict)->count--;
90       }
91     }
92     xbt_free(table);
93     xbt_free(*dict);
94     *dict = NULL;
95   }
96 }
97
98 /**
99  * Returns the amount of elements in the dict
100  */
101 XBT_INLINE unsigned int xbt_dict_size(xbt_dict_t dict)
102 {
103   return (dict ? (unsigned int) dict->count : (unsigned int) 0);
104 }
105
106 /* Expend the size of the dict */
107 static void xbt_dict_rehash(xbt_dict_t dict)
108 {
109   const int oldsize = dict->table_size + 1;
110   register int newsize = oldsize * 2;
111   register int i;
112   register xbt_dictelm_t *currcell;
113   register xbt_dictelm_t *twincell;
114   register xbt_dictelm_t bucklet;
115   register xbt_dictelm_t *pprev;
116
117   currcell =
118       (xbt_dictelm_t *) xbt_realloc((char *) dict->table,
119                                     newsize * sizeof(xbt_dictelm_t));
120   memset(&currcell[oldsize], 0, oldsize * sizeof(xbt_dictelm_t));       /* zero second half */
121   dict->table_size = --newsize;
122   dict->table = currcell;
123   XBT_DEBUG("REHASH (%d->%d)", oldsize, newsize);
124
125   for (i = 0; i < oldsize; i++, currcell++) {
126     if (!*currcell)             /* empty cell */
127       continue;
128     twincell = currcell + oldsize;
129     for (pprev = currcell, bucklet = *currcell; bucklet; bucklet = *pprev) {
130       /* Since we use "& size" instead of "%size" and since the size was doubled,
131          each bucklet of this cell must either :
132          - stay  in  cell i (ie, currcell)
133          - go to the cell i+oldsize (ie, twincell) */
134       if ((bucklet->hash_code & newsize) != i) {        /* Move to b */
135         *pprev = bucklet->next;
136         bucklet->next = *twincell;
137         if (!*twincell)
138           dict->fill++;
139         *twincell = bucklet;
140         continue;
141       } else {
142         pprev = &bucklet->next;
143       }
144
145     }
146
147     if (!*currcell)             /* everything moved */
148       dict->fill--;
149   }
150 }
151
152 /**
153  * \brief Add data to the dict (arbitrary key)
154  * \param dict the container
155  * \param key the key to set the new data
156  * \param key_len the size of the \a key
157  * \param data the data to add in the dict
158  * \param free_ctn function to call with (\a data as argument) when
159  *        \a data is removed from the dictionary
160  *
161  * Set the \a data in the structure under the \a key, which can be any kind
162  * of data, as long as its length is provided in \a key_len.
163  */
164 XBT_INLINE void xbt_dict_set_ext(xbt_dict_t dict,
165                                  const char *key, int key_len,
166                                  void *data, void_f_pvoid_t free_ctn)
167 {
168
169   unsigned int hash_code = xbt_str_hash_ext(key, key_len);
170
171   xbt_dictelm_t current, previous = NULL;
172   xbt_assert(dict);
173
174   XBT_DEBUG("ADD %.*s hash = %u, size = %d, & = %u", key_len, key, hash_code,
175          dict->table_size, hash_code & dict->table_size);
176   current = dict->table[hash_code & dict->table_size];
177   while (current != NULL &&
178          (hash_code != current->hash_code || key_len != current->key_len
179           || memcmp(key, current->key, key_len))) {
180     previous = current;
181     current = current->next;
182   }
183
184   if (current == NULL) {
185     /* this key doesn't exist yet */
186     current = xbt_dictelm_new(dict, key, key_len, hash_code, data, free_ctn);
187     dict->count++;
188     if (previous == NULL) {
189       dict->table[hash_code & dict->table_size] = current;
190       dict->fill++;
191       if ((dict->fill * 100) / (dict->table_size + 1) > MAX_FILL_PERCENT)
192         xbt_dict_rehash(dict);
193     } else {
194       previous->next = current;
195     }
196   } else {
197     XBT_DEBUG("Replace %.*s by %.*s under key %.*s",
198            key_len, (char *) current->content,
199            key_len, (char *) data, key_len, (char *) key);
200     /* there is already an element with the same key: overwrite it */
201     xbt_dictelm_set_data(dict, current, data, free_ctn);
202   }
203 }
204
205 /**
206  * \brief Add data to the dict (null-terminated key)
207  *
208  * \param dict the dict
209  * \param key the key to set the new data
210  * \param data the data to add in the dict
211  * \param free_ctn function to call with (\a data as argument) when
212  *        \a data is removed from the dictionary
213  *
214  * set the \a data in the structure under the \a key, which is a
215  * null terminated string.
216  */
217 XBT_INLINE void xbt_dict_set(xbt_dict_t dict,
218                              const char *key, void *data,
219                              void_f_pvoid_t free_ctn)
220 {
221
222   xbt_dict_set_ext(dict, key, strlen(key), data, free_ctn);
223 }
224
225 /**
226  * \brief Retrieve data from the dict (arbitrary key)
227  *
228  * \param dict the dealer of data
229  * \param key the key to find data
230  * \param key_len the size of the \a key
231  * \return the data that we are looking for
232  *
233  * Search the given \a key. Throws not_found_error when not found.
234  */
235 XBT_INLINE void *xbt_dict_get_ext(xbt_dict_t dict, const char *key,
236                                   int key_len)
237 {
238
239
240   unsigned int hash_code = xbt_str_hash_ext(key, key_len);
241   xbt_dictelm_t current;
242
243   xbt_assert(dict);
244
245   current = dict->table[hash_code & dict->table_size];
246   while (current != NULL &&
247          (hash_code != current->hash_code || key_len != current->key_len
248           || memcmp(key, current->key, key_len))) {
249     current = current->next;
250   }
251
252   if (current == NULL)
253     THROWF(not_found_error, 0, "key %.*s not found", key_len, key);
254
255   return current->content;
256 }
257
258 /**
259  * \brief like xbt_dict_get_ext(), but returning NULL when not found
260  */
261 void *xbt_dict_get_or_null_ext(xbt_dict_t dict, const char *key,
262                                int key_len)
263 {
264
265   unsigned int hash_code = xbt_str_hash_ext(key, key_len);
266   xbt_dictelm_t current;
267
268   xbt_assert(dict);
269
270   current = dict->table[hash_code & dict->table_size];
271   while (current != NULL &&
272          (hash_code != current->hash_code || key_len != current->key_len
273           || memcmp(key, current->key, key_len))) {
274     current = current->next;
275   }
276
277   if (current == NULL)
278     return NULL;
279
280   return current->content;
281 }
282
283 /**
284  * @brief retrieve the key associated to that object. Warning, that's a linear search
285  *
286  * Returns NULL if the object cannot be found
287  */
288 char *xbt_dict_get_key(xbt_dict_t dict, const void *data)
289 {
290   int i;
291   xbt_dictelm_t current;
292
293
294   for (i = 0; i <= dict->table_size; i++) {
295     current = dict->table[i];
296     while (current != NULL) {
297       if (current->content == data)
298         return current->key;
299       current = current->next;
300     }
301   }
302
303   return NULL;
304 }
305
306 /**
307  * \brief Retrieve data from the dict (null-terminated key)
308  *
309  * \param dict the dealer of data
310  * \param key the key to find data
311  * \return the data that we are looking for
312  *
313  * Search the given \a key. Throws not_found_error when not found.
314  * Check xbt_dict_get_or_null() for a version returning NULL without exception when
315  * not found.
316  */
317 XBT_INLINE void *xbt_dict_get(xbt_dict_t dict, const char *key)
318 {
319
320   unsigned int hash_code = xbt_str_hash(key);
321   xbt_dictelm_t current;
322
323   xbt_assert(dict);
324
325   current = dict->table[hash_code & dict->table_size];
326   while (current != NULL
327          && (hash_code != current->hash_code || strcmp(key, current->key)))
328     current = current->next;
329
330   if (current == NULL)
331     THROWF(not_found_error, 0, "key %s not found", key);
332
333   return current->content;
334 }
335
336 /**
337  * \brief like xbt_dict_get(), but returning NULL when not found
338  */
339 XBT_INLINE void *xbt_dict_get_or_null(xbt_dict_t dict, const char *key)
340 {
341   unsigned int hash_code = xbt_str_hash(key);
342   xbt_dictelm_t current;
343
344   xbt_assert(dict);
345
346   current = dict->table[hash_code & dict->table_size];
347   while (current != NULL &&
348          (hash_code != current->hash_code || strcmp(key, current->key)))
349     current = current->next;
350
351   if (current == NULL)
352     return NULL;
353
354   return current->content;
355 }
356
357
358 /**
359  * \brief Remove data from the dict (arbitrary key)
360  *
361  * \param dict the trash can
362  * \param key the key of the data to be removed
363  * \param key_len the size of the \a key
364  *
365  * Remove the entry associated with the given \a key (throws not_found)
366  */
367 XBT_INLINE void xbt_dict_remove_ext(xbt_dict_t dict, const char *key,
368                                     int key_len)
369 {
370
371
372   unsigned int hash_code = xbt_str_hash_ext(key, key_len);
373   xbt_dictelm_t current, previous = NULL;
374
375   xbt_assert(dict);
376
377   //  fprintf(stderr,"RM %.*s hash = %d, size = %d, & = %d\n",key_len,key,hash_code, dict->table_size, hash_code & dict->table_size);
378   current = dict->table[hash_code & dict->table_size];
379   while (current != NULL &&
380          (hash_code != current->hash_code || key_len != current->key_len
381           || strncmp(key, current->key, key_len))) {
382     previous = current;         /* save the previous node */
383     current = current->next;
384   }
385
386   if (current == NULL)
387     THROWF(not_found_error, 0, "key %.*s not found", key_len, key);
388
389   if (previous != NULL) {
390     previous->next = current->next;
391   } else {
392     dict->table[hash_code & dict->table_size] = current->next;
393   }
394
395   if (!dict->table[hash_code & dict->table_size])
396     dict->fill--;
397
398   xbt_dictelm_free(dict, current);
399   dict->count--;
400 }
401
402
403
404 /**
405  * \brief Remove data from the dict (null-terminated key)
406  *
407  * \param dict the dict
408  * \param key the key of the data to be removed
409  *
410  * Remove the entry associated with the given \a key
411  */
412 XBT_INLINE void xbt_dict_remove(xbt_dict_t dict, const char *key)
413 {
414   xbt_dict_remove_ext(dict, key, strlen(key));
415 }
416
417 #ifdef XBT_USE_DEPRECATED
418 /**
419  * \brief Add data to the dict (arbitrary key)
420  * \param dict the container
421  * \param key the key to set the new data
422  * \param data the data to add in the dict
423  *
424  * Set the \a data in the structure under the \a key.
425  * Both \a data and \a key are considered as uintptr_t.
426  */
427 XBT_INLINE void xbt_dicti_set(xbt_dict_t dict,
428                               uintptr_t key, uintptr_t data)
429 {
430   xbt_dict_set_ext(dict, (void *)&key, sizeof key, (void*)data, NULL);
431 }
432
433 /**
434  * \brief Retrieve data from the dict (key considered as a uintptr_t)
435  *
436  * \param dict the dealer of data
437  * \param key the key to find data
438  * \return the data that we are looking for (or 0 if not found)
439  *
440  * Mixing uintptr_t keys with regular keys in the same dict is discouraged
441  */
442 XBT_INLINE uintptr_t xbt_dicti_get(xbt_dict_t dict, uintptr_t key)
443 {
444   return (uintptr_t)xbt_dict_get_or_null_ext(dict, (void *)&key, sizeof key);
445 }
446
447 /** Remove a uintptr_t key from the dict */
448 XBT_INLINE void xbt_dicti_remove(xbt_dict_t dict, uintptr_t key)
449 {
450   xbt_dict_remove_ext(dict, (void *)&key, sizeof key);
451 }
452 #endif
453
454 /**
455  * \brief Remove all data from the dict
456  * \param dict the dict
457  */
458 void xbt_dict_reset(xbt_dict_t dict)
459 {
460
461   int i;
462   xbt_dictelm_t current, previous = NULL;
463
464   xbt_assert(dict);
465
466   if (dict->count == 0)
467     return;
468
469   for (i = 0; i <= dict->table_size; i++) {
470     current = dict->table[i];
471     while (current != NULL) {
472       previous = current;
473       current = current->next;
474       xbt_dictelm_free(dict, previous);
475     }
476     dict->table[i] = NULL;
477   }
478
479   dict->count = 0;
480   dict->fill = 0;
481 }
482
483 /**
484  * \brief Return the number of elements in the dict.
485  * \param dict a dictionary
486  */
487 XBT_INLINE int xbt_dict_length(xbt_dict_t dict)
488 {
489   xbt_assert(dict);
490
491   return dict->count;
492 }
493
494 /** @brief function to be used in xbt_dict_dump as long as the stored values are strings */
495 void xbt_dict_dump_output_string(void *s)
496 {
497   fputs(s, stdout);
498 }
499
500 /**
501  * \brief test if the dict is empty or not
502  */
503 XBT_INLINE int xbt_dict_is_empty(xbt_dict_t dict)
504 {
505   return !dict || (xbt_dict_length(dict) == 0);
506 }
507
508 /**
509  * \brief Outputs the content of the structure (debugging purpose)
510  *
511  * \param dict the exibitionist
512  * \param output a function to dump each data in the tree (check @ref xbt_dict_dump_output_string)
513  *
514  * Outputs the content of the structure. (for debugging purpose). \a output is a
515  * function to output the data. If NULL, data won't be displayed.
516  */
517
518 void xbt_dict_dump(xbt_dict_t dict, void_f_pvoid_t output)
519 {
520   int i;
521   xbt_dictelm_t element;
522   printf("Dict %p:\n", dict);
523   if (dict != NULL) {
524     for (i = 0; i < dict->table_size; i++) {
525       element = dict->table[i];
526       if (element) {
527         printf("[\n");
528         while (element != NULL) {
529           printf(" %s -> '", element->key);
530           if (output != NULL) {
531             output(element->content);
532           }
533           printf("'\n");
534           element = element->next;
535         }
536         printf("]\n");
537       } else {
538         printf("[]\n");
539       }
540     }
541   }
542 }
543
544 xbt_dynar_t all_sizes = NULL;
545 /** @brief shows some debugging info about the bucklet repartition */
546 void xbt_dict_dump_sizes(xbt_dict_t dict)
547 {
548
549   int i;
550   unsigned int count;
551   unsigned int size;
552   xbt_dictelm_t element;
553   xbt_dynar_t sizes = xbt_dynar_new(sizeof(int), NULL);
554
555   printf("Dict %p: %d bucklets, %d used cells (of %d) ", dict, dict->count,
556          dict->fill, dict->table_size);
557   if (dict != NULL) {
558     for (i = 0; i < dict->table_size; i++) {
559       element = dict->table[i];
560       size = 0;
561       if (element) {
562         while (element != NULL) {
563           size++;
564           element = element->next;
565         }
566       }
567       if (xbt_dynar_length(sizes) <= size) {
568         int prevsize = 1;
569         xbt_dynar_set(sizes, size, &prevsize);
570       } else {
571         int prevsize;
572         xbt_dynar_get_cpy(sizes, size, &prevsize);
573         prevsize++;
574         xbt_dynar_set(sizes, size, &prevsize);
575       }
576     }
577     if (!all_sizes)
578       all_sizes = xbt_dynar_new(sizeof(int), NULL);
579
580     xbt_dynar_foreach(sizes, count, size) {
581       /* Copy values of this one into all_sizes */
582       int prevcount;
583       if (xbt_dynar_length(all_sizes) <= count) {
584         prevcount = size;
585         xbt_dynar_set(all_sizes, count, &prevcount);
586       } else {
587         xbt_dynar_get_cpy(all_sizes, count, &prevcount);
588         prevcount += size;
589         xbt_dynar_set(all_sizes, count, &prevcount);
590       }
591
592       /* Report current sizes */
593       if (count == 0)
594         continue;
595       if (size == 0)
596         continue;
597       printf("%uelm x %u cells; ", count, size);
598     }
599   }
600   printf("\n");
601   xbt_dynar_free(&sizes);
602 }
603
604 /**
605  * Create the dict mallocators.
606  * This is an internal XBT function called during the lib initialization.
607  * It can be used several times to recreate the mallocator, for example when you switch to MC mode
608  */
609 void xbt_dict_preinit(void)
610 {
611   dict_elm_mallocator = xbt_mallocator_new(256,
612                                            dict_elm_mallocator_new_f,
613                                            dict_elm_mallocator_free_f,
614                                            dict_elm_mallocator_reset_f);
615   dict_het_elm_mallocator = xbt_mallocator_new(256,
616                                                dict_het_elm_mallocator_new_f,
617                                                dict_het_elm_mallocator_free_f,
618                                                dict_het_elm_mallocator_reset_f);
619 }
620
621 /**
622  * Destroy the dict mallocators.
623  * This is an internal XBT function during the lib initialization
624  */
625 void xbt_dict_postexit(void)
626 {
627   if (dict_elm_mallocator != NULL) {
628     xbt_mallocator_free(dict_elm_mallocator);
629     dict_elm_mallocator = NULL;
630     xbt_mallocator_free(dict_het_elm_mallocator);
631     dict_het_elm_mallocator = NULL;
632   }
633   if (all_sizes) {
634     unsigned int count;
635     int size;
636     double avg = 0;
637     int total_count = 0;
638     printf("Overall stats:");
639     xbt_dynar_foreach(all_sizes, count, size) {
640       if (count == 0)
641         continue;
642       if (size == 0)
643         continue;
644       printf("%uelm x %d cells; ", count, size);
645       avg += count * size;
646       total_count += size;
647     }
648     printf("; %f elm per cell\n", avg / (double) total_count);
649   }
650 }
651
652 #ifdef SIMGRID_TEST
653 #include "xbt.h"
654 #include "xbt/ex.h"
655 #include "portable.h"
656
657 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(xbt_dict);
658
659 XBT_TEST_SUITE("dict", "Dict data container");
660
661 static void print_str(void *str)
662 {
663   printf("%s", (char *) PRINTF_STR(str));
664 }
665
666 static void debuged_add_ext(xbt_dict_t head, const char *key,
667                             const char *data_to_fill, void_f_pvoid_t free_f)
668 {
669   char *data = xbt_strdup(data_to_fill);
670
671   xbt_test_log("Add %s under %s", PRINTF_STR(data_to_fill),
672                 PRINTF_STR(key));
673
674   xbt_dict_set(head, key, data, free_f);
675   if (XBT_LOG_ISENABLED(xbt_dict, xbt_log_priority_debug)) {
676     xbt_dict_dump(head, (void (*)(void *)) &printf);
677     fflush(stdout);
678   }
679 }
680
681 static void debuged_add(xbt_dict_t head, const char *key, void_f_pvoid_t free_f)
682 {
683   debuged_add_ext(head, key, key, free_f);
684 }
685
686 static void fill(xbt_dict_t * head, int homogeneous)
687 {
688   void_f_pvoid_t free_f = homogeneous ? NULL : &free;
689
690   xbt_test_add("Fill in the dictionnary");
691
692   *head = homogeneous ? xbt_dict_new_homogeneous(&free) : xbt_dict_new();
693   debuged_add(*head, "12", free_f);
694   debuged_add(*head, "12a", free_f);
695   debuged_add(*head, "12b", free_f);
696   debuged_add(*head, "123", free_f);
697   debuged_add(*head, "123456", free_f);
698   /* Child becomes child of what to add */
699   debuged_add(*head, "1234", free_f);
700   /* Need of common ancestor */
701   debuged_add(*head, "123457", free_f);
702 }
703
704
705 static void search_ext(xbt_dict_t head, const char *key, const char *data)
706 {
707   void *found;
708
709   xbt_test_add("Search %s", key);
710   found = xbt_dict_get(head, key);
711   xbt_test_log("Found %s", (char *) found);
712   if (data)
713     xbt_test_assert(found,
714                      "data do not match expectations: found NULL while searching for %s",
715                      data);
716   if (found)
717     xbt_test_assert(!strcmp((char *) data, found),
718                      "data do not match expectations: found %s while searching for %s",
719                      (char *) found, data);
720 }
721
722 static void search(xbt_dict_t head, const char *key)
723 {
724   search_ext(head, key, key);
725 }
726
727 static void debuged_remove(xbt_dict_t head, const char *key)
728 {
729
730   xbt_test_add("Remove '%s'", PRINTF_STR(key));
731   xbt_dict_remove(head, key);
732   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
733 }
734
735
736 static void traverse(xbt_dict_t head)
737 {
738   xbt_dict_cursor_t cursor = NULL;
739   char *key;
740   char *data;
741   int i = 0;
742
743   xbt_dict_foreach(head, cursor, key, data) {
744     if (!key || !data || strcmp(key, data)) {
745       xbt_test_log("Seen #%d:  %s->%s", ++i, PRINTF_STR(key),
746                     PRINTF_STR(data));
747     } else {
748       xbt_test_log("Seen #%d:  %s", ++i, PRINTF_STR(key));
749     }
750     xbt_test_assert(!data || !strcmp(key, data),
751                      "Key(%s) != value(%s). Aborting", key, data);
752   }
753 }
754
755 static void search_not_found(xbt_dict_t head, const char *data)
756 {
757   int ok = 0;
758   xbt_ex_t e;
759
760   xbt_test_add("Search %s (expected not to be found)", data);
761
762   TRY {
763     data = xbt_dict_get(head, data);
764     THROWF(unknown_error, 0,
765            "Found something which shouldn't be there (%s)", data);
766   }
767   CATCH(e) {
768     if (e.category != not_found_error)
769       xbt_test_exception(e);
770     xbt_ex_free(e);
771     ok = 1;
772   }
773   xbt_test_assert(ok, "Exception not raised");
774 }
775
776 static void count(xbt_dict_t dict, int length)
777 {
778   xbt_dict_cursor_t cursor;
779   char *key;
780   void *data;
781   int effective = 0;
782
783
784   xbt_test_add("Count elements (expecting %d)", length);
785   xbt_test_assert(xbt_dict_length(dict) == length,
786                    "Announced length(%d) != %d.", xbt_dict_length(dict),
787                    length);
788
789   xbt_dict_foreach(dict, cursor, key, data)
790       effective++;
791
792   xbt_test_assert(effective == length, "Effective length(%d) != %d.",
793                    effective, length);
794
795 }
796
797 static void count_check_get_key(xbt_dict_t dict, int length)
798 {
799   xbt_dict_cursor_t cursor;
800   char *key;
801   _XBT_GNUC_UNUSED char *key2;
802   void *data;
803   int effective = 0;
804
805
806   xbt_test_add
807       ("Count elements (expecting %d), and test the getkey function",
808        length);
809   xbt_test_assert(xbt_dict_length(dict) == length,
810                    "Announced length(%d) != %d.", xbt_dict_length(dict),
811                    length);
812
813   xbt_dict_foreach(dict, cursor, key, data) {
814     effective++;
815     key2 = xbt_dict_get_key(dict, data);
816     xbt_assert(!strcmp(key, key2),
817                 "The data was registered under %s instead of %s as expected",
818                 key2, key);
819   }
820
821   xbt_test_assert(effective == length, "Effective length(%d) != %d.",
822                    effective, length);
823
824 }
825
826 xbt_ex_t e;
827 xbt_dict_t head = NULL;
828 char *data;
829
830 static void basic_test(int homogeneous)
831 {
832   void_f_pvoid_t free_f;
833
834   xbt_test_add("Traversal the null dictionary");
835   traverse(head);
836
837   xbt_test_add("Traversal and search the empty dictionary");
838   head = homogeneous ? xbt_dict_new_homogeneous(&free) : xbt_dict_new();
839   traverse(head);
840   TRY {
841     debuged_remove(head, "12346");
842   }
843   CATCH(e) {
844     if (e.category != not_found_error)
845       xbt_test_exception(e);
846     xbt_ex_free(e);
847   }
848   xbt_dict_free(&head);
849
850   free_f = homogeneous ? NULL : &free;
851
852   xbt_test_add("Traverse the full dictionary");
853   fill(&head, homogeneous);
854   count_check_get_key(head, 7);
855
856   debuged_add_ext(head, "toto", "tutu", free_f);
857   search_ext(head, "toto", "tutu");
858   debuged_remove(head, "toto");
859
860   search(head, "12a");
861   traverse(head);
862
863   xbt_test_add("Free the dictionary (twice)");
864   xbt_dict_free(&head);
865   xbt_dict_free(&head);
866
867   /* CHANGING */
868   fill(&head, homogeneous);
869   count_check_get_key(head, 7);
870   xbt_test_add("Change 123 to 'Changed 123'");
871   xbt_dict_set(head, "123", strdup("Changed 123"), free_f);
872   count_check_get_key(head, 7);
873
874   xbt_test_add("Change 123 back to '123'");
875   xbt_dict_set(head, "123", strdup("123"), free_f);
876   count_check_get_key(head, 7);
877
878   xbt_test_add("Change 12a to 'Dummy 12a'");
879   xbt_dict_set(head, "12a", strdup("Dummy 12a"), free_f);
880   count_check_get_key(head, 7);
881
882   xbt_test_add("Change 12a to '12a'");
883   xbt_dict_set(head, "12a", strdup("12a"), free_f);
884   count_check_get_key(head, 7);
885
886   xbt_test_add("Traverse the resulting dictionary");
887   traverse(head);
888
889   /* RETRIEVE */
890   xbt_test_add("Search 123");
891   data = xbt_dict_get(head, "123");
892   xbt_test_assert(data);
893   xbt_test_assert(!strcmp("123", data));
894
895   search_not_found(head, "Can't be found");
896   search_not_found(head, "123 Can't be found");
897   search_not_found(head, "12345678 NOT");
898
899   search(head, "12a");
900   search(head, "12b");
901   search(head, "12");
902   search(head, "123456");
903   search(head, "1234");
904   search(head, "123457");
905
906   xbt_test_add("Traverse the resulting dictionary");
907   traverse(head);
908
909   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
910
911   xbt_test_add("Free the dictionary twice");
912   xbt_dict_free(&head);
913   xbt_dict_free(&head);
914
915   xbt_test_add("Traverse the resulting dictionary");
916   traverse(head);
917 }
918
919 XBT_TEST_UNIT("basic_heterogeneous", test_dict_basic_heterogeneous, "Basic usage: change, retrieve, traverse: heterogeneous dict")
920 {
921   basic_test(0);
922 }
923
924 XBT_TEST_UNIT("basic_homogeneous", test_dict_basic_homogeneous, "Basic usage: change, retrieve, traverse: homogeneous dict")
925 {
926   basic_test(1);
927 }
928
929 static void remove_test(int homogeneous)
930 {
931   fill(&head, homogeneous);
932   count(head, 7);
933   xbt_test_add("Remove non existing data");
934   TRY {
935     debuged_remove(head, "Does not exist");
936   }
937   CATCH(e) {
938     if (e.category != not_found_error)
939       xbt_test_exception(e);
940     xbt_ex_free(e);
941   }
942   traverse(head);
943
944   xbt_dict_free(&head);
945
946   xbt_test_add
947       ("Remove each data manually (traversing the resulting dictionary each time)");
948   fill(&head, homogeneous);
949   debuged_remove(head, "12a");
950   traverse(head);
951   count(head, 6);
952   debuged_remove(head, "12b");
953   traverse(head);
954   count(head, 5);
955   debuged_remove(head, "12");
956   traverse(head);
957   count(head, 4);
958   debuged_remove(head, "123456");
959   traverse(head);
960   count(head, 3);
961   TRY {
962     debuged_remove(head, "12346");
963   }
964   CATCH(e) {
965     if (e.category != not_found_error)
966       xbt_test_exception(e);
967     xbt_ex_free(e);
968     traverse(head);
969   }
970   debuged_remove(head, "1234");
971   traverse(head);
972   debuged_remove(head, "123457");
973   traverse(head);
974   debuged_remove(head, "123");
975   traverse(head);
976   TRY {
977     debuged_remove(head, "12346");
978   }
979   CATCH(e) {
980     if (e.category != not_found_error)
981       xbt_test_exception(e);
982     xbt_ex_free(e);
983   }
984   traverse(head);
985
986   xbt_test_add
987       ("Free dict, create new fresh one, and then reset the dict");
988   xbt_dict_free(&head);
989   fill(&head, homogeneous);
990   xbt_dict_reset(head);
991   count(head, 0);
992   traverse(head);
993
994   xbt_test_add("Free the dictionary twice");
995   xbt_dict_free(&head);
996   xbt_dict_free(&head);
997 }
998
999 XBT_TEST_UNIT("remove_heterogeneous", test_dict_remove_heterogeneous, "Removing some values: heterogeneous dict")
1000 {
1001   remove_test(0);
1002 }
1003
1004 XBT_TEST_UNIT("remove_homogeneous", test_dict_remove_homogeneous, "Removing some values: homogeneous dict")
1005 {
1006   remove_test(1);
1007 }
1008
1009 XBT_TEST_UNIT("nulldata", test_dict_nulldata, "NULL data management")
1010 {
1011   fill(&head, 1);
1012
1013   xbt_test_add("Store NULL under 'null'");
1014   xbt_dict_set(head, "null", NULL, NULL);
1015   search_ext(head, "null", NULL);
1016
1017   xbt_test_add("Check whether I see it while traversing...");
1018   {
1019     xbt_dict_cursor_t cursor = NULL;
1020     char *key;
1021     int found = 0;
1022
1023     xbt_dict_foreach(head, cursor, key, data) {
1024       if (!key || !data || strcmp(key, data)) {
1025         xbt_test_log("Seen:  %s->%s", PRINTF_STR(key), PRINTF_STR(data));
1026       } else {
1027         xbt_test_log("Seen:  %s", PRINTF_STR(key));
1028       }
1029
1030       if (!strcmp(key, "null"))
1031         found = 1;
1032     }
1033     xbt_test_assert(found,
1034                      "the key 'null', associated to NULL is not found");
1035   }
1036   xbt_dict_free(&head);
1037 }
1038
1039 #define NB_ELM 20000
1040 #define SIZEOFKEY 1024
1041 static int countelems(xbt_dict_t head)
1042 {
1043   xbt_dict_cursor_t cursor;
1044   char *key;
1045   void *data;
1046   int res = 0;
1047
1048   xbt_dict_foreach(head, cursor, key, data) {
1049     res++;
1050   }
1051   return res;
1052 }
1053
1054 XBT_TEST_UNIT("crash", test_dict_crash, "Crash test")
1055 {
1056   xbt_dict_t head = NULL;
1057   int i, j, k;
1058   char *key;
1059
1060   srand((unsigned int) time(NULL));
1061
1062   for (i = 0; i < 10; i++) {
1063     xbt_test_add("CRASH test number %d (%d to go)", i + 1, 10 - i - 1);
1064     xbt_test_log
1065         ("Fill the struct, count its elems and frees the structure");
1066     xbt_test_log
1067         ("using 1000 elements with %d chars long randomized keys.",
1068          SIZEOFKEY);
1069     head = xbt_dict_new();
1070     /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
1071     for (j = 0; j < 1000; j++) {
1072       char *data = NULL;
1073       key = xbt_malloc(SIZEOFKEY);
1074
1075       do {
1076         for (k = 0; k < SIZEOFKEY - 1; k++)
1077           key[k] = rand() % ('z' - 'a') + 'a';
1078         key[k] = '\0';
1079         /*      printf("[%d %s]\n",j,key); */
1080         data = xbt_dict_get_or_null(head, key);
1081       } while (data != NULL);
1082
1083       xbt_dict_set(head, key, key, &free);
1084       data = xbt_dict_get(head, key);
1085       xbt_test_assert(!strcmp(key, data),
1086                        "Retrieved value (%s) != Injected value (%s)", key,
1087                        data);
1088
1089       count(head, j + 1);
1090     }
1091     /*    xbt_dict_dump(head,(void (*)(void*))&printf); */
1092     traverse(head);
1093     xbt_dict_free(&head);
1094     xbt_dict_free(&head);
1095   }
1096
1097
1098   head = xbt_dict_new();
1099   xbt_test_add("Fill %d elements, with keys being the number of element",
1100                 NB_ELM);
1101   for (j = 0; j < NB_ELM; j++) {
1102     /* if (!(j%1000)) { printf("."); fflush(stdout); } */
1103
1104     key = xbt_malloc(10);
1105
1106     sprintf(key, "%d", j);
1107     xbt_dict_set(head, key, key, &free);
1108   }
1109   /*xbt_dict_dump(head,(void (*)(void*))&printf); */
1110
1111   xbt_test_add
1112       ("Count the elements (retrieving the key and data for each)");
1113   i = countelems(head);
1114   xbt_test_log("There is %d elements", i);
1115
1116   xbt_test_add("Search my %d elements 20 times", NB_ELM);
1117   key = xbt_malloc(10);
1118   for (i = 0; i < 20; i++) {
1119     void *data;
1120     /* if (i%10) printf("."); else printf("%d",i/10); fflush(stdout); */
1121     for (j = 0; j < NB_ELM; j++) {
1122
1123       sprintf(key, "%d", j);
1124       data = xbt_dict_get(head, key);
1125       xbt_test_assert(!strcmp(key, (char *) data),
1126                        "with get, key=%s != data=%s", key, (char *) data);
1127       data = xbt_dict_get_ext(head, key, strlen(key));
1128       xbt_test_assert(!strcmp(key, (char *) data),
1129                        "with get_ext, key=%s != data=%s", key,
1130                        (char *) data);
1131     }
1132   }
1133   free(key);
1134
1135   xbt_test_add("Remove my %d elements", NB_ELM);
1136   key = xbt_malloc(10);
1137   for (j = 0; j < NB_ELM; j++) {
1138     /* if (!(j%10000)) printf("."); fflush(stdout); */
1139
1140     sprintf(key, "%d", j);
1141     xbt_dict_remove(head, key);
1142   }
1143   free(key);
1144
1145
1146   xbt_test_add("Free the structure (twice)");
1147   xbt_dict_free(&head);
1148   xbt_dict_free(&head);
1149 }
1150
1151 #endif                          /* SIMGRID_TEST */