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