dbm.c revision 1219:f89f56c2d9ac 
1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License").  You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22
23/*
24 * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
25 * Use is subject to license terms.
26 */
27
28/*	Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T */
29/*	  All Rights Reserved   */
30
31/*
32 * Portions of this source code were derived from Berkeley
33 * under license from the Regents of the University of
34 * California.
35 */
36
37#pragma ident	"%Z%%M%	%I%	%E% SMI"
38
39#include "mt.h"
40#include <rpcsvc/dbm.h>
41#include <sys/types.h>
42#include <sys/stat.h>
43#include <string.h>
44#include <unistd.h>
45#include <stdlib.h>
46#include <fcntl.h>
47#include <stdio.h>
48#include <errno.h>
49
50void dbm_access(long);
51void delitem(char *, int);
52void chkblk(char *);
53int  additem(char *, datum);
54int  getbit(void);
55int  setbit(void);
56int  cmpdatum(datum, datum);
57
58int
59dbminit(char *file)
60{
61	struct stat statb;
62
63	dbrdonly = 0;
64	if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) ||
65	    strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) {
66		/*
67		 * file.pag does not fit into pagbuf.
68		 * fails with ENAMETOOLONG.
69		 */
70		errno = ENAMETOOLONG;
71		return (-1);
72	}
73	pagf = open(pagbuf, 2);
74	if (pagf < 0) {
75		pagf = open(pagbuf, 0);
76		dbrdonly = 1;
77	}
78	/*
79	 * We know this won't overflow so it is safe to ignore the
80	 * return value; we use strl* to prevent false hits in
81	 * code sweeps.
82	 */
83	(void) strlcpy(pagbuf, file, sizeof (pagbuf));
84	(void) strlcat(pagbuf, ".dir", sizeof (pagbuf));
85	dirf = open(pagbuf, 2);
86	if (dirf < 0) {
87		dirf = open(pagbuf, 0);
88		dbrdonly = 1;
89	}
90	if (pagf < 0 || dirf < 0)
91		return (-1);
92	(void) fstat(dirf, &statb);
93	maxbno = statb.st_size*BYTESIZ-1;
94	return (0);
95}
96
97static long oldb1 = -1;
98static long oldb2 = -1;
99
100/* Avoid using cached data for subsequent accesses. */
101int
102dbmflush(void)
103{
104	oldb1 = -1;
105	oldb2 = -1;
106	return (0);
107}
108
109/* Clean up after ourself. */
110int
111dbmclose(void)
112{
113	(void) close(pagf);
114	(void) close(dirf);
115	bitno = 0;
116	maxbno = 0;
117	blkno = 0;
118	hmask = 0;
119	oldb1 = -1;
120	oldb2 = -1;
121	return (0);
122}
123
124long
125forder(datum key)
126{
127	long hash;
128
129	hash = calchash(key);
130	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
131		blkno = hash & hmask;
132		bitno = blkno + hmask;
133		if (getbit() == 0)
134			break;
135	}
136	return (blkno);
137}
138
139datum
140fetch(datum key)
141{
142	int i;
143	datum item;
144
145	dbm_access(calchash(key));
146	for (i = 0; ; i += 2) {
147		item = makdatum(pagbuf, i);
148		if (item.dptr == NULL) {
149			return (item);
150		}
151		if (cmpdatum(key, item) == 0) {
152			item = makdatum(pagbuf, i+1);
153			if (item.dptr == NULL)
154				(void) printf("items not in pairs\n");
155			return (item);
156		}
157	}
158}
159
160int
161delete(datum key)
162{
163	int i;
164	datum item;
165
166	if (dbrdonly)
167		return (-1);
168	dbm_access(calchash(key));
169	for (i = 0; ; i += 2) {
170		item = makdatum(pagbuf, i);
171		if (item.dptr == NULL)
172			return (-1);
173		if (cmpdatum(key, item) == 0) {
174			delitem(pagbuf, i);
175			delitem(pagbuf, i);
176			break;
177		}
178	}
179	(void) lseek(pagf, blkno*PBLKSIZ, 0);
180	(void) write(pagf, pagbuf, PBLKSIZ);
181	return (0);
182}
183
184int
185store(datum key, datum dat)
186{
187	int i;
188	datum item;
189	char ovfbuf[PBLKSIZ];
190
191	if (dbrdonly)
192		return (-1);
193loop:
194	dbm_access(calchash(key));
195	for (i = 0; ; i += 2) {
196		item = makdatum(pagbuf, i);
197		if (item.dptr == NULL)
198			break;
199		if (cmpdatum(key, item) == 0) {
200			delitem(pagbuf, i);
201			delitem(pagbuf, i);
202			break;
203		}
204	}
205	i = additem(pagbuf, key);
206	if (i < 0)
207		goto split;
208	if (additem(pagbuf, dat) < 0) {
209		delitem(pagbuf, i);
210		goto split;
211	}
212	(void) lseek(pagf, blkno*PBLKSIZ, 0);
213	(void) write(pagf, pagbuf, PBLKSIZ);
214	return (0);
215
216split:
217	if (key.dsize + dat.dsize + 3 * sizeof (short) >= PBLKSIZ) {
218		(void) printf("entry too big\n");
219		return (-1);
220	}
221	(void) memset(&ovfbuf, 0, PBLKSIZ);
222	for (i = 0; ; ) {
223		item = makdatum(pagbuf, i);
224		if (item.dptr == NULL)
225			break;
226		if (calchash(item) & (hmask+1)) {
227			(void) additem(ovfbuf, item);
228			delitem(pagbuf, i);
229			item = makdatum(pagbuf, i);
230			if (item.dptr == NULL) {
231				(void) printf("split not paired\n");
232				break;
233			}
234			(void) additem(ovfbuf, item);
235			delitem(pagbuf, i);
236			continue;
237		}
238		i += 2;
239	}
240	(void) lseek(pagf, blkno*PBLKSIZ, 0);
241	if (write(pagf, pagbuf, PBLKSIZ) < 0) {
242		return (-1);
243	}
244	(void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
245	if (write(pagf, ovfbuf, PBLKSIZ) < 0) {
246		return (-1);
247	}
248	if (setbit() < 0) {
249		return (-1);
250	}
251	goto loop;
252}
253
254datum
255firstkey(void)
256{
257	return (firsthash(0L));
258}
259
260datum
261nextkey(datum key)
262{
263	int i;
264	datum item, bitem;
265	long hash;
266	int f;
267
268#ifdef lint
269	bitem.dptr = NULL;
270	bitem.dsize = 0;
271#endif /* lint */
272	hash = calchash(key);
273	dbm_access(hash);
274	f = 1;
275	for (i = 0; ; i += 2) {
276		item = makdatum(pagbuf, i);
277		if (item.dptr == NULL)
278			break;
279		if (cmpdatum(key, item) <= 0)
280			continue;
281		if (f || cmpdatum(bitem, item) < 0) {
282			bitem = item;
283			f = 0;
284		}
285	}
286	if (f == 0)
287		return (bitem);
288	hash = hashinc(hash);
289	if (hash == 0)
290		return (item);
291	return (firsthash(hash));
292}
293
294datum
295firsthash(long hash)
296{
297	int i;
298	datum item, bitem;
299
300loop:
301	dbm_access(hash);
302	bitem = makdatum(pagbuf, 0);
303	for (i = 2; ; i += 2) {
304		item = makdatum(pagbuf, i);
305		if (item.dptr == NULL)
306			break;
307		if (cmpdatum(bitem, item) < 0)
308			bitem = item;
309	}
310	if (bitem.dptr != NULL)
311		return (bitem);
312	hash = hashinc(hash);
313	if (hash == 0)
314		return (item);
315	goto loop;
316}
317
318void
319dbm_access(long hash)
320{
321	ssize_t readsize;
322
323	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
324		blkno = hash & hmask;
325		bitno = blkno + hmask;
326		if (getbit() == 0)
327			break;
328	}
329	if (blkno != oldb1) {
330		(void) lseek(pagf, blkno*PBLKSIZ, 0);
331		readsize = read(pagf, pagbuf, PBLKSIZ);
332		if (readsize != PBLKSIZ) {
333			if (readsize < 0)
334				readsize = 0;
335			(void) memset((&pagbuf+readsize), 0, PBLKSIZ-readsize);
336		}
337		chkblk(pagbuf);
338		oldb1 = blkno;
339	}
340}
341
342int
343getbit(void)
344{
345	long bn;
346	ssize_t readsize;
347	long b, i, n;
348
349	if (bitno > maxbno)
350		return (0);
351	n = bitno % BYTESIZ;
352	bn = bitno / BYTESIZ;
353	i = bn % DBLKSIZ;
354	b = bn / DBLKSIZ;
355	if (b != oldb2) {
356		(void) lseek(dirf, (long)b*DBLKSIZ, 0);
357		readsize = read(dirf, dirbuf, DBLKSIZ);
358		if (readsize != DBLKSIZ) {
359			if (readsize < 0)
360				readsize = 0;
361			(void) memset(&dirbuf+readsize, 0, DBLKSIZ-readsize);
362		}
363		oldb2 = b;
364	}
365	if (dirbuf[i] & (1<<n))
366		return (1);
367	return (0);
368}
369
370int
371setbit(void)
372{
373	long bn;
374	long i, n, b;
375
376	if (dbrdonly)
377		return (-1);
378	if (bitno > maxbno) {
379		maxbno = bitno;
380		(void) getbit();
381	}
382	n = bitno % BYTESIZ;
383	bn = bitno / BYTESIZ;
384	i = bn % DBLKSIZ;
385	b = bn / DBLKSIZ;
386	dirbuf[i] |= 1<<n;
387	(void) lseek(dirf, (long)b*DBLKSIZ, 0);
388	if (write(dirf, dirbuf, DBLKSIZ) < 0)
389		return (-1);
390	return (0);
391}
392
393datum
394makdatum(char buf[PBLKSIZ], int n)
395{
396	short *sp;
397	int t;
398	datum item;
399
400	/* LINTED pointer cast */
401	sp = (short *)buf;
402	if (n < 0 || n >= sp[0])
403		goto null;
404	t = PBLKSIZ;
405	if (n > 0)
406		t = sp[n+1-1];
407	item.dptr = buf+sp[n+1];
408	item.dsize = t - sp[n+1];
409	return (item);
410
411null:
412	item.dptr = NULL;
413	item.dsize = 0;
414	return (item);
415}
416
417int
418cmpdatum(datum d1, datum d2)
419{
420	int n;
421	char *p1, *p2;
422
423	n = d1.dsize;
424	if (n != d2.dsize)
425		return (n - d2.dsize);
426	if (n == 0)
427		return (0);
428	p1 = d1.dptr;
429	p2 = d2.dptr;
430	do
431		if (*p1++ != *p2++)
432			return (*--p1 - *--p2);
433	while (--n);
434	return (0);
435}
436
437int	hitab[16]
438/*
439 * ken's
440 * {
441 *	055, 043, 036, 054, 063, 014, 004, 005,
442 *	010, 064, 077, 000, 035, 027, 025, 071,
443 * };
444 */
445	= {	61, 57, 53, 49, 45, 41, 37, 33,
446	29, 25, 21, 17, 13,  9,  5,  1,
447};
448long	hltab[64]
449	= {
450	06100151277L, 06106161736L, 06452611562L, 05001724107L,
451	02614772546L, 04120731531L, 04665262210L, 07347467531L,
452	06735253126L, 06042345173L, 03072226605L, 01464164730L,
453	03247435524L, 07652510057L, 01546775256L, 05714532133L,
454	06173260402L, 07517101630L, 02431460343L, 01743245566L,
455	00261675137L, 02433103631L, 03421772437L, 04447707466L,
456	04435620103L, 03757017115L, 03641531772L, 06767633246L,
457	02673230344L, 00260612216L, 04133454451L, 00615531516L,
458	06137717526L, 02574116560L, 02304023373L, 07061702261L,
459	05153031405L, 05322056705L, 07401116734L, 06552375715L,
460	06165233473L, 05311063631L, 01212221723L, 01052267235L,
461	06000615237L, 01075222665L, 06330216006L, 04402355630L,
462	01451177262L, 02000133436L, 06025467062L, 07121076461L,
463	03123433522L, 01010635225L, 01716177066L, 05161746527L,
464	01736635071L, 06243505026L, 03637211610L, 01756474365L,
465	04723077174L, 03642763134L, 05750130273L, 03655541561L,
466};
467
468long
469hashinc(long hash)
470{
471	long bit;
472
473	hash &= hmask;
474	bit = hmask+1;
475	for (; ; ) {
476		bit >>= 1;
477		if (bit == 0)
478			return (0L);
479		if ((hash&bit) == 0)
480			return (hash|bit);
481		hash &= ~bit;
482	}
483}
484
485long
486calchash(datum item)
487{
488	int i, j, f;
489	long hashl;
490	int hashi;
491
492	hashl = 0;
493	hashi = 0;
494	for (i = 0; i < item.dsize; i++) {
495		f = item.dptr[i];
496		for (j = 0; j < BYTESIZ; j += 4) {
497			hashi += hitab[f&017];
498			hashl += hltab[hashi&63];
499			f >>= 4;
500		}
501	}
502	return (hashl);
503}
504
505void
506delitem(char buf[PBLKSIZ], int n)
507{
508	short *sp;
509	int i1, i2, i3;
510
511	/* LINTED pointer cast */
512	sp = (short *)buf;
513	if (n < 0 || n >= sp[0])
514		goto bad;
515	i1 = sp[n+1];
516	i2 = PBLKSIZ;
517	if (n > 0)
518		i2 = sp[n+1-1];
519	i3 = sp[sp[0]+1-1];
520	if (i2 > i1)
521	while (i1 > i3) {
522		i1--;
523		i2--;
524		buf[i2] = buf[i1];
525		buf[i1] = 0;
526	}
527	i2 -= i1;
528	for (i1 = n + 1; i1 < sp[0]; i1++)
529		sp[i1+1-1] = sp[i1+1] + i2;
530	sp[0]--;
531	sp[sp[0]+1] = 0;
532	return;
533
534bad:
535	(void) printf("bad delitem\n");
536	abort();
537}
538
539int
540additem(char buf[PBLKSIZ], datum item)
541{
542	short *sp;
543	int i1, i2;
544
545	/* LINTED pointer cast */
546	sp = (short *)buf;
547	i1 = PBLKSIZ;
548	if (sp[0] > 0)
549		i1 = sp[sp[0]+1-1];
550	i1 -= item.dsize;
551	i2 = (sp[0]+2) * (int)sizeof (short);
552	if (i1 <= i2)
553		return (-1);
554	sp[sp[0]+1] = (short)i1;
555	for (i2 = 0; i2 < item.dsize; i2++) {
556		buf[i1] = item.dptr[i2];
557		i1++;
558	}
559	sp[0]++;
560	return (sp[0]-1);
561}
562
563void
564chkblk(char buf[PBLKSIZ])
565{
566	short *sp;
567	int t, i;
568
569	/* LINTED pointer cast */
570	sp = (short *)buf;
571	t = PBLKSIZ;
572	for (i = 0; i < sp[0]; i++) {
573		if (sp[i+1] > t)
574			goto bad;
575		t = sp[i+1];
576	}
577	if (t < (sp[0]+1) * sizeof (short))
578		goto bad;
579	return;
580
581bad:
582	(void) printf("bad block\n");
583	abort();
584	(void) memset(&buf, 0, PBLKSIZ);
585}
586