Mercurial > repos > blastem

comparison tern.c @ 1692:5dacaef602a7 segacd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge from default
author Michael Pavone <pavone@retrodev.com>
date Sat, 05 Jan 2019 00:58:08 -0800
parents 63659fb92db4
children 193b804c9845
comparison
equal deleted inserted replaced
1504:95b3a1a8b26c 1692:5dacaef602a7
43 if (!*cur) { 43 if (!*cur) {
44 *cur = malloc(sizeof(tern_node)); 44 *cur = malloc(sizeof(tern_node));
45 (*cur)->left = NULL; 45 (*cur)->left = NULL;
46 (*cur)->right = NULL; 46 (*cur)->right = NULL;
47 (*cur)->el = 0; 47 (*cur)->el = 0;
48 (*cur)->valtype = TVAL_NONE;
49 }
50 if ((*cur)->valtype == TVAL_PTR) {
51 //not freeing tern nodes can also cause leaks, but handling freeing those here is problematic
52 //since updating a sub-tree may involve creating a new root node
53 free((*cur)->straight.value.ptrval);
48 } 54 }
49 (*cur)->straight.value = value; 55 (*cur)->straight.value = value;
50 (*cur)->valtype = valtype; 56 (*cur)->valtype = valtype;
51 return head; 57 return head;
52 } 58 }
130 return ret.ptrval; 136 return ret.ptrval;
131 } 137 }
132 return NULL; 138 return NULL;
133 } 139 }
134 140
141 uint8_t tern_delete(tern_node **head, char const *key, tern_val *out)
142 {
143 tern_node *cur = *head, **last = head;
144 while (cur)
145 {
146 if (cur->el == *key) {
147 if (*key) {
148 last = &cur->straight.next;
149 cur = cur->straight.next;
150 key++;
151 } else {
152 break;
153 }
154 } else if (*key < cur->el) {
155 last = &cur->left;
156 cur = cur->left;
157 } else {
158 last = &cur->right;
159 cur = cur->right;
160 }
161 }
162 if (!cur) {
163 return TVAL_NONE;
164 }
165 *last = cur->right;
166 uint8_t valtype = cur->valtype;
167 if (out) {
168 *out = cur->straight.value;
169 }
170 free(cur);
171 return valtype;
172 }
173
135 tern_val tern_find_path_default(tern_node *head, char const *key, tern_val def, uint8_t req_valtype) 174 tern_val tern_find_path_default(tern_node *head, char const *key, tern_val def, uint8_t req_valtype)
136 { 175 {
137 tern_val ret; 176 tern_val ret;
138 while (*key) 177 while (*key)
139 { 178 {
173 tern_val val; 212 tern_val val;
174 val.ptrval = value; 213 val.ptrval = value;
175 return tern_insert(head, key, val, TVAL_NODE); 214 return tern_insert(head, key, val, TVAL_NODE);
176 } 215 }
177 216
217 tern_node *tern_insert_path(tern_node *head, char const *key, tern_val val, uint8_t valtype)
218 {
219 const char *next_key = key + strlen(key) + 1;
220 if (*next_key) {
221 tern_node *child = tern_find_node(head, key);
222 child = tern_insert_path(child, next_key, val, valtype);
223 return tern_insert_node(head, key, child);
224 } else {
225 return tern_insert(head, key, val, valtype);
226 }
227 }
228
229 uint8_t tern_delete_path(tern_node **head, char const *key, tern_val *out)
230 {
231 const char *next_key = key + strlen(key) + 1;
232 if (*next_key) {
233 tern_node *child = tern_find_node(*head, key);
234 if (!child) {
235 return TVAL_NONE;
236 }
237 tern_node *tmp = child;
238 uint8_t valtype = tern_delete_path(&tmp, next_key, out);
239 if (tmp != child) {
240 *head = tern_insert_node(*head, key, tmp);
241 }
242 return valtype;
243 } else {
244 return tern_delete(head, key, out);
245 }
246 }
247
178 uint32_t tern_count(tern_node *head) 248 uint32_t tern_count(tern_node *head)
179 { 249 {
180 uint32_t count = 0; 250 uint32_t count = 0;
181 if (head->left) { 251 if (head->left) {
182 count += tern_count(head->left); 252 count += tern_count(head->left);
200 fun(keybuf, head->straight.value, head->valtype, data); 270 fun(keybuf, head->straight.value, head->valtype, data);
201 } 271 }
202 if (head->left) { 272 if (head->left) {
203 tern_foreach_int(head->left, fun, data, keybuf, pos); 273 tern_foreach_int(head->left, fun, data, keybuf, pos);
204 } 274 }
205 if (head->el) { 275 if (head->el && head->straight.next) {
206 if (pos == MAX_ITER_KEY) { 276 if (pos == MAX_ITER_KEY) {
207 fatal_error("tern_foreach_int: exceeded maximum key size"); 277 fatal_error("tern_foreach_int: exceeded maximum key size");
208 } 278 }
209 keybuf[pos] = head->el; 279 keybuf[pos] = head->el;
210 tern_foreach_int(head->straight.next, fun, data, keybuf, pos+1); 280 tern_foreach_int(head->straight.next, fun, data, keybuf, pos+1);