Mercurial > repos > blastem

comparison tern.c @ 429:f6fdde540791

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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