Annotation of researchv8dc/libdbm/dbm.c, revision 1.1.1.1

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

unix.superglobalmegacorp.com