Mercurial > repos > blastem

annotate tern.c @ 768:2f48a3c187c6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add support for reading cartridge memory map from ROM database, though without EEPROM support for now
author Michael Pavone <pavone@retrodev.com>
date Tue, 07 Jul 2015 19:33:33 -0700
parents 1b2f8280ba81
children 724bbec47f86
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)) {
768
2f48a3c187c6 Add support for reading cartridge memory map from ROM database, though without EEPROM support for now
Michael Pavone <pavone@retrodev.com>
parents: 766
diff changeset
110 if (ret.intval & 1) {
2f48a3c187c6 Add support for reading cartridge memory map from ROM database, though without EEPROM support for now
Michael Pavone <pavone@retrodev.com>
parents: 766
diff changeset
111 return (void *)(ret.intval & ~1);
2f48a3c187c6 Add support for reading cartridge memory map from ROM database, though without EEPROM support for now
Michael Pavone <pavone@retrodev.com>
parents: 766
diff changeset
112 } else {
2f48a3c187c6 Add support for reading cartridge memory map from ROM database, though without EEPROM support for now
Michael Pavone <pavone@retrodev.com>
parents: 766
diff changeset
113 return ret.ptrval;
2f48a3c187c6 Add support for reading cartridge memory map from ROM database, though without EEPROM support for now
Michael Pavone <pavone@retrodev.com>
parents: 766
diff changeset
114 }
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
115 }
498
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
116 return def;
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
117 }
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
118
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
119 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
120 {
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
121 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
122 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
123
766
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
124 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
125 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
126 tern_val ret;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
127 while (*key)
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
128 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
129 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
130 return def;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
131 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
132 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
133 if (*key) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
134 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
135 if (!head) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
136 return def;
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 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
140 return ret;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
141 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
142
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
143 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
144 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
145 tern_val def;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
146 def.ptrval = NULL;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
147 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
148 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
149
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
150 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
151 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
152 tern_val val;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
153 val.ptrval = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
154 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
155 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
156
766
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
157 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
158 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
159 tern_val val;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
160 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
161 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
162 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
163
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
164 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
165 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
166 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
167 if (head->left) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
168 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
169 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
170 if (head->right) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
171 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
172 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
173 if (!head->el) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
174 count++;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
175 } 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
176 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
177 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
178 return count;
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
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
181 #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
182 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
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->el) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
185 keybuf[pos] = 0;
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
186 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
187 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
188 if (head->left) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
189 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
190 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
191 if (head->el) {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
192 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
193 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
194 exit(1);
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
195 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
196 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
197 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
198 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
199 if (head->right) {
768
2f48a3c187c6 Add support for reading cartridge memory map from ROM database, though without EEPROM support for now
Michael Pavone <pavone@retrodev.com>
parents: 766
diff changeset
200 tern_foreach_int(head->right, fun, data, keybuf, pos);
766
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 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
203
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
204 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
205 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
206 //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
207 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
208 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
209 }
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
210
631
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
211 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
212 {
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
213 char * cur = buf;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
214 while (key)
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
215 {
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
216 *(cur++) = (key & 0x7F) + 1;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
217 key >>= 7;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
218 }
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
219 *cur = 0;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
220 return buf;
de6f00204fa2 Add support for disassembling VOS program modules
Michael Pavone <pavone@retrodev.com>
parents: 498
diff changeset
221 }
766
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
222
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
223 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
224 {
1b2f8280ba81 WIP changes to support reading cart memory map from ROM DB
Michael Pavone <pavone@retrodev.com>
parents: 631
diff changeset
225 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
226 }