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 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 64 void 65 putpair(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 90 datum 91 getpair(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 109 int 110 exipair(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 121 int 122 duppair(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 129 datum 130 getnkey(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 148 int 149 delpair(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; 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, int n, const char *key, int siz) 222 { 223 int i; 224 int off = PBLKSIZ; 225 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 int n; 243 int off = PBLKSIZ; 244 char cur[PBLKSIZ]; 245 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 int n; 281 int off; 282 short *ino = (short *) pag; 283 284 if ((n = ino[0]) < 0 || n > (int)(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 } 299