1 /* search.c: Glulxe code for built-in search opcodes
2 Designed by Andrew Plotkin <erkyrath@eblong.com>
3 http://eblong.com/zarf/glulx/index.html
9 #define serop_KeyIndirect (0x01)
10 #define serop_ZeroKeyTerminates (0x02)
11 #define serop_ReturnIndex (0x04)
12 /* ### KeyZeroBounded? variants? */
13 /* ### LowerBoundKey? */
15 /* In general, these search functions look through a bunch of structures
16 in memory, searching for one whose key (a fixed-size sequence of bytes
17 within the structure) matches a given key. The result can indicate a
18 particular structure within the bunch, or it can be NULL ("not found".)
20 Any or all of these options can be applied:
22 KeyIndirect: If this is true, the key argument is taken to be the
23 start of an array of bytes in memory (whose length is keysize).
24 If it is false, the key argument contains the key itself. In
25 this case, keysize *must* be 1, 2, or 4. The key is stored in the
26 lower bytes of the key argument, big-endian. (The upper bytes are
29 ZeroKeyTerminates: If this is true, when the search reaches a struct
30 whose key is all zeroes, the search terminates (and returns NULL).
31 If the searched-for key happens to also be zeroes, the key-match
32 (returning the struct) takes precedence over the zero-match (returning
35 ReturnIndex: If this is false, the return value is the memory address
36 of the matching struct, or 0 to indicate NULL. If true, the return value
37 is the array index of the matching struct, or -1 to indicate NULL.
40 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize,
44 An array of data structures is stored in memory, beginning at start,
45 each structure being structsize bytes. Within each struct, there is
46 a key value keysize bytes long, starting at position keyoffset (from
47 the start of the structure.) Search through these in order. If one
48 is found whose key matches, return it. If numstructs are searched
49 with no result, return NULL.
51 numstructs may be -1 (0xFFFFFFFF) to indicate no upper limit to the
52 number of structures to search. The search will continue until a match
53 is found, or (if ZeroKeyTerminates is set) a zero key.
55 The KeyIndirect, ZeroKeyTerminates, and ReturnIndex options may be
58 glui32 linear_search(glui32 key, glui32 keysize,
59 glui32 start, glui32 structsize, glui32 numstructs,
60 glui32 keyoffset, glui32 options)
62 unsigned char keybuf[4];
65 int retindex = ((options & serop_ReturnIndex) != 0);
66 int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
68 fetchkey(keybuf, key, keysize, options);
70 for (count=0; count<numstructs; count++, start+=structsize) {
73 for (ix=0; match && ix<keysize; ix++) {
74 if (Mem1(start + keyoffset + ix) != keybuf[ix])
79 for (ix=0; match && ix<keysize; ix++) {
80 if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
94 for (ix=0; match && ix<keysize; ix++) {
95 if (Mem1(start + keyoffset + ix) != 0)
111 An array of data structures is in memory, as above. However, the
112 structs must be stored in forward order of their keys (taking each key
113 to be a multibyte unsigned integer.) There can be no duplicate keys.
114 numstructs must indicate the exact length of the array; it cannot
117 The KeyIndirect and ReturnIndex options may be used.
119 glui32 binary_search(glui32 key, glui32 keysize,
120 glui32 start, glui32 structsize, glui32 numstructs,
121 glui32 keyoffset, glui32 options)
123 unsigned char keybuf[4];
124 unsigned char byte, byte2;
125 glui32 top, bot, val, addr;
127 int retindex = ((options & serop_ReturnIndex) != 0);
129 fetchkey(keybuf, key, keysize, options);
136 addr = start + val * structsize;
139 for (ix=0; (!cmp) && ix<keysize; ix++) {
140 byte = Mem1(addr + keyoffset + ix);
144 else if (byte > byte2)
149 for (ix=0; (!cmp) && ix<keysize; ix++) {
150 byte = Mem1(addr + keyoffset + ix);
151 byte2 = Mem1(key + ix);
154 else if (byte > byte2)
181 The structures may be anywhere in memory, in any order. They are
182 linked by a four-byte address field, which is found in each struct
183 at position nextoffset. If this field contains zero, it indicates
184 the end of the linked list.
186 The KeyIndirect and ZeroKeyTerminates options may be used.
188 glui32 linked_search(glui32 key, glui32 keysize,
189 glui32 start, glui32 keyoffset, glui32 nextoffset, glui32 options)
191 unsigned char keybuf[4];
194 int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
196 fetchkey(keybuf, key, keysize, options);
201 for (ix=0; match && ix<keysize; ix++) {
202 if (Mem1(start + keyoffset + ix) != keybuf[ix])
207 for (ix=0; match && ix<keysize; ix++) {
208 if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
219 for (ix=0; match && ix<keysize; ix++) {
220 if (Mem1(start + keyoffset + ix) != 0)
228 val = start + nextoffset;
236 This massages the key into a form that's easier to handle. When it
237 returns, the key will be stored in keybuf if keysize <= 4; otherwise,
238 it will be in memory.
240 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize,
245 if (options & serop_KeyIndirect) {
247 for (ix=0; ix<keysize; ix++)
248 keybuf[ix] = Mem1(key+ix);
263 fatal_error("Direct search key must hold one, two, or four bytes.");