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