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 */ 25static int seepair(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 47int 48fitpair(char *pag, int need) 49{ 50 int n; 51 int off; 52 int free; 53 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 64void 65putpair(char *pag, datum key, datum val) 66{ 67 int n; 68 int off; 69 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 90datum 91getpair(char *pag, datum key) 92{ 93 int i; 94 int n; 95 datum val; 96 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 109int 110exipair(char *pag, datum key) 111{ 112 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 121int 122duppair(char *pag, datum key) 123{ 124 short *ino = (short *) pag; 125 return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0; 126} 127#endif 128 129datum 130getnkey(char *pag, int num) 131{ 132 datum key; 133 int off; 134 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 148int 149delpair(char *pag, datum key) 150{ 151 int n; 152 int i; 153 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 int m; 169 char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]); 170 char *src = pag + ino[i + 1]; 171 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 int loop = (m + 8 - 1) >> 3; 183 184 switch (m & (8 - 1)) { 185 case 0: do { 186 MOVB; /* FALLTHROUGH */ case 7: MOVB; /* FALLTHROUGH */ 187 case 6: MOVB; /* FALLTHROUGH */ case 5: MOVB; /* FALLTHROUGH */ 188 case 4: MOVB; /* FALLTHROUGH */ case 3: MOVB; /* FALLTHROUGH */ 189 case 2: MOVB; /* FALLTHROUGH */ case 1: MOVB; 190 } while (--loop); 191 } 192 } 193#else 194 dst -= m; 195 src -= m; 196 memmove(dst, src, m); 197#endif 198/* 199 * adjust offset index up 200 */ 201 while (i < n - 1) { 202 ino[i] = ino[i + 2] + zoo; 203 i++; 204 } 205 } 206 ino[0] -= 2; 207 return 1; 208} 209 210/* 211 * search for the key in the page. 212 * return offset index in the range 0 < i < n. 213 * return 0 if not found. 214 */ 215static int 216seepair(char *pag, int n, const char *key, int siz) 217{ 218 int i; 219 int off = PBLKSIZ; 220 short *ino = (short *) pag; 221 222 for (i = 1; i < n; i += 2) { 223 if (siz == off - ino[i] && 224 memEQ(key, pag + ino[i], siz)) 225 return i; 226 off = ino[i + 1]; 227 } 228 return 0; 229} 230 231void 232splpage(char *pag, char *New, long int sbit) 233{ 234 datum key; 235 datum val; 236 237 int n; 238 int off = PBLKSIZ; 239 char cur[PBLKSIZ]; 240 short *ino = (short *) cur; 241 242 (void) memcpy(cur, pag, PBLKSIZ); 243 (void) memset(pag, 0, PBLKSIZ); 244 (void) memset(New, 0, PBLKSIZ); 245 246 n = ino[0]; 247 for (ino++; n > 0; ino += 2) { 248 key.dptr = cur + ino[0]; 249 key.dsize = off - ino[0]; 250 val.dptr = cur + ino[1]; 251 val.dsize = ino[0] - ino[1]; 252/* 253 * select the page pointer (by looking at sbit) and insert 254 */ 255 (void) putpair((exhash(key) & sbit) ? New : pag, key, val); 256 257 off = ino[1]; 258 n -= 2; 259 } 260 261 debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 262 ((short *) New)[0] / 2, 263 ((short *) pag)[0] / 2)); 264} 265 266/* 267 * check page sanity: 268 * number of entries should be something 269 * reasonable, and all offsets in the index should be in order. 270 * this could be made more rigorous. 271 */ 272/* 273 Layout of a page is: 274 Top of block: 275 number of keys/values (short) 276 Array of (number of keys/values) offsets, alternating between key offsets 277 and value offsets (shorts) 278 End of block: 279 - value/key data, last key ends at end of block (bytes) 280 281 So: 282 N key0off val0off key1off val1off ... val1 key1 val0 key0 283 284 Be careful to note N is the number of offsets, *not* the number of keys. 285 */ 286int 287chkpage(char *pag) 288{ 289 int n; 290 int off; 291 short *ino = (short *) pag; 292 293 if ((n = ino[0]) < 0 || n > (int)(PBLKSIZ / sizeof(short))) 294 return 0; 295 296 if (n > 0) { 297 off = PBLKSIZ; 298 for (ino++; n > 0; ino += 2) { 299 if (ino[0] > off || ino[1] > off || 300 ino[1] > ino[0] || ino[1] <= 0) 301 return 0; 302 off = ino[1]; 303 n -= 2; 304 } 305 /* there must be an even number of offsets */ 306 if (n != 0) 307 return 0; 308 /* check the key/value offsets don't overlap the key/value data */ 309 if ((char *)ino > pag + off) 310 return 0; 311 } 312 return 1; 313} 314