Mercurial > repos > blastem

annotate tern.c @ 778:6e1711d56633

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Remove extraneous define
author Michael Pavone <pavone@retrodev.com>
date Mon, 20 Jul 2015 21:58:31 -0700
parents 2f48a3c187c6
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 }