Logo AND Algorithmique Numérique Distribuée

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