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