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