Mercurial > repos > blastem

annotate tern.c @ 766:1b2f8280ba81

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
WIP changes to support reading cart memory map from ROM DB
author Michael Pavone <pavone@retrodev.com>
date Sun, 05 Jul 2015 14:21:34 -0700
parents de6f00204fa2
children 2f48a3c187c6
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>
766
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
9 #include <string.h>
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
10 #include <stdio.h>
429
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 * 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
13 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
14 tern_node ** cur = &head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
15 while(*key)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
16 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
17 if (*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
18 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
19 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
20 if (*key < (*cur)->el) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
21 cur = &(*cur)->left;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
22 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
23 cur = &(*cur)->right;
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 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
26 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
27 if (!*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
28 *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
29 (*cur)->left = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
30 (*cur)->right = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
31 (*cur)->straight.next = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
32 (*cur)->el = *key;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
33 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
34 cur = &((*cur)->straight.next);
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
35 key++;
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 while(*cur && (*cur)->el)
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 cur = &(*cur)->left;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
40 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
41 if (!*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
42 *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
43 (*cur)->left = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
44 (*cur)->right = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
45 (*cur)->el = 0;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
46 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
47 (*cur)->straight.value = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
48 return head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
49 }
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 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
52 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
53 tern_node * cur = head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
54 while (cur)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
55 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
56 if (cur->el == *key) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
57 if (*key) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
58 cur = cur->straight.next;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
59 key++;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
60 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
61 *ret = cur->straight.value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
62 return 1;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
63 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
64 } 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
65 cur = cur->left;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
66 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
67 cur = cur->right;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
68 }
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 return 0;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
71 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
72
431
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
73 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
74 {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
75 tern_node * cur = head;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
76 while (cur && *key)
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
77 {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
78 if (cur->el == *key) {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
79 cur = cur->straight.next;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
80 key++;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
81 } else if (*key < cur->el) {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
82 cur = cur->left;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
83 } else {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
84 cur = cur->right;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
85 }
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 return cur;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
88 }
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
89
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
90 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
91 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
92 tern_val ret;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
93 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
94 return ret.intval;
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 return def;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
97 }
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_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
100 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
101 tern_val val;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
102 val.intval = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
103 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
104 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
105
498
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
106 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
107 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
108 tern_val ret;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
109 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
110 return ret.ptrval;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
111 }
498
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
112 return def;
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
113 }
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 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
116 {
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
117 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
118 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
119
766
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
120 tern_val tern_find_path_default(tern_node *head, char *key, tern_val def)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
121 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
122 tern_val ret;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
123 while (*key)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
124 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
125 if (!tern_find(head, key, &ret)) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
126 return def;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
127 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
128 key = key + strlen(key) + 1;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
129 if (*key) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
130 head = tern_get_node(ret);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
131 if (!head) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
132 return def;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
133 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
134 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
135 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
136 return ret;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
137 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
138
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
139 tern_val tern_find_path(tern_node *head, char *key)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
140 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
141 tern_val def;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
142 def.ptrval = NULL;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
143 return tern_find_path_default(head, key, def);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
144 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
145
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
146 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
147 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
148 tern_val val;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
149 val.ptrval = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
150 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
151 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
152
766
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
153 tern_node * tern_insert_node(tern_node *head, char *key, tern_node *value)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
154 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
155 tern_val val;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
156 val.intval = ((intptr_t)value) | 1;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
157 return tern_insert(head, key, val);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
158 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
159
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
160 uint32_t tern_count(tern_node *head)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
161 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
162 uint32_t count = 0;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
163 if (head->left) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
164 count += tern_count(head->left);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
165 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
166 if (head->right) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
167 count += tern_count(head->right);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
168 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
169 if (!head->el) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
170 count++;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
171 } else if (head->straight.next) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
172 count += tern_count(head->straight.next);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
173 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
174 return count;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
175 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
176
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
177 #define MAX_ITER_KEY 127
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
178 void tern_foreach_int(tern_node *head, iter_fun fun, void *data, char *keybuf, int pos)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
179 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
180 if (!head->el) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
181 keybuf[pos] = 0;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
182 fun(keybuf, head->straight.value, data);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
183 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
184 if (head->left) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
185 tern_foreach_int(head->left, fun, data, keybuf, pos);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
186 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
187 if (head->el) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
188 if (pos == MAX_ITER_KEY) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
189 fputs("exceeded maximum key size", stderr);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
190 exit(1);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
191 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
192 keybuf[pos] = head->el;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
193 tern_foreach_int(head->straight.next, fun, data, keybuf, pos+1);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
194 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
195 if (head->right) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
196 tern_foreach_int(head->left, fun, data, keybuf, pos);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
197 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
198 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
199
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
200 void tern_foreach(tern_node *head, iter_fun fun, void *data)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
201 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
202 //lame, but good enough for my purposes
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
203 char key[MAX_ITER_KEY+1];
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
204 tern_foreach_int(head, fun, data, key, 0);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
205 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
206
631
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
207 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
208 {
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
209 char * cur = buf;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
210 while (key)
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
211 {
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
212 *(cur++) = (key & 0x7F) + 1;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
213 key >>= 7;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
214 }
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
215 *cur = 0;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
216 return buf;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
217 }
766
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
218
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
219 tern_node * tern_get_node(tern_val value)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
220 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
221 return value.intval & 1 ? (tern_node *)(value.intval & ~1) : NULL;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
222 }