20060303a

1 files changed, 463 insertions, 0 deletions

diff --git a/appl/lib/dbm.b b/appl/lib/dbm.b
new file mode 100644
index 00000000..e6c27630
--- /dev/null
+++ b/appl/lib/dbm.b
@@ -0,0 +1,463 @@
+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;
+}