Fixed bug - glk_stylehint_set doesn't loop infinitely anymore
[rodin/chimara.git] / interpreters / git / search.c
1 // $Id: search.c,v 1.1 2003/10/18 20:06:41 iain Exp $
2
3 // search.c: Glulxe code for built-in search opcodes
4 // Designed by Andrew Plotkin <erkyrath@eblong.com>
5 // http://www.eblong.com/zarf/glulx/index.html
6
7 #include "glk.h"
8 #include "git.h"
9 #include "opcodes.h"
10
11 #ifndef TRUE
12 #define TRUE 1
13 #endif
14 #ifndef FALSE
15 #define FALSE 0
16 #endif
17
18 #define serop_KeyIndirect (0x01)
19 #define serop_ZeroKeyTerminates (0x02)
20 #define serop_ReturnIndex (0x04)
21 /* ### KeyZeroBounded? variants? */
22 /* ### LowerBoundKey? */
23
24 /* In general, these search functions look through a bunch of structures
25    in memory, searching for one whose key (a fixed-size sequence of bytes
26    within the structure) matches a given key. The result can indicate a
27    particular structure within the bunch, or it can be NULL ("not found".)
28
29    Any or all of these options can be applied:
30
31    KeyIndirect: If this is true, the key argument is taken to be the
32    start of an array of bytes in memory (whose length is keysize).
33    If it is false, the key argument contains the key itself. In
34    this case, keysize *must* be 1, 2, or 4. The key is stored in the
35    lower bytes of the key argument, big-endian. (The upper bytes are
36    ignored.)
37
38    ZeroKeyTerminates: If this is true, when the search reaches a struct
39    whose key is all zeroes, the search terminates (and returns NULL).
40    If the searched-for key happens to also be zeroes, the key-match
41    (returning the struct) takes precedence over the zero-match (returning
42    NULL.)
43
44    ReturnIndex: If this is false, the return value is the memory address
45    of the matching struct, or 0 to indicate NULL. If true, the return value
46    is the array index of the matching struct, or -1 to indicate NULL. 
47 */
48
49 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize, 
50   glui32 options);
51
52 /* linear_search():
53    An array of data structures is stored in memory, beginning at start,
54    each structure being structsize bytes. Within each struct, there is
55    a key value keysize bytes long, starting at position keyoffset (from
56    the start of the structure.) Search through these in order. If one
57    is found whose key matches, return it. If numstructs are searched
58    with no result, return NULL.
59    
60    numstructs may be -1 (0xFFFFFFFF) to indicate no upper limit to the
61    number of structures to search. The search will continue until a match
62    is found, or (if ZeroKeyTerminates is set) a zero key.
63
64    The KeyIndirect, ZeroKeyTerminates, and ReturnIndex options may be
65    used.
66 */
67 glui32 git_linear_search(glui32 key, glui32 keysize, 
68   glui32 start, glui32 structsize, glui32 numstructs, 
69   glui32 keyoffset, glui32 options)
70 {
71   unsigned char keybuf[4];
72   glui32 count;
73   int ix;
74   int retindex = ((options & serop_ReturnIndex) != 0);
75   int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
76
77   fetchkey(keybuf, key, keysize, options);
78
79   for (count=0; count<numstructs; count++, start+=structsize) {
80     int match = TRUE;
81     if (keysize <= 4) {
82       for (ix=0; match && ix<keysize; ix++) {
83         if (memRead8(start + keyoffset + ix) != keybuf[ix])
84           match = FALSE;
85       }
86     }
87     else {
88       for (ix=0; match && ix<keysize; ix++) {
89         if (memRead8(start + keyoffset + ix) != memRead8(key + ix))
90           match = FALSE;
91       }
92     }
93
94     if (match) {
95       if (retindex)
96         return count;
97       else
98         return start;
99     }
100
101     if (zeroterm) {
102       match = TRUE;
103       for (ix=0; match && ix<keysize; ix++) {
104         if (memRead8(start + keyoffset + ix) != 0)
105           match = FALSE;
106       }
107       if (match) {
108         break;
109       }
110     }
111   }
112   
113   if (retindex)
114     return -1;
115   else
116     return 0;
117 }
118
119 /* binary_search():
120    An array of data structures is in memory, as above. However, the
121    structs must be stored in forward order of their keys (taking each key
122    to be a multibyte unsigned integer.) There can be no duplicate keys. 
123    numstructs must indicate the exact length of the array; it cannot
124    be -1.
125
126    The KeyIndirect and ReturnIndex options may be used.
127 */
128 glui32 git_binary_search(glui32 key, glui32 keysize, 
129   glui32 start, glui32 structsize, glui32 numstructs, 
130   glui32 keyoffset, glui32 options)
131 {
132   unsigned char keybuf[4];
133   unsigned char byte, byte2;
134   glui32 top, bot, val, addr;
135   int ix;
136   int retindex = ((options & serop_ReturnIndex) != 0);
137
138   fetchkey(keybuf, key, keysize, options);
139   
140   bot = 0;
141   top = numstructs;
142   while (bot < top) {
143     int cmp = 0;
144     val = (top+bot) / 2;
145     addr = start + val * structsize;
146
147     if (keysize <= 4) {
148       for (ix=0; (!cmp) && ix<keysize; ix++) {
149         byte = memRead8(addr + keyoffset + ix);
150         byte2 = keybuf[ix];
151         if (byte < byte2)
152           cmp = -1;
153         else if (byte > byte2)
154           cmp = 1;
155       }
156     }
157     else {
158       for (ix=0; (!cmp) && ix<keysize; ix++) {
159         byte = memRead8(addr + keyoffset + ix);
160         byte2 = memRead8(key + ix);
161         if (byte < byte2)
162           cmp = -1;
163         else if (byte > byte2)
164           cmp = 1;
165       }
166     }
167
168     if (!cmp) {
169       if (retindex)
170         return val;
171       else
172         return addr;
173     }
174
175     if (cmp < 0) {
176       bot = val+1;
177     }
178     else {
179       top = val;
180     }
181   }
182
183   if (retindex)
184     return -1;
185   else
186     return 0;
187 }
188
189 /* linked_search():
190    The structures may be anywhere in memory, in any order. They are
191    linked by a four-byte address field, which is found in each struct
192    at position nextoffset. If this field contains zero, it indicates
193    the end of the linked list.
194
195    The KeyIndirect and ZeroKeyTerminates options may be used.
196 */
197 glui32 git_linked_search(glui32 key, glui32 keysize, 
198   glui32 start, glui32 keyoffset, glui32 nextoffset, glui32 options)
199 {
200   unsigned char keybuf[4];
201   int ix;
202   glui32 val;
203   int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
204
205   fetchkey(keybuf, key, keysize, options);
206
207   while (start != 0) {
208     int match = TRUE;
209     if (keysize <= 4) {
210       for (ix=0; match && ix<keysize; ix++) {
211         if (memRead8(start + keyoffset + ix) != keybuf[ix])
212           match = FALSE;
213       }
214     }
215     else {
216       for (ix=0; match && ix<keysize; ix++) {
217         if (memRead8(start + keyoffset + ix) != memRead8(key + ix))
218           match = FALSE;
219       }
220     }
221
222     if (match) {
223       return start;
224     }
225
226     if (zeroterm) {
227       match = TRUE;
228       for (ix=0; match && ix<keysize; ix++) {
229         if (memRead8(start + keyoffset + ix) != 0)
230           match = FALSE;
231       }
232       if (match) {
233         break;
234       }
235     }
236     
237     val = start + nextoffset;
238     start = memRead32(val);
239   }
240
241   return 0;
242 }
243
244 /* fetchkey():
245    This massages the key into a form that's easier to handle. When it
246    returns, the key will be stored in keybuf if keysize <= 4; otherwise,
247    it will be in memory.
248 */
249 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize, 
250   glui32 options)
251 {
252   int ix;
253
254   if (options & serop_KeyIndirect) {
255     if (keysize <= 4) {
256       for (ix=0; ix<keysize; ix++)
257         keybuf[ix] = memRead8(key+ix);
258     }
259   }
260   else {
261     switch (keysize) {
262     case 4:
263       write32(keybuf, key);
264       break;
265     case 2:
266       write16(keybuf, key);
267       break;
268     case 1:
269       write8(keybuf, key);
270       break;
271     default:
272       fatalError("Direct search key must hold one, two, or four bytes.");
273     }
274   }
275 }