[comp.unix.questions] dbm library from BSD4.3...

dab@msudoc.UUCP (03/13/87)

In an article in Unix Review (February 1987), Ken Arnold said that the
BSD 4.3 release of UNIX contains an improved version of the dbm library.
He also stated that this version has been placed in the public domain.
If that is so, I would be (almost) eternally grateful if someone would
mail me the source so that I can attempt to bring it up on my System V
UNIX.

Thanks.

-- 
David A. Bright
Michigan State University Computer Laboratory Systems Development Group
...!ihnp4!msudoc!dab   		(work)
...!ihnp4!msudoc!dab!dab	(home)

rick@seismo.UUCP (03/15/87)

ALL of the allegedly public domain dbm implementations I have seen
OBVIOUSLY contain ATT code (try diff). This explicitly includes the
4.3BSD DBM code. I have no idea how Arnold  came to the conclusion that
the code was public domain, but he obviously didn't diff the
4.3BSD code with the 32V ATT release. (Berkeley thinks it requires
an ATT license too. I asked.)

I have been looking for a dbm to distribute with the news software for 3
years. I have yet to find one that isn't obviously ATT derived (despite
what the person sending it to me says)

The "heart" of dbm is the hashing code. I've seen the rest of dbm
rewritten several times, but people always "borrow" the ATT hashing code.

---rick

chan@lll-ncis.arpa (Ada Lee Chan) (03/19/87)

In article <1267@msudoc.UUCP> dab@msudoc.UUCP (David A. Bright) writes:
>In an article in Unix Review (February 1987), Ken Arnold said that the
>BSD 4.3 release of UNIX contains an improved version of the dbm library.
>He also stated that this version has been placed in the public domain.
>If that is so, I would be (almost) eternally grateful if someone would
>mail me the source so that I can attempt to bring it up on my System V
>UNIX.
>


I have a newer version of dbm (called ndbm).  It's from Berkeley 4.2
and I suspect it may be included in 4.3.  I'm not sure if it's exactly
what you want, but here it is.  Below ndbm.h is ndbm.c.


/*      ndbm.h     4.2     83/12/20     */

/*
 * (New) Hashed key data base library (-lndbm).
 */
#define PBLKSIZ 1024
#define DBLKSIZ 4096

typedef struct {
	int     db_dirf;                /* open directory file */
	int     db_pagf;                /* open page file */
	int     db_flags;
#define _DB_RDONLY      0x1     /* data base open read-only */
	long    db_maxbno;              /* last ``block'' in page file */
	long    db_bitno;
	long    db_hmask;
	long    db_blkno;               /* current page to read/write */
	long    db_pagbno;              /* current page in pagbuf */
	char    db_pagbuf[PBLKSIZ];     /* page file block buffer */
	long    db_dirbno;              /* current block in dirbuf */
	char    db_dirbuf[DBLKSIZ];     /* directory file block buffer */
} DBM;

#define dbrdonly(db)    ((db)->db_flags&_DB_RDONLY) != 0

typedef struct {
	char    *dptr;
	int     dsize;
} datum;

	/* flags to dbmstore() */
#define DB_INSERT	0
#define DB_REPLACE	1

datum   dbmfetch();
datum   dbmfirstkey();
datum   dbmnextkey();
long    dbmforder();
int     dbmdelete();
int     dbmstore();

DBM     *ndbmopen();
void    ndbmclose();




****************************************************************************
****************************************************************************

	HERE IS ndbm.c !!

****************************************************************************
****************************************************************************

#ifndef lint
static char sccsid[] = "@(#)ndbm.c	4.2 (Berkeley) 12/20/83";
#endif

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/file.h>
#include <errno.h>
#include <ndbm.h>

#define BYTESIZ 8

static  datum firsthash();
static  dbm_access();
static  getbit();
static  setbit();
static  datum makdatum();
static  cmpdatum();
static  long hashinc();
static  long dcalchash();
static  delitem();
static  additem();
static  chkblk();
extern  int errno;

