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 /*
23 * Copyright 2008 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 * University Copyright- Copyright (c) 1982, 1986, 1988
32 * The Regents of the University of California
33 * All Rights Reserved
34 *
35 * University Acknowledgment- Portions of this document are derived from
36 * software developed by the University of California, Berkeley, and its
37 * contributors.
38 */
39
40 #pragma ident "%Z%%M% %I% %E% SMI"
41
42 #include "lint.h"
43 #include <sys/types.h>
44 #include <sys/stat.h>
45 #include <fcntl.h>
46 #include <sys/file.h>
47 #include <stdio.h>
48 #include <stdlib.h>
49 #include <errno.h>
50 #include <ndbm.h>
51 #include <unistd.h>
52 #include <string.h>
53 #include <pthread.h>
54
55 /* add support for batched writing for NIS */
56
57 #define _DBM_DEFWRITE 0x4
58 #define _DBM_DIRTY 0x8
59 #define _DBM_DIRDIRTY 0x10
60 #define dbm_dirty(db) ((db)->dbm_flags & _DBM_DIRTY)
61 #define dbm_dirdirty(db) ((db)->dbm_flags & _DBM_DIRDIRTY)
62 #define dbm_defwrite(db) ((db)->dbm_flags & _DBM_DEFWRITE)
63 #define dbm_setdirty(db) (db)->dbm_flags |= _DBM_DIRTY
64 #define dbm_clrdirty(db) (db)->dbm_flags &= ~_DBM_DIRTY
65 #define dbm_setdirdirty(db) (db)->dbm_flags |= _DBM_DIRDIRTY
66 #define dbm_clrdirdirty(db) (db)->dbm_flags &= ~_DBM_DIRDIRTY
67
68 /*
69 * forward declarations
70 */
71 static datum makdatum(char *, int);
72 static unsigned long dcalchash(datum);
73 static void dbm_access(DBM *, unsigned long);
74 static int finddatum(char *, datum);
75 static int delitem(char *, int);
76 static int additem(char *, datum, datum);
77 static int cmpdatum(datum, datum);
78 static int setbit(DBM *);
79 static int getbit(DBM *);
80 static int dbm_flushdir(DBM *);
81 static int dbm_flushpag(DBM *db);
82
83 /* the following three are required by mapfile-vers */
84 datum dbm_do_nextkey(DBM *, datum);
85 int dbm_close_status(DBM *);
86
87 /* used to make a dbm file all at once instead of incrementally */
88 void
dbm_setdefwrite(DBM * db)89 dbm_setdefwrite(DBM *db)
90 {
91 db->dbm_flags |= _DBM_DEFWRITE;
92 }
93
94 #undef dbm_error
95
96 int
dbm_error(DBM * db)97 dbm_error(DBM *db)
98 {
99 return (db->dbm_flags & _DBM_IOERR);
100 }
101
102 #undef dbm_clearerr
103
104 int
dbm_clearerr(DBM * db)105 dbm_clearerr(DBM *db)
106 {
107 return (db->dbm_flags &= ~_DBM_IOERR);
108 }
109
110 int
dbm_flush(DBM * db)111 dbm_flush(DBM *db)
112 {
113 int ok = 0;
114 if (dbm_flushpag(db) < 0)
115 ok = -1;
116 if (dbm_flushdir(db) < 0)
117 ok = -1;
118 return (ok);
119 }
120
121 static int
dbm_flushpag(DBM * db)122 dbm_flushpag(DBM *db)
123 {
124 int ok = 0;
125 off64_t where;
126
127 if (dbm_dirty(db)) { /* must page out the page */
128 where = (((off64_t)db->dbm_pagbno) * PBLKSIZ);
129 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
130 (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
131 db->dbm_flags |= _DBM_IOERR;
132 ok = -1;
133 }
134 dbm_clrdirty(db);
135 }
136 return (ok);
137 }
138
139 static int
dbm_flushdir(DBM * db)140 dbm_flushdir(DBM *db)
141 {
142 int ok = 0;
143 off64_t where;
144 if (dbm_dirdirty(db)) { /* must page out the dir */
145 where = (((off64_t)db->dbm_dirbno) * DBLKSIZ);
146 if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
147 (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)) {
148 ok = -1;
149 }
150 dbm_clrdirdirty(db);
151 }
152 return (ok);
153 }
154
155 #define BYTESIZ 8
156 #undef setbit
157
158 DBM *
dbm_open(const char * file,int flags,mode_t mode)159 dbm_open(const char *file, int flags, mode_t mode)
160 {
161 struct stat64 statb;
162 DBM *db;
163 int serrno;
164
165 if ((db = (DBM *)malloc(sizeof (*db))) == 0) {
166 errno = ENOMEM;
167 return ((DBM *)0);
168 }
169 db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
170 if ((flags & 03) == O_WRONLY)
171 flags = (flags & ~03) | O_RDWR;
172 if (strlcpy(db->dbm_pagbuf, file, sizeof (db->dbm_pagbuf)) >=
173 sizeof (db->dbm_pagbuf) ||
174 strlcat(db->dbm_pagbuf, ".pag", sizeof (db->dbm_pagbuf)) >=
175 sizeof (db->dbm_pagbuf)) {
176 /*
177 * file.pag does not fit into dbm_pagbuf.
178 * fail with ENAMETOOLONG.
179 */
180 serrno = ENAMETOOLONG;
181 goto bad;
182 }
183 db->dbm_pagf = open64(db->dbm_pagbuf, flags, mode);
184 if (db->dbm_pagf < 0) {
185 serrno = errno;
186 goto bad;
187 }
188 /*
189 * We know this won't overflow so it is safe to ignore the
190 * return value; we use strl* to prevent false hits in
191 * code sweeps.
192 */
193 (void) strlcpy(db->dbm_pagbuf, file, sizeof (db->dbm_pagbuf));
194 (void) strlcat(db->dbm_pagbuf, ".dir", sizeof (db->dbm_pagbuf));
195 db->dbm_dirf = open64(db->dbm_pagbuf, flags, mode);
196 if (db->dbm_dirf < 0) {
197 serrno = errno;
198 goto bad1;
199 }
200 (void) fstat64(db->dbm_dirf, &statb);
201 db->dbm_maxbno = statb.st_size * BYTESIZ-1;
202 db->dbm_pagbno = db->dbm_dirbno = -1;
203 return (db);
204 bad1:
205 (void) close(db->dbm_pagf);
206 bad:
207 free((char *)db);
208 errno = serrno;
209 return ((DBM *)0);
210 }
211
212 void
dbm_close(DBM * db)213 dbm_close(DBM *db)
214 {
215 (void) dbm_close_status(db);
216 }
217
218 /* close with return code */
219 int
dbm_close_status(DBM * db)220 dbm_close_status(DBM *db)
221 {
222 int ok;
223 ok = 0;
224
225 if (dbm_flush(db) < 0)
226 ok = -1;
227 if (close(db->dbm_dirf) < 0)
228 ok = -1;
229 if (close(db->dbm_pagf) < 0)
230 ok = -1;
231 free((char *)db);
232 return (ok);
233 }
234
235 long
dbm_forder(DBM * db,datum key)236 dbm_forder(DBM *db, datum key)
237 {
238 unsigned long hash;
239
240 hash = dcalchash(key);
241 for (db->dbm_hmask = 0; ; db->dbm_hmask = (db->dbm_hmask<<1)+1) {
242 db->dbm_blkno = hash & db->dbm_hmask;
243 db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
244 if (getbit(db) == 0)
245 break;
246 }
247 return (db->dbm_blkno);
248 }
249
250 datum
dbm_fetch(DBM * db,datum key)251 dbm_fetch(DBM *db, datum key)
252 {
253 int i;
254 datum item;
255
256 if (dbm_error(db))
257 goto err;
258 dbm_access(db, dcalchash(key));
259 if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
260 item = makdatum(db->dbm_pagbuf, i+1);
261 if (item.dptr != NULL)
262 return (item);
263 }
264 err:
265 item.dptr = NULL;
266 item.dsize = 0;
267 return (item);
268 }
269
270 int
dbm_delete(DBM * db,datum key)271 dbm_delete(DBM *db, datum key)
272 {
273 int i;
274 off64_t where;
275
276 if (dbm_error(db))
277 return (-1);
278 if (dbm_rdonly(db)) {
279 errno = EPERM;
280 return (-1);
281 }
282 dbm_access(db, dcalchash(key));
283 if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
284 return (-1);
285 if (!delitem(db->dbm_pagbuf, i))
286 goto err;
287 db->dbm_pagbno = db->dbm_blkno;
288 if (dbm_defwrite(db)) {
289 dbm_setdirty(db);
290 } else {
291 where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
292 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
293 (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
294 err:
295 db->dbm_flags |= _DBM_IOERR;
296 return (-1);
297 }
298 }
299 return (0);
300 }
301
302 int
dbm_store(DBM * db,datum key,datum dat,int replace)303 dbm_store(DBM *db, datum key, datum dat, int replace)
304 {
305 int i;
306 datum item, item1;
307 char ovfbuf[PBLKSIZ];
308 unsigned long hashdiff, key_hash, item_hash;
309 off64_t where;
310
311 if (dbm_error(db))
312 return (-1);
313 if (dbm_rdonly(db)) {
314 errno = EPERM;
315 return (-1);
316 }
317 loop:
318 key_hash = dcalchash(key);
319 dbm_access(db, key_hash);
320 if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
321 if (!replace)
322 return (1);
323 if (!delitem(db->dbm_pagbuf, i)) {
324 db->dbm_flags |= _DBM_IOERR;
325 return (-1);
326 }
327 }
328 if (!additem(db->dbm_pagbuf, key, dat))
329 goto split;
330 db->dbm_pagbno = db->dbm_blkno;
331 if (dbm_defwrite(db)) {
332 dbm_setdirty(db);
333 } else {
334 where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
335 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
336 (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
337 db->dbm_flags |= _DBM_IOERR;
338 return (-1);
339 }
340 }
341 return (0);
342 split:
343 hashdiff = 0;
344 if (key.dsize + dat.dsize + 3 * (int)sizeof (short) >= PBLKSIZ) {
345 db->dbm_flags |= _DBM_IOERR;
346 errno = ENOSPC;
347 return (-1);
348 }
349 (void) memset(ovfbuf, 0, PBLKSIZ);
350 for (i = 0; ; ) {
351 item = makdatum(db->dbm_pagbuf, i);
352 if (item.dptr == NULL)
353 break;
354 item_hash = dcalchash(item);
355 if (item_hash != key_hash) {
356 hashdiff++;
357 }
358
359 if (item_hash & (db->dbm_hmask+1)) {
360 item1 = makdatum(db->dbm_pagbuf, i+1);
361 if (item1.dptr == NULL) {
362 /* (void) fprintf(stderr, "ndbm: */
363 /* split not paired\n"); */
364 db->dbm_flags |= _DBM_IOERR;
365 break;
366 }
367 if (!additem(ovfbuf, item, item1) ||
368 !delitem(db->dbm_pagbuf, i)) {
369 db->dbm_flags |= _DBM_IOERR;
370 return (-1);
371 }
372 continue;
373 }
374 i += 2;
375 }
376 db->dbm_pagbno = db->dbm_blkno;
377 where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
378 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
379 (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
380 db->dbm_flags |= _DBM_IOERR;
381 return (-1);
382 }
383 dbm_clrdirty(db); /* clear dirty */
384 where = (((off64_t)db->dbm_blkno + db->dbm_hmask + 1) * PBLKSIZ);
385 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
386 (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ)) {
387 db->dbm_flags |= _DBM_IOERR;
388 return (-1);
389 }
390 if (setbit(db) < 0) {
391 db->dbm_flags |= _DBM_IOERR;
392 return (-1);
393 }
394 if (hashdiff == 0) {
395 db->dbm_flags |= _DBM_IOERR;
396 return (-1);
397 }
398 goto loop;
399 }
400
401 static unsigned long
dbm_hashinc(DBM * db,unsigned long hash)402 dbm_hashinc(DBM *db, unsigned long hash)
403 {
404 long bit;
405
406 hash &= db->dbm_hmask;
407 bit = db->dbm_hmask+1;
408 for (;;) {
409 bit >>= 1;
410 if (bit == 0)
411 return (0L);
412 if ((hash&bit) == 0)
413 return (hash|bit);
414 hash &= ~bit;
415 }
416 }
417
418
419
420 static datum nullkey = {NULL, 0};
421
422 datum
dbm_firsthash(DBM * db,unsigned long hash)423 dbm_firsthash(DBM *db, unsigned long hash)
424 {
425 int i, j;
426 datum item, bitem;
427
428 loop:
429 dbm_access(db, hash);
430 j = 0;
431 bitem = makdatum(db->dbm_pagbuf, 0);
432 for (i = 2; ; i += 2) {
433 item = makdatum(db->dbm_pagbuf, i);
434 if (item.dptr == NULL)
435 break;
436 if (cmpdatum(bitem, item) < 0) {
437 j = i;
438 bitem = item;
439 }
440 }
441 if (bitem.dptr != NULL) {
442 db->dbm_keyptr = j + 2;
443 db->dbm_blkptr = db->dbm_blkno;
444 return (bitem);
445 }
446 hash = dbm_hashinc(db, hash);
447 if (hash == 0)
448 return (item); /* null item */
449 goto loop;
450
451 }
452
453 datum
dbm_firstkey(DBM * db)454 dbm_firstkey(DBM *db)
455 {
456 /*
457 * For some reason, the Posix specification (SUSv3)
458 * says that dbm_firstkey() is not a cancellation point.
459 * It really should be, but in order to pass the SUSv3
460 * test suite we make it not a cancellation point.
461 * XXX: fix me when the SUSv3 specification gets fixed.
462 */
463 int cancel_state;
464 datum rval;
465
466 db->dbm_blkptr = 0L;
467 db->dbm_keyptr = 0;
468 (void) pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cancel_state);
469 rval = dbm_firsthash(db, 0L);
470 (void) pthread_setcancelstate(cancel_state, NULL);
471 return (rval);
472 }
473
474 datum
dbm_nextkey(DBM * db)475 dbm_nextkey(DBM *db)
476 {
477
478 return (dbm_do_nextkey(db, nullkey));
479 }
480
481 /*
482 * this is used if keyptr-2, blocknum doesn't point to the previous
483 * specific key allowing the fast hash order search --
484 * its use indicates user tampering with our state variables,
485 * which some evil users might do to search from some specific place.
486 * It finds the first key at or after blkptr, keyptr in block seq order
487 * this requires looking at all sorts of emtpy blocks in many cases
488 */
489
490 static
491 datum
dbm_slow_nextkey(DBM * db)492 dbm_slow_nextkey(DBM *db)
493 {
494
495 struct stat64 statb;
496 datum item;
497 off64_t where;
498
499 if (dbm_error(db) || fstat64(db->dbm_pagf, &statb) < 0)
500 goto err;
501 statb.st_size /= PBLKSIZ;
502
503 for (;;) {
504 if (db->dbm_blkptr != db->dbm_pagbno) {
505
506 if (dbm_dirty(db)) (void) dbm_flushpag(db);
507
508 db->dbm_pagbno = db->dbm_blkptr;
509 where = (((off64_t)db->dbm_blkptr) * PBLKSIZ);
510 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
511 (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
512 PBLKSIZ))
513 (void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
514 #ifdef DEBUG
515 else if (chkblk(db->dbm_pagbuf) < 0)
516 db->dbm_flags |= _DBM_IOERR;
517 #endif
518 }
519 /* Am I an empty block? */
520 if (((short *)(uintptr_t)db->dbm_pagbuf)[0] != 0) {
521 item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
522 if (item.dptr != NULL) {
523 db->dbm_keyptr += 2;
524 return (item);
525 }
526 db->dbm_keyptr = 0;
527 }
528 /* go to next sequential block */
529 if (++db->dbm_blkptr >= statb.st_size)
530 break;
531 }
532 err:
533 item.dptr = NULL;
534 item.dsize = 0;
535 return (item);
536 }
537
538
539
540 datum
dbm_do_nextkey(DBM * db,datum inkey)541 dbm_do_nextkey(DBM *db, datum inkey)
542 {
543 datum item, bitem;
544 unsigned long hash;
545 datum key;
546 int f;
547 int i;
548 int j;
549 short *sp;
550 long n;
551 char *p1, *p2;
552 off64_t where;
553
554 if (dbm_error(db)) {
555 item.dptr = NULL;
556 item.dsize = 0;
557 return (item);
558 }
559
560 /* user has supplied lastkey */
561
562 if (inkey.dptr != NULL) {
563 dbm_access(db, (hash = dcalchash(inkey)));
564 if ((i = finddatum(db->dbm_pagbuf, inkey)) >= 0) {
565 db->dbm_keyptr = i + 2;
566 db->dbm_blkptr = db->dbm_blkno;
567 }
568 key = inkey;
569 } else {
570 /* is this a manual firstkey request? */
571
572 if (db->dbm_blkptr == 0L &&
573 db->dbm_keyptr == 0)
574 return (dbm_firsthash(db, 0L));
575
576 /* no -- get lastkey this is like dbm_access by blkptr */
577
578 if (db->dbm_blkptr != db->dbm_pagbno) {
579
580 if (dbm_dirty(db)) (void) dbm_flushpag(db);
581 db->dbm_pagbno = db->dbm_blkptr;
582 where = (((off64_t)db->dbm_blkptr) * PBLKSIZ);
583 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
584 (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
585 PBLKSIZ))
586 (void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
587 #ifdef DEBUG
588 else if (chkblk(db->dbm_pagbuf) < 0)
589 db->dbm_flags |= _DBM_IOERR;
590 #endif
591 }
592 /* now just make up last key datum */
593 if (db->dbm_keyptr >= 2)
594 key = makdatum(db->dbm_pagbuf, (db->dbm_keyptr-2));
595 else key = nullkey;
596
597 /*
598 * the keyptr pagbuf have failed us, the user must
599 * be an extra clever moron who depends on
600 * these variables and their former meaning.
601 * If we set the variables this would have got
602 * us the key for sure! So give him the old algorithm.
603 */
604 if (key.dptr == NULL)
605 return (dbm_slow_nextkey(db));
606 }
607
608 /*
609 * at this point the last key is paged in and
610 * we can proceed as in old dbm -- like Ken did his.
611 */
612
613 f = 1;
614 j = 0;
615 sp = (short *)(uintptr_t)db->dbm_pagbuf;
616
617 for (i = 0; ; i += 2) {
618
619 /* begin put makdatum inline */
620
621 if ((unsigned)i >= sp[0]) {
622 item.dptr = NULL;
623 item.dsize = 0;
624 break; /* from below */
625 } else {
626 if (i > 0) item.dsize = sp[i] - sp[i + 1];
627 else item.dsize = PBLKSIZ - sp[i + 1];
628 item.dptr = db->dbm_pagbuf+sp[i + 1];
629 }
630
631 /* item = makdatum(db->dbm_pagbuf, i); */
632 /* end put makdatum inline */
633
634 if (item.dptr == NULL)
635 break;
636 /* inline cmpdatum */
637
638
639 n = key.dsize;
640 if (n != item.dsize) {
641 if ((n - item.dsize) <= 0)
642 continue;
643 } else {
644 if (n == 0) continue;
645 p1 = key.dptr;
646 p2 = item.dptr;
647 do {
648 if (*p1++ != *p2++)
649 if ((*--p1 - *--p2) > 0)
650 goto keep_going;
651 else continue;
652 } while (--n);
653 continue;
654 }
655
656 keep_going:
657
658 /* end inline cmpdatum */
659 /*
660 * if (cmpdatum(key, item) <= 0)
661 * continue;
662 */
663
664 if (f) {
665 bitem = item;
666 j = i;
667 f = 0;
668 } else {
669
670 /* if (cmpdatum(bitem, item) < 0) */
671
672 n = bitem.dsize;
673 if (n != item.dsize) {
674 if ((n - item.dsize) < 0) {
675 bitem = item;
676 j = i;
677 }
678 } else
679 if (n != 0) {
680 p1 = bitem.dptr;
681 p2 = item.dptr;
682 do {
683 if (*p1++ != *p2++) {
684 if ((*--p1 - *--p2) < 0) {
685 bitem = item;
686 j = i;
687 }
688 break;
689 }
690 } while (--n);
691 }
692 }
693 }
694
695 if (f == 0) {
696 db->dbm_keyptr = j + 2;
697 db->dbm_blkptr = db->dbm_blkno;
698 return (bitem);
699 }
700
701 /* really need hash at this point */
702 /* if he gave us a key we have already calculated the hash */
703 /* if not get it */
704 if (inkey.dptr == NULL)
705 hash = dcalchash(key);
706 hash = dbm_hashinc(db, hash);
707
708 if (hash == 0)
709 return (item); /* null */
710 /* get first item on next page in hash table order */
711 return (dbm_firsthash(db, hash));
712
713
714 }
715
716 static void
dbm_access(DBM * db,unsigned long hash)717 dbm_access(DBM *db, unsigned long hash)
718 {
719 long b, i, n;
720 long bn;
721 long my_bitno;
722 long my_hmask;
723 long my_blkno;
724 int j = (sizeof (my_hmask)) * 8;
725 off64_t where;
726
727 for (my_hmask = 0; j-- > 0; my_hmask = (my_hmask<<1) + 1) {
728 my_blkno = hash & my_hmask;
729 my_bitno = my_blkno + my_hmask;
730 /* getbit inline */
731 if (my_bitno > db->dbm_maxbno) break;
732 n = my_bitno % BYTESIZ;
733 bn = my_bitno / BYTESIZ;
734 i = bn % DBLKSIZ;
735 b = bn / DBLKSIZ;
736 if (b != db->dbm_dirbno) {
737 if (dbm_dirdirty(db))
738 (void) dbm_flushdir(db); /* must flush */
739 db->dbm_dirbno = b;
740 where = (((off64_t)b) * DBLKSIZ);
741 if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
742 (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) !=
743 DBLKSIZ))
744 (void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
745 }
746 if ((db->dbm_dirbuf[i] & (1<<n)) == 0) break;
747
748 /*
749 * if (getbit(db) == 0)
750 * break;
751 */
752 }
753 /* copy */
754 db->dbm_blkno = my_blkno;
755 db->dbm_bitno = my_bitno;
756 db->dbm_hmask = my_hmask;
757
758 if (my_blkno != db->dbm_pagbno) {
759 if (dbm_dirty(db)) { /* must page out the page */
760 where = (((off64_t)db->dbm_pagbno) * PBLKSIZ);
761 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
762 (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
763 PBLKSIZ)) {
764 db->dbm_flags |= _DBM_IOERR;
765 }
766 dbm_clrdirty(db);
767 }
768
769 db->dbm_pagbno = my_blkno;
770 where = (((off64_t)my_blkno) * PBLKSIZ);
771 if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
772 (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ))
773 (void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
774 #ifdef DEBUG
775 else if (chkblk(db->dbm_pagbuf) < 0)
776 db->dbm_flags |= _DBM_IOERR;
777 #endif
778 }
779 }
780
781 static int
getbit(DBM * db)782 getbit(DBM *db)
783 {
784 long bn;
785 long b, i, n;
786 off64_t where;
787
788 if (db->dbm_bitno > db->dbm_maxbno)
789 return (0);
790 n = db->dbm_bitno % BYTESIZ;
791 bn = db->dbm_bitno / BYTESIZ;
792 i = bn % DBLKSIZ;
793 b = bn / DBLKSIZ;
794 if (b != db->dbm_dirbno) {
795 if (dbm_dirdirty(db))
796 (void) dbm_flushdir(db); /* must flush */
797 db->dbm_dirbno = b;
798 where = (((off64_t)b) * DBLKSIZ);
799 if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
800 (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ))
801 (void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
802 }
803 return (db->dbm_dirbuf[i] & (1<<n));
804 }
805
806 static int
setbit(DBM * db)807 setbit(DBM *db)
808 {
809 long bn;
810 long i, n, b;
811 off64_t where;
812
813 if (db->dbm_bitno > db->dbm_maxbno)
814 db->dbm_maxbno = db->dbm_bitno;
815 n = db->dbm_bitno % BYTESIZ;
816 bn = db->dbm_bitno / BYTESIZ;
817 i = bn % DBLKSIZ;
818 b = bn / DBLKSIZ;
819 if (b != db->dbm_dirbno) {
820 if (dbm_dirdirty(db))
821 (void) dbm_flushdir(db);
822 db->dbm_dirbno = b;
823 where = (((off64_t)b) * DBLKSIZ);
824 if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
825 (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ))
826 (void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
827 }
828 db->dbm_dirbuf[i] |= 1<<n;
829 db->dbm_dirbno = b;
830 if (dbm_defwrite(db)) {
831 dbm_setdirdirty(db);
832 } else {
833 where = (((off64_t)b) * DBLKSIZ);
834 if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
835 (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)) {
836 return (-1);
837 }
838 }
839 return (0);
840 }
841
842 static datum
makdatum(char buf[PBLKSIZ],int n)843 makdatum(char buf[PBLKSIZ], int n)
844 {
845 short *sp;
846 int t;
847 datum item;
848
849 sp = (short *)(uintptr_t)buf;
850 if ((unsigned)n >= sp[0]) {
851 item.dptr = NULL;
852 item.dsize = 0;
853 return (item);
854 }
855 t = PBLKSIZ;
856 if (n > 0)
857 t = sp[n];
858 item.dptr = buf + sp[n + 1];
859 item.dsize = t - sp[n + 1];
860 return (item);
861 }
862
863 static int
cmpdatum(datum d1,datum d2)864 cmpdatum(datum d1, datum d2)
865 {
866 long n;
867 char *p1, *p2;
868
869 n = d1.dsize;
870 if (n != d2.dsize)
871 return ((int)(n - d2.dsize));
872 if (n == 0)
873 return (0);
874 p1 = d1.dptr;
875 p2 = d2.dptr;
876 do {
877 if (*p1 != *p2)
878 return (*p1 - *p2);
879 else {
880 p1++;
881 p2++;
882 }
883 } while (--n);
884 return (0);
885 }
886
887 static int
finddatum(char buf[PBLKSIZ],datum item)888 finddatum(char buf[PBLKSIZ], datum item)
889 {
890 short *sp;
891 int i, n, j;
892
893 sp = (short *)(uintptr_t)buf;
894 n = PBLKSIZ;
895 for (i = 0, j = sp[0]; i < j; i += 2, n = sp[i]) {
896 n -= sp[i + 1];
897 if (n != item.dsize)
898 continue;
899 if (n == 0 || memcmp(&buf[sp[i+1]], item.dptr, n) == 0)
900 return (i);
901 }
902 return (-1);
903 }
904
905 static const int hitab[16]
906 /*
907 * ken's
908 * {
909 * 055, 043, 036, 054, 063, 014, 004, 005,
910 * 010, 064, 077, 000, 035, 027, 025, 071,
911 * };
912 */
913 = { 61, 57, 53, 49, 45, 41, 37, 33,
914 29, 25, 21, 17, 13, 9, 5, 1,
915 };
916
917 /* could consider to make it 32-bit int table to minimize memory usage */
918 static const long hltab[64]
919 = {
920 06100151277L, 06106161736L, 06452611562L, 05001724107L,
921 02614772546L, 04120731531L, 04665262210L, 07347467531L,
922 06735253126L, 06042345173L, 03072226605L, 01464164730L,
923 03247435524L, 07652510057L, 01546775256L, 05714532133L,
924 06173260402L, 07517101630L, 02431460343L, 01743245566L,
925 00261675137L, 02433103631L, 03421772437L, 04447707466L,
926 04435620103L, 03757017115L, 03641531772L, 06767633246L,
927 02673230344L, 00260612216L, 04133454451L, 00615531516L,
928 06137717526L, 02574116560L, 02304023373L, 07061702261L,
929 05153031405L, 05322056705L, 07401116734L, 06552375715L,
930 06165233473L, 05311063631L, 01212221723L, 01052267235L,
931 06000615237L, 01075222665L, 06330216006L, 04402355630L,
932 01451177262L, 02000133436L, 06025467062L, 07121076461L,
933 03123433522L, 01010635225L, 01716177066L, 05161746527L,
934 01736635071L, 06243505026L, 03637211610L, 01756474365L,
935 04723077174L, 03642763134L, 05750130273L, 03655541561L,
936 };
937
938 static unsigned long
dcalchash(datum item)939 dcalchash(datum item)
940 {
941 long s;
942 int c, j;
943 char *cp;
944 unsigned long hashl;
945 long hashi;
946
947 hashl = 0;
948 hashi = 0;
949 for (cp = item.dptr, s = item.dsize; --s >= 0; ) {
950 c = *cp++;
951 for (j = 0; j < BYTESIZ; j += 4) {
952 hashi += hitab[c&017];
953 hashl += hltab[hashi&63];
954 c >>= 4;
955 }
956 }
957 return (hashl);
958 }
959
960 /*
961 * Delete pairs of items (n & n+1).
962 */
963 static int
delitem(char buf[PBLKSIZ],int n)964 delitem(char buf[PBLKSIZ], int n)
965 {
966 short *sp, *sp1;
967 int i1, i2;
968
969 sp = (short *)(uintptr_t)buf;
970 i2 = sp[0];
971 if ((unsigned)n >= i2 || (n & 1))
972 return (0);
973 if (n == i2-2) {
974 sp[0] -= 2;
975 return (1);
976 }
977 i1 = PBLKSIZ;
978 if (n > 0)
979 i1 = sp[n];
980 i1 -= sp[n+2];
981 if (i1 > 0) {
982 i2 = sp[i2];
983 (void) memmove(&buf[i2 + i1], &buf[i2], sp[n+2] - i2);
984 }
985 sp[0] -= 2;
986 for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
987 sp[0] = sp[2] + i1;
988 return (1);
989 }
990
991 /*
992 * Add pairs of items (item & item1).
993 */
994 static int
additem(char buf[PBLKSIZ],datum item,datum item1)995 additem(char buf[PBLKSIZ], datum item, datum item1)
996 {
997 short *sp;
998 int i1, i2;
999
1000 sp = (short *)(uintptr_t)buf;
1001 i1 = PBLKSIZ;
1002 i2 = sp[0];
1003 if (i2 > 0)
1004 i1 = sp[i2];
1005 i1 -= item.dsize + item1.dsize;
1006 if (i1 <= (i2+3) * (int)sizeof (short))
1007 return (0);
1008 sp[0] += 2;
1009 sp[++i2] = (short)(i1 + item1.dsize);
1010 (void) memmove(&buf[i1 + item1.dsize], item.dptr, item.dsize);
1011 sp[++i2] = i1;
1012 (void) memmove(&buf[i1], item1.dptr, item1.dsize);
1013 return (1);
1014 }
1015
1016 #ifdef DEBUG
1017 static int
chkblk(char buf[PBLKSIZ])1018 chkblk(char buf[PBLKSIZ])
1019 {
1020 short *sp;
1021 int t, i;
1022
1023 sp = (short *)buf;
1024 t = PBLKSIZ;
1025 for (i = 0; i < sp[0]; i++) {
1026 if (sp[i + 1] > t)
1027 return (-1);
1028 t = sp[i + 1];
1029 }
1030 if (t < (sp[0] + 1) * sizeof (short))
1031 return (-1);
1032 return (0);
1033 }
1034 #endif
1035