Return to dbm.c CVS log

Up to [CSRG BSD Unix] / 42BSD / usr.lib / libdbm

Annotation of 42BSD/usr.lib/libdbm/dbm.c, revision 1.1

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

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