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;
}