2.9BSD - /usr/src/lib/dbm/dbm.c

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

Defined functions

Defined variables