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