1 #pragma ident "%Z%%M% %I% %E% SMI"
2
3 /*-
4 * Copyright (c) 1990, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Margo Seltzer.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 * must display the following acknowledgement:
20 * This product includes software developed by the University of
21 * California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 * may be used to endorse or promote products derived from this software
24 * without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 */
38
39 #if defined(LIBC_SCCS) && !defined(lint)
40 static char sccsid[] = "@(#)hash_page.c 8.11 (Berkeley) 11/7/95";
41 #endif /* LIBC_SCCS and not lint */
42
43 /*
44 * PACKAGE: hashing
45 *
46 * DESCRIPTION:
47 * Page manipulation for hashing package.
48 *
49 * ROUTINES:
50 *
51 * External
52 * __get_page
53 * __add_ovflpage
54 * Internal
55 * overflow_page
56 * open_temp
57 */
58
59 #include <sys/types.h>
60
61 #ifdef DEBUG
62 #include <assert.h>
63 #endif
64 #include <stdio.h>
65 #include <stdlib.h>
66 #include <string.h>
67 #include <unistd.h>
68 #include <libintl.h>
69 #include "db-int.h"
70 #include "hash.h"
71 #include "page.h"
72 #include "extern.h"
73
74 static int32_t add_bigptr __P((HTAB *, ITEM_INFO *, indx_t));
75 static u_int32_t *fetch_bitmap __P((HTAB *, int32_t));
76 static u_int32_t first_free __P((u_int32_t));
77 static indx_t next_realkey __P((PAGE16 *, indx_t));
78 static u_int16_t overflow_page __P((HTAB *));
79 static void page_init __P((HTAB *, PAGE16 *, db_pgno_t, u_int8_t));
80 static indx_t prev_realkey __P((PAGE16 *, indx_t));
81 static void putpair __P((PAGE8 *, const DBT *, const DBT *));
82 static void swap_page_header_in __P((PAGE16 *));
83 static void swap_page_header_out __P((PAGE16 *));
84
85 #ifdef DEBUG_SLOW
86 static void account_page(HTAB *, db_pgno_t, int);
87 #endif
88
89 u_int32_t
__get_item(hashp,cursorp,key,val,item_info)90 __get_item(hashp, cursorp, key, val, item_info)
91 HTAB *hashp;
92 CURSOR *cursorp;
93 DBT *key, *val;
94 ITEM_INFO *item_info;
95 {
96 db_pgno_t next_pgno;
97 int32_t i;
98
99 /* Check if we need to get a page. */
100 if (!cursorp->pagep) {
101 if (cursorp->pgno == INVALID_PGNO) {
102 cursorp->pagep =
103 __get_page(hashp, cursorp->bucket, A_BUCKET);
104 cursorp->pgno = ADDR(cursorp->pagep);
105 cursorp->ndx = 0;
106 cursorp->pgndx = 0;
107 } else
108 cursorp->pagep =
109 __get_page(hashp, cursorp->pgno, A_RAW);
110 if (!cursorp->pagep) {
111 item_info->status = ITEM_ERROR;
112 return (-1);
113 }
114 }
115 if (item_info->seek_size &&
116 FREESPACE(cursorp->pagep) > item_info->seek_size)
117 item_info->seek_found_page = cursorp->pgno;
118
119 if (cursorp->pgndx == NUM_ENT(cursorp->pagep)) {
120 /* Fetch next page. */
121 if (NEXT_PGNO(cursorp->pagep) == INVALID_PGNO) {
122 item_info->status = ITEM_NO_MORE;
123 return (-1);
124 }
125 next_pgno = NEXT_PGNO(cursorp->pagep);
126 cursorp->pgndx = 0;
127 __put_page(hashp, cursorp->pagep, A_RAW, 0);
128 cursorp->pagep = __get_page(hashp, next_pgno, A_RAW);
129 if (!cursorp->pagep) {
130 item_info->status = ITEM_ERROR;
131 return (-1);
132 }
133 cursorp->pgno = next_pgno;
134 }
135 if (KEY_OFF(cursorp->pagep, cursorp->pgndx) != BIGPAIR) {
136 if ((i = prev_realkey(cursorp->pagep, cursorp->pgndx)) ==
137 cursorp->pgndx)
138 key->size = hashp->hdr.bsize -
139 KEY_OFF(cursorp->pagep, cursorp->pgndx);
140 else
141 key->size = DATA_OFF(cursorp->pagep, i) -
142 KEY_OFF(cursorp->pagep, cursorp->pgndx);
143 }
144
145 /*
146 * All of this information will be set incorrectly for big keys, but
147 * it will be ignored anyway.
148 */
149 val->size = KEY_OFF(cursorp->pagep, cursorp->pgndx) -
150 DATA_OFF(cursorp->pagep, cursorp->pgndx);
151 key->data = KEY(cursorp->pagep, cursorp->pgndx);
152 val->data = DATA(cursorp->pagep, cursorp->pgndx);
153 item_info->pgno = cursorp->pgno;
154 item_info->bucket = cursorp->bucket;
155 item_info->ndx = cursorp->ndx;
156 item_info->pgndx = cursorp->pgndx;
157 item_info->key_off = KEY_OFF(cursorp->pagep, cursorp->pgndx);
158 item_info->data_off = DATA_OFF(cursorp->pagep, cursorp->pgndx);
159 item_info->status = ITEM_OK;
160
161 return (0);
162 }
163
164 u_int32_t
__get_item_reset(hashp,cursorp)165 __get_item_reset(hashp, cursorp)
166 HTAB *hashp;
167 CURSOR *cursorp;
168 {
169 if (cursorp->pagep)
170 __put_page(hashp, cursorp->pagep, A_RAW, 0);
171 cursorp->pagep = NULL;
172 cursorp->bucket = -1;
173 cursorp->ndx = 0;
174 cursorp->pgndx = 0;
175 cursorp->pgno = INVALID_PGNO;
176 return (0);
177 }
178
179 u_int32_t
__get_item_done(hashp,cursorp)180 __get_item_done(hashp, cursorp)
181 HTAB *hashp;
182 CURSOR *cursorp;
183 {
184 if (cursorp->pagep)
185 __put_page(hashp, cursorp->pagep, A_RAW, 0);
186 cursorp->pagep = NULL;
187
188 /*
189 * We don't throw out the page number since we might want to
190 * continue getting on this page.
191 */
192 return (0);
193 }
194
195 u_int32_t
__get_item_first(hashp,cursorp,key,val,item_info)196 __get_item_first(hashp, cursorp, key, val, item_info)
197 HTAB *hashp;
198 CURSOR *cursorp;
199 DBT *key, *val;
200 ITEM_INFO *item_info;
201 {
202 __get_item_reset(hashp, cursorp);
203 cursorp->bucket = 0;
204 return (__get_item_next(hashp, cursorp, key, val, item_info));
205 }
206
207 /*
208 * Returns a pointer to key/data pair on a page. In the case of bigkeys,
209 * just returns the page number and index of the bigkey pointer pair.
210 */
211 u_int32_t
__get_item_next(hashp,cursorp,key,val,item_info)212 __get_item_next(hashp, cursorp, key, val, item_info)
213 HTAB *hashp;
214 CURSOR *cursorp;
215 DBT *key, *val;
216 ITEM_INFO *item_info;
217 {
218 int status;
219
220 status = __get_item(hashp, cursorp, key, val, item_info);
221 cursorp->ndx++;
222 cursorp->pgndx++;
223 return (status);
224 }
225
226 /*
227 * Put a non-big pair on a page.
228 */
229 static void
putpair(p,key,val)230 putpair(p, key, val)
231 PAGE8 *p;
232 const DBT *key, *val;
233 {
234 u_int16_t *pagep, n, off;
235
236 pagep = (PAGE16 *)p;
237
238 /* Items on the page are 0-indexed. */
239 n = NUM_ENT(pagep);
240 off = OFFSET(pagep) - key->size + 1;
241 memmove(p + off, key->data, key->size);
242 KEY_OFF(pagep, n) = off;
243
244 off -= val->size;
245 memmove(p + off, val->data, val->size);
246 DATA_OFF(pagep, n) = off;
247
248 /* Adjust page info. */
249 NUM_ENT(pagep) = n + 1;
250 OFFSET(pagep) = off - 1;
251 }
252
253 /*
254 * Returns the index of the next non-bigkey pair after n on the page.
255 * Returns -1 if there are no more non-big things on the page.
256 */
257 static indx_t
258 #ifdef __STDC__
next_realkey(PAGE16 * pagep,indx_t n)259 next_realkey(PAGE16 * pagep, indx_t n)
260 #else
261 next_realkey(pagep, n)
262 PAGE16 *pagep;
263 u_int32_t n;
264 #endif
265 {
266 indx_t i;
267
268 for (i = n + 1; i < NUM_ENT(pagep); i++)
269 if (KEY_OFF(pagep, i) != BIGPAIR)
270 return (i);
271 return (-1);
272 }
273
274 /*
275 * Returns the index of the previous non-bigkey pair after n on the page.
276 * Returns n if there are no previous non-big things on the page.
277 */
278 static indx_t
279 #ifdef __STDC__
prev_realkey(PAGE16 * pagep,indx_t n)280 prev_realkey(PAGE16 * pagep, indx_t n)
281 #else
282 prev_realkey(pagep, n)
283 PAGE16 *pagep;
284 u_int32_t n;
285 #endif
286 {
287 int32_t i;
288
289 /* Need a signed value to do the compare properly. */
290 for (i = n - 1; i > -1; i--)
291 if (KEY_OFF(pagep, i) != BIGPAIR)
292 return (i);
293 return (n);
294 }
295
296 /*
297 * Returns:
298 * 0 OK
299 * -1 error
300 */
301 extern int32_t
302 __delpair(hashp, cursorp, item_info)
303 HTAB *hashp;
304 CURSOR *cursorp;
305 ITEM_INFO *item_info;
306 {
307 PAGE16 *pagep;
308 indx_t ndx;
309 short check_ndx;
310 int16_t delta, len, next_key;
311 int32_t n;
312 u_int8_t *src, *dest;
313
314 ndx = cursorp->pgndx;
315 if (!cursorp->pagep) {
316 pagep = __get_page(hashp, cursorp->pgno, A_RAW);
317 if (!pagep)
318 return (-1);
319 /*
320 * KLUGE: pgndx has gone one too far, because cursor points
321 * to the _next_ item. Use pgndx - 1.
322 */
323 --ndx;
324 } else
325 pagep = cursorp->pagep;
326 #ifdef DEBUG
327 assert(ADDR(pagep) == cursorp->pgno);
328 #endif
329
330 if (KEY_OFF(pagep, ndx) == BIGPAIR) {
331 delta = 0;
332 __big_delete(hashp, pagep, ndx);
333 } else {
334 /*
335 * Compute "delta", the amount we have to shift all of the
336 * offsets. To find the delta, we need to make sure that
337 * we aren't looking at the DATA_OFF of a big/keydata pair.
338 */
339 for (check_ndx = (short)(ndx - 1);
340 check_ndx >= 0 && KEY_OFF(pagep, check_ndx) == BIGPAIR;
341 check_ndx--);
342 if (check_ndx < 0)
343 delta = hashp->hdr.bsize - DATA_OFF(pagep, ndx);
344 else
345 delta =
346 DATA_OFF(pagep, check_ndx) - DATA_OFF(pagep, ndx);
347
348 /*
349 * The hard case: we want to remove something other than
350 * the last item on the page. We need to shift data and
351 * offsets down.
352 */
353 if (ndx != NUM_ENT(pagep) - 1) {
354 /*
355 * Move the data: src is the address of the last data
356 * item on the page.
357 */
358 src = (u_int8_t *)pagep + OFFSET(pagep) + 1;
359 /*
360 * Length is the distance between where to start
361 * deleting and end of the data on the page.
362 */
363 len = DATA_OFF(pagep, ndx) - (OFFSET(pagep) + 1);
364 /*
365 * Dest is the location of the to-be-deleted item
366 * occupied - length.
367 */
368 if (check_ndx < 0)
369 dest =
370 (u_int8_t *)pagep + hashp->hdr.bsize - len;
371 else
372 dest = (u_int8_t *)pagep +
373 DATA_OFF(pagep, (check_ndx)) - len;
374 memmove(dest, src, len);
375 }
376 }
377
378 /* Adjust the offsets. */
379 for (n = ndx; n < NUM_ENT(pagep) - 1; n++)
380 if (KEY_OFF(pagep, (n + 1)) != BIGPAIR) {
381 next_key = next_realkey(pagep, n);
382 #ifdef DEBUG
383 assert(next_key != -1);
384 #endif
385 KEY_OFF(pagep, n) = KEY_OFF(pagep, (n + 1)) + delta;
386 DATA_OFF(pagep, n) = DATA_OFF(pagep, (n + 1)) + delta;
387 } else {
388 KEY_OFF(pagep, n) = KEY_OFF(pagep, (n + 1));
389 DATA_OFF(pagep, n) = DATA_OFF(pagep, (n + 1));
390 }
391
392 /* Adjust page metadata. */
393 OFFSET(pagep) = OFFSET(pagep) + delta;
394 NUM_ENT(pagep) = NUM_ENT(pagep) - 1;
395
396 --hashp->hdr.nkeys;
397
398 /* Is this page now an empty overflow page? If so, free it. */
399 if (TYPE(pagep) == HASH_OVFLPAGE && NUM_ENT(pagep) == 0) {
400 PAGE16 *empty_page;
401 db_pgno_t to_find, next_pgno, link_page;
402
403 /*
404 * We need to go back to the first page in the chain and
405 * look for this page so that we can update the previous
406 * page's NEXT_PGNO field.
407 */
408 to_find = ADDR(pagep);
409 empty_page = pagep;
410 link_page = NEXT_PGNO(empty_page);
411 pagep = __get_page(hashp, item_info->bucket, A_BUCKET);
412 if (!pagep)
413 return (-1);
414 while (NEXT_PGNO(pagep) != to_find) {
415 next_pgno = NEXT_PGNO(pagep);
416 #ifdef DEBUG
417 assert(next_pgno != INVALID_PGNO);
418 #endif
419 __put_page(hashp, pagep, A_RAW, 0);
420 pagep = __get_page(hashp, next_pgno, A_RAW);
421 if (!pagep)
422 return (-1);
423 }
424
425 /*
426 * At this point, pagep should point to the page before the
427 * page to be deleted.
428 */
429 NEXT_PGNO(pagep) = link_page;
430 if (item_info->pgno == to_find) {
431 item_info->pgno = ADDR(pagep);
432 item_info->pgndx = NUM_ENT(pagep);
433 item_info->seek_found_page = ADDR(pagep);
434 }
435 __delete_page(hashp, empty_page, A_OVFL);
436 }
437 __put_page(hashp, pagep, A_RAW, 1);
438
439 return (0);
440 }
441
442 extern int32_t
443 __split_page(hashp, obucket, nbucket)
444 HTAB *hashp;
445 u_int32_t obucket, nbucket;
446 {
447 DBT key, val;
448 ITEM_INFO old_ii, new_ii;
449 PAGE16 *old_pagep, *temp_pagep;
450 db_pgno_t next_pgno;
451 int32_t off;
452 u_int16_t n;
453 int8_t base_page;
454
455 off = hashp->hdr.bsize;
456 old_pagep = __get_page(hashp, obucket, A_BUCKET);
457
458 base_page = 1;
459
460 temp_pagep = hashp->split_buf;
461 memcpy(temp_pagep, old_pagep, hashp->hdr.bsize);
462
463 page_init(hashp, old_pagep, ADDR(old_pagep), HASH_PAGE);
464 __put_page(hashp, old_pagep, A_RAW, 1);
465
466 old_ii.pgno = BUCKET_TO_PAGE(obucket);
467 new_ii.pgno = BUCKET_TO_PAGE(nbucket);
468 old_ii.bucket = obucket;
469 new_ii.bucket = nbucket;
470 old_ii.seek_found_page = new_ii.seek_found_page = 0;
471
472 while (temp_pagep != 0) {
473 off = hashp->hdr.bsize;
474 for (n = 0; n < NUM_ENT(temp_pagep); n++) {
475 if (KEY_OFF(temp_pagep, n) == BIGPAIR) {
476 __get_bigkey(hashp, temp_pagep, n, &key);
477 if (__call_hash(hashp,
478 key.data, key.size) == obucket)
479 add_bigptr(hashp, &old_ii,
480 DATA_OFF(temp_pagep, n));
481 else
482 add_bigptr(hashp, &new_ii,
483 DATA_OFF(temp_pagep, n));
484 } else {
485 key.size = off - KEY_OFF(temp_pagep, n);
486 key.data = KEY(temp_pagep, n);
487 off = KEY_OFF(temp_pagep, n);
488 val.size = off - DATA_OFF(temp_pagep, n);
489 val.data = DATA(temp_pagep, n);
490 if (__call_hash(hashp,
491 key.data, key.size) == obucket)
492 __addel(hashp, &old_ii, &key, &val,
493 NO_EXPAND, 1);
494 else
495 __addel(hashp, &new_ii, &key, &val,
496 NO_EXPAND, 1);
497 off = DATA_OFF(temp_pagep, n);
498 }
499 }
500 next_pgno = NEXT_PGNO(temp_pagep);
501
502 /* Clear temp_page; if it's an overflow page, free it. */
503 if (!base_page)
504 __delete_page(hashp, temp_pagep, A_OVFL);
505 else
506 base_page = 0;
507 if (next_pgno != INVALID_PGNO)
508 temp_pagep = __get_page(hashp, next_pgno, A_RAW);
509 else
510 break;
511 }
512 return (0);
513 }
514
515 /*
516 * Add the given pair to the page.
517 *
518 *
519 * Returns:
520 * 0 ==> OK
521 * -1 ==> failure
522 */
523 extern int32_t
524 #ifdef __STDC__
__addel(HTAB * hashp,ITEM_INFO * item_info,const DBT * key,const DBT * val,u_int32_t num_items,const u_int8_t expanding)525 __addel(HTAB *hashp, ITEM_INFO *item_info, const DBT *key, const DBT *val,
526 u_int32_t num_items, const u_int8_t expanding)
527 #else
528 __addel(hashp, item_info, key, val, num_items, expanding)
529 HTAB *hashp;
530 ITEM_INFO *item_info;
531 const DBT *key, *val;
532 u_int32_t num_items;
533 const u_int32_t expanding;
534 #endif
535 {
536 PAGE16 *pagep;
537 int32_t do_expand;
538 db_pgno_t next_pgno;
539
540 do_expand = 0;
541
542 pagep = __get_page(hashp,
543 item_info->seek_found_page != 0 ?
544 item_info->seek_found_page : item_info->pgno, A_RAW);
545 if (!pagep)
546 return (-1);
547
548 /* Advance to first page in chain with room for item. */
549 while (NUM_ENT(pagep) && NEXT_PGNO(pagep) != INVALID_PGNO) {
550 /*
551 * This may not be the end of the chain, but the pair may fit
552 * anyway.
553 */
554 if (ISBIG(PAIRSIZE(key, val), hashp) && BIGPAIRFITS(pagep))
555 break;
556 if (PAIRFITS(pagep, key, val))
557 break;
558 next_pgno = NEXT_PGNO(pagep);
559 __put_page(hashp, pagep, A_RAW, 0);
560 pagep = (PAGE16 *)__get_page(hashp, next_pgno, A_RAW);
561 if (!pagep)
562 return (-1);
563 }
564
565 if ((ISBIG(PAIRSIZE(key, val), hashp) &&
566 !BIGPAIRFITS(pagep)) ||
567 (!ISBIG(PAIRSIZE(key, val), hashp) &&
568 !PAIRFITS(pagep, key, val))) {
569 do_expand = 1;
570 pagep = __add_ovflpage(hashp, pagep);
571 if (!pagep)
572 return (-1);
573
574 if ((ISBIG(PAIRSIZE(key, val), hashp) &&
575 !BIGPAIRFITS(pagep)) ||
576 (!ISBIG(PAIRSIZE(key, val), hashp) &&
577 !PAIRFITS(pagep, key, val))) {
578 __put_page(hashp, pagep, A_RAW, 0);
579 return (-1);
580 }
581 }
582
583 /* At this point, we know the page fits, so we just add it */
584
585 if (ISBIG(PAIRSIZE(key, val), hashp)) {
586 if (__big_insert(hashp, pagep, key, val))
587 return (-1);
588 } else {
589 putpair((PAGE8 *)pagep, key, val);
590 }
591
592 /*
593 * For splits, we are going to update item_info's page number
594 * field, so that we can easily return to the same page the
595 * next time we come in here. For other operations, this shouldn't
596 * matter, since adds are the last thing that happens before we
597 * return to the user program.
598 */
599 item_info->pgno = ADDR(pagep);
600
601 if (!expanding)
602 hashp->hdr.nkeys++;
603
604 /* Kludge: if this is a big page, then it's already been put. */
605 if (!ISBIG(PAIRSIZE(key, val), hashp))
606 __put_page(hashp, pagep, A_RAW, 1);
607
608 if (expanding)
609 item_info->caused_expand = 0;
610 else
611 switch (num_items) {
612 case NO_EXPAND:
613 item_info->caused_expand = 0;
614 break;
615 case UNKNOWN:
616 item_info->caused_expand |=
617 (hashp->hdr.nkeys / hashp->hdr.max_bucket) >
618 hashp->hdr.ffactor ||
619 item_info->pgndx > hashp->hdr.ffactor;
620 break;
621 default:
622 item_info->caused_expand =
623 num_items > hashp->hdr.ffactor ? 1 : do_expand;
624 break;
625 }
626 return (0);
627 }
628
629 /*
630 * Special __addel used in big splitting; this one just puts the pointer
631 * to an already-allocated big page in the appropriate bucket.
632 */
633 static int32_t
634 #ifdef __STDC__
add_bigptr(HTAB * hashp,ITEM_INFO * item_info,indx_t big_pgno)635 add_bigptr(HTAB * hashp, ITEM_INFO * item_info, indx_t big_pgno)
636 #else
637 add_bigptr(hashp, item_info, big_pgno)
638 HTAB *hashp;
639 ITEM_INFO *item_info;
640 u_int32_t big_pgno;
641 #endif
642 {
643 PAGE16 *pagep;
644 db_pgno_t next_pgno;
645
646 pagep = __get_page(hashp, item_info->bucket, A_BUCKET);
647 if (!pagep)
648 return (-1);
649
650 /*
651 * Note: in __addel(), we used item_info->pgno for the beginning of
652 * our search for space. Now, we use item_info->bucket, since we
653 * know that the space required by a big pair on the base page is
654 * quite small, and we may very well find that space early in the
655 * chain.
656 */
657
658 /* Find first page in chain that has space for a big pair. */
659 while (NUM_ENT(pagep) && (NEXT_PGNO(pagep) != INVALID_PGNO)) {
660 if (BIGPAIRFITS(pagep))
661 break;
662 next_pgno = NEXT_PGNO(pagep);
663 __put_page(hashp, pagep, A_RAW, 0);
664 pagep = __get_page(hashp, next_pgno, A_RAW);
665 if (!pagep)
666 return (-1);
667 }
668 if (!BIGPAIRFITS(pagep)) {
669 pagep = __add_ovflpage(hashp, pagep);
670 if (!pagep)
671 return (-1);
672 #ifdef DEBUG
673 assert(BIGPAIRFITS(pagep));
674 #endif
675 }
676 KEY_OFF(pagep, NUM_ENT(pagep)) = BIGPAIR;
677 DATA_OFF(pagep, NUM_ENT(pagep)) = big_pgno;
678 NUM_ENT(pagep) = NUM_ENT(pagep) + 1;
679
680 __put_page(hashp, pagep, A_RAW, 1);
681
682 return (0);
683 }
684
685 /*
686 *
687 * Returns:
688 * pointer on success
689 * NULL on error
690 */
691 extern PAGE16 *
692 __add_ovflpage(hashp, pagep)
693 HTAB *hashp;
694 PAGE16 *pagep;
695 {
696 PAGE16 *new_pagep;
697 u_int16_t ovfl_num;
698
699 /* Check if we are dynamically determining the fill factor. */
700 if (hashp->hdr.ffactor == DEF_FFACTOR) {
701 hashp->hdr.ffactor = NUM_ENT(pagep) >> 1;
702 if (hashp->hdr.ffactor < MIN_FFACTOR)
703 hashp->hdr.ffactor = MIN_FFACTOR;
704 }
705 ovfl_num = overflow_page(hashp);
706 if (!ovfl_num)
707 return (NULL);
708
709 if (__new_page(hashp, (u_int32_t)ovfl_num, A_OVFL) != 0)
710 return (NULL);
711
712 if (!ovfl_num || !(new_pagep = __get_page(hashp, ovfl_num, A_OVFL)))
713 return (NULL);
714
715 NEXT_PGNO(pagep) = (db_pgno_t)OADDR_TO_PAGE(ovfl_num);
716 TYPE(new_pagep) = HASH_OVFLPAGE;
717
718 __put_page(hashp, pagep, A_RAW, 1);
719
720 #ifdef HASH_STATISTICS
721 hash_overflows++;
722 #endif
723 return (new_pagep);
724 }
725
726 /*
727 *
728 * Returns:
729 * pointer on success
730 * NULL on error
731 */
732 extern PAGE16 *
733 #ifdef __STDC__
__add_bigpage(HTAB * hashp,PAGE16 * pagep,indx_t ndx,const u_int8_t is_basepage)734 __add_bigpage(HTAB * hashp, PAGE16 * pagep, indx_t ndx, const u_int8_t
735 is_basepage)
736 #else
737 __add_bigpage(hashp, pagep, ndx, is_basepage)
738 HTAB *hashp;
739 PAGE16 *pagep;
740 u_int32_t ndx;
741 const u_int32_t is_basepage;
742 #endif
743 {
744 PAGE16 *new_pagep;
745 u_int16_t ovfl_num;
746
747 ovfl_num = overflow_page(hashp);
748 if (!ovfl_num)
749 return (NULL);
750
751 if (__new_page(hashp, (u_int32_t)ovfl_num, A_OVFL) != 0)
752 return (NULL);
753
754 if (!ovfl_num || !(new_pagep = __get_page(hashp, ovfl_num, A_OVFL)))
755 return (NULL);
756
757 if (is_basepage) {
758 KEY_OFF(pagep, ndx) = BIGPAIR;
759 DATA_OFF(pagep, ndx) = (indx_t)ovfl_num;
760 } else
761 NEXT_PGNO(pagep) = ADDR(new_pagep);
762
763 __put_page(hashp, pagep, A_RAW, 1);
764
765 TYPE(new_pagep) = HASH_BIGPAGE;
766
767 #ifdef HASH_STATISTICS
768 hash_bigpages++;
769 #endif
770 return (new_pagep);
771 }
772
773 static void
774 #ifdef __STDC__
page_init(HTAB * hashp,PAGE16 * pagep,db_pgno_t pgno,u_int8_t type)775 page_init(HTAB * hashp, PAGE16 * pagep, db_pgno_t pgno, u_int8_t type)
776 #else
777 page_init(hashp, pagep, pgno, type)
778 HTAB *hashp;
779 PAGE16 *pagep;
780 db_pgno_t pgno;
781 u_int32_t type;
782 #endif
783 {
784 NUM_ENT(pagep) = 0;
785 PREV_PGNO(pagep) = NEXT_PGNO(pagep) = INVALID_PGNO;
786 TYPE(pagep) = type;
787 OFFSET(pagep) = hashp->hdr.bsize - 1;
788 /*
789 * Note: since in the current version ADDR(pagep) == PREV_PGNO(pagep),
790 * make sure that ADDR(pagep) is set after resetting PREV_PGNO(pagep).
791 * We reset PREV_PGNO(pagep) just in case the macros are changed.
792 */
793 ADDR(pagep) = pgno;
794
795 return;
796 }
797
798 int32_t
__new_page(hashp,addr,addr_type)799 __new_page(hashp, addr, addr_type)
800 HTAB *hashp;
801 u_int32_t addr;
802 int32_t addr_type;
803 {
804 db_pgno_t paddr;
805 PAGE16 *pagep;
806
807 switch (addr_type) { /* Convert page number. */
808 case A_BUCKET:
809 paddr = BUCKET_TO_PAGE(addr);
810 break;
811 case A_OVFL:
812 case A_BITMAP:
813 paddr = OADDR_TO_PAGE(addr);
814 break;
815 default:
816 paddr = addr;
817 break;
818 }
819 pagep = mpool_new(hashp->mp, &paddr, MPOOL_PAGE_REQUEST);
820 if (!pagep)
821 return (-1);
822 #if DEBUG_SLOW
823 account_page(hashp, paddr, 1);
824 #endif
825
826 if (addr_type != A_BITMAP)
827 page_init(hashp, pagep, paddr, HASH_PAGE);
828
829 __put_page(hashp, pagep, addr_type, 1);
830
831 return (0);
832 }
833
834 int32_t
__delete_page(hashp,pagep,page_type)835 __delete_page(hashp, pagep, page_type)
836 HTAB *hashp;
837 PAGE16 *pagep;
838 int32_t page_type;
839 {
840 if (page_type == A_OVFL)
841 __free_ovflpage(hashp, pagep);
842 return (mpool_delete(hashp->mp, pagep));
843 }
844
845 static u_int8_t
is_bitmap_pgno(hashp,pgno)846 is_bitmap_pgno(hashp, pgno)
847 HTAB *hashp;
848 db_pgno_t pgno;
849 {
850 int32_t i;
851
852 for (i = 0; i < hashp->nmaps; i++)
853 if (OADDR_TO_PAGE(hashp->hdr.bitmaps[i]) == pgno)
854 return (1);
855 return (0);
856 }
857
858 void
__pgin_routine(pg_cookie,pgno,page)859 __pgin_routine(pg_cookie, pgno, page)
860 void *pg_cookie;
861 db_pgno_t pgno;
862 void *page;
863 {
864 HTAB *hashp;
865 PAGE16 *pagep;
866 int32_t max, i;
867
868 pagep = (PAGE16 *)page;
869 hashp = (HTAB *)pg_cookie;
870
871 /*
872 * There are the following cases for swapping:
873 * 0) New page that may be unitialized.
874 * 1) Bucket page or overflow page. Either swap
875 * the header or initialize the page.
876 * 2) Bitmap page. Swap the whole page!
877 * 3) Header pages. Not handled here; these are written directly
878 * to the file.
879 */
880
881 if (NUM_ENT(pagep) == 0 && NEXT_PGNO(pagep) == 0 &&
882 !is_bitmap_pgno(hashp, pgno)) {
883 /* XXX check for !0 LSN */
884 page_init(hashp, pagep, pgno, HASH_PAGE);
885 return;
886 }
887
888 if (hashp->hdr.lorder == DB_BYTE_ORDER)
889 return;
890 if (is_bitmap_pgno(hashp, pgno)) {
891 max = hashp->hdr.bsize >> 2; /* divide by 4 bytes */
892 for (i = 0; i < max; i++)
893 M_32_SWAP(((int32_t *)pagep)[i]);
894 } else
895 swap_page_header_in(pagep);
896 }
897
898 void
__pgout_routine(pg_cookie,pgno,page)899 __pgout_routine(pg_cookie, pgno, page)
900 void *pg_cookie;
901 db_pgno_t pgno;
902 void *page;
903 {
904 HTAB *hashp;
905 PAGE16 *pagep;
906 int32_t i, max;
907
908 pagep = (PAGE16 *)page;
909 hashp = (HTAB *)pg_cookie;
910
911 /*
912 * There are the following cases for swapping:
913 * 1) Bucket page or overflow page. Just swap the header.
914 * 2) Bitmap page. Swap the whole page!
915 * 3) Header pages. Not handled here; these are written directly
916 * to the file.
917 */
918
919 if (hashp->hdr.lorder == DB_BYTE_ORDER)
920 return;
921 if (is_bitmap_pgno(hashp, pgno)) {
922 max = hashp->hdr.bsize >> 2; /* divide by 4 bytes */
923 for (i = 0; i < max; i++)
924 M_32_SWAP(((int32_t *)pagep)[i]);
925 } else
926 swap_page_header_out(pagep);
927 }
928
929 /*
930 *
931 * Returns:
932 * 0 ==> OK
933 * -1 ==>failure
934 */
935 extern int32_t
936 __put_page(hashp, pagep, addr_type, is_dirty)
937 HTAB *hashp;
938 PAGE16 *pagep;
939 int32_t addr_type, is_dirty;
940 {
941 #if DEBUG_SLOW
942 account_page(hashp,
943 ((BKT *)((char *)pagep - sizeof(BKT)))->pgno, -1);
944 #endif
945
946 return (mpool_put(hashp->mp, pagep, (is_dirty ? MPOOL_DIRTY : 0)));
947 }
948
949 /*
950 * Returns:
951 * 0 indicates SUCCESS
952 * -1 indicates FAILURE
953 */
954 extern PAGE16 *
955 __get_page(hashp, addr, addr_type)
956 HTAB *hashp;
957 u_int32_t addr;
958 int32_t addr_type;
959 {
960 PAGE16 *pagep;
961 db_pgno_t paddr;
962
963 switch (addr_type) { /* Convert page number. */
964 case A_BUCKET:
965 paddr = BUCKET_TO_PAGE(addr);
966 break;
967 case A_OVFL:
968 case A_BITMAP:
969 paddr = OADDR_TO_PAGE(addr);
970 break;
971 default:
972 paddr = addr;
973 break;
974 }
975 pagep = (PAGE16 *)mpool_get(hashp->mp, paddr, 0);
976
977 #if DEBUG_SLOW
978 account_page(hashp, paddr, 1);
979 #endif
980 #ifdef DEBUG
981 assert(ADDR(pagep) == paddr || ADDR(pagep) == 0 ||
982 addr_type == A_BITMAP || addr_type == A_HEADER);
983 #endif
984
985 return (pagep);
986 }
987
988 static void
swap_page_header_in(pagep)989 swap_page_header_in(pagep)
990 PAGE16 *pagep;
991 {
992 u_int32_t i;
993
994 /* can leave type and filler alone, since they're 1-byte quantities */
995
996 M_32_SWAP(PREV_PGNO(pagep));
997 M_32_SWAP(NEXT_PGNO(pagep));
998 M_16_SWAP(NUM_ENT(pagep));
999 M_16_SWAP(OFFSET(pagep));
1000
1001 for (i = 0; i < NUM_ENT(pagep); i++) {
1002 M_16_SWAP(KEY_OFF(pagep, i));
1003 M_16_SWAP(DATA_OFF(pagep, i));
1004 }
1005 }
1006
1007 static void
swap_page_header_out(pagep)1008 swap_page_header_out(pagep)
1009 PAGE16 *pagep;
1010 {
1011 u_int32_t i;
1012
1013 for (i = 0; i < NUM_ENT(pagep); i++) {
1014 M_16_SWAP(KEY_OFF(pagep, i));
1015 M_16_SWAP(DATA_OFF(pagep, i))
1016 }
1017
1018 /* can leave type and filler alone, since they're 1-byte quantities */
1019
1020 M_32_SWAP(PREV_PGNO(pagep));
1021 M_32_SWAP(NEXT_PGNO(pagep));
1022 M_16_SWAP(NUM_ENT(pagep));
1023 M_16_SWAP(OFFSET(pagep));
1024 }
1025
1026 #define BYTE_MASK ((1 << INT32_T_BYTE_SHIFT) -1)
1027 /*
1028 * Initialize a new bitmap page. Bitmap pages are left in memory
1029 * once they are read in.
1030 */
1031 extern int32_t
1032 __ibitmap(hashp, pnum, nbits, ndx)
1033 HTAB *hashp;
1034 int32_t pnum, nbits, ndx;
1035 {
1036 u_int32_t *ip;
1037 int32_t clearbytes, clearints;
1038
1039 /* make a new bitmap page */
1040 if (__new_page(hashp, pnum, A_BITMAP) != 0)
1041 return (1);
1042 if (!(ip = (u_int32_t *)__get_page(hashp, pnum, A_BITMAP)))
1043 return (1);
1044 hashp->nmaps++;
1045 clearints = ((nbits - 1) >> INT32_T_BYTE_SHIFT) + 1;
1046 clearbytes = clearints << INT32_T_TO_BYTE;
1047 (void)memset((int8_t *)ip, 0, clearbytes);
1048 (void)memset((int8_t *)ip + clearbytes,
1049 0xFF, hashp->hdr.bsize - clearbytes);
1050 ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
1051 SETBIT(ip, 0);
1052 hashp->hdr.bitmaps[ndx] = (u_int16_t)pnum;
1053 hashp->mapp[ndx] = ip;
1054 return (0);
1055 }
1056
1057 static u_int32_t
first_free(map)1058 first_free(map)
1059 u_int32_t map;
1060 {
1061 u_int32_t i, mask;
1062
1063 for (mask = 0x1, i = 0; i < BITS_PER_MAP; i++) {
1064 if (!(mask & map))
1065 return (i);
1066 mask = mask << 1;
1067 }
1068 return (i);
1069 }
1070
1071 /*
1072 * returns 0 on error
1073 */
1074 static u_int16_t
overflow_page(hashp)1075 overflow_page(hashp)
1076 HTAB *hashp;
1077 {
1078 u_int32_t *freep;
1079 int32_t bit, first_page, free_bit, free_page, i, in_use_bits, j;
1080 int32_t max_free, offset, splitnum;
1081 u_int16_t addr;
1082 #ifdef DEBUG2
1083 int32_t tmp1, tmp2;
1084 #endif
1085
1086 splitnum = hashp->hdr.ovfl_point;
1087 max_free = hashp->hdr.spares[splitnum];
1088
1089 free_page = (max_free - 1) >> (hashp->hdr.bshift + BYTE_SHIFT);
1090 free_bit = (max_free - 1) & ((hashp->hdr.bsize << BYTE_SHIFT) - 1);
1091
1092 /*
1093 * Look through all the free maps to find the first free block.
1094 * The compiler under -Wall will complain that freep may be used
1095 * before being set, however, this loop will ALWAYS get executed
1096 * at least once, so freep is guaranteed to be set.
1097 */
1098 first_page = hashp->hdr.last_freed >> (hashp->hdr.bshift + BYTE_SHIFT);
1099 for (i = first_page; i <= free_page; i++) {
1100 if (!(freep = fetch_bitmap(hashp, i)))
1101 return (0);
1102 if (i == free_page)
1103 in_use_bits = free_bit;
1104 else
1105 in_use_bits = (hashp->hdr.bsize << BYTE_SHIFT) - 1;
1106
1107 if (i == first_page) {
1108 bit = hashp->hdr.last_freed &
1109 ((hashp->hdr.bsize << BYTE_SHIFT) - 1);
1110 j = bit / BITS_PER_MAP;
1111 bit = bit & ~(BITS_PER_MAP - 1);
1112 } else {
1113 bit = 0;
1114 j = 0;
1115 }
1116 for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
1117 if (freep[j] != ALL_SET)
1118 goto found;
1119 }
1120
1121 /* No Free Page Found */
1122 hashp->hdr.last_freed = hashp->hdr.spares[splitnum];
1123 hashp->hdr.spares[splitnum]++;
1124 offset = hashp->hdr.spares[splitnum] -
1125 (splitnum ? hashp->hdr.spares[splitnum - 1] : 0);
1126
1127 #define OVMSG "HASH: Out of overflow pages. Increase page size\n"
1128
1129 if (offset > SPLITMASK) {
1130 if (++splitnum >= NCACHED) {
1131 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
1132 return (0);
1133 }
1134 hashp->hdr.ovfl_point = splitnum;
1135 hashp->hdr.spares[splitnum] = hashp->hdr.spares[splitnum - 1];
1136 hashp->hdr.spares[splitnum - 1]--;
1137 offset = 1;
1138 }
1139 /* Check if we need to allocate a new bitmap page. */
1140 if (free_bit == (hashp->hdr.bsize << BYTE_SHIFT) - 1) {
1141 free_page++;
1142 if (free_page >= NCACHED) {
1143 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
1144 return (0);
1145 }
1146 /*
1147 * This is tricky. The 1 indicates that you want the new page
1148 * allocated with 1 clear bit. Actually, you are going to
1149 * allocate 2 pages from this map. The first is going to be
1150 * the map page, the second is the overflow page we were
1151 * looking for. The __ibitmap routine automatically, sets
1152 * the first bit of itself to indicate that the bitmap itself
1153 * is in use. We would explicitly set the second bit, but
1154 * don't have to if we tell __ibitmap not to leave it clear
1155 * in the first place.
1156 */
1157 if (__ibitmap(hashp,
1158 (int32_t)OADDR_OF(splitnum, offset), 1, free_page))
1159 return (0);
1160 hashp->hdr.spares[splitnum]++;
1161 #ifdef DEBUG2
1162 free_bit = 2;
1163 #endif
1164 offset++;
1165 if (offset > SPLITMASK) {
1166 if (++splitnum >= NCACHED) {
1167 (void)write(STDERR_FILENO,
1168 OVMSG, sizeof(OVMSG) - 1);
1169 return (0);
1170 }
1171 hashp->hdr.ovfl_point = splitnum;
1172 hashp->hdr.spares[splitnum] =
1173 hashp->hdr.spares[splitnum - 1];
1174 hashp->hdr.spares[splitnum - 1]--;
1175 offset = 0;
1176 }
1177 } else {
1178 /*
1179 * Free_bit addresses the last used bit. Bump it to address
1180 * the first available bit.
1181 */
1182 free_bit++;
1183 SETBIT(freep, free_bit);
1184 }
1185
1186 /* Calculate address of the new overflow page */
1187 addr = OADDR_OF(splitnum, offset);
1188 #ifdef DEBUG2
1189 (void)fprintf(stderr, dgettext(TEXT_DOMAIN,
1190 "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n"),
1191 addr, free_bit, free_page);
1192 #endif
1193
1194 if (OADDR_TO_PAGE(addr) > MAX_PAGES(hashp)) {
1195 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
1196 return (0);
1197 }
1198 return (addr);
1199
1200 found:
1201 bit = bit + first_free(freep[j]);
1202 SETBIT(freep, bit);
1203 #ifdef DEBUG2
1204 tmp1 = bit;
1205 tmp2 = i;
1206 #endif
1207 /*
1208 * Bits are addressed starting with 0, but overflow pages are addressed
1209 * beginning at 1. Bit is a bit address number, so we need to increment
1210 * it to convert it to a page number.
1211 */
1212 bit = 1 + bit + (i * (hashp->hdr.bsize << BYTE_SHIFT));
1213 if (bit >= hashp->hdr.last_freed)
1214 hashp->hdr.last_freed = bit - 1;
1215
1216 /* Calculate the split number for this page */
1217 for (i = 0; i < splitnum && (bit > hashp->hdr.spares[i]); i++);
1218 offset = (i ? bit - hashp->hdr.spares[i - 1] : bit);
1219 if (offset >= SPLITMASK)
1220 return (0); /* Out of overflow pages */
1221 addr = OADDR_OF(i, offset);
1222 #ifdef DEBUG2
1223 (void)fprintf(stderr, dgettext(TEXT_DOMAIN,
1224 "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n"),
1225 addr, tmp1, tmp2);
1226 #endif
1227
1228 if (OADDR_TO_PAGE(addr) > MAX_PAGES(hashp)) {
1229 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
1230 return (0);
1231 }
1232 /* Allocate and return the overflow page */
1233 return (addr);
1234 }
1235
1236 #ifdef DEBUG
1237 int
bucket_to_page(hashp,n)1238 bucket_to_page(hashp, n)
1239 HTAB *hashp;
1240 int n;
1241 {
1242 int ret_val;
1243
1244 ret_val = n + hashp->hdr.hdrpages;
1245 if (n != 0)
1246 ret_val += hashp->hdr.spares[__log2(n + 1) - 1];
1247 return (ret_val);
1248 }
1249
1250 int32_t
oaddr_to_page(hashp,n)1251 oaddr_to_page(hashp, n)
1252 HTAB *hashp;
1253 int n;
1254 {
1255 int ret_val, temp;
1256
1257 temp = (1 << SPLITNUM(n)) - 1;
1258 ret_val = bucket_to_page(hashp, temp);
1259 ret_val += (n & SPLITMASK);
1260
1261 return (ret_val);
1262 }
1263 #endif /* DEBUG */
1264
1265 static indx_t
page_to_oaddr(hashp,pgno)1266 page_to_oaddr(hashp, pgno)
1267 HTAB *hashp;
1268 db_pgno_t pgno;
1269 {
1270 int32_t sp, ret_val;
1271
1272 /*
1273 * To convert page number to overflow address:
1274 *
1275 * 1. Find a starting split point -- use 0 since there are only
1276 * 32 split points.
1277 * 2. Find the split point s.t. 2^sp + hdr.spares[sp] < pgno and
1278 * 2^(sp+1) = hdr.spares[sp+1] > pgno. The overflow address will
1279 * be located at sp.
1280 * 3. return...
1281 */
1282 pgno -= hashp->hdr.hdrpages;
1283 for (sp = 0; sp < NCACHED; sp++)
1284 if (POW2(sp) + hashp->hdr.spares[sp] < pgno &&
1285 (POW2(sp + 1) + hashp->hdr.spares[sp + 1]) > pgno)
1286 break;
1287
1288 ret_val = OADDR_OF(sp + 1,
1289 pgno - ((POW2(sp + 1) - 1) + hashp->hdr.spares[sp]));
1290 #ifdef DEBUG
1291 assert(OADDR_TO_PAGE(ret_val) == (pgno + hashp->hdr.hdrpages));
1292 #endif
1293 return (ret_val);
1294 }
1295
1296 /*
1297 * Mark this overflow page as free.
1298 */
1299 extern void
1300 __free_ovflpage(hashp, pagep)
1301 HTAB *hashp;
1302 PAGE16 *pagep;
1303 {
1304 u_int32_t *freep;
1305 int32_t bit_address, free_page, free_bit;
1306 u_int16_t addr, ndx;
1307
1308 addr = page_to_oaddr(hashp, ADDR(pagep));
1309
1310 #ifdef DEBUG2
1311 (void)fprintf(stderr, dgettext(TEXT_DOMAIN,
1312 "Freeing %d\n"), addr);
1313 #endif
1314 ndx = ((u_int16_t)addr) >> SPLITSHIFT;
1315 bit_address =
1316 (ndx ? hashp->hdr.spares[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
1317 if (bit_address < hashp->hdr.last_freed)
1318 hashp->hdr.last_freed = bit_address;
1319 free_page = (bit_address >> (hashp->hdr.bshift + BYTE_SHIFT));
1320 free_bit = bit_address & ((hashp->hdr.bsize << BYTE_SHIFT) - 1);
1321
1322 freep = fetch_bitmap(hashp, free_page);
1323 #ifdef DEBUG
1324 /*
1325 * This had better never happen. It means we tried to read a bitmap
1326 * that has already had overflow pages allocated off it, and we
1327 * failed to read it from the file.
1328 */
1329 if (!freep)
1330 assert(0);
1331 #endif
1332 CLRBIT(freep, free_bit);
1333 #ifdef DEBUG2
1334 (void)fprintf(stderr, dgettext(TEXT_DOMAIN,
1335 "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n"),
1336 obufp->addr, free_bit, free_page);
1337 #endif
1338 }
1339
1340 static u_int32_t *
fetch_bitmap(hashp,ndx)1341 fetch_bitmap(hashp, ndx)
1342 HTAB *hashp;
1343 int32_t ndx;
1344 {
1345 if (ndx >= hashp->nmaps)
1346 return (NULL);
1347 if (!hashp->mapp[ndx])
1348 hashp->mapp[ndx] = (u_int32_t *)__get_page(hashp,
1349 hashp->hdr.bitmaps[ndx], A_BITMAP);
1350
1351 return (hashp->mapp[ndx]);
1352 }
1353
1354 #ifdef DEBUG_SLOW
1355 static void
account_page(hashp,pgno,inout)1356 account_page(hashp, pgno, inout)
1357 HTAB *hashp;
1358 db_pgno_t pgno;
1359 int inout;
1360 {
1361 static struct {
1362 db_pgno_t pgno;
1363 int times;
1364 } list[100];
1365 static int last;
1366 int i, j;
1367
1368 if (inout == -1) /* XXX: Kluge */
1369 inout = 0;
1370
1371 /* Find page in list. */
1372 for (i = 0; i < last; i++)
1373 if (list[i].pgno == pgno)
1374 break;
1375 /* Not found. */
1376 if (i == last) {
1377 list[last].times = inout;
1378 list[last].pgno = pgno;
1379 last++;
1380 }
1381 list[i].times = inout;
1382 if (list[i].times == 0) {
1383 for (j = i; j < last; j++)
1384 list[j] = list[j + 1];
1385 last--;
1386 }
1387 for (i = 0; i < last; i++, list[i].times++)
1388 if (list[i].times > 20 && !is_bitmap_pgno(hashp, list[i].pgno))
1389 (void)fprintf(stderr,
1390 dgettext(TEXT_DOMAIN,
1391 "Warning: pg %d has been out for %d times\n"),
1392 list[i].pgno, list[i].times);
1393 }
1394 #endif /* DEBUG_SLOW */
1395