src/xbt/dict_elm.c

   1 /* $Id$ */
   2
   3 /* dict - a generic dictionnary, variation over the B-tree concept          */
   4
   5 /* Authors: Martin Quinson                                                  */
   6 /* Copyright (C) 2003 the OURAGAN project.                                  */
   7
   8 /* This program is free software; you can redistribute it and/or modify it
   9    under the terms of the license (GNU LGPL) which comes with this package. */
  10
  11 #include "dict_private.h"  /* prototypes of this module */
  12
  13 XBT_LOG_EXTERNAL_CATEGORY(dict);
  14 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dict_elm,dict,"Dictionaries internals");
  15
  16 XBT_LOG_NEW_SUBCATEGORY(dict_add,dict,"Dictionaries internals: elements addition");
  17 XBT_LOG_NEW_SUBCATEGORY(dict_search,dict,"Dictionaries internals: searching");
  18 XBT_LOG_NEW_SUBCATEGORY(dict_remove,dict,"Dictionaries internals: elements removal");
  19 XBT_LOG_NEW_SUBCATEGORY(dict_collapse,dict,"Dictionaries internals: post-removal cleanup");
  20 XBT_LOG_NEW_SUBCATEGORY(dict_multi,dict,"Dictionaries internals: dictionaries of dictionaries");
  21
  22 /*####[ Private prototypes ]#################################################*/
  23
  24 static _XBT_INLINE void _xbt_dictelm_alloc(char                *key,
  25                                              int                  offset,
  26                                              int                  key_len,
  27                                              void                *data,
  28                                              void_f_pvoid_t      *free_f,
  29                                              /*OUT*/s_xbt_dictelm_t **where);
  30 static void         _dictelm_wrapper_free(void*);
  31
  32 static _XBT_INLINE void  _str_prefix_lgr(const char *key1,
  33                                           int         key_len1,
  34                                           const char *key2,
  35                                           int         key_len2,
  36                                           int        *offset,
  37                                           int        *match);
  38
  39
  40 static void _xbt_dictelm_dump_rec(s_xbt_dictelm_t *head,
  41                                    int             offset,
  42                                    void_f_pvoid_t *output);
  43
  44
  45
  46 static void _xbt_dictelm_set_rec(s_xbt_dictelm_t *head,
  47                                   char           *key,
  48                                   int             key_len,
  49                                   int             offset,
  50                                   void           *data,
  51                                   void_f_pvoid_t *free_f);
  52 static xbt_error_t _xbt_dictelm_get_rec(s_xbt_dictelm_t *head,
  53                                                const char     *key,
  54                                                int             key_len,
  55                                                int             offset,
  56                                                /* OUT */void **data);
  57 static xbt_error_t _xbt_dictelm_remove_rec(s_xbt_dictelm_t *head,
  58                                              const char     *key,
  59                                              int             key_len,
  60                                              int             offset);
  61
  62 static _XBT_INLINE
  63 void
  64 _collapse_if_need(s_xbt_dictelm_t *p_head,
  65                   int             pos,
  66                   int             offset);
  67
  68 /* ---- */
  69
  70 static _XBT_INLINE
  71 void *
  72 xbt_memdup(const void * const ptr,
  73             const size_t       length) {
  74   void * new_ptr = NULL;
  75
  76   new_ptr = xbt_malloc(length);
  77   memcpy(new_ptr, ptr, length);
  78
  79   return new_ptr;
  80 }
  81
  82 /*
  83  * _xbt_nibble_to_char:
  84  *
  85  * Change any byte to a printable char
  86  */
  87
  88 static _XBT_INLINE
  89 char
  90 _xbt_nibble_to_char(unsigned char c) {
  91   c &= 0x0f;
  92   return c>9 ? c-10+'a' : c + '0';
  93 }
  94
  95 /*
  96  * _xbt_bytes_to_string:
  97  *
  98  * Change any byte array to a printable string
  99  * The length of string_container should at least be data_len*2+1
 100  */
 101 static _XBT_INLINE
 102 char *
 103 _xbt_bytes_to_string(char * const ptr,
 104                       int          data_len,
 105                       char * const string_container) {
 106   unsigned char *src = (unsigned char *)ptr;
 107            char *dst = string_container;
 108
 109   while (data_len--) {
 110     *dst++ = _xbt_nibble_to_char(*src   & 0x0f     );
 111     *dst++ = _xbt_nibble_to_char(*src++ & 0xf0 >> 4);
 112   }
 113
 114   *dst = 0;
 115
 116   return ptr;
 117 }
 118
 119 /* ---- */
 120
 121 /*
 122  * _xbt_dictelm_alloc:
 123  *
 124  * Alloc a dict element with no child.
 125  */
 126 static _XBT_INLINE
 127 void
 128 _xbt_dictelm_alloc(char                *key,
 129                     int                  key_len,
 130                     int                  offset,
 131                     void                *data,
 132                     void_f_pvoid_t      *free_f,
 133                  /*OUT*/s_xbt_dictelm_t **pp_elm) {
 134   s_xbt_dictelm_t *p_elm  = NULL;
 135
 136   p_elm = xbt_new(s_xbt_dictelm_t,1);
 137
 138   p_elm->key      = key;
 139   p_elm->key_len  = key_len;
 140   p_elm->offset   = offset;
 141   p_elm->content  = data;
 142   p_elm->free_f = free_f;
 143   p_elm->sub      = xbt_dynar_new(sizeof(s_xbt_dictelm_t*), _dictelm_wrapper_free);
 144
 145   *pp_elm = p_elm;
 146
 147 }
 148
 149 /**
 150  * xbt_dictelm_free:
 151  *
 152  * @pp_elm: the dict elem to be freed
 153  *
 154  * Frees a dictionnary element with all its childs.
 155  */
 156 void
 157 xbt_dictelm_free(s_xbt_dictelm_t **pp_elm)  {
 158   if (*pp_elm) {
 159     s_xbt_dictelm_t *p_elm = *pp_elm;
 160
 161     xbt_dynar_free(&(p_elm->sub));
 162
 163     if (p_elm->key) {
 164       xbt_free(p_elm->key);
 165     }
 166
 167     if (p_elm->free_f && p_elm->content) {
 168       p_elm->free_f(p_elm->content);
 169     }
 170
 171     xbt_free(p_elm);
 172     *pp_elm = NULL;
 173   }
 174 }
 175
 176 /**
 177  * _dictelm_wrapper_free:
 178  *
 179  * a wrapper to free dictelm with the right prototype to be usable within dynar
 180  */
 181 static
 182 void
 183 _dictelm_wrapper_free(void *pp_elm) {
 184   DEBUG3("Free dictelm '%.*s' %p",
 185          (*(s_xbt_dictelm_t**)pp_elm)->key_len, (*(s_xbt_dictelm_t**)pp_elm)->key,
 186          *(void**)pp_elm);
 187   xbt_dictelm_free((s_xbt_dictelm_t**)pp_elm);
 188 }
 189
 190 /*####[ utility functions ]##################################################*/
 191 /**
 192  * _str_prefix_lgr:
 193  *
 194  *
 195  * Returns the length of the common prefix of @str1 and @str2.
 196  * Do make sure the strings are not null
 197  */
 198 static _XBT_INLINE
 199 void
 200 _str_prefix_lgr(const char *key1,
 201                 int         key_len1,
 202                 const char *key2,
 203                 int         key_len2,
 204                 int        *p_offset,
 205                 int        *p_match) {
 206   const int old_offset = *p_offset;
 207   int       o          = *p_offset;
 208   int       m          = *p_match;
 209
 210   m = 0;
 211
 212   /*CDEBUG5(dict_search, "%s: [%.*s] <=> [%.*s]", __FUNCTION__,
 213             key1,key_len1,key2,key_len2);*/
 214
 215   if (o < key_len1  &&  o < key_len2) {
 216
 217     while (key1[o] == key2[o]) {
 218       o++;
 219
 220       if (!(o < key_len1  &&  o < key_len2))
 221         break;
 222
 223     }
 224
 225   }
 226
 227
 228   if (o != old_offset) {
 229
 230     if (o >= key_len1) {
 231
 232       if (o >= key_len2) {
 233         m = 1;
 234       } else {
 235         m = 2;
 236       }
 237
 238     } else if (o >= key_len2) {
 239       m = 3;
 240     } else {
 241       m = 4;
 242     }
 243   }
 244
 245
 246   *p_offset = o;
 247   *p_match  = m;
 248 }
 249
 250 /**
 251  * _dictelm_child_cmp:
 252  *
 253  * Compares two dictelm keys and return their matching (using the same
 254  * convention than @_xbt_dict_child_search() )
 255  */
 256 static _XBT_INLINE
 257 void
 258 _dict_child_cmp(s_xbt_dictelm_t *p_dict,
 259                 int          pos,
 260                 const char  *key,
 261                 const int    key_len,
 262                 int         *p_offset,
 263                 int         *p_match,
 264                 int         *p_cmp) {
 265   s_xbt_dictelm_t  *p_child = NULL;
 266   int           cmp     = 0;
 267   int           o       = *p_offset;
 268   int           m       = *p_match;
 269
 270   p_child = xbt_dynar_get_as(p_dict->sub, pos, s_xbt_dictelm_t*);
 271
 272   /* Compute the length of the prefix
 273      and if the searched key is before or after cur */
 274   _str_prefix_lgr(p_child->key, p_child->key_len,
 275                   key,          key_len,
 276                   &o, &m);
 277
 278
 279   if (m) /* found, get out */
 280     goto end;
 281
 282   if (o < p_child->key_len  &&  (o >= key_len  ||  key[o] < p_child->key[o])) {
 283     cmp = -1;
 284   } else {
 285     cmp =  1;
 286   }
 287
 288   CDEBUG6(dict_search, "Cmp '%.*s' and '%.*s' (offset=%d) => %d",
 289           p_child->key_len - *p_offset, p_child->key + *p_offset,
 290           key_len - *p_offset, key + *p_offset,
 291           *p_offset,cmp);
 292
 293  end:
 294   *p_offset = o;
 295   *p_match  = m;
 296   *p_cmp    = cmp;
 297 }
 298
 299 /**
 300  * _xbt_dict_child_search:
 301  *
 302  * Search where would be inserted @key between the childs of @p_elm.
 303  *
 304  * Returns position of the child having a common prefix with this key
 305  * If *match==0, no child have a common prefix
 306  *               *pos is where to add the key
 307  * If *match==1, A child (located at *pos) have exactly this key
 308  * If *match==2, A child (located at *pos) constitutes a prefix of the key
 309  *               the recursion have to go on that guy
 310  *               *prefix = the size of the key eaten at this level
 311  * If *match==3  The key is a prefix of the child at *pos
 312  * If *match==4, A child (loc. at *pos) share a common prefix with this key
 313  *               *prefix = size of the prefix.
 314  *               If searching, that's a mismatch.
 315  *               If inserting, you have to break the child and create an
 316  *                 internal node having {child, key} as childs
 317  * offset is used in input and output. In input, that's the length of the key
 318  *  handled by previous levels of recursion. In output, that the one counting
 319  *  also this level.
 320  */
 321 static _XBT_INLINE
 322 void
 323 _xbt_dictelm_child_search(s_xbt_dictelm_t *p_elm,
 324                            const char  *key,
 325                            int          key_len,
 326                            int         *p_pos,
 327                            int         *p_offset,
 328                            int         *p_match) {
 329
 330   int          p       = 0;
 331   int          o       = *p_offset;
 332   int          m       = 0;
 333   int          len     = 0;
 334
 335
 336   CDEBUG5(dict_search, "search child [%.*s] under [%.*s] (len=%lu)",
 337           key_len, key,
 338           p_elm?p_elm->key_len:6, p_elm?p_elm->key:"(head)",
 339           (p_elm&&p_elm->sub)?xbt_dynar_length(p_elm->sub):0);
 340
 341
 342   len = xbt_dynar_length(p_elm->sub);
 343
 344   if(1) {
 345     int p_min = 0;
 346     int p_max = len-1;
 347     int cmp = 0;
 348
 349     p = p_min;
 350     if(len==0) {
 351       p=0;
 352     } else {
 353       _dict_child_cmp(p_elm, p_min, key, key_len, &o, &m, &cmp);
 354       if(!m) { /* OK, maybe it is somewhere else. */
 355         o = *p_offset;
 356         if (cmp<0) { /* Insert at the very beginning */
 357           p=0;
 358         } else if (p_max<=0) { /* No way. It is not there. Insert à the very end */
 359           p=p_max+1;
 360           m = 0;
 361         } else {
 362           p=p_max;
 363           _dict_child_cmp(p_elm, p_max, key, key_len, &o, &m, &cmp);
 364           if(!m) {
 365             o = *p_offset;
 366             if(cmp>0) { /* Should be located at the end of the table */
 367               p=p_max+1;
 368             } else { /* Too bad, let's go for a dichotomic search. */
 369               while(p_max-p_min>1) {
 370                 _dict_child_cmp(p_elm, (p_min+p_max)/2, key, key_len, &o, &m, &cmp);
 371                 if(m) break;
 372                 o = *p_offset;
 373                 if(cmp<0) p_max=(p_min+p_max)/2;
 374                 if(cmp>0) p_min=(p_min+p_max)/2;
 375               }
 376               if(m) /* We have the element */
 377                 p=(p_min+p_max)/2 ;
 378               else /* it should be inserted just after p_min */
 379                 p=p_min + 1;
 380             }
 381           }
 382         }
 383       }
 384     }
 385   } else {
 386     for (p = 0; p < len; p++) {
 387       int          cmp     = 0;
 388
 389       _dict_child_cmp(p_elm, p, key, key_len, &o, &m, &cmp);
 390
 391       if (m)
 392         break;
 393
 394       o = *p_offset;
 395       m = 0;
 396     }
 397   }
 398
 399   *p_offset = o;
 400   *p_pos    = p;
 401   *p_match  = m;
 402   CDEBUG5(dict_search, "search [%.*s] in [%.*s] => %s",
 403           key_len, key,
 404           p_elm?p_elm->key_len:6, p_elm?p_elm->key:"(head)",
 405           ( m == 0 ? "no child have a common prefix" :
 406             ( m == 1 ? "selected child have exactly this key" :
 407               ( m == 2 ? "selected child constitutes a prefix" :
 408                 ( m == 3 ? "key is a prefix of selected child" :
 409                   (m == 4 ? "selected child share a prefix" :
 410                    "internal error")))))
 411           );
 412 }
 413
 414 /**
 415  * _xbt_dictelm_change_value:
 416  *
 417  * Change the value of the dictelm, making sure to free the old one, if any.
 418  */
 419 static _XBT_INLINE
 420 void
 421 _xbt_dictelm_change_value(s_xbt_dictelm_t    *p_elm,
 422                            void           *data,
 423                            void_f_pvoid_t *free_f) {
 424
 425   if (p_elm->content && p_elm->free_f) {
 426     p_elm->free_f(p_elm->content);
 427   }
 428
 429   p_elm->free_f = free_f;
 430   p_elm->content  = data;
 431 }
 432
 433 /**
 434  * _xbt_dictelm_set_rec:
 435  *
 436  * @head: the head of the dict
 437  * @key: the key to set the new data
 438  * @offset: offset on key.
 439  * @data: the data to add in the dict
 440  *
 441  * set the @data in the structure under the @key. The @key is destroyed
 442  * in the process. Think to strdup it before.
 443  *
 444  * This is a helper function to xbt_dict_set which locks the struct and
 445  * strdup the key before action.
 446  */
 447 void
 448 _xbt_dictelm_set_rec(s_xbt_dictelm_t     *p_head,
 449                          char            *key,
 450                          int              key_len,
 451                          int              offset,
 452                          void            *data,
 453                          void_f_pvoid_t  *free_f) {
 454   int          match      = 0;
 455   int          pos        = 0;
 456   const int    old_offset = offset;
 457
 458   CDEBUG6(dict_add, "--> Insert '%.*s' after '%.*s' (offset=%d) in tree %p",
 459           key_len, key,
 460           ((p_head && p_head->key) ? p_head->key_len : 6),
 461           ((p_head && p_head->key) ? p_head->key : "(head)"),
 462           offset, (void*)p_head);
 463
 464   /*** The trivial cases first ***/
 465
 466   /* there is no key (we did enough recursion), change the value of head */
 467   if (offset >= key_len) {
 468
 469     CDEBUG0(dict_add, "--> Change the value of head");
 470
 471     _xbt_dictelm_change_value(p_head, data, free_f);
 472     xbt_free(key); /* Keep the key used in the tree */
 473
 474     return;
 475   }
 476
 477   /*** Search where to add this child, and how ***/
 478   _xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
 479
 480   CDEBUG3(dict_add, "child_search => pos=%d, offset=%d, match=%d",
 481           pos, offset, match);
 482
 483   switch (match) {
 484
 485   case 0: /* no child have a common prefix */
 486     {
 487       s_xbt_dictelm_t *p_child = NULL;
 488
 489       _xbt_dictelm_alloc(key, key_len, offset, data, free_f, &p_child);
 490       CDEBUG1(dict_add, "-> Add a child %p", (void*)p_child);
 491       xbt_dynar_insert_at(p_head->sub, pos, &p_child);
 492
 493       return;
 494     }
 495
 496   case 1: /* A child have exactly this key => change its value*/
 497     {
 498       s_xbt_dictelm_t *p_child = NULL;
 499
 500       p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
 501       CDEBUG1(dict_add, "-> Change the value of the child %p", (void*)p_child);
 502       _xbt_dictelm_change_value(p_child, data, free_f);
 503
 504       xbt_free(key);
 505
 506       return;
 507     }
 508
 509   case 2: /* A child constitutes a prefix of the key => recurse */
 510     {
 511       s_xbt_dictelm_t *p_child = NULL;
 512
 513       p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
 514       CDEBUG2(dict_add,"-> Recurse on %p (offset=%d)", (void*)p_child, offset);
 515
 516       _xbt_dictelm_set_rec(p_child, key, key_len,
 517                             offset, data, free_f);
 518       return;
 519     }
 520
 521   case 3: /* The key is a prefix of the child => child becomes child of p_new */
 522     {
 523       s_xbt_dictelm_t *p_new   = NULL;
 524       s_xbt_dictelm_t *p_child = NULL;
 525
 526       p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
 527       _xbt_dictelm_alloc(key, key_len, old_offset, data, free_f, &p_new);
 528
 529       CDEBUG2(dict_add, "-> The child %p become child of new dict (%p)",
 530               (void*)p_child, (void*)p_new);
 531
 532       xbt_dynar_push(p_new->sub, &p_child);
 533       p_child->offset = offset;
 534       xbt_dynar_set(p_head->sub, pos, &p_new);
 535
 536       return;
 537     }
 538
 539   case 4: /* A child share a common prefix with this key => Common ancestor */
 540     {
 541       s_xbt_dictelm_t *p_new       = NULL;
 542       s_xbt_dictelm_t *p_child     = NULL;
 543       s_xbt_dictelm_t *p_anc       = NULL;
 544       char        *anc_key     = NULL;
 545       int          anc_key_len = offset;
 546
 547       _xbt_dictelm_alloc(key, key_len, offset, data, free_f, &p_new);
 548       p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
 549
 550       anc_key = xbt_memdup(key, anc_key_len);
 551
 552       _xbt_dictelm_alloc(anc_key, anc_key_len, old_offset, NULL, NULL, &p_anc);
 553
 554       CDEBUG3(dict_add, "-> Make a common ancestor %p (%.*s)",
 555               (void*)p_anc, anc_key_len, anc_key);
 556
 557       if (key[offset] < p_child->key[offset]) {
 558         xbt_dynar_push(p_anc->sub, &p_new);
 559         xbt_dynar_push(p_anc->sub, &p_child);
 560       } else {
 561         xbt_dynar_push(p_anc->sub, &p_child);
 562         xbt_dynar_push(p_anc->sub, &p_new);
 563       }
 564
 565       p_child->offset = offset;
 566
 567       xbt_dynar_set(p_head->sub, pos, &p_anc);
 568
 569       return;
 570     }
 571
 572   default:
 573     DIE_IMPOSSIBLE;
 574   }
 575 }
 576
 577 /**
 578  * xbt_dictelm_set_ext:
 579  *
 580  * @head: the head of the dict
 581  * @key: the key to set the new data
 582  * @data: the data to add in the dict
 583  *
 584  * set the @data in the structure under the @key, which can be any kind
 585  * of data, as long as its length is provided in @key_len.
 586  */
 587 void
 588 xbt_dictelm_set_ext(s_xbt_dictelm_t **pp_head,
 589                         const char      *_key,
 590                         int              key_len,
 591                         void            *data,
 592                         void_f_pvoid_t  *free_f) {
 593   s_xbt_dictelm_t  *p_head  = *pp_head;
 594   char         *key     =  NULL;
 595
 596   key = xbt_memdup(_key, key_len);
 597
 598   /* there is no head, create it */
 599   if (!p_head) {
 600     s_xbt_dictelm_t *p_child = NULL;
 601
 602     CDEBUG0(dict_add, "Create an head");
 603
 604     /* The head is priviledged by being the only one with a NULL key */
 605     _xbt_dictelm_alloc(NULL, 0, 0, NULL, NULL, &p_head);
 606
 607     _xbt_dictelm_alloc(key, key_len, 0, data, free_f, &p_child);
 608     xbt_dynar_insert_at(p_head->sub, 0, &p_child);
 609
 610     *pp_head = p_head;
 611
 612     return;
 613   }
 614
 615   _xbt_dictelm_set_rec(p_head, key, key_len, 0, data, free_f);
 616 }
 617
 618 /**
 619  * xbt_dictelm_set:
 620  *
 621  * @head: the head of the dict
 622  * @key: the key to set the new data
 623  * @data: the data to add in the dict
 624  *
 625  * set the @data in the structure under the @key, which is a
 626  * null terminated string.
 627  */
 628 void
 629 xbt_dictelm_set(s_xbt_dictelm_t **pp_head,
 630                     const char      *_key,
 631                     void            *data,
 632                     void_f_pvoid_t  *free_f) {
 633
 634   xbt_dictelm_set_ext(pp_head, _key, 1+strlen(_key), data, free_f);
 635 }
 636
 637 /**
 638  * _xbt_dict_get_rec:
 639  *
 640  * @head: the head of the dict
 641  * @key: the key to find data
 642  * @offset: offset on the key
 643  * @data: the data that we are looking for
 644  * @Returns: xbt_error
 645  *
 646  * Search the given @key. mismatch_error when not found.
 647  */
 648 static
 649 xbt_error_t
 650 _xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head,
 651                       const char     *key,
 652                       int             key_len,
 653                       int             offset,
 654                       void **data) {
 655
 656   CDEBUG3(dict_search, "Search %.*s in %p", key_len, key, (void*)p_head);
 657
 658   /*** The trivial case first ***/
 659
 660   /* we did enough recursion, we're done */
 661   if (offset >= key_len) {
 662     *data = p_head->content;
 663
 664     return no_error;
 665   }
 666
 667   {
 668     int match = 0;
 669     int pos   = 0;
 670
 671     *data = NULL; /* Make it ready to answer 'not found' in one operation */
 672
 673     /*** Search where is the good child, and how good it is ***/
 674     _xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
 675
 676     switch (match) {
 677
 678     case 0: /* no child have a common prefix */
 679       return mismatch_error;
 680
 681     case 1: /* A child have exactly this key => Got it */
 682       {
 683         s_xbt_dictelm_t *p_child = NULL;
 684
 685         p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
 686         *data = p_child->content;
 687
 688         return no_error;
 689       }
 690
 691     case 2: /* A child constitutes a prefix of the key => recurse */
 692       {
 693         s_xbt_dictelm_t *p_child = NULL;
 694
 695         p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
 696
 697         return _xbt_dictelm_get_rec(p_child, key, key_len, offset, data);
 698       }
 699
 700     case 3: /* The key is a prefix of the child => not found */
 701       return mismatch_error;
 702
 703     case 4: /* A child share a common prefix with this key => not found */
 704       return mismatch_error;
 705
 706     default:
 707       RAISE_IMPOSSIBLE;
 708     }
 709   }
 710 }
 711
 712 /**
 713  * xbt_dictelm_get_ext:
 714  *
 715  * @head: the head of the dict
 716  * @key: the key to find data
 717  * @data: the data that we are looking for
 718  * @Returns: xbt_error
 719  *
 720  * Search the given @key. mismatch_error when not found.
 721  */
 722 xbt_error_t
 723 xbt_dictelm_get_ext(s_xbt_dictelm_t *p_head,
 724                           const char     *key,
 725                           int             key_len,
 726                           /* OUT */void **data) {
 727   /* there is no head, go to hell */
 728   if (!p_head) {
 729     return mismatch_error;
 730   }
 731
 732   return _xbt_dictelm_get_rec(p_head, key, key_len, 0, data);
 733 }
 734
 735 /**
 736  * xbt_dictelm_get:
 737  *
 738  * @head: the head of the dict
 739  * @key: the key to find data
 740  * @data: the data that we are looking for
 741  * @Returns: xbt_error
 742  *
 743  * Search the given @key. mismatch_error when not found.
 744  */
 745 xbt_error_t
 746 xbt_dictelm_get(s_xbt_dictelm_t    *p_head,
 747                    const char     *key,
 748                    /* OUT */void **data) {
 749
 750   return xbt_dictelm_get_ext(p_head, key, 1+strlen(key), data);
 751 }
 752
 753 /*----[ _xbt_dict_collapse ]------------------------------------------------*/
 754 static _XBT_INLINE
 755 void
 756 _collapse_if_need(xbt_dictelm_t head,
 757                   int            pos,
 758                   int            offset) {
 759   xbt_dictelm_t child = NULL;
 760
 761   CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, (void*)head);
 762
 763   if (pos >= 0) {
 764     /* Remove the child if |it's key| == 0 (meaning it's dead) */
 765     child = xbt_dynar_get_as(head->sub, pos, xbt_dictelm_t);
 766
 767     if (offset >= child->key_len) {
 768
 769       xbt_assert0(xbt_dynar_length(child->sub) == 0,
 770                    "Found a dead child with grand childs. Internal error");
 771
 772       CDEBUG1(dict_collapse, "Remove dead child %p.... ", (void*)child);
 773       xbt_dynar_remove_at(head->sub, pos, &child);
 774       xbt_dictelm_free(&child);
 775     }
 776   }
 777
 778   if (!head->key) {
 779     CDEBUG0(dict_collapse, "Do not collapse the head, you stupid programm");
 780     return;
 781   }
 782
 783   if (head->content || head->free_f ||
 784       xbt_dynar_length(head->sub) != 1) {
 785     CDEBUG0(dict_collapse, "Cannot collapse");
 786     return; /* cannot collapse */
 787   }
 788
 789   child = xbt_dynar_get_as(head->sub, 0, xbt_dictelm_t);
 790
 791   /* Get the child's key as new key */
 792   CDEBUG2(dict_collapse,
 793           "Do collapse with only child %.*s", child->key_len, child->key);
 794
 795   head->content  = child->content;
 796   head->free_f = child->free_f;
 797   xbt_free(head->key);
 798   head->key      = child->key;
 799   head->key_len  = child->key_len;
 800
 801   xbt_dynar_free_container(&(head->sub)) ;
 802
 803   head->sub = child->sub;
 804   xbt_free(child);
 805 }
 806
 807 /**
 808  * _xbt_dict_remove_rec:
 809  *
 810  * @head: the head of the dict
 811  * @key: the key of the data to be removed
 812  * @offset: offset on the key
 813  * @Returns: xbt_error_t
 814  *
 815  * Remove the entry associated with the given @key
 816  */
 817 xbt_error_t
 818 _xbt_dictelm_remove_rec(xbt_dictelm_t head,
 819                          const char  *key,
 820                          int          key_len,
 821                          int          offset) {
 822   xbt_error_t errcode = no_error;
 823
 824   /* there is no key to search, we did enough recursion => kill current */
 825   if (offset >= key_len) {
 826     int killme = 0; /* do I need to suicide me ? */
 827
 828     if (head->content && head->free_f) {
 829       head->free_f(head->content);
 830     }
 831
 832     killme = !xbt_dynar_length(head->sub);
 833     head->content  = NULL;
 834     head->free_f = NULL;
 835     _collapse_if_need(head, -1, offset);
 836
 837     if (killme) {
 838       DEBUG0("kill this node");
 839       head->key_len = 0; /* killme. Cleanup done one step higher in recursion */
 840     }
 841
 842     return errcode;
 843
 844   } else {
 845     int match      =      0;
 846     int pos        =      0;
 847     int old_offset = offset;
 848
 849     /*** Search where is the good child, and how good it is ***/
 850     _xbt_dictelm_child_search(head, key, key_len, &pos, &offset, &match);
 851
 852     switch (match) {
 853
 854     case 1: /* A child have exactly this key           => recurse */
 855     case 2: /* A child constitutes a prefix of the key => recurse */
 856
 857       {
 858         s_xbt_dictelm_t *p_child = NULL;
 859
 860         p_child = xbt_dynar_get_as(head->sub, pos, s_xbt_dictelm_t*);
 861         /*DEBUG5("Recurse on child %d of %p to remove %.*s (prefix=%d)",
 862           pos, (void*)p_child, key+offset, key_len-offset,offset);*/
 863         TRY(_xbt_dictelm_remove_rec(p_child, key, key_len, offset));
 864
 865         _collapse_if_need(head, pos, old_offset);
 866         return no_error;
 867       }
 868
 869
 870     case 0: /* no child have a common prefix */
 871     case 3: /* The key is a prefix of the child => not found */
 872     case 4: /* A child share a common prefix with this key => not found */
 873
 874       return mismatch_error;
 875
 876
 877     default:
 878       RAISE_IMPOSSIBLE;
 879
 880     }
 881   }
 882 }
 883
 884 /**
 885  * xbt_dictelm_remove_ext:
 886  *
 887  * @head: the head of the dict
 888  * @key: the key of the data to be removed
 889  * @Returns: xbt_error_t
 890  *
 891  * Remove the entry associated with the given @key
 892  */
 893 xbt_error_t
 894 xbt_dictelm_remove_ext(xbt_dictelm_t head,
 895                         const char  *key,
 896                         int          key_len) {
 897   /* there is no head, go to hell */
 898   if (!head) {
 899     RAISE0(mismatch_error, "there is no head, go to hell");
 900   }
 901
 902   return _xbt_dictelm_remove_rec(head, key, key_len, 0);
 903 }
 904
 905 /**
 906  * xbt_dictelm_remove:
 907  *
 908  * @head: the head of the dict
 909  * @key: the key of the data to be removed
 910  * @Returns: xbt_error_t
 911  *
 912  * Remove the entry associated with the given @key
 913  */
 914 xbt_error_t
 915 xbt_dictelm_remove(xbt_dictelm_t head,
 916                     const char     *key) {
 917   return _xbt_dictelm_remove_rec(head, key, 1+strlen(key),0);
 918 }
 919
 920 /*----[ _xbt_dict_dump_rec ]------------------------------------------------*/
 921 /* private function to do the job of xbt_dict_dump recursively              */
 922 /*---------------------------------------------------------------------------*/
 923 static
 924 void
 925 _xbt_dictelm_dump_rec(xbt_dictelm_t  head,
 926                        int             offset,
 927                        void_f_pvoid_t *output) {
 928   xbt_dictelm_t child   =     NULL;
 929   char          *key     =     NULL;
 930   int            key_len =        0;
 931   int            i       =        0;
 932
 933   if (!head)
 934     return;
 935
 936   printf("[%p] ", (void*)head);
 937
 938   key     = head->key;
 939   key_len = head->key_len;
 940
 941   if (key_len)
 942     printf ("  ");
 943
 944   for (i = 0; i < offset; i++)
 945     printf("-");
 946
 947   fflush(stdout);
 948
 949   if (key) {
 950
 951     if (!key_len) {
 952       printf ("HEAD");
 953     } else {
 954       char *key_string = NULL;
 955
 956       key_string = xbt_malloc(key_len*2+1);
 957       _xbt_bytes_to_string(key, key_len, key_string);
 958
 959       printf("%.*s|(%d)", key_len-offset, key_string + offset, offset);
 960
 961       xbt_free(key_string);
 962     }
 963
 964   }
 965
 966   printf(" -> ");
 967
 968   if (head->content) {
 969
 970     if (output) {
 971       output(head->content);
 972     } else {
 973       printf("(data)");
 974     }
 975
 976   } else {
 977     printf("(null)");
 978   }
 979
 980   printf("    \t\t\t[ %lu child(s) ]\n", xbt_dynar_length(head->sub));
 981
 982   xbt_dynar_foreach(head->sub, i, child)
 983     _xbt_dictelm_dump_rec(child, child->offset, output);
 984
 985 }
 986
 987 /**
 988  * xbt_dictelm_dump:
 989  *
 990  * @head: the head of the dict
 991  * @output: a function to dump each data in the tree
 992  * @Returns: xbt_error_t
 993  *
 994  * Ouputs the content of the structure. (for debuging purpose). @ouput is a
 995  * function to output the data. If NULL, data won't be displayed.
 996  */
 997
 998 void
 999 xbt_dictelm_dump(xbt_dictelm_t  head,
1000                   void_f_pvoid_t *output) {
1001   _xbt_dictelm_dump_rec(head, 0, output);
1002 }
1003
1004 /**
1005  * xbt_dictelm_print_fct:
1006  *
1007  * @data:
1008  *
1009  * To dump multidict, this function dumps a dict
1010  */
1011
1012 void
1013 xbt_dictelm_print_fct(void *data) {
1014   printf("tree %p", (void*)data);
1015 }
1016