* Copyright (c) 1990 The Regents of the University of California.
* 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
[] = "@(#)page.c 5.13 (Berkeley) 6/17/91";
#endif /* LIBC_SCCS and not lint */
/******************************************************************************
Page manipulation for hashing package.
******************************************************************************/
extern BUFHEAD
*__get_buf();
extern void __reclaim_buf();
extern int __big_split();
extern int __big_insert();
extern int __big_delete();
extern int __find_bigpair();
extern u_int
__call_hash();
extern int __expand_table();
extern BUFHEAD
*__add_ovflpage();
extern int __split_page();
static u_short
overflow_page();
static void squeeze_key();
static u_long
*fetch_bitmap();
extern long hash_accesses
, hash_collisions
, hash_expansions
, hash_overflows
;
((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 stuff on.
register u_short
*bp
= (u_short
*) p
;
/* enter the key first */
off
= OFFSET(bp
) - key
->size
;
bcopy( key
->data
, p
+off
, key
->size
);
bcopy(val
->data
, p
+ off
, val
->size
);
bp
[n
+1] = off
- ((n
+3)*sizeof(u_short
));
register u_short
*bp
= (u_short
*) bufp
->page
;
if ( bp
[ndx
+1] < REAL_KEY
) return ( __big_delete ( bufp
, ndx
) );
if ( ndx
!= 1 ) newoff
= bp
[ndx
-1];
else newoff
= hashp
->BSIZE
;
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
;
bcopy ( src
, dst
, 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(obucket
, nbucket
)
register BUFHEAD
*new_bufp
;
register BUFHEAD
*old_bufp
;
u_short copyto
= (u_short
)hashp
->BSIZE
;
u_short off
= (u_short
)hashp
->BSIZE
;
old_bufp
= __get_buf ( obucket
, NULL
, 0 );
new_bufp
= __get_buf ( 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( obucket
, old_bufp
, new_bufp
,
old_bufp
->flags
&= ~BUF_PIN
;
new_bufp
->flags
&= ~BUF_PIN
;
key
.data
= (u_char
*)op
+ ino
[n
];
if ( __call_hash ( key
.data
, key
.size
) == obucket
) {
copyto
= ino
[n
+1] + diff
;
bcopy ( op
+ ino
[n
+1], op
+ copyto
, off
-ino
[n
+1]);
ino
[ndx
] = copyto
+ ino
[n
] - ino
[n
+1];
} else copyto
= ino
[n
+1];
val
.data
= (u_char
*)op
+ ino
[n
+1];
val
.size
= ino
[n
] - ino
[n
+1];
putpair( np
, &key
, &val
);
/* Now clean up the page */
FREESPACE(ino
) = copyto
- sizeof(u_short
) * (ino
[0]+3);
fprintf(stderr
, "split %d/%d\n",
((u_short
*) op
)[0] / 2);
old_bufp
->flags
&= ~BUF_PIN
;
new_bufp
->flags
&= ~BUF_PIN
;
Called when we encounter an overflow or big key/data page during
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 big key/data pair.
ugly_split( obucket
, old_bufp
, new_bufp
, copyto
, moved
)
u_int obucket
; /* Same as __split_page */
u_short copyto
; /* First byte on page which contains key/data values */
int moved
; /* number of pairs moved to new page */
register BUFHEAD
*bufp
= old_bufp
; /* Buffer header for ino */
register u_short
*ino
= (u_short
*)old_bufp
->page
;
/* Page keys come off of */
register u_short
*np
= (u_short
*)new_bufp
->page
; /* New page */
register u_short
*op
= (u_short
*)old_bufp
->page
;
/* Page keys go on to if they
char *cino
; /* Character value of ino */
BUFHEAD
*last_bfp
= NULL
; /* Last buffer header OVFL which
u_short ov_addr
, last_addr
= 0;
if ( ino
[2] < REAL_KEY
&& ino
[2] != OVFLPAGE
) {
if (__big_split (old_bufp
, new_bufp
, bufp
, ov_addr
, obucket
, &ret
)) {
if ( !old_bufp
) return(-1);
op
= (u_short
*)old_bufp
->page
;
if ( !new_bufp
) return(-1);
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
FREESPACE(ino
) = copyto
- sizeof(u_short
) * (ino
[0]+3);
bufp
= __get_buf ( ov_addr
, bufp
, 0 );
ino
= (u_short
*)bufp
->page
;
__free_ovflpage( 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 ( key
.data
, key
.size
) == obucket
) {
if (PAIRFITS(op
,(&key
),(&val
))) putpair((char *)op
, &key
, &val
);
old_bufp
= __add_ovflpage ( old_bufp
);
if ( !old_bufp
) return(-1);
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
);
new_bufp
= __add_ovflpage ( new_bufp
);
if ( !new_bufp
)return(-1);
np
= (u_short
*)new_bufp
->page
;
putpair ((char *)np
, &key
, &val
);
new_bufp
->flags
|= BUF_MOD
;
__free_ovflpage(last_bfp
);
Add the given pair to the page
register u_short
*bp
= (u_short
*)bufp
->page
;
while ( bp
[0] && (bp
[bp
[0]] < REAL_KEY
) ) {
if ( bp
[2] < REAL_KEY
) {
/* This is a big-keydata pair */
bufp
= __add_ovflpage(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 ( bp
[bp
[0]-1], bufp
, 0 );
bp
= (u_short
*)bufp
->page
;
if ( PAIRFITS(bp
,key
,val
) ) putpair (bufp
->page
, key
, val
);
bufp
= __add_ovflpage ( bufp
);
sop
= (u_short
*) bufp
->page
;
if ( PAIRFITS(sop
, key
, val
) ) putpair ( (char *)sop
, key
, val
);
else if ( __big_insert ( 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());
returns a pointer, NULL on error
register u_short
*sp
= (u_short
*)bufp
->page
;
ovfl_num
= overflow_page ();
tmp2
= bufp
->ovfl
?bufp
->ovfl
->addr
:0;
if (!ovfl_num
|| !(bufp
->ovfl
= __get_buf ( ovfl_num
, bufp
, 1 ))) {
bufp
->ovfl
->flags
|= BUF_MOD
;
fprintf ( stderr
, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", tmp1
, tmp2
,
Since a pair is allocated on a page only if there's room
to add an overflow page, we know that the OVFL information
sp
[ndx
+3] = FREESPACE(sp
) - OVFLSIZE
;
__get_page ( p
, bucket
, is_bucket
, is_disk
, is_bitmap
)
if ( (fd
== -1) || !is_disk
) {
if ( is_bucket
) page
= BUCKET_TO_PAGE (bucket
);
else page
= OADDR_TO_PAGE (bucket
);
if ((lseek ( fd
, page
<< hashp
->BSHIFT
, SEEK_SET
) == -1) ||
((rsize
= read ( fd
, p
, size
)) == -1 )) {
bp
[0] = 0; /* We hit the EOF, so initialize a new page */
} else if ( rsize
!= size
) {
} else 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 ( p
, bucket
, is_bucket
, is_bitmap
)
if ( (hashp
->fp
== -1) && open_temp() ) return (1);
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
]);
if (is_bucket
) page
= BUCKET_TO_PAGE (bucket
);
else page
= OADDR_TO_PAGE ( bucket
);
if ((lseek ( fd
, 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(pnum
, nbits
, ndx
)
if ( !(ip
= (u_long
*)malloc (hashp
->BSIZE
)) ) return (NULL
);
clearints
= ((nbits
- 1) >> INT_BYTE_SHIFT
) + 1;
clearbytes
= clearints
<< INT_TO_BYTE
;
memset ((char *)ip
, 0, clearbytes
);
memset ( ((char *) ip
) + clearbytes
, 0xFF,
hashp
->BSIZE
-clearbytes
);
ip
[clearints
-1] = ALL_SET
<< (nbits
& BYTE_MASK
);
hashp
->BITMAPS
[ndx
] = pnum
;
for ( i
=0; i
< BITS_PER_MAP
; i
++ ) {
if ( !(mask
& map
) ) return(i
);
splitnum
= __log2(hashp
->MAX_BUCKET
);
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 */
for ( i
= 0; i
<= free_page
; i
++ ) {
if (!(freep
= (u_long
*)hashp
->mapp
[i
]) &&
!(freep
= fetch_bitmap(i
)) ) {
if ( i
== free_page
) in_use_bits
= free_bit
;
else in_use_bits
= (hashp
->BSIZE
<< BYTE_SHIFT
) -1;
for (j
= 0, bit
= 0; bit
<= in_use_bits
; j
++, bit
+= BITS_PER_MAP
) {
if ( freep
[j
] != ALL_SET
) goto found
;
hashp
->SPARES
[splitnum
]++;
offset
= hashp
->SPARES
[splitnum
] -
(splitnum
? hashp
->SPARES
[splitnum
-1] : 0);
/* Check if we need to allocate a new bitmap page */
if ( free_bit
== (hashp
->BSIZE
<< BYTE_SHIFT
) - 1 ) {
#define OVMSG "hash: out of overflow pages; increase page size\n"
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 in the first place.
__init_bitmap ( OADDR_OF(splitnum
, offset
), 1, free_page
);
hashp
->SPARES
[splitnum
]++;
Free_bit addresses the last used bit. Bump it to
address the first available bit.
SETBIT ( freep
, free_bit
);
/* Calculate address of the new overflow page */
if ( offset
> SPLITMASK
) {
(void) write (STDERR_FILENO
, OVMSG
, sizeof(OVMSG
) - 1);
addr
= OADDR_OF(splitnum
, offset
);
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
));
/* 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
);
if ( offset
>= SPLITMASK
) return(NULL
);/* Out of overflow pages */
addr
= OADDR_OF(i
, offset
);
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 ( obufp
)
register u_short addr
= obufp
->addr
;
fprintf ( stderr
, "Freeing %d\n", addr
);
ndx
= (((u_short
)addr
) >> SPLITSHIFT
);
bit_address
= (ndx
? hashp
->SPARES
[ndx
-1] : 0) + (addr
& SPLITMASK
) - 1;
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( 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
fprintf ( stderr
, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
obufp
->addr
, free_bit
, free_page
);
static char namestr
[] = "_hashXXXXXX";
/* Block signals; make sure file goes away at process exit. */
sigaddset(&set
, SIGQUIT
);
sigaddset(&set
, SIGTERM
);
(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
squeeze_key ( sp
, key
, val
)
register char *p
= (char *)sp
;
free_space
= FREESPACE(sp
);
bcopy ( key
->data
, p
+ off
, key
->size
);
bcopy ( val
->data
, p
+ off
, val
->size
);
FREESPACE(sp
) = free_space
- PAIRSIZE(key
,val
);
if ( ndx
>= hashp
->nmaps
||
!(hashp
->mapp
[ndx
] = (u_long
*)malloc ( hashp
->BSIZE
)) ||
__get_page ((char *)hashp
->mapp
[ndx
], hashp
->BITMAPS
[ndx
], 0, 1, 1)) {
return ( hashp
->mapp
[ndx
] );
fprintf ( stderr
, "%d ", addr
);
bufp
= __get_buf ( (int)addr
, NULL
, 0 );
bp
= (short *)bufp
->page
;
((bp
[bp
[0]] == OVFLPAGE
) ||
((bp
[0] > 2) && bp
[2] < REAL_KEY
))) {
fprintf ( stderr
, "%d ", (int)oaddr
);
bufp
= __get_buf ( (int)oaddr
, bufp
, 0 );
bp
= (short *)bufp
->page
;
fprintf ( stderr
, "\n" );