Mercurial > repos > blastem

annotate tern.c @ 572:0f32f52fc98e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Make some small changes in trans so that it is more likely to produce the same output as mustrans when given misbehaving programs. Add lea to testcases.txt. Improve the output of comparetest.py so that known issues can easily be separated from new ones.
author Michael Pavone <pavone@retrodev.com>
date Mon, 03 Mar 2014 21:08:43 -0800
parents 51bf87f76d15
children de6f00204fa2
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
467
140af5509ce7 Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents: 431
diff changeset
1 /*
140af5509ce7 Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents: 431
diff changeset
2 Copyright 2013 Michael Pavone
498
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
3 This file is part of BlastEm.
467
140af5509ce7 Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents: 431
diff changeset
4 BlastEm is free software distributed under the terms of the GNU General Public License version 3 or greater. See COPYING for full license text.
140af5509ce7 Added copyright notice to source files and added GPL license text in COPYING
Mike Pavone <pavone@retrodev.com>
parents: 431
diff changeset
5 */
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
6 #include "tern.h"
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
7 #include <stddef.h>
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
8 #include <stdlib.h>
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
9
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
10 tern_node * tern_insert(tern_node * head, char * key, tern_val value)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
11 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
12 tern_node ** cur = &head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
13 while(*key)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
14 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
15 if (*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
16 while(*cur && (*cur)->el != *key)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
17 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
18 if (*key < (*cur)->el) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
19 cur = &(*cur)->left;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
20 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
21 cur = &(*cur)->right;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
22 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
23 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
24 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
25 if (!*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
26 *cur = malloc(sizeof(tern_node));
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
27 (*cur)->left = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
28 (*cur)->right = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
29 (*cur)->straight.next = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
30 (*cur)->el = *key;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
31 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
32 cur = &((*cur)->straight.next);
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
33 key++;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
34 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
35 while(*cur && (*cur)->el)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
36 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
37 cur = &(*cur)->left;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
38 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
39 if (!*cur) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
40 *cur = malloc(sizeof(tern_node));
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
41 (*cur)->left = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
42 (*cur)->right = NULL;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
43 (*cur)->el = 0;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
44 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
45 (*cur)->straight.value = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
46 return head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
47 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
48
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
49 int tern_find(tern_node * head, char * key, tern_val *ret)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
50 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
51 tern_node * cur = head;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
52 while (cur)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
53 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
54 if (cur->el == *key) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
55 if (*key) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
56 cur = cur->straight.next;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
57 key++;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
58 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
59 *ret = cur->straight.value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
60 return 1;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
61 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
62 } else if (*key < cur->el) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
63 cur = cur->left;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
64 } else {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
65 cur = cur->right;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
66 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
67 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
68 return 0;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
69 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
70
431
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
71 tern_node * tern_find_prefix(tern_node * head, char * key)
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
72 {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
73 tern_node * cur = head;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
74 while (cur && *key)
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
75 {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
76 if (cur->el == *key) {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
77 cur = cur->straight.next;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
78 key++;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
79 } else if (*key < cur->el) {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
80 cur = cur->left;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
81 } else {
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
82 cur = cur->right;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
83 }
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
84 }
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
85 return cur;
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
86 }
440efd7d27a9 Read key bindings from config file
Mike Pavone <pavone@retrodev.com>
parents: 429
diff changeset
87
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
88 intptr_t tern_find_int(tern_node * head, char * key, intptr_t def)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
89 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
90 tern_val ret;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
91 if (tern_find(head, key, &ret)) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
92 return ret.intval;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
93 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
94 return def;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
95 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
96
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
97 tern_node * tern_insert_int(tern_node * head, char * key, intptr_t value)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
98 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
99 tern_val val;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
100 val.intval = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
101 return tern_insert(head, key, val);
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
102 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
103
498
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
104 void * tern_find_ptr_default(tern_node * head, char * key, void * def)
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
105 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
106 tern_val ret;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
107 if (tern_find(head, key, &ret)) {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
108 return ret.ptrval;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
109 }
498
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
110 return def;
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
111 }
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
112
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
113 void * tern_find_ptr(tern_node * head, char * key)
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
114 {
51bf87f76d15 Pull shader file names from config file.
Mike Pavone <pavone@retrodev.com>
parents: 467
diff changeset
115 return tern_find_ptr_default(head, key, NULL);
429
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
116 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
117
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
118 tern_node * tern_insert_ptr(tern_node * head, char * key, void * value)
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
119 {
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
120 tern_val val;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
121 val.ptrval = value;
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
122 return tern_insert(head, key, val);
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
123 }
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
124
f6fdde540791 Added ternary tree implementation and a simple test program for it
Mike Pavone <pavone@retrodev.com>
parents:
diff changeset
125