4.3BSD - /usr/src/old/libdbm/dbm.c

   1: #ifndef lint
   2: static char sccsid[] = "@(#)dbm.c	4.5 (Berkeley) 6/19/85";
   3: #endif
   4: 
   5: #include    "dbm.h"
   6: #undef      NULL
   7: #include    <sys/types.h>
   8: #undef      setbit
   9: #include    <sys/stat.h>
  10: 
  11: dbminit(file)
  12: char *file;
  13: {
  14:     struct stat statb;
  15: 
  16:     dbrdonly = 0;
  17:     strcpy(pagbuf, file);
  18:     strcat(pagbuf, ".pag");
  19:     pagf = open(pagbuf, 2);
  20:     if (pagf < 0) {
  21:         pagf = open(pagbuf, 0);
  22:         dbrdonly = 1;
  23:     }
  24: 
  25:     strcpy(pagbuf, file);
  26:     strcat(pagbuf, ".dir");
  27:     dirf = open(pagbuf, 2);
  28:     if (dirf < 0) {
  29:         dirf = open(pagbuf, 0);
  30:         dbrdonly = 1;
  31:     }
  32:     if(pagf < 0 || dirf < 0) {
  33:         printf("dbm: %s: cannot open database\n", file);
  34:         return(-1);
  35:     }
  36:     fstat(dirf, &statb);
  37:     maxbno = statb.st_size*BYTESIZ-1;
  38:     return(0);
  39: }
  40: 
  41: long
  42: forder(key)
  43: datum key;
  44: {
  45:     long hash;
  46: 
  47:     hash = calchash(key);
  48:     for(hmask=0;; hmask=(hmask<<1)+1) {
  49:         blkno = hash & hmask;
  50:         bitno = blkno + hmask;
  51:         if(getbit() == 0)
  52:             break;
  53:     }
  54:     return(blkno);
  55: }
  56: 
  57: datum
  58: fetch(key)
  59: datum key;
  60: {
  61:     register i;
  62:     datum item;
  63: 
  64:     dbm_access(calchash(key));
  65:     for(i=0;; i+=2) {
  66:         item = makdatum(pagbuf, i);
  67:         if(item.dptr == NULL)
  68:             return(item);
  69:         if(cmpdatum(key, item) == 0) {
  70:             item = makdatum(pagbuf, i+1);
  71:             if(item.dptr == NULL)
  72:                 printf("dbm: items not in pairs\n");
  73:             return(item);
  74:         }
  75:     }
  76: }
  77: 
  78: delete(key)
  79: datum key;
  80: {
  81:     register i;
  82:     datum item;
  83: 
  84:     if (dbrdonly)
  85:         return -1;
  86:     dbm_access(calchash(key));
  87:     for(i=0;; i+=2) {
  88:         item = makdatum(pagbuf, i);
  89:         if(item.dptr == NULL)
  90:             return(-1);
  91:         if(cmpdatum(key, item) == 0) {
  92:             delitem(pagbuf, i);
  93:             delitem(pagbuf, i);
  94:             break;
  95:         }
  96:     }
  97:     lseek(pagf, blkno*PBLKSIZ, 0);
  98:     write(pagf, pagbuf, PBLKSIZ);
  99:     return(0);
 100: }
 101: 
 102: store(key, dat)
 103: datum key, dat;
 104: {
 105:     register i;
 106:     datum item;
 107:     char ovfbuf[PBLKSIZ];
 108: 
 109:     if (dbrdonly)
 110:         return -1;
 111: loop:
 112:     dbm_access(calchash(key));
 113:     for(i=0;; i+=2) {
 114:         item = makdatum(pagbuf, i);
 115:         if(item.dptr == NULL)
 116:             break;
 117:         if(cmpdatum(key, item) == 0) {
 118:             delitem(pagbuf, i);
 119:             delitem(pagbuf, i);
 120:             break;
 121:         }
 122:     }
 123:     i = additem(pagbuf, key);
 124:     if(i < 0)
 125:         goto split;
 126:     if(additem(pagbuf, dat) < 0) {
 127:         delitem(pagbuf, i);
 128:         goto split;
 129:     }
 130:     lseek(pagf, blkno*PBLKSIZ, 0);
 131:     write(pagf, pagbuf, PBLKSIZ);
 132:     return (0);
 133: 
 134: split:
 135:     if(key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
 136:         printf("dbm: entry too big\n");
 137:         return (-1);
 138:     }
 139:     clrbuf(ovfbuf, PBLKSIZ);
 140:     for(i=0;;) {
 141:         item = makdatum(pagbuf, i);
 142:         if(item.dptr == NULL)
 143:             break;
 144:         if(calchash(item) & (hmask+1)) {
 145:             additem(ovfbuf, item);
 146:             delitem(pagbuf, i);
 147:             item = makdatum(pagbuf, i);
 148:             if(item.dptr == NULL) {
 149:                 printf("dbm: split not paired\n");
 150:                 break;
 151:             }
 152:             additem(ovfbuf, item);
 153:             delitem(pagbuf, i);
 154:             continue;
 155:         }
 156:         i += 2;
 157:     }
 158:     lseek(pagf, blkno*PBLKSIZ, 0);
 159:     write(pagf, pagbuf, PBLKSIZ);
 160:     lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
 161:     write(pagf, ovfbuf, PBLKSIZ);
 162:     setbit();
 163:     goto loop;
 164: }
 165: 
 166: datum
 167: firstkey()
 168: {
 169:     return(firsthash(0L));
 170: }
 171: 
 172: datum
 173: nextkey(key)
 174: datum key;
 175: {
 176:     register i;
 177:     datum item, bitem;
 178:     long hash;
 179:     int f;
 180: 
 181:     hash = calchash(key);
 182:     dbm_access(hash);
 183:     f = 1;
 184:     for(i=0;; i+=2) {
 185:         item = makdatum(pagbuf, i);
 186:         if(item.dptr == NULL)
 187:             break;
 188:         if(cmpdatum(key, item) <= 0)
 189:             continue;
 190:         if(f || cmpdatum(bitem, item) < 0) {
 191:             bitem = item;
 192:             f = 0;
 193:         }
 194:     }
 195:     if(f == 0)
 196:         return(bitem);
 197:     hash = hashinc(hash);
 198:     if(hash == 0)
 199:         return(item);
 200:     return(firsthash(hash));
 201: }
 202: 
 203: datum
 204: firsthash(hash)
 205: long hash;
 206: {
 207:     register i;
 208:     datum item, bitem;
 209: 
 210: loop:
 211:     dbm_access(hash);
 212:     bitem = makdatum(pagbuf, 0);
 213:     for(i=2;; i+=2) {
 214:         item = makdatum(pagbuf, i);
 215:         if(item.dptr == NULL)
 216:             break;
 217:         if(cmpdatum(bitem, item) < 0)
 218:             bitem = item;
 219:     }
 220:     if(bitem.dptr != NULL)
 221:         return(bitem);
 222:     hash = hashinc(hash);
 223:     if(hash == 0)
 224:         return(item);
 225:     goto loop;
 226: }
 227: 
 228: dbm_access(hash)
 229: long hash;
 230: {
 231:     static long oldb = -1;
 232: 
 233:     for(hmask=0;; hmask=(hmask<<1)+1) {
 234:         blkno = hash & hmask;
 235:         bitno = blkno + hmask;
 236:         if(getbit() == 0)
 237:             break;
 238:     }
 239:     if(blkno != oldb) {
 240:         clrbuf(pagbuf, PBLKSIZ);
 241:         lseek(pagf, blkno*PBLKSIZ, 0);
 242:         read(pagf, pagbuf, PBLKSIZ);
 243:         chkblk(pagbuf);
 244:         oldb = blkno;
 245:     }
 246: }
 247: 
 248: getbit()
 249: {
 250:     long bn;
 251:     register b, i, n;
 252:     static oldb = -1;
 253: 
 254:     if(bitno > maxbno)
 255:         return(0);
 256:     n = bitno % BYTESIZ;
 257:     bn = bitno / BYTESIZ;
 258:     i = bn % DBLKSIZ;
 259:     b = bn / DBLKSIZ;
 260:     if(b != oldb) {
 261:         clrbuf(dirbuf, DBLKSIZ);
 262:         lseek(dirf, (long)b*DBLKSIZ, 0);
 263:         read(dirf, dirbuf, DBLKSIZ);
 264:         oldb = b;
 265:     }
 266:     if(dirbuf[i] & (1<<n))
 267:         return(1);
 268:     return(0);
 269: }
 270: 
 271: setbit()
 272: {
 273:     long bn;
 274:     register i, n, b;
 275: 
 276:     if (dbrdonly)
 277:         return -1;
 278:     if(bitno > maxbno) {
 279:         maxbno = bitno;
 280:         getbit();
 281:     }
 282:     n = bitno % BYTESIZ;
 283:     bn = bitno / BYTESIZ;
 284:     i = bn % DBLKSIZ;
 285:     b = bn / DBLKSIZ;
 286:     dirbuf[i] |= 1<<n;
 287:     lseek(dirf, (long)b*DBLKSIZ, 0);
 288:     write(dirf, dirbuf, DBLKSIZ);
 289: }
 290: 
 291: clrbuf(cp, n)
 292: register char *cp;
 293: register n;
 294: {
 295: 
 296:     do
 297:         *cp++ = 0;
 298:     while(--n);
 299: }
 300: 
 301: datum
 302: makdatum(buf, n)
 303: char buf[PBLKSIZ];
 304: {
 305:     register short *sp;
 306:     register t;
 307:     datum item;
 308: 
 309:     sp = (short *)buf;
 310:     if(n < 0 || n >= sp[0])
 311:         goto null;
 312:     t = PBLKSIZ;
 313:     if(n > 0)
 314:         t = sp[n+1-1];
 315:     item.dptr = buf+sp[n+1];
 316:     item.dsize = t - sp[n+1];
 317:     return(item);
 318: 
 319: null:
 320:     item.dptr = NULL;
 321:     item.dsize = 0;
 322:     return(item);
 323: }
 324: 
 325: cmpdatum(d1, d2)
 326: datum d1, d2;
 327: {
 328:     register n;
 329:     register char *p1, *p2;
 330: 
 331:     n = d1.dsize;
 332:     if(n != d2.dsize)
 333:         return(n - d2.dsize);
 334:     if(n == 0)
 335:         return(0);
 336:     p1 = d1.dptr;
 337:     p2 = d2.dptr;
 338:     do
 339:         if(*p1++ != *p2++)
 340:             return(*--p1 - *--p2);
 341:     while(--n);
 342:     return(0);
 343: }
 344: 
 345: int hitab[16]
 346: /* ken's
 347: {
 348: 	055,043,036,054,063,014,004,005,
 349: 	010,064,077,000,035,027,025,071,
 350: };
 351: */
 352:  = {    61, 57, 53, 49, 45, 41, 37, 33,
 353:     29, 25, 21, 17, 13,  9,  5,  1,
 354: };
 355: long    hltab[64]
 356:  = {
 357:     06100151277L,06106161736L,06452611562L,05001724107L,
 358:     02614772546L,04120731531L,04665262210L,07347467531L,
 359:     06735253126L,06042345173L,03072226605L,01464164730L,
 360:     03247435524L,07652510057L,01546775256L,05714532133L,
 361:     06173260402L,07517101630L,02431460343L,01743245566L,
 362:     00261675137L,02433103631L,03421772437L,04447707466L,
 363:     04435620103L,03757017115L,03641531772L,06767633246L,
 364:     02673230344L,00260612216L,04133454451L,00615531516L,
 365:     06137717526L,02574116560L,02304023373L,07061702261L,
 366:     05153031405L,05322056705L,07401116734L,06552375715L,
 367:     06165233473L,05311063631L,01212221723L,01052267235L,
 368:     06000615237L,01075222665L,06330216006L,04402355630L,
 369:     01451177262L,02000133436L,06025467062L,07121076461L,
 370:     03123433522L,01010635225L,01716177066L,05161746527L,
 371:     01736635071L,06243505026L,03637211610L,01756474365L,
 372:     04723077174L,03642763134L,05750130273L,03655541561L,
 373: };
 374: 
 375: long
 376: hashinc(hash)
 377: long hash;
 378: {
 379:     long bit;
 380: 
 381:     hash &= hmask;
 382:     bit = hmask+1;
 383:     for(;;) {
 384:         bit >>= 1;
 385:         if(bit == 0)
 386:             return(0L);
 387:         if((hash&bit) == 0)
 388:             return(hash|bit);
 389:         hash &= ~bit;
 390:     }
 391: }
 392: 
 393: long
 394: calchash(item)
 395: datum item;
 396: {
 397:     register i, j, f;
 398:     long hashl;
 399:     int hashi;
 400: 
 401:     hashl = 0;
 402:     hashi = 0;
 403:     for(i=0; i<item.dsize; i++) {
 404:         f = item.dptr[i];
 405:         for(j=0; j<BYTESIZ; j+=4) {
 406:             hashi += hitab[f&017];
 407:             hashl += hltab[hashi&63];
 408:             f >>= 4;
 409:         }
 410:     }
 411:     return(hashl);
 412: }
 413: 
 414: delitem(buf, n)
 415: char buf[PBLKSIZ];
 416: {
 417:     register short *sp;
 418:     register i1, i2, i3;
 419: 
 420:     sp = (short *)buf;
 421:     if(n < 0 || n >= sp[0])
 422:         goto bad;
 423:     i1 = sp[n+1];
 424:     i2 = PBLKSIZ;
 425:     if(n > 0)
 426:         i2 = sp[n+1-1];
 427:     i3 = sp[sp[0]+1-1];
 428:     if(i2 > i1)
 429:     while(i1 > i3) {
 430:         i1--;
 431:         i2--;
 432:         buf[i2] = buf[i1];
 433:         buf[i1] = 0;
 434:     }
 435:     i2 -= i1;
 436:     for(i1=n+1; i1<sp[0]; i1++)
 437:         sp[i1+1-1] = sp[i1+1] + i2;
 438:     sp[0]--;
 439:     sp[sp[0]+1] = 0;
 440:     return;
 441: 
 442: bad:
 443:     printf("dbm: bad delitem\n");
 444:     abort();
 445: }
 446: 
 447: additem(buf, item)
 448: char buf[PBLKSIZ];
 449: datum item;
 450: {
 451:     register short *sp;
 452:     register i1, i2;
 453: 
 454:     sp = (short *)buf;
 455:     i1 = PBLKSIZ;
 456:     if(sp[0] > 0)
 457:         i1 = sp[sp[0]+1-1];
 458:     i1 -= item.dsize;
 459:     i2 = (sp[0]+2) * sizeof(short);
 460:     if(i1 <= i2)
 461:         return(-1);
 462:     sp[sp[0]+1] = i1;
 463:     for(i2=0; i2<item.dsize; i2++) {
 464:         buf[i1] = item.dptr[i2];
 465:         i1++;
 466:     }
 467:     sp[0]++;
 468:     return(sp[0]-1);
 469: }
 470: 
 471: chkblk(buf)
 472: char buf[PBLKSIZ];
 473: {
 474:     register short *sp;
 475:     register t, i;
 476: 
 477:     sp = (short *)buf;
 478:     t = PBLKSIZ;
 479:     for(i=0; i<sp[0]; i++) {
 480:         if(sp[i+1] > t)
 481:             goto bad;
 482:         t = sp[i+1];
 483:     }
 484:     if(t < (sp[0]+1)*sizeof(short))
 485:         goto bad;
 486:     return;
 487: 
 488: bad:
 489:     printf("dbm: bad block\n");
 490:     abort();
 491:     clrbuf(buf, PBLKSIZ);
 492: }

Defined functions

Defined variables