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, retrive, 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   /* RETRIVE */
 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 */