[unix-history] / usr / src / libdbm / dbm.c

#include	"dbm.h"
#include	<sys/types.h>
#include	<sys/stat.h>

dbminit(file)
char *file;
{
	struct stat statb;

	strcpy(pagbuf, file);
	strcat(pagbuf, ".pag");
	pagf = open(pagbuf, 2);

	strcpy(pagbuf, file);
	strcat(pagbuf, ".dir");
	dirf = open(pagbuf, 2);
	if(pagf < 0 || dirf < 0) {
		printf("cannot open database %s\n", file);
		return(-1);
	}
	fstat(dirf, &statb);
	maxbno = statb.st_size*BYTESIZ-1;
	return(0);
}

long
forder(key)
datum key;
{
	long hash;

	hash = calchash(key);
	for(hmask=0;; hmask=(hmask<<1)+1) {
		blkno = hash & hmask;
		bitno = blkno + hmask;
		if(getbit() == 0)
			break;
	}
	return(blkno);
}

datum
fetch(key)
datum key;
{
	register i;
	datum item;

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

delete(key)
datum key;
{
	register i;
	datum item;

	dbm_access(calchash(key));
	for(i=0;; i+=2) {
		item = makdatum(pagbuf, i);
		if(item.dptr == NULL)
			return(-1);
		if(cmpdatum(key, item) == 0) {
			delitem(pagbuf, i);
			delitem(pagbuf, i);
			break;
		}
	}
	lseek(pagf, blkno*PBLKSIZ, 0);
	write(pagf, pagbuf, PBLKSIZ);
	return(0);
}

store(key, dat)
datum key, dat;
{
	register i;
	datum item;
	char ovfbuf[PBLKSIZ];

loop:
	dbm_access(calchash(key));
	for(i=0;; i+=2) {
		item = makdatum(pagbuf, i);
		if(item.dptr == NULL)
			break;
		if(cmpdatum(key, item) == 0) {
			delitem(pagbuf, i);
			delitem(pagbuf, i);
			break;
		}
	}
	i = additem(pagbuf, key);
	if(i < 0)
		goto split;
	if(additem(pagbuf, dat) < 0) {
		delitem(pagbuf, i);
		goto split;
	}
	lseek(pagf, blkno*PBLKSIZ, 0);
	write(pagf, pagbuf, PBLKSIZ);
	return;

split:
	if(key.dsize+dat.dsize+2*sizeof(short) >= PBLKSIZ) {
		printf("entry too big\n");
		return;
	}
	clrbuf(ovfbuf, PBLKSIZ);
	for(i=0;;) {
		item = makdatum(pagbuf, i);
		if(item.dptr == NULL)
			break;
		if(calchash(item) & (hmask+1)) {
			additem(ovfbuf, item);
			delitem(pagbuf, i);
			item = makdatum(pagbuf, i);
			if(item.dptr == NULL) {
				printf("split not paired\n");
				break;
			}
			additem(ovfbuf, item);
			delitem(pagbuf, i);
			continue;
		}
		i += 2;
	}
	lseek(pagf, blkno*PBLKSIZ, 0);
	write(pagf, pagbuf, PBLKSIZ);
	lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
	write(pagf, ovfbuf, PBLKSIZ);
	setbit();
	goto loop;
}

datum
firstkey()
{
	return(firsthash(0L));
}

datum
nextkey(key)
datum key;
{
	register i;
	datum item, bitem;
	long hash;
	int f;

	hash = calchash(key);
	dbm_access(hash);
	f = 1;
	for(i=0;; i+=2) {
		item = makdatum(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(hash);
	if(hash == 0)
		return(item);
	return(firsthash(hash));
}

datum
firsthash(hash)
long hash;
{
	register i;
	datum item, bitem;

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

dbm_access(hash)
long hash;
{
	static long oldb = -1;

	for(hmask=0;; hmask=(hmask<<1)+1) {
		blkno = hash & hmask;
		bitno = blkno + hmask;
		if(getbit() == 0)
			break;
	}
	if(blkno != oldb) {
		clrbuf(pagbuf, PBLKSIZ);
		lseek(pagf, blkno*PBLKSIZ, 0);
		read(pagf, pagbuf, PBLKSIZ);
		chkblk(pagbuf);
		oldb = blkno;
	}
}

getbit()
{
	long bn;
	register b, i, n;
	static oldb = -1;

	if(bitno > maxbno)
		return(0);
	n = bitno % BYTESIZ;
	bn = bitno / BYTESIZ;
	i = bn % DBLKSIZ;
	b = bn / DBLKSIZ;
	if(b != oldb) {
		clrbuf(dirbuf, DBLKSIZ);
		lseek(dirf, (long)b*DBLKSIZ, 0);
		read(dirf, dirbuf, DBLKSIZ);
		oldb = b;
	}
	if(dirbuf[i] & (1<<n))
		return(1);
	return(0);
}

setbit()
{
	long bn;
	register i, n, b;

	if(bitno > maxbno) {
		maxbno = bitno;
		getbit();
	}
	n = bitno % BYTESIZ;
	bn = bitno / BYTESIZ;
	i = bn % DBLKSIZ;
	b = bn / DBLKSIZ;
	dirbuf[i] |= 1<<n;
	lseek(dirf, (long)b*DBLKSIZ, 0);
	write(dirf, dirbuf, DBLKSIZ);
}

clrbuf(cp, n)
register char *cp;
register n;
{

	do
		*cp++ = 0;
	while(--n);
}

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

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

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

long
hashinc(hash)
long hash;
{
	long bit;

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

long
calchash(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);
}

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("bad delitem\n");
	abort();
}

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

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