3 /* dict - a generic dictionnary, variation over the B-tree concept */
5 /* Authors: Martin Quinson */
6 /* Copyright (C) 2003 the OURAGAN project. */
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. */
12 #include "gras_private.h"
13 #include "dict_private.h" /* prototypes of this module */
15 #include <stdlib.h> /* malloc() */
16 #include <string.h> /* strlen() */
20 GRAS_LOG_EXTERNAL_CATEGORY(dict);
21 GRAS_LOG_NEW_DEFAULT_SUBCATEGORY(dict_elm,dict);
23 GRAS_LOG_NEW_SUBCATEGORY(dict_add,dict);
24 GRAS_LOG_NEW_SUBCATEGORY(dict_search,dict);
25 GRAS_LOG_NEW_SUBCATEGORY(dict_remove,dict);
26 GRAS_LOG_NEW_SUBCATEGORY(dict_collapse,dict);
27 GRAS_LOG_NEW_SUBCATEGORY(dict_multi,dict);
29 /*####[ Private prototypes ]#################################################*/
31 static inline gras_error_t _gras_dictelm_alloc(char *key,
35 void_f_pvoid_t *free_ctn,
36 /*OUT*/gras_dictelm_t **where);
37 static void _dictelm_wrapper_free(void*);
39 static inline void _str_prefix_lgr(const char *key1,
47 static gras_error_t _gras_dictelm_dump_rec(gras_dictelm_t *head,
49 void_f_pvoid_t *output);
53 static gras_error_t _gras_dictelm_set_rec(gras_dictelm_t *head,
58 void_f_pvoid_t *free_ctn);
59 static gras_error_t _gras_dictelm_get_rec(gras_dictelm_t *head,
63 /* OUT */void **data);
64 static gras_error_t _gras_dictelm_remove_rec(gras_dictelm_t *head,
71 _collapse_if_need(gras_dictelm_t *p_head,
79 memdup(const void * const ptr,
80 const size_t length) {
81 void * new_ptr = NULL;
83 new_ptr = malloc(length);
86 memcpy(new_ptr, ptr, length);
93 * _gras_nibble_to_char:
95 * Change any byte to a printable char
100 _gras_nibble_to_char(unsigned char c) {
102 return c>9 ? c-10+'a' : c + '0';
106 * _gras_bytes_to_string:
108 * Change any byte array to a printable string
109 * The length of string_container should at least be data_len*2+1
113 _gras_bytes_to_string(char * const ptr,
115 char * const string_container) {
116 unsigned char *src = (unsigned char *)ptr;
117 char *dst = string_container;
120 *dst++ = _gras_nibble_to_char(*src & 0x0f );
121 *dst++ = _gras_nibble_to_char(*src++ & 0xf0 >> 4);
132 * _gras_dictelm_alloc:
134 * Alloc a dict element with no child.
139 _gras_dictelm_alloc(char *key,
143 void_f_pvoid_t *free_ctn,
144 /*OUT*/gras_dictelm_t **pp_elm) {
145 gras_error_t errcode = no_error;
146 gras_dictelm_t *p_elm = NULL;
148 if (!(p_elm = calloc(1, sizeof(gras_dictelm_t)))) {
149 if (free_ctn && data) {
157 p_elm->key_len = key_len;
158 p_elm->offset = offset;
159 p_elm->content = data;
160 p_elm->free_ctn = free_ctn;
162 errcode = gras_dynar_new(&(p_elm->sub), sizeof(gras_dictelm_t*),
163 _dictelm_wrapper_free);
164 if (errcode != no_error) {
165 if (free_ctn && data) {
180 * @pp_elm: the dict elem to be freed
182 * Frees a dictionnary element with all its childs.
185 gras_dictelm_free(gras_dictelm_t **pp_elm) {
187 gras_dictelm_t *p_elm = *pp_elm;
189 gras_dynar_free(p_elm->sub);
195 if (p_elm->free_ctn && p_elm->content) {
196 p_elm->free_ctn(p_elm->content);
199 memset(p_elm, 0, sizeof (*p_elm));
207 * _dictelm_wrapper_free:
209 * a wrapper to free dictelm with the right prototype to be usable within dynar
213 _dictelm_wrapper_free(void *pp_elm) {
214 DEBUG3("Free dictelm '%.*s' %p",
215 (*(gras_dictelm_t**)pp_elm)->key_len, (*(gras_dictelm_t**)pp_elm)->key,
217 gras_dictelm_free((gras_dictelm_t**)pp_elm);
220 /*####[ utility functions ]##################################################*/
225 * Returns the length of the common prefix of @str1 and @str2.
226 * Do make sure the strings are not null
230 _str_prefix_lgr(const char *key1,
236 const int old_offset = *p_offset;
242 /*CDEBUG5(dict_search, "%s: [%.*s] <=> [%.*s]", __FUNCTION__,
243 key1,key_len1,key2,key_len2);*/
245 if (o < key_len1 && o < key_len2) {
247 while (key1[o] == key2[o]) {
250 if (!(o < key_len1 && o < key_len2))
258 if (o != old_offset) {
268 } else if (o >= key_len2) {
281 * _dictelm_child_cmp:
283 * Compares two dictelm keys and return their matching (using the same
284 * convention than @_gras_dict_child_search() )
288 _dict_child_cmp(gras_dictelm_t *p_dict,
295 gras_dictelm_t *p_child = NULL;
300 gras_dynar_get(p_dict->sub, pos, &p_child);
302 /* Compute the length of the prefix
303 and if the searched key is before or after cur */
304 _str_prefix_lgr(p_child->key, p_child->key_len,
309 if (m) /* found, get out */
312 if (o < p_child->key_len && (o >= key_len || key[o] < p_child->key[o])) {
318 CDEBUG6(dict_search, "Cmp '%.*s' and '%.*s' (offset=%d) => %d",
319 p_child->key_len - *p_offset, p_child->key + *p_offset,
320 key_len - *p_offset, key + *p_offset,
330 * _gras_dict_child_search:
332 * Search where would be inserted @key between the childs of @p_elm.
334 * Returns position of the child having a common prefix with this key
335 * If *match==0, no child have a common prefix
336 * *pos is where to add the key
337 * If *match==1, A child (located at *pos) have exactly this key
338 * If *match==2, A child (located at *pos) constitutes a prefix of the key
339 * the recursion have to go on that guy
340 * *prefix = the size of the key eaten at this level
341 * If *match==3 The key is a prefix of the child at *pos
342 * If *match==4, A child (loc. at *pos) share a common prefix with this key
343 * *prefix = size of the prefix.
344 * If searching, that's a mismatch.
345 * If inserting, you have to break the child and create an
346 * internal node having {child, key} as childs
347 * offset is used in input and output. In input, that's the length of the key
348 * handled by previous levels of recursion. In output, that the one counting
353 _gras_dictelm_child_search(gras_dictelm_t *p_elm,
366 CDEBUG5(dict_search, "search child [%.*s] under [%.*s] (len=%d)",
368 p_elm?p_elm->key_len:6, p_elm?p_elm->key:"(head)",
369 (p_elm&&p_elm->sub)?gras_dynar_length(p_elm->sub):0);
372 len = gras_dynar_length(p_elm->sub);
374 for (p = 0; p < len; p++) {
377 _dict_child_cmp(p_elm, p, key, key_len, &o, &m, &cmp);
389 CDEBUG5(dict_search, "search [%.*s] in [%.*s] => %s",
391 p_elm?p_elm->key_len:6, p_elm?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 * _gras_dictelm_change_value:
404 * Change the value of the dictelm, making sure to free the old one, if any.
408 _gras_dictelm_change_value(gras_dictelm_t *p_elm,
410 void_f_pvoid_t *free_ctn) {
412 if (p_elm->content && p_elm->free_ctn) {
413 p_elm->free_ctn(p_elm->content);
416 p_elm->free_ctn = free_ctn;
417 p_elm->content = data;
421 * _gras_dictelm_set_rec:
423 * @head: the head of the dict
424 * @key: the key to set the new data
425 * @offset: offset on key.
426 * @data: the data to add in the dict
427 * @Returns: a gras_error
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 gras_dict_set which locks the struct and
433 * strdup the key before action.
436 _gras_dictelm_set_rec(gras_dictelm_t *p_head,
441 void_f_pvoid_t *free_ctn) {
442 gras_error_t errcode = no_error;
445 const int old_offset = offset;
447 CDEBUG6(dict_add, "--> Insert '%.*s' after '%.*s' (offset=%d) in tree %p",
449 ((p_head && p_head->key) ? p_head->key_len : 6),
450 ((p_head && p_head->key) ? p_head->key : "(head)"),
453 /*** The trivial cases first ***/
455 /* there is no key (we did enough recursion), change the value of head */
456 if (offset >= key_len) {
458 CDEBUG0(dict_add, "--> Change the value of head");
460 _gras_dictelm_change_value(p_head, data, free_ctn);
461 free(key); /* Keep the key used in the tree */
466 /*** Search where to add this child, and how ***/
467 _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
469 CDEBUG3(dict_add, "child_search => pos=%d, offset=%d, match=%d",
474 case 0: /* no child have a common prefix */
476 gras_dictelm_t *p_child = NULL;
478 TRY(_gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_child));
479 CDEBUG1(dict_add, "-> Add a child %p", p_child);
480 TRY(gras_dynar_insert_at(p_head->sub, pos, &p_child));
485 case 1: /* A child have exactly this key => change its value*/
487 gras_dictelm_t *p_child = NULL;
489 gras_dynar_get(p_head->sub, pos, &p_child);
490 CDEBUG1(dict_add, "-> Change the value of the child %p", p_child);
491 _gras_dictelm_change_value(p_child, data, free_ctn);
498 case 2: /* A child constitutes a prefix of the key => recurse */
500 gras_dictelm_t *p_child = NULL;
502 gras_dynar_get(p_head->sub, pos, &p_child);
503 CDEBUG2(dict_add,"-> Recurse on %p (offset=%d)", p_child, offset);
505 return _gras_dictelm_set_rec(p_child, key, key_len,
506 offset, data, free_ctn);
509 case 3: /* The key is a prefix of the child => child becomes child of p_new */
511 gras_dictelm_t *p_new = NULL;
512 gras_dictelm_t *p_child = NULL;
514 gras_dynar_get(p_head->sub, pos, &p_child);
515 TRY(_gras_dictelm_alloc(key, key_len, old_offset, data, free_ctn, &p_new));
517 CDEBUG2(dict_add, "-> The child %p become child of new dict (%p)",
520 TRY(gras_dynar_push(p_new->sub, &p_child));
521 p_child->offset = offset;
522 TRY(gras_dynar_set(p_head->sub, pos, &p_new));
527 case 4: /* A child share a common prefix with this key => Common ancestor */
529 gras_dictelm_t *p_new = NULL;
530 gras_dictelm_t *p_child = NULL;
531 gras_dictelm_t *p_anc = NULL;
532 char *anc_key = NULL;
533 int anc_key_len = offset;
535 TRY(_gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_new));
536 gras_dynar_get(p_head->sub, pos, &p_child);
538 anc_key = memdup(key, anc_key_len);
540 TRY(_gras_dictelm_alloc(anc_key, anc_key_len, old_offset,
541 NULL, NULL, &p_anc));
543 CDEBUG3(dict_add, "-> Make a common ancestor %p (%.*s)",
544 p_anc, anc_key_len, anc_key);
546 if (key[offset] < p_child->key[offset]) {
547 TRY(gras_dynar_push(p_anc->sub, &p_new));
548 TRY(gras_dynar_push(p_anc->sub, &p_child));
550 TRY(gras_dynar_push(p_anc->sub, &p_child));
551 TRY(gras_dynar_push(p_anc->sub, &p_new));
554 p_child->offset = offset;
556 TRY(gras_dynar_set(p_head->sub, pos, &p_anc));
568 * gras_dictelm_set_ext:
570 * @head: the head of the dict
571 * @key: the key to set the new data
572 * @data: the data to add in the dict
573 * @Returns: a gras_error
575 * set the @data in the structure under the @key, which can be any kind
576 * of data, as long as its length is provided in @key_len.
579 gras_dictelm_set_ext(gras_dictelm_t **pp_head,
583 void_f_pvoid_t *free_ctn) {
584 gras_error_t errcode = no_error;
585 gras_dictelm_t *p_head = *pp_head;
588 key = memdup(_key, key_len);
592 /* there is no head, create it */
594 gras_dictelm_t *p_child = NULL;
596 CDEBUG0(dict_add, "Create an head");
598 /* The head is priviledged by being the only one with a NULL key */
599 TRY(_gras_dictelm_alloc(NULL, 0, 0, NULL, NULL, &p_head));
601 TRY(_gras_dictelm_alloc(key, key_len, 0, data, free_ctn, &p_child));
602 TRY(gras_dynar_insert_at(p_head->sub, 0, &p_child));
609 return _gras_dictelm_set_rec(p_head, key, key_len, 0, data, free_ctn);
615 * @head: the head of the dict
616 * @key: the key to set the new data
617 * @data: the data to add in the dict
618 * @Returns: a gras_error
620 * set the @data in the structure under the @key, which is a
621 * null terminated string.
624 gras_dictelm_set(gras_dictelm_t **pp_head,
627 void_f_pvoid_t *free_ctn) {
629 return gras_dictelm_set_ext(pp_head, _key, 1+strlen(_key), data, free_ctn);
633 * _gras_dict_get_rec:
635 * @head: the head of the dict
636 * @key: the key to find data
637 * @offset: offset on the key
638 * @data: the data that we are looking for
639 * @Returns: gras_error
641 * Search the given @key. mismatch_error when not found.
645 _gras_dictelm_get_rec(gras_dictelm_t *p_head,
652 CDEBUG3(dict_search, "Search %.*s in %p", key_len, key, p_head);
654 /*** The trivial case first ***/
656 /* we did enough recursion, we're done */
657 if (offset >= key_len) {
658 *data = p_head->content;
667 *data = NULL; // Make it ready to answer 'not found' in one operation
669 /*** Search where is the good child, and how good it is ***/
670 _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
674 case 0: /* no child have a common prefix */
675 return mismatch_error;
677 case 1: /* A child have exactly this key => Got it */
679 gras_dictelm_t *p_child = NULL;
681 gras_dynar_get(p_head->sub, pos, &p_child);
682 *data = p_child->content;
687 case 2: /* A child constitutes a prefix of the key => recurse */
689 gras_dictelm_t *p_child = NULL;
691 gras_dynar_get(p_head->sub, pos, &p_child);
693 return _gras_dictelm_get_rec(p_child, key, key_len, offset, data);
696 case 3: /* The key is a prefix of the child => not found */
697 return mismatch_error;
699 case 4: /* A child share a common prefix with this key => not found */
700 return mismatch_error;
709 * gras_dictelm_get_ext:
711 * @head: the head of the dict
712 * @key: the key to find data
713 * @data: the data that we are looking for
714 * @Returns: gras_error
716 * Search the given @key. mismatch_error when not found.
719 gras_dictelm_get_ext(gras_dictelm_t *p_head,
722 /* OUT */void **data) {
723 /* there is no head, go to hell */
725 return mismatch_error;
728 return _gras_dictelm_get_rec(p_head, key, key_len, 0, data);
734 * @head: the head of the dict
735 * @key: the key to find data
736 * @data: the data that we are looking for
737 * @Returns: gras_error
739 * Search the given @key. mismatch_error when not found.
742 gras_dictelm_get(gras_dictelm_t *p_head,
744 /* OUT */void **data) {
746 return gras_dictelm_get_ext(p_head, key, 1+strlen(key), data);
749 /*----[ _gras_dict_collapse ]------------------------------------------------*/
752 _collapse_if_need(gras_dictelm_t *p_head,
755 gras_dictelm_t *p_child = NULL;
757 CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, p_head); fflush(stdout);
760 /* Remove the child if |it's key| == 0 (meaning it's dead) */
761 gras_dynar_get(p_head->sub, pos, &p_child);
763 if (offset >= p_child->key_len) {
765 gras_assert0(gras_dynar_length(p_child->sub) == 0,
766 "Found a dead child with grand childs. Internal error");
768 CDEBUG1(dict_collapse, "Remove dead child %p.... ", p_child);
769 gras_dynar_remove_at(p_head->sub, pos, &p_child);
774 CDEBUG0(dict_collapse, "Do not collapse the head, you stupid programm");
778 if (p_head->content || p_head->free_ctn ||
779 gras_dynar_length(p_head->sub) != 1) {
780 CDEBUG0(dict_collapse, "Cannot collapse");
781 return; /* cannot collapse */
784 gras_dynar_get(p_head->sub, 0, &p_child);
786 /* Get the child's key as new key */
787 CDEBUG2(dict_collapse,
788 "Do collapse with only child %.*s", p_child->key_len, p_child->key);
790 p_head->content = p_child->content;
791 p_head->free_ctn = p_child->free_ctn;
793 p_head->key = p_child->key;
794 p_head->key_len = p_child->key_len;
796 gras_dynar_free_container(p_head->sub) ;
798 p_head->sub = p_child->sub;
803 * _gras_dict_remove_rec:
805 * @head: the head of the dict
806 * @key: the key of the data to be removed
807 * @offset: offset on the key
808 * @Returns: gras_error_t
810 * Remove the entry associated with the given @key
813 _gras_dictelm_remove_rec(gras_dictelm_t *p_head,
817 gras_error_t errcode = no_error;
819 /* there is no key to search, we did enough recursion => kill current */
820 if (offset >= key_len) {
821 int killme = 0; /* do I need to suicide me ? */
823 if (p_head->content && p_head->free_ctn) {
824 p_head->free_ctn(p_head->content);
827 killme = !gras_dynar_length(p_head->sub);
828 p_head->content = NULL;
829 p_head->free_ctn = NULL;
830 _collapse_if_need(p_head, -1, offset);
833 DEBUG0("kill this node");
834 p_head->key_len = 0; /* killme. Cleanup done one step higher in recursion */
842 int old_offset = offset;
844 /*** Search where is the good child, and how good it is ***/
845 _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
849 case 1: /* A child have exactly this key => recurse */
850 case 2: /* A child constitutes a prefix of the key => recurse */
853 gras_dictelm_t *p_child = NULL;
855 gras_dynar_get(p_head->sub, pos, &p_child);
856 /*DEBUG5("Recurse on child %d of %p to remove %.*s (prefix=%d)",
857 pos, p_child, key+offset, key_len-offset,offset);*/
858 TRY(_gras_dictelm_remove_rec(p_child, key, key_len, offset));
860 _collapse_if_need(p_head, pos, old_offset);
865 case 0: /* no child have a common prefix */
866 case 3: /* The key is a prefix of the child => not found */
867 case 4: /* A child share a common prefix with this key => not found */
869 return mismatch_error;
880 * gras_dictelm_remove_ext:
882 * @head: the head of the dict
883 * @key: the key of the data to be removed
884 * @Returns: gras_error_t
886 * Remove the entry associated with the given @key
889 gras_dictelm_remove_ext(gras_dictelm_t *p_head,
892 /* there is no head, go to hell */
894 RAISE0(mismatch_error, "there is no head, go to hell");
897 return _gras_dictelm_remove_rec(p_head, key, key_len, 0);
901 * gras_dictelm_remove:
903 * @head: the head of the dict
904 * @key: the key of the data to be removed
905 * @Returns: gras_error_t
907 * Remove the entry associated with the given @key
910 gras_dictelm_remove(gras_dictelm_t *p_head,
912 return _gras_dictelm_remove_rec(p_head, key, 1+strlen(key),0);
915 /*----[ _gras_dict_dump_rec ]------------------------------------------------*/
916 /* private function to do the job of gras_dict_dump recursively */
917 /*---------------------------------------------------------------------------*/
920 _gras_dictelm_dump_rec(gras_dictelm_t *p_head,
922 void_f_pvoid_t *output) {
923 gras_error_t errcode = no_error;
924 gras_dictelm_t *p_child = NULL;
932 printf("[%p] ", p_head);
935 key_len = p_head->key_len;
941 for (i = 0; i < offset; i++) {
952 char *key_string = NULL;
954 key_string = malloc(key_len*2+1);
958 _gras_bytes_to_string(key, key_len, key_string);
960 printf("%.*s|(%d)", key_len-offset, key_string + offset, offset);
969 if (p_head->content) {
972 output(p_head->content);
981 printf(" \t\t\t[ %d child(s) ]\n", gras_dynar_length(p_head->sub));
983 gras_dynar_foreach(p_head->sub, i, p_child)
984 TRY(_gras_dictelm_dump_rec(p_child, p_child->offset, output));
992 * @head: the head of the dict
993 * @output: a function to dump each data in the tree
994 * @Returns: gras_error_t
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.
1001 gras_dictelm_dump(gras_dictelm_t *p_head,
1002 void_f_pvoid_t *output) {
1003 return _gras_dictelm_dump_rec(p_head, 0, output);
1007 * gras_dictelm_print_fct:
1011 * To dump multidict, this function dumps a dict
1015 gras_dictelm_print_fct(void *data) {
1016 printf("tree %p", data);