usr/src/lib/libc/port/nsl/dbm.c

   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, O_RDWR);
  74         if (pagf < 0) {
  75                 pagf = open(pagbuf, O_RDONLY);
  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, O_RDWR);
  86         if (dirf < 0) {
  87                 dirf = open(pagbuf, O_RDONLY);
  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         hash = calchash(key);
 269         dbm_access(hash);
 270         f = 1;
 271         for (i = 0; ; i += 2) {
 272                 item = makdatum(pagbuf, i);
 273                 if (item.dptr == NULL)
 274                         break;
 275                 if (cmpdatum(key, item) <= 0)
 276                         continue;
 277                 if (f || cmpdatum(bitem, item) < 0) {
 278                         bitem = item;
 279                         f = 0;
 280                 }
 281         }
 282         if (f == 0)
 283                 return (bitem);
 284         hash = hashinc(hash);
 285         if (hash == 0)
 286                 return (item);
 287         return (firsthash(hash));
 288 }
 289
 290 datum
 291 firsthash(long hash)
 292 {
 293         int i;
 294         datum item, bitem;
 295
 296 loop:
 297         dbm_access(hash);
 298         bitem = makdatum(pagbuf, 0);
 299         for (i = 2; ; i += 2) {
 300                 item = makdatum(pagbuf, i);
 301                 if (item.dptr == NULL)
 302                         break;
 303                 if (cmpdatum(bitem, item) < 0)
 304                         bitem = item;
 305         }
 306         if (bitem.dptr != NULL)
 307                 return (bitem);
 308         hash = hashinc(hash);
 309         if (hash == 0)
 310                 return (item);
 311         goto loop;
 312 }
 313
 314 void
 315 dbm_access(long hash)
 316 {
 317         ssize_t readsize;
 318
 319         for (hmask = 0; ; hmask = (hmask<<1) + 1) {
 320                 blkno = hash & hmask;
 321                 bitno = blkno + hmask;
 322                 if (getbit() == 0)
 323                         break;
 324         }
 325         if (blkno != oldb1) {
 326                 (void) lseek(pagf, blkno*PBLKSIZ, 0);
 327                 readsize = read(pagf, pagbuf, PBLKSIZ);
 328                 if (readsize != PBLKSIZ) {
 329                         if (readsize < 0)
 330                                 readsize = 0;
 331                         (void) memset((&pagbuf+readsize), 0, PBLKSIZ-readsize);
 332                 }
 333                 chkblk(pagbuf);
 334                 oldb1 = blkno;
 335         }
 336 }
 337
 338 int
 339 getbit(void)
 340 {
 341         long bn;
 342         ssize_t readsize;
 343         long b, i, n;
 344
 345         if (bitno > maxbno)
 346                 return (0);
 347         n = bitno % BYTESIZ;
 348         bn = bitno / BYTESIZ;
 349         i = bn % DBLKSIZ;
 350         b = bn / DBLKSIZ;
 351         if (b != oldb2) {
 352                 (void) lseek(dirf, (long)b*DBLKSIZ, 0);
 353                 readsize = read(dirf, dirbuf, DBLKSIZ);
 354                 if (readsize != DBLKSIZ) {
 355                         if (readsize < 0)
 356                                 readsize = 0;
 357                         (void) memset(&dirbuf+readsize, 0, DBLKSIZ-readsize);
 358                 }
 359                 oldb2 = b;
 360         }
 361         if (dirbuf[i] & (1<<n))
 362                 return (1);
 363         return (0);
 364 }
 365
 366 int
 367 setbit(void)
 368 {
 369         long bn;
 370         long i, n, b;
 371
 372         if (dbrdonly)
 373                 return (-1);
 374         if (bitno > maxbno) {
 375                 maxbno = bitno;
 376                 (void) getbit();
 377         }
 378         n = bitno % BYTESIZ;
 379         bn = bitno / BYTESIZ;
 380         i = bn % DBLKSIZ;
 381         b = bn / DBLKSIZ;
 382         dirbuf[i] |= 1<<n;
 383         (void) lseek(dirf, (long)b*DBLKSIZ, 0);
 384         if (write(dirf, dirbuf, DBLKSIZ) < 0)
 385                 return (-1);
 386         return (0);
 387 }
 388
 389 datum
 390 makdatum(char buf[PBLKSIZ], int n)
 391 {
 392         short *sp;
 393         int t;
 394         datum item;
 395
 396         /* LINTED pointer cast */
 397         sp = (short *)buf;
 398         if (n < 0 || n >= sp[0])
 399                 goto null;
 400         t = PBLKSIZ;
 401         if (n > 0)
 402                 t = sp[n+1-1];
 403         item.dptr = buf+sp[n+1];
 404         item.dsize = t - sp[n+1];
 405         return (item);
 406
 407 null:
 408         item.dptr = NULL;
 409         item.dsize = 0;
 410         return (item);
 411 }
 412
 413 int
 414 cmpdatum(datum d1, datum d2)
 415 {
 416         int n;
 417         char *p1, *p2;
 418
 419         n = d1.dsize;
 420         if (n != d2.dsize)
 421                 return (n - d2.dsize);
 422         if (n == 0)
 423                 return (0);
 424         p1 = d1.dptr;
 425         p2 = d2.dptr;
 426         do
 427                 if (*p1++ != *p2++)
 428                         return (*--p1 - *--p2);
 429         while (--n);
 430         return (0);
 431 }
 432
 433 int     hitab[16]
 434 /*
 435  * ken's
 436  * {
 437  *      055, 043, 036, 054, 063, 014, 004, 005,
 438  *      010, 064, 077, 000, 035, 027, 025, 071,
 439  * };
 440  */
 441         = {     61, 57, 53, 49, 45, 41, 37, 33,
 442         29, 25, 21, 17, 13,  9,  5,  1,
 443 };
 444 long    hltab[64]
 445         = {
 446         06100151277L, 06106161736L, 06452611562L, 05001724107L,
 447         02614772546L, 04120731531L, 04665262210L, 07347467531L,
 448         06735253126L, 06042345173L, 03072226605L, 01464164730L,
 449         03247435524L, 07652510057L, 01546775256L, 05714532133L,
 450         06173260402L, 07517101630L, 02431460343L, 01743245566L,
 451         00261675137L, 02433103631L, 03421772437L, 04447707466L,
 452         04435620103L, 03757017115L, 03641531772L, 06767633246L,
 453         02673230344L, 00260612216L, 04133454451L, 00615531516L,
 454         06137717526L, 02574116560L, 02304023373L, 07061702261L,
 455         05153031405L, 05322056705L, 07401116734L, 06552375715L,
 456         06165233473L, 05311063631L, 01212221723L, 01052267235L,
 457         06000615237L, 01075222665L, 06330216006L, 04402355630L,
 458         01451177262L, 02000133436L, 06025467062L, 07121076461L,
 459         03123433522L, 01010635225L, 01716177066L, 05161746527L,
 460         01736635071L, 06243505026L, 03637211610L, 01756474365L,
 461         04723077174L, 03642763134L, 05750130273L, 03655541561L,
 462 };
 463
 464 long
 465 hashinc(long hash)
 466 {
 467         long bit;
 468
 469         hash &= hmask;
 470         bit = hmask+1;
 471         for (; ; ) {
 472                 bit >>= 1;
 473                 if (bit == 0)
 474                         return (0L);
 475                 if ((hash&bit) == 0)
 476                         return (hash|bit);
 477                 hash &= ~bit;
 478         }
 479 }
 480
 481 long
 482 calchash(datum item)
 483 {
 484         int i, j, f;
 485         long hashl;
 486         int hashi;
 487
 488         hashl = 0;
 489         hashi = 0;
 490         for (i = 0; i < item.dsize; i++) {
 491                 f = item.dptr[i];
 492                 for (j = 0; j < BYTESIZ; j += 4) {
 493                         hashi += hitab[f&017];
 494                         hashl += hltab[hashi&63];
 495                         f >>= 4;
 496                 }
 497         }
 498         return (hashl);
 499 }
 500
 501 void
 502 delitem(char buf[PBLKSIZ], int n)
 503 {
 504         short *sp;
 505         int i1, i2, i3;
 506
 507         /* LINTED pointer cast */
 508         sp = (short *)buf;
 509         if (n < 0 || n >= sp[0])
 510                 goto bad;
 511         i1 = sp[n+1];
 512         i2 = PBLKSIZ;
 513         if (n > 0)
 514                 i2 = sp[n+1-1];
 515         i3 = sp[sp[0]+1-1];
 516         if (i2 > i1)
 517         while (i1 > i3) {
 518                 i1--;
 519                 i2--;
 520                 buf[i2] = buf[i1];
 521                 buf[i1] = 0;
 522         }
 523         i2 -= i1;
 524         for (i1 = n + 1; i1 < sp[0]; i1++)
 525                 sp[i1+1-1] = sp[i1+1] + i2;
 526         sp[0]--;
 527         sp[sp[0]+1] = 0;
 528         return;
 529
 530 bad:
 531         (void) printf("bad delitem\n");
 532         abort();
 533 }
 534
 535 int
 536 additem(char buf[PBLKSIZ], datum item)
 537 {
 538         short *sp;
 539         int i1, i2;
 540
 541         /* LINTED pointer cast */
 542         sp = (short *)buf;
 543         i1 = PBLKSIZ;
 544         if (sp[0] > 0)
 545                 i1 = sp[sp[0]+1-1];
 546         i1 -= item.dsize;
 547         i2 = (sp[0]+2) * (int)sizeof (short);
 548         if (i1 <= i2)
 549                 return (-1);
 550         sp[sp[0]+1] = (short)i1;
 551         for (i2 = 0; i2 < item.dsize; i2++) {
 552                 buf[i1] = item.dptr[i2];
 553                 i1++;
 554         }
 555         sp[0]++;
 556         return (sp[0]-1);
 557 }
 558
 559 void
 560 chkblk(char buf[PBLKSIZ])
 561 {
 562         short *sp;
 563         int t, i;
 564
 565         /* LINTED pointer cast */
 566         sp = (short *)buf;
 567         t = PBLKSIZ;
 568         for (i = 0; i < sp[0]; i++) {
 569                 if (sp[i+1] > t)
 570                         goto bad;
 571                 t = sp[i+1];
 572         }
 573         if (t < (sp[0]+1) * sizeof (short))
 574                 goto bad;
 575         return;
 576
 577 bad:
 578         (void) printf("bad block\n");
 579         abort();
 580         (void) memset(&buf, 0, PBLKSIZ);
 581 }