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