Lines Matching refs:node
64 /* prefix, common part for all children of this node */
95 static int node_add_child(struct trie *trie, struct trie_node *node, struct trie_node *node_child, uint8_t c) {
99 child = realloc(node->children, (node->children_count + 1) * sizeof(struct trie_child_entry));
103 node->children = child;
105 node->children[node->children_count].c = c;
106 node->children[node->children_count].child = node_child;
107 node->children_count++;
108 qsort(node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
114 static struct trie_node *node_lookup(const struct trie_node *node, uint8_t c) {
119 child = bsearch(&search, node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
125 static void trie_node_cleanup(struct trie_node *node) {
128 for (i = 0; i < node->children_count; i++)
129 trie_node_cleanup(node->children[i].child);
130 free(node->children);
131 free(node->values);
132 free(node);
157 static int trie_node_add_value(struct trie *trie, struct trie_node *node,
169 if (node->values_count) {
175 val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
184 val = realloc(node->values, (node->values_count + 1) * sizeof(struct trie_value_entry));
188 node->values = val;
189 node->values[node->values_count].key_off = k;
190 node->values[node->values_count].value_off = v;
191 node->values_count++;
192 qsort_r(node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
196 static int trie_insert(struct trie *trie, struct trie_node *node, const char *search,
206 for (p = 0; (c = trie->strings->buf[node->prefix_off + p]); p++) {
214 /* split node */
220 new_child->prefix_off = node->prefix_off + p+1;
221 new_child->children = node->children;
222 new_child->children_count = node->children_count;
223 new_child->values = node->values;
224 new_child->values_count = node->values_count;
227 s = strndup(trie->strings->buf + node->prefix_off, p);
235 node->prefix_off = off;
236 node->children = NULL;
237 node->children_count = 0;
238 node->values = NULL;
239 node->values_count = 0;
240 err = node_add_child(trie, node, new_child, c);
251 return trie_node_add_value(trie, node, key, value);
253 child = node_lookup(node, c);
269 err = node_add_child(trie, node, child, c);
278 node = child;
294 static void trie_store_nodes_size(struct trie_f *trie, struct trie_node *node) {
297 for (i = 0; i < node->children_count; i++)
298 trie_store_nodes_size(trie, node->children[i].child);
301 for (i = 0; i < node->children_count; i++)
303 for (i = 0; i < node->values_count; i++)
307 static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) {
310 .prefix_off = htole64(trie->strings_off + node->prefix_off),
311 .children_count = node->children_count,
312 .values_count = htole64(node->values_count),
317 if (node->children_count) {
318 children = new0(struct trie_child_entry_f, node->children_count);
324 for (i = 0; i < node->children_count; i++) {
327 child_off = trie_store_nodes(trie, node->children[i].child);
332 children[i].c = node->children[i].c;
336 /* write node */
342 if (node->children_count) {
343 fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);
344 trie->children_count += node->children_count;
349 for (i = 0; i < node->values_count; i++) {
351 .key_off = htole64(trie->strings_off + node->values[i].key_off),
352 .value_off = htole64(trie->strings_off + node->values[i].value_off),