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