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