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