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   /*CDEBUG3(dict_search, "%s: [%s] <=> [%s]", __FUNCTION__, s1, s2);*/
 241
 242   if (o < key_len1  &&  o < key_len2) {
 243
 244     while (key1[o] == key2[o]) {
 245       o++;
 246
 247       if (!(o < key_len1  &&  o < key_len2))
 248         break;
 249
 250     }
 251
 252   }
 253
 254
 255   if (o != old_offset) {
 256
 257     if (o >= key_len1) {
 258
 259       if (o >= key_len2) {
 260         m = 1;
 261       } else {
 262         m = 2;
 263       }
 264
 265     } else if (o >= key_len2) {
 266       m = 3;
 267     } else {
 268       m = 4;
 269     }
 270   }
 271
 272
 273   *p_offset = o;
 274   *p_match  = m;
 275 }
 276
 277 /**
 278  * _dictelm_child_cmp:
 279  *
 280  * Compares two dictelm keys and return their matching (using the same
 281  * convention than @_gras_dict_child_search() )
 282  */
 283 static inline
 284 void
 285 _dict_child_cmp(gras_dictelm_t *p_dict,
 286                 int          pos,
 287                 const char  *key,
 288                 const int    key_len,
 289                 int         *p_offset,
 290                 int         *p_match,
 291                 int         *p_cmp) {
 292   gras_dictelm_t  *p_child = NULL;
 293   int           cmp     = 0;
 294   int           o       = *p_offset;
 295   int           m       = *p_match;
 296
 297   gras_dynar_get(p_dict->sub, pos, &p_child);
 298
 299   /* Compute the length of the prefix
 300      and if the searched key is before or after cur */
 301   _str_prefix_lgr(p_child->key, p_child->key_len,
 302                   key,          key_len,
 303                   &o, &m);
 304
 305
 306   if (m) /* found, get out */
 307     goto end;
 308
 309   if (o < p_child->key_len  &&  (o >= key_len  ||  key[o] < p_child->key[o])) {
 310     cmp = -1;
 311   } else {
 312     cmp =  1;
 313   }
 314
 315   CDEBUG3(dict_search, "Cmp %s and %s => %d", p_child->key + *p_offset,
 316           key + *p_offset, cmp);
 317
 318  end:
 319   *p_offset = o;
 320   *p_match  = m;
 321   *p_cmp    = cmp;
 322 }
 323
 324 /**
 325  * _gras_dict_child_search:
 326  *
 327  * Search where would be inserted @key between the childs of @p_elm.
 328  *
 329  * Returns position of the child having a common prefix with this key
 330  * If *match==0, no child have a common prefix
 331  *               *pos is where to add the key
 332  * If *match==1, A child (located at *pos) have exactly this key
 333  * If *match==2, A child (located at *pos) constitutes a prefix of the key
 334  *               the recursion have to go on that guy
 335  *               *prefix = the size of the key eaten at this level
 336  * If *match==3  The key is a prefix of the child at *pos
 337  * If *match==4, A child (loc. at *pos) share a common prefix with this key
 338  *               *prefix = size of the prefix.
 339  *               If searching, that's a mismatch.
 340  *               If inserting, you have to break the child and create an
 341  *                 internal node having {child, key} as childs
 342  * offset is used in input and output. In input, that's the length of the key
 343  *  handled by previous levels of recursion. In output, that the one counting
 344  *  also this level.
 345  */
 346 static inline
 347 void
 348 _gras_dictelm_child_search(gras_dictelm_t *p_elm,
 349                            const char  *key,
 350                            int          key_len,
 351                            int         *p_pos,
 352                            int         *p_offset,
 353                            int         *p_match) {
 354
 355   int          p       = 0;
 356   int          o       = *p_offset;
 357   int          m       = 0;
 358   int          len     = 0;
 359
 360
 361   CDEBUG3(dict_search, "search child [%s] under [%s] (len=%d)",
 362           key,
 363           p_elm?p_elm->key:"(head)",
 364           (p_elm&&p_elm->sub)?gras_dynar_length(p_elm->sub):0);
 365
 366
 367   len = gras_dynar_length(p_elm->sub);
 368
 369   for (p = 0; p < len; p++) {
 370     int          cmp     = 0;
 371
 372     _dict_child_cmp(p_elm, p, key, key_len, &o, &m, &cmp);
 373
 374     if (m)
 375       break;
 376
 377     o = *p_offset;
 378     m = 0;
 379   }
 380
 381   *p_offset = o;
 382   *p_pos    = p;
 383   *p_match  = m;
 384   CDEBUG3(dict_search, "search [%s] in [%s] => %s",
 385           key,
 386           p_elm?p_elm->key:"(head)",
 387           ( m == 0 ? "no child have a common prefix" :
 388             ( m == 1 ? "selected child have exactly this key" :
 389               ( m == 2 ? "selected child constitutes a prefix" :
 390                 ( m == 3 ? "key is a prefix of selected child" :
 391                   (m == 4 ? "selected child share a prefix" :
 392                    "internal error")))))
 393           );
 394 }
 395
 396 /**
 397  * _gras_dictelm_change_value:
 398  *
 399  * Change the value of the dictelm, making sure to free the old one, if any.
 400  */
 401 static inline
 402 void
 403 _gras_dictelm_change_value(gras_dictelm_t    *p_elm,
 404                            void           *data,
 405                            void_f_pvoid_t *free_ctn) {
 406
 407   if (p_elm->content && p_elm->free_ctn) {
 408     p_elm->free_ctn(p_elm->content);
 409   }
 410
 411   p_elm->free_ctn = free_ctn;
 412   p_elm->content  = data;
 413 }
 414
 415 /**
 416  * _gras_dictelm_set_rec:
 417  *
 418  * @head: the head of the dict
 419  * @key: the key to set the new data
 420  * @offset: offset on key.
 421  * @data: the data to add in the dict
 422  * @Returns: a gras_error
 423  *
 424  * set the @data in the structure under the @key. The @key is destroyed
 425  * in the process. Think to strdup it before.
 426  *
 427  * This is a helper function to gras_dict_set which locks the struct and
 428  * strdup the key before action.
 429  */
 430 gras_error_t
 431 _gras_dictelm_set_rec(gras_dictelm_t     *p_head,
 432                          char            *key,
 433                          int              key_len,
 434                          int              offset,
 435                          void            *data,
 436                          void_f_pvoid_t  *free_ctn) {
 437   gras_error_t errcode    = no_error;
 438   int          match      = 0;
 439   int          pos        = 0;
 440   const int    old_offset = offset;
 441
 442   CDEBUG4(dict_add, "--> Insert '%s' after '%s' (offset=%d) in tree %p",
 443           key, ((p_head && p_head->key) ? p_head->key : "(head)"), offset,
 444           p_head);
 445
 446   /*** The trivial cases first ***/
 447
 448   /* there is no key (we did enough recursion), change the value of head */
 449   if (offset >= key_len) {
 450
 451     CDEBUG0(dict_add, "--> Change the value of head");
 452
 453     _gras_dictelm_change_value(p_head, data, free_ctn);
 454     free(key); /* Keep the key used in the tree */
 455
 456     return errcode;
 457   }
 458
 459   /*** Search where to add this child, and how ***/
 460   _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
 461
 462   CDEBUG3(dict_add, "child_search => pos=%d, offset=%d, match=%d",
 463           pos, offset, match);
 464
 465   switch (match) {
 466
 467   case 0: /* no child have a common prefix */
 468     {
 469       gras_dictelm_t *p_child = NULL;
 470
 471       TRY(_gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_child));
 472       CDEBUG1(dict_add, "-> Add a child %p", p_child);
 473       TRY(gras_dynar_insert_at(p_head->sub, pos, &p_child));
 474
 475       return errcode;
 476     }
 477
 478   case 1: /* A child have exactly this key => change its value*/
 479     {
 480       gras_dictelm_t *p_child = NULL;
 481
 482       gras_dynar_get(p_head->sub, pos, &p_child);
 483       CDEBUG1(dict_add, "-> Change the value of the child %p", p_child);
 484       _gras_dictelm_change_value(p_child, data, free_ctn);
 485
 486       free(key);
 487
 488       return errcode;
 489     }
 490
 491   case 2: /* A child constitutes a prefix of the key => recurse */
 492     {
 493       gras_dictelm_t *p_child = NULL;
 494
 495       gras_dynar_get(p_head->sub, pos, &p_child);
 496       CDEBUG2(dict_add,"-> Recurse on %p (offset=%d)", p_child, offset);
 497
 498       return _gras_dictelm_set_rec(p_child, key, key_len,
 499                                       offset, data, free_ctn);
 500     }
 501
 502   case 3: /* The key is a prefix of the child => child becomes child of p_new */
 503     {
 504       gras_dictelm_t *p_new   = NULL;
 505       gras_dictelm_t *p_child = NULL;
 506
 507       gras_dynar_get(p_head->sub, pos, &p_child);
 508       TRY(_gras_dictelm_alloc(key, key_len, old_offset, data, free_ctn, &p_new));
 509
 510       CDEBUG2(dict_add, "-> The child %p become child of new dict (%p)",
 511               p_child, p_new);
 512
 513       TRY(gras_dynar_push(p_new->sub, &p_child));
 514       p_child->offset = offset;
 515       TRY(gras_dynar_set(p_head->sub, pos, &p_new));
 516
 517       return errcode;
 518     }
 519
 520   case 4: /* A child share a common prefix with this key => Common ancestor */
 521     {
 522       gras_dictelm_t *p_new       = NULL;
 523       gras_dictelm_t *p_child     = NULL;
 524       gras_dictelm_t *p_anc       = NULL;
 525       char        *anc_key     = NULL;
 526       int          anc_key_len = offset;
 527
 528       TRY(_gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_new));
 529       gras_dynar_get(p_head->sub, pos, &p_child);
 530
 531       anc_key = memdup(key, anc_key_len);
 532
 533       TRY(_gras_dictelm_alloc(anc_key, anc_key_len, old_offset,
 534                               NULL, NULL, &p_anc));
 535
 536       CDEBUG2(dict_add, "-> Make a common ancestor %p (%s)", p_anc, anc_key);
 537
 538       if (key[offset] < p_child->key[offset]) {
 539         TRY(gras_dynar_push(p_anc->sub, &p_new));
 540         TRY(gras_dynar_push(p_anc->sub, &p_child));
 541       } else {
 542         TRY(gras_dynar_push(p_anc->sub, &p_child));
 543         TRY(gras_dynar_push(p_anc->sub, &p_new));
 544       }
 545
 546       p_child->offset = offset;
 547
 548       TRY(gras_dynar_set(p_head->sub, pos, &p_anc));
 549
 550       return errcode;
 551     }
 552
 553   default:
 554     RAISE_IMPOSSIBLE;
 555   }
 556
 557 }
 558
 559 /**
 560  * gras_dictelm_set_ext:
 561  *
 562  * @head: the head of the dict
 563  * @key: the key to set the new data
 564  * @data: the data to add in the dict
 565  * @Returns: a gras_error
 566  *
 567  * set the @data in the structure under the @key, which can be any kind
 568  * of data, as long as its length is provided in @key_len.
 569  */
 570 gras_error_t
 571 gras_dictelm_set_ext(gras_dictelm_t **pp_head,
 572                         const char      *_key,
 573                         int              key_len,
 574                         void            *data,
 575                         void_f_pvoid_t  *free_ctn) {
 576   gras_error_t  errcode =  no_error;
 577   gras_dictelm_t  *p_head  = *pp_head;
 578   char         *key     =  NULL;
 579
 580   key = memdup(_key, key_len);
 581   if (!key)
 582     RAISE_MALLOC;
 583
 584   /* there is no head, create it */
 585   if (!p_head) {
 586     gras_dictelm_t *p_child = NULL;
 587
 588     CDEBUG0(dict_add, "Create an head");
 589
 590     /* The head is priviledged by being the only one with a NULL key */
 591     TRY(_gras_dictelm_alloc(NULL, 0, 0, NULL, NULL, &p_head));
 592
 593     TRY(_gras_dictelm_alloc(key, key_len, 0, data, free_ctn, &p_child));
 594     TRY(gras_dynar_insert_at(p_head->sub, 0, &p_child));
 595
 596     *pp_head = p_head;
 597
 598     return errcode;
 599   }
 600
 601   return _gras_dictelm_set_rec(p_head, key, key_len, 0, data, free_ctn);
 602 }
 603
 604 /**
 605  * gras_dictelm_set:
 606  *
 607  * @head: the head of the dict
 608  * @key: the key to set the new data
 609  * @data: the data to add in the dict
 610  * @Returns: a gras_error
 611  *
 612  * set the @data in the structure under the @key, which is a
 613  * null terminated string.
 614  */
 615 gras_error_t
 616 gras_dictelm_set(gras_dictelm_t **pp_head,
 617                     const char      *_key,
 618                     void            *data,
 619                     void_f_pvoid_t  *free_ctn) {
 620
 621   return gras_dictelm_set_ext(pp_head, _key, 1+strlen(_key), data, free_ctn);
 622 }
 623
 624 /**
 625  * _gras_dict_get_rec:
 626  *
 627  * @head: the head of the dict
 628  * @key: the key to find data
 629  * @offset: offset on the key
 630  * @data: the data that we are looking for
 631  * @Returns: gras_error
 632  *
 633  * Search the given @key. mismatch_error when not found.
 634  */
 635 static
 636 gras_error_t
 637 _gras_dictelm_get_rec(gras_dictelm_t *p_head,
 638                            const char     *key,
 639                            int             key_len,
 640                            int             offset,
 641                            /* OUT */void **data) {
 642
 643   gras_error_t errcode = no_error;
 644
 645   CDEBUG2(dict_search, "Search %s in %p", key, p_head);
 646
 647   /*** The trivial case first ***/
 648
 649   /* we did enough recursion, we're done */
 650   if (offset >= key_len) {
 651     *data = p_head->content;
 652
 653     return errcode;
 654   }
 655
 656   {
 657     int match = 0;
 658     int pos   = 0;
 659
 660     *data = NULL; // Make it ready to answer 'not found' in one operation
 661
 662     /*** Search where is the good child, and how good it is ***/
 663     _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
 664
 665     switch (match) {
 666
 667     case 0: /* no child have a common prefix */
 668       return mismatch_error;
 669
 670     case 1: /* A child have exactly this key => Got it */
 671       {
 672         gras_dictelm_t *p_child = NULL;
 673
 674         gras_dynar_get(p_head->sub, pos, &p_child);
 675         *data = p_child->content;
 676
 677         return errcode;
 678       }
 679
 680     case 2: /* A child constitutes a prefix of the key => recurse */
 681       {
 682         gras_dictelm_t *p_child = NULL;
 683
 684         gras_dynar_get(p_head->sub, pos, &p_child);
 685
 686         return _gras_dictelm_get_rec(p_child, key, key_len, offset, data);
 687       }
 688
 689     case 3: /* The key is a prefix of the child => not found */
 690       return mismatch_error;
 691
 692     case 4: /* A child share a common prefix with this key => not found */
 693       return mismatch_error;
 694
 695     default:
 696       RAISE_IMPOSSIBLE;
 697     }
 698   }
 699 }
 700
 701 /**
 702  * gras_dictelm_get_ext:
 703  *
 704  * @head: the head of the dict
 705  * @key: the key to find data
 706  * @data: the data that we are looking for
 707  * @Returns: gras_error
 708  *
 709  * Search the given @key. mismatch_error when not found.
 710  */
 711 gras_error_t
 712 gras_dictelm_get_ext(gras_dictelm_t *p_head,
 713                           const char     *key,
 714                           int             key_len,
 715                           /* OUT */void **data) {
 716   /* there is no head, go to hell */
 717   if (!p_head) {
 718     return mismatch_error;
 719   }
 720
 721   return _gras_dictelm_get_rec(p_head, key, key_len, 0, data);
 722 }
 723
 724 /**
 725  * gras_dictelm_get:
 726  *
 727  * @head: the head of the dict
 728  * @key: the key to find data
 729  * @data: the data that we are looking for
 730  * @Returns: gras_error
 731  *
 732  * Search the given @key. mismatch_error when not found.
 733  */
 734 gras_error_t
 735 gras_dictelm_get(gras_dictelm_t    *p_head,
 736                    const char     *key,
 737                    /* OUT */void **data) {
 738
 739   return gras_dictelm_get_ext(p_head, key, 1+strlen(key), data);
 740 }
 741
 742 /*----[ _gras_dict_collapse ]------------------------------------------------*/
 743 static inline
 744 void
 745 _collapse_if_need(gras_dictelm_t *p_head,
 746                   int             pos,
 747                   int             offset) {
 748   gras_dictelm_t  *p_child = NULL;
 749
 750   CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, p_head); fflush(stdout);
 751
 752   if (pos >= 0) {
 753     /* Remove the child if |it's key| == 0 (meaning it's dead) */
 754     gras_dynar_get(p_head->sub, pos, &p_child);
 755
 756     if (offset >= p_child->key_len) {
 757
 758       gras_assert0(gras_dynar_length(p_child->sub) == 0,
 759                    "Found a dead child with grand childs. Internal error");
 760
 761       CDEBUG1(dict_collapse, "Remove dead child %p.... ", p_child);
 762       gras_dynar_remove_at(p_head->sub, pos, &p_child);
 763     }
 764   }
 765
 766   if (!p_head->key) {
 767     CDEBUG0(dict_collapse, "Do not collapse the head, you stupid programm");
 768     return;
 769   }
 770
 771   if (p_head->content || p_head->free_ctn ||
 772       gras_dynar_length(p_head->sub) != 1) {
 773     CDEBUG0(dict_collapse, "Cannot collapse");
 774     return; /* cannot collapse */
 775   }
 776
 777   gras_dynar_get(p_head->sub, 0, &p_child);
 778
 779   /* Get the child's key as new key */
 780   CDEBUG1(dict_collapse, "Do collapse with only child %s", p_child->key);
 781
 782   p_head->content  = p_child->content;
 783   p_head->free_ctn = p_child->free_ctn;
 784   free(p_head->key);
 785   p_head->key      = p_child->key;
 786   p_head->key_len  = p_child->key_len;
 787
 788   gras_dynar_free_container(p_head->sub) ;
 789
 790   p_head->sub = p_child->sub;
 791   free(p_child);
 792 }
 793
 794 /**
 795  * _gras_dict_remove_rec:
 796  *
 797  * @head: the head of the dict
 798  * @key: the key of the data to be removed
 799  * @offset: offset on the key
 800  * @Returns: gras_error_t
 801  *
 802  * Remove the entry associated with the given @key
 803  */
 804 gras_error_t
 805 _gras_dictelm_remove_rec(gras_dictelm_t *p_head,
 806                          const char  *key,
 807                          int          key_len,
 808                          int          offset) {
 809   gras_error_t errcode = no_error;
 810
 811   /* there is no key to search, we did enough recursion => kill current */
 812   if (offset >= key_len) {
 813     int killme = 0; /* do I need to suicide me ? */
 814
 815     if (p_head->content && p_head->free_ctn) {
 816       p_head->free_ctn(p_head->content);
 817     }
 818
 819     killme = !gras_dynar_length(p_head->sub);
 820     p_head->content  = NULL;
 821     p_head->free_ctn = NULL;
 822     _collapse_if_need(p_head, -1, offset);
 823
 824     if (killme) {
 825       DEBUG0("kill this node");
 826       p_head->key_len = 0; /* killme. Cleanup done one step higher in recursion */
 827     }
 828
 829     return errcode;
 830
 831   } else {
 832     int match      =      0;
 833     int pos        =      0;
 834     int old_offset = offset;
 835
 836     /*** Search where is the good child, and how good it is ***/
 837     _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
 838
 839     switch (match) {
 840
 841     case 1: /* A child have exactly this key           => recurse */
 842     case 2: /* A child constitutes a prefix of the key => recurse */
 843
 844       {
 845         gras_dictelm_t *p_child = NULL;
 846
 847         gras_dynar_get(p_head->sub, pos, &p_child);
 848         /*DEBUG4("Recurse on child %d of %p to remove %s (prefix=%d)",
 849           pos, p_child, key+offset, offset);*/
 850         TRY(_gras_dictelm_remove_rec(p_child, key, key_len, offset));
 851
 852         _collapse_if_need(p_head, pos, old_offset);
 853         return no_error;
 854       }
 855
 856
 857     case 0: /* no child have a common prefix */
 858     case 3: /* The key is a prefix of the child => not found */
 859     case 4: /* A child share a common prefix with this key => not found */
 860
 861       return mismatch_error;
 862
 863
 864     default:
 865       RAISE_IMPOSSIBLE;
 866
 867     }
 868   }
 869 }
 870
 871 /**
 872  * gras_dictelm_remove_ext:
 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_ext(gras_dictelm_t *p_head,
 882                      const char  *key,
 883                      int          key_len) {
 884   /* there is no head, go to hell */
 885   if (!p_head) {
 886     RAISE0(mismatch_error, "there is no head, go to hell");
 887   }
 888
 889   return _gras_dictelm_remove_rec(p_head, key, key_len, 0);
 890 }
 891
 892 /**
 893  * gras_dictelm_remove:
 894  *
 895  * @head: the head of the dict
 896  * @key: the key of the data to be removed
 897  * @Returns: gras_error_t
 898  *
 899  * Remove the entry associated with the given @key
 900  */
 901 gras_error_t
 902 gras_dictelm_remove(gras_dictelm_t *p_head,
 903                     const char     *key) {
 904   return _gras_dictelm_remove_rec(p_head, key, 1+strlen(key),0);
 905 }
 906
 907 /*----[ _gras_dict_dump_rec ]------------------------------------------------*/
 908 /* private function to do the job of gras_dict_dump recursively              */
 909 /*---------------------------------------------------------------------------*/
 910 static
 911 gras_error_t
 912 _gras_dictelm_dump_rec(gras_dictelm_t *p_head,
 913                        int             offset,
 914                        void_f_pvoid_t *output) {
 915   gras_error_t  errcode = no_error;
 916   gras_dictelm_t  *p_child =     NULL;
 917   char         *key     =     NULL;
 918   int           key_len =        0;
 919   int           i       =        0;
 920
 921   if (!p_head)
 922     return no_error;
 923
 924   printf("[%p] ", p_head);
 925
 926   key     = p_head->key;
 927   key_len = p_head->key_len;
 928
 929   if (key_len) {
 930     printf ("  ");
 931   }
 932
 933   for (i = 0; i < offset; i++) {
 934     printf("-");
 935   }
 936
 937   fflush(stdout);
 938
 939   if (key) {
 940
 941     if (!key_len) {
 942       printf ("HEAD");
 943     } else {
 944       char *key_string = NULL;
 945
 946       key_string = malloc(key_len*2+1);
 947       if (!key_string)
 948         RAISE_MALLOC;
 949
 950       _gras_bytes_to_string(key, key_len, key_string);
 951
 952       printf("%s|(%d)", key_string + offset, offset);
 953
 954       free(key_string);
 955     }
 956
 957   }
 958
 959   printf(" -> ");
 960
 961   if (p_head->content) {
 962
 963     if (output) {
 964       output(p_head->content);
 965     } else {
 966       printf("(data)");
 967     }
 968
 969   } else {
 970     printf("(null)");
 971   }
 972
 973   printf("    \t\t\t[ %d child(s) ]\n", gras_dynar_length(p_head->sub));
 974
 975   gras_dynar_foreach(p_head->sub, i, p_child)
 976     TRY(_gras_dictelm_dump_rec(p_child, p_child->offset, output));
 977
 978   return errcode;
 979 }
 980
 981 /**
 982  * gras_dictelm_dump:
 983  *
 984  * @head: the head of the dict
 985  * @output: a function to dump each data in the tree
 986  * @Returns: gras_error_t
 987  *
 988  * Ouputs the content of the structure. (for debuging purpose). @ouput is a
 989  * function to output the data. If NULL, data won't be displayed.
 990  */
 991
 992 gras_error_t
 993 gras_dictelm_dump(gras_dictelm_t *p_head,
 994                void_f_pvoid_t *output) {
 995   return _gras_dictelm_dump_rec(p_head, 0, output);
 996 }
 997
 998 /**
 999  * gras_dictelm_print_fct:
1000  *
1001  * @data:
1002  *
1003  * To dump multidict, this function dumps a dict
1004  */
1005
1006 void
1007 gras_dictelm_print_fct(void *data) {
1008   printf("tree %p", data);
1009 }
1010