interpreters/glulxe/search.c

   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
   4 */
   5
   6 #include "glk.h"
   7 #include "glulxe.h"
   8
   9 #define serop_KeyIndirect (0x01)
  10 #define serop_ZeroKeyTerminates (0x02)
  11 #define serop_ReturnIndex (0x04)
  12 /* ### KeyZeroBounded? variants? */
  13 /* ### LowerBoundKey? */
  14
  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".)
  19
  20    Any or all of these options can be applied:
  21
  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
  27    ignored.)
  28
  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
  33    NULL.)
  34
  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.
  38 */
  39
  40 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize,
  41   glui32 options);
  42
  43 /* linear_search():
  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.
  50
  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.
  54
  55    The KeyIndirect, ZeroKeyTerminates, and ReturnIndex options may be
  56    used.
  57 */
  58 glui32 linear_search(glui32 key, glui32 keysize,
  59   glui32 start, glui32 structsize, glui32 numstructs,
  60   glui32 keyoffset, glui32 options)
  61 {
  62   unsigned char keybuf[4];
  63   glui32 count;
  64   int ix;
  65   int retindex = ((options & serop_ReturnIndex) != 0);
  66   int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
  67
  68   fetchkey(keybuf, key, keysize, options);
  69
  70   for (count=0; count<numstructs; count++, start+=structsize) {
  71     int match = TRUE;
  72     if (keysize <= 4) {
  73       for (ix=0; match && ix<keysize; ix++) {
  74         if (Mem1(start + keyoffset + ix) != keybuf[ix])
  75           match = FALSE;
  76       }
  77     }
  78     else {
  79       for (ix=0; match && ix<keysize; ix++) {
  80         if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
  81           match = FALSE;
  82       }
  83     }
  84
  85     if (match) {
  86       if (retindex)
  87         return count;
  88       else
  89         return start;
  90     }
  91
  92     if (zeroterm) {
  93       match = TRUE;
  94       for (ix=0; match && ix<keysize; ix++) {
  95         if (Mem1(start + keyoffset + ix) != 0)
  96           match = FALSE;
  97       }
  98       if (match) {
  99         break;
 100       }
 101     }
 102   }
 103
 104   if (retindex)
 105     return -1;
 106   else
 107     return 0;
 108 }
 109
 110 /* binary_search():
 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
 115    be -1.
 116
 117    The KeyIndirect and ReturnIndex options may be used.
 118 */
 119 glui32 binary_search(glui32 key, glui32 keysize,
 120   glui32 start, glui32 structsize, glui32 numstructs,
 121   glui32 keyoffset, glui32 options)
 122 {
 123   unsigned char keybuf[4];
 124   unsigned char byte, byte2;
 125   glui32 top, bot, val, addr;
 126   int ix;
 127   int retindex = ((options & serop_ReturnIndex) != 0);
 128
 129   fetchkey(keybuf, key, keysize, options);
 130
 131   bot = 0;
 132   top = numstructs;
 133   while (bot < top) {
 134     int cmp = 0;
 135     val = (top+bot) / 2;
 136     addr = start + val * structsize;
 137
 138     if (keysize <= 4) {
 139       for (ix=0; (!cmp) && ix<keysize; ix++) {
 140         byte = Mem1(addr + keyoffset + ix);
 141         byte2 = keybuf[ix];
 142         if (byte < byte2)
 143           cmp = -1;
 144         else if (byte > byte2)
 145           cmp = 1;
 146       }
 147     }
 148     else {
 149       for (ix=0; (!cmp) && ix<keysize; ix++) {
 150         byte = Mem1(addr + keyoffset + ix);
 151         byte2 = Mem1(key + ix);
 152         if (byte < byte2)
 153           cmp = -1;
 154         else if (byte > byte2)
 155           cmp = 1;
 156       }
 157     }
 158
 159     if (!cmp) {
 160       if (retindex)
 161         return val;
 162       else
 163         return addr;
 164     }
 165
 166     if (cmp < 0) {
 167       bot = val+1;
 168     }
 169     else {
 170       top = val;
 171     }
 172   }
 173
 174   if (retindex)
 175     return -1;
 176   else
 177     return 0;
 178 }
 179
 180 /* linked_search():
 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.
 185
 186    The KeyIndirect and ZeroKeyTerminates options may be used.
 187 */
 188 glui32 linked_search(glui32 key, glui32 keysize,
 189   glui32 start, glui32 keyoffset, glui32 nextoffset, glui32 options)
 190 {
 191   unsigned char keybuf[4];
 192   int ix;
 193   glui32 val;
 194   int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
 195
 196   fetchkey(keybuf, key, keysize, options);
 197
 198   while (start != 0) {
 199     int match = TRUE;
 200     if (keysize <= 4) {
 201       for (ix=0; match && ix<keysize; ix++) {
 202         if (Mem1(start + keyoffset + ix) != keybuf[ix])
 203           match = FALSE;
 204       }
 205     }
 206     else {
 207       for (ix=0; match && ix<keysize; ix++) {
 208         if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
 209           match = FALSE;
 210       }
 211     }
 212
 213     if (match) {
 214       return start;
 215     }
 216
 217     if (zeroterm) {
 218       match = TRUE;
 219       for (ix=0; match && ix<keysize; ix++) {
 220         if (Mem1(start + keyoffset + ix) != 0)
 221           match = FALSE;
 222       }
 223       if (match) {
 224         break;
 225       }
 226     }
 227
 228     val = start + nextoffset;
 229     start = Mem4(val);
 230   }
 231
 232   return 0;
 233 }
 234
 235 /* fetchkey():
 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.
 239 */
 240 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize,
 241   glui32 options)
 242 {
 243   int ix;
 244
 245   if (options & serop_KeyIndirect) {
 246     if (keysize <= 4) {
 247       for (ix=0; ix<keysize; ix++)
 248         keybuf[ix] = Mem1(key+ix);
 249     }
 250   }
 251   else {
 252     switch (keysize) {
 253     case 4:
 254       Write4(keybuf, key);
 255       break;
 256     case 2:
 257       Write2(keybuf, key);
 258       break;
 259     case 1:
 260       Write1(keybuf, key);
 261       break;
 262     default:
 263       fatal_error("Direct search key must hold one, two, or four bytes.");
 264     }
 265   }
 266 }