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