src/xbt/dict_elm.c

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