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