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