Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Fix a little bug
[simgrid.git] / 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   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                            /* OUT */void **data) {
650
651   gras_error_t errcode = no_error;
652
653   CDEBUG3(dict_search, "Search %.*s in %p", key_len, key, p_head); 
654
655   /*** The trivial case first ***/
656
657   /* we did enough recursion, we're done */
658   if (offset >= key_len) {
659     *data = p_head->content;
660
661     return errcode;
662   }
663
664   {
665     int match = 0;
666     int pos   = 0;
667
668     *data = NULL; // Make it ready to answer 'not found' in one operation
669
670     /*** Search where is the good child, and how good it is ***/
671     _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
672
673     switch (match) {
674
675     case 0: /* no child have a common prefix */
676       return mismatch_error;
677
678     case 1: /* A child have exactly this key => Got it */
679       {
680         gras_dictelm_t *p_child = NULL;
681
682         gras_dynar_get(p_head->sub, pos, &p_child);
683         *data = p_child->content;
684
685         return errcode;
686       }
687
688     case 2: /* A child constitutes a prefix of the key => recurse */
689       {
690         gras_dictelm_t *p_child = NULL;
691
692         gras_dynar_get(p_head->sub, pos, &p_child);
693
694         return _gras_dictelm_get_rec(p_child, key, key_len, offset, data);
695       }
696
697     case 3: /* The key is a prefix of the child => not found */
698       return mismatch_error;
699
700     case 4: /* A child share a common prefix with this key => not found */
701       return mismatch_error;
702
703     default:
704       RAISE_IMPOSSIBLE;
705     }
706   }
707 }
708
709 /**
710  * gras_dictelm_get_ext:
711  *
712  * @head: the head of the dict
713  * @key: the key to find data
714  * @data: the data that we are looking for
715  * @Returns: gras_error
716  *
717  * Search the given @key. mismatch_error when not found.
718  */
719 gras_error_t
720 gras_dictelm_get_ext(gras_dictelm_t *p_head,
721                           const char     *key,
722                           int             key_len,
723                           /* OUT */void **data) {
724   /* there is no head, go to hell */
725   if (!p_head) {
726     return mismatch_error;
727   }
728
729   return _gras_dictelm_get_rec(p_head, key, key_len, 0, data);
730 }
731
732 /**
733  * gras_dictelm_get:
734  *
735  * @head: the head of the dict
736  * @key: the key to find data
737  * @data: the data that we are looking for
738  * @Returns: gras_error
739  *
740  * Search the given @key. mismatch_error when not found.
741  */
742 gras_error_t
743 gras_dictelm_get(gras_dictelm_t    *p_head,
744                    const char     *key,
745                    /* OUT */void **data) {
746
747   return gras_dictelm_get_ext(p_head, key, 1+strlen(key), data);
748 }
749
750 /*----[ _gras_dict_collapse ]------------------------------------------------*/
751 static inline
752 void
753 _collapse_if_need(gras_dictelm_t *p_head,
754                   int             pos,
755                   int             offset) {
756   gras_dictelm_t  *p_child = NULL;
757
758   CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, p_head); fflush(stdout);
759
760   if (pos >= 0) {
761     /* Remove the child if |it's key| == 0 (meaning it's dead) */
762     gras_dynar_get(p_head->sub, pos, &p_child);
763
764     if (offset >= p_child->key_len) {
765
766       gras_assert0(gras_dynar_length(p_child->sub) == 0,
767                    "Found a dead child with grand childs. Internal error");
768
769       CDEBUG1(dict_collapse, "Remove dead child %p.... ", p_child);
770       gras_dynar_remove_at(p_head->sub, pos, &p_child);
771     }
772   }
773
774   if (!p_head->key) {
775     CDEBUG0(dict_collapse, "Do not collapse the head, you stupid programm");
776     return;
777   }
778
779   if (p_head->content || p_head->free_ctn ||
780       gras_dynar_length(p_head->sub) != 1) {
781     CDEBUG0(dict_collapse, "Cannot collapse");
782     return; /* cannot collapse */
783   }
784
785   gras_dynar_get(p_head->sub, 0, &p_child);
786
787   /* Get the child's key as new key */
788   CDEBUG2(dict_collapse,
789           "Do collapse with only child %.*s", p_child->key_len, p_child->key);
790
791   p_head->content  = p_child->content;
792   p_head->free_ctn = p_child->free_ctn;
793   free(p_head->key);
794   p_head->key      = p_child->key;
795   p_head->key_len  = p_child->key_len;
796
797   gras_dynar_free_container(p_head->sub) ;
798
799   p_head->sub = p_child->sub;
800   free(p_child);
801 }
802
803 /**
804  * _gras_dict_remove_rec:
805  *
806  * @head: the head of the dict
807  * @key: the key of the data to be removed
808  * @offset: offset on the key
809  * @Returns: gras_error_t
810  *
811  * Remove the entry associated with the given @key
812  */
813 gras_error_t
814 _gras_dictelm_remove_rec(gras_dictelm_t *p_head,
815                          const char  *key,
816                          int          key_len,
817                          int          offset) {
818   gras_error_t errcode = no_error;
819
820   /* there is no key to search, we did enough recursion => kill current */
821   if (offset >= key_len) {
822     int killme = 0; /* do I need to suicide me ? */
823
824     if (p_head->content && p_head->free_ctn) {
825       p_head->free_ctn(p_head->content);
826     }
827
828     killme = !gras_dynar_length(p_head->sub);
829     p_head->content  = NULL;
830     p_head->free_ctn = NULL;
831     _collapse_if_need(p_head, -1, offset);
832
833     if (killme) {
834       DEBUG0("kill this node");
835       p_head->key_len = 0; /* killme. Cleanup done one step higher in recursion */
836     }
837
838     return errcode;
839
840   } else {
841     int match      =      0;
842     int pos        =      0;
843     int old_offset = offset;
844
845     /*** Search where is the good child, and how good it is ***/
846     _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
847
848     switch (match) {
849
850     case 1: /* A child have exactly this key           => recurse */
851     case 2: /* A child constitutes a prefix of the key => recurse */
852
853       {
854         gras_dictelm_t *p_child = NULL;
855
856         gras_dynar_get(p_head->sub, pos, &p_child);
857         /*DEBUG5("Recurse on child %d of %p to remove %.*s (prefix=%d)",
858           pos, p_child, key+offset, key_len-offset,offset);*/
859         TRY(_gras_dictelm_remove_rec(p_child, key, key_len, offset));
860
861         _collapse_if_need(p_head, pos, old_offset);
862         return no_error;
863       }
864
865
866     case 0: /* no child have a common prefix */
867     case 3: /* The key is a prefix of the child => not found */
868     case 4: /* A child share a common prefix with this key => not found */
869
870       return mismatch_error;
871
872
873     default:
874       RAISE_IMPOSSIBLE;
875
876     }
877   }
878 }
879
880 /**
881  * gras_dictelm_remove_ext:
882  *
883  * @head: the head of the dict
884  * @key: the key of the data to be removed
885  * @Returns: gras_error_t
886  *
887  * Remove the entry associated with the given @key
888  */
889 gras_error_t
890 gras_dictelm_remove_ext(gras_dictelm_t *p_head,
891                      const char  *key,
892                      int          key_len) {
893   /* there is no head, go to hell */
894   if (!p_head) {
895     RAISE0(mismatch_error, "there is no head, go to hell");
896   }
897   
898   return _gras_dictelm_remove_rec(p_head, key, key_len, 0);
899 }
900
901 /**
902  * gras_dictelm_remove:
903  *
904  * @head: the head of the dict
905  * @key: the key of the data to be removed
906  * @Returns: gras_error_t
907  *
908  * Remove the entry associated with the given @key
909  */
910 gras_error_t
911 gras_dictelm_remove(gras_dictelm_t *p_head,
912                     const char     *key) {
913   return _gras_dictelm_remove_rec(p_head, key, 1+strlen(key),0);
914 }
915
916 /*----[ _gras_dict_dump_rec ]------------------------------------------------*/
917 /* private function to do the job of gras_dict_dump recursively              */
918 /*---------------------------------------------------------------------------*/
919 static
920 gras_error_t
921 _gras_dictelm_dump_rec(gras_dictelm_t *p_head,
922                        int             offset,
923                        void_f_pvoid_t *output) {
924   gras_error_t  errcode = no_error;
925   gras_dictelm_t  *p_child =     NULL;
926   char         *key     =     NULL;
927   int           key_len =        0;
928   int           i       =        0;
929
930   if (!p_head)
931     return no_error;
932
933   printf("[%p] ", p_head);
934
935   key     = p_head->key;
936   key_len = p_head->key_len;
937
938   if (key_len) {
939     printf ("  ");
940   }
941
942   for (i = 0; i < offset; i++) {
943     printf("-");
944   }
945
946   fflush(stdout);
947
948   if (key) {
949
950     if (!key_len) {
951       printf ("HEAD");
952     } else {
953       char *key_string = NULL;
954
955       key_string = malloc(key_len*2+1);
956       if (!key_string)
957         RAISE_MALLOC;
958
959       _gras_bytes_to_string(key, key_len, key_string);
960
961       printf("%.*s|(%d)", key_len-offset, key_string + offset, offset);
962
963       free(key_string);
964     }
965
966   }
967
968   printf(" -> ");
969
970   if (p_head->content) {
971
972     if (output) {
973       output(p_head->content);
974     } else {
975       printf("(data)");
976     }
977
978   } else {
979     printf("(null)");
980   }
981
982   printf("    \t\t\t[ %d child(s) ]\n", gras_dynar_length(p_head->sub));
983
984   gras_dynar_foreach(p_head->sub, i, p_child) 
985     TRY(_gras_dictelm_dump_rec(p_child, p_child->offset, output));
986
987   return errcode;
988 }
989
990 /**
991  * gras_dictelm_dump:
992  *
993  * @head: the head of the dict
994  * @output: a function to dump each data in the tree
995  * @Returns: gras_error_t
996  *
997  * Ouputs the content of the structure. (for debuging purpose). @ouput is a
998  * function to output the data. If NULL, data won't be displayed.
999  */
1000
1001 gras_error_t
1002 gras_dictelm_dump(gras_dictelm_t *p_head,
1003                void_f_pvoid_t *output) {
1004   return _gras_dictelm_dump_rec(p_head, 0, output);
1005 }
1006
1007 /**
1008  * gras_dictelm_print_fct:
1009  *
1010  * @data:
1011  *
1012  * To dump multidict, this function dumps a dict
1013  */
1014
1015 void
1016 gras_dictelm_print_fct(void *data) {
1017   printf("tree %p", data);
1018 }
1019