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