3 /* dict - a generic dictionnary, variation over the B-tree concept */
5 /* Copyright (c) 2003, 2004 Martin Quinson. All rights reserved. */
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. */
11 #include "portable.h" /* PRINTF_STR */
12 #include "dict_private.h" /* prototypes of this module */
14 XBT_LOG_EXTERNAL_CATEGORY(dict);
15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(dict_elm,dict,"Dictionaries internals");
17 XBT_LOG_NEW_SUBCATEGORY(dict_add,dict,"Dictionaries internals: elements addition");
18 XBT_LOG_NEW_SUBCATEGORY(dict_search,dict,"Dictionaries internals: searching");
19 XBT_LOG_NEW_SUBCATEGORY(dict_remove,dict,"Dictionaries internals: elements removal");
20 XBT_LOG_NEW_SUBCATEGORY(dict_collapse,dict,"Dictionaries internals: post-removal cleanup");
22 /*####[ Private prototypes ]#################################################*/
24 static _XBT_INLINE void _xbt_dictelm_alloc(char *key,
29 void_f_pvoid_t *free_f,
30 /*OUT*/s_xbt_dictelm_t **where);
31 static void _dictelm_wrapper_free(void*);
33 static _XBT_INLINE void _str_prefix_lgr(const char *key1,
41 static void _xbt_dictelm_dump_rec(s_xbt_dictelm_t *head,
43 void_f_pvoid_t *output);
47 static void _xbt_dictelm_set_rec(s_xbt_dictelm_t *head,
52 void_f_pvoid_t *free_f);
53 static void * _xbt_dictelm_get_rec(s_xbt_dictelm_t *head,
57 static void _xbt_dictelm_remove_rec(s_xbt_dictelm_t *head,
64 _collapse_if_need(s_xbt_dictelm_t *p_head,
71 * _xbt_nibble_to_char:
73 * Change any byte to a printable char
78 _xbt_nibble_to_char(unsigned char c) {
80 return c>9 ? c-10+'a' : c + '0';
84 * _xbt_bytes_to_string:
86 * Change any byte array to a printable string
87 * The length of string_container should at least be data_len*2+1
91 _xbt_bytes_to_string(char * const ptr,
93 char * const string_container) {
94 unsigned char *src = (unsigned char *)ptr;
95 char *dst = string_container;
98 *dst++ = _xbt_nibble_to_char(*src & 0x0f );
99 *dst++ = _xbt_nibble_to_char(*src++ & 0xf0 >> 4);
110 * _xbt_dictelm_alloc:
112 * Alloc a dict element with no child.
116 _xbt_dictelm_alloc(char *key,
121 void_f_pvoid_t *free_f,
122 /*OUT*/s_xbt_dictelm_t **pp_elm) {
123 s_xbt_dictelm_t *p_elm = NULL;
125 p_elm = xbt_new(s_xbt_dictelm_t,1);
128 p_elm->key_len = key_len;
129 p_elm->offset = offset;
130 p_elm->internal = internal;
131 p_elm->content = data;
132 p_elm->free_f = free_f;
133 p_elm->sub = xbt_dynar_new(sizeof(s_xbt_dictelm_t*), _dictelm_wrapper_free);
142 * @pp_elm: the dict elem to be freed
144 * Frees a dictionnary element with all its childs.
147 xbt_dictelm_free(s_xbt_dictelm_t **pp_elm) {
149 s_xbt_dictelm_t *p_elm = *pp_elm;
151 xbt_dynar_free(&(p_elm->sub));
157 if (p_elm->free_f && p_elm->content) {
158 p_elm->free_f(p_elm->content);
167 * _dictelm_wrapper_free:
169 * a wrapper to free dictelm with the right prototype to be usable within dynar
173 _dictelm_wrapper_free(void *pp_elm) {
174 DEBUG3("Free dictelm '%.*s' %p",
175 (*(s_xbt_dictelm_t**)pp_elm)->key_len, (*(s_xbt_dictelm_t**)pp_elm)->key,
177 xbt_dictelm_free((s_xbt_dictelm_t**)pp_elm);
180 /*####[ utility functions ]##################################################*/
185 * Returns the length of the common prefix of @str1 and @str2.
186 * Do make sure the strings are not null, this function don't
190 _str_prefix_lgr(const char *key1,
196 const int old_offset = *p_offset;
202 /*CDEBUG5(dict_search, "%s: [%.*s] <=> [%.*s]", __FUNCTION__,
203 key1,key_len1,key2,key_len2);*/
205 if (o < key_len1 && o < key_len2) {
207 while (key1[o] == key2[o]) {
210 if (!(o < key_len1 && o < key_len2))
218 if (o != old_offset) {
223 m = 1; /* exact match */
225 m = 2; /* child is prefix */
228 } else if (o >= key_len2) {
229 m = 3; /* key prefix of child */
231 DEBUG7("Common prefix. o=%d; key1=%.*s; key_len1=%d; key2=%.*s; key_len2=%d",
237 m = 4; /* Common prefix (=> common ancestor) */
247 * _dictelm_child_cmp:
249 * Compares two dictelm keys and return their matching (using the same
250 * convention than @_xbt_dict_child_search() )
254 _dict_child_cmp(s_xbt_dictelm_t *p_dict,
261 s_xbt_dictelm_t *p_child = NULL;
266 p_child = xbt_dynar_get_as(p_dict->sub, pos, s_xbt_dictelm_t*);
268 /* Compute the length of the prefix
269 and if the searched key is before or after cur */
270 _str_prefix_lgr(p_child->key, p_child->key_len,
275 if (m) /* found, get out */
278 if (o < p_child->key_len && (o >= key_len || key[o] < p_child->key[o])) {
284 CDEBUG6(dict_search, "Cmp '%.*s' and '%.*s' (offset=%d) => %d",
285 p_child->key_len - *p_offset, p_child->key + *p_offset,
286 key_len - *p_offset, key + *p_offset,
296 * _xbt_dict_child_search:
298 * Search where would be inserted @key between the childs of @p_elm.
300 * Returns position of the child having a common prefix with this key
301 * If *match==0, no child have a common prefix
302 * *pos is where to add the key
303 * If *match==1, A child (located at *pos) have exactly this key
304 * If *match==2, A child (located at *pos) constitutes a prefix of the key
305 * the recursion have to go on that guy
306 * *prefix = the size of the key eaten at this level
307 * If *match==3 The key is a prefix of the child at *pos
308 * If *match==4, A child (loc. at *pos) share a common prefix with this key
309 * *prefix = size of the prefix.
310 * If searching, that's a mismatch.
311 * If inserting, you have to break the child and create an
312 * internal node having {child, key} as childs
313 * offset is used in input and output. In input, that's the length of the key
314 * handled by previous levels of recursion. In output, that the one counting
319 _xbt_dictelm_child_search(s_xbt_dictelm_t *p_elm,
332 CDEBUG6(dict_search, "search child [%.*s] under [%.*s]=%p (len=%lu)",
334 p_elm ? (p_elm->key_len?p_elm->key_len:6) : 6,
335 p_elm ? PRINTF_STR(p_elm->key) : "(head)",
337 (p_elm&&p_elm->sub) ? xbt_dynar_length(p_elm->sub) : 0);
340 len = xbt_dynar_length(p_elm->sub);
351 _dict_child_cmp(p_elm, p_min, key, key_len, &o, &m, &cmp);
352 if(!m) { /* OK, maybe it is somewhere else. */
354 if (cmp<0) { /* Insert at the very beginning */
356 } else if (p_max<=0) { /* No way. It is not there. Insert at the very end */
361 _dict_child_cmp(p_elm, p_max, key, key_len, &o, &m, &cmp);
364 if(cmp>0) { /* Should be located at the end of the table */
366 } else { /* Too bad, let's go for a dichotomic search. */
367 while(p_max-p_min>1) {
368 _dict_child_cmp(p_elm, (p_min+p_max)/2, key, key_len, &o, &m, &cmp);
371 if(cmp<0) p_max=(p_min+p_max)/2;
372 if(cmp>0) p_min=(p_min+p_max)/2;
374 if(m) /* We have the element */
376 else /* it should be inserted just after p_min */
388 CDEBUG6(dict_search, "search [%.*s] in [%.*s]=%p => %s",
390 p_elm?(p_elm->key_len?p_elm->key_len:6):6, p_elm?PRINTF_STR(p_elm->key):"(head)",
392 ( m == 0 ? "no child have a common prefix" :
393 ( m == 1 ? "selected child have exactly this key" :
394 ( m == 2 ? "selected child constitutes a prefix" :
395 ( m == 3 ? "key is a prefix of selected child" :
396 (m == 4 ? "selected child share a prefix" :
397 "internal error")))))
402 * _xbt_dictelm_change_value:
404 * Change the value of the dictelm, making sure to free the old one, if any. The node also become a non-internal one.
408 _xbt_dictelm_change_value(s_xbt_dictelm_t *p_elm,
410 void_f_pvoid_t *free_f) {
412 if (p_elm->content && p_elm->free_f) {
413 p_elm->free_f(p_elm->content);
416 p_elm->free_f = free_f;
417 p_elm->content = data;
418 p_elm->internal = FALSE;
422 * _xbt_dictelm_set_rec:
424 * @head: the head of the dict
425 * @key: the key to set the new data
426 * @offset: offset on key.
427 * @data: the data to add in the dict
429 * set the @data in the structure under the @key. The @key is destroyed
430 * in the process. Think to strdup it before.
432 * This is a helper function to xbt_dict_set which locks the struct and
433 * strdup the key before action.
436 _xbt_dictelm_set_rec(s_xbt_dictelm_t *p_head,
441 void_f_pvoid_t *free_f) {
444 const int old_offset = offset;
446 CDEBUG6(dict_add, "--> Insert '%.*s' after '%.*s' (offset=%d) in tree %p",
448 ((p_head && p_head->key) ? p_head->key_len : 6),
449 ((p_head && p_head->key) ? p_head->key : "(head)"),
450 offset, (void*)p_head);
452 /*** The trivial cases first ***/
454 /* there is no key (we did enough recursion), change the value of head */
455 if (offset >= key_len) {
457 CDEBUG0(dict_add, "--> Change the value of head");
459 _xbt_dictelm_change_value(p_head, data, free_f);
460 free(key); /* Keep the key used in the tree */
465 /*** Search where to add this child, and how ***/
466 _xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
468 CDEBUG3(dict_add, "child_search => pos=%d, offset=%d, match=%d",
473 case 0: /* no child have a common prefix */
475 s_xbt_dictelm_t *p_child = NULL;
477 _xbt_dictelm_alloc(key, key_len, offset, FALSE, data, free_f, &p_child);
478 CDEBUG1(dict_add, "-> Add a child %p", (void*)p_child);
479 xbt_dynar_insert_at(p_head->sub, pos, &p_child);
484 case 1: /* A child have exactly this key => change its value*/
486 s_xbt_dictelm_t *p_child = NULL;
488 p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
489 CDEBUG1(dict_add, "-> Change the value of the child %p", (void*)p_child);
490 _xbt_dictelm_change_value(p_child, data, free_f);
497 case 2: /* A child constitutes a prefix of the key => recurse */
499 s_xbt_dictelm_t *p_child = NULL;
501 p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
502 CDEBUG2(dict_add,"-> Recurse on %p (offset=%d)", (void*)p_child, offset);
504 _xbt_dictelm_set_rec(p_child, key, key_len,
505 offset, data, free_f);
509 case 3: /* The key is a prefix of the child => child becomes child of p_new */
511 s_xbt_dictelm_t *p_new = NULL;
512 s_xbt_dictelm_t *p_child = NULL;
514 p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
515 _xbt_dictelm_alloc(key, key_len, old_offset, FALSE, data, free_f, &p_new);
517 CDEBUG2(dict_add, "-> The child %p become child of new dict (%p)",
518 (void*)p_child, (void*)p_new);
520 xbt_dynar_push(p_new->sub, &p_child);
521 p_child->offset = offset;
522 xbt_dynar_set(p_head->sub, pos, &p_new);
527 case 4: /* A child share a common prefix with this key => Common ancestor */
529 s_xbt_dictelm_t *p_new = NULL;
530 s_xbt_dictelm_t *p_child = NULL;
531 s_xbt_dictelm_t *p_anc = NULL;
532 char *anc_key = NULL;
533 int anc_key_len = offset;
535 _xbt_dictelm_alloc(key, key_len, offset, FALSE, data, free_f, &p_new);
536 p_child=xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
538 /* memdup the old key, taking care of the terminating NULL byte */
539 anc_key = xbt_malloc(anc_key_len+1);
540 memcpy(anc_key, key, anc_key_len);
541 anc_key[anc_key_len] = '\0';
544 _xbt_dictelm_alloc(anc_key, anc_key_len, old_offset, TRUE, NULL, NULL, &p_anc);
546 CDEBUG3(dict_add, "-> Make a common ancestor %p (%.*s)",
547 (void*)p_anc, anc_key_len, anc_key);
549 if (key[offset] < p_child->key[offset]) {
550 xbt_dynar_push(p_anc->sub, &p_new);
551 xbt_dynar_push(p_anc->sub, &p_child);
553 xbt_dynar_push(p_anc->sub, &p_child);
554 xbt_dynar_push(p_anc->sub, &p_new);
557 p_child->offset = offset;
559 xbt_dynar_set(p_head->sub, pos, &p_anc);
570 * xbt_dictelm_set_ext:
572 * @head: the head of the dict
573 * @key: the key to set the new data
574 * @data: the data to add in the dict
576 * set the @data in the structure under the @key, which can be any kind
577 * of data, as long as its length is provided in @key_len.
580 xbt_dictelm_set_ext(s_xbt_dictelm_t **pp_head,
584 void_f_pvoid_t *free_f) {
585 s_xbt_dictelm_t *p_head = *pp_head;
588 /* Make sure the copied key is NULL-terminated */
589 key = xbt_malloc(key_len+1);
590 memcpy(key, _key, key_len);
593 /* there is no head, create it */
595 s_xbt_dictelm_t *p_child = NULL;
597 CDEBUG0(dict_add, "Create an head");
599 /* The head is priviledged by being the only one with a NULL key */
600 _xbt_dictelm_alloc(NULL, 0, 0, TRUE, NULL, NULL, &p_head);
602 CDEBUG2(dict_add, "Push %.*s as child of this head",key_len,key);
603 _xbt_dictelm_alloc(key, key_len, 0, FALSE, data, free_f, &p_child);
604 xbt_dynar_insert_at(p_head->sub, 0, &p_child);
611 _xbt_dictelm_set_rec(p_head, key, key_len, 0, data, free_f);
617 * @head: the head of the dict
618 * @key: the key to set the new data
619 * @data: the data to add in the dict
621 * set the @data in the structure under the @key, which is a
622 * null terminated string.
625 xbt_dictelm_set(s_xbt_dictelm_t **pp_head,
628 void_f_pvoid_t *free_f) {
630 xbt_dictelm_set_ext(pp_head, _key, strlen(_key), data, free_f);
636 * @head: the head of the dict
637 * @key: the key to find data
638 * @offset: offset on the key
639 * @data: the data that we are looking for
641 * Search the given @key. Throws not_found_error when not found.
645 _xbt_dictelm_get_rec(s_xbt_dictelm_t *p_head,
650 CDEBUG3(dict_search, "Search %.*s in %p", key_len, key, (void*)p_head);
652 /*** The trivial case first ***/
654 /* we did enough recursion, we're done */
655 if (offset >= key_len) {
656 return p_head->content;
663 /*** Search where is the good child, and how good it is ***/
664 _xbt_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
668 case 0: /* no child have a common prefix */
669 THROW2(not_found_error,0,"key '%.*s' not found",key_len,key);
671 case 1: /* A child have exactly this key => Got it */
673 s_xbt_dictelm_t *p_child = NULL;
674 p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
675 return p_child->content;
678 case 2: /* A child constitutes a prefix of the key => recurse */
680 s_xbt_dictelm_t *p_child = NULL;
682 p_child = xbt_dynar_get_as(p_head->sub, pos, s_xbt_dictelm_t*);
684 return _xbt_dictelm_get_rec(p_child, key, key_len, offset);
687 case 3: /* The key is a prefix of the child => not found */
688 THROW2(not_found_error,0,"key %.*s not found",key_len,key);
690 case 4: /* A child share a common prefix with this key => not found */
691 THROW2(not_found_error,0,"key %.*s not found",key_len,key);
700 * xbt_dictelm_get_ext:
702 * @head: the head of the dict
703 * @key: the key to find data
704 * @data: the data that we are looking for
706 * Search the given @key. Throws not_found_error when not found.
709 xbt_dictelm_get_ext(s_xbt_dictelm_t *p_head,
712 /* there is no head, go to hell */
714 THROW2(not_found_error,0,"Key '%.*s' not found in dict",key_len,key);
716 return _xbt_dictelm_get_rec(p_head, key, key_len, 0);
722 * @head: the head of the dict
723 * @key: the key to find data
724 * @data: the data that we are looking for
726 * Search the given @key. Throws not_found_error when not found.
729 xbt_dictelm_get(s_xbt_dictelm_t *p_head,
732 return xbt_dictelm_get_ext(p_head, key, strlen(key));
735 /*----[ _xbt_dict_collapse ]------------------------------------------------*/
738 _collapse_if_need(xbt_dictelm_t head,
741 xbt_dictelm_t child = NULL;
743 CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, (void*)head);
746 /* Remove the child if |it's key| == 0 (meaning it's dead) */
747 child = xbt_dynar_get_as(head->sub, pos, xbt_dictelm_t);
749 if (offset >= child->key_len) {
751 xbt_assert0(xbt_dynar_length(child->sub) == 0,
752 "Found a dead child with grand childs. Internal error");
754 CDEBUG1(dict_collapse, "Remove dead child %p.... ", (void*)child);
755 xbt_dynar_remove_at(head->sub, pos, &child);
756 xbt_dictelm_free(&child);
761 CDEBUG0(dict_collapse, "Do not collapse the head, you stupid programm");
765 if (head->content || head->free_f ||
766 xbt_dynar_length(head->sub) != 1) {
767 CDEBUG0(dict_collapse, "Cannot collapse");
768 return; /* cannot collapse */
771 child = xbt_dynar_get_as(head->sub, 0, xbt_dictelm_t);
773 /* Get the child's key as new key */
774 CDEBUG2(dict_collapse,
775 "Do collapse with only child %.*s", child->key_len, child->key);
777 head->content = child->content;
778 head->free_f = child->free_f;
780 head->key = child->key;
781 head->key_len = child->key_len;
783 xbt_dynar_free_container(&(head->sub)) ;
785 head->sub = child->sub;
790 * _xbt_dict_remove_rec:
792 * @head: the head of the dict
793 * @key: the key of the data to be removed
794 * @offset: offset on the key
796 * Remove the entry associated with the given @key. Throws not_found_error.
799 _xbt_dictelm_remove_rec(xbt_dictelm_t head,
804 /* there is no key to search, we did enough recursion => kill current */
805 if (offset >= key_len) {
806 int killme = 0; /* do I need to suicide me ? */
808 if (head->content && head->free_f) {
809 head->free_f(head->content);
812 killme = !xbt_dynar_length(head->sub);
813 head->content = NULL;
815 _collapse_if_need(head, -1, offset);
818 DEBUG0("kill this node");
819 head->key_len = 0; /* killme. Cleanup done one step higher in recursion */
827 int old_offset = offset;
829 /*** Search where is the good child, and how good it is ***/
830 _xbt_dictelm_child_search(head, key, key_len, &pos, &offset, &match);
834 case 1: /* A child have exactly this key => recurse */
835 case 2: /* A child constitutes a prefix of the key => recurse */
838 s_xbt_dictelm_t *p_child = NULL;
840 p_child = xbt_dynar_get_as(head->sub, pos, s_xbt_dictelm_t*);
841 /*DEBUG5("Recurse on child %d of %p to remove %.*s (prefix=%d)",
842 pos, (void*)p_child, key+offset, key_len-offset,offset);*/
843 _xbt_dictelm_remove_rec(p_child, key, key_len, offset);
845 _collapse_if_need(head, pos, old_offset);
850 case 0: /* no child have a common prefix */
851 case 3: /* The key is a prefix of the child => not found */
852 case 4: /* A child share a common prefix with this key => not found */
854 THROW2(not_found_error,0,"Unable to remove key '%.*s': not found",key_len,key);
864 * xbt_dictelm_remove_ext:
866 * @head: the head of the dict
867 * @key: the key of the data to be removed
869 * Remove the entry associated with the given @key. Throws not_found_err
872 xbt_dictelm_remove_ext(xbt_dictelm_t head,
875 /* there is no head, go to hell */
877 THROW1(arg_error,0,"Asked to remove key %s from NULL dict",key);
879 _xbt_dictelm_remove_rec(head, key, key_len, 0);
883 * xbt_dictelm_remove:
885 * @head: the head of the dict
886 * @key: the key of the data to be removed
888 * Throws not_found when applicable
891 xbt_dictelm_remove(xbt_dictelm_t head,
893 _xbt_dictelm_remove_rec(head, key, strlen(key),0);
896 /*----[ _xbt_dict_dump_rec ]------------------------------------------------*/
897 /* private function to do the job of xbt_dict_dump recursively */
898 /*---------------------------------------------------------------------------*/
901 _xbt_dictelm_dump_rec(xbt_dictelm_t head,
903 void_f_pvoid_t *output) {
904 xbt_dictelm_t child = NULL;
912 printf("[%p] ", (void*)head);
915 key_len = head->key_len;
920 for (i = 0; i < offset; i++)
929 } else if (key[key_len] != '\0') {
930 char *key_string = NULL;
932 key_string = xbt_malloc(key_len*2+1);
933 _xbt_bytes_to_string(key, key_len, key_string);
935 printf("%.*s|(%d)", key_len-2*offset, key_string + 2*offset, offset);
939 printf("%.*s|(%d)", key_len-offset, key + offset , offset);
948 output(head->content);
953 } else if (head->internal) {
954 printf("(internal node)");
959 printf(" \t\t\t[ %lu child(s) ]\n", xbt_dynar_length(head->sub));
961 xbt_dynar_foreach(head->sub, i, child)
962 _xbt_dictelm_dump_rec(child, child->offset, output);
969 * @head: the head of the dict
970 * @output: a function to dump each data in the tree
972 * Ouputs the content of the structure. (for debuging purpose). @ouput is a
973 * function to output the data. If NULL, data won't be displayed.
977 xbt_dictelm_dump(xbt_dictelm_t head,
978 void_f_pvoid_t *output) {
979 _xbt_dictelm_dump_rec(head, 0, output);
983 * xbt_dictelm_print_fct:
987 * To dump multidict, this function dumps a dict
991 xbt_dictelm_print_fct(void *data) {
992 printf("tree %p", (void*)data);