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_insert_rec(gras_dictelm_t *head,
58 void_f_pvoid_t *free_ctn);
59 static gras_error_t _gras_dictelm_retrieve_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 DEBUG2("Free dictelm %p (*=%p)", pp_elm, *(void**)pp_elm);
215 gras_dictelm_free((gras_dictelm_t**)pp_elm);
218 /*####[ utility functions ]##################################################*/
223 * Returns the length of the common prefix of @str1 and @str2.
224 * Do make sure the strings are not null
228 _str_prefix_lgr(const char *key1,
234 const int old_offset = *p_offset;
240 /*CDEBUG3(dict_search, "%s: [%s] <=> [%s]", __FUNCTION__, s1, s2);*/
242 if (o < key_len1 && o < key_len2) {
244 while (key1[o] == key2[o]) {
247 if (!(o < key_len1 && o < key_len2))
255 if (o != old_offset) {
265 } else if (o >= key_len2) {
278 * _dictelm_child_cmp:
280 * Compares two dictelm keys and return their matching (using the same
281 * convention than @_gras_dict_child_search() )
285 _dict_child_cmp(gras_dictelm_t *p_dict,
292 gras_dictelm_t *p_child = NULL;
297 gras_dynar_get(p_dict->sub, pos, &p_child);
299 /* Compute the length of the prefix
300 and if the searched key is before or after cur */
301 _str_prefix_lgr(p_child->key, p_child->key_len,
306 if (m) /* found, get out */
309 if (o < p_child->key_len && (o >= key_len || key[o] < p_child->key[o])) {
315 CDEBUG3(dict_search, "Cmp %s and %s => %d", p_child->key + *p_offset,
316 key + *p_offset, cmp);
325 * _gras_dict_child_search:
327 * Search where would be inserted @key between the childs of @p_elm.
329 * Returns position of the child having a common prefix with this key
330 * If *match==0, no child have a common prefix
331 * *pos is where to add the key
332 * If *match==1, A child (located at *pos) have exactly this key
333 * If *match==2, A child (located at *pos) constitutes a prefix of the key
334 * the recursion have to go on that guy
335 * *prefix = the size of the key eaten at this level
336 * If *match==3 The key is a prefix of the child at *pos
337 * If *match==4, A child (loc. at *pos) share a common prefix with this key
338 * *prefix = size of the prefix.
339 * If searching, that's a mismatch.
340 * If inserting, you have to break the child and create an
341 * internal node having {child, key} as childs
342 * offset is used in input and output. In input, that's the length of the key
343 * handled by previous levels of recursion. In output, that the one counting
348 _gras_dictelm_child_search(gras_dictelm_t *p_elm,
361 CDEBUG3(dict_search, "search child [%s] under [%s] (len=%d)",
363 p_elm?p_elm->key:"(head)",
364 (p_elm&&p_elm->sub)?gras_dynar_length(p_elm->sub):0);
367 len = gras_dynar_length(p_elm->sub);
369 for (p = 0; p < len; p++) {
372 _dict_child_cmp(p_elm, p, key, key_len, &o, &m, &cmp);
384 CDEBUG3(dict_search, "search [%s] in [%s] => %s",
386 p_elm?p_elm->key:"(head)",
387 ( m == 0 ? "no child have a common prefix" :
388 ( m == 1 ? "selected child have exactly this key" :
389 ( m == 2 ? "selected child constitutes a prefix" :
390 ( m == 3 ? "key is a prefix of selected child" :
391 (m == 4 ? "selected child share a prefix" :
392 "internal error")))))
397 * _gras_dictelm_change_value:
399 * Change the value of the dictelm, making sure to free the old one, if any.
403 _gras_dictelm_change_value(gras_dictelm_t *p_elm,
405 void_f_pvoid_t *free_ctn) {
407 if (p_elm->content && p_elm->free_ctn) {
408 p_elm->free_ctn(p_elm->content);
411 p_elm->free_ctn = free_ctn;
412 p_elm->content = data;
416 * _gras_dictelm_insert_rec:
418 * @head: the head of the dict
419 * @key: the key to insert the new data
420 * @offset: offset on key.
421 * @data: the data to add in the dict
422 * @Returns: a gras_error
424 * Insert the @data in the structure under the @key. The @key is destroyed
425 * in the process. Think to strdup it before.
427 * This is a helper function to gras_dict_insert which locks the struct and
428 * strdup the key before action.
431 _gras_dictelm_insert_rec(gras_dictelm_t *p_head,
436 void_f_pvoid_t *free_ctn) {
437 gras_error_t errcode = no_error;
440 const int old_offset = offset;
442 CDEBUG4(dict_add, "--> Insert '%s' after '%s' (offset=%d) in tree %p",
443 key, ((p_head && p_head->key) ? p_head->key : "(head)"), offset,
446 /*** The trivial cases first ***/
448 /* there is no key (we did enough recursion), change the value of head */
449 if (offset >= key_len) {
451 CDEBUG0(dict_add, "--> Change the value of head");
453 _gras_dictelm_change_value(p_head, data, free_ctn);
454 free(key); /* Keep the key used in the tree */
459 /*** Search where to add this child, and how ***/
460 _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
462 CDEBUG3(dict_add, "child_search => pos=%d, offset=%d, match=%d",
467 case 0: /* no child have a common prefix */
469 gras_dictelm_t *p_child = NULL;
471 TRY(_gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_child));
472 CDEBUG1(dict_add, "-> Add a child %p", p_child);
473 TRY(gras_dynar_insert_at(p_head->sub, pos, &p_child));
478 case 1: /* A child have exactly this key => change its value*/
480 gras_dictelm_t *p_child = NULL;
482 gras_dynar_get(p_head->sub, pos, &p_child);
483 CDEBUG1(dict_add, "-> Change the value of the child %p", p_child);
484 _gras_dictelm_change_value(p_child, data, free_ctn);
491 case 2: /* A child constitutes a prefix of the key => recurse */
493 gras_dictelm_t *p_child = NULL;
495 gras_dynar_get(p_head->sub, pos, &p_child);
496 CDEBUG2(dict_add,"-> Recurse on %p (offset=%d)", p_child, offset);
498 return _gras_dictelm_insert_rec(p_child, key, key_len,
499 offset, data, free_ctn);
502 case 3: /* The key is a prefix of the child => child becomes child of p_new */
504 gras_dictelm_t *p_new = NULL;
505 gras_dictelm_t *p_child = NULL;
507 gras_dynar_get(p_head->sub, pos, &p_child);
508 TRY(_gras_dictelm_alloc(key, key_len, old_offset, data, free_ctn, &p_new));
510 CDEBUG2(dict_add, "-> The child %p become child of new dict (%p)",
513 TRY(gras_dynar_push(p_new->sub, &p_child));
514 p_child->offset = offset;
515 TRY(gras_dynar_set(p_head->sub, pos, &p_new));
520 case 4: /* A child share a common prefix with this key => Common ancestor */
522 gras_dictelm_t *p_new = NULL;
523 gras_dictelm_t *p_child = NULL;
524 gras_dictelm_t *p_anc = NULL;
525 char *anc_key = NULL;
526 int anc_key_len = offset;
528 TRY(_gras_dictelm_alloc(key, key_len, offset, data, free_ctn, &p_new));
529 gras_dynar_get(p_head->sub, pos, &p_child);
531 anc_key = memdup(key, anc_key_len);
533 TRY(_gras_dictelm_alloc(anc_key, anc_key_len, old_offset,
534 NULL, NULL, &p_anc));
536 CDEBUG2(dict_add, "-> Make a common ancestor %p (%s)", p_anc, anc_key);
538 if (key[offset] < p_child->key[offset]) {
539 TRY(gras_dynar_push(p_anc->sub, &p_new));
540 TRY(gras_dynar_push(p_anc->sub, &p_child));
542 TRY(gras_dynar_push(p_anc->sub, &p_child));
543 TRY(gras_dynar_push(p_anc->sub, &p_new));
546 p_child->offset = offset;
548 TRY(gras_dynar_set(p_head->sub, pos, &p_anc));
560 * gras_dictelm_insert_ext:
562 * @head: the head of the dict
563 * @key: the key to insert the new data
564 * @data: the data to add in the dict
565 * @Returns: a gras_error
567 * Insert the @data in the structure under the @key, which can be any kind
568 * of data, as long as its length is provided in @key_len.
571 gras_dictelm_insert_ext(gras_dictelm_t **pp_head,
575 void_f_pvoid_t *free_ctn) {
576 gras_error_t errcode = no_error;
577 gras_dictelm_t *p_head = *pp_head;
580 key = memdup(_key, key_len);
584 /* there is no head, create it */
586 gras_dictelm_t *p_child = NULL;
588 CDEBUG0(dict_add, "Create an head");
590 /* The head is priviledged by being the only one with a NULL key */
591 TRY(_gras_dictelm_alloc(NULL, 0, 0, NULL, NULL, &p_head));
593 TRY(_gras_dictelm_alloc(key, key_len, 0, data, free_ctn, &p_child));
594 TRY(gras_dynar_insert_at(p_head->sub, 0, &p_child));
601 return _gras_dictelm_insert_rec(p_head, key, key_len, 0, data, free_ctn);
605 * gras_dictelm_insert:
607 * @head: the head of the dict
608 * @key: the key to insert the new data
609 * @data: the data to add in the dict
610 * @Returns: a gras_error
612 * Insert the @data in the structure under the @key, which is a
613 * null terminated string.
616 gras_dictelm_insert(gras_dictelm_t **pp_head,
619 void_f_pvoid_t *free_ctn) {
621 return gras_dictelm_insert_ext(pp_head, _key, 1+strlen(_key), data, free_ctn);
625 * _gras_dict_retrieve_rec:
627 * @head: the head of the dict
628 * @key: the key to find data
629 * @offset: offset on the key
630 * @data: the data that we are looking for
631 * @Returns: gras_error
633 * Search the given @key. mismatch_error when not found.
637 _gras_dictelm_retrieve_rec(gras_dictelm_t *p_head,
641 /* OUT */void **data) {
643 gras_error_t errcode = no_error;
645 CDEBUG2(dict_search, "Search %s in %p", key, p_head);
647 /*** The trivial case first ***/
649 /* we did enough recursion, we're done */
650 if (offset >= key_len) {
651 *data = p_head->content;
660 *data = NULL; // Make it ready to answer 'not found' in one operation
662 /*** Search where is the good child, and how good it is ***/
663 _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
667 case 0: /* no child have a common prefix */
668 return mismatch_error;
670 case 1: /* A child have exactly this key => Got it */
672 gras_dictelm_t *p_child = NULL;
674 gras_dynar_get(p_head->sub, pos, &p_child);
675 *data = p_child->content;
680 case 2: /* A child constitutes a prefix of the key => recurse */
682 gras_dictelm_t *p_child = NULL;
684 gras_dynar_get(p_head->sub, pos, &p_child);
686 return _gras_dictelm_retrieve_rec(p_child, key, key_len, offset, data);
689 case 3: /* The key is a prefix of the child => not found */
690 return mismatch_error;
692 case 4: /* A child share a common prefix with this key => not found */
693 return mismatch_error;
702 * gras_dictelm_retrieve_ext:
704 * @head: the head of the dict
705 * @key: the key to find data
706 * @data: the data that we are looking for
707 * @Returns: gras_error
709 * Search the given @key. mismatch_error when not found.
712 gras_dictelm_retrieve_ext(gras_dictelm_t *p_head,
715 /* OUT */void **data) {
716 /* there is no head, go to hell */
718 return mismatch_error;
721 return _gras_dictelm_retrieve_rec(p_head, key, key_len, 0, data);
725 * gras_dictelm_retrieve:
727 * @head: the head of the dict
728 * @key: the key to find data
729 * @data: the data that we are looking for
730 * @Returns: gras_error
732 * Search the given @key. mismatch_error when not found.
735 gras_dictelm_retrieve(gras_dictelm_t *p_head,
737 /* OUT */void **data) {
739 return gras_dictelm_retrieve_ext(p_head, key, 1+strlen(key), data);
742 /*----[ _gras_dict_collapse ]------------------------------------------------*/
745 _collapse_if_need(gras_dictelm_t *p_head,
748 gras_dictelm_t *p_child = NULL;
750 CDEBUG2(dict_collapse, "Collapse %d of %p... ", pos, p_head); fflush(stdout);
753 /* Remove the child if |it's key| == 0 (meaning it's dead) */
754 gras_dynar_get(p_head->sub, pos, &p_child);
756 if (offset >= p_child->key_len) {
758 gras_assert0(gras_dynar_length(p_child->sub) == 0,
759 "Found a dead child with grand childs. Internal error");
761 CDEBUG1(dict_collapse, "Remove dead child %p.... ", p_child);
762 gras_dynar_remove_at(p_head->sub, pos, &p_child);
767 CDEBUG0(dict_collapse, "Do not collapse the head, you stupid programm");
771 if (p_head->content || p_head->free_ctn ||
772 gras_dynar_length(p_head->sub) != 1) {
773 CDEBUG0(dict_collapse, "Cannot collapse");
774 return; /* cannot collapse */
777 gras_dynar_get(p_head->sub, 0, &p_child);
779 /* Get the child's key as new key */
780 CDEBUG1(dict_collapse, "Do collapse with only child %s", p_child->key);
782 p_head->content = p_child->content;
783 p_head->free_ctn = p_child->free_ctn;
785 p_head->key = p_child->key;
786 p_head->key_len = p_child->key_len;
788 gras_dynar_free_container(p_head->sub) ;
790 p_head->sub = p_child->sub;
795 * _gras_dict_remove_rec:
797 * @head: the head of the dict
798 * @key: the key of the data to be removed
799 * @offset: offset on the key
800 * @Returns: gras_error_t
802 * Remove the entry associated with the given @key
805 _gras_dictelm_remove_rec(gras_dictelm_t *p_head,
809 gras_error_t errcode = no_error;
811 /* there is no key to search, we did enough recursion => kill current */
812 if (offset >= key_len) {
813 int killme = 0; /* do I need to suicide me ? */
815 if (p_head->content && p_head->free_ctn) {
816 p_head->free_ctn(p_head->content);
819 killme = !gras_dynar_length(p_head->sub);
820 p_head->content = NULL;
821 p_head->free_ctn = NULL;
822 _collapse_if_need(p_head, -1, offset);
825 DEBUG0("kill this node");
826 p_head->key_len = 0; /* killme. Cleanup done one step higher in recursion */
834 int old_offset = offset;
836 /*** Search where is the good child, and how good it is ***/
837 _gras_dictelm_child_search(p_head, key, key_len, &pos, &offset, &match);
841 case 1: /* A child have exactly this key => recurse */
842 case 2: /* A child constitutes a prefix of the key => recurse */
845 gras_dictelm_t *p_child = NULL;
847 gras_dynar_get(p_head->sub, pos, &p_child);
848 /*DEBUG4("Recurse on child %d of %p to remove %s (prefix=%d)",
849 pos, p_child, key+offset, offset);*/
850 TRY(_gras_dictelm_remove_rec(p_child, key, key_len, offset));
852 _collapse_if_need(p_head, pos, old_offset);
857 case 0: /* no child have a common prefix */
858 case 3: /* The key is a prefix of the child => not found */
859 case 4: /* A child share a common prefix with this key => not found */
861 return mismatch_error;
872 * gras_dictelm_remove_ext:
874 * @head: the head of the dict
875 * @key: the key of the data to be removed
876 * @Returns: gras_error_t
878 * Remove the entry associated with the given @key
881 gras_dictelm_remove_ext(gras_dictelm_t *p_head,
884 /* there is no head, go to hell */
886 RAISE0(mismatch_error, "there is no head, go to hell");
889 return _gras_dictelm_remove_rec(p_head, key, key_len, 0);
893 * gras_dictelm_remove:
895 * @head: the head of the dict
896 * @key: the key of the data to be removed
897 * @Returns: gras_error_t
899 * Remove the entry associated with the given @key
902 gras_dictelm_remove(gras_dictelm_t *p_head,
904 return _gras_dictelm_remove_rec(p_head, key, 1+strlen(key),0);
907 /*----[ _gras_dict_dump_rec ]------------------------------------------------*/
908 /* private function to do the job of gras_dict_dump recursively */
909 /*---------------------------------------------------------------------------*/
912 _gras_dictelm_dump_rec(gras_dictelm_t *p_head,
914 void_f_pvoid_t *output) {
915 gras_error_t errcode = no_error;
916 gras_dictelm_t *p_child = NULL;
924 printf("[%p] ", p_head);
927 key_len = p_head->key_len;
933 for (i = 0; i < offset; i++) {
944 char *key_string = NULL;
946 key_string = malloc(key_len*2+1);
950 _gras_bytes_to_string(key, key_len, key_string);
952 printf("%s|(%d)", key_string + offset, offset);
961 if (p_head->content) {
964 output(p_head->content);
973 printf(" \t\t\t[ %d child(s) ]\n", gras_dynar_length(p_head->sub));
975 gras_dynar_foreach(p_head->sub, i, p_child)
976 TRY(_gras_dictelm_dump_rec(p_child, p_child->offset, output));
984 * @head: the head of the dict
985 * @output: a function to dump each data in the tree
986 * @Returns: gras_error_t
988 * Ouputs the content of the structure. (for debuging purpose). @ouput is a
989 * function to output the data. If NULL, data won't be displayed.
993 gras_dictelm_dump(gras_dictelm_t *p_head,
994 void_f_pvoid_t *output) {
995 return _gras_dictelm_dump_rec(p_head, 0, output);
999 * gras_dictelm_print_fct:
1003 * To dump multidict, this function dumps a dict
1007 gras_dictelm_print_fct(void *data) {
1008 printf("tree %p", data);