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