1 #include "gskprefixtree.h"
2 #include <string.h>
3
4 static inline GskPrefixTree *
tree_alloc(const char * str)5 tree_alloc (const char *str)
6 {
7 GskPrefixTree *rv = g_new (GskPrefixTree, 1);
8 rv->prefix = g_strdup (str);
9 rv->next_sibling = rv->children = NULL;
10 rv->has_data = FALSE;
11 return rv;
12 }
13
14 static inline GskPrefixTree *
tree_alloc_n(const char * str,guint len)15 tree_alloc_n (const char *str, guint len)
16 {
17 GskPrefixTree *rv = g_new (GskPrefixTree, 1);
18 rv->prefix = g_strndup (str, len);
19 rv->next_sibling = rv->children = NULL;
20 rv->has_data = FALSE;
21 return rv;
22 }
23 static inline void
tree_set_prefix(GskPrefixTree * tree,const char * prefix)24 tree_set_prefix (GskPrefixTree *tree,
25 const char *prefix)
26 {
27 char *dup = g_strdup (prefix);
28 g_free (tree->prefix);
29 tree->prefix = dup;
30 }
31
gsk_prefix_tree_insert(GskPrefixTree ** tree,const char * prefix,gpointer data)32 gpointer gsk_prefix_tree_insert (GskPrefixTree **tree,
33 const char *prefix,
34 gpointer data)
35 {
36 g_return_val_if_fail (prefix[0] != 0, NULL);
37
38 /* look for a node that shares some prefix in common with us */
39 while (*tree)
40 {
41 if (prefix[0] == (*tree)->prefix[0])
42 {
43 const char *tp_at = (*tree)->prefix;
44 const char *p_at = prefix;
45 while (*p_at != 0 && *p_at == *tp_at)
46 {
47 p_at++;
48 tp_at++;
49 }
50 if (*p_at == 0 && *tp_at == 0)
51 {
52 /* *tree is an exact match */
53 gpointer rv = (*tree)->has_data ? (*tree)->data : NULL;
54 (*tree)->has_data = TRUE;
55 (*tree)->data = data;
56 return rv;
57 }
58
59 if (*tp_at == 0) /* p_at not empty */
60 {
61 tree = &((*tree)->children);
62 prefix = p_at;
63 continue;
64 }
65
66 if (*p_at == 0)
67 {
68 /* pattern is too short for tree: must restructure tree:
69
70 if tree is 'prevsib's' pointer, and *tree is the crrent node,
71 then
72
73 prevsib prevsib
74 | |
75 v v
76 *tree -> child becomes new -> *tree -> child
77 | |
78 v v
79 nextsib nextsib */
80 GskPrefixTree *new = tree_alloc_n (prefix, p_at - prefix);
81 new->next_sibling = (*tree)->next_sibling;
82 (*tree)->next_sibling = NULL;
83 new->children = (*tree);
84 tree_set_prefix (new->children, tp_at);
85 *tree = new;
86 new->has_data = TRUE;
87 new->data = data;
88 return NULL;
89 }
90
91 /* else, a mismatch. we must make a new family of trees.
92
93 prevsib prevsib
94 | |
95 v v
96 *tree becomes common -> *tree(end)
97 | | |
98 v v v
99 nextsib nextsib new */
100 {
101 GskPrefixTree *common = tree_alloc_n (prefix, p_at - prefix);
102 GskPrefixTree *cur = *tree;
103 common->next_sibling = cur->next_sibling;
104 common->children = cur;
105 *tree = common;
106 cur->next_sibling = NULL;
107 tree = &(cur->next_sibling);
108 tree_set_prefix (cur, tp_at);
109 prefix += p_at - prefix;
110
111 /* prefix not empty */
112 }
113 }
114 else
115 {
116 tree = &((*tree)->next_sibling);
117 }
118 }
119
120 /* create a new node with the remaining characters is in */
121 *tree = tree_alloc (prefix);
122 (*tree)->has_data = TRUE;
123 (*tree)->data = data;
124 return NULL;
125 }
126
127
gsk_prefix_tree_lookup(GskPrefixTree * tree,const char * str)128 gpointer gsk_prefix_tree_lookup (GskPrefixTree *tree,
129 const char *str)
130 {
131 gpointer found = NULL;
132 GskPrefixTree *at = tree;
133
134 while (*str && at)
135 {
136 for ( ; at; at = at->next_sibling)
137 if (g_str_has_prefix (str, at->prefix))
138 {
139 str += strlen (at->prefix);
140 if (at->has_data)
141 found = at->data;
142 at = at->children;
143 break;
144 }
145 }
146 return found;
147 }
148
gsk_prefix_tree_lookup_exact(GskPrefixTree * tree,const char * str)149 gpointer gsk_prefix_tree_lookup_exact (GskPrefixTree *tree,
150 const char *str)
151 {
152 gpointer found = NULL;
153 GskPrefixTree *at = tree;
154
155 while (*str && at)
156 {
157 for ( ; at; at = at->next_sibling)
158 if (g_str_has_prefix (str, at->prefix))
159 {
160 str += strlen (at->prefix);
161 if (at->has_data)
162 found = at->data;
163 at = at->children;
164 break;
165 }
166 }
167 return *str ? NULL : found;
168 }
169
gsk_prefix_tree_lookup_all(GskPrefixTree * tree,const char * str)170 GSList *gsk_prefix_tree_lookup_all (GskPrefixTree *tree,
171 const char *str)
172 {
173 GSList *rv = NULL;
174 GskPrefixTree *at = tree;
175
176 while (*str && at)
177 {
178 for ( ; at; at = at->next_sibling)
179 if (g_str_has_prefix (str, at->prefix))
180 {
181 str += strlen (at->prefix);
182 if (at->has_data)
183 rv = g_slist_prepend (rv, at->data);
184 at = at->children;
185 break;
186 }
187 }
188 return rv;
189 }
190 // good idea, but we don't need it.
191 //gpointer gsk_prefix_tree_remove (GskPrefixTree *tree,
192 // const char *prefix)
193 //{
194 // ...
195 //}
196 //
gsk_prefix_tree_foreach(GskPrefixTree * tree,GFunc func,gpointer func_data)197 void gsk_prefix_tree_foreach (GskPrefixTree *tree,
198 GFunc func,
199 gpointer func_data)
200 {
201 while (tree)
202 {
203 if (tree->has_data)
204 func (tree->data, func_data);
205 gsk_prefix_tree_foreach (tree->children, func, func_data);
206 tree = tree->next_sibling;
207 }
208 }
gsk_prefix_tree_destroy(GskPrefixTree * tree)209 void gsk_prefix_tree_destroy (GskPrefixTree *tree)
210 {
211 while (tree)
212 {
213 GskPrefixTree *next = tree->next_sibling;
214 g_free (tree->prefix);
215 gsk_prefix_tree_destroy (tree->children);
216 tree = next;
217 }
218 }
219