3 /* dict - a generic dictionnary, variation over the B-tree concept */
5 /* Copyright (c) 2003,2004 Martin Quinson. All rights reserved. */
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. */
11 #include "dict_private.h"
13 XBT_LOG_NEW_SUBCATEGORY(dict,xbt,
14 "Dictionaries provide the same functionnalities than hash tables");
15 /*####[ Private prototypes ]#################################################*/
17 /*####[ Code ]###############################################################*/
21 * @return pointer to the destination
23 * Creates and initialize a new dictionnary
27 xbt_dict_t res= xbt_new(s_xbt_dict_t,1);
33 * @param dict the dictionnary to be freed
35 * Frees a cache structure with all its childs.
38 xbt_dict_free(xbt_dict_t *dict) {
41 xbt_dictelm_free( &( (*dict)->head ) );
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
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.
62 xbt_dict_set_ext(xbt_dict_t dict,
66 void_f_pvoid_t *free_ctn) {
70 xbt_dictelm_set_ext(&(dict->head),
71 key, key_len, data, free_ctn);
75 * \brief Add data to the dict (null-terminated key)
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
83 * set the \a data in the structure under the \a key, which is a
84 * null terminated string.
87 xbt_dict_set(xbt_dict_t dict,
90 void_f_pvoid_t *free_ctn) {
94 xbt_dictelm_set(&(dict->head), key, data, free_ctn);
98 * \brief Retrieve data from the dict (arbitrary key)
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
105 * Search the given \a key. throws not_found_error when not found.
108 xbt_dict_get_ext(xbt_dict_t dict,
114 return xbt_dictelm_get_ext(dict->head, key, key_len);
118 * \brief Retrieve data from the dict (null-terminated key)
120 * \param dict the dealer of data
121 * \param key the key to find data
122 * \returns the data that we are looking for
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
129 xbt_dict_get(xbt_dict_t dict,
133 return xbt_dictelm_get(dict->head, key);
137 * \brief like xbt_dict_get(), but returning NULL when not found
140 xbt_dict_get_or_null(xbt_dict_t dict,
145 res = xbt_dictelm_get(dict->head, key);
147 if (e.category != not_found_error)
157 * \brief Remove data from the dict (arbitrary key)
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
164 * Remove the entry associated with the given \a key (throws not_found)
167 xbt_dict_remove_ext(xbt_dict_t dict,
172 xbt_dictelm_remove_ext(dict->head, key, key_len);
176 * \brief Remove data from the dict (null-terminated key)
178 * \param dict the head of the dict
179 * \param key the key of the data to be removed
181 * Remove the entry associated with the given \a key
184 xbt_dict_remove(xbt_dict_t dict,
187 THROW1(arg_error,0,"Asked to remove key %s from NULL dict",key);
189 xbt_dictelm_remove(dict->head, key);
194 * \brief Outputs the content of the structure (debuging purpose)
196 * \param dict the exibitionist
197 * \param output a function to dump each data in the tree
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.
204 xbt_dict_dump(xbt_dict_t dict,
205 void_f_pvoid_t *output) {
207 printf("Dict %p:\n", (void*)dict);
208 xbt_dictelm_dump(dict ? dict->head: NULL, output);
214 #include "portable.h"
216 XBT_LOG_EXTERNAL_CATEGORY(dict);
217 XBT_LOG_DEFAULT_CATEGORY(dict);
219 XBT_TEST_SUITE("dict","Dict data container");
221 static void print_str(void *str) {
222 printf("%s",(char*)PRINTF_STR(str));
225 static void debuged_add(xbt_dict_t head,const char*key)
227 char *data=xbt_strdup(key);
229 xbt_test_log1("Add %s",PRINTF_STR(key));
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);
238 static void fill(xbt_dict_t *head) {
239 xbt_test_add0("Fill in the dictionnary");
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");
254 static void search(xbt_dict_t head,const char*key) {
257 xbt_test_add1("Search %s",key);
258 data=xbt_dict_get(head,key);
259 xbt_test_log1("Found %s",(char *)data);
261 xbt_test_assert0(!strcmp((char*)data,key),"Key and data do not match");
264 static void debuged_remove(xbt_dict_t head,const char*key) {
266 xbt_test_add1("Remove '%s'",PRINTF_STR(key));
267 xbt_dict_remove(head,key);
268 /* xbt_dict_dump(head,(void (*)(void*))&printf); */
272 static void traverse(xbt_dict_t head) {
273 xbt_dict_cursor_t cursor=NULL;
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);
284 static void search_not_found(xbt_dict_t head, const char *data) {
287 xbt_test_add1("Search %s (expected not to be found)",data);
290 data = xbt_dict_get(head,"Can't be found");
291 THROW1(unknown_error,0,"Found something which shouldn't be there (%s)",data);
293 if (e.category != not_found_error)
294 xbt_test_exception(e);
300 xbt_dict_t head=NULL;
304 XBT_TEST_UNIT("basic",test_dict_basic,"Basic usage: change, retrive, traverse"){
306 xbt_test_add0("Traversal the empty dictionnary");
309 xbt_test_add0("Traverse the full dictionnary");
315 xbt_test_add0("Free the dictionnary (twice)");
316 xbt_dict_free(&head);
317 xbt_dict_free(&head);
321 xbt_test_add0("Change 123 to 'Changed 123'");
322 xbt_dict_set(head,"123",strdup("Changed 123"),&free);
324 xbt_test_add0("Change 123 back to '123'");
325 xbt_dict_set(head,"123",strdup("123"),&free);
327 xbt_test_add0("Change 12a to 'Dummy 12a'");
328 xbt_dict_set(head,"12a",strdup("Dummy 12a"),&free);
330 xbt_test_add0("Change 12a to '12a'");
331 xbt_dict_set(head,"12a",strdup("12a"),&free);
333 xbt_test_add0("Traverse the resulting dictionnary");
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));
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");
349 search(head,"123456");
351 search(head,"123457");
353 xbt_test_add0("Traverse the resulting dictionnary");
356 /* xbt_dict_dump(head,(void (*)(void*))&printf); */
358 xbt_test_add0("Free the dictionnary twice");
359 xbt_dict_free(&head);
360 xbt_dict_free(&head);
362 xbt_test_add0("Traverse the resulting dictionnary");
366 XBT_TEST_UNIT("remove",test_dict_remove,"Removing some values"){
368 xbt_test_add0("Remove non existing data");
370 debuged_remove(head,"Does not exist");
372 if (e.category != not_found_error)
373 xbt_test_exception(e);
378 xbt_dict_free(&head);
380 xbt_test_add0("Remove data from the NULL dict");
382 debuged_remove(head,"12345");
384 if (e.category != arg_error)
385 xbt_test_exception(e);
389 xbt_test_add0("Remove each data manually (traversing the resulting dictionnary each time)");
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);
396 debuged_remove(head,"12346");
398 if (e.category != not_found_error)
399 xbt_test_exception(e);
403 debuged_remove(head,"1234"); traverse(head);
404 debuged_remove(head,"123457"); traverse(head);
405 debuged_remove(head,"123"); traverse(head);
407 debuged_remove(head,"12346");
409 if (e.category != not_found_error)
410 xbt_test_exception(e);
414 xbt_test_add0("Free the dictionnary twice");
415 xbt_dict_free(&head);
416 xbt_dict_free(&head);
419 XBT_TEST_UNIT("nulldata",test_dict_nulldata,"NULL data management"){
422 xbt_test_add0("Store NULL under 'null'");
423 xbt_dict_set(head,"null",NULL,NULL);
426 xbt_test_add0("Check whether I see it while traversing...");
428 xbt_dict_cursor_t cursor=NULL;
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"))
437 xbt_test_assert0(found,"the key 'null', associated to NULL is not found");
439 xbt_dict_free(&head);
443 #define SIZEOFKEY 1024
444 static int countelems(xbt_dict_t head) {
445 xbt_dict_cursor_t cursor;
450 xbt_dict_foreach(head,cursor,key,data) {
456 XBT_TEST_UNIT("crash",test_dict_crash,"Crash test"){
457 xbt_dict_t head=NULL;
462 srand((unsigned int)time(NULL));
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);
470 // if (i%10) printf("."); else printf("%d",i/10); fflush(stdout);
472 for (j=0;j<1000;j++) {
473 key=xbt_malloc(SIZEOFKEY);
475 for (k=0;k<SIZEOFKEY-1;k++)
476 key[k]=rand() % ('z' - 'a') + 'a';
478 /* printf("[%d %s]\n",j,key); */
479 xbt_dict_set(head,key,key,&free);
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);
485 xbt_dict_free(&head);
486 xbt_dict_free(&head);
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); }
495 key = xbt_malloc(10);
498 xbt_dict_set(head,key,key,&free);
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);
505 xbt_test_add1("Search my %d elements 20 times",NB_ELM);
508 // if (i%10) printf("."); else printf("%d",i/10); fflush(stdout);
509 for (j=0;j<NB_ELM;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);
519 xbt_test_add1("Remove my %d elements",NB_ELM);
521 for (j=0;j<NB_ELM;j++) {
522 //if (!(j%10000)) printf("."); fflush(stdout);
525 xbt_dict_remove(head,key);
530 xbt_test_add0("Free the structure (twice)");
531 xbt_dict_free(&head);
532 xbt_dict_free(&head);
535 static void str_free(void *s) {
540 XBT_TEST_UNIT("multicrash",test_dict_multicrash,"Multi-dict crash test"){
543 #define NB_ELM 100 /*00*/
546 #define NB_TEST 20 /*20*/
549 xbt_dict_t mdict = NULL;
551 xbt_dynar_t keys = xbt_dynar_new(sizeof(char*),str_free);
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);
561 for (l=0 ; l<DEPTH ; l++) {
562 key=xbt_malloc(KEY_SIZE);
563 xbt_dynar_push(keys,&key);
566 for (i=0;i<NB_TEST;i++) {
567 mdict = xbt_dict_new();
568 VERB1("mdict=%p",mdict);
570 printf("Test %d\n",i);
571 /* else if (i%10) printf("."); else printf("%d",i/10);*/
573 for (j=0;j<NB_ELM;j++) {
574 if (verbose>0) printf (" Add {");
576 for (l=0 ; l<DEPTH ; l++) {
577 key=*(char**)xbt_dynar_get_ptr(keys,l);
579 for (k=0;k<KEY_SIZE-1;k++)
580 key[k]=rand() % ('z' - 'a') + 'a';
584 if (verbose>0) printf("%p=%s %s ",key, key,(l<DEPTH-1?";":"}"));
586 if (verbose>0) printf("in multitree %p.\n",mdict);
588 xbt_multidict_set(mdict,keys,xbt_strdup(key),free);
590 data = xbt_multidict_get(mdict,keys);
592 xbt_test_assert2(data && !strcmp((char*)data,key),
593 "Retrieved value (%s) does not match the entrered one (%s)\n",
596 xbt_dict_free(&mdict);
599 xbt_dynar_free(&keys);
602 xbt_dict_dump(mdict,&xbt_dict_print);*/
604 xbt_dict_free(&mdict);
605 xbt_dynar_free(&keys);
608 #endif /* SIMGRID_TEST */