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