Mercurial > repos > blastem

annotate tern.c @ 660:e7cae6d9aaa6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add the 3 cycle delay back in to Z80 bank area access
author Michael Pavone <pavone@retrodev.com>
date Thu, 01 Jan 2015 22:18:32 -0800
parents de6f00204fa2
children 1b2f8280ba81
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
631
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
125 char * tern_int_key(uint32_t key, char * buf)
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
126 {
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
127 char * cur = buf;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
128 while (key)
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
129 {
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
130 *(cur++) = (key & 0x7F) + 1;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
131 key >>= 7;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
132 }
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
133 *cur = 0;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
134 return buf;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
135 }