Logo AND Algorithmique Numérique Distribuée

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