DBM *
ndbmopen(file, flags, mode)
	char *file;
	int flags, mode;
{
	struct stat statb;
	register DBM *db;

	if ((db = (DBM *)malloc(sizeof *db)) == 0) {
		errno = ENOMEM;
		return ((DBM *)0);
	}
	if ((flags & 03) == O_WRONLY)
		flags = (flags & ~03) | O_RDWR;
	db->db_flags = 0;
	strcpy(db->db_pagbuf, file);
	strcat(db->db_pagbuf, ".pag");
	db->db_pagf = open(db->db_pagbuf, flags, mode);
	if (db->db_pagf < 0)
		goto bad;
	strcpy(db->db_pagbuf, file);
	strcat(db->db_pagbuf, ".dir");
	db->db_dirf = open(db->db_pagbuf, flags, mode);
	if (db->db_dirf < 0)
		goto bad1;
	fstat(db->db_dirf, &statb);
	db->db_maxbno = statb.st_size*BYTESIZ-1;
	db->db_pagbno = db->db_dirbno = -1;
	return (db);
bad1:
	(void) close(db->db_pagf);
bad:
	free((char *)db);
	return ((DBM *)0);
}

void
ndbmclose(db)
	DBM *db;
{

	(void) close(db->db_dirf);
	(void) close(db->db_pagf);
	free((char *)db);
}

long
dbmforder(db, key)
	register DBM *db;
	datum key;
{
	long hash;

	hash = dcalchash(key);
	for (db->db_hmask=0;; db->db_hmask=(db->db_hmask<<1)+1) {
		db->db_blkno = hash & db->db_hmask;
		db->db_bitno = db->db_blkno + db->db_hmask;
		if (getbit(db) == 0)
			break;
	}
	return (db->db_blkno);
}

datum
dbmfetch(db, key)
	register DBM *db;
	datum key;
{
	register i;
	datum item;

	dbm_access(db, dcalchash(key));
	for (i=0;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			return (item);
		if (cmpdatum(key, item) == 0) {
			item = makdatum(db->db_pagbuf, i+1);
			if (item.dptr == NULL)
				printf("items not in pairs\n");
			return (item);
		}
	}
}

dbmdelete(db, key)
	register DBM *db;
	datum key;
{
	register i;
	datum item;

	if (dbrdonly(db)) {
		errno = EPERM;
		return (-1);
	}
	dbm_access(db, dcalchash(key));
	for (i=0;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			return (-1);
		if (cmpdatum(key, item) == 0) {
			delitem(db->db_pagbuf, i);
			delitem(db->db_pagbuf, i);
			break;
		}
	}
	(void) lseek(db->db_pagf, db->db_blkno*PBLKSIZ, L_SET);
	(void) write(db->db_pagf, db->db_pagbuf, PBLKSIZ);
	db->db_pagbno = db->db_blkno;
	return (0);
}

dbmstore(db, key, dat, replace)
	register DBM *db;
	datum key, dat;
	int replace;
{
	register i;
	datum item;
	char ovfbuf[PBLKSIZ];

	if (dbrdonly(db)) {
		errno = EPERM;
		return (-1);
	}
loop:
	dbm_access(db, dcalchash(key));
	for (i=0;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			break;
		if (cmpdatum(key, item) == 0) {
			if (!replace)
				return (1);
			delitem(db->db_pagbuf, i);
			delitem(db->db_pagbuf, i);
			break;
		}
	}
	i = additem(db->db_pagbuf, key);
	if (i < 0)
		goto split;
	if (additem(db->db_pagbuf, dat) < 0) {
		delitem(db->db_pagbuf, i);
		goto split;
	}
	(void) lseek(db->db_pagf, db->db_blkno*PBLKSIZ, L_SET);
	(void) write(db->db_pagf, db->db_pagbuf, PBLKSIZ);
	db->db_pagbno = db->db_blkno;
	return (0);

split:
	if (key.dsize+dat.dsize+2*sizeof(short) >= PBLKSIZ) {
		errno = ENOSPC;
		return (-1);
	}
	bzero(ovfbuf, PBLKSIZ);
	for (i=0;;) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			break;
		if (dcalchash(item) & (db->db_hmask+1)) {
			additem(ovfbuf, item);
			delitem(db->db_pagbuf, i);
			item = makdatum(db->db_pagbuf, i);
			if (item.dptr == NULL) {
				printf("ndbm: split not paired\n");
				break;
			}
			additem(ovfbuf, item);
			delitem(db->db_pagbuf, i);
			continue;
		}
		i += 2;
	}
	(void) lseek(db->db_pagf, db->db_blkno*PBLKSIZ, L_SET);
	(void) write(db->db_pagf, db->db_pagbuf, PBLKSIZ);
	db->db_pagbno = db->db_blkno;
	(void) lseek(db->db_pagf, (db->db_blkno+db->db_hmask+1)*PBLKSIZ, L_SET);
	(void) write(db->db_pagf, ovfbuf, PBLKSIZ);
	setbit(db);
	goto loop;
}

