Logo AND Algorithmique Numérique Distribuée

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