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