datum
dbmfirstkey(db)
	DBM *db;
{

	return (firsthash(db, 0L));
}

datum
dbmnextkey(db, key)
	register DBM *db;
	datum key;
{
	register i;
	datum item, bitem;
	long hash;
	int f;

	hash = dcalchash(key);
	dbm_access(db, hash);
	f = 1;
	for (i=0;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			break;
		if (cmpdatum(key, item) <= 0)
			continue;
		if (f || cmpdatum(bitem, item) < 0) {
			bitem = item;
			f = 0;
		}
	}
	if (f == 0)
		return (bitem);
	hash = hashinc(db, hash);
	if (hash == 0)
		return (item);
	return (firsthash(db, hash));
}

static datum
firsthash(db, hash)
	register DBM *db;
	long hash;
{
	register i;
	datum item, bitem;

loop:
	dbm_access(db, hash);
	bitem = makdatum(db->db_pagbuf, 0);
	for (i=2;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			break;
		if (cmpdatum(bitem, item) < 0)
			bitem = item;
	}
	if (bitem.dptr != NULL)
		return (bitem);
	hash = hashinc(db, hash);
	if (hash == 0)
		return (item);
	goto loop;
}

static
dbm_access(db, hash)
	register DBM *db;
	long hash;
{
	
	for (db->db_hmask=0;; db->db_hmask=(db->db_hmask<<1)+1) {
		db->db_blkno = hash & db->db_hmask;
		db->db_bitno = db->db_blkno + db->db_hmask;
		if (getbit(db) == 0)
			break;
	}
	if (db->db_blkno != db->db_pagbno) {
		bzero(db->db_pagbuf, PBLKSIZ);
		(void) lseek(db->db_pagf, db->db_blkno*PBLKSIZ, L_SET);
		(void) read(db->db_pagf, db->db_pagbuf, PBLKSIZ);
		chkblk(db->db_pagbuf);
		db->db_pagbno = db->db_blkno;
	}
}

static
getbit(db)
	register DBM *db;
{
	long bn;
	register b, i, n;
	

	if (db->db_bitno > db->db_maxbno)
		return (0);
	n = db->db_bitno % BYTESIZ;
	bn = db->db_bitno / BYTESIZ;
	i = bn % DBLKSIZ;
	b = bn / DBLKSIZ;
	if (b != db->db_dirbno) {
		bzero(db->db_dirbuf, DBLKSIZ);
		(void) lseek(db->db_dirf, (long)b*DBLKSIZ, L_SET);
		(void) read(db->db_dirf, db->db_dirbuf, DBLKSIZ);
		db->db_dirbno = b;
	}
	if (db->db_dirbuf[i] & (1<<n))
		return (1);
	return (0);
}

static
setbit(db)
	register DBM *db;
{
	long bn;
	register i, n, b;

	if (dbrdonly(db)) {
		errno = EPERM;
		return (-1);
	}
	if (db->db_bitno > db->db_maxbno) {
		db->db_maxbno = db->db_bitno;
		getbit(db);
	}
	n = db->db_bitno % BYTESIZ;
	bn = db->db_bitno / BYTESIZ;
	i = bn % DBLKSIZ;
	b = bn / DBLKSIZ;
	db->db_dirbuf[i] |= 1<<n;
	(void) lseek(db->db_dirf, (long)b*DBLKSIZ, L_SET);
	(void) write(db->db_dirf, db->db_dirbuf, DBLKSIZ);
	db->db_dirbno = b;
}

static datum
makdatum(buf, n)
	char buf[PBLKSIZ];
{
	register short *sp;
	register t;
	datum item;

	sp = (short *)buf;
	if (n < 0 || n >= sp[0])
		goto null;
	t = PBLKSIZ;
	if (n > 0)
		t = sp[n+1-1];
	item.dptr = buf+sp[n+1];
	item.dsize = t - sp[n+1];
	return (item);

null:
	item.dptr = NULL;
	item.dsize = 0;
	return (item);
}

static
cmpdatum(d1, d2)
	datum d1, d2;
{
	register n;
	register char *p1, *p2;

	n = d1.dsize;
	if (n != d2.dsize)
		return (n - d2.dsize);
	if (n == 0)
		return (0);
	p1 = d1.dptr;
	p2 = d2.dptr;
	do
		if (*p1++ != *p2++)
			return (*--p1 - *--p2);
	while (--n);
	return (0);
}

