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