Logo AND Algorithmique Numérique Distribuée

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