Return to dbm.c CVS log

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

Annotation of 3BSD/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:        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: /* ken's
        !           326: {
        !           327:        055,043,036,054,063,014,004,005,
        !           328:        010,064,077,000,035,027,025,071,
        !           329: };
        !           330: */
        !           331:  = {   61, 57, 53, 49, 45, 41, 37, 33,
        !           332:        29, 25, 21, 17, 13,  9,  5,  1,
        !           333: };
        !           334: long   hltab[64]
        !           335:  = {
        !           336:        06100151277L,06106161736L,06452611562L,05001724107L,
        !           337:        02614772546L,04120731531L,04665262210L,07347467531L,
        !           338:        06735253126L,06042345173L,03072226605L,01464164730L,
        !           339:        03247435524L,07652510057L,01546775256L,05714532133L,
        !           340:        06173260402L,07517101630L,02431460343L,01743245566L,
        !           341:        00261675137L,02433103631L,03421772437L,04447707466L,
        !           342:        04435620103L,03757017115L,03641531772L,06767633246L,
        !           343:        02673230344L,00260612216L,04133454451L,00615531516L,
        !           344:        06137717526L,02574116560L,02304023373L,07061702261L,
        !           345:        05153031405L,05322056705L,07401116734L,06552375715L,
        !           346:        06165233473L,05311063631L,01212221723L,01052267235L,
        !           347:        06000615237L,01075222665L,06330216006L,04402355630L,
        !           348:        01451177262L,02000133436L,06025467062L,07121076461L,
        !           349:        03123433522L,01010635225L,01716177066L,05161746527L,
        !           350:        01736635071L,06243505026L,03637211610L,01756474365L,
        !           351:        04723077174L,03642763134L,05750130273L,03655541561L,
        !           352: };
        !           353: 
        !           354: long
        !           355: hashinc(hash)
        !           356: long hash;
        !           357: {
        !           358:        long bit;
        !           359: 
        !           360:        hash &= hmask;
        !           361:        bit = hmask+1;
        !           362:        for(;;) {
        !           363:                bit >>= 1;
        !           364:                if(bit == 0)
        !           365:                        return(0L);
        !           366:                if((hash&bit) == 0)
        !           367:                        return(hash|bit);
        !           368:                hash &= ~bit;
        !           369:        }
        !           370: }
        !           371: 
        !           372: long
        !           373: calchash(item)
        !           374: datum item;
        !           375: {
        !           376:        register i, j, f;
        !           377:        long hashl;
        !           378:        int hashi;
        !           379: 
        !           380:        hashl = 0;
        !           381:        hashi = 0;
        !           382:        for(i=0; i<item.dsize; i++) {
        !           383:                f = item.dptr[i];
        !           384:                for(j=0; j<BYTESIZ; j+=4) {
        !           385:                        hashi += hitab[f&017];
        !           386:                        hashl += hltab[hashi&63];
        !           387:                        f >>= 4;
        !           388:                }
        !           389:        }
        !           390:        return(hashl);
        !           391: }
        !           392: 
        !           393: delitem(buf, n)
        !           394: char buf[PBLKSIZ];
        !           395: {
        !           396:        register short *sp;
        !           397:        register i1, i2, i3;
        !           398: 
        !           399:        sp = (short *)buf;
        !           400:        if(n < 0 || n >= sp[0])
        !           401:                goto bad;
        !           402:        i1 = sp[n+1];
        !           403:        i2 = PBLKSIZ;
        !           404:        if(n > 0)
        !           405:                i2 = sp[n+1-1];
        !           406:        i3 = sp[sp[0]+1-1];
        !           407:        if(i2 > i1)
        !           408:        while(i1 > i3) {
        !           409:                i1--;
        !           410:                i2--;
        !           411:                buf[i2] = buf[i1];
        !           412:                buf[i1] = 0;
        !           413:        }
        !           414:        i2 -= i1;
        !           415:        for(i1=n+1; i1<sp[0]; i1++)
        !           416:                sp[i1+1-1] = sp[i1+1] + i2;
        !           417:        sp[0]--;
        !           418:        sp[sp[0]+1] = 0;
        !           419:        return;
        !           420: 
        !           421: bad:
        !           422:        printf("bad delitem\n");
        !           423:        abort();
        !           424: }
        !           425: 
        !           426: additem(buf, item)
        !           427: char buf[PBLKSIZ];
        !           428: datum item;
        !           429: {
        !           430:        register short *sp;
        !           431:        register i1, i2;
        !           432: 
        !           433:        sp = (short *)buf;
        !           434:        i1 = PBLKSIZ;
        !           435:        if(sp[0] > 0)
        !           436:                i1 = sp[sp[0]+1-1];
        !           437:        i1 -= item.dsize;
        !           438:        i2 = (sp[0]+2) * sizeof(short);
        !           439:        if(i1 <= i2)
        !           440:                return(-1);
        !           441:        sp[sp[0]+1] = i1;
        !           442:        for(i2=0; i2<item.dsize; i2++) {
        !           443:                buf[i1] = item.dptr[i2];
        !           444:                i1++;
        !           445:        }
        !           446:        sp[0]++;
        !           447:        return(sp[0]-1);
        !           448: }
        !           449: 
        !           450: chkblk(buf)
        !           451: char buf[PBLKSIZ];
        !           452: {
        !           453:        register short *sp;
        !           454:        register t, i;
        !           455: 
        !           456:        sp = (short *)buf;
        !           457:        t = PBLKSIZ;
        !           458:        for(i=0; i<sp[0]; i++) {
        !           459:                if(sp[i+1] > t)
        !           460:                        goto bad;
        !           461:                t = sp[i+1];
        !           462:        }
        !           463:        if(t < (sp[0]+1)*sizeof(short))
        !           464:                goto bad;
        !           465:        return;
        !           466: 
        !           467: bad:
        !           468:        printf("bad block\n");
        !           469:        abort();
        !           470:        clrbuf(buf, PBLKSIZ);
        !           471: }

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