static  int hitab[16]
/* ken's
{
	055,043,036,054,063,014,004,005,
	010,064,077,000,035,027,025,071,
};
*/
 = {    61, 57, 53, 49, 45, 41, 37, 33,
	29, 25, 21, 17, 13,  9,  5,  1,
};
static  long hltab[64]
 = {
	06100151277L,06106161736L,06452611562L,05001724107L,
	02614772546L,04120731531L,04665262210L,07347467531L,
	06735253126L,06042345173L,03072226605L,01464164730L,
	03247435524L,07652510057L,01546775256L,05714532133L,
	06173260402L,07517101630L,02431460343L,01743245566L,
	00261675137L,02433103631L,03421772437L,04447707466L,
	04435620103L,03757017115L,03641531772L,06767633246L,
	02673230344L,00260612216L,04133454451L,00615531516L,
	06137717526L,02574116560L,02304023373L,07061702261L,
	05153031405L,05322056705L,07401116734L,06552375715L,
	06165233473L,05311063631L,01212221723L,01052267235L,
	06000615237L,01075222665L,06330216006L,04402355630L,
	01451177262L,02000133436L,06025467062L,07121076461L,
	03123433522L,01010635225L,01716177066L,05161746527L,
	01736635071L,06243505026L,03637211610L,01756474365L,
	04723077174L,03642763134L,05750130273L,03655541561L,
};

static long
hashinc(db, hash)
	register DBM *db;
	long hash;
{
	long bit;

	hash &= db->db_hmask;
	bit = db->db_hmask+1;
	for (;;) {
		bit >>= 1;
		if (bit == 0)
			return (0L);
		if ((hash&bit) == 0)
			return (hash|bit);
		hash &= ~bit;
	}
}

static long
dcalchash(item)
	datum item;
{
	register i, j, f;
	long hashl;
	int hashi;

	hashl = 0;
	hashi = 0;
	for (i=0; i<item.dsize; i++) {
		f = item.dptr[i];
		for (j=0; j<BYTESIZ; j+=4) {
			hashi += hitab[f&017];
			hashl += hltab[hashi&63];
			f >>= 4;
		}
	}
	return (hashl);
}

static
delitem(buf, n)
	char buf[PBLKSIZ];
{
	register short *sp;
	register i1, i2, i3;

	sp = (short *)buf;
	if (n < 0 || n >= sp[0])
		goto bad;
	i1 = sp[n+1];
	i2 = PBLKSIZ;
	if (n > 0)
		i2 = sp[n+1-1];
	i3 = sp[sp[0]+1-1];
	if (i2 > i1)
	while (i1 > i3) {
		i1--;
		i2--;
		buf[i2] = buf[i1];
		buf[i1] = 0;
	}
	i2 -= i1;
	for (i1=n+1; i1<sp[0]; i1++)
		sp[i1+1-1] = sp[i1+1] + i2;
	sp[0]--;
	sp[sp[0]+1] = 0;
	return;

bad:
	printf("ndbm: bad delitem\n");
	abort();
}

static
additem(buf, item)
	char buf[PBLKSIZ];
	datum item;
{
	register short *sp;
	register i1, i2;

	sp = (short *)buf;
	i1 = PBLKSIZ;
	if (sp[0] > 0)
		i1 = sp[sp[0]+1-1];
	i1 -= item.dsize;
	i2 = (sp[0]+2) * sizeof(short);
	if (i1 <= i2)
		return (-1);
	sp[sp[0]+1] = i1;
	for (i2=0; i2<item.dsize; i2++) {
		buf[i1] = item.dptr[i2];
		i1++;
	}
	sp[0]++;
	return (sp[0]-1);
}

static
chkblk(buf)
	char buf[PBLKSIZ];
{
	register short *sp;
	register t, i;

	sp = (short *)buf;
	t = PBLKSIZ;
	for (i=0; i<sp[0]; i++) {
		if (sp[i+1] > t)
			goto bad;
		t = sp[i+1];
	}
	if (t < (sp[0]+1)*sizeof(short))
		goto bad;
	return;

bad:
	printf("ndbm: bad block\n");
	abort();
	bzero(buf, PBLKSIZ);
}

rick@seismo.CSS.GOV (Rick Adams) (03/20/87)

In case there is any doubt, this posting (ndbm) DOES contain ATT
proprietary source code. (The hashing function).

I would suggest that you cancel it on your system.

---rick