1/*
  2 Copyright 2013 Michael Pavone
  3 This file is part of BlastEm.
  4 BlastEm is free software distributed under the terms of the GNU General Public License version 3 or greater. See COPYING for full license text.
  5*/
  6#include "tern.h"
  7#include <stddef.h>
  8#include <stdlib.h>
  9#include <string.h>
 10#include <stdio.h>
 11#include "util.h"
 12
 13tern_node * tern_insert(tern_node * head, char const * key, tern_val value, uint8_t valtype)
 14{
 15	tern_node ** cur = &head;
 16	while(*key)
 17	{
 18		if (*cur) {
 19			while(*cur && (*cur)->el != *key)
 20			{
 21				if (*key < (*cur)->el) {
 22					cur = &(*cur)->left;
 23				} else {
 24					cur = &(*cur)->right;
 25				}
 26			}
 27		}
 28		if (!*cur) {
 29			*cur = malloc(sizeof(tern_node));
 30			(*cur)->left = NULL;
 31			(*cur)->right = NULL;
 32			(*cur)->straight.next = NULL;
 33			(*cur)->el = *key;
 34			(*cur)->valtype = TVAL_NONE;
 35		}
 36		cur = &((*cur)->straight.next);
 37		key++;
 38	}
 39	while(*cur && (*cur)->el)
 40	{
 41		cur = &(*cur)->left;
 42	}
 43	if (!*cur) {
 44		*cur = malloc(sizeof(tern_node));
 45		(*cur)->left = NULL;
 46		(*cur)->right = NULL;
 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);
 54	}
 55	(*cur)->straight.value = value;
 56	(*cur)->valtype = valtype;
 57	return head;
 58}
 59
 60uint8_t tern_find(tern_node * head, char const * key, tern_val *ret)
 61{
 62	tern_node * cur = head;
 63	while (cur)
 64	{
 65		if (cur->el == *key) {
 66			if (*key) {
 67				cur = cur->straight.next;
 68				key++;
 69			} else {
 70				*ret = cur->straight.value;
 71				return cur->valtype;
 72			}
 73		} else if (*key < cur->el) {
 74			cur = cur->left;
 75		} else {
 76			cur = cur->right;
 77		}
 78	}
 79	return TVAL_NONE;
 80}
 81
 82tern_node * tern_find_prefix(tern_node * head, char const * key)
 83{
 84	tern_node * cur = head;
 85	while (cur && *key)
 86	{
 87		if (cur->el == *key) {
 88			cur = cur->straight.next;
 89			key++;
 90		} else if (*key < cur->el) {
 91			cur = cur->left;
 92		} else {
 93			cur = cur->right;
 94		}
 95	}
 96	return cur;
 97}
 98
 99intptr_t tern_find_int(tern_node * head, char const * key, intptr_t def)
100{
101	tern_val ret;
102	uint8_t valtype = tern_find(head, key, &ret);
103	if (valtype == TVAL_INT) {
104		return ret.intval;
105	}
106	return def;
107}
108
109tern_node * tern_insert_int(tern_node * head, char const * key, intptr_t value)
110{
111	tern_val val;
112	val.intval = value;
113	return tern_insert(head, key, val, TVAL_INT);
114}
115
116void * tern_find_ptr_default(tern_node * head, char const * key, void * def)
117{
118	tern_val ret;
119	uint8_t valtype = tern_find(head, key, &ret);
120	if (valtype == TVAL_PTR) {
121		return ret.ptrval;
122	}
123	return def;
124}
125
126void * tern_find_ptr(tern_node * head, char const * key)
127{
128	return tern_find_ptr_default(head, key, NULL);
129}
130
131tern_node *tern_find_node(tern_node *head, char const *key)
132{
133	tern_val ret;
134	uint8_t valtype = tern_find(head, key, &ret);
135	if (valtype == TVAL_NODE) {
136		return ret.ptrval;
137	}
138	return NULL;
139}
140
141uint8_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
174tern_val tern_find_path_default(tern_node *head, char const *key, tern_val def, uint8_t req_valtype)
175{
176	tern_val ret;
177	while (*key)
178	{
179		uint8_t valtype = tern_find(head, key, &ret);
180		if (!valtype) {
181			return def;
182		}
183		key = key + strlen(key) + 1;
184		if (*key) {
185			if (valtype != TVAL_NODE) {
186				return def;
187			}
188			head = ret.ptrval;
189		} else if (req_valtype && req_valtype != valtype) {
190			return def;
191		}
192	}
193	return ret;
194}
195
196tern_val tern_find_path(tern_node *head, char const *key, uint8_t valtype)
197{
198	tern_val def;
199	def.ptrval = NULL;
200	return tern_find_path_default(head, key, def, valtype);
201}
202
203tern_node * tern_insert_ptr(tern_node * head, char const * key, void * value)
204{
205	tern_val val;
206	val.ptrval = value;
207	return tern_insert(head, key, val, TVAL_PTR);
208}
209
210tern_node * tern_insert_node(tern_node *head, char const *key, tern_node *value)
211{
212	tern_val val;
213	val.ptrval = value;
214	return tern_insert(head, key, val, TVAL_NODE);
215}
216
217tern_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
229uint8_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
248uint32_t tern_count(tern_node *head)
249{
250	uint32_t count = 0;
251	if (head->left) {
252		count += tern_count(head->left);
253	}
254	if (head->right) {
255		count += tern_count(head->right);
256	}
257	if (!head->el) {
258		count++;
259	} else if (head->straight.next) {
260		count += tern_count(head->straight.next);
261	}
262	return count;
263}
264
265#define MAX_ITER_KEY 127
266void tern_foreach_int(tern_node *head, iter_fun fun, void *data, char *keybuf, int pos)
267{
268	if (!head->el) {
269		keybuf[pos] = 0;
270		fun(keybuf, head->straight.value, head->valtype, data);
271	}
272	if (head->left) {
273		tern_foreach_int(head->left, fun, data, keybuf, pos);
274	}
275	if (head->el && head->straight.next) {
276		if (pos == MAX_ITER_KEY) {
277			fatal_error("tern_foreach_int: exceeded maximum key size");
278		}
279		keybuf[pos] = head->el;
280		tern_foreach_int(head->straight.next, fun, data, keybuf, pos+1);
281	}
282	if (head->right) {
283		tern_foreach_int(head->right, fun, data, keybuf, pos);
284	}
285}
286
287void tern_foreach(tern_node *head, iter_fun fun, void *data)
288{
289	//lame, but good enough for my purposes
290	char key[MAX_ITER_KEY+1];
291	tern_foreach_int(head, fun, data, key, 0);
292}
293
294char * tern_int_key(uint32_t key, char * buf)
295{
296	char * cur = buf;
297	while (key)
298	{
299		*(cur++) = (key & 0x7F) + 1;
300		key >>= 7;
301	}
302	*cur = 0;
303	return buf;
304}
305
306void tern_free(tern_node *head)
307{
308	if (head->left) {
309		tern_free(head->left);
310	}
311	if (head->right) {
312		tern_free(head->right);
313	}
314	if (head->el) {
315		tern_free(head->straight.next);
316	}
317	free(head);
318}