Mercurial > repos > blastem

annotate tern.c @ 450:3758bcdae5de

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix bug that caused a DMA fill to start after another DMA operation completed if the FIFO is not empty
author Mike Pavone <pavone@retrodev.com>
date Sun, 01 Sep 2013 12:11:28 -0700
parents 440efd7d27a9
children 140af5509ce7
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
1 #include "tern.h"
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
2 #include <stddef.h>
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
3 #include <stdlib.h>
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
4
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
5 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
6 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
7 tern_node ** cur = &head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
8 while(*key)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
9 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
10 if (*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
11 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
12 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
13 if (*key < (*cur)->el) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
14 cur = &(*cur)->left;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
15 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
16 cur = &(*cur)->right;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
17 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
18 }
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 (!*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
21 *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
22 (*cur)->left = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
23 (*cur)->right = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
24 (*cur)->straight.next = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
25 (*cur)->el = *key;
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 cur = &((*cur)->straight.next);
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
28 key++;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
29 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
30 while(*cur && (*cur)->el)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
31 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
32 cur = &(*cur)->left;
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 if (!*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
35 *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
36 (*cur)->left = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
37 (*cur)->right = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
38 (*cur)->el = 0;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
39 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
40 (*cur)->straight.value = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
41 return head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
42 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
43
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
44 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
45 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
46 tern_node * cur = head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
47 while (cur)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
48 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
49 if (cur->el == *key) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
50 if (*key) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
51 cur = cur->straight.next;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
52 key++;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
53 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
54 *ret = cur->straight.value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
55 return 1;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
56 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
57 } 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
58 cur = cur->left;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
59 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
60 cur = cur->right;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
61 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
62 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
63 return 0;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
64 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
65
431
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
66 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
67 {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
68 tern_node * cur = head;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
69 while (cur && *key)
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
70 {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
71 if (cur->el == *key) {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
72 cur = cur->straight.next;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
73 key++;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
74 } else if (*key < cur->el) {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
75 cur = cur->left;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
76 } else {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
77 cur = cur->right;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
78 }
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
79 }
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
80 return cur;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
81 }
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
82
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
83 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
84 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
85 tern_val ret;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
86 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
87 return ret.intval;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
88 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
89 return def;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
90 }
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_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
93 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
94 tern_val val;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
95 val.intval = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
96 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
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 void * tern_find_ptr(tern_node * head, char * key)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
100 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
101 tern_val ret;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
102 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
103 return ret.ptrval;
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 return NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
106 }
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_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
109 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
110 tern_val val;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
111 val.ptrval = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
112 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
113 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
114
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
115