Mercurial > repos > blastem

comparison tern.c @ 1326:071e761bcdcf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix a deficiency in the way types were handled in my ternary tree. Fixes in which some paths that were constructed from a template with variables would sometimes get an extra garbage character thrown in
author Michael Pavone <pavone@retrodev.com>
date Fri, 21 Apr 2017 23:35:32 -0700
parents 72ea3885e7b5
children e890971f3757
comparison
equal deleted inserted replaced
1325:58bfbed6cdb5 1326:071e761bcdcf
8 #include <stdlib.h> 8 #include <stdlib.h>
9 #include <string.h> 9 #include <string.h>
10 #include <stdio.h> 10 #include <stdio.h>
11 #include "util.h" 11 #include "util.h"
12 12
13 tern_node * tern_insert(tern_node * head, char const * key, tern_val value) 13 tern_node * tern_insert(tern_node * head, char const * key, tern_val value, uint8_t valtype)
14 { 14 {
15 tern_node ** cur = &head; 15 tern_node ** cur = &head;
16 while(*key) 16 while(*key)
17 { 17 {
18 if (*cur) { 18 if (*cur) {
29 *cur = malloc(sizeof(tern_node)); 29 *cur = malloc(sizeof(tern_node));
30 (*cur)->left = NULL; 30 (*cur)->left = NULL;
31 (*cur)->right = NULL; 31 (*cur)->right = NULL;
32 (*cur)->straight.next = NULL; 32 (*cur)->straight.next = NULL;
33 (*cur)->el = *key; 33 (*cur)->el = *key;
34 (*cur)->valtype = TVAL_NONE;
34 } 35 }
35 cur = &((*cur)->straight.next); 36 cur = &((*cur)->straight.next);
36 key++; 37 key++;
37 } 38 }
38 while(*cur && (*cur)->el) 39 while(*cur && (*cur)->el)
44 (*cur)->left = NULL; 45 (*cur)->left = NULL;
45 (*cur)->right = NULL; 46 (*cur)->right = NULL;
46 (*cur)->el = 0; 47 (*cur)->el = 0;
47 } 48 }
48 (*cur)->straight.value = value; 49 (*cur)->straight.value = value;
50 (*cur)->valtype = valtype;
49 return head; 51 return head;
50 } 52 }
51 53
52 int tern_find(tern_node * head, char const * key, tern_val *ret) 54 uint8_t tern_find(tern_node * head, char const * key, tern_val *ret)
53 { 55 {
54 tern_node * cur = head; 56 tern_node * cur = head;
55 while (cur) 57 while (cur)
56 { 58 {
57 if (cur->el == *key) { 59 if (cur->el == *key) {
58 if (*key) { 60 if (*key) {
59 cur = cur->straight.next; 61 cur = cur->straight.next;
60 key++; 62 key++;
61 } else { 63 } else {
62 *ret = cur->straight.value; 64 *ret = cur->straight.value;
63 return 1; 65 return cur->valtype;
64 } 66 }
65 } else if (*key < cur->el) { 67 } else if (*key < cur->el) {
66 cur = cur->left; 68 cur = cur->left;
67 } else { 69 } else {
68 cur = cur->right; 70 cur = cur->right;
69 } 71 }
70 } 72 }
71 return 0; 73 return TVAL_NONE;
72 } 74 }
73 75
74 tern_node * tern_find_prefix(tern_node * head, char const * key) 76 tern_node * tern_find_prefix(tern_node * head, char const * key)
75 { 77 {
76 tern_node * cur = head; 78 tern_node * cur = head;
89 } 91 }
90 92
91 intptr_t tern_find_int(tern_node * head, char const * key, intptr_t def) 93 intptr_t tern_find_int(tern_node * head, char const * key, intptr_t def)
92 { 94 {
93 tern_val ret; 95 tern_val ret;
94 if (tern_find(head, key, &ret)) { 96 uint8_t valtype = tern_find(head, key, &ret);
97 if (valtype == TVAL_INT) {
95 return ret.intval; 98 return ret.intval;
96 } 99 }
97 return def; 100 return def;
98 } 101 }
99 102
100 tern_node * tern_insert_int(tern_node * head, char const * key, intptr_t value) 103 tern_node * tern_insert_int(tern_node * head, char const * key, intptr_t value)
101 { 104 {
102 tern_val val; 105 tern_val val;
103 val.intval = value; 106 val.intval = value;
104 return tern_insert(head, key, val); 107 return tern_insert(head, key, val, TVAL_INT);
105 } 108 }
106 109
107 void * tern_find_ptr_default(tern_node * head, char const * key, void * def) 110 void * tern_find_ptr_default(tern_node * head, char const * key, void * def)
108 { 111 {
109 tern_val ret; 112 tern_val ret;
110 if (tern_find(head, key, &ret)) { 113 uint8_t valtype = tern_find(head, key, &ret);
111 if (ret.intval & 1) { 114 if (valtype == TVAL_PTR) {
112 return (void *)(ret.intval & ~1); 115 return ret.ptrval;
113 } else {
114 return ret.ptrval;
115 }
116 } 116 }
117 return def; 117 return def;
118 } 118 }
119 119
120 void * tern_find_ptr(tern_node * head, char const * key) 120 void * tern_find_ptr(tern_node * head, char const * key)
121 { 121 {
122 return tern_find_ptr_default(head, key, NULL); 122 return tern_find_ptr_default(head, key, NULL);
123 } 123 }
124 124
125 tern_val tern_find_path_default(tern_node *head, char const *key, tern_val def) 125 tern_node *tern_find_node(tern_node *head, char const *key)
126 {
127 tern_val ret;
128 uint8_t valtype = tern_find(head, key, &ret);
129 if (valtype == TVAL_NODE) {
130 return ret.ptrval;
131 }
132 return NULL;
133 }
134
135 tern_val tern_find_path_default(tern_node *head, char const *key, tern_val def, uint8_t req_valtype)
126 { 136 {
127 tern_val ret; 137 tern_val ret;
128 while (*key) 138 while (*key)
129 { 139 {
130 if (!tern_find(head, key, &ret)) { 140 uint8_t valtype = tern_find(head, key, &ret);
141 if (!valtype) {
131 return def; 142 return def;
132 } 143 }
133 key = key + strlen(key) + 1; 144 key = key + strlen(key) + 1;
134 if (*key) { 145 if (*key) {
135 head = tern_get_node(ret); 146 if (valtype != TVAL_NODE) {
136 if (!head) {
137 return def; 147 return def;
138 } 148 }
149 head = ret.ptrval;
150 } else if (req_valtype && req_valtype != valtype) {
151 return def;
139 } 152 }
140 } 153 }
141 return ret; 154 return ret;
142 } 155 }
143 156
144 tern_val tern_find_path(tern_node *head, char const *key) 157 tern_val tern_find_path(tern_node *head, char const *key, uint8_t valtype)
145 { 158 {
146 tern_val def; 159 tern_val def;
147 def.ptrval = NULL; 160 def.ptrval = NULL;
148 return tern_find_path_default(head, key, def); 161 return tern_find_path_default(head, key, def, valtype);
149 } 162 }
150 163
151 tern_node * tern_insert_ptr(tern_node * head, char const * key, void * value) 164 tern_node * tern_insert_ptr(tern_node * head, char const * key, void * value)
152 { 165 {
153 tern_val val; 166 tern_val val;
154 val.ptrval = value; 167 val.ptrval = value;
155 return tern_insert(head, key, val); 168 return tern_insert(head, key, val, TVAL_PTR);
156 } 169 }
157 170
158 tern_node * tern_insert_node(tern_node *head, char const *key, tern_node *value) 171 tern_node * tern_insert_node(tern_node *head, char const *key, tern_node *value)
159 { 172 {
160 tern_val val; 173 tern_val val;
161 val.intval = ((intptr_t)value) | 1; 174 val.ptrval = value;
162 return tern_insert(head, key, val); 175 return tern_insert(head, key, val, TVAL_NODE);
163 } 176 }
164 177
165 uint32_t tern_count(tern_node *head) 178 uint32_t tern_count(tern_node *head)
166 { 179 {
167 uint32_t count = 0; 180 uint32_t count = 0;
182 #define MAX_ITER_KEY 127 195 #define MAX_ITER_KEY 127
183 void tern_foreach_int(tern_node *head, iter_fun fun, void *data, char *keybuf, int pos) 196 void tern_foreach_int(tern_node *head, iter_fun fun, void *data, char *keybuf, int pos)
184 { 197 {
185 if (!head->el) { 198 if (!head->el) {
186 keybuf[pos] = 0; 199 keybuf[pos] = 0;
187 fun(keybuf, head->straight.value, data); 200 fun(keybuf, head->straight.value, head->valtype, data);
188 } 201 }
189 if (head->left) { 202 if (head->left) {
190 tern_foreach_int(head->left, fun, data, keybuf, pos); 203 tern_foreach_int(head->left, fun, data, keybuf, pos);
191 } 204 }
192 if (head->el) { 205 if (head->el) {
218 } 231 }
219 *cur = 0; 232 *cur = 0;
220 return buf; 233 return buf;
221 } 234 }
222 235
223 tern_node * tern_get_node(tern_val value)
224 {
225 return value.intval & 1 ? (tern_node *)(value.intval & ~1) : NULL;
226 }
227
228 void tern_free(tern_node *head) 236 void tern_free(tern_node *head)
229 { 237 {
230 if (head->left) { 238 if (head->left) {
231 tern_free(head->left); 239 tern_free(head->left);
232 } 240 }
234 tern_free(head->right); 242 tern_free(head->right);
235 } 243 }
236 if (head->el) { 244 if (head->el) {
237 tern_free(head->straight.next); 245 tern_free(head->straight.next);
238 } 246 }
239 } 247 free(head);
248 }