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