File: search.c

package info (click to toggle)
glulxe 0.5.4-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 516 kB
  • sloc: ansic: 9,504; python: 835; objc: 483; makefile: 29
file content (266 lines) | stat: -rw-r--r-- 7,105 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
/* search.c: Glulxe code for built-in search opcodes
    Designed by Andrew Plotkin <erkyrath@eblong.com>
    http://eblong.com/zarf/glulx/index.html
*/

#include "glk.h"
#include "glulxe.h"

#define serop_KeyIndirect (0x01)
#define serop_ZeroKeyTerminates (0x02)
#define serop_ReturnIndex (0x04)
/* ### KeyZeroBounded? variants? */
/* ### LowerBoundKey? */

/* In general, these search functions look through a bunch of structures
   in memory, searching for one whose key (a fixed-size sequence of bytes
   within the structure) matches a given key. The result can indicate a
   particular structure within the bunch, or it can be NULL ("not found".)

   Any or all of these options can be applied:

   KeyIndirect: If this is true, the key argument is taken to be the
   start of an array of bytes in memory (whose length is keysize).
   If it is false, the key argument contains the key itself. In
   this case, keysize *must* be 1, 2, or 4. The key is stored in the
   lower bytes of the key argument, big-endian. (The upper bytes are
   ignored.)

   ZeroKeyTerminates: If this is true, when the search reaches a struct
   whose key is all zeroes, the search terminates (and returns NULL).
   If the searched-for key happens to also be zeroes, the key-match
   (returning the struct) takes precedence over the zero-match (returning
   NULL.)

   ReturnIndex: If this is false, the return value is the memory address
   of the matching struct, or 0 to indicate NULL. If true, the return value
   is the array index of the matching struct, or -1 to indicate NULL. 
*/

static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize, 
  glui32 options);

/* linear_search():
   An array of data structures is stored in memory, beginning at start,
   each structure being structsize bytes. Within each struct, there is
   a key value keysize bytes long, starting at position keyoffset (from
   the start of the structure.) Search through these in order. If one
   is found whose key matches, return it. If numstructs are searched
   with no result, return NULL.
   
   numstructs may be -1 (0xFFFFFFFF) to indicate no upper limit to the
   number of structures to search. The search will continue until a match
   is found, or (if ZeroKeyTerminates is set) a zero key.

   The KeyIndirect, ZeroKeyTerminates, and ReturnIndex options may be
   used.
*/
glui32 linear_search(glui32 key, glui32 keysize, 
  glui32 start, glui32 structsize, glui32 numstructs, 
  glui32 keyoffset, glui32 options)
{
  unsigned char keybuf[4];
  glui32 count;
  int ix;
  int retindex = ((options & serop_ReturnIndex) != 0);
  int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);

  fetchkey(keybuf, key, keysize, options);

  for (count=0; count<numstructs; count++, start+=structsize) {
    int match = TRUE;
    if (keysize <= 4) {
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != keybuf[ix])
          match = FALSE;
      }
    }
    else {
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
          match = FALSE;
      }
    }

    if (match) {
      if (retindex)
        return count;
      else
        return start;
    }

    if (zeroterm) {
      match = TRUE;
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != 0)
          match = FALSE;
      }
      if (match) {
        break;
      }
    }
  }
  
  if (retindex)
    return -1;
  else
    return 0;
}

/* binary_search():
   An array of data structures is in memory, as above. However, the
   structs must be stored in forward order of their keys (taking each key
   to be a multibyte unsigned integer.) There can be no duplicate keys. 
   numstructs must indicate the exact length of the array; it cannot
   be -1.

   The KeyIndirect and ReturnIndex options may be used.
*/
glui32 binary_search(glui32 key, glui32 keysize, 
  glui32 start, glui32 structsize, glui32 numstructs, 
  glui32 keyoffset, glui32 options)
{
  unsigned char keybuf[4];
  unsigned char byte, byte2;
  glui32 top, bot, val, addr;
  int ix;
  int retindex = ((options & serop_ReturnIndex) != 0);

  fetchkey(keybuf, key, keysize, options);
  
  bot = 0;
  top = numstructs;
  while (bot < top) {
    int cmp = 0;
    val = (top+bot) / 2;
    addr = start + val * structsize;

    if (keysize <= 4) {
      for (ix=0; (!cmp) && ix<keysize; ix++) {
        byte = Mem1(addr + keyoffset + ix);
        byte2 = keybuf[ix];
        if (byte < byte2)
          cmp = -1;
        else if (byte > byte2)
          cmp = 1;
      }
    }
    else {
      for (ix=0; (!cmp) && ix<keysize; ix++) {
        byte = Mem1(addr + keyoffset + ix);
        byte2 = Mem1(key + ix);
        if (byte < byte2)
          cmp = -1;
        else if (byte > byte2)
          cmp = 1;
      }
    }

    if (!cmp) {
      if (retindex)
        return val;
      else
        return addr;
    }

    if (cmp < 0) {
      bot = val+1;
    }
    else {
      top = val;
    }
  }

  if (retindex)
    return -1;
  else
    return 0;
}

/* linked_search():
   The structures may be anywhere in memory, in any order. They are
   linked by a four-byte address field, which is found in each struct
   at position nextoffset. If this field contains zero, it indicates
   the end of the linked list.

   The KeyIndirect and ZeroKeyTerminates options may be used.
*/
glui32 linked_search(glui32 key, glui32 keysize, 
  glui32 start, glui32 keyoffset, glui32 nextoffset, glui32 options)
{
  unsigned char keybuf[4];
  int ix;
  glui32 val;
  int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);

  fetchkey(keybuf, key, keysize, options);

  while (start != 0) {
    int match = TRUE;
    if (keysize <= 4) {
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != keybuf[ix])
          match = FALSE;
      }
    }
    else {
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
          match = FALSE;
      }
    }

    if (match) {
      return start;
    }

    if (zeroterm) {
      match = TRUE;
      for (ix=0; match && ix<keysize; ix++) {
        if (Mem1(start + keyoffset + ix) != 0)
          match = FALSE;
      }
      if (match) {
        break;
      }
    }
    
    val = start + nextoffset;
    start = Mem4(val);
  }

  return 0;
}

/* fetchkey():
   This massages the key into a form that's easier to handle. When it
   returns, the key will be stored in keybuf if keysize <= 4; otherwise,
   it will be in memory.
*/
static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize, 
  glui32 options)
{
  int ix;

  if (options & serop_KeyIndirect) {
    if (keysize <= 4) {
      for (ix=0; ix<keysize; ix++)
        keybuf[ix] = Mem1(key+ix);
    }
  }
  else {
    switch (keysize) {
    case 4:
      Write4(keybuf, key);
      break;
    case 2:
      Write2(keybuf, key);
      break;
    case 1:
      Write1(keybuf, key);
      break;
    default:
      fatal_error("Direct search key must hold one, two, or four bytes.");
    }
  }
}