2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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. ***REMOVED*** - see
17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
18 * 4. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 #define MY_LSEEK lseek
38 #define MY_LSEEK new_lseek
39 extern long new_lseek(int fd
, long pos
, int start
);
42 #if defined(LIBC_SCCS) && !defined(lint)
43 static char sccsid
[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94";
44 #endif /* LIBC_SCCS and not lint */
50 * Page manipulation for hashing package.
62 #include <sys/types.h>
65 #if defined(macintosh)
71 #if defined(_WIN32) || defined(_WINDOWS)
79 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
88 /* #include "extern.h" */
90 extern int mkstempflags(char *path
, int extraFlags
);
92 static uint32
*fetch_bitmap
__P((HTAB
*, uint32
));
93 static uint32 first_free
__P((uint32
));
94 static int open_temp
__P((HTAB
*));
95 static uint16 overflow_page
__P((HTAB
*));
96 static void squeeze_key
__P((uint16
*, const DBT
*, const DBT
*));
98 __P((HTAB
*, uint32
, BUFHEAD
*, BUFHEAD
*, int, int));
100 #define PAGE_INIT(P) { \
101 ((uint16 *)(P))[0] = 0; \
102 ((uint16 *)(P))[1] = hashp->BSIZE - 3 * sizeof(uint16); \
103 ((uint16 *)(P))[2] = hashp->BSIZE; \
106 /* implement a new lseek using lseek that
107 * writes zero's when extending a file
110 long new_lseek(int fd
, long offset
, int origin
)
116 if(origin
== SEEK_CUR
)
119 return(lseek(fd
, offset
, SEEK_CUR
));
121 cur_pos
= lseek(fd
, 0, SEEK_CUR
);
127 end_pos
= lseek(fd
, 0, SEEK_END
);
131 if(origin
== SEEK_SET
)
133 else if(origin
== SEEK_CUR
)
134 seek_pos
= cur_pos
+ offset
;
135 else if(origin
== SEEK_END
)
136 seek_pos
= end_pos
+ offset
;
143 /* the seek position desired is before the
144 * end of the file. We don't need
145 * to do anything special except the seek.
147 if(seek_pos
<= end_pos
)
148 return(lseek(fd
, seek_pos
, SEEK_SET
));
150 /* the seek position is beyond the end of the
151 * file. Write zero's to the end.
153 * we are already at the end of the file so
154 * we just need to "write()" zeros for the
155 * difference between seek_pos-end_pos and
156 * then seek to the position to finish
161 long len
= seek_pos
-end_pos
;
162 memset(&buffer
, 0, 1024);
165 write(fd
, (char*)&buffer
, (size_t)(1024 > len
? len
: 1024));
168 return(lseek(fd
, seek_pos
, SEEK_SET
));
174 * This is called AFTER we have verified that there is room on the page for
175 * the pair (PAIRFITS has returned true) so we go right ahead and start moving
179 putpair(char *p
, const DBT
*key
, DBT
* val
)
181 register uint16
*bp
, n
, off
;
185 /* Enter the key first. */
188 off
= OFFSET(bp
) - key
->size
;
189 memmove(p
+ off
, key
->data
, key
->size
);
194 memmove(p
+ off
, val
->data
, val
->size
);
197 /* Adjust page info. */
199 bp
[n
+ 1] = off
- ((n
+ 3) * sizeof(uint16
));
209 __delpair(HTAB
*hashp
, BUFHEAD
*bufp
, int ndx
)
211 register uint16
*bp
, newoff
;
215 bp
= (uint16
*)bufp
->page
;
218 if (bp
[ndx
+ 1] < REAL_KEY
)
219 return (__big_delete(hashp
, bufp
));
221 newoff
= bp
[ndx
- 1];
223 newoff
= hashp
->BSIZE
;
224 pairlen
= newoff
- bp
[ndx
+ 1];
226 if (ndx
!= (n
- 1)) {
227 /* Hard Case -- need to shuffle keys */
229 register char *src
= bufp
->page
+ (int)OFFSET(bp
);
230 uint32 dst_offset
= (uint32
)OFFSET(bp
) + (uint32
)pairlen
;
231 register char *dst
= bufp
->page
+ dst_offset
;
232 uint32 length
= bp
[ndx
+ 1] - OFFSET(bp
);
235 * +-----------+XXX+---------+XXX+---------+---------> +infinity
237 * 0 src_offset dst_offset BSIZE
239 * Dst_offset is > src_offset, so if src_offset were bad, dst_offset
240 * would be too, therefore we check only dst_offset.
242 * If dst_offset is >= BSIZE, either OFFSET(bp), or pairlen, or both
245 * Once we know dst_offset is < BSIZE, we can subtract it from BSIZE
246 * to get an upper bound on length.
248 if(dst_offset
> (uint32
)hashp
->BSIZE
)
249 return(DATABASE_CORRUPTED_ERROR
);
251 if(length
> (uint32
)(hashp
->BSIZE
- dst_offset
))
252 return(DATABASE_CORRUPTED_ERROR
);
254 memmove(dst
, src
, length
);
256 /* Now adjust the pointers */
257 for (i
= ndx
+ 2; i
<= n
; i
+= 2) {
258 if (bp
[i
+ 1] == OVFLPAGE
) {
260 bp
[i
- 1] = bp
[i
+ 1];
262 bp
[i
- 2] = bp
[i
] + pairlen
;
263 bp
[i
- 1] = bp
[i
+ 1] + pairlen
;
267 /* Finally adjust the page data */
268 bp
[n
] = OFFSET(bp
) + pairlen
;
269 bp
[n
- 1] = bp
[n
+ 1] + pairlen
+ 2 * sizeof(uint16
);
273 bufp
->flags
|= BUF_MOD
;
282 __split_page(HTAB
*hashp
, uint32 obucket
, uint32 nbucket
)
284 register BUFHEAD
*new_bufp
, *old_bufp
;
285 register uint16
*ino
;
286 register uint16
*tmp_uint16_array
;
291 uint16 copyto
, diff
, moved
;
295 copyto
= (uint16
)hashp
->BSIZE
;
296 off
= (uint16
)hashp
->BSIZE
;
297 old_bufp
= __get_buf(hashp
, obucket
, NULL
, 0);
298 if (old_bufp
== NULL
)
300 new_bufp
= __get_buf(hashp
, nbucket
, NULL
, 0);
301 if (new_bufp
== NULL
)
304 old_bufp
->flags
|= (BUF_MOD
| BUF_PIN
);
305 new_bufp
->flags
|= (BUF_MOD
| BUF_PIN
);
307 ino
= (uint16
*)(op
= old_bufp
->page
);
312 for (n
= 1, ndx
= 1; n
< ino
[0]; n
+= 2) {
313 if (ino
[n
+ 1] < REAL_KEY
) {
314 retval
= ugly_split(hashp
, obucket
, old_bufp
, new_bufp
,
315 (int)copyto
, (int)moved
);
316 old_bufp
->flags
&= ~BUF_PIN
;
317 new_bufp
->flags
&= ~BUF_PIN
;
321 key
.data
= (uint8
*)op
+ ino
[n
];
323 /* check here for ino[n] being greater than
324 * off. If it is then the database has
328 return(DATABASE_CORRUPTED_ERROR
);
330 key
.size
= off
- ino
[n
];
333 /* make sure the size is positive */
334 assert(((int)key
.size
) > -1);
337 if (__call_hash(hashp
, (char *)key
.data
, key
.size
) == obucket
) {
338 /* Don't switch page */
341 copyto
= ino
[n
+ 1] + diff
;
342 memmove(op
+ copyto
, op
+ ino
[n
+ 1],
344 ino
[ndx
] = copyto
+ ino
[n
] - ino
[n
+ 1];
345 ino
[ndx
+ 1] = copyto
;
351 val
.data
= (uint8
*)op
+ ino
[n
+ 1];
352 val
.size
= ino
[n
] - ino
[n
+ 1];
354 /* if the pair doesn't fit something is horribly
357 tmp_uint16_array
= (uint16
*)np
;
358 if(!PAIRFITS(tmp_uint16_array
, &key
, &val
))
359 return(DATABASE_CORRUPTED_ERROR
);
361 putpair(np
, &key
, &val
);
368 /* Now clean up the page */
370 FREESPACE(ino
) = copyto
- sizeof(uint16
) * (ino
[0] + 3);
371 OFFSET(ino
) = copyto
;
374 (void)fprintf(stderr
, "split %d/%d\n",
375 ((uint16
*)np
)[0] / 2,
376 ((uint16
*)op
)[0] / 2);
378 /* unpin both pages */
379 old_bufp
->flags
&= ~BUF_PIN
;
380 new_bufp
->flags
&= ~BUF_PIN
;
385 * Called when we encounter an overflow or big key/data page during split
386 * handling. This is special cased since we have to begin checking whether
387 * the key/data pairs fit on their respective pages and because we may need
388 * overflow pages for both the old and new pages.
390 * The first page might be a page with regular key/data pairs in which case
391 * we have a regular overflow condition and just need to go on to the next
392 * page or it might be a big key/data pair in which case we need to fix the
400 /* the maximum number of loops we will allow UGLY split to chew
401 * on before we assume the database is corrupted and throw it
404 #define MAX_UGLY_SPLIT_LOOPS 10000
407 ugly_split(HTAB
*hashp
, uint32 obucket
, BUFHEAD
*old_bufp
,
408 BUFHEAD
*new_bufp
,/* Same as __split_page. */ int copyto
, int moved
)
409 /* int copyto; First byte on page which contains key/data values. */
410 /* int moved; Number of pairs moved to new page. */
412 register BUFHEAD
*bufp
; /* Buffer header for ino */
413 register uint16
*ino
; /* Page keys come off of */
414 register uint16
*np
; /* New page */
415 register uint16
*op
; /* Page keys go on to if they aren't moving */
416 uint32 loop_detection
=0;
418 BUFHEAD
*last_bfp
; /* Last buf header OVFL needing to be freed */
421 uint16 n
, off
, ov_addr
, scopyto
;
422 char *cino
; /* Character value of ino */
426 ino
= (uint16
*)old_bufp
->page
;
427 np
= (uint16
*)new_bufp
->page
;
428 op
= (uint16
*)old_bufp
->page
;
430 scopyto
= (uint16
)copyto
; /* ANSI */
436 /* this function goes nuts sometimes and never returns.
437 * I havent found the problem yet but I need a solution
438 * so if we loop too often we assume a database curruption error
443 if(loop_detection
> MAX_UGLY_SPLIT_LOOPS
)
444 return DATABASE_CORRUPTED_ERROR
;
446 if (ino
[2] < REAL_KEY
&& ino
[2] != OVFLPAGE
) {
447 if ((status
= __big_split(hashp
, old_bufp
,
448 new_bufp
, bufp
, bufp
->addr
, obucket
, &ret
)))
453 op
= (uint16
*)old_bufp
->page
;
457 np
= (uint16
*)new_bufp
->page
;
461 cino
= (char *)bufp
->page
;
462 ino
= (uint16
*)cino
;
463 last_bfp
= ret
.nextp
;
464 } else if (ino
[n
+ 1] == OVFLPAGE
) {
467 * Fix up the old page -- the extra 2 are the fields
468 * which contained the overflow information.
470 ino
[0] -= (moved
+ 2);
472 scopyto
- sizeof(uint16
) * (ino
[0] + 3);
473 OFFSET(ino
) = scopyto
;
475 bufp
= __get_buf(hashp
, ov_addr
, bufp
, 0);
479 ino
= (uint16
*)bufp
->page
;
481 scopyto
= hashp
->BSIZE
;
485 __free_ovflpage(hashp
, last_bfp
);
488 /* Move regular sized pairs of there are any */
490 for (n
= 1; (n
< ino
[0]) && (ino
[n
+ 1] >= REAL_KEY
); n
+= 2) {
492 key
.data
= (uint8
*)cino
+ ino
[n
];
493 key
.size
= off
- ino
[n
];
494 val
.data
= (uint8
*)cino
+ ino
[n
+ 1];
495 val
.size
= ino
[n
] - ino
[n
+ 1];
498 if (__call_hash(hashp
, (char*)key
.data
, key
.size
) == obucket
) {
499 /* Keep on old page */
500 if (PAIRFITS(op
, (&key
), (&val
)))
501 putpair((char *)op
, &key
, &val
);
504 __add_ovflpage(hashp
, old_bufp
);
507 op
= (uint16
*)old_bufp
->page
;
508 putpair((char *)op
, &key
, &val
);
510 old_bufp
->flags
|= BUF_MOD
;
512 /* Move to new page */
513 if (PAIRFITS(np
, (&key
), (&val
)))
514 putpair((char *)np
, &key
, &val
);
517 __add_ovflpage(hashp
, new_bufp
);
520 np
= (uint16
*)new_bufp
->page
;
521 putpair((char *)np
, &key
, &val
);
523 new_bufp
->flags
|= BUF_MOD
;
528 __free_ovflpage(hashp
, last_bfp
);
533 * Add the given pair to the page
540 __addel(HTAB
*hashp
, BUFHEAD
*bufp
, const DBT
*key
, const DBT
* val
)
542 register uint16
*bp
, *sop
;
545 bp
= (uint16
*)bufp
->page
;
547 while (bp
[0] && (bp
[2] < REAL_KEY
|| bp
[bp
[0]] < REAL_KEY
))
549 if (bp
[2] == FULL_KEY_DATA
&& bp
[0] == 2)
550 /* This is the last page of a big key/data pair
551 and we need to add another page */
553 else if (bp
[2] < REAL_KEY
&& bp
[bp
[0]] != OVFLPAGE
) {
554 bufp
= __get_buf(hashp
, bp
[bp
[0] - 1], bufp
, 0);
562 bp
= (uint16
*)bufp
->page
;
564 /* Try to squeeze key on this page */
565 if (FREESPACE(bp
) > PAIRSIZE(key
, val
)) {
567 squeeze_key(bp
, key
, val
);
569 /* LJM: I added this because I think it was
570 * left out on accident.
571 * if this isn't incremented nkeys will not
572 * be the actual number of keys in the db.
578 bufp
= __get_buf(hashp
, bp
[bp
[0] - 1], bufp
, 0);
586 bp
= (uint16
*)bufp
->page
;
589 if (PAIRFITS(bp
, key
, val
))
590 putpair(bufp
->page
, key
, (DBT
*)val
);
593 bufp
= __add_ovflpage(hashp
, bufp
);
601 sop
= (uint16
*)bufp
->page
;
603 if (PAIRFITS(sop
, key
, val
))
604 putpair((char *)sop
, key
, (DBT
*)val
);
606 if (__big_insert(hashp
, bufp
, key
, val
))
614 bufp
->flags
|= BUF_MOD
;
616 * If the average number of keys per bucket exceeds the fill factor,
621 (hashp
->NKEYS
/ (hashp
->MAX_BUCKET
+ 1) > hashp
->FFACTOR
))
622 return (__expand_table(hashp
));
633 __add_ovflpage(HTAB
*hashp
, BUFHEAD
*bufp
)
636 uint16 ndx
, ovfl_num
;
640 sp
= (uint16
*)bufp
->page
;
642 /* Check if we are dynamically determining the fill factor */
643 if (hashp
->FFACTOR
== DEF_FFACTOR
) {
644 hashp
->FFACTOR
= sp
[0] >> 1;
645 if (hashp
->FFACTOR
< MIN_FFACTOR
)
646 hashp
->FFACTOR
= MIN_FFACTOR
;
648 bufp
->flags
|= BUF_MOD
;
649 ovfl_num
= overflow_page(hashp
);
652 tmp2
= bufp
->ovfl
? bufp
->ovfl
->addr
: 0;
654 if (!ovfl_num
|| !(bufp
->ovfl
= __get_buf(hashp
, ovfl_num
, bufp
, 1)))
656 bufp
->ovfl
->flags
|= BUF_MOD
;
658 (void)fprintf(stderr
, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
659 tmp1
, tmp2
, bufp
->ovfl
->addr
);
663 * Since a pair is allocated on a page only if there's room to add
664 * an overflow page, we know that the OVFL information will fit on
667 sp
[ndx
+ 4] = OFFSET(sp
);
668 sp
[ndx
+ 3] = FREESPACE(sp
) - OVFLSIZE
;
669 sp
[ndx
+ 1] = ovfl_num
;
670 sp
[ndx
+ 2] = OVFLPAGE
;
672 #ifdef HASH_STATISTICS
680 * 0 indicates SUCCESS
681 * -1 indicates FAILURE
684 __get_page(HTAB
*hashp
,
691 register int fd
, page
;
699 if ((fd
== -1) || !is_disk
) {
704 page
= BUCKET_TO_PAGE(bucket
);
706 page
= OADDR_TO_PAGE(bucket
);
707 if ((MY_LSEEK(fd
, (off_t
)page
<< hashp
->BSHIFT
, SEEK_SET
) == -1) ||
708 ((rsize
= read(fd
, p
, size
)) == -1))
713 bp
[0] = 0; /* We hit the EOF, so initialize a new page */
715 if ((unsigned)rsize
!= size
) {
720 if (!is_bitmap
&& !bp
[0]) {
725 if(BYTE_ORDER
== LITTLE_ENDIAN
)
727 int is_little_endian
;
728 is_little_endian
= BYTE_ORDER
;
730 else if(BYTE_ORDER
== BIG_ENDIAN
)
733 is_big_endian
= BYTE_ORDER
;
741 if (hashp
->LORDER
!= BYTE_ORDER
) {
745 max
= hashp
->BSIZE
>> 2; /* divide by 4 */
746 for (i
= 0; i
< max
; i
++)
747 M_32_SWAP(((int *)p
)[i
]);
752 /* bound the size of max by
753 * the maximum number of entries
756 if((unsigned)max
> (size
/ sizeof(uint16
)))
757 return(DATABASE_CORRUPTED_ERROR
);
759 /* do the byte order swap
761 for (i
= 1; i
<= max
; i
++)
766 /* check the validity of the page here
767 * (after doing byte order swaping if necessary)
769 if(!is_bitmap
&& bp
[0] != 0)
771 uint16 num_keys
= bp
[0];
775 /* bp[0] is supposed to be the number of
776 * entries currently in the page. If
777 * bp[0] is too large (larger than the whole
778 * page) then the page is corrupted
780 if(bp
[0] > (size
/ sizeof(uint16
)))
781 return(DATABASE_CORRUPTED_ERROR
);
783 /* bound free space */
784 if(FREESPACE(bp
) > size
)
785 return(DATABASE_CORRUPTED_ERROR
);
787 /* check each key and data offset to make
788 * sure they are all within bounds they
789 * should all be less than the previous
793 for(i
=1 ; i
<= num_keys
; i
+=2)
795 /* ignore overflow pages etc. */
796 if(bp
[i
+1] >= REAL_KEY
)
799 if(bp
[i
] > offset
|| bp
[i
+1] > bp
[i
])
800 return(DATABASE_CORRUPTED_ERROR
);
806 /* there are no other valid keys after
807 * seeing a non REAL_KEY
818 * Write page p to disk
825 __put_page(HTAB
*hashp
, char *p
, uint32 bucket
, int is_bucket
, int is_bitmap
)
827 register int fd
, page
;
833 if ((hashp
->fp
== -1) && open_temp(hashp
))
837 if (hashp
->LORDER
!= BYTE_ORDER
) {
842 max
= hashp
->BSIZE
>> 2; /* divide by 4 */
843 for (i
= 0; i
< max
; i
++)
844 M_32_SWAP(((int *)p
)[i
]);
846 max
= ((uint16
*)p
)[0] + 2;
848 /* bound the size of max by
849 * the maximum number of entries
852 if((unsigned)max
> (size
/ sizeof(uint16
)))
853 return(DATABASE_CORRUPTED_ERROR
);
855 for (i
= 0; i
<= max
; i
++)
856 M_16_SWAP(((uint16
*)p
)[i
]);
862 page
= BUCKET_TO_PAGE(bucket
);
864 page
= OADDR_TO_PAGE(bucket
);
865 offset
= (off_t
)page
<< hashp
->BSHIFT
;
866 if ((MY_LSEEK(fd
, offset
, SEEK_SET
) == -1) ||
867 ((wsize
= write(fd
, p
, size
)) == -1))
870 if ((unsigned)wsize
!= size
) {
874 #if defined(_WIN32) || defined(_WINDOWS)
875 if (offset
+ size
> hashp
->file_size
) {
876 hashp
->updateEOF
= 1;
879 /* put the page back the way it was so that it isn't byteswapped
880 * if it remains in memory - LJM
882 if (hashp
->LORDER
!= BYTE_ORDER
) {
887 max
= hashp
->BSIZE
>> 2; /* divide by 4 */
888 for (i
= 0; i
< max
; i
++)
889 M_32_SWAP(((int *)p
)[i
]);
891 uint16
*bp
= (uint16
*)p
;
896 /* no need to bound the size if max again
897 * since it was done already above
900 /* do the byte order re-swap
902 for (i
= 1; i
<= max
; i
++)
910 #define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1)
912 * Initialize a new bitmap page. Bitmap pages are left in memory
913 * once they are read in.
916 __ibitmap(HTAB
*hashp
, int pnum
, int nbits
, int ndx
)
919 size_t clearbytes
, clearints
;
921 if ((ip
= (uint32
*)malloc((size_t)hashp
->BSIZE
)) == NULL
)
924 clearints
= ((nbits
- 1) >> INT_BYTE_SHIFT
) + 1;
925 clearbytes
= clearints
<< INT_TO_BYTE
;
926 (void)memset((char *)ip
, 0, clearbytes
);
927 (void)memset(((char *)ip
) + clearbytes
, 0xFF,
928 hashp
->BSIZE
- clearbytes
);
929 ip
[clearints
- 1] = ALL_SET
<< (nbits
& BYTE_MASK
);
931 hashp
->BITMAPS
[ndx
] = (uint16
)pnum
;
932 hashp
->mapp
[ndx
] = ip
;
937 first_free(uint32 map
)
939 register uint32 i
, mask
;
942 for (i
= 0; i
< BITS_PER_MAP
; i
++) {
951 overflow_page(HTAB
*hashp
)
953 register uint32
*freep
=NULL
;
954 register int max_free
, offset
, splitnum
;
957 int bit
, first_page
, free_bit
, free_page
, in_use_bits
, j
;
961 splitnum
= hashp
->OVFL_POINT
;
962 max_free
= hashp
->SPARES
[splitnum
];
964 free_page
= (max_free
- 1) >> (hashp
->BSHIFT
+ BYTE_SHIFT
);
965 free_bit
= (max_free
- 1) & ((hashp
->BSIZE
<< BYTE_SHIFT
) - 1);
967 /* Look through all the free maps to find the first free block */
968 first_page
= hashp
->LAST_FREED
>>(hashp
->BSHIFT
+ BYTE_SHIFT
);
969 for ( i
= first_page
; i
<= (unsigned)free_page
; i
++ ) {
970 if (!(freep
= (uint32
*)hashp
->mapp
[i
]) &&
971 !(freep
= fetch_bitmap(hashp
, i
)))
973 if (i
== (unsigned)free_page
)
974 in_use_bits
= free_bit
;
976 in_use_bits
= (hashp
->BSIZE
<< BYTE_SHIFT
) - 1;
978 if (i
== (unsigned)first_page
) {
979 bit
= hashp
->LAST_FREED
&
980 ((hashp
->BSIZE
<< BYTE_SHIFT
) - 1);
981 j
= bit
/ BITS_PER_MAP
;
982 bit
= bit
& ~(BITS_PER_MAP
- 1);
987 for (; bit
<= in_use_bits
; j
++, bit
+= BITS_PER_MAP
)
988 if (freep
[j
] != ALL_SET
)
992 /* No Free Page Found */
993 hashp
->LAST_FREED
= hashp
->SPARES
[splitnum
];
994 hashp
->SPARES
[splitnum
]++;
995 offset
= hashp
->SPARES
[splitnum
] -
996 (splitnum
? hashp
->SPARES
[splitnum
- 1] : 0);
998 #define OVMSG "HASH: Out of overflow pages. Increase page size\n"
999 if (offset
> SPLITMASK
) {
1000 if (++splitnum
>= NCACHED
) {
1002 (void)write(STDERR_FILENO
, OVMSG
, sizeof(OVMSG
) - 1);
1006 hashp
->OVFL_POINT
= splitnum
;
1007 hashp
->SPARES
[splitnum
] = hashp
->SPARES
[splitnum
-1];
1008 hashp
->SPARES
[splitnum
-1]--;
1012 /* Check if we need to allocate a new bitmap page */
1013 if (free_bit
== (hashp
->BSIZE
<< BYTE_SHIFT
) - 1) {
1015 if (free_page
>= NCACHED
) {
1017 (void)write(STDERR_FILENO
, OVMSG
, sizeof(OVMSG
) - 1);
1022 * This is tricky. The 1 indicates that you want the new page
1023 * allocated with 1 clear bit. Actually, you are going to
1024 * allocate 2 pages from this map. The first is going to be
1025 * the map page, the second is the overflow page we were
1026 * looking for. The init_bitmap routine automatically, sets
1027 * the first bit of itself to indicate that the bitmap itself
1028 * is in use. We would explicitly set the second bit, but
1029 * don't have to if we tell init_bitmap not to leave it clear
1030 * in the first place.
1032 if (__ibitmap(hashp
,
1033 (int)OADDR_OF(splitnum
, offset
), 1, free_page
))
1035 hashp
->SPARES
[splitnum
]++;
1040 if (offset
> SPLITMASK
) {
1041 if (++splitnum
>= NCACHED
) {
1043 (void)write(STDERR_FILENO
, OVMSG
,
1048 hashp
->OVFL_POINT
= splitnum
;
1049 hashp
->SPARES
[splitnum
] = hashp
->SPARES
[splitnum
-1];
1050 hashp
->SPARES
[splitnum
-1]--;
1055 * Free_bit addresses the last used bit. Bump it to address
1056 * the first available bit.
1059 SETBIT(freep
, free_bit
);
1062 /* Calculate address of the new overflow page */
1063 addr
= OADDR_OF(splitnum
, offset
);
1065 (void)fprintf(stderr
, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
1066 addr
, free_bit
, free_page
);
1071 bit
= bit
+ first_free(freep
[j
]);
1078 * Bits are addressed starting with 0, but overflow pages are addressed
1079 * beginning at 1. Bit is a bit addressnumber, so we need to increment
1080 * it to convert it to a page number.
1082 bit
= 1 + bit
+ (i
* (hashp
->BSIZE
<< BYTE_SHIFT
));
1083 if (bit
>= hashp
->LAST_FREED
)
1084 hashp
->LAST_FREED
= bit
- 1;
1086 /* Calculate the split number for this page */
1087 for (i
= 0; (i
< (unsigned)splitnum
) && (bit
> hashp
->SPARES
[i
]); i
++) {}
1088 offset
= (i
? bit
- hashp
->SPARES
[i
- 1] : bit
);
1089 if (offset
>= SPLITMASK
)
1090 return (0); /* Out of overflow pages */
1091 addr
= OADDR_OF(i
, offset
);
1093 (void)fprintf(stderr
, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
1097 /* Allocate and return the overflow page */
1102 * Mark this overflow page as free.
1105 __free_ovflpage(HTAB
*hashp
, BUFHEAD
*obufp
)
1109 uint32 bit_address
, free_page
, free_bit
;
1112 if(!obufp
|| !obufp
->addr
)
1117 (void)fprintf(stderr
, "Freeing %d\n", addr
);
1119 ndx
= (((uint16
)addr
) >> SPLITSHIFT
);
1121 (ndx
? hashp
->SPARES
[ndx
- 1] : 0) + (addr
& SPLITMASK
) - 1;
1122 if (bit_address
< (uint32
)hashp
->LAST_FREED
)
1123 hashp
->LAST_FREED
= bit_address
;
1124 free_page
= (bit_address
>> (hashp
->BSHIFT
+ BYTE_SHIFT
));
1125 free_bit
= bit_address
& ((hashp
->BSIZE
<< BYTE_SHIFT
) - 1);
1127 if (!(freep
= hashp
->mapp
[free_page
]))
1128 freep
= fetch_bitmap(hashp
, free_page
);
1132 * This had better never happen. It means we tried to read a bitmap
1133 * that has already had overflow pages allocated off it, and we
1134 * failed to read it from the file.
1142 CLRBIT(freep
, free_bit
);
1144 (void)fprintf(stderr
, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
1145 obufp
->addr
, free_bit
, free_page
);
1147 __reclaim_buf(hashp
, obufp
);
1156 open_temp(HTAB
*hashp
)
1159 hashp
->fp
= mkstemp(NULL
);
1161 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1164 #if !defined(macintosh)
1169 static const char namestr
[] = "/_hashXXXXXX";
1170 char filename
[1024];
1172 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1173 /* Block signals; make sure file goes away at process exit. */
1174 (void)sigfillset(&set
);
1175 (void)sigprocmask(SIG_BLOCK
, &set
, &oset
);
1179 #if defined(macintosh)
1180 strcat(filename
, namestr
+ 1);
1182 tmpdir
= getenv("TMP");
1184 tmpdir
= getenv("TMPDIR");
1186 tmpdir
= getenv("TEMP");
1189 len
= strlen(tmpdir
);
1190 if (len
&& len
< (sizeof filename
- sizeof namestr
)) {
1191 strcpy(filename
, tmpdir
);
1193 len
= strlen(filename
);
1194 last
= tmpdir
[len
- 1];
1195 strcat(filename
, (last
== '/' || last
== '\\') ? namestr
+ 1 : namestr
);
1198 #if defined(_WIN32) || defined(_WINDOWS)
1199 if ((hashp
->fp
= mkstempflags(filename
, _O_BINARY
|_O_TEMPORARY
)) != -1) {
1200 if (hashp
->filename
) {
1201 free(hashp
->filename
);
1203 hashp
->filename
= strdup(filename
);
1207 if ((hashp
->fp
= mkstemp(filename
)) != -1) {
1208 (void)unlink(filename
);
1209 #if !defined(macintosh)
1210 (void)fcntl(hashp
->fp
, F_SETFD
, 1);
1215 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1216 (void)sigprocmask(SIG_SETMASK
, &oset
, (sigset_t
*)NULL
);
1219 return (hashp
->fp
!= -1 ? 0 : -1);
1223 * We have to know that the key will fit, but the last entry on the page is
1224 * an overflow pair, so we need to shift things.
1227 squeeze_key(uint16
*sp
, const DBT
* key
, const DBT
* val
)
1230 uint16 free_space
, n
, off
, pageno
;
1234 free_space
= FREESPACE(sp
);
1240 memmove(p
+ off
, key
->data
, key
->size
);
1243 memmove(p
+ off
, val
->data
, val
->size
);
1246 sp
[n
+ 2] = OVFLPAGE
;
1247 FREESPACE(sp
) = free_space
- PAIRSIZE(key
, val
);
1252 fetch_bitmap(HTAB
*hashp
, uint32 ndx
)
1254 if (ndx
>= (unsigned)hashp
->nmaps
)
1256 if ((hashp
->mapp
[ndx
] = (uint32
*)malloc((size_t)hashp
->BSIZE
)) == NULL
)
1258 if (__get_page(hashp
,
1259 (char *)hashp
->mapp
[ndx
], hashp
->BITMAPS
[ndx
], 0, 1, 1)) {
1260 free(hashp
->mapp
[ndx
]);
1261 hashp
->mapp
[ndx
] = NULL
; /* NEW: 9-11-95 */
1264 return (hashp
->mapp
[ndx
]);
1269 print_chain(int addr
)
1274 (void)fprintf(stderr
, "%d ", addr
);
1275 bufp
= __get_buf(hashp
, addr
, NULL
, 0);
1276 bp
= (short *)bufp
->page
;
1277 while (bp
[0] && ((bp
[bp
[0]] == OVFLPAGE
) ||
1278 ((bp
[0] > 2) && bp
[2] < REAL_KEY
))) {
1279 oaddr
= bp
[bp
[0] - 1];
1280 (void)fprintf(stderr
, "%d ", (int)oaddr
);
1281 bufp
= __get_buf(hashp
, (int)oaddr
, bufp
, 0);
1282 bp
= (short *)bufp
->page
;
1284 (void)fprintf(stderr
, "\n");