1 /*
2 * Copyright (C) 2011 Red Hat, Inc.
3 *
4 * Author: Angus Salkeld <asalkeld@redhat.com>
5 *
6 * This file is part of libqb.
7 *
8 * libqb is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as published by
10 * the Free Software Foundation, either version 2.1 of the License, or
11 * (at your option) any later version.
12 *
13 * libqb is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with libqb. If not, see <http://www.gnu.org/licenses/>.
20 */
21 #include <os_base.h>
22 #include <assert.h>
23
24 #include <qb/qbdefs.h>
25 #include <qb/qblist.h>
26 #include <qb/qbmap.h>
27 #include "map_int.h"
28
29 struct trie_iter {
30 struct qb_map_iter i;
31 const char *prefix;
32 struct trie_node *n;
33 struct trie_node *root;
34 };
35
36 struct trie_node {
37 uint32_t idx;
38 char *segment;
39 uint32_t num_segments;
40 char *key;
41 void *value;
42 struct trie_node **children;
43 uint32_t num_children;
44 uint32_t refcount;
45 struct trie_node *parent;
46 struct qb_list_head *notifier_head;
47 };
48
49 struct trie {
50 struct qb_map map;
51
52 size_t length;
53 uint32_t num_nodes;
54 uint32_t mem_used;
55 struct trie_node *header;
56 };
57
58 static void trie_notify(struct trie_node *n, uint32_t event, const char *key,
59 void *old_value, void *value);
60 static struct trie_node *trie_new_node(struct trie *t, struct trie_node *parent);
61 static void trie_destroy_node(struct trie_node *node);
62
63 /*
64 * characters are stored in reverse to make accessing the
65 * more common case (non-control chars) more space efficient.
66 */
67 #define TRIE_CHAR2INDEX(ch) (127 - (signed char)ch)
68 #define TRIE_INDEX2CHAR(idx) (127 - (signed char)idx)
69
70
71 static int32_t
trie_node_alive(struct trie_node * node)72 trie_node_alive(struct trie_node *node)
73 {
74 if (node->value == NULL ||
75 node->refcount <= 0) {
76 return QB_FALSE;
77 }
78 return QB_TRUE;
79 }
80
81 static struct trie_node *
trie_node_next(struct trie_node * node,struct trie_node * root,int all)82 trie_node_next(struct trie_node *node, struct trie_node *root, int all)
83 {
84 struct trie_node *c = node;
85 struct trie_node *n;
86 struct trie_node *p;
87 int i;
88
89 keep_going:
90 n = NULL;
91
92 /* child/outward
93 */
94 for (i = c->num_children - 1; i >= 0; i--) {
95 if (c->children[i]) {
96 n = c->children[i];
97 break;
98 }
99 }
100 if (n) {
101 if (all || trie_node_alive(n)) {
102 return n;
103 } else {
104 c = n;
105 goto keep_going;
106 }
107 }
108 /* sibling/parent
109 */
110 if (c == root) {
111 return NULL;
112 }
113 p = c;
114 do {
115 for (i = p->idx - 1; i >= 0; i--) {
116 if (p->parent->children[i]) {
117 n = p->parent->children[i];
118 break;
119 }
120 }
121 if (n == NULL) {
122 p = p->parent;
123 }
124 } while (n == NULL && p != root);
125
126 if (n) {
127 if (all || trie_node_alive(n)) {
128 return n;
129 }
130 if (n == root) {
131 return NULL;
132 }
133 c = n;
134 goto keep_going;
135 }
136
137 return n;
138 }
139
140 static struct trie_node *
new_child_node(struct trie * t,struct trie_node * parent,char ch)141 new_child_node(struct trie *t, struct trie_node * parent, char ch)
142 {
143 struct trie_node *new_node;
144 int old_max_idx;
145 int i;
146 int idx = TRIE_CHAR2INDEX(ch);
147
148 if (idx >= parent->num_children) {
149 old_max_idx = parent->num_children;
150 parent->num_children = QB_MAX(idx + 1, 30);
151 t->mem_used += (sizeof(struct trie_node*) * (parent->num_children - old_max_idx));
152 parent->children = realloc(parent->children,
153 (parent->num_children * sizeof(struct trie_node*)));
154 if (parent->children == NULL) {
155 return NULL;
156 }
157 for (i = old_max_idx; i < parent->num_children; i++) {
158 parent->children[i] = NULL;
159 }
160 }
161 new_node = trie_new_node(t, parent);
162 if (new_node == NULL) {
163 return NULL;
164 }
165 new_node->idx = idx;
166 parent->children[idx] = new_node;
167 return new_node;
168 }
169
170
171 static struct trie_node *
trie_node_split(struct trie * t,struct trie_node * cur_node,int seg_cnt)172 trie_node_split(struct trie *t, struct trie_node *cur_node, int seg_cnt)
173 {
174 struct trie_node *split_node;
175 struct trie_node ** children = cur_node->children;
176 uint32_t num_children = cur_node->num_children;
177 struct qb_list_head *tmp;
178 int i;
179 int s;
180
181 cur_node->children = NULL;
182 cur_node->num_children = 0;
183 split_node = new_child_node(t, cur_node, cur_node->segment[seg_cnt]);
184 if (split_node == NULL) {
185 return NULL;
186 }
187 split_node->children = children;
188 split_node->num_children = num_children;
189 for (i = 0; i < split_node->num_children; i++) {
190 if (split_node->children[i]) {
191 split_node->children[i]->parent = split_node;
192 }
193 }
194 split_node->value = cur_node->value;
195 split_node->key = cur_node->key;
196 split_node->refcount = cur_node->refcount;
197 cur_node->value = NULL;
198 cur_node->key = NULL;
199 cur_node->refcount = 0;
200 /* move notifier list to split */
201 tmp = split_node->notifier_head;
202 split_node->notifier_head = cur_node->notifier_head;
203 cur_node->notifier_head = tmp;
204 qb_list_init(cur_node->notifier_head);
205
206 if (seg_cnt < cur_node->num_segments) {
207 split_node->num_segments = cur_node->num_segments - seg_cnt - 1;
208 split_node->segment = malloc(split_node->num_segments * sizeof(char));
209 if (split_node->segment == NULL) {
210 trie_destroy_node(split_node);
211 return NULL;
212 }
213 for (i = (seg_cnt + 1); i < cur_node->num_segments; i++) {
214 s = i - seg_cnt - 1;
215 split_node->segment[s] = cur_node->segment[i];
216 cur_node->segment[i] = '\0';
217 }
218 cur_node->num_segments = seg_cnt;
219 }
220 return cur_node;
221 }
222
223 static struct trie_node *
trie_insert(struct trie * t,const char * key)224 trie_insert(struct trie *t, const char *key)
225 {
226 struct trie_node *cur_node = t->header;
227 struct trie_node *new_node;
228 char *cur = (char *)key;
229 int idx = TRIE_CHAR2INDEX(key[0]);
230 int seg_cnt = 0;
231
232 do {
233 new_node = NULL;
234 if (cur_node->num_segments > 0 &&
235 seg_cnt < cur_node->num_segments) {
236 if (cur_node->segment[seg_cnt] == *cur) {
237 /* we found the char in the segment */
238 seg_cnt++;
239 } else {
240 cur_node = trie_node_split(t, cur_node, seg_cnt);
241 if (cur_node == NULL) {
242 return NULL;
243 }
244 new_node = new_child_node(t, cur_node, *cur);
245 if (new_node == NULL) {
246 return NULL;
247 }
248 }
249 } else if (idx < cur_node->num_children &&
250 cur_node->children[idx]) {
251 /* the char can be found on the next node */
252 new_node = cur_node->children[idx];
253 } else if (cur_node == t->header) {
254 /* the root node is empty so make it on the next node */
255 new_node = new_child_node(t, cur_node, *cur);
256 if (new_node == NULL) {
257 return NULL;
258 }
259 } else if (cur_node->value == NULL &&
260 qb_list_empty(cur_node->notifier_head) &&
261 cur_node->num_children == 0 &&
262 seg_cnt == cur_node->num_segments) {
263 /* we are on a leaf (with no value) so just add it as a segment */
264 cur_node->segment = realloc(cur_node->segment, cur_node->num_segments + 1);
265 cur_node->segment[cur_node->num_segments] = *cur;
266 t->mem_used += sizeof(char);
267 cur_node->num_segments++;
268 seg_cnt++;
269 } else if (seg_cnt == cur_node->num_segments) {
270 /* on the last segment need to make a new node */
271 new_node = new_child_node(t, cur_node, *cur);
272 if (new_node == NULL) {
273 return NULL;
274 }
275 } else /* need_to_split */ {
276 cur_node = trie_node_split(t, cur_node, seg_cnt);
277 if (cur_node == NULL) {
278 return NULL;
279 }
280 new_node = new_child_node(t, cur_node, *cur);
281 if (new_node == NULL) {
282 return NULL;
283 }
284 }
285 if (new_node) {
286 seg_cnt = 0;
287 cur_node = new_node;
288 }
289 cur++;
290 idx = TRIE_CHAR2INDEX(*cur);
291 } while (*cur != '\0');
292
293 if (cur_node->num_segments > 0 &&
294 seg_cnt < cur_node->num_segments) {
295 /* we need to split */
296 cur_node = trie_node_split(t, cur_node, seg_cnt);
297 if (cur_node == NULL) {
298 return NULL;
299 }
300 new_node = new_child_node(t, cur_node, *cur);
301 if (new_node == NULL) {
302 return NULL;
303 }
304 }
305
306 return cur_node;
307 }
308
309 static struct trie_node *
trie_lookup(struct trie * t,const char * key,int exact_match)310 trie_lookup(struct trie *t, const char *key, int exact_match)
311 {
312 struct trie_node *cur_node = t->header;
313 char *cur = (char *)key;
314 int idx = TRIE_CHAR2INDEX(key[0]);
315 int seg_cnt = 0;
316
317 do {
318 if (cur_node->num_segments > 0 &&
319 seg_cnt < cur_node->num_segments) {
320 if (cur_node->segment[seg_cnt] == *cur) {
321 /* we found the char in the segment */
322 seg_cnt++;
323 } else {
324 return NULL;
325 }
326 } else if (idx < cur_node->num_children &&
327 cur_node->children[idx]) {
328 /* the char can be found on the next node */
329 cur_node = cur_node->children[idx];
330 seg_cnt = 0;
331 } else {
332 return NULL;
333 }
334 cur++;
335 idx = TRIE_CHAR2INDEX(*cur);
336 } while (*cur != '\0');
337
338 if (exact_match &&
339 cur_node->num_segments > 0 &&
340 seg_cnt < cur_node->num_segments) {
341 return NULL;
342 }
343
344 return cur_node;
345 }
346
347 static void
trie_node_release(struct trie * t,struct trie_node * node)348 trie_node_release(struct trie *t, struct trie_node *node)
349 {
350 int i;
351 int empty = QB_FALSE;
352
353 if (node->key == NULL &&
354 node->parent != NULL &&
355 qb_list_empty(node->notifier_head)) {
356 struct trie_node *p = node->parent;
357
358 if (node->num_children == 0) {
359 empty = QB_TRUE;
360 } else {
361 empty = QB_TRUE;
362 for (i = node->num_children - 1; i >= 0; i--) {
363 if (node->children[i]) {
364 empty = QB_FALSE;
365 break;
366 }
367 }
368 }
369 if (!empty) {
370 return;
371 }
372
373 /*
374 * unlink the node from the parent
375 */
376 p->children[node->idx] = NULL;
377 trie_destroy_node(node);
378 t->num_nodes--;
379 t->mem_used -= sizeof(struct trie_node);
380
381 trie_node_release(t, p);
382 }
383 }
384
385 static void
trie_node_destroy(struct trie * t,struct trie_node * n)386 trie_node_destroy(struct trie *t, struct trie_node *n)
387 {
388 if (n->value == NULL) {
389 return;
390 }
391 trie_notify(n, QB_MAP_NOTIFY_DELETED, n->key, n->value, NULL);
392
393 n->key = NULL;
394 n->value = NULL;
395
396 trie_node_release(t, n);
397 }
398
399 static void
trie_print_node(struct trie_node * n,struct trie_node * r,const char * suffix)400 trie_print_node(struct trie_node *n, struct trie_node *r, const char *suffix)
401 {
402 int i;
403
404 if (n->parent) {
405 trie_print_node(n->parent, n, suffix);
406 }
407 if (n->idx == 0) {
408 return;
409 }
410
411 printf("[%c", (char) TRIE_INDEX2CHAR(n->idx));
412 for (i = 0; i < n->num_segments; i++) {
413 printf("%c", n->segment[i]);
414 }
415 if (n == r) {
416 #ifndef S_SPLINT_S
417 printf("] (%" PRIu32 ") %s\n", n->refcount, suffix);
418 #endif /* S_SPLINT_S */
419 } else {
420 printf("] ");
421 }
422 }
423
424 static void
trie_node_ref(struct trie * t,struct trie_node * node)425 trie_node_ref(struct trie *t, struct trie_node *node)
426 {
427 if (t->header == node) {
428 return;
429 }
430 node->refcount++;
431 }
432
433 static void
trie_node_deref(struct trie * t,struct trie_node * node)434 trie_node_deref(struct trie *t, struct trie_node *node)
435 {
436 if (!trie_node_alive(node)) {
437 return;
438 }
439 node->refcount--;
440 if (node->refcount > 0) {
441 return;
442 }
443 trie_node_destroy(t, node);
444 }
445
446 static void
trie_destroy(struct qb_map * map)447 trie_destroy(struct qb_map *map)
448 {
449 struct trie *t = (struct trie *)map;
450
451 struct trie_node *cur_node = t->header;
452 struct trie_node *fwd_node;
453
454 do {
455 fwd_node = trie_node_next(cur_node, t->header, QB_FALSE);
456 trie_node_destroy(t, cur_node);
457 } while ((cur_node = fwd_node));
458
459 free(t);
460 }
461
462 static void
trie_destroy_node(struct trie_node * node)463 trie_destroy_node(struct trie_node *node)
464 {
465 free(node->segment);
466 free(node->children);
467 free(node->notifier_head);
468 free(node);
469 }
470
471 static struct trie_node *
trie_new_node(struct trie * t,struct trie_node * parent)472 trie_new_node(struct trie *t, struct trie_node *parent)
473 {
474 struct trie_node *new_node = calloc(1, sizeof(struct trie_node));
475
476 if (new_node == NULL) {
477 return NULL;
478 }
479
480 new_node->notifier_head = calloc(1, sizeof(struct qb_list_head));
481 if (new_node->notifier_head == NULL) {
482 free(new_node);
483 return NULL;
484 }
485
486 new_node->parent = parent;
487 new_node->num_children = 0;
488 new_node->children = NULL;
489 new_node->num_segments = 0;
490 new_node->segment = NULL;
491 t->num_nodes++;
492 t->mem_used += sizeof(struct trie_node);
493 qb_list_init(new_node->notifier_head);
494 return new_node;
495 }
496
497 void
qb_trie_dump(qb_map_t * m)498 qb_trie_dump(qb_map_t* m)
499 {
500 struct trie * t = (struct trie*)m;
501 struct trie_node *n;
502
503 if (t == NULL) {
504 return;
505 }
506
507 #ifndef S_SPLINT_S
508 printf("nodes: %" PRIu32 ", bytes: %" PRIu32 "\n", t->num_nodes, t->mem_used);
509 #endif /* S_SPLINT_S */
510
511 n = t->header;
512 do {
513 if (n->num_children == 0) {
514 trie_print_node(n, n, " ");
515 }
516 n = trie_node_next(n, t->header, QB_FALSE);
517 } while (n);
518 }
519
520 static void
trie_put(struct qb_map * map,const char * key,const void * value)521 trie_put(struct qb_map *map, const char *key, const void *value)
522 {
523 struct trie *t = (struct trie *)map;
524 struct trie_node *n = trie_insert(t, key);
525 if (n) {
526 const char *old_value = n->value;
527 const char *old_key = n->key;
528
529 n->key = (char *)key;
530 n->value = (void *)value;
531
532 if (old_value == NULL) {
533 trie_node_ref(t, n);
534 t->length++;
535 trie_notify(n, QB_MAP_NOTIFY_INSERTED,
536 n->key, NULL, n->value);
537 } else {
538 trie_notify(n, QB_MAP_NOTIFY_REPLACED,
539 (char *)old_key, (void *)old_value,
540 (void *)value);
541 }
542 }
543 }
544
545 static int32_t
trie_rm(struct qb_map * map,const char * key)546 trie_rm(struct qb_map *map, const char *key)
547 {
548 struct trie *t = (struct trie *)map;
549 struct trie_node *n = trie_lookup(t, key, QB_TRUE);
550 if (n) {
551 trie_node_deref(t, n);
552 t->length--;
553 return QB_TRUE;
554 } else {
555 return QB_FALSE;
556 }
557 }
558
559 static void *
trie_get(struct qb_map * map,const char * key)560 trie_get(struct qb_map *map, const char *key)
561 {
562 struct trie *t = (struct trie *)map;
563 struct trie_node *n = trie_lookup(t, key, QB_TRUE);
564 if (n) {
565 return n->value;
566 }
567
568 return NULL;
569 }
570
571 static void
trie_notify_deref(struct qb_map_notifier * f)572 trie_notify_deref(struct qb_map_notifier *f)
573 {
574 f->refcount--;
575 if (f->refcount == 0) {
576 qb_list_del(&f->list);
577 free(f);
578 }
579 }
580
581 static void
trie_notify_ref(struct qb_map_notifier * f)582 trie_notify_ref(struct qb_map_notifier *f)
583 {
584 f->refcount++;
585 }
586
587 static void
trie_notify(struct trie_node * n,uint32_t event,const char * key,void * old_value,void * value)588 trie_notify(struct trie_node *n,
589 uint32_t event, const char *key, void *old_value, void *value)
590 {
591 struct trie_node *c = n;
592 struct qb_list_head *list;
593 struct qb_list_head *next;
594 struct qb_list_head *head;
595 struct qb_map_notifier *tn;
596
597 do {
598 head = c->notifier_head;
599 qb_list_for_each_safe(list, next, head) {
600 tn = qb_list_entry(list, struct qb_map_notifier, list);
601 trie_notify_ref(tn);
602
603 if ((tn->events & event) &&
604 ((tn->events & QB_MAP_NOTIFY_RECURSIVE) ||
605 (n == c))) {
606 tn->callback(event, (char *)key, old_value,
607 value, tn->user_data);
608 }
609 if (((event & QB_MAP_NOTIFY_DELETED) ||
610 (event & QB_MAP_NOTIFY_REPLACED)) &&
611 (tn->events & QB_MAP_NOTIFY_FREE)) {
612 tn->callback(QB_MAP_NOTIFY_FREE, (char *)key,
613 old_value, value, tn->user_data);
614 }
615
616 trie_notify_deref(tn);
617 }
618 c = c->parent;
619 } while (c);
620 }
621
622 static int32_t
trie_notify_add(qb_map_t * m,const char * key,qb_map_notify_fn fn,int32_t events,void * user_data)623 trie_notify_add(qb_map_t * m, const char *key,
624 qb_map_notify_fn fn, int32_t events, void *user_data)
625 {
626 struct trie *t = (struct trie *)m;
627 struct qb_map_notifier *f;
628 struct trie_node *n;
629 struct qb_list_head *list;
630 int add_to_tail = QB_FALSE;
631
632 if (key) {
633 n = trie_lookup(t, key, QB_TRUE);
634 if (n == NULL) {
635 n = trie_insert(t, key);
636 }
637 } else {
638 n = t->header;
639 }
640 if (n) {
641 qb_list_for_each(list, n->notifier_head) {
642 f = qb_list_entry(list, struct qb_map_notifier, list);
643
644 if (events & QB_MAP_NOTIFY_FREE &&
645 f->events == events) {
646 /* only one free notifier */
647 return -EEXIST;
648 }
649 if (f->events == events &&
650 f->callback == fn &&
651 f->user_data == user_data) {
652 return -EEXIST;
653 }
654 }
655
656 f = malloc(sizeof(struct qb_map_notifier));
657 if (f == NULL) {
658 return -errno;
659 }
660 f->events = events;
661 f->user_data = user_data;
662 f->callback = fn;
663 f->refcount = 1;
664 qb_list_init(&f->list);
665 if (key) {
666 if (events & QB_MAP_NOTIFY_RECURSIVE) {
667 add_to_tail = QB_TRUE;
668 }
669 } else {
670 if (events & QB_MAP_NOTIFY_FREE) {
671 add_to_tail = QB_TRUE;
672 }
673 }
674 if (add_to_tail) {
675 qb_list_add_tail(&f->list, n->notifier_head);
676 } else {
677 qb_list_add(&f->list, n->notifier_head);
678 }
679 return 0;
680 }
681 return -EINVAL;
682 }
683
684 static int32_t
trie_notify_del(qb_map_t * m,const char * key,qb_map_notify_fn fn,int32_t events,int32_t cmp_userdata,void * user_data)685 trie_notify_del(qb_map_t * m, const char *key,
686 qb_map_notify_fn fn, int32_t events,
687 int32_t cmp_userdata, void *user_data)
688 {
689 struct trie *t = (struct trie *)m;
690 struct trie_node *n;
691 struct qb_list_head *list;
692 struct qb_list_head *next;
693 int32_t found = QB_FALSE;
694
695 if (key) {
696 n = trie_lookup(t, key, QB_FALSE);
697 } else {
698 n = t->header;
699 }
700 if (n == NULL) {
701 return -ENOENT;
702 }
703 qb_list_for_each_safe(list, next, n->notifier_head) {
704 struct qb_map_notifier *f = qb_list_entry(list, struct qb_map_notifier, list);
705
706 if (f->events == events && f->callback == fn) {
707 if (cmp_userdata && (f->user_data == user_data)) {
708 trie_notify_deref(f);
709 found = QB_TRUE;
710 } else if (!cmp_userdata) {
711 trie_notify_deref(f);
712 found = QB_TRUE;
713 }
714 }
715
716 }
717 if (found) {
718 trie_node_release(t, n);
719 return 0;
720 } else {
721 return -ENOENT;
722 }
723 }
724
725 static qb_map_iter_t *
trie_iter_create(struct qb_map * map,const char * prefix)726 trie_iter_create(struct qb_map *map, const char *prefix)
727 {
728 struct trie_iter *i = malloc(sizeof(struct trie_iter));
729 struct trie *t = (struct trie *)map;
730 if (i == NULL) {
731 return NULL;
732 }
733 i->i.m = map;
734 i->prefix = prefix;
735 i->n = t->header;
736 i->root = t->header;
737 return (qb_map_iter_t *) i;
738 }
739
740 static const char *
trie_iter_next(qb_map_iter_t * i,void ** value)741 trie_iter_next(qb_map_iter_t * i, void **value)
742 {
743 struct trie_iter *si = (struct trie_iter *)i;
744 struct trie_node *p = si->n;
745 struct trie *t = (struct trie *)(i->m);
746
747 if (p == NULL) {
748 return NULL;
749 }
750
751 if (p->parent == NULL && si->prefix) {
752 si->root = trie_lookup(t, si->prefix, QB_FALSE);
753 if (si->root == NULL) {
754 si->n = NULL;
755 } else if (si->root->value == NULL) {
756 si->n = trie_node_next(si->root, si->root, QB_FALSE);
757 } else {
758 si->n = si->root;
759 }
760 } else {
761 si->n = trie_node_next(p, si->root, QB_FALSE);
762 }
763 if (si->n == NULL) {
764 trie_node_deref(t, p);
765 return NULL;
766 }
767 trie_node_ref(t, si->n);
768 trie_node_deref(t, p);
769 *value = si->n->value;
770 return si->n->key;
771 }
772
773 static void
trie_iter_free(qb_map_iter_t * i)774 trie_iter_free(qb_map_iter_t * i)
775 {
776 struct trie_iter *si = (struct trie_iter *)i;
777 struct trie *t = (struct trie *)(i->m);
778
779 if (si->n != NULL) {
780 /* if free'ing the iterator before getting to the last
781 * node make sure we de-ref the current node.
782 */
783 trie_node_deref(t, si->n);
784 }
785 free(i);
786 }
787
788 static size_t
trie_count_get(struct qb_map * map)789 trie_count_get(struct qb_map *map)
790 {
791 struct trie *list = (struct trie *)map;
792 return list->length;
793 }
794
795 qb_map_t *
qb_trie_create(void)796 qb_trie_create(void)
797 {
798 struct trie *t = malloc(sizeof(struct trie));
799 if (t == NULL) {
800 return NULL;
801 }
802
803 t->map.put = trie_put;
804 t->map.get = trie_get;
805 t->map.rm = trie_rm;
806 t->map.count_get = trie_count_get;
807 t->map.iter_create = trie_iter_create;
808 t->map.iter_next = trie_iter_next;
809 t->map.iter_free = trie_iter_free;
810 t->map.destroy = trie_destroy;
811 t->map.notify_add = trie_notify_add;
812 t->map.notify_del = trie_notify_del;
813 t->length = 0;
814 t->num_nodes = 0;
815 t->mem_used = sizeof(struct trie);
816 t->header = trie_new_node(t, NULL);
817
818 return (qb_map_t *) t;
819 }
820