Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
retrive -> retrieve
[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 "xbt/ex.h"
11 #include "dict_private.h"
12
13 XBT_LOG_NEW_SUBCATEGORY(dict,xbt,
14    "Dictionaries provide the same functionnalities than hash tables");
15 /*####[ Private prototypes ]#################################################*/
16
17 /*####[ Code ]###############################################################*/
18
19 /**
20  * @brief Constructor
21  * @return pointer to the destination
22  *
23  * Creates and initialize a new dictionnary
24  */
25 xbt_dict_t 
26 xbt_dict_new(void) {
27   xbt_dict_t res= xbt_new(s_xbt_dict_t,1);
28   res->head=NULL;
29   return res;
30 }
31 /**
32  * @brief Destructor
33  * @param dict the dictionnary to be freed
34  *
35  * Frees a cache structure with all its childs.
36  */
37 void
38 xbt_dict_free(xbt_dict_t *dict)  {
39   if (dict && *dict) {
40     if ((*dict)->head) {
41       xbt_dictelm_free( &( (*dict)->head ) );
42       (*dict)->head = NULL;
43     }
44     free(*dict);
45     *dict=NULL;
46   }
47 }
48
49 /**
50  * \brief Add data to the dict (arbitrary key)
51  * \param dict the container
52  * \param key the key to set the new data
53  * \param key_len the size of the \a key
54  * \param data the data to add in the dict
55  * \param free_ctn function to call with (\a key as argument) when 
56  *        \a key is removed from the dictionnary
57  *
58  * set the \a data in the structure under the \a key, which can be any kind 
59  * of data, as long as its length is provided in \a key_len.
60  */
61 void
62 xbt_dict_set_ext(xbt_dict_t      dict,
63                   const char      *key,
64                   int              key_len,
65                   void            *data,
66                   void_f_pvoid_t  *free_ctn) {
67
68   xbt_assert(dict);
69
70   xbt_dictelm_set_ext(&(dict->head),
71                        key, key_len, data, free_ctn);
72 }
73
74 /**
75  * \brief Add data to the dict (null-terminated key)
76  *
77  * \param dict the head of the dict
78  * \param key the key to set the new data
79  * \param data the data to add in the dict
80  * \param free_ctn function to call with (\a key as argument) when 
81  *        \a key is removed from the dictionnary
82  *
83  * set the \a data in the structure under the \a key, which is a 
84  * null terminated string.
85  */
86 void
87 xbt_dict_set(xbt_dict_t     dict,
88               const char     *key,
89               void           *data,
90               void_f_pvoid_t *free_ctn) {
91
92   xbt_assert(dict);
93   
94   xbt_dictelm_set(&(dict->head), key, data, free_ctn);
95 }
96
97 /**
98  * \brief Retrieve data from the dict (arbitrary key)
99  *
100  * \param dict the dealer of data
101  * \param key the key to find data
102  * \param key_len the size of the \a key
103  * \returns the data that we are looking for
104  *
105  * Search the given \a key. throws not_found_error when not found.
106  */
107 void *
108 xbt_dict_get_ext(xbt_dict_t      dict,
109                  const char     *key,
110                  int             key_len) {
111
112   xbt_assert(dict);
113
114   return xbt_dictelm_get_ext(dict->head, key, key_len);
115 }
116
117 /**
118  * \brief Retrieve data from the dict (null-terminated key) 
119  *
120  * \param dict the dealer of data
121  * \param key the key to find data
122  * \returns the data that we are looking for
123  *
124  * Search the given \a key. THROWs mismatch_error when not found. 
125  * Check xbt_dict_get_or_null() for a version returning NULL without exception when 
126  * not found.
127  */
128 void *
129 xbt_dict_get(xbt_dict_t     dict,
130              const char     *key) {
131   xbt_assert(dict);
132
133   return xbt_dictelm_get(dict->head, key);
134 }
135
136 /**
137  * \brief like xbt_dict_get(), but returning NULL when not found
138  */
139 void *
140 xbt_dict_get_or_null(xbt_dict_t     dict,
141                      const char     *key) {
142   xbt_ex_t e;
143   void *res=NULL;
144   TRY {
145     res = xbt_dictelm_get(dict->head, key);
146   } CATCH(e) {
147     if (e.category != not_found_error) 
148       RETHROW;
149     xbt_ex_free(e);
150     res=NULL;
151   }
152   return res;
153 }
154
155
156 /**
157  * \brief Remove data from the dict (arbitrary key)
158  *
159  * \param dict the trash can
160  * \param key the key of the data to be removed
161  * \param key_len the size of the \a key
162  * 
163  *
164  * Remove the entry associated with the given \a key (throws not_found)
165  */
166 void
167 xbt_dict_remove_ext(xbt_dict_t  dict,
168                      const char  *key,
169                      int          key_len) {
170   xbt_assert(dict);
171   
172   xbt_dictelm_remove_ext(dict->head, key, key_len);
173 }
174
175 /**
176  * \brief Remove data from the dict (null-terminated key)
177  *
178  * \param dict the head of the dict
179  * \param key the key of the data to be removed
180  *
181  * Remove the entry associated with the given \a key
182  */
183 void
184 xbt_dict_remove(xbt_dict_t  dict,
185                  const char  *key) {
186   if (!dict)
187     THROW1(arg_error,0,"Asked to remove key %s from NULL dict",key);
188
189   xbt_dictelm_remove(dict->head, key);
190 }
191
192
193 /**
194  * \brief Outputs the content of the structure (debuging purpose) 
195  *
196  * \param dict the exibitionist
197  * \param output a function to dump each data in the tree
198  *
199  * Ouputs the content of the structure. (for debuging purpose). \a ouput is a
200  * function to output the data. If NULL, data won't be displayed, just the tree structure.
201  */
202
203 void
204 xbt_dict_dump(xbt_dict_t     dict,
205                void_f_pvoid_t *output) {
206
207   printf("Dict %p:\n", (void*)dict);
208   xbt_dictelm_dump(dict ? dict->head: NULL, output);
209 }
210
211 #ifdef SIMGRID_TEST
212 #include "xbt.h"
213 #include "xbt/ex.h"
214 #include "portable.h"
215
216 XBT_LOG_EXTERNAL_CATEGORY(dict);
217 XBT_LOG_DEFAULT_CATEGORY(dict);
218
219 XBT_TEST_SUITE("dict","Dict data container");
220
221 static void print_str(void *str) {
222   printf("%s",(char*)PRINTF_STR(str));
223 }
224
225 static void debuged_add(xbt_dict_t head,const char*key)
226 {
227   char *data=xbt_strdup(key);
228
229   xbt_test_log1("Add %s",PRINTF_STR(key));
230
231   xbt_dict_set(head,key,data,&free);
232   if (XBT_LOG_ISENABLED(dict,xbt_log_priority_debug)) {
233     xbt_dict_dump(head,(void (*)(void*))&printf);
234     fflush(stdout);
235   }
236 }
237
238 static void fill(xbt_dict_t *head) {
239   xbt_test_add0("Fill in the dictionnary");
240
241   *head = xbt_dict_new();
242   debuged_add(*head,"12");
243   debuged_add(*head,"12a");
244   debuged_add(*head,"12b");
245   debuged_add(*head,"123");
246   debuged_add(*head,"123456");
247   /* Child becomes child of what to add */
248   debuged_add(*head,"1234");
249   /* Need of common ancestor */
250   debuged_add(*head,"123457");
251
252 }
253
254 static void search(xbt_dict_t head,const char*key) {
255   void *data;
256   
257   xbt_test_add1("Search %s",key);
258   data=xbt_dict_get(head,key);
259   xbt_test_log1("Found %s",(char *)data);
260   if (data)
261     xbt_test_assert0(!strcmp((char*)data,key),"Key and data do not match");
262 }
263
264 static void debuged_remove(xbt_dict_t head,const char*key) {
265
266   xbt_test_add1("Remove '%s'",PRINTF_STR(key));
267   xbt_dict_remove(head,key);
268   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
269 }
270
271
272 static void traverse(xbt_dict_t head) {
273   xbt_dict_cursor_t cursor=NULL;
274   char *key;
275   char *data;
276
277   xbt_dict_foreach(head,cursor,key,data) {
278     xbt_test_log2("Seen:  %s->%s",PRINTF_STR(key),PRINTF_STR(data));
279     xbt_test_assert2(!data || !strcmp(key,data),
280                      "Key(%s) != value(%s). Abording\n",key,data);
281   }
282 }
283
284 static void search_not_found(xbt_dict_t head, const char *data) {
285   xbt_ex_t e;
286
287   xbt_test_add1("Search %s (expected not to be found)",data);
288
289   TRY {    
290     data = xbt_dict_get(head,"Can't be found");
291     THROW1(unknown_error,0,"Found something which shouldn't be there (%s)",data);
292   } CATCH(e) {
293     if (e.category != not_found_error) 
294       xbt_test_exception(e);
295     xbt_ex_free(e);
296   }
297 }
298
299 xbt_ex_t e;
300 xbt_dict_t head=NULL;
301 char *data;
302
303
304 XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrieve, traverse"){
305
306   xbt_test_add0("Traversal the empty dictionnary");
307   traverse(head);
308
309   xbt_test_add0("Traverse the full dictionnary");
310   fill(&head);
311
312   search(head,"12a");
313   traverse(head);
314
315   xbt_test_add0("Free the dictionnary (twice)");
316   xbt_dict_free(&head);
317   xbt_dict_free(&head);
318
319   /* CHANGING */
320   fill(&head);
321   xbt_test_add0("Change 123 to 'Changed 123'");
322   xbt_dict_set(head,"123",strdup("Changed 123"),&free);
323
324   xbt_test_add0("Change 123 back to '123'");
325   xbt_dict_set(head,"123",strdup("123"),&free);
326
327   xbt_test_add0("Change 12a to 'Dummy 12a'");
328   xbt_dict_set(head,"12a",strdup("Dummy 12a"),&free);
329
330   xbt_test_add0("Change 12a to '12a'");
331   xbt_dict_set(head,"12a",strdup("12a"),&free);
332
333   xbt_test_add0("Traverse the resulting dictionnary");
334   traverse(head);
335   
336   /* RETRIEVE */
337   xbt_test_add0("Search 123");
338   data = xbt_dict_get(head,"123");
339   xbt_test_assert(data);
340   xbt_test_assert(!strcmp("123",data));
341
342   search_not_found(head,"Can't be found");
343   search_not_found(head,"123 Can't be found");
344   search_not_found(head,"12345678 NOT");
345
346   search(head,"12a");
347   search(head,"12b");
348   search(head,"12");
349   search(head,"123456");
350   search(head,"1234");
351   search(head,"123457");
352
353   xbt_test_add0("Traverse the resulting dictionnary");
354   traverse(head);
355
356   /*  xbt_dict_dump(head,(void (*)(void*))&printf); */
357
358   xbt_test_add0("Free the dictionnary twice");
359   xbt_dict_free(&head);
360   xbt_dict_free(&head);
361
362   xbt_test_add0("Traverse the resulting dictionnary");
363   traverse(head);
364 }
365
366 XBT_TEST_UNIT("remove",test_dict_remove,"Removing some values"){
367   fill(&head);
368   xbt_test_add0("Remove non existing data");
369   TRY {
370     debuged_remove(head,"Does not exist");
371   } CATCH(e) {
372     if (e.category != not_found_error) 
373       xbt_test_exception(e);
374     xbt_ex_free(e);
375   }
376   traverse(head);
377
378   xbt_dict_free(&head);
379
380   xbt_test_add0("Remove data from the NULL dict");
381   TRY {
382     debuged_remove(head,"12345");
383   } CATCH(e) {
384     if (e.category != arg_error) 
385       xbt_test_exception(e);
386     xbt_ex_free(e);
387   } 
388
389   xbt_test_add0("Remove each data manually (traversing the resulting dictionnary each time)");
390   fill(&head);
391   debuged_remove(head,"12a");    traverse(head);
392   debuged_remove(head,"12b");    traverse(head);
393   debuged_remove(head,"12");     traverse(head);
394   debuged_remove(head,"123456"); traverse(head);
395   TRY {
396     debuged_remove(head,"12346");
397   } CATCH(e) {
398     if (e.category != not_found_error) 
399       xbt_test_exception(e);
400     xbt_ex_free(e);         
401     traverse(head);
402   } 
403   debuged_remove(head,"1234");   traverse(head);
404   debuged_remove(head,"123457"); traverse(head);
405   debuged_remove(head,"123");    traverse(head);
406   TRY {
407     debuged_remove(head,"12346");
408   } CATCH(e) {
409     if (e.category != not_found_error) 
410       xbt_test_exception(e);
411     xbt_ex_free(e);
412   }                              traverse(head);
413   
414   xbt_test_add0("Free the dictionnary twice");
415   xbt_dict_free(&head);
416   xbt_dict_free(&head);      
417 }
418
419 XBT_TEST_UNIT("nulldata",test_dict_nulldata,"NULL data management"){
420   fill(&head);
421
422   xbt_test_add0("Store NULL under 'null'");
423   xbt_dict_set(head,"null",NULL,NULL);
424   search(head,"null");
425
426   xbt_test_add0("Check whether I see it while traversing...");
427   {
428     xbt_dict_cursor_t cursor=NULL;
429     char *key;
430     int found=0;
431     
432     xbt_dict_foreach(head,cursor,key,data) {
433       xbt_test_log2("Seen:  %s->%s",PRINTF_STR(key),PRINTF_STR(data));
434       if (!strcmp(key,"null"))
435         found = 1;
436     }
437     xbt_test_assert0(found,"the key 'null', associated to NULL is not found");
438   }
439   xbt_dict_free(&head);
440 }
441
442 #define NB_ELM 20000
443 #define SIZEOFKEY 1024
444 static int countelems(xbt_dict_t head) {
445   xbt_dict_cursor_t cursor;
446   char *key;
447   void *data;
448   int res = 0;
449
450   xbt_dict_foreach(head,cursor,key,data) {
451     res++;
452   }
453   return res;
454 }
455
456 XBT_TEST_UNIT("crash",test_dict_crash,"Crash test"){
457   xbt_dict_t head=NULL;
458   int i,j,k, nb;
459   char *key;
460   void *data;
461
462   srand((unsigned int)time(NULL));
463
464   xbt_test_add0("CRASH test");
465   xbt_test_log0("Fill the struct, count its elems and frees the structure (x10)");
466   xbt_test_log1("using 1000 elements with %d chars long randomized keys.",SIZEOFKEY);
467
468   for (i=0;i<10;i++) {
469     head=xbt_dict_new();
470     //    if (i%10) printf("."); else printf("%d",i/10); fflush(stdout);
471     nb=0;
472     for (j=0;j<1000;j++) {
473       key=xbt_malloc(SIZEOFKEY);
474
475       for (k=0;k<SIZEOFKEY-1;k++)
476         key[k]=rand() % ('z' - 'a') + 'a';
477       key[k]='\0';
478       /*      printf("[%d %s]\n",j,key); */
479       xbt_dict_set(head,key,key,&free);
480     }
481     /*    xbt_dict_dump(head,(void (*)(void*))&printf); */
482     nb = countelems(head);
483     xbt_test_assert1(nb == 1000,"found %d elements instead of 1000",nb);
484     traverse(head);
485     xbt_dict_free(&head);
486     xbt_dict_free(&head);
487   }
488
489
490   head=xbt_dict_new();
491   xbt_test_add1("Fill %d elements, with keys being the number of element",NB_ELM);
492   for (j=0;j<NB_ELM;j++) {
493     //    if (!(j%1000)) { printf("."); fflush(stdout); }
494
495     key = xbt_malloc(10);
496     
497     sprintf(key,"%d",j);
498     xbt_dict_set(head,key,key,&free);
499   }
500
501   xbt_test_add0("Count the elements (retrieving the key and data for each)");
502   i = countelems(head);
503   xbt_test_log1("There is %d elements",i);
504
505   xbt_test_add1("Search my %d elements 20 times",NB_ELM);
506   key=xbt_malloc(10);
507   for (i=0;i<20;i++) {
508     //    if (i%10) printf("."); else printf("%d",i/10); fflush(stdout);
509     for (j=0;j<NB_ELM;j++) {
510       
511       sprintf(key,"%d",j);
512       data = xbt_dict_get(head,key);
513       xbt_test_assert2(!strcmp(key,(char*)data),
514                        "key=%s != data=%s\n",key,(char*)data);
515     }
516   }
517   free(key);
518
519   xbt_test_add1("Remove my %d elements",NB_ELM);
520   key=xbt_malloc(10);
521   for (j=0;j<NB_ELM;j++) {
522     //if (!(j%10000)) printf("."); fflush(stdout);
523     
524     sprintf(key,"%d",j);
525     xbt_dict_remove(head,key);
526   }
527   free(key);
528
529   
530   xbt_test_add0("Free the structure (twice)");
531   xbt_dict_free(&head);
532   xbt_dict_free(&head);
533 }
534
535 static void str_free(void *s) {
536   char *c=*(char**)s;
537   free(c);
538 }
539
540 XBT_TEST_UNIT("multicrash",test_dict_multicrash,"Multi-dict crash test"){
541
542 #undef NB_ELM
543 #define NB_ELM 100 /*00*/
544 #define DEPTH 5
545 #define KEY_SIZE 512
546 #define NB_TEST 20 /*20*/
547 int verbose=0;
548
549   xbt_dict_t mdict = NULL;
550   int i,j,k,l;
551   xbt_dynar_t keys = xbt_dynar_new(sizeof(char*),str_free);
552   void *data;
553   char *key;
554
555
556   xbt_test_add0("Generic multicache CRASH test");
557   xbt_test_log4(" Fill the struct and frees it %d times, using %d elements, "
558                 "depth of multicache=%d, key size=%d",
559                 NB_TEST,NB_ELM,DEPTH,KEY_SIZE);
560
561   for (l=0 ; l<DEPTH ; l++) {
562     key=xbt_malloc(KEY_SIZE);
563     xbt_dynar_push(keys,&key);
564   }     
565
566   for (i=0;i<NB_TEST;i++) {
567     mdict = xbt_dict_new();
568     VERB1("mdict=%p",mdict);
569     if (verbose>0)
570       printf("Test %d\n",i);
571     /* else if (i%10) printf("."); else printf("%d",i/10);*/
572     
573     for (j=0;j<NB_ELM;j++) {
574       if (verbose>0) printf ("  Add {");
575       
576       for (l=0 ; l<DEPTH ; l++) {
577         key=*(char**)xbt_dynar_get_ptr(keys,l);
578         
579         for (k=0;k<KEY_SIZE-1;k++) 
580           key[k]=rand() % ('z' - 'a') + 'a';
581           
582         key[k]='\0';
583         
584         if (verbose>0) printf("%p=%s %s ",key, key,(l<DEPTH-1?";":"}"));
585       }
586       if (verbose>0) printf("in multitree %p.\n",mdict);
587                                                         
588       xbt_multidict_set(mdict,keys,xbt_strdup(key),free);
589
590       data = xbt_multidict_get(mdict,keys);
591
592       xbt_test_assert2(data && !strcmp((char*)data,key),
593                        "Retrieved value (%s) does not match the entrered one (%s)\n",
594                        (char*)data,key);
595     }
596     xbt_dict_free(&mdict);
597   }
598   
599   xbt_dynar_free(&keys);
600
601 /*  if (verbose>0)
602     xbt_dict_dump(mdict,&xbt_dict_print);*/
603     
604   xbt_dict_free(&mdict);
605   xbt_dynar_free(&keys);
606
607 }
608 #endif /* SIMGRID_TEST */