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