ext/dbm/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(pag, need)
  48 char *pag;
  49 int need;
  50 {
  51         register int n;
  52         register int off;
  53         register int free;
  54         register short *ino = (short *) pag;
  55
  56         off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
  57         free = off - (n + 1) * sizeof(short);
  58         need += 2 * sizeof(short);
  59
  60         debug(("free %d need %d\n", free, need));
  61
  62         return need <= free;
  63 }
  64
  65 void
  66 putpair(pag, key, val)
  67 char *pag;
  68 datum key;
  69 datum val;
  70 {
  71         register int n;
  72         register int off;
  73         register short *ino = (short *) pag;
  74
  75         off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
  76 /*
  77  * enter the key first
  78  */
  79         off -= key.dsize;
  80         (void) memcpy(pag + off, key.dptr, key.dsize);
  81         ino[n + 1] = off;
  82 /*
  83  * now the data
  84  */
  85         off -= val.dsize;
  86         (void) memcpy(pag + off, val.dptr, val.dsize);
  87         ino[n + 2] = off;
  88 /*
  89  * adjust item count
  90  */
  91         ino[0] += 2;
  92 }
  93
  94 datum
  95 getpair(pag, key)
  96 char *pag;
  97 datum key;
  98 {
  99         register int i;
 100         register int n;
 101         datum val;
 102         register short *ino = (short *) pag;
 103
 104         if ((n = ino[0]) == 0)
 105                 return nullitem;
 106
 107         if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
 108                 return nullitem;
 109
 110         val.dptr = pag + ino[i + 1];
 111         val.dsize = ino[i] - ino[i + 1];
 112         return val;
 113 }
 114
 115 #ifdef SEEDUPS
 116 int
 117 duppair(pag, key)
 118 char *pag;
 119 datum key;
 120 {
 121         register short *ino = (short *) pag;
 122         return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
 123 }
 124 #endif
 125
 126 datum
 127 getnkey(pag, num)
 128 char *pag;
 129 int num;
 130 {
 131         datum key;
 132         register int off;
 133         register short *ino = (short *) pag;
 134
 135         num = num * 2 - 1;
 136         if (ino[0] == 0 || num > ino[0])
 137                 return nullitem;
 138
 139         off = (num > 1) ? ino[num - 1] : PBLKSIZ;
 140
 141         key.dptr = pag + ino[num];
 142         key.dsize = off - ino[num];
 143
 144         return key;
 145 }
 146
 147 int
 148 delpair(pag, key)
 149 char *pag;
 150 datum key;
 151 {
 152         register int n;
 153         register int i;
 154         register short *ino = (short *) pag;
 155
 156         if ((n = ino[0]) == 0)
 157                 return 0;
 158
 159         if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
 160                 return 0;
 161 /*
 162  * found the key. if it is the last entry
 163  * [i.e. i == n - 1] we just adjust the entry count.
 164  * hard case: move all data down onto the deleted pair,
 165  * shift offsets onto deleted offsets, and adjust them.
 166  * [note: 0 < i < n]
 167  */
 168         if (i < n - 1) {
 169                 register int m;
 170                 register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
 171                 register char *src = pag + ino[i + 1];
 172                 register int   zoo = dst - src;
 173
 174                 debug(("free-up %d ", zoo));
 175 /*
 176  * shift data/keys down
 177  */
 178                 m = ino[i + 1] - ino[n];
 179 #ifdef DUFF
 180 #define MOVB    *--dst = *--src
 181
 182                 if (m > 0) {
 183                         register int loop = (m + 8 - 1) >> 3;
 184
 185                         switch (m & (8 - 1)) {
 186                         case 0: do {
 187                                 MOVB;   case 7: MOVB;
 188                         case 6: MOVB;   case 5: MOVB;
 189                         case 4: MOVB;   case 3: MOVB;
 190                         case 2: MOVB;   case 1: MOVB;
 191                                 } while (--loop);
 192                         }
 193                 }
 194 #else
 195 #ifdef HAS_MEMMOVE
 196                 memmove(dst, src, m);
 197 #else
 198                 while (m--)
 199                         *--dst = *--src;
 200 #endif
 201 #endif
 202 /*
 203  * adjust offset index up
 204  */
 205                 while (i < n - 1) {
 206                         ino[i] = ino[i + 2] + zoo;
 207                         i++;
 208                 }
 209         }
 210         ino[0] -= 2;
 211         return 1;
 212 }
 213
 214 /*
 215  * search for the key in the page.
 216  * return offset index in the range 0 < i < n.
 217  * return 0 if not found.
 218  */
 219 static int
 220 seepair(pag, n, key, siz)
 221 char *pag;
 222 register int n;
 223 register char *key;
 224 register int siz;
 225 {
 226         register int i;
 227         register int off = PBLKSIZ;
 228         register short *ino = (short *) pag;
 229
 230         for (i = 1; i < n; i += 2) {
 231                 if (siz == off - ino[i] &&
 232                     memcmp(key, pag + ino[i], siz) == 0)
 233                         return i;
 234                 off = ino[i + 1];
 235         }
 236         return 0;
 237 }
 238
 239 void
 240 splpage(pag, new, sbit)
 241 char *pag;
 242 char *new;
 243 long sbit;
 244 {
 245         datum key;
 246         datum val;
 247
 248         register int n;
 249         register int off = PBLKSIZ;
 250         char cur[PBLKSIZ];
 251         register short *ino = (short *) cur;
 252
 253         (void) memcpy(cur, pag, PBLKSIZ);
 254         (void) memset(pag, 0, PBLKSIZ);
 255         (void) memset(new, 0, PBLKSIZ);
 256
 257         n = ino[0];
 258         for (ino++; n > 0; ino += 2) {
 259                 key.dptr = cur + ino[0];
 260                 key.dsize = off - ino[0];
 261                 val.dptr = cur + ino[1];
 262                 val.dsize = ino[0] - ino[1];
 263 /*
 264  * select the page pointer (by looking at sbit) and insert
 265  */
 266                 (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
 267
 268                 off = ino[1];
 269                 n -= 2;
 270         }
 271
 272         debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
 273                ((short *) new)[0] / 2,
 274                ((short *) pag)[0] / 2));
 275 }
 276
 277 /*
 278  * check page sanity:
 279  * number of entries should be something
 280  * reasonable, and all offsets in the index should be in order.
 281  * this could be made more rigorous.
 282  */
 283 int
 284 chkpage(pag)
 285 char *pag;
 286 {
 287         register int n;
 288         register int off;
 289         register short *ino = (short *) pag;
 290
 291         if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
 292                 return 0;
 293
 294         if (n > 0) {
 295                 off = PBLKSIZ;
 296                 for (ino++; n > 0; ino += 2) {
 297                         if (ino[0] > off || ino[1] > off ||
 298                             ino[1] > ino[0])
 299                                 return 0;
 300                         off = ino[1];
 301                         n -= 2;
 302                 }
 303         }
 304         return 1;
 305 }