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