Mercurial > repos > blastem
comparison tern.c @ 429:f6fdde540791
Added ternary tree implementation and a simple test program for it
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Tue, 09 Jul 2013 20:51:42 -0700 |
parents | |
children | 440efd7d27a9 |
comparison
equal
deleted
inserted
replaced
428:006008a3f370 | 429:f6fdde540791 |
---|---|
1 #include "tern.h" | |
2 #include <stddef.h> | |
3 #include <stdlib.h> | |
4 | |
5 tern_node * tern_insert(tern_node * head, char * key, tern_val value) | |
6 { | |
7 tern_node ** cur = &head; | |
8 while(*key) | |
9 { | |
10 if (*cur) { | |
11 while(*cur && (*cur)->el != *key) | |
12 { | |
13 if (*key < (*cur)->el) { | |
14 cur = &(*cur)->left; | |
15 } else { | |
16 cur = &(*cur)->right; | |
17 } | |
18 } | |
19 } | |
20 if (!*cur) { | |
21 *cur = malloc(sizeof(tern_node)); | |
22 (*cur)->left = NULL; | |
23 (*cur)->right = NULL; | |
24 (*cur)->straight.next = NULL; | |
25 (*cur)->el = *key; | |
26 } | |
27 cur = &((*cur)->straight.next); | |
28 key++; | |
29 } | |
30 while(*cur && (*cur)->el) | |
31 { | |
32 cur = &(*cur)->left; | |
33 } | |
34 if (!*cur) { | |
35 *cur = malloc(sizeof(tern_node)); | |
36 (*cur)->left = NULL; | |
37 (*cur)->right = NULL; | |
38 (*cur)->el = 0; | |
39 } | |
40 (*cur)->straight.value = value; | |
41 return head; | |
42 } | |
43 | |
44 int tern_find(tern_node * head, char * key, tern_val *ret) | |
45 { | |
46 tern_node * cur = head; | |
47 while (cur) | |
48 { | |
49 if (cur->el == *key) { | |
50 if (*key) { | |
51 cur = cur->straight.next; | |
52 key++; | |
53 } else { | |
54 *ret = cur->straight.value; | |
55 return 1; | |
56 } | |
57 } else if (*key < cur->el) { | |
58 cur = cur->left; | |
59 } else { | |
60 cur = cur->right; | |
61 } | |
62 } | |
63 return 0; | |
64 } | |
65 | |
66 intptr_t tern_find_int(tern_node * head, char * key, intptr_t def) | |
67 { | |
68 tern_val ret; | |
69 if (tern_find(head, key, &ret)) { | |
70 return ret.intval; | |
71 } | |
72 return def; | |
73 } | |
74 | |
75 tern_node * tern_insert_int(tern_node * head, char * key, intptr_t value) | |
76 { | |
77 tern_val val; | |
78 val.intval = value; | |
79 return tern_insert(head, key, val); | |
80 } | |
81 | |
82 void * tern_find_ptr(tern_node * head, char * key) | |
83 { | |
84 tern_val ret; | |
85 if (tern_find(head, key, &ret)) { | |
86 return ret.ptrval; | |
87 } | |
88 return NULL; | |
89 } | |
90 | |
91 tern_node * tern_insert_ptr(tern_node * head, char * key, void * value) | |
92 { | |
93 tern_val val; | |
94 val.ptrval = value; | |
95 return tern_insert(head, key, val); | |
96 } | |
97 | |
98 |