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