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