trie.c (2187B)
1 #define HEADER_IMPL 2 #include "trie.h" 3 4 #include <assert.h> 5 #include <stdio.h> 6 7 static inline void 8 trie_display(struct trie_node const *trie, size_t indent) 9 { 10 for (size_t i = 0; i < indent; i++) 11 printf(" "); 12 13 printf("{ %p, prefix: \"%.*s\", }\n", 14 trie, (int) (trie->prefix.end - trie->prefix.begin), trie->prefix.begin); 15 16 struct trie_node *it; 17 LIST_ENTRY_ITER(&trie->children, it, list_node) { 18 trie_display(it, indent + 1); 19 } 20 } 21 22 int 23 main(void) 24 { 25 char buf[8192]; 26 struct arena_allocator arena = { .ptr = buf, .cap = sizeof buf, .len = 0, }; 27 28 printf("trie_init()\n"); 29 struct trie_node *root = trie_init(&arena); 30 assert(root); 31 trie_display(root, 0); 32 33 printf("trie_insert(\"foo\")\n"); 34 struct trie_node *foo = trie_insert(&arena, root, "foo", 3); 35 trie_display(root, 0); 36 37 printf("trie_insert(\"for\")\n"); 38 struct trie_node *_for = trie_insert(&arena, root, "for", 3); 39 trie_display(root, 0); 40 41 printf("trie_insert(\"foobar\")\n"); 42 struct trie_node *foobar = trie_insert(&arena, root, "foobar", 6); 43 trie_display(root, 0); 44 45 printf("trie_insert(\"bar\")\n"); 46 struct trie_node *bar = trie_insert(&arena, root, "bar", 3); 47 trie_display(root, 0); 48 49 printf("trie_insert(\"forsen\")\n"); 50 struct trie_node *forsen = trie_insert(&arena, root, "forsen", 6); 51 trie_display(root, 0); 52 53 printf("trie_insert(\"forseen\")\n"); 54 struct trie_node *forseen = trie_insert(&arena, root, "forseen", 7); 55 trie_display(root, 0); 56 57 printf("trie_insert(\"forsee\")\n"); 58 struct trie_node *forsee = trie_insert(&arena, root, "forsee", 6); 59 trie_display(root, 0); 60 61 struct trie_node const *search_result; 62 63 printf("trie_search(\"foo\")\n"); 64 search_result = trie_search(root, "foo", 3); 65 assert(search_result == foo); 66 67 printf("trie_search(\"bar\")\n"); 68 search_result = trie_search(root, "bar", 3); 69 assert(search_result == bar); 70 71 printf("trie_search(\"baz\")\n"); 72 search_result = trie_search(root, "baz", 3); 73 assert(!search_result); 74 75 printf("trie_search(\"forsee\")\n"); 76 search_result = trie_search(root, "forsee", 6); 77 assert(search_result == forsee); 78 79 printf("arena stats: %zu/%zu bytes used, %zu nodes allocated\n", 80 arena.len, arena.cap, arena.len / sizeof *root); 81 82 return 0; 83 }