1 /*-
2 * Copyright (c) 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Margo Seltzer.
7 *
8 * %sccs.include.redist.c%
9 */
10
11 #if defined(LIBC_SCCS) && !defined(lint)
12 static char sccsid[] = "@(#)hash_page.c 8.4 (Berkeley) 02/21/94";
13 #endif /* LIBC_SCCS and not lint */
14
15 /*
16 * PACKAGE: hashing
17 *
18 * DESCRIPTION:
19 * Page manipulation for hashing package.
20 *
21 * ROUTINES:
22 *
23 * External
24 * __get_page
25 * __add_ovflpage
26 * Internal
27 * overflow_page
28 * open_temp
29 */
30
31 #include <sys/types.h>
32
33 #include <errno.h>
34 #include <fcntl.h>
35 #include <signal.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39 #include <unistd.h>
40 #ifdef DEBUG
41 #include <assert.h>
42 #endif
43
44 #include <db.h>
45 #include "hash.h"
46 #include "page.h"
47 #include "extern.h"
48
49 static u_long *fetch_bitmap __P((HTAB *, int));
50 static u_long first_free __P((u_long));
51 static int open_temp __P((HTAB *));
52 static u_short overflow_page __P((HTAB *));
53 static void putpair __P((char *, const DBT *, const DBT *));
54 static void squeeze_key __P((u_short *, const DBT *, const DBT *));
55 static int ugly_split
56 __P((HTAB *, u_int, BUFHEAD *, BUFHEAD *, int, int));
57
58 #define PAGE_INIT(P) { \
59 ((u_short *)(P))[0] = 0; \
60 ((u_short *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_short); \
61 ((u_short *)(P))[2] = hashp->BSIZE; \
62 }
63
64 /*
65 * This is called AFTER we have verified that there is room on the page for
66 * the pair (PAIRFITS has returned true) so we go right ahead and start moving
67 * stuff on.
68 */
69 static void
putpair(p,key,val)70 putpair(p, key, val)
71 char *p;
72 const DBT *key, *val;
73 {
74 register u_short *bp, n, off;
75
76 bp = (u_short *)p;
77
78 /* Enter the key first. */
79 n = bp[0];
80
81 off = OFFSET(bp) - key->size;
82 memmove(p + off, key->data, key->size);
83 bp[++n] = off;
84
85 /* Now the data. */
86 off -= val->size;
87 memmove(p + off, val->data, val->size);
88 bp[++n] = off;
89
90 /* Adjust page info. */
91 bp[0] = n;
92 bp[n + 1] = off - ((n + 3) * sizeof(u_short));
93 bp[n + 2] = off;
94 }
95
96 /*
97 * Returns:
98 * 0 OK
99 * -1 error
100 */
101 extern int
102 __delpair(hashp, bufp, ndx)
103 HTAB *hashp;
104 BUFHEAD *bufp;
105 register int ndx;
106 {
107 register u_short *bp, newoff;
108 register int n;
109 u_short pairlen;
110
111 bp = (u_short *)bufp->page;
112 n = bp[0];
113
114 if (bp[ndx + 1] < REAL_KEY)
115 return (__big_delete(hashp, bufp));
116 if (ndx != 1)
117 newoff = bp[ndx - 1];
118 else
119 newoff = hashp->BSIZE;
120 pairlen = newoff - bp[ndx + 1];
121
122 if (ndx != (n - 1)) {
123 /* Hard Case -- need to shuffle keys */
124 register int i;
125 register char *src = bufp->page + (int)OFFSET(bp);
126 register char *dst = src + (int)pairlen;
127 memmove(dst, src, bp[ndx + 1] - OFFSET(bp));
128
129 /* Now adjust the pointers */
130 for (i = ndx + 2; i <= n; i += 2) {
131 if (bp[i + 1] == OVFLPAGE) {
132 bp[i - 2] = bp[i];
133 bp[i - 1] = bp[i + 1];
134 } else {
135 bp[i - 2] = bp[i] + pairlen;
136 bp[i - 1] = bp[i + 1] + pairlen;
137 }
138 }
139 }
140 /* Finally adjust the page data */
141 bp[n] = OFFSET(bp) + pairlen;
142 bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_short);
143 bp[0] = n - 2;
144 hashp->NKEYS--;
145
146 bufp->flags |= BUF_MOD;
147 return (0);
148 }
149 /*
150 * Returns:
151 * 0 ==> OK
152 * -1 ==> Error
153 */
154 extern int
155 __split_page(hashp, obucket, nbucket)
156 HTAB *hashp;
157 u_int obucket, nbucket;
158 {
159 register BUFHEAD *new_bufp, *old_bufp;
160 register u_short *ino;
161 register char *np;
162 DBT key, val;
163 int n, ndx, retval;
164 u_short copyto, diff, off, moved;
165 char *op;
166
167 copyto = (u_short)hashp->BSIZE;
168 off = (u_short)hashp->BSIZE;
169 old_bufp = __get_buf(hashp, obucket, NULL, 0);
170 if (old_bufp == NULL)
171 return (-1);
172 new_bufp = __get_buf(hashp, nbucket, NULL, 0);
173 if (new_bufp == NULL)
174 return (-1);
175
176 old_bufp->flags |= (BUF_MOD | BUF_PIN);
177 new_bufp->flags |= (BUF_MOD | BUF_PIN);
178
179 ino = (u_short *)(op = old_bufp->page);
180 np = new_bufp->page;
181
182 moved = 0;
183
184 for (n = 1, ndx = 1; n < ino[0]; n += 2) {
185 if (ino[n + 1] < REAL_KEY) {
186 retval = ugly_split(hashp, obucket, old_bufp, new_bufp,
187 (int)copyto, (int)moved);
188 old_bufp->flags &= ~BUF_PIN;
189 new_bufp->flags &= ~BUF_PIN;
190 return (retval);
191
192 }
193 key.data = (u_char *)op + ino[n];
194 key.size = off - ino[n];
195
196 if (__call_hash(hashp, key.data, key.size) == obucket) {
197 /* Don't switch page */
198 diff = copyto - off;
199 if (diff) {
200 copyto = ino[n + 1] + diff;
201 memmove(op + copyto, op + ino[n + 1],
202 off - ino[n + 1]);
203 ino[ndx] = copyto + ino[n] - ino[n + 1];
204 ino[ndx + 1] = copyto;
205 } else
206 copyto = ino[n + 1];
207 ndx += 2;
208 } else {
209 /* Switch page */
210 val.data = (u_char *)op + ino[n + 1];
211 val.size = ino[n] - ino[n + 1];
212 putpair(np, &key, &val);
213 moved += 2;
214 }
215
216 off = ino[n + 1];
217 }
218
219 /* Now clean up the page */
220 ino[0] -= moved;
221 FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0] + 3);
222 OFFSET(ino) = copyto;
223
224 #ifdef DEBUG3
225 (void)fprintf(stderr, "split %d/%d\n",
226 ((u_short *)np)[0] / 2,
227 ((u_short *)op)[0] / 2);
228 #endif
229 /* unpin both pages */
230 old_bufp->flags &= ~BUF_PIN;
231 new_bufp->flags &= ~BUF_PIN;
232 return (0);
233 }
234
235 /*
236 * Called when we encounter an overflow or big key/data page during split
237 * handling. This is special cased since we have to begin checking whether
238 * the key/data pairs fit on their respective pages and because we may need
239 * overflow pages for both the old and new pages.
240 *
241 * The first page might be a page with regular key/data pairs in which case
242 * we have a regular overflow condition and just need to go on to the next
243 * page or it might be a big key/data pair in which case we need to fix the
244 * big key/data pair.
245 *
246 * Returns:
247 * 0 ==> success
248 * -1 ==> failure
249 */
250 static int
ugly_split(hashp,obucket,old_bufp,new_bufp,copyto,moved)251 ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved)
252 HTAB *hashp;
253 u_int obucket; /* Same as __split_page. */
254 BUFHEAD *old_bufp, *new_bufp;
255 int copyto; /* First byte on page which contains key/data values. */
256 int moved; /* Number of pairs moved to new page. */
257 {
258 register BUFHEAD *bufp; /* Buffer header for ino */
259 register u_short *ino; /* Page keys come off of */
260 register u_short *np; /* New page */
261 register u_short *op; /* Page keys go on to if they aren't moving */
262
263 BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */
264 DBT key, val;
265 SPLIT_RETURN ret;
266 u_short n, off, ov_addr, scopyto;
267 char *cino; /* Character value of ino */
268
269 bufp = old_bufp;
270 ino = (u_short *)old_bufp->page;
271 np = (u_short *)new_bufp->page;
272 op = (u_short *)old_bufp->page;
273 last_bfp = NULL;
274 scopyto = (u_short)copyto; /* ANSI */
275
276 n = ino[0] - 1;
277 while (n < ino[0]) {
278 if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) {
279 if (__big_split(hashp, old_bufp,
280 new_bufp, bufp, bufp->addr, obucket, &ret))
281 return (-1);
282 old_bufp = ret.oldp;
283 if (!old_bufp)
284 return (-1);
285 op = (u_short *)old_bufp->page;
286 new_bufp = ret.newp;
287 if (!new_bufp)
288 return (-1);
289 np = (u_short *)new_bufp->page;
290 bufp = ret.nextp;
291 if (!bufp)
292 return (0);
293 cino = (char *)bufp->page;
294 ino = (u_short *)cino;
295 last_bfp = ret.nextp;
296 } else if (ino[n + 1] == OVFLPAGE) {
297 ov_addr = ino[n];
298 /*
299 * Fix up the old page -- the extra 2 are the fields
300 * which contained the overflow information.
301 */
302 ino[0] -= (moved + 2);
303 FREESPACE(ino) =
304 scopyto - sizeof(u_short) * (ino[0] + 3);
305 OFFSET(ino) = scopyto;
306
307 bufp = __get_buf(hashp, ov_addr, bufp, 0);
308 if (!bufp)
309 return (-1);
310
311 ino = (u_short *)bufp->page;
312 n = 1;
313 scopyto = hashp->BSIZE;
314 moved = 0;
315
316 if (last_bfp)
317 __free_ovflpage(hashp, last_bfp);
318 last_bfp = bufp;
319 }
320 /* Move regular sized pairs of there are any */
321 off = hashp->BSIZE;
322 for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {
323 cino = (char *)ino;
324 key.data = (u_char *)cino + ino[n];
325 key.size = off - ino[n];
326 val.data = (u_char *)cino + ino[n + 1];
327 val.size = ino[n] - ino[n + 1];
328 off = ino[n + 1];
329
330 if (__call_hash(hashp, key.data, key.size) == obucket) {
331 /* Keep on old page */
332 if (PAIRFITS(op, (&key), (&val)))
333 putpair((char *)op, &key, &val);
334 else {
335 old_bufp =
336 __add_ovflpage(hashp, old_bufp);
337 if (!old_bufp)
338 return (-1);
339 op = (u_short *)old_bufp->page;
340 putpair((char *)op, &key, &val);
341 }
342 old_bufp->flags |= BUF_MOD;
343 } else {
344 /* Move to new page */
345 if (PAIRFITS(np, (&key), (&val)))
346 putpair((char *)np, &key, &val);
347 else {
348 new_bufp =
349 __add_ovflpage(hashp, new_bufp);
350 if (!new_bufp)
351 return (-1);
352 np = (u_short *)new_bufp->page;
353 putpair((char *)np, &key, &val);
354 }
355 new_bufp->flags |= BUF_MOD;
356 }
357 }
358 }
359 if (last_bfp)
360 __free_ovflpage(hashp, last_bfp);
361 return (0);
362 }
363
364 /*
365 * Add the given pair to the page
366 *
367 * Returns:
368 * 0 ==> OK
369 * 1 ==> failure
370 */
371 extern int
372 __addel(hashp, bufp, key, val)
373 HTAB *hashp;
374 BUFHEAD *bufp;
375 const DBT *key, *val;
376 {
377 register u_short *bp, *sop;
378 int do_expand;
379
380 bp = (u_short *)bufp->page;
381 do_expand = 0;
382 while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY))
383 /* Exception case */
384 if (bp[2] == FULL_KEY_DATA && bp[0] == 2)
385 /* This is the last page of a big key/data pair
386 and we need to add another page */
387 break;
388 else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) {
389 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
390 if (!bufp)
391 return (-1);
392 bp = (u_short *)bufp->page;
393 } else
394 /* Try to squeeze key on this page */
395 if (FREESPACE(bp) > PAIRSIZE(key, val)) {
396 squeeze_key(bp, key, val);
397 return (0);
398 } else {
399 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
400 if (!bufp)
401 return (-1);
402 bp = (u_short *)bufp->page;
403 }
404
405 if (PAIRFITS(bp, key, val))
406 putpair(bufp->page, key, val);
407 else {
408 do_expand = 1;
409 bufp = __add_ovflpage(hashp, bufp);
410 if (!bufp)
411 return (-1);
412 sop = (u_short *)bufp->page;
413
414 if (PAIRFITS(sop, key, val))
415 putpair((char *)sop, key, val);
416 else
417 if (__big_insert(hashp, bufp, key, val))
418 return (-1);
419 }
420 bufp->flags |= BUF_MOD;
421 /*
422 * If the average number of keys per bucket exceeds the fill factor,
423 * expand the table.
424 */
425 hashp->NKEYS++;
426 if (do_expand ||
427 (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))
428 return (__expand_table(hashp));
429 return (0);
430 }
431
432 /*
433 *
434 * Returns:
435 * pointer on success
436 * NULL on error
437 */
438 extern BUFHEAD *
439 __add_ovflpage(hashp, bufp)
440 HTAB *hashp;
441 BUFHEAD *bufp;
442 {
443 register u_short *sp;
444 u_short ndx, ovfl_num;
445 #ifdef DEBUG1
446 int tmp1, tmp2;
447 #endif
448 sp = (u_short *)bufp->page;
449
450 /* Check if we are dynamically determining the fill factor */
451 if (hashp->FFACTOR == DEF_FFACTOR) {
452 hashp->FFACTOR = sp[0] >> 1;
453 if (hashp->FFACTOR < MIN_FFACTOR)
454 hashp->FFACTOR = MIN_FFACTOR;
455 }
456 bufp->flags |= BUF_MOD;
457 ovfl_num = overflow_page(hashp);
458 #ifdef DEBUG1
459 tmp1 = bufp->addr;
460 tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;
461 #endif
462 if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1)))
463 return (NULL);
464 bufp->ovfl->flags |= BUF_MOD;
465 #ifdef DEBUG1
466 (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
467 tmp1, tmp2, bufp->ovfl->addr);
468 #endif
469 ndx = sp[0];
470 /*
471 * Since a pair is allocated on a page only if there's room to add
472 * an overflow page, we know that the OVFL information will fit on
473 * the page.
474 */
475 sp[ndx + 4] = OFFSET(sp);
476 sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE;
477 sp[ndx + 1] = ovfl_num;
478 sp[ndx + 2] = OVFLPAGE;
479 sp[0] = ndx + 2;
480 #ifdef HASH_STATISTICS
481 hash_overflows++;
482 #endif
483 return (bufp->ovfl);
484 }
485
486 /*
487 * Returns:
488 * 0 indicates SUCCESS
489 * -1 indicates FAILURE
490 */
491 extern int
492 __get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap)
493 HTAB *hashp;
494 char *p;
495 u_int bucket;
496 int is_bucket, is_disk, is_bitmap;
497 {
498 register int fd, page, size;
499 int rsize;
500 u_short *bp;
501
502 fd = hashp->fp;
503 size = hashp->BSIZE;
504
505 if ((fd == -1) || !is_disk) {
506 PAGE_INIT(p);
507 return (0);
508 }
509 if (is_bucket)
510 page = BUCKET_TO_PAGE(bucket);
511 else
512 page = OADDR_TO_PAGE(bucket);
513 if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
514 ((rsize = read(fd, p, size)) == -1))
515 return (-1);
516 bp = (u_short *)p;
517 if (!rsize)
518 bp[0] = 0; /* We hit the EOF, so initialize a new page */
519 else
520 if (rsize != size) {
521 errno = EFTYPE;
522 return (-1);
523 }
524 if (!is_bitmap && !bp[0]) {
525 PAGE_INIT(p);
526 } else
527 if (hashp->LORDER != BYTE_ORDER) {
528 register int i, max;
529
530 if (is_bitmap) {
531 max = hashp->BSIZE >> 2; /* divide by 4 */
532 for (i = 0; i < max; i++)
533 M_32_SWAP(((long *)p)[i]);
534 } else {
535 M_16_SWAP(bp[0]);
536 max = bp[0] + 2;
537 for (i = 1; i <= max; i++)
538 M_16_SWAP(bp[i]);
539 }
540 }
541 return (0);
542 }
543
544 /*
545 * Write page p to disk
546 *
547 * Returns:
548 * 0 ==> OK
549 * -1 ==>failure
550 */
551 extern int
552 __put_page(hashp, p, bucket, is_bucket, is_bitmap)
553 HTAB *hashp;
554 char *p;
555 u_int bucket;
556 int is_bucket, is_bitmap;
557 {
558 register int fd, page, size;
559 int wsize;
560
561 size = hashp->BSIZE;
562 if ((hashp->fp == -1) && open_temp(hashp))
563 return (-1);
564 fd = hashp->fp;
565
566 if (hashp->LORDER != BYTE_ORDER) {
567 register int i;
568 register int max;
569
570 if (is_bitmap) {
571 max = hashp->BSIZE >> 2; /* divide by 4 */
572 for (i = 0; i < max; i++)
573 M_32_SWAP(((long *)p)[i]);
574 } else {
575 max = ((u_short *)p)[0] + 2;
576 for (i = 0; i <= max; i++)
577 M_16_SWAP(((u_short *)p)[i]);
578 }
579 }
580 if (is_bucket)
581 page = BUCKET_TO_PAGE(bucket);
582 else
583 page = OADDR_TO_PAGE(bucket);
584 if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
585 ((wsize = write(fd, p, size)) == -1))
586 /* Errno is set */
587 return (-1);
588 if (wsize != size) {
589 errno = EFTYPE;
590 return (-1);
591 }
592 return (0);
593 }
594
595 #define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1)
596 /*
597 * Initialize a new bitmap page. Bitmap pages are left in memory
598 * once they are read in.
599 */
600 extern int
601 __init_bitmap(hashp, pnum, nbits, ndx)
602 HTAB *hashp;
603 int pnum, nbits, ndx;
604 {
605 u_long *ip;
606 int clearbytes, clearints;
607
608 if ((ip = (u_long *)malloc(hashp->BSIZE)) == NULL)
609 return (1);
610 hashp->nmaps++;
611 clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
612 clearbytes = clearints << INT_TO_BYTE;
613 (void)memset((char *)ip, 0, clearbytes);
614 (void)memset(((char *)ip) + clearbytes, 0xFF,
615 hashp->BSIZE - clearbytes);
616 ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
617 SETBIT(ip, 0);
618 hashp->BITMAPS[ndx] = (u_short)pnum;
619 hashp->mapp[ndx] = ip;
620 return (0);
621 }
622
623 static u_long
first_free(map)624 first_free(map)
625 u_long map;
626 {
627 register u_long i, mask;
628
629 mask = 0x1;
630 for (i = 0; i < BITS_PER_MAP; i++) {
631 if (!(mask & map))
632 return (i);
633 mask = mask << 1;
634 }
635 return (i);
636 }
637
638 static u_short
overflow_page(hashp)639 overflow_page(hashp)
640 HTAB *hashp;
641 {
642 register u_long *freep;
643 register int max_free, offset, splitnum;
644 u_short addr;
645 int bit, first_page, free_bit, free_page, i, in_use_bits, j;
646 #ifdef DEBUG2
647 int tmp1, tmp2;
648 #endif
649 splitnum = hashp->OVFL_POINT;
650 max_free = hashp->SPARES[splitnum];
651
652 free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
653 free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
654
655 /* Look through all the free maps to find the first free block */
656 first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT);
657 for ( i = first_page; i <= free_page; i++ ) {
658 if (!(freep = (u_long *)hashp->mapp[i]) &&
659 !(freep = fetch_bitmap(hashp, i)))
660 return (NULL);
661 if (i == free_page)
662 in_use_bits = free_bit;
663 else
664 in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;
665
666 if (i == first_page) {
667 bit = hashp->LAST_FREED &
668 ((hashp->BSIZE << BYTE_SHIFT) - 1);
669 j = bit / BITS_PER_MAP;
670 bit = bit & ~(BITS_PER_MAP - 1);
671 } else {
672 bit = 0;
673 j = 0;
674 }
675 for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
676 if (freep[j] != ALL_SET)
677 goto found;
678 }
679
680 /* No Free Page Found */
681 hashp->LAST_FREED = hashp->SPARES[splitnum];
682 hashp->SPARES[splitnum]++;
683 offset = hashp->SPARES[splitnum] -
684 (splitnum ? hashp->SPARES[splitnum - 1] : 0);
685
686 #define OVMSG "HASH: Out of overflow pages. Increase page size\n"
687 if (offset > SPLITMASK) {
688 if (++splitnum >= NCACHED) {
689 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
690 return (NULL);
691 }
692 hashp->OVFL_POINT = splitnum;
693 hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
694 hashp->SPARES[splitnum-1]--;
695 offset = 1;
696 }
697
698 /* Check if we need to allocate a new bitmap page */
699 if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
700 free_page++;
701 if (free_page >= NCACHED) {
702 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
703 return (NULL);
704 }
705 /*
706 * This is tricky. The 1 indicates that you want the new page
707 * allocated with 1 clear bit. Actually, you are going to
708 * allocate 2 pages from this map. The first is going to be
709 * the map page, the second is the overflow page we were
710 * looking for. The init_bitmap routine automatically, sets
711 * the first bit of itself to indicate that the bitmap itself
712 * is in use. We would explicitly set the second bit, but
713 * don't have to if we tell init_bitmap not to leave it clear
714 * in the first place.
715 */
716 if (__init_bitmap(hashp, (int)OADDR_OF(splitnum, offset),
717 1, free_page))
718 return (NULL);
719 hashp->SPARES[splitnum]++;
720 #ifdef DEBUG2
721 free_bit = 2;
722 #endif
723 offset++;
724 if (offset > SPLITMASK) {
725 if (++splitnum >= NCACHED) {
726 (void)write(STDERR_FILENO, OVMSG,
727 sizeof(OVMSG) - 1);
728 return (NULL);
729 }
730 hashp->OVFL_POINT = splitnum;
731 hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
732 hashp->SPARES[splitnum-1]--;
733 offset = 0;
734 }
735 } else {
736 /*
737 * Free_bit addresses the last used bit. Bump it to address
738 * the first available bit.
739 */
740 free_bit++;
741 SETBIT(freep, free_bit);
742 }
743
744 /* Calculate address of the new overflow page */
745 addr = OADDR_OF(splitnum, offset);
746 #ifdef DEBUG2
747 (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
748 addr, free_bit, free_page);
749 #endif
750 return (addr);
751
752 found:
753 bit = bit + first_free(freep[j]);
754 SETBIT(freep, bit);
755 #ifdef DEBUG2
756 tmp1 = bit;
757 tmp2 = i;
758 #endif
759 /*
760 * Bits are addressed starting with 0, but overflow pages are addressed
761 * beginning at 1. Bit is a bit addressnumber, so we need to increment
762 * it to convert it to a page number.
763 */
764 bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
765 if (bit >= hashp->LAST_FREED)
766 hashp->LAST_FREED = bit - 1;
767
768 /* Calculate the split number for this page */
769 for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
770 offset = (i ? bit - hashp->SPARES[i - 1] : bit);
771 if (offset >= SPLITMASK)
772 return (NULL); /* Out of overflow pages */
773 addr = OADDR_OF(i, offset);
774 #ifdef DEBUG2
775 (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
776 addr, tmp1, tmp2);
777 #endif
778
779 /* Allocate and return the overflow page */
780 return (addr);
781 }
782
783 /*
784 * Mark this overflow page as free.
785 */
786 extern void
787 __free_ovflpage(hashp, obufp)
788 HTAB *hashp;
789 BUFHEAD *obufp;
790 {
791 register u_short addr;
792 u_long *freep;
793 int bit_address, free_page, free_bit;
794 u_short ndx;
795
796 addr = obufp->addr;
797 #ifdef DEBUG1
798 (void)fprintf(stderr, "Freeing %d\n", addr);
799 #endif
800 ndx = (((u_short)addr) >> SPLITSHIFT);
801 bit_address =
802 (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
803 if (bit_address < hashp->LAST_FREED)
804 hashp->LAST_FREED = bit_address;
805 free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
806 free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
807
808 if (!(freep = hashp->mapp[free_page]))
809 freep = fetch_bitmap(hashp, free_page);
810 #ifdef DEBUG
811 /*
812 * This had better never happen. It means we tried to read a bitmap
813 * that has already had overflow pages allocated off it, and we
814 * failed to read it from the file.
815 */
816 if (!freep)
817 assert(0);
818 #endif
819 CLRBIT(freep, free_bit);
820 #ifdef DEBUG2
821 (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
822 obufp->addr, free_bit, free_page);
823 #endif
824 __reclaim_buf(hashp, obufp);
825 }
826
827 /*
828 * Returns:
829 * 0 success
830 * -1 failure
831 */
832 static int
open_temp(hashp)833 open_temp(hashp)
834 HTAB *hashp;
835 {
836 sigset_t set, oset;
837 static char namestr[] = "_hashXXXXXX";
838
839 /* Block signals; make sure file goes away at process exit. */
840 (void)sigfillset(&set);
841 (void)sigprocmask(SIG_BLOCK, &set, &oset);
842 if ((hashp->fp = mkstemp(namestr)) != -1) {
843 (void)unlink(namestr);
844 (void)fcntl(hashp->fp, F_SETFD, 1);
845 }
846 (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
847 return (hashp->fp != -1 ? 0 : -1);
848 }
849
850 /*
851 * We have to know that the key will fit, but the last entry on the page is
852 * an overflow pair, so we need to shift things.
853 */
854 static void
squeeze_key(sp,key,val)855 squeeze_key(sp, key, val)
856 u_short *sp;
857 const DBT *key, *val;
858 {
859 register char *p;
860 u_short free_space, n, off, pageno;
861
862 p = (char *)sp;
863 n = sp[0];
864 free_space = FREESPACE(sp);
865 off = OFFSET(sp);
866
867 pageno = sp[n - 1];
868 off -= key->size;
869 sp[n - 1] = off;
870 memmove(p + off, key->data, key->size);
871 off -= val->size;
872 sp[n] = off;
873 memmove(p + off, val->data, val->size);
874 sp[0] = n + 2;
875 sp[n + 1] = pageno;
876 sp[n + 2] = OVFLPAGE;
877 FREESPACE(sp) = free_space - PAIRSIZE(key, val);
878 OFFSET(sp) = off;
879 }
880
881 static u_long *
fetch_bitmap(hashp,ndx)882 fetch_bitmap(hashp, ndx)
883 HTAB *hashp;
884 int ndx;
885 {
886 if (ndx >= hashp->nmaps)
887 return (NULL);
888 if ((hashp->mapp[ndx] = (u_long *)malloc(hashp->BSIZE)) == NULL)
889 return (NULL);
890 if (__get_page(hashp,
891 (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) {
892 free(hashp->mapp[ndx]);
893 return (NULL);
894 }
895 return (hashp->mapp[ndx]);
896 }
897
898 #ifdef DEBUG4
899 int
print_chain(addr)900 print_chain(addr)
901 int addr;
902 {
903 BUFHEAD *bufp;
904 short *bp, oaddr;
905
906 (void)fprintf(stderr, "%d ", addr);
907 bufp = __get_buf(hashp, addr, NULL, 0);
908 bp = (short *)bufp->page;
909 while (bp[0] && ((bp[bp[0]] == OVFLPAGE) ||
910 ((bp[0] > 2) && bp[2] < REAL_KEY))) {
911 oaddr = bp[bp[0] - 1];
912 (void)fprintf(stderr, "%d ", (int)oaddr);
913 bufp = __get_buf(hashp, (int)oaddr, bufp, 0);
914 bp = (short *)bufp->page;
915 }
916 (void)fprintf(stderr, "\n");
917 }
918 #endif
919