Mercurial > repos > blastem
annotate tern.c @ 478:2e4a4188cfb0
Fix DMA fill so that it does not cause observable changes to the FIFO. Get DMA copy mostly correct from an observable ffect perspective. DMA copy probably does not reflect internal implementation still given that evidence seems to suggest no FIFO usage at all.
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Tue, 17 Sep 2013 00:11:45 -0700 |
parents | 140af5509ce7 |
children | 51bf87f76d15 |
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 |
140af5509ce7
Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents:
431
diff
changeset
|
3 This file is part of BlastEm. |
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 |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
104 void * tern_find_ptr(tern_node * head, char * key) |
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 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
110 return NULL; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
111 } |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
112 |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
113 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
|
114 { |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
115 tern_val val; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
116 val.ptrval = value; |
f6fdde540791
Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff
changeset
|
117 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
|
118 } |
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 |