Return to dbm.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / old / libdbm

Annotation of 43BSDTahoe/old/libdbm/dbm.c, revision 1.1

1.1     ! root        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: }

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