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