interpreters/git/search.c

   1 // $Id: search.c,v 1.1 2003/10/18 20:06:41 iain Exp $
   2
   3 // search.c: Glulxe code for built-in search opcodes
   4 // Designed by Andrew Plotkin <erkyrath@eblong.com>
   5 // http://www.eblong.com/zarf/glulx/index.html
   6
   7 #include "glk.h"
   8 #include "git.h"
   9 #include "opcodes.h"
  10
  11 #ifndef TRUE
  12 #define TRUE 1
  13 #endif
  14 #ifndef FALSE
  15 #define FALSE 0
  16 #endif
  17
  18 #define serop_KeyIndirect (0x01)
  19 #define serop_ZeroKeyTerminates (0x02)
  20 #define serop_ReturnIndex (0x04)
  21 /* ### KeyZeroBounded? variants? */
  22 /* ### LowerBoundKey? */
  23
  24 /* In general, these search functions look through a bunch of structures
  25    in memory, searching for one whose key (a fixed-size sequence of bytes
  26    within the structure) matches a given key. The result can indicate a
  27    particular structure within the bunch, or it can be NULL ("not found".)
  28
  29    Any or all of these options can be applied:
  30
  31    KeyIndirect: If this is true, the key argument is taken to be the
  32    start of an array of bytes in memory (whose length is keysize).
  33    If it is false, the key argument contains the key itself. In
  34    this case, keysize *must* be 1, 2, or 4. The key is stored in the
  35    lower bytes of the key argument, big-endian. (The upper bytes are
  36    ignored.)
  37
  38    ZeroKeyTerminates: If this is true, when the search reaches a struct
  39    whose key is all zeroes, the search terminates (and returns NULL).
  40    If the searched-for key happens to also be zeroes, the key-match
  41    (returning the struct) takes precedence over the zero-match (returning
  42    NULL.)
  43
  44    ReturnIndex: If this is false, the return value is the memory address
  45    of the matching struct, or 0 to indicate NULL. If true, the return value
  46    is the array index of the matching struct, or -1 to indicate NULL.
  47 */
  48
  49 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize,
  50   glui32 options);
  51
  52 /* linear_search():
  53    An array of data structures is stored in memory, beginning at start,
  54    each structure being structsize bytes. Within each struct, there is
  55    a key value keysize bytes long, starting at position keyoffset (from
  56    the start of the structure.) Search through these in order. If one
  57    is found whose key matches, return it. If numstructs are searched
  58    with no result, return NULL.
  59
  60    numstructs may be -1 (0xFFFFFFFF) to indicate no upper limit to the
  61    number of structures to search. The search will continue until a match
  62    is found, or (if ZeroKeyTerminates is set) a zero key.
  63
  64    The KeyIndirect, ZeroKeyTerminates, and ReturnIndex options may be
  65    used.
  66 */
  67 glui32 git_linear_search(glui32 key, glui32 keysize,
  68   glui32 start, glui32 structsize, glui32 numstructs,
  69   glui32 keyoffset, glui32 options)
  70 {
  71   unsigned char keybuf[4];
  72   glui32 count;
  73   int ix;
  74   int retindex = ((options & serop_ReturnIndex) != 0);
  75   int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
  76
  77   fetchkey(keybuf, key, keysize, options);
  78
  79   for (count=0; count<numstructs; count++, start+=structsize) {
  80     int match = TRUE;
  81     if (keysize <= 4) {
  82       for (ix=0; match && ix<keysize; ix++) {
  83         if (memRead8(start + keyoffset + ix) != keybuf[ix])
  84           match = FALSE;
  85       }
  86     }
  87     else {
  88       for (ix=0; match && ix<keysize; ix++) {
  89         if (memRead8(start + keyoffset + ix) != memRead8(key + ix))
  90           match = FALSE;
  91       }
  92     }
  93
  94     if (match) {
  95       if (retindex)
  96         return count;
  97       else
  98         return start;
  99     }
 100
 101     if (zeroterm) {
 102       match = TRUE;
 103       for (ix=0; match && ix<keysize; ix++) {
 104         if (memRead8(start + keyoffset + ix) != 0)
 105           match = FALSE;
 106       }
 107       if (match) {
 108         break;
 109       }
 110     }
 111   }
 112
 113   if (retindex)
 114     return -1;
 115   else
 116     return 0;
 117 }
 118
 119 /* binary_search():
 120    An array of data structures is in memory, as above. However, the
 121    structs must be stored in forward order of their keys (taking each key
 122    to be a multibyte unsigned integer.) There can be no duplicate keys.
 123    numstructs must indicate the exact length of the array; it cannot
 124    be -1.
 125
 126    The KeyIndirect and ReturnIndex options may be used.
 127 */
 128 glui32 git_binary_search(glui32 key, glui32 keysize,
 129   glui32 start, glui32 structsize, glui32 numstructs,
 130   glui32 keyoffset, glui32 options)
 131 {
 132   unsigned char keybuf[4];
 133   unsigned char byte, byte2;
 134   glui32 top, bot, val, addr;
 135   int ix;
 136   int retindex = ((options & serop_ReturnIndex) != 0);
 137
 138   fetchkey(keybuf, key, keysize, options);
 139
 140   bot = 0;
 141   top = numstructs;
 142   while (bot < top) {
 143     int cmp = 0;
 144     val = (top+bot) / 2;
 145     addr = start + val * structsize;
 146
 147     if (keysize <= 4) {
 148       for (ix=0; (!cmp) && ix<keysize; ix++) {
 149         byte = memRead8(addr + keyoffset + ix);
 150         byte2 = keybuf[ix];
 151         if (byte < byte2)
 152           cmp = -1;
 153         else if (byte > byte2)
 154           cmp = 1;
 155       }
 156     }
 157     else {
 158       for (ix=0; (!cmp) && ix<keysize; ix++) {
 159         byte = memRead8(addr + keyoffset + ix);
 160         byte2 = memRead8(key + ix);
 161         if (byte < byte2)
 162           cmp = -1;
 163         else if (byte > byte2)
 164           cmp = 1;
 165       }
 166     }
 167
 168     if (!cmp) {
 169       if (retindex)
 170         return val;
 171       else
 172         return addr;
 173     }
 174
 175     if (cmp < 0) {
 176       bot = val+1;
 177     }
 178     else {
 179       top = val;
 180     }
 181   }
 182
 183   if (retindex)
 184     return -1;
 185   else
 186     return 0;
 187 }
 188
 189 /* linked_search():
 190    The structures may be anywhere in memory, in any order. They are
 191    linked by a four-byte address field, which is found in each struct
 192    at position nextoffset. If this field contains zero, it indicates
 193    the end of the linked list.
 194
 195    The KeyIndirect and ZeroKeyTerminates options may be used.
 196 */
 197 glui32 git_linked_search(glui32 key, glui32 keysize,
 198   glui32 start, glui32 keyoffset, glui32 nextoffset, glui32 options)
 199 {
 200   unsigned char keybuf[4];
 201   int ix;
 202   glui32 val;
 203   int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
 204
 205   fetchkey(keybuf, key, keysize, options);
 206
 207   while (start != 0) {
 208     int match = TRUE;
 209     if (keysize <= 4) {
 210       for (ix=0; match && ix<keysize; ix++) {
 211         if (memRead8(start + keyoffset + ix) != keybuf[ix])
 212           match = FALSE;
 213       }
 214     }
 215     else {
 216       for (ix=0; match && ix<keysize; ix++) {
 217         if (memRead8(start + keyoffset + ix) != memRead8(key + ix))
 218           match = FALSE;
 219       }
 220     }
 221
 222     if (match) {
 223       return start;
 224     }
 225
 226     if (zeroterm) {
 227       match = TRUE;
 228       for (ix=0; match && ix<keysize; ix++) {
 229         if (memRead8(start + keyoffset + ix) != 0)
 230           match = FALSE;
 231       }
 232       if (match) {
 233         break;
 234       }
 235     }
 236
 237     val = start + nextoffset;
 238     start = memRead32(val);
 239   }
 240
 241   return 0;
 242 }
 243
 244 /* fetchkey():
 245    This massages the key into a form that's easier to handle. When it
 246    returns, the key will be stored in keybuf if keysize <= 4; otherwise,
 247    it will be in memory.
 248 */
 249 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize,
 250   glui32 options)
 251 {
 252   int ix;
 253
 254   if (options & serop_KeyIndirect) {
 255     if (keysize <= 4) {
 256       for (ix=0; ix<keysize; ix++)
 257         keybuf[ix] = memRead8(key+ix);
 258     }
 259   }
 260   else {
 261     switch (keysize) {
 262     case 4:
 263       write32(keybuf, key);
 264       break;
 265     case 2:
 266       write16(keybuf, key);
 267       break;
 268     case 1:
 269       write8(keybuf, key);
 270       break;
 271     default:
 272       fatalError("Direct search key must hold one, two, or four bytes.");
 273     }
 274   }
 275 }