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