ref: 44ce0097b612a1fefd754065bdf8d9d2e5ef60c8
dir: /appl/lib/dbm.b/
implement Dbm;
# Copyright © Caldera International Inc. 2001-2002. All rights reserved.
# Limbo transliteration (with amendment) Copyright © 2004 Vita Nuova Holdings Limited.
include "sys.m";
sys: Sys;
OREAD, OWRITE, ORDWR: import Sys;
include "dbm.m";
BYTESIZ: con 8; # bits
SHORTSIZ: con 2; # bytes
PBLKSIZ: con 512;
DBLKSIZ: con 8192; # was 4096
init()
{
sys = load Sys Sys->PATH;
}
Dbf.create(file: string, mode: int): ref Dbf
{
pf := sys->create(file+".pag", ORDWR, mode);
if(pf == nil)
return nil;
df := sys->create(file+".dir", ORDWR, mode);
if(df == nil)
return nil;
return alloc(pf, df, ORDWR);
}
Dbf.open(file: string, flags: int): ref Dbf
{
if((flags & 3) == OWRITE)
flags = (flags & ~3) | ORDWR;
pf := sys->open(file+".pag", flags);
if(pf == nil)
return nil;
df := sys->open(file+".dir", flags);
if(df == nil)
return nil;
return alloc(pf, df, flags);
}
alloc(pf: ref Sys->FD, df: ref Sys->FD, flags: int): ref Dbf
{
db := ref Dbf;
db.pagf = pf;
db.dirf = df;
db.flags = flags & 3;
db.maxbno = 0;
db.bitno = 0;
db.hmask = 0;
db.blkno = 0;
db.pagbno = -1;
db.pagbuf = array[PBLKSIZ] of byte;
db.dirbno = -1;
db.dirbuf = array[DBLKSIZ] of byte;
(ok, d) := sys->fstat(db.dirf);
if(ok < 0)
d.length = big 0;
db.maxbno = int (d.length*big BYTESIZ - big 1);
return db;
}
Dbf.flush(db: self ref Dbf)
{
db.pagbno = db.dirbno = -1;
}
Dbf.isrdonly(db: self ref Dbf): int
{
return db.flags == OREAD;
}
Dbf.fetch(db: self ref Dbf, key: Datum): Datum
{
access(db, calchash(key));
for(i:=0;; i+=2){
item := makdatum(db.pagbuf, i);
if(item == nil)
return item;
if(cmpdatum(key, item) == 0){
item = makdatum(db.pagbuf, i+1);
if(item == nil){
sys->fprint(sys->fildes(2), "dbm: items not in pairs\n");
raise "dbm: items not in pairs";
}
return item;
}
}
}
Dbf.delete(db: self ref Dbf, key: Datum): int
{
if(db.isrdonly())
return -1;
access(db, calchash(key));
for(i:=0;; i+=2){
item := makdatum(db.pagbuf, i);
if(item == nil)
return -1;
if(cmpdatum(key, item) == 0){
delitem(db.pagbuf, i);
delitem(db.pagbuf, i);
break;
}
}
sys->seek(db.pagf, big db.blkno*big PBLKSIZ, 0);
write(db.pagf, db.pagbuf, PBLKSIZ);
db.pagbno = db.blkno;
return 0;
}
Dbf.store(db: self ref Dbf, key: Datum, dat: Datum, replace: int): int
{
if(db.isrdonly())
return -1;
for(;;){
access(db, calchash(key));
for(i:=0;; i+=2){
item := makdatum(db.pagbuf, i);
if(item == nil)
break;
if(cmpdatum(key, item) == 0){
if(!replace)
return 1;
delitem(db.pagbuf, i);
delitem(db.pagbuf, i);
break;
}
}
i = additem(db.pagbuf, key);
if(i >= 0){
if(additem(db.pagbuf, dat) >= 0)
break;
delitem(db.pagbuf, i);
}
if(!split(db, key, dat))
return -1;
}
sys->seek(db.pagf, big db.blkno*big PBLKSIZ, 0);
write(db.pagf, db.pagbuf, PBLKSIZ);
db.pagbno = db.blkno;
return 0;
}
split(db: ref Dbf, key: Datum, dat: Datum): int
{
if(len key+len dat+3*SHORTSIZ >= PBLKSIZ)
return 0;
ovfbuf := array[PBLKSIZ] of {* => byte 0};
for(i:=0;;){
item := makdatum(db.pagbuf, i);
if(item == nil)
break;
if(calchash(item) & (db.hmask+1)){
additem(ovfbuf, item);
delitem(db.pagbuf, i);
item = makdatum(db.pagbuf, i);
if(item == nil){
sys->fprint(sys->fildes(2), "dbm: split not paired\n");
raise "dbm: split not paired";
#break;
}
additem(ovfbuf, item);
delitem(db.pagbuf, i);
continue;
}
i += 2;
}
sys->seek(db.pagf, big db.blkno*big PBLKSIZ, 0);
write(db.pagf, db.pagbuf, PBLKSIZ);
db.pagbno = db.blkno;
sys->seek(db.pagf, (big db.blkno+big db.hmask+big 1)*big PBLKSIZ, 0);
write(db.pagf, ovfbuf, PBLKSIZ);
setbit(db);
return 1;
}
Dbf.firstkey(db: self ref Dbf): Datum
{
return copy(firsthash(db, 0));
}
Dbf.nextkey(db: self ref Dbf, key: Datum): Datum
{
hash := calchash(key);
access(db, hash);
item, bitem: Datum;
for(i:=0;; i+=2){
item = makdatum(db.pagbuf, i);
if(item == nil)
break;
if(cmpdatum(key, item) <= 0)
continue;
if(bitem == nil || cmpdatum(bitem, item) < 0)
bitem = item;
}
if(bitem != nil)
return copy(bitem);
hash = hashinc(db, hash);
if(hash == 0)
return copy(item);
return copy(firsthash(db, hash));
}
firsthash(db: ref Dbf, hash: int): Datum
{
for(;;){
access(db, hash);
bitem := makdatum(db.pagbuf, 0);
item: Datum;
for(i:=2;; i+=2){
item = makdatum(db.pagbuf, i);
if(item == nil)
break;
if(cmpdatum(bitem, item) < 0)
bitem = item;
}
if(bitem != nil)
return bitem;
hash = hashinc(db, hash);
if(hash == 0)
return item;
}
}
access(db: ref Dbf, hash: int)
{
for(db.hmask=0;; db.hmask=(db.hmask<<1)+1){
db.blkno = hash & db.hmask;
db.bitno = db.blkno + db.hmask;
if(getbit(db) == 0)
break;
}
if(db.blkno != db.pagbno){
sys->seek(db.pagf, big db.blkno * big PBLKSIZ, 0);
read(db.pagf, db.pagbuf, PBLKSIZ);
chkblk(db.pagbuf);
db.pagbno = db.blkno;
}
}
getbit(db: ref Dbf): int
{
if(db.bitno > db.maxbno)
return 0;
n := db.bitno % BYTESIZ;
bn := db.bitno / BYTESIZ;
i := bn % DBLKSIZ;
b := bn / DBLKSIZ;
if(b != db.dirbno){
sys->seek(db.dirf, big b * big DBLKSIZ, 0);
read(db.dirf, db.dirbuf, DBLKSIZ);
db.dirbno = b;
}
if(int db.dirbuf[i] & (1<<n))
return 1;
return 0;
}
setbit(db: ref Dbf)
{
if(db.bitno > db.maxbno){
db.maxbno = db.bitno;
getbit(db);
}
n := db.bitno % BYTESIZ;
bn := db.bitno / BYTESIZ;
i := bn % DBLKSIZ;
b := bn / DBLKSIZ;
db.dirbuf[i] |= byte (1<<n);
sys->seek(db.dirf, big b * big DBLKSIZ, 0);
write(db.dirf, db.dirbuf, DBLKSIZ);
db.dirbno = b;
}
makdatum(buf: array of byte, n: int): Datum
{
ne := GETS(buf, 0);
if(n < 0 || n >= ne)
return nil;
t := PBLKSIZ;
if(n > 0)
t = GETS(buf, n+1-1);
v := GETS(buf, n+1);
return buf[v: t]; # size is t-v
}
cmpdatum(d1: Datum, d2: Datum): int
{
n := len d1;
if(n != len d2)
return n - len d2;
if(n == 0)
return 0;
for(i := 0; i < len d1; i++)
if(d1[i] != d2[i])
return int d1[i] - int d2[i];
return 0;
}
copy(d: Datum): Datum
{
if(d == nil)
return nil;
a := array[len d] of byte;
a[0:] = d;
return a;
}
# ken's
#
# 055,043,036,054,063,014,004,005,
# 010,064,077,000,035,027,025,071,
#
hitab := array[16] of {
61, 57, 53, 49, 45, 41, 37, 33,
29, 25, 21, 17, 13, 9, 5, 1,
};
hltab := array[64] of {
8r6100151277,8r6106161736,8r6452611562,8r5001724107,
8r2614772546,8r4120731531,8r4665262210,8r7347467531,
8r6735253126,8r6042345173,8r3072226605,8r1464164730,
8r3247435524,8r7652510057,8r1546775256,8r5714532133,
8r6173260402,8r7517101630,8r2431460343,8r1743245566,
8r0261675137,8r2433103631,8r3421772437,8r4447707466,
8r4435620103,8r3757017115,8r3641531772,8r6767633246,
8r2673230344,8r0260612216,8r4133454451,8r0615531516,
8r6137717526,8r2574116560,8r2304023373,8r7061702261,
8r5153031405,8r5322056705,8r7401116734,8r6552375715,
8r6165233473,8r5311063631,8r1212221723,8r1052267235,
8r6000615237,8r1075222665,8r6330216006,8r4402355630,
8r1451177262,8r2000133436,8r6025467062,8r7121076461,
8r3123433522,8r1010635225,8r1716177066,8r5161746527,
8r1736635071,8r6243505026,8r3637211610,8r1756474365,
8r4723077174,8r3642763134,8r5750130273,8r3655541561,
};
hashinc(db: ref Dbf, hash: int): int
{
hash &= db.hmask;
bit := db.hmask+1;
for(;;){
bit >>= 1;
if(bit == 0)
return 0;
if((hash&bit) == 0)
return hash|bit;
hash &= ~bit;
}
}
calchash(item: Datum): int
{
hashl := 0;
hashi := 0;
for(i:=0; i<len item; i++){
f := int item[i];
for(j:=0; j<BYTESIZ; j+=4){
hashi += hitab[f&16rF];
hashl += hltab[hashi&16r3F];
f >>= 4;
}
}
return hashl;
}
delitem(buf: array of byte, n: int)
{
ne := GETS(buf, 0);
if(n < 0 || n >= ne){
sys->fprint(sys->fildes(2), "dbm: bad delitem\n");
raise "dbm: bad delitem";
}
i1 := GETS(buf, n+1);
i2 := PBLKSIZ;
if(n > 0)
i2 = GETS(buf, n+1-1);
i3 := GETS(buf, ne+1-1);
if(i2 > i1)
while(i1 > i3){
i1--;
i2--;
buf[i2] = buf[i1];
buf[i1] = byte 0;
}
i2 -= i1;
for(i1=n+1; i1<ne; i1++)
PUTS(buf, i1+1-1, GETS(buf, i1+1) + i2);
PUTS(buf, 0, ne-1);
PUTS(buf, ne, 0);
}
additem(buf: array of byte, item: Datum): int
{
i1 := PBLKSIZ;
ne := GETS(buf, 0);
if(ne > 0)
i1 = GETS(buf, ne+1-1);
i1 -= len item;
i2 := (ne+2) * SHORTSIZ;
if(i1 <= i2)
return -1;
PUTS(buf, ne+1, i1);
buf[i1:] = item;
PUTS(buf, 0, ne+1);
return ne;
}
chkblk(buf: array of byte)
{
t := PBLKSIZ;
ne := GETS(buf, 0);
for(i:=0; i<ne; i++){
v := GETS(buf, i+1);
if(v > t)
badblk();
t = v;
}
if(t < (ne+1)*SHORTSIZ)
badblk();
}
read(fd: ref Sys->FD, buf: array of byte, n: int)
{
nr := sys->read(fd, buf, n);
if(nr == 0){
for(i := 0; i < len buf; i++)
buf[i] = byte 0;
}else if(nr != n)
raise "dbm: read error: "+sys->sprint("%r");
}
write(fd: ref Sys->FD, buf: array of byte, n: int)
{
if(sys->write(fd, buf, n) != n)
raise "dbm: write error: "+sys->sprint("%r");
}
badblk()
{
sys->fprint(sys->fildes(2), "dbm: bad block\n");
raise "dbm: bad block";
}
GETS(buf: array of byte, sh: int): int
{
sh *= SHORTSIZ;
return (int buf[sh]<<8) | int buf[sh+1];
}
PUTS(buf: array of byte, sh: int, v: int)
{
sh *= SHORTSIZ;
buf[sh] = byte (v>>8);
buf[sh+1] = byte v;
}