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