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