1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2002 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 28 /* All Rights Reserved */ 29 30 /* 31 * Portions of this source code were derived from Berkeley 4.3 BSD 32 * under license from the Regents of the University of California. 33 */ 34 35 #pragma ident "%Z%%M% %I% %E% SMI" 36 37 /*LINTLIBRARY*/ 38 39 #include <sys/types.h> 40 #include <stdio.h> 41 #include <unistd.h> 42 #include <stdlib.h> 43 #include <strings.h> 44 #include <malloc.h> 45 #include <sys/stat.h> 46 #include <fcntl.h> 47 #include <dbm.h> 48 #include <errno.h> 49 50 /* forward declarations */ 51 /* could be all static if not were for older *.a releases */ 52 void chkblk(char buf[PBLKSIZ]); 53 void delitem(char buf[PBLKSIZ], int n); 54 void dbm_access(long hash); 55 int getbit(void); 56 int setbit(void); 57 int additem(char buf[PBLKSIZ], datum item); 58 int cmpdatum(datum d1, datum d2); 59 60 int 61 dbminit(char *file) 62 { 63 struct stat64 statb; 64 65 dbrdonly = 0; 66 if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) || 67 strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) { 68 /* 69 * file.pag does not fit into pagbuf. 70 * fails with ENAMETOOLONG. 71 */ 72 errno = ENAMETOOLONG; 73 return (-1); 74 } 75 pagf = open(pagbuf, 2); 76 if (pagf < 0) { 77 pagf = open(pagbuf, 0); 78 dbrdonly = 1; 79 } 80 81 /* 82 * We know this won't overflow so it is safe to ignore the 83 * return value; we use strl* to prevent false hits in 84 * code sweeps. 85 */ 86 (void) strlcpy(pagbuf, file, sizeof (pagbuf)); 87 (void) strlcat(pagbuf, ".dir", sizeof (pagbuf)); 88 dirf = open(pagbuf, 2); 89 if (dirf < 0) { 90 dirf = open(pagbuf, 0); 91 dbrdonly = 1; 92 } 93 if (pagf < 0 || dirf < 0) { 94 (void) printf("cannot open database %s\n", file); 95 return (-1); 96 } 97 /* Guards against large inodes */ 98 (void) fstat64(dirf, &statb); 99 maxbno = (off_t)statb.st_size * BYTESIZ - 1; 100 return (0); 101 } 102 103 static long oldb1 = -1L; 104 static long oldb2 = -1L; 105 106 /* Avoid using cached data for subsequent accesses. */ 107 int 108 dbmflush(void) 109 { 110 oldb1 = -1L; 111 oldb2 = -1L; 112 return (0); 113 } 114 115 /* Clean up after ourself. */ 116 int 117 dbmclose(void) 118 { 119 (void) close(pagf); 120 (void) close(dirf); 121 bitno = 0; 122 maxbno = 0; 123 blkno = 0; 124 hmask = 0; 125 oldb1 = -1L; 126 oldb2 = -1L; 127 return (0); 128 } 129 130 long 131 forder(datum key) 132 { 133 long hash; 134 135 hash = calchash(key); 136 for (hmask = 0; ; hmask = (hmask<<1)+1) { 137 blkno = hash & hmask; 138 bitno = blkno + hmask; 139 if (getbit() == 0) 140 break; 141 } 142 return (blkno); 143 } 144 145 datum 146 fetch(datum key) 147 { 148 int i; 149 datum item; 150 151 dbm_access(calchash(key)); 152 for (i = 0; ; i += 2) { 153 item = makdatum(pagbuf, i); 154 if (item.dptr == NULL) 155 return (item); 156 if (cmpdatum(key, item) == 0) { 157 item = makdatum(pagbuf, i+1); 158 if (item.dptr == NULL) 159 (void) printf("items not in pairs\n"); 160 return (item); 161 } 162 } 163 } 164 165 int 166 delete(datum key) 167 { 168 int i; 169 datum item; 170 171 if (dbrdonly) 172 return (-1); 173 dbm_access(calchash(key)); 174 for (i = 0; ; i += 2) { 175 item = makdatum(pagbuf, i); 176 if (item.dptr == NULL) 177 return (-1); 178 if (cmpdatum(key, item) == 0) { 179 delitem(pagbuf, i); 180 delitem(pagbuf, i); 181 break; 182 } 183 } 184 (void) lseek(pagf, blkno*PBLKSIZ, 0); 185 (void) write(pagf, pagbuf, PBLKSIZ); 186 return (0); 187 } 188 189 int 190 store(datum key, datum dat) 191 { 192 int i; 193 datum item; 194 char ovfbuf[PBLKSIZ]; 195 datum Sentry; 196 int Oneflag; 197 198 Sentry.dsize = 0; 199 Sentry.dptr = NULL; 200 201 if (dbrdonly) 202 return (-1); 203 loop: 204 dbm_access(calchash(key)); 205 for (i = 0; ; i += 2) { 206 item = makdatum(pagbuf, i); 207 if (item.dptr == NULL) 208 break; 209 if (cmpdatum(key, item) == 0) { 210 delitem(pagbuf, i); 211 delitem(pagbuf, i); 212 break; 213 } 214 } 215 i = additem(pagbuf, key); 216 if (i < 0) 217 goto split; 218 if (additem(pagbuf, dat) < 0) { 219 delitem(pagbuf, i); 220 goto split; 221 } 222 (void) lseek(pagf, blkno*PBLKSIZ, 0); 223 (void) write(pagf, pagbuf, PBLKSIZ); 224 return (0); 225 split: 226 if (key.dsize+dat.dsize+3*sizeof (short) >= PBLKSIZ) { 227 (void) printf("entry too big\n"); 228 return (-1); 229 } 230 bzero(ovfbuf, PBLKSIZ); 231 Oneflag = 0; 232 for (i = 0; ; ) { 233 item = makdatum(pagbuf, i); 234 Oneflag++; 235 if (item.dptr == NULL) { 236 if ((Sentry.dsize == key.dsize) && 237 (strncmp(Sentry.dptr, key.dptr, key.dsize) == 0)) 238 return (-1); 239 if (Oneflag == 2) { 240 Sentry.dsize = key.dsize; 241 Sentry.dptr = malloc(strlen(key.dptr)+1); 242 (void) strncpy(Sentry.dptr, key.dptr, 243 key.dsize); 244 } 245 break; 246 } 247 if (calchash(item) & (hmask+1)) { 248 (void) additem(ovfbuf, item); 249 delitem(pagbuf, i); 250 item = makdatum(pagbuf, i); 251 if (item.dptr == NULL) { 252 (void) printf("split not paired\n"); 253 break; 254 } 255 (void) additem(ovfbuf, item); 256 delitem(pagbuf, i); 257 continue; 258 } 259 i += 2; 260 } 261 (void) lseek(pagf, blkno*PBLKSIZ, 0); 262 if (write(pagf, pagbuf, PBLKSIZ) < 0) 263 return (-1); 264 (void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0); 265 if (write(pagf, ovfbuf, PBLKSIZ) < 0) 266 return (-1); 267 if (setbit() < 0) 268 return (-1); 269 goto loop; 270 } 271 272 datum 273 firstkey(void) 274 { 275 return (firsthash(0L)); 276 } 277 278 datum 279 nextkey(datum key) 280 { 281 int i; 282 datum item, bitem; 283 long hash; 284 int f; 285 286 hash = calchash(key); 287 dbm_access(hash); 288 f = 1; 289 for (i = 0; ; i += 2) { 290 item = makdatum(pagbuf, i); 291 if (item.dptr == NULL) 292 break; 293 if (cmpdatum(key, item) <= 0) 294 continue; 295 if (f || cmpdatum(bitem, item) < 0) { 296 bitem = item; 297 f = 0; 298 } 299 } 300 if (f == 0) 301 return (bitem); 302 hash = hashinc(hash); 303 if (hash == 0) 304 return (item); 305 return (firsthash(hash)); 306 } 307 308 datum 309 firsthash(long hash) 310 { 311 int i; 312 datum item, bitem; 313 314 loop: 315 dbm_access(hash); 316 bitem = makdatum(pagbuf, 0); 317 for (i = 2; ; i += 2) { 318 item = makdatum(pagbuf, i); 319 if (item.dptr == NULL) 320 break; 321 if (cmpdatum(bitem, item) < 0) 322 bitem = item; 323 } 324 if (bitem.dptr != NULL) 325 return (bitem); 326 hash = hashinc(hash); 327 if (hash == 0) 328 return (item); 329 goto loop; 330 } 331 332 void 333 dbm_access(long hash) 334 { 335 ssize_t readsize; 336 337 for (hmask = 0; ; hmask = (hmask<<1)+1) { 338 blkno = hash & hmask; 339 bitno = blkno + hmask; 340 if (getbit() == 0) 341 break; 342 } 343 if (blkno != oldb1) { 344 (void) lseek(pagf, blkno*PBLKSIZ, 0); 345 readsize = read(pagf, pagbuf, PBLKSIZ); 346 if (readsize != PBLKSIZ) { 347 if (readsize < 0) readsize = 0; 348 bzero(pagbuf+readsize, PBLKSIZ-readsize); 349 } 350 chkblk(pagbuf); 351 oldb1 = blkno; 352 } 353 } 354 355 int 356 getbit(void) 357 { 358 long bn; 359 ssize_t readsize; 360 long b, i, n; 361 362 if (bitno > maxbno) 363 return (0); 364 n = bitno % BYTESIZ; 365 bn = bitno / BYTESIZ; 366 i = bn % DBLKSIZ; 367 b = bn / DBLKSIZ; 368 if (b != oldb2) { 369 (void) lseek(dirf, (long)b*DBLKSIZ, 0); 370 readsize = read(dirf, dirbuf, DBLKSIZ); 371 if (readsize != DBLKSIZ) { 372 if (readsize < 0) readsize = 0; 373 bzero(dirbuf+readsize, DBLKSIZ-readsize); 374 } 375 oldb2 = b; 376 } 377 if (dirbuf[i] & (1<<n)) 378 return (1); 379 return (0); 380 } 381 382 int 383 setbit(void) 384 { 385 long bn; 386 long i, n, b; 387 388 if (dbrdonly) 389 return (-1); 390 if (bitno > maxbno) { 391 maxbno = bitno; 392 (void) getbit(); 393 } 394 n = bitno % BYTESIZ; 395 bn = bitno / BYTESIZ; 396 i = bn % DBLKSIZ; 397 b = bn / DBLKSIZ; 398 dirbuf[i] |= 1<<n; 399 (void) lseek(dirf, (long)b*DBLKSIZ, 0); 400 if (write(dirf, dirbuf, DBLKSIZ) < 0) 401 return (-1); 402 return (0); 403 } 404 405 datum 406 makdatum(char buf[PBLKSIZ], int n) 407 { 408 short *sp; 409 int t; 410 datum item; 411 412 sp = (short *)buf; 413 if (n < 0 || n >= sp[0]) 414 goto null; 415 t = PBLKSIZ; 416 if (n > 0) 417 t = sp[n+1-1]; 418 item.dptr = buf+sp[n+1]; 419 item.dsize = t - sp[n+1]; 420 return (item); 421 422 null: 423 item.dptr = NULL; 424 item.dsize = 0; 425 return (item); 426 } 427 428 int 429 cmpdatum(datum d1, datum d2) 430 { 431 int n; 432 char *p1, *p2; 433 434 n = d1.dsize; 435 if (n != d2.dsize) 436 return (n - d2.dsize); 437 if (n == 0) 438 return (0); 439 p1 = d1.dptr; 440 p2 = d2.dptr; 441 do 442 if (*p1++ != *p2++) 443 return (*--p1 - *--p2); 444 while (--n); 445 return (0); 446 } 447 448 int hitab[16] 449 /* 450 * ken's 451 * { 452 * 055,043,036,054,063,014,004,005, 453 * 010,064,077,000,035,027,025,071, 454 * }; 455 */ 456 = { 61, 57, 53, 49, 45, 41, 37, 33, 457 29, 25, 21, 17, 13, 9, 5, 1, 458 }; 459 long hltab[64] = { 460 06100151277L, 06106161736L, 06452611562L, 05001724107L, 461 02614772546L, 04120731531L, 04665262210L, 07347467531L, 462 06735253126L, 06042345173L, 03072226605L, 01464164730L, 463 03247435524L, 07652510057L, 01546775256L, 05714532133L, 464 06173260402L, 07517101630L, 02431460343L, 01743245566L, 465 00261675137L, 02433103631L, 03421772437L, 04447707466L, 466 04435620103L, 03757017115L, 03641531772L, 06767633246L, 467 02673230344L, 00260612216L, 04133454451L, 00615531516L, 468 06137717526L, 02574116560L, 02304023373L, 07061702261L, 469 05153031405L, 05322056705L, 07401116734L, 06552375715L, 470 06165233473L, 05311063631L, 01212221723L, 01052267235L, 471 06000615237L, 01075222665L, 06330216006L, 04402355630L, 472 01451177262L, 02000133436L, 06025467062L, 07121076461L, 473 03123433522L, 01010635225L, 01716177066L, 05161746527L, 474 01736635071L, 06243505026L, 03637211610L, 01756474365L, 475 04723077174L, 03642763134L, 05750130273L, 03655541561L, 476 }; 477 478 long 479 hashinc(long hash) 480 { 481 long bit; 482 483 hash &= hmask; 484 bit = hmask+1; 485 for (;;) { 486 bit >>= 1; 487 if (bit == 0) 488 return (0L); 489 if ((hash&bit) == 0) 490 return (hash|bit); 491 hash &= ~bit; 492 } 493 } 494 495 long 496 calchash(datum item) 497 { 498 int i, j, f; 499 long hashl; 500 int hashi; 501 502 hashl = 0; 503 hashi = 0; 504 for (i = 0; i < item.dsize; i++) { 505 f = item.dptr[i]; 506 for (j = 0; j < BYTESIZ; j += 4) { 507 hashi += hitab[f&017]; 508 hashl += hltab[hashi&63]; 509 f >>= 4; 510 } 511 } 512 return (hashl); 513 } 514 515 void 516 delitem(char buf[PBLKSIZ], int n) 517 { 518 short *sp; 519 int i1, i2, i3; 520 521 sp = (short *)buf; 522 if (n < 0 || n >= sp[0]) 523 goto bad; 524 i1 = sp[n+1]; 525 i2 = PBLKSIZ; 526 if (n > 0) 527 i2 = sp[n+1-1]; 528 i3 = sp[sp[0]+1-1]; 529 if (i2 > i1) 530 while (i1 > i3) { 531 i1--; 532 i2--; 533 buf[i2] = buf[i1]; 534 buf[i1] = 0; 535 } 536 i2 -= i1; 537 for (i1 = n+1; i1 < sp[0]; i1++) 538 sp[i1+1-1] = sp[i1+1] + i2; 539 sp[0]--; 540 sp[sp[0]+1] = 0; 541 return; 542 543 bad: 544 (void) printf("bad delitem\n"); 545 abort(); 546 } 547 548 int 549 additem(char buf[PBLKSIZ], datum item) 550 { 551 short *sp; 552 int i1, i2; 553 554 sp = (short *)buf; 555 i1 = PBLKSIZ; 556 if (sp[0] > 0) 557 i1 = sp[sp[0]+1-1]; 558 i1 -= item.dsize; 559 i2 = (int)((sp[0]+2) * sizeof (short)); 560 if (i1 <= i2) 561 return (-1); 562 sp[sp[0]+1] = (short)i1; 563 for (i2 = 0; i2 < item.dsize; i2++) { 564 buf[i1] = item.dptr[i2]; 565 i1++; 566 } 567 sp[0]++; 568 return (sp[0]-1); 569 } 570 571 void 572 chkblk(char buf[PBLKSIZ]) 573 { 574 short *sp; 575 int t, i; 576 577 sp = (short *)buf; 578 t = PBLKSIZ; 579 for (i = 0; i < sp[0]; i++) { 580 if (sp[i+1] > t) 581 goto bad; 582 t = sp[i+1]; 583 } 584 if (t < (sp[0]+1)*sizeof (short)) 585 goto bad; 586 return; 587 588 bad: 589 (void) printf("bad block\n"); 590 abort(); 591 bzero(buf, PBLKSIZ); 592 } 593