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