1 /*
2 * Schism Tracker - a cross-platform Impulse Tracker clone
3 * copyright (c) 2003-2005 Storlek <storlek@rigelseven.com>
4 * copyright (c) 2005-2008 Mrs. Brisby <mrs.brisby@nimh.org>
5 * copyright (c) 2009 Storlek & Mrs. Brisby
6 * copyright (c) 2010-2012 Storlek
7 * URL: http://schismtracker.org/
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 */
23
24 #include <stdlib.h>
25
26 #include "tree.h"
27
28
29 typedef struct treenode {
30 struct treenode *left, *right;
31 void *value;
32 } treenode_t;
33
34 struct tree {
35 treecmp_t cmp;
36 treenode_t *root;
37 };
38
39 typedef void (*nodewalk_t) (treenode_t *node);
40
41
_treenode_walk(treenode_t * node,treewalk_t tapply,nodewalk_t napply)42 static void _treenode_walk(treenode_t *node, treewalk_t tapply, nodewalk_t napply)
43 {
44 // IF IF IF IF IF
45
46 if (!node)
47 return;
48 if (node->left)
49 _treenode_walk(node->left, tapply, napply);
50 if (node->right)
51 _treenode_walk(node->right, tapply, napply);
52 if (tapply)
53 tapply(node->value);
54 if (napply)
55 napply(node);
56 }
57
_treenode_free(treenode_t * node)58 static void _treenode_free(treenode_t *node)
59 {
60 free(node);
61 }
62
tree_alloc(treecmp_t cmp)63 tree_t *tree_alloc(treecmp_t cmp)
64 {
65 tree_t *tree = mem_calloc(1, sizeof(tree_t));
66 tree->cmp = cmp;
67 return tree;
68 }
69
tree_free(tree_t * tree,treewalk_t freeval)70 void tree_free(tree_t *tree, treewalk_t freeval)
71 {
72 _treenode_walk(tree->root, freeval, _treenode_free);
73 free(tree);
74 }
75
76
_treenode_find(treenode_t * node,treecmp_t cmp,void * value)77 static treenode_t *_treenode_find(treenode_t *node, treecmp_t cmp, void *value)
78 {
79 int r;
80
81 while (node) {
82 r = cmp(value, node->value);
83 if (r == 0)
84 break;
85 else if (r < 0)
86 node = node->left;
87 else
88 node = node->right;
89 }
90 return node;
91 }
92
_treenode_insert(treenode_t * node,treecmp_t cmp,treenode_t * new)93 static treenode_t *_treenode_insert(treenode_t *node, treecmp_t cmp, treenode_t *new)
94 {
95 int r;
96
97 if (!node)
98 return new;
99
100 r = cmp(new->value, node->value);
101 if (r < 0)
102 node->left = _treenode_insert(node->left, cmp, new);
103 else
104 node->right = _treenode_insert(node->right, cmp, new);
105 return node;
106 }
107
tree_walk(tree_t * tree,treewalk_t apply)108 void tree_walk(tree_t *tree, treewalk_t apply)
109 {
110 _treenode_walk(tree->root, apply, NULL);
111 }
112
113
tree_insert(tree_t * tree,void * value)114 void *tree_insert(tree_t *tree, void *value)
115 {
116 treenode_t *node = _treenode_find(tree->root, tree->cmp, value);
117
118 if (node)
119 return node->value;
120
121 node = mem_calloc(1, sizeof(treenode_t));
122 node->value = value;
123 tree->root = _treenode_insert(tree->root, tree->cmp, node);
124 return NULL;
125 }
126
tree_replace(tree_t * tree,void * value)127 void *tree_replace(tree_t *tree, void *value)
128 {
129 void *prev;
130 treenode_t *node = _treenode_find(tree->root, tree->cmp, value);
131
132 if (node) {
133 prev = node->value;
134 node->value = value;
135 return prev;
136 }
137
138 node = mem_calloc(1, sizeof(treenode_t));
139 node->value = value;
140 tree->root = _treenode_insert(tree->root, tree->cmp, node);
141 return NULL;
142 }
143
tree_find(tree_t * tree,void * value)144 void *tree_find(tree_t *tree, void *value)
145 {
146 treenode_t *node = _treenode_find(tree->root, tree->cmp, value);
147 return node ? node->value : NULL;
148 }
149
150
151
152
153 #ifdef TEST
154 #include <stdio.h>
155 #include <string.h>
156
157 struct node {
158 char *k, *v;
159 };
160
sncmp(const void * a,const void * b)161 int sncmp(const void *a, const void *b)
162 {
163 return strcmp(((struct node *) a)->k,
164 ((struct node *) b)->k);
165 }
166
snalloc(char * k,char * v)167 struct node *snalloc(char *k, char *v)
168 {
169 struct node *n = mem_alloc(sizeof(struct node));
170 n->k = k;
171 n->v = v;
172 return n;
173 }
174
main(int argc,char ** argv)175 int main(int argc, char **argv)
176 {
177 // some random junk
178 struct node nodes[] = {
179 {"caches", "disgruntled"},
180 {"logician", "daemon"},
181 {"silence", "rinse"},
182 {"shipwreck", "formats"},
183 {"justifying", "gnash"},
184 {"gadgetry", "ever"},
185 {"silence", "oxidized"}, // note: duplicate key
186 {"plumbing", "rickshaw"},
187 {NULL, NULL},
188 };
189 struct node find;
190 struct node *p;
191 tree_t *tree;
192 int n;
193
194 // test 1: populate with tree_insert
195 tree = tree_alloc(sncmp);
196 for (n = 0; nodes[n].k; n++) {
197 p = snalloc(nodes[n].k, nodes[n].v);
198 if (tree_insert(tree, p)) {
199 printf("duplicate key %s\n", p->k);
200 free(p);
201 }
202 }
203 find.k = "silence";
204 p = tree_find(tree, &find);
205 printf("%s: %s (should be 'rinse')\n", p->k, p->v);
206 tree_free(tree, free);
207
208
209 // test 2: populate with tree_replace
210 tree = tree_alloc(sncmp);
211 for (n = 0; nodes[n].k; n++) {
212 p = snalloc(nodes[n].k, nodes[n].v);
213 p = tree_replace(tree, p);
214 if (p) {
215 printf("duplicate key %s\n", p->k);
216 free(p);
217 }
218 }
219 find.k = "silence";
220 p = tree_find(tree, &find);
221 printf("%s: %s (should be 'oxidized')\n", p->k, p->v);
222 tree_free(tree, free);
223
224 return 0;
225 }
226 #endif /* TEST */
227
228