ext/SDBM_File/sdbm/pair.c

   1 /*
   2  * sdbm - ndbm work-alike hashed database library
   3  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
   4  * author: oz@nexus.yorku.ca
   5  * status: public domain.
   6  *
   7  * page-level routines
   8  */
   9
  10 #ifndef lint
  11 static char rcsid[] = "$Id: pair.c,v 1.10 90/12/13 13:00:35 oz Exp $";
  12 #endif
  13
  14 #include "config.h"
  15 #include "sdbm.h"
  16 #include "tune.h"
  17 #include "pair.h"
  18
  19 #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
  20
  21 /*
  22  * forward
  23  */
  24 static int seepair proto((char *, int, char *, int));
  25
  26 /*
  27  * page format:
  28  *      +------------------------------+
  29  * ino  | n | keyoff | datoff | keyoff |
  30  *      +------------+--------+--------+
  31  *      | datoff | - - - ---->         |
  32  *      +--------+---------------------+
  33  *      |        F R E E A R E A       |
  34  *      +--------------+---------------+
  35  *      |  <---- - - - | data          |
  36  *      +--------+-----+----+----------+
  37  *      |  key   | data     | key      |
  38  *      +--------+----------+----------+
  39  *
  40  * calculating the offsets for free area:  if the number
  41  * of entries (ino[0]) is zero, the offset to the END of
  42  * the free area is the block size. Otherwise, it is the
  43  * nth (ino[ino[0]]) entry's offset.
  44  */
  45
  46 int
  47 fitpair(char *pag, int need)
  48 {
  49         register int n;
  50         register int off;
  51         register int free;
  52         register short *ino = (short *) pag;
  53
  54         off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
  55         free = off - (n + 1) * sizeof(short);
  56         need += 2 * sizeof(short);
  57
  58         debug(("free %d need %d\n", free, need));
  59
  60         return need <= free;
  61 }
  62
  63 void
  64 putpair(char *pag, datum key, datum val)
  65 {
  66         register int n;
  67         register int off;
  68         register short *ino = (short *) pag;
  69
  70         off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
  71 /*
  72  * enter the key first
  73  */
  74         off -= key.dsize;
  75         (void) memcpy(pag + off, key.dptr, key.dsize);
  76         ino[n + 1] = off;
  77 /*
  78  * now the data
  79  */
  80         off -= val.dsize;
  81         (void) memcpy(pag + off, val.dptr, val.dsize);
  82         ino[n + 2] = off;
  83 /*
  84  * adjust item count
  85  */
  86         ino[0] += 2;
  87 }
  88
  89 datum
  90 getpair(char *pag, datum key)
  91 {
  92         register int i;
  93         register int n;
  94         datum val;
  95         register short *ino = (short *) pag;
  96
  97         if ((n = ino[0]) == 0)
  98                 return nullitem;
  99
 100         if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
 101                 return nullitem;
 102
 103         val.dptr = pag + ino[i + 1];
 104         val.dsize = ino[i] - ino[i + 1];
 105         return val;
 106 }
 107
 108 #ifdef SEEDUPS
 109 int
 110 duppair(char *pag, datum key)
 111 {
 112         register short *ino = (short *) pag;
 113         return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
 114 }
 115 #endif
 116
 117 datum
 118 getnkey(char *pag, int num)
 119 {
 120         datum key;
 121         register int off;
 122         register short *ino = (short *) pag;
 123
 124         num = num * 2 - 1;
 125         if (ino[0] == 0 || num > ino[0])
 126                 return nullitem;
 127
 128         off = (num > 1) ? ino[num - 1] : PBLKSIZ;
 129
 130         key.dptr = pag + ino[num];
 131         key.dsize = off - ino[num];
 132
 133         return key;
 134 }
 135
 136 int
 137 delpair(char *pag, datum key)
 138 {
 139         register int n;
 140         register int i;
 141         register short *ino = (short *) pag;
 142
 143         if ((n = ino[0]) == 0)
 144                 return 0;
 145
 146         if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
 147                 return 0;
 148 /*
 149  * found the key. if it is the last entry
 150  * [i.e. i == n - 1] we just adjust the entry count.
 151  * hard case: move all data down onto the deleted pair,
 152  * shift offsets onto deleted offsets, and adjust them.
 153  * [note: 0 < i < n]
 154  */
 155         if (i < n - 1) {
 156                 register int m;
 157                 register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
 158                 register char *src = pag + ino[i + 1];
 159                 register int   zoo = dst - src;
 160
 161                 debug(("free-up %d ", zoo));
 162 /*
 163  * shift data/keys down
 164  */
 165                 m = ino[i + 1] - ino[n];
 166 #ifdef DUFF
 167 #define MOVB    *--dst = *--src
 168
 169                 if (m > 0) {
 170                         register int loop = (m + 8 - 1) >> 3;
 171
 172                         switch (m & (8 - 1)) {
 173                         case 0: do {
 174                                 MOVB;   case 7: MOVB;
 175                         case 6: MOVB;   case 5: MOVB;
 176                         case 4: MOVB;   case 3: MOVB;
 177                         case 2: MOVB;   case 1: MOVB;
 178                                 } while (--loop);
 179                         }
 180                 }
 181 #else
 182 #ifdef HAS_MEMMOVE
 183                 dst -= m;
 184                 src -= m;
 185                 memmove(dst, src, m);
 186 #else
 187                 while (m--)
 188                         *--dst = *--src;
 189 #endif
 190 #endif
 191 /*
 192  * adjust offset index up
 193  */
 194                 while (i < n - 1) {
 195                         ino[i] = ino[i + 2] + zoo;
 196                         i++;
 197                 }
 198         }
 199         ino[0] -= 2;
 200         return 1;
 201 }
 202
 203 /*
 204  * search for the key in the page.
 205  * return offset index in the range 0 < i < n.
 206  * return 0 if not found.
 207  */
 208 static int
 209 seepair(char *pag, register int n, register char *key, register int siz)
 210 {
 211         register int i;
 212         register int off = PBLKSIZ;
 213         register short *ino = (short *) pag;
 214
 215         for (i = 1; i < n; i += 2) {
 216                 if (siz == off - ino[i] &&
 217                     memEQ(key, pag + ino[i], siz))
 218                         return i;
 219                 off = ino[i + 1];
 220         }
 221         return 0;
 222 }
 223
 224 void
 225 splpage(char *pag, char *New, long int sbit)
 226 {
 227         datum key;
 228         datum val;
 229
 230         register int n;
 231         register int off = PBLKSIZ;
 232         char cur[PBLKSIZ];
 233         register short *ino = (short *) cur;
 234
 235         (void) memcpy(cur, pag, PBLKSIZ);
 236         (void) memset(pag, 0, PBLKSIZ);
 237         (void) memset(New, 0, PBLKSIZ);
 238
 239         n = ino[0];
 240         for (ino++; n > 0; ino += 2) {
 241                 key.dptr = cur + ino[0];
 242                 key.dsize = off - ino[0];
 243                 val.dptr = cur + ino[1];
 244                 val.dsize = ino[0] - ino[1];
 245 /*
 246  * select the page pointer (by looking at sbit) and insert
 247  */
 248                 (void) putpair((exhash(key) & sbit) ? New : pag, key, val);
 249
 250                 off = ino[1];
 251                 n -= 2;
 252         }
 253
 254         debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
 255                ((short *) New)[0] / 2,
 256                ((short *) pag)[0] / 2));
 257 }
 258
 259 /*
 260  * check page sanity:
 261  * number of entries should be something
 262  * reasonable, and all offsets in the index should be in order.
 263  * this could be made more rigorous.
 264  */
 265 int
 266 chkpage(char *pag)
 267 {
 268         register int n;
 269         register int off;
 270         register short *ino = (short *) pag;
 271
 272         if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
 273                 return 0;
 274
 275         if (n > 0) {
 276                 off = PBLKSIZ;
 277                 for (ino++; n > 0; ino += 2) {
 278                         if (ino[0] > off || ino[1] > off ||
 279                             ino[1] > ino[0])
 280                                 return 0;
 281                         off = ino[1];
 282                         n -= 2;
 283                 }
 284         }
 285         return 1;
 286 }