1 #ifndef lint 2 static char sccsid[] = "@(#)ndbm.c 4.4 (Berkeley) 09/05/84"; 3 #endif 4 5 #include <sys/types.h> 6 #include <sys/stat.h> 7 #include <sys/file.h> 8 #include <stdio.h> 9 #include <errno.h> 10 #include <ndbm.h> 11 12 #define BYTESIZ 8 13 14 static datum makdatum(); 15 static long hashinc(); 16 static long dcalchash(); 17 extern int errno; 18 19 DBM * 20 dbm_open(file, flags, mode) 21 char *file; 22 int flags, mode; 23 { 24 struct stat statb; 25 register DBM *db; 26 27 if ((db = (DBM *)malloc(sizeof *db)) == 0) { 28 errno = ENOMEM; 29 return ((DBM *)0); 30 } 31 db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0; 32 if ((flags & 03) == O_WRONLY) 33 flags = (flags & ~03) | O_RDWR; 34 strcpy(db->dbm_pagbuf, file); 35 strcat(db->dbm_pagbuf, ".pag"); 36 db->dbm_pagf = open(db->dbm_pagbuf, flags, mode); 37 if (db->dbm_pagf < 0) 38 goto bad; 39 strcpy(db->dbm_pagbuf, file); 40 strcat(db->dbm_pagbuf, ".dir"); 41 db->dbm_dirf = open(db->dbm_pagbuf, flags, mode); 42 if (db->dbm_dirf < 0) 43 goto bad1; 44 fstat(db->dbm_dirf, &statb); 45 db->dbm_maxbno = statb.st_size*BYTESIZ-1; 46 db->dbm_pagbno = db->dbm_dirbno = -1; 47 return (db); 48 bad1: 49 (void) close(db->dbm_pagf); 50 bad: 51 free((char *)db); 52 return ((DBM *)0); 53 } 54 55 void 56 dbm_close(db) 57 DBM *db; 58 { 59 60 (void) close(db->dbm_dirf); 61 (void) close(db->dbm_pagf); 62 free((char *)db); 63 } 64 65 long 66 dbm_forder(db, key) 67 register DBM *db; 68 datum key; 69 { 70 long hash; 71 72 hash = dcalchash(key); 73 for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) { 74 db->dbm_blkno = hash & db->dbm_hmask; 75 db->dbm_bitno = db->dbm_blkno + db->dbm_hmask; 76 if (getbit(db) == 0) 77 break; 78 } 79 return (db->dbm_blkno); 80 } 81 82 datum 83 dbm_fetch(db, key) 84 register DBM *db; 85 datum key; 86 { 87 register i; 88 datum item; 89 90 if (dbm_error(db)) 91 goto err; 92 dbm_access(db, dcalchash(key)); 93 if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) { 94 item = makdatum(db->dbm_pagbuf, i+1); 95 if (item.dptr != NULL) 96 return (item); 97 } 98 err: 99 item.dptr = NULL; 100 item.dsize = 0; 101 return (item); 102 } 103 104 dbm_delete(db, key) 105 register DBM *db; 106 datum key; 107 { 108 register i; 109 datum item; 110 111 if (dbm_error(db)) 112 return (-1); 113 if (dbm_rdonly(db)) { 114 errno = EPERM; 115 return (-1); 116 } 117 dbm_access(db, dcalchash(key)); 118 if ((i = finddatum(db->dbm_pagbuf, key)) < 0) 119 return (-1); 120 if (!delitem(db->dbm_pagbuf, i)) 121 goto err; 122 db->dbm_pagbno = db->dbm_blkno; 123 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET); 124 if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) { 125 err: 126 db->dbm_flags |= _DBM_IOERR; 127 return (-1); 128 } 129 return (0); 130 } 131 132 dbm_store(db, key, dat, replace) 133 register DBM *db; 134 datum key, dat; 135 int replace; 136 { 137 register i; 138 datum item, item1; 139 char ovfbuf[PBLKSIZ]; 140 141 if (dbm_error(db)) 142 return (-1); 143 if (dbm_rdonly(db)) { 144 errno = EPERM; 145 return (-1); 146 } 147 loop: 148 dbm_access(db, dcalchash(key)); 149 if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) { 150 if (!replace) 151 return (1); 152 if (!delitem(db->dbm_pagbuf, i)) { 153 db->dbm_flags |= _DBM_IOERR; 154 return (-1); 155 } 156 } 157 if (!additem(db->dbm_pagbuf, key, dat)) 158 goto split; 159 db->dbm_pagbno = db->dbm_blkno; 160 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET); 161 if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) { 162 db->dbm_flags |= _DBM_IOERR; 163 return (-1); 164 } 165 return (0); 166 167 split: 168 if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) { 169 db->dbm_flags |= _DBM_IOERR; 170 errno = ENOSPC; 171 return (-1); 172 } 173 bzero(ovfbuf, PBLKSIZ); 174 for (i=0;;) { 175 item = makdatum(db->dbm_pagbuf, i); 176 if (item.dptr == NULL) 177 break; 178 if (dcalchash(item) & (db->dbm_hmask+1)) { 179 item1 = makdatum(db->dbm_pagbuf, i+1); 180 if (item1.dptr == NULL) { 181 fprintf(stderr, "ndbm: split not paired\n"); 182 db->dbm_flags |= _DBM_IOERR; 183 break; 184 } 185 if (!additem(ovfbuf, item, item1) || 186 !delitem(db->dbm_pagbuf, i)) { 187 db->dbm_flags |= _DBM_IOERR; 188 return (-1); 189 } 190 continue; 191 } 192 i += 2; 193 } 194 db->dbm_pagbno = db->dbm_blkno; 195 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET); 196 if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) { 197 db->dbm_flags |= _DBM_IOERR; 198 return (-1); 199 } 200 (void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET); 201 if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) { 202 db->dbm_flags |= _DBM_IOERR; 203 return (-1); 204 } 205 setbit(db); 206 goto loop; 207 } 208 209 datum 210 dbm_firstkey(db) 211 DBM *db; 212 { 213 214 db->dbm_blkptr = 0L; 215 db->dbm_keyptr = 0; 216 return (dbm_nextkey(db)); 217 } 218 219 datum 220 dbm_nextkey(db) 221 register DBM *db; 222 { 223 struct stat statb; 224 datum item; 225 226 if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0) 227 goto err; 228 statb.st_size /= PBLKSIZ; 229 for (;;) { 230 if (db->dbm_blkptr != db->dbm_pagbno) { 231 db->dbm_pagbno = db->dbm_blkptr; 232 (void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET); 233 if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) 234 bzero(db->dbm_pagbuf, PBLKSIZ); 235 #ifdef DEBUG 236 else if (chkblk(db->dbm_pagbuf) < 0) 237 db->dbm_flags |= _DBM_IOERR; 238 #endif 239 } 240 if (((short *)db->dbm_pagbuf)[0] != 0) { 241 item = makdatum(db->dbm_pagbuf, db->dbm_keyptr); 242 if (item.dptr != NULL) { 243 db->dbm_keyptr += 2; 244 return (item); 245 } 246 db->dbm_keyptr = 0; 247 } 248 if (++db->dbm_blkptr >= statb.st_size) 249 break; 250 } 251 err: 252 item.dptr = NULL; 253 item.dsize = 0; 254 return (item); 255 } 256 257 static 258 dbm_access(db, hash) 259 register DBM *db; 260 long hash; 261 { 262 263 for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) { 264 db->dbm_blkno = hash & db->dbm_hmask; 265 db->dbm_bitno = db->dbm_blkno + db->dbm_hmask; 266 if (getbit(db) == 0) 267 break; 268 } 269 if (db->dbm_blkno != db->dbm_pagbno) { 270 db->dbm_pagbno = db->dbm_blkno; 271 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET); 272 if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) 273 bzero(db->dbm_pagbuf, PBLKSIZ); 274 #ifdef DEBUG 275 else if (chkblk(db->dbm_pagbuf) < 0) 276 db->dbm_flags |= _DBM_IOERR; 277 #endif 278 } 279 } 280 281 static 282 getbit(db) 283 register DBM *db; 284 { 285 long bn; 286 register b, i, n; 287 288 289 if (db->dbm_bitno > db->dbm_maxbno) 290 return (0); 291 n = db->dbm_bitno % BYTESIZ; 292 bn = db->dbm_bitno / BYTESIZ; 293 i = bn % DBLKSIZ; 294 b = bn / DBLKSIZ; 295 if (b != db->dbm_dirbno) { 296 db->dbm_dirbno = b; 297 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET); 298 if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ) 299 bzero(db->dbm_dirbuf, DBLKSIZ); 300 } 301 return (db->dbm_dirbuf[i] & (1<<n)); 302 } 303 304 static 305 setbit(db) 306 register DBM *db; 307 { 308 long bn; 309 register i, n, b; 310 311 if (db->dbm_bitno > db->dbm_maxbno) 312 db->dbm_maxbno = db->dbm_bitno; 313 n = db->dbm_bitno % BYTESIZ; 314 bn = db->dbm_bitno / BYTESIZ; 315 i = bn % DBLKSIZ; 316 b = bn / DBLKSIZ; 317 if (b != db->dbm_dirbno) { 318 db->dbm_dirbno = b; 319 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET); 320 if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ) 321 bzero(db->dbm_dirbuf, DBLKSIZ); 322 } 323 db->dbm_dirbuf[i] |= 1<<n; 324 db->dbm_dirbno = b; 325 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET); 326 if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ) 327 db->dbm_flags |= _DBM_IOERR; 328 } 329 330 static datum 331 makdatum(buf, n) 332 char buf[PBLKSIZ]; 333 { 334 register short *sp; 335 register t; 336 datum item; 337 338 sp = (short *)buf; 339 if ((unsigned)n >= sp[0]) { 340 item.dptr = NULL; 341 item.dsize = 0; 342 return (item); 343 } 344 t = PBLKSIZ; 345 if (n > 0) 346 t = sp[n]; 347 item.dptr = buf+sp[n+1]; 348 item.dsize = t - sp[n+1]; 349 return (item); 350 } 351 352 static 353 finddatum(buf, item) 354 char buf[PBLKSIZ]; 355 datum item; 356 { 357 register short *sp; 358 register int i, n, j; 359 360 sp = (short *)buf; 361 n = PBLKSIZ; 362 for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) { 363 n -= sp[i+1]; 364 if (n != item.dsize) 365 continue; 366 if (n == 0 || bcmp(&buf[sp[i+1]], item.dptr, n) == 0) 367 return (i); 368 } 369 return (-1); 370 } 371 372 static int hitab[16] 373 /* ken's 374 { 375 055,043,036,054,063,014,004,005, 376 010,064,077,000,035,027,025,071, 377 }; 378 */ 379 = { 61, 57, 53, 49, 45, 41, 37, 33, 380 29, 25, 21, 17, 13, 9, 5, 1, 381 }; 382 static long hltab[64] 383 = { 384 06100151277L,06106161736L,06452611562L,05001724107L, 385 02614772546L,04120731531L,04665262210L,07347467531L, 386 06735253126L,06042345173L,03072226605L,01464164730L, 387 03247435524L,07652510057L,01546775256L,05714532133L, 388 06173260402L,07517101630L,02431460343L,01743245566L, 389 00261675137L,02433103631L,03421772437L,04447707466L, 390 04435620103L,03757017115L,03641531772L,06767633246L, 391 02673230344L,00260612216L,04133454451L,00615531516L, 392 06137717526L,02574116560L,02304023373L,07061702261L, 393 05153031405L,05322056705L,07401116734L,06552375715L, 394 06165233473L,05311063631L,01212221723L,01052267235L, 395 06000615237L,01075222665L,06330216006L,04402355630L, 396 01451177262L,02000133436L,06025467062L,07121076461L, 397 03123433522L,01010635225L,01716177066L,05161746527L, 398 01736635071L,06243505026L,03637211610L,01756474365L, 399 04723077174L,03642763134L,05750130273L,03655541561L, 400 }; 401 402 static long 403 hashinc(db, hash) 404 register DBM *db; 405 long hash; 406 { 407 long bit; 408 409 hash &= db->dbm_hmask; 410 bit = db->dbm_hmask+1; 411 for (;;) { 412 bit >>= 1; 413 if (bit == 0) 414 return (0L); 415 if ((hash & bit) == 0) 416 return (hash | bit); 417 hash &= ~bit; 418 } 419 } 420 421 static long 422 dcalchash(item) 423 datum item; 424 { 425 register int s, c, j; 426 register char *cp; 427 register long hashl; 428 register int hashi; 429 430 hashl = 0; 431 hashi = 0; 432 for (cp = item.dptr, s=item.dsize; --s >= 0; ) { 433 c = *cp++; 434 for (j=0; j<BYTESIZ; j+=4) { 435 hashi += hitab[c&017]; 436 hashl += hltab[hashi&63]; 437 c >>= 4; 438 } 439 } 440 return (hashl); 441 } 442 443 /* 444 * Delete pairs of items (n & n+1). 445 */ 446 static 447 delitem(buf, n) 448 char buf[PBLKSIZ]; 449 { 450 register short *sp, *sp1; 451 register i1, i2; 452 453 sp = (short *)buf; 454 i2 = sp[0]; 455 if ((unsigned)n >= i2 || (n & 1)) 456 return (0); 457 if (n == i2-2) { 458 sp[0] -= 2; 459 return (1); 460 } 461 i1 = PBLKSIZ; 462 if (n > 0) 463 i1 = sp[n]; 464 i1 -= sp[n+2]; 465 if (i1 > 0) { 466 i2 = sp[i2]; 467 bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2); 468 } 469 sp[0] -= 2; 470 for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++) 471 sp[0] = sp[2] + i1; 472 return (1); 473 } 474 475 /* 476 * Add pairs of items (item & item1). 477 */ 478 static 479 additem(buf, item, item1) 480 char buf[PBLKSIZ]; 481 datum item, item1; 482 { 483 register short *sp; 484 register i1, i2; 485 486 sp = (short *)buf; 487 i1 = PBLKSIZ; 488 i2 = sp[0]; 489 if (i2 > 0) 490 i1 = sp[i2]; 491 i1 -= item.dsize + item1.dsize; 492 if (i1 <= (i2+3) * sizeof(short)) 493 return (0); 494 sp[0] += 2; 495 sp[++i2] = i1 + item1.dsize; 496 bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize); 497 sp[++i2] = i1; 498 bcopy(item1.dptr, &buf[i1], item1.dsize); 499 return (1); 500 } 501 502 #ifdef DEBUG 503 static 504 chkblk(buf) 505 char buf[PBLKSIZ]; 506 { 507 register short *sp; 508 register t, i; 509 510 sp = (short *)buf; 511 t = PBLKSIZ; 512 for (i=0; i<sp[0]; i++) { 513 if (sp[i+1] > t) 514 return (-1); 515 t = sp[i+1]; 516 } 517 if (t < (sp[0]+1)*sizeof(short)) 518 return (-1); 519 return (0); 520 } 521 #endif 522