Mercurial > repos > blastem
annotate tern.c @ 583:819921b76b4b
Use update_flags instead of individual set_flag calls in a few places
author | Michael Pavone <pavone@retrodev.com> |
---|---|
date | Fri, 07 Mar 2014 17:51:40 -0800 |
parents | 51bf87f76d15 |
children | de6f00204fa2 |
rev | line source |
---|---|
467
140af5509ce7
Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents:
431
diff
changeset
|
1 /* |
140af5509ce7
Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents:
431
diff
changeset
|
2 Copyright 2013 Michael Pavone |
498
51bf87f76d15
Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents:
467
diff
changeset
|
3 This file is part of BlastEm. |
467
140af5509ce7
Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents:
431
diff
changeset
|
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. |
140af5509ce7
Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents:
431
diff
changeset
|
5 */ |
429
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
6 #include "tern.h" |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
7 #include <stddef.h> |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
8 #include <stdlib.h> |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
9 |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
10 tern_node * tern_insert(tern_node * head, char * key, tern_val value) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
11 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
12 tern_node ** cur = &head; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
13 while(*key) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
14 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
15 if (*cur) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
16 while(*cur && (*cur)->el != *key) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
17 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
18 if (*key < (*cur)->el) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
19 cur = &(*cur)->left; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
20 } else { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
21 cur = &(*cur)->right; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
22 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
23 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
24 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
25 if (!*cur) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
26 *cur = malloc(sizeof(tern_node)); |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
27 (*cur)->left = NULL; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
28 (*cur)->right = NULL; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
29 (*cur)->straight.next = NULL; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
30 (*cur)->el = *key; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
31 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
32 cur = &((*cur)->straight.next); |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
33 key++; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
34 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
35 while(*cur && (*cur)->el) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
36 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
37 cur = &(*cur)->left; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
38 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
39 if (!*cur) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
40 *cur = malloc(sizeof(tern_node)); |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
41 (*cur)->left = NULL; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
42 (*cur)->right = NULL; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
43 (*cur)->el = 0; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
44 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
45 (*cur)->straight.value = value; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
46 return head; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
47 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
48 |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
49 int tern_find(tern_node * head, char * key, tern_val *ret) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
50 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
51 tern_node * cur = head; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
52 while (cur) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
53 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
54 if (cur->el == *key) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
55 if (*key) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
56 cur = cur->straight.next; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
57 key++; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
58 } else { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
59 *ret = cur->straight.value; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
60 return 1; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
61 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
62 } else if (*key < cur->el) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
63 cur = cur->left; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
64 } else { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
65 cur = cur->right; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
66 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
67 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
68 return 0; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
69 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
70 |
431
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
71 tern_node * tern_find_prefix(tern_node * head, char * key) |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
72 { |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
73 tern_node * cur = head; |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
74 while (cur && *key) |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
75 { |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
76 if (cur->el == *key) { |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
77 cur = cur->straight.next; |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
78 key++; |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
79 } else if (*key < cur->el) { |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
80 cur = cur->left; |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
81 } else { |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
82 cur = cur->right; |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
83 } |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
84 } |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
85 return cur; |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
86 } |
440efd7d27a9
Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents:
429
diff
changeset
|
87 |
429
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
88 intptr_t tern_find_int(tern_node * head, char * key, intptr_t def) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
89 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
90 tern_val ret; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
91 if (tern_find(head, key, &ret)) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
92 return ret.intval; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
93 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
94 return def; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
95 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
96 |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
97 tern_node * tern_insert_int(tern_node * head, char * key, intptr_t value) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
98 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
99 tern_val val; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
100 val.intval = value; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
101 return tern_insert(head, key, val); |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
102 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
103 |
498
51bf87f76d15
Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents:
467
diff
changeset
|
104 void * tern_find_ptr_default(tern_node * head, char * key, void * def) |
429
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
105 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
106 tern_val ret; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
107 if (tern_find(head, key, &ret)) { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
108 return ret.ptrval; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
109 } |
498
51bf87f76d15
Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents:
467
diff
changeset
|
110 return def; |
51bf87f76d15
Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents:
467
diff
changeset
|
111 } |
51bf87f76d15
Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents:
467
diff
changeset
|
112 |
51bf87f76d15
Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents:
467
diff
changeset
|
113 void * tern_find_ptr(tern_node * head, char * key) |
51bf87f76d15
Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents:
467
diff
changeset
|
114 { |
51bf87f76d15
Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents:
467
diff
changeset
|
115 return tern_find_ptr_default(head, key, NULL); |
429
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
116 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
117 |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
118 tern_node * tern_insert_ptr(tern_node * head, char * key, void * value) |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
119 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
120 tern_val val; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
121 val.ptrval = value; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
122 return tern_insert(head, key, val); |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
123 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
124 |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
125 |