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