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
10 #define serop_KeyIndirect (0x01)
11 #define serop_ZeroKeyTerminates (0x02)
12 #define serop_ReturnIndex (0x04)
13 /* ### KeyZeroBounded? variants? */
14 /* ### LowerBoundKey? */
16 /* In general, these search functions look through a bunch of structures
17 in memory, searching for one whose key (a fixed-size sequence of bytes
18 within the structure) matches a given key. The result can indicate a
19 particular structure within the bunch, or it can be NULL ("not found".)
21 Any or all of these options can be applied:
23 KeyIndirect: If this is true, the key argument is taken to be the
24 start of an array of bytes in memory (whose length is keysize).
25 If it is false, the key argument contains the key itself. In
26 this case, keysize *must* be 1, 2, or 4. The key is stored in the
27 lower bytes of the key argument, big-endian. (The upper bytes are
30 ZeroKeyTerminates: If this is true, when the search reaches a struct
31 whose key is all zeroes, the search terminates (and returns NULL).
32 If the searched-for key happens to also be zeroes, the key-match
33 (returning the struct) takes precedence over the zero-match (returning
36 ReturnIndex: If this is false, the return value is the memory address
37 of the matching struct, or 0 to indicate NULL. If true, the return value
38 is the array index of the matching struct, or -1 to indicate NULL.
41 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize,
45 An array of data structures is stored in memory, beginning at start,
46 each structure being structsize bytes. Within each struct, there is
47 a key value keysize bytes long, starting at position keyoffset (from
48 the start of the structure.) Search through these in order. If one
49 is found whose key matches, return it. If numstructs are searched
50 with no result, return NULL.
52 numstructs may be -1 (0xFFFFFFFF) to indicate no upper limit to the
53 number of structures to search. The search will continue until a match
54 is found, or (if ZeroKeyTerminates is set) a zero key.
56 The KeyIndirect, ZeroKeyTerminates, and ReturnIndex options may be
59 glui32 linear_search(glui32 key, glui32 keysize,
60 glui32 start, glui32 structsize, glui32 numstructs,
61 glui32 keyoffset, glui32 options)
63 unsigned char keybuf[4];
66 int retindex = ((options & serop_ReturnIndex) != 0);
67 int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
69 fetchkey(keybuf, key, keysize, options);
71 for (count=0; count<numstructs; count++, start+=structsize) {
74 for (ix=0; match && ix<keysize; ix++) {
75 if (Mem1(start + keyoffset + ix) != keybuf[ix])
80 for (ix=0; match && ix<keysize; ix++) {
81 if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
95 for (ix=0; match && ix<keysize; ix++) {
96 if (Mem1(start + keyoffset + ix) != 0)
112 An array of data structures is in memory, as above. However, the
113 structs must be stored in forward order of their keys (taking each key
114 to be a multibyte unsigned integer.) There can be no duplicate keys.
115 numstructs must indicate the exact length of the array; it cannot
118 The KeyIndirect and ReturnIndex options may be used.
120 glui32 binary_search(glui32 key, glui32 keysize,
121 glui32 start, glui32 structsize, glui32 numstructs,
122 glui32 keyoffset, glui32 options)
124 unsigned char keybuf[4];
125 unsigned char byte, byte2;
126 glui32 top, bot, val, addr;
128 int retindex = ((options & serop_ReturnIndex) != 0);
130 fetchkey(keybuf, key, keysize, options);
137 addr = start + val * structsize;
140 for (ix=0; (!cmp) && ix<keysize; ix++) {
141 byte = Mem1(addr + keyoffset + ix);
145 else if (byte > byte2)
150 for (ix=0; (!cmp) && ix<keysize; ix++) {
151 byte = Mem1(addr + keyoffset + ix);
152 byte2 = Mem1(key + ix);
155 else if (byte > byte2)
182 The structures may be anywhere in memory, in any order. They are
183 linked by a four-byte address field, which is found in each struct
184 at position nextoffset. If this field contains zero, it indicates
185 the end of the linked list.
187 The KeyIndirect and ZeroKeyTerminates options may be used.
189 glui32 linked_search(glui32 key, glui32 keysize,
190 glui32 start, glui32 keyoffset, glui32 nextoffset, glui32 options)
192 unsigned char keybuf[4];
195 int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
197 fetchkey(keybuf, key, keysize, options);
202 for (ix=0; match && ix<keysize; ix++) {
203 if (Mem1(start + keyoffset + ix) != keybuf[ix])
208 for (ix=0; match && ix<keysize; ix++) {
209 if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
220 for (ix=0; match && ix<keysize; ix++) {
221 if (Mem1(start + keyoffset + ix) != 0)
229 val = start + nextoffset;
237 This massages the key into a form that's easier to handle. When it
238 returns, the key will be stored in keybuf if keysize <= 4; otherwise,
239 it will be in memory.
241 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize,
246 if (options & serop_KeyIndirect) {
248 for (ix=0; ix<keysize; ix++)
249 keybuf[ix] = Mem1(key+ix);
264 fatal_error("Direct search key must hold one, two, or four bytes.");