Return to dbm.c CVS log

Up to [CSRG BSD Unix] / 40BSD / lib / libdbm

Annotation of 40BSD/lib/libdbm/dbm.c, revision 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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.