* Copyright (c) 1990, 1993
* The Regents of the University of California. All rights reserved.
* This code is derived from software contributed to Berkeley by
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)hash_page.c 8.1 (Berkeley) 6/6/93";
#endif /* LIBC_SCCS and not lint */
* Page manipulation for hashing package.
static u_long
*fetch_bitmap
__P((HTAB
*, int));
static u_long first_free
__P((u_long
));
static int open_temp
__P((HTAB
*));
static u_short overflow_page
__P((HTAB
*));
static void putpair
__P((char *, const DBT
*, const DBT
*));
static void squeeze_key
__P((u_short
*, const DBT
*, const DBT
*));
__P((HTAB
*, u_int
, BUFHEAD
*, BUFHEAD
*, int, int));
((u_short *)(P))[0] = 0; \
((u_short *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_short); \
((u_short *)(P))[2] = hashp->BSIZE; \
* This is called AFTER we have verified that there is room on the page for
* the pair (PAIRFITS has returned true) so we go right ahead and start moving
register u_short
*bp
, n
, off
;
/* Enter the key first. */
off
= OFFSET(bp
) - key
->size
;
memmove(p
+ off
, key
->data
, key
->size
);
memmove(p
+ off
, val
->data
, val
->size
);
bp
[n
+ 1] = off
- ((n
+ 3) * sizeof(u_short
));
__delpair(hashp
, bufp
, ndx
)
register u_short
*bp
, newoff
;
bp
= (u_short
*)bufp
->page
;
if (bp
[ndx
+ 1] < REAL_KEY
)
return (__big_delete(hashp
, bufp
));
pairlen
= newoff
- bp
[ndx
+ 1];
/* Hard Case -- need to shuffle keys */
register char *src
= bufp
->page
+ (int)OFFSET(bp
);
register char *dst
= src
+ (int)pairlen
;
memmove(dst
, src
, bp
[ndx
+ 1] - OFFSET(bp
));
/* Now adjust the pointers */
for (i
= ndx
+ 2; i
<= n
; i
+= 2) {
if (bp
[i
+ 1] == OVFLPAGE
) {
bp
[i
- 2] = bp
[i
] + pairlen
;
bp
[i
- 1] = bp
[i
+ 1] + pairlen
;
/* Finally adjust the page data */
bp
[n
] = OFFSET(bp
) + pairlen
;
bp
[n
- 1] = bp
[n
+ 1] + pairlen
+ 2 * sizeof(u_short
);
__split_page(hashp
, obucket
, nbucket
)
register BUFHEAD
*new_bufp
, *old_bufp
;
u_short copyto
, diff
, off
, moved
;
copyto
= (u_short
)hashp
->BSIZE
;
off
= (u_short
)hashp
->BSIZE
;
old_bufp
= __get_buf(hashp
, obucket
, NULL
, 0);
new_bufp
= __get_buf(hashp
, nbucket
, NULL
, 0);
old_bufp
->flags
|= (BUF_MOD
| BUF_PIN
);
new_bufp
->flags
|= (BUF_MOD
| BUF_PIN
);
ino
= (u_short
*)(op
= old_bufp
->page
);
for (n
= 1, ndx
= 1; n
< ino
[0]; n
+= 2) {
if (ino
[n
+ 1] < REAL_KEY
) {
retval
= ugly_split(hashp
, obucket
, old_bufp
, new_bufp
,
(int)copyto
, (int)moved
);
old_bufp
->flags
&= ~BUF_PIN
;
new_bufp
->flags
&= ~BUF_PIN
;
key
.data
= (u_char
*)op
+ ino
[n
];
if (__call_hash(hashp
, key
.data
, key
.size
) == obucket
) {
copyto
= ino
[n
+ 1] + diff
;
memmove(op
+ copyto
, op
+ ino
[n
+ 1],
ino
[ndx
] = copyto
+ ino
[n
] - ino
[n
+ 1];
val
.data
= (u_char
*)op
+ ino
[n
+ 1];
val
.size
= ino
[n
] - ino
[n
+ 1];
/* Now clean up the page */
FREESPACE(ino
) = copyto
- sizeof(u_short
) * (ino
[0] + 3);
(void)fprintf(stderr
, "split %d/%d\n",
old_bufp
->flags
&= ~BUF_PIN
;
new_bufp
->flags
&= ~BUF_PIN
;
* Called when we encounter an overflow or big key/data page during split
* handling. This is special cased since we have to begin checking whether
* the key/data pairs fit on their respective pages and because we may need
* overflow pages for both the old and new pages.
* The first page might be a page with regular key/data pairs in which case
* we have a regular overflow condition and just need to go on to the next
* page or it might be a big key/data pair in which case we need to fix the
ugly_split(hashp
, obucket
, old_bufp
, new_bufp
, copyto
, moved
)
u_int obucket
; /* Same as __split_page. */
BUFHEAD
*old_bufp
, *new_bufp
;
int copyto
; /* First byte on page which contains key/data values. */
int moved
; /* Number of pairs moved to new page. */
register BUFHEAD
*bufp
; /* Buffer header for ino */
register u_short
*ino
; /* Page keys come off of */
register u_short
*np
; /* New page */
register u_short
*op
; /* Page keys go on to if they aren't moving */
BUFHEAD
*last_bfp
; /* Last buf header OVFL needing to be freed */
u_short n
, off
, ov_addr
, scopyto
;
char *cino
; /* Character value of ino */
ino
= (u_short
*)old_bufp
->page
;
np
= (u_short
*)new_bufp
->page
;
op
= (u_short
*)old_bufp
->page
;
scopyto
= (u_short
)copyto
; /* ANSI */
if (ino
[2] < REAL_KEY
&& ino
[2] != OVFLPAGE
) {
* Ov_addr gets set before reaching this point; there's
* always an overflow page before a big key/data page.
if (__big_split(hashp
, old_bufp
,
new_bufp
, bufp
, ov_addr
, obucket
, &ret
))
op
= (u_short
*)old_bufp
->page
;
np
= (u_short
*)new_bufp
->page
;
cino
= (char *)bufp
->page
;
} else if (ino
[n
+ 1] == OVFLPAGE
) {
* Fix up the old page -- the extra 2 are the fields
* which contained the overflow information.
scopyto
- sizeof(u_short
) * (ino
[0] + 3);
bufp
= __get_buf(hashp
, ov_addr
, bufp
, 0);
ino
= (u_short
*)bufp
->page
;
__free_ovflpage(hashp
, last_bfp
);
/* Move regular sized pairs of there are any */
for (n
= 1; (n
< ino
[0]) && (ino
[n
+ 1] >= REAL_KEY
); n
+= 2) {
key
.data
= (u_char
*)cino
+ ino
[n
];
val
.data
= (u_char
*)cino
+ ino
[n
+ 1];
val
.size
= ino
[n
] - ino
[n
+ 1];
if (__call_hash(hashp
, key
.data
, key
.size
) == obucket
) {
if (PAIRFITS(op
, (&key
), (&val
)))
putpair((char *)op
, &key
, &val
);
__add_ovflpage(hashp
, old_bufp
);
op
= (u_short
*)old_bufp
->page
;
putpair((char *)op
, &key
, &val
);
old_bufp
->flags
|= BUF_MOD
;
if (PAIRFITS(np
, (&key
), (&val
)))
putpair((char *)np
, &key
, &val
);
__add_ovflpage(hashp
, new_bufp
);
np
= (u_short
*)new_bufp
->page
;
putpair((char *)np
, &key
, &val
);
new_bufp
->flags
|= BUF_MOD
;
__free_ovflpage(hashp
, last_bfp
);
* Add the given pair to the page
__addel(hashp
, bufp
, key
, val
)
register u_short
*bp
, *sop
;
bp
= (u_short
*)bufp
->page
;
while (bp
[0] && (bp
[bp
[0]] < REAL_KEY
))
if (bp
[2] < REAL_KEY
&& bp
[bp
[0]] != OVFLPAGE
) {
/* This is a big-keydata pair */
bufp
= __add_ovflpage(hashp
, bufp
);
bp
= (u_short
*)bufp
->page
;
/* Try to squeeze key on this page */
if (FREESPACE(bp
) > PAIRSIZE(key
, val
)) {
squeeze_key(bp
, key
, val
);
bufp
= __get_buf(hashp
, bp
[bp
[0] - 1], bufp
, 0);
bp
= (u_short
*)bufp
->page
;
if (PAIRFITS(bp
, key
, val
))
putpair(bufp
->page
, key
, val
);
bufp
= __add_ovflpage(hashp
, bufp
);
sop
= (u_short
*)bufp
->page
;
if (PAIRFITS(sop
, key
, val
))
putpair((char *)sop
, key
, val
);
if (__big_insert(hashp
, bufp
, key
, val
))
* If the average number of keys per bucket exceeds the fill factor,
(hashp
->NKEYS
/ (hashp
->MAX_BUCKET
+ 1) > hashp
->FFACTOR
))
return (__expand_table(hashp
));
__add_ovflpage(hashp
, bufp
)
sp
= (u_short
*)bufp
->page
;
/* Check if we are dynamically determining the fill factor */
if (hashp
->FFACTOR
== DEF_FFACTOR
) {
hashp
->FFACTOR
= sp
[0] >> 1;
if (hashp
->FFACTOR
< MIN_FFACTOR
)
hashp
->FFACTOR
= MIN_FFACTOR
;
ovfl_num
= overflow_page(hashp
);
tmp2
= bufp
->ovfl
? bufp
->ovfl
->addr
: 0;
if (!ovfl_num
|| !(bufp
->ovfl
= __get_buf(hashp
, ovfl_num
, bufp
, 1)))
bufp
->ovfl
->flags
|= BUF_MOD
;
(void)fprintf(stderr
, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
tmp1
, tmp2
, bufp
->ovfl
->addr
);
* Since a pair is allocated on a page only if there's room to add
* an overflow page, we know that the OVFL information will fit on
sp
[ndx
+ 4] = OFFSET(sp
);
sp
[ndx
+ 3] = FREESPACE(sp
) - OVFLSIZE
;
__get_page(hashp
, p
, bucket
, is_bucket
, is_disk
, is_bitmap
)
int is_bucket
, is_disk
, is_bitmap
;
register int fd
, page
, size
;
if ((fd
== -1) || !is_disk
) {
page
= BUCKET_TO_PAGE(bucket
);
page
= OADDR_TO_PAGE(bucket
);
if ((lseek(fd
, (off_t
)page
<< hashp
->BSHIFT
, SEEK_SET
) == -1) ||
((rsize
= read(fd
, p
, size
)) == -1))
bp
[0] = 0; /* We hit the EOF, so initialize a new page */
if (!is_bitmap
&& !bp
[0]) {
if (hashp
->LORDER
!= BYTE_ORDER
) {
max
= hashp
->BSIZE
>> 2; /* divide by 4 */
for (i
= 0; i
< max
; i
++)
for (i
= 1; i
<= max
; i
++)
__put_page(hashp
, p
, bucket
, is_bucket
, is_bitmap
)
int is_bucket
, is_bitmap
;
register int fd
, page
, size
;
if ((hashp
->fp
== -1) && open_temp(hashp
))
if (hashp
->LORDER
!= BYTE_ORDER
) {
max
= hashp
->BSIZE
>> 2; /* divide by 4 */
for (i
= 0; i
< max
; i
++)
max
= ((u_short
*)p
)[0] + 2;
for (i
= 0; i
<= max
; i
++)
BSSWAP(((u_short
*)p
)[i
]);
page
= BUCKET_TO_PAGE(bucket
);
page
= OADDR_TO_PAGE(bucket
);
if ((lseek(fd
, (off_t
)page
<< hashp
->BSHIFT
, SEEK_SET
) == -1) ||
((wsize
= write(fd
, p
, size
)) == -1))
#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1)
* Initialize a new bitmap page. Bitmap pages are left in memory
__init_bitmap(hashp
, pnum
, nbits
, ndx
)
int clearbytes
, clearints
;
if (!(ip
= malloc(hashp
->BSIZE
)))
clearints
= ((nbits
- 1) >> INT_BYTE_SHIFT
) + 1;
clearbytes
= clearints
<< INT_TO_BYTE
;
(void)memset((char *)ip
, 0, clearbytes
);
(void)memset(((char *)ip
) + clearbytes
, 0xFF,
hashp
->BSIZE
- clearbytes
);
ip
[clearints
- 1] = ALL_SET
<< (nbits
& BYTE_MASK
);
hashp
->BITMAPS
[ndx
] = (u_short
)pnum
;
for (i
= 0; i
< BITS_PER_MAP
; i
++) {
register int max_free
, offset
, splitnum
;
int bit
, first_page
, free_bit
, free_page
, i
, in_use_bits
, j
;
splitnum
= hashp
->OVFL_POINT
;
max_free
= hashp
->SPARES
[splitnum
];
free_page
= (max_free
- 1) >> (hashp
->BSHIFT
+ BYTE_SHIFT
);
free_bit
= (max_free
- 1) & ((hashp
->BSIZE
<< BYTE_SHIFT
) - 1);
/* Look through all the free maps to find the first free block */
first_page
= hashp
->LAST_FREED
>>(hashp
->BSHIFT
+ BYTE_SHIFT
);
for ( i
= first_page
; i
<= free_page
; i
++ ) {
if (!(freep
= (u_long
*)hashp
->mapp
[i
]) &&
!(freep
= fetch_bitmap(hashp
, i
)))
in_use_bits
= (hashp
->BSIZE
<< BYTE_SHIFT
) - 1;
bit
= hashp
->LAST_FREED
&
((hashp
->BSIZE
<< BYTE_SHIFT
) - 1);
bit
= bit
& ~(BITS_PER_MAP
- 1);
for (; bit
<= in_use_bits
; j
++, bit
+= BITS_PER_MAP
)
hashp
->LAST_FREED
= hashp
->SPARES
[splitnum
];
hashp
->SPARES
[splitnum
]++;
offset
= hashp
->SPARES
[splitnum
] -
(splitnum
? hashp
->SPARES
[splitnum
- 1] : 0);
#define OVMSG "HASH: Out of overflow pages. Increase page size\n"
if (offset
> SPLITMASK
) {
if (++splitnum
>= NCACHED
) {
(void)write(STDERR_FILENO
, OVMSG
, sizeof(OVMSG
) - 1);
hashp
->OVFL_POINT
= splitnum
;
hashp
->SPARES
[splitnum
] = hashp
->SPARES
[splitnum
-1];
hashp
->SPARES
[splitnum
-1]--;
/* Check if we need to allocate a new bitmap page */
if (free_bit
== (hashp
->BSIZE
<< BYTE_SHIFT
) - 1) {
if (free_page
>= NCACHED
) {
(void)write(STDERR_FILENO
, OVMSG
, sizeof(OVMSG
) - 1);
* This is tricky. The 1 indicates that you want the new page
* allocated with 1 clear bit. Actually, you are going to
* allocate 2 pages from this map. The first is going to be
* the map page, the second is the overflow page we were
* looking for. The init_bitmap routine automatically, sets
* the first bit of itself to indicate that the bitmap itself
* is in use. We would explicitly set the second bit, but
* don't have to if we tell init_bitmap not to leave it clear
if (__init_bitmap(hashp
, (int)OADDR_OF(splitnum
, offset
),
hashp
->SPARES
[splitnum
]++;
if (offset
> SPLITMASK
) {
if (++splitnum
>= NCACHED
) {
(void)write(STDERR_FILENO
, OVMSG
,
hashp
->OVFL_POINT
= splitnum
;
hashp
->SPARES
[splitnum
] = hashp
->SPARES
[splitnum
-1];
hashp
->SPARES
[splitnum
-1]--;
* Free_bit addresses the last used bit. Bump it to address
* the first available bit.
/* Calculate address of the new overflow page */
addr
= OADDR_OF(splitnum
, offset
);
(void)fprintf(stderr
, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
addr
, free_bit
, free_page
);
bit
= bit
+ first_free(freep
[j
]);
* Bits are addressed starting with 0, but overflow pages are addressed
* beginning at 1. Bit is a bit addressnumber, so we need to increment
* it to convert it to a page number.
bit
= 1 + bit
+ (i
* (hashp
->BSIZE
<< BYTE_SHIFT
));
if (bit
>= hashp
->LAST_FREED
)
hashp
->LAST_FREED
= bit
- 1;
/* Calculate the split number for this page */
for (i
= 0; (i
< splitnum
) && (bit
> hashp
->SPARES
[i
]); i
++);
offset
= (i
? bit
- hashp
->SPARES
[i
- 1] : bit
);
return (NULL
); /* Out of overflow pages */
addr
= OADDR_OF(i
, offset
);
(void)fprintf(stderr
, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
/* Allocate and return the overflow page */
* Mark this overflow page as free.
__free_ovflpage(hashp
, obufp
)
int bit_address
, free_page
, free_bit
;
(void)fprintf(stderr
, "Freeing %d\n", addr
);
ndx
= (((u_short
)addr
) >> SPLITSHIFT
);
(ndx
? hashp
->SPARES
[ndx
- 1] : 0) + (addr
& SPLITMASK
) - 1;
if (bit_address
< hashp
->LAST_FREED
)
hashp
->LAST_FREED
= bit_address
;
free_page
= (bit_address
>> (hashp
->BSHIFT
+ BYTE_SHIFT
));
free_bit
= bit_address
& ((hashp
->BSIZE
<< BYTE_SHIFT
) - 1);
if (!(freep
= hashp
->mapp
[free_page
]))
freep
= fetch_bitmap(hashp
, free_page
);
* This had better never happen. It means we tried to read a bitmap
* that has already had overflow pages allocated off it, and we
* failed to read it from the file.
(void)fprintf(stderr
, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
obufp
->addr
, free_bit
, free_page
);
__reclaim_buf(hashp
, obufp
);
static char namestr
[] = "_hashXXXXXX";
/* Block signals; make sure file goes away at process exit. */
(void)sigprocmask(SIG_BLOCK
, &set
, &oset
);
if ((hashp
->fp
= mkstemp(namestr
)) != -1) {
(void)fcntl(hashp
->fp
, F_SETFD
, 1);
(void)sigprocmask(SIG_SETMASK
, &oset
, (sigset_t
*)NULL
);
return (hashp
->fp
!= -1 ? 0 : -1);
* We have to know that the key will fit, but the last entry on the page is
* an overflow pair, so we need to shift things.
squeeze_key(sp
, key
, val
)
u_short free_space
, n
, off
, pageno
;
free_space
= FREESPACE(sp
);
memmove(p
+ off
, key
->data
, key
->size
);
memmove(p
+ off
, val
->data
, val
->size
);
FREESPACE(sp
) = free_space
- PAIRSIZE(key
, val
);
if (ndx
>= hashp
->nmaps
||
!(hashp
->mapp
[ndx
] = malloc(hashp
->BSIZE
)) ||
__get_page(hashp
, (char *)hashp
->mapp
[ndx
],
hashp
->BITMAPS
[ndx
], 0, 1, 1))
return (hashp
->mapp
[ndx
]);
(void)fprintf(stderr
, "%d ", addr
);
bufp
= __get_buf(hashp
, addr
, NULL
, 0);
bp
= (short *)bufp
->page
;
while (bp
[0] && ((bp
[bp
[0]] == OVFLPAGE
) ||
((bp
[0] > 2) && bp
[2] < REAL_KEY
))) {
(void)fprintf(stderr
, "%d ", (int)oaddr
);
bufp
= __get_buf(hashp
, (int)oaddr
, bufp
, 0);
bp
= (short *)bufp
->page
;
(void)fprintf(stderr
, "\n");