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