* 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
[] = "@(#)dynahash.c 5.14 (Berkeley) 4/2/91";
#endif /* LIBC_SCCS and not lint */
/* Fast arithmetic, relying on powers of 2, */
#define MOD(x,y) ((x) & ((y)-1))
#define RETURN_ERROR(ERR,LOC) { save_errno = ERR; goto LOC; }
extern int __split_page();
extern u_long
*__init_bitmap();
extern int __big_return();
extern int __big_keydata();
extern u_short
__find_last_page();
extern BUFHEAD
*__get_buf();
extern void __buf_init();
extern int (*default_hash
)();
extern int __expand_table();
extern u_int
__call_hash();
static HTAB
*init_hash();
static int hash_access();
static char *hash_realloc();
static int hash_delete();
static void swap_header_copy();
static void swap_header();
long hash_accesses
, hash_collisions
, hash_expansions
, hash_overflows
;
/************************** INTERFACE ROUTINES **********************/
hash_open ( file
, flags
, mode
, info
)
const HASHINFO
*info
; /* Special directives for create */
if ( !(hashp
= (HTAB
*) calloc( 1, sizeof(HTAB
) ))) {
/* calloc should set errno */
Select flags relevant to us.
Even if user wants write only, we need to be able to read
the actual file, so we need to open it read/write. But, the
field in the hashp structure needs to be accurate so that
flags
= flags
& (O_CREAT
| O_EXCL
| O_RDONLY
| O_RDWR
| O_TRUNC
| O_WRONLY
);
if ( flags
& O_WRONLY
) flags
= (flags
& ~O_WRONLY
) | O_RDWR
;
(stat ( file
, &statbuf
) && (errno
== ENOENT
)) ) {
errno
= 0; /* Just in case someone looks at errno */
if ((hashp
->fp
= open ( file
, flags
, mode
)) == -1) {
RETURN_ERROR (errno
, error0
);
(void)fcntl(hashp
->fp
, F_SETFD
, 1);
if ( !(hashp
= init_hash( info
)) ) {
RETURN_ERROR(errno
,error1
);
/* Table already exists */
if ( info
&& info
->hash
) hashp
->hash
= info
->hash
;
else hashp
->hash
= default_hash
;
hdrsize
= read ( hashp
->fp
, &hashp
->hdr
, sizeof(HASHHDR
) );
#if BYTE_ORDER == LITTLE_ENDIAN
RETURN_ERROR(errno
, error1
);
if ( hdrsize
!= sizeof(HASHHDR
) ) {
RETURN_ERROR(EFTYPE
, error1
);
/* Verify file type, versions and hash function */
if ( hashp
->MAGIC
!= HASHMAGIC
)
RETURN_ERROR ( EFTYPE
, error1
);
if ( hashp
->VERSION
!= VERSION_NO
)
RETURN_ERROR ( EFTYPE
, error1
);
if (hashp
->hash ( CHARKEY
, sizeof(CHARKEY
) ) != hashp
->H_CHARKEY
) {
RETURN_ERROR ( EFTYPE
, error1
);
Figure out how many segments we need.
nsegs
= (hashp
->MAX_BUCKET
+ hashp
->SGSIZE
-1)/ hashp
->SGSIZE
;
if (alloc_segs( nsegs
)) {
If alloc_segs fails, table will have been destroyed
and errno will have been set.
bpages
= (hashp
->SPARES
[__log2(hashp
->MAX_BUCKET
)] +
(hashp
->BSIZE
<< BYTE_SHIFT
) - 1) >>
(hashp
->BSHIFT
+ BYTE_SHIFT
);
memset ( &hashp
->mapp
[0], 0, bpages
* sizeof ( u_long
*) );
/* Initialize Buffer Manager */
if ( info
&& info
->cachesize
) {
__buf_init (info
->cachesize
);
__buf_init (DEF_BUFSIZE
);
hashp
->new_file
= new_table
;
hashp
->save_file
= file
&& (hashp
->flags
& (O_WRONLY
|O_RDWR
));
if ( !(dbp
= (DB
*)malloc ( sizeof (DB
) )) ) {
dbp
->internal
= (char *)hashp
;
(void)fprintf(stderr
, "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
"BUCKET SIZE ", hashp
->BSIZE
,
"BUCKET SHIFT ", hashp
->BSHIFT
,
"DIRECTORY SIZE ", hashp
->DSIZE
,
"SEGMENT SIZE ", hashp
->SGSIZE
,
"SEGMENT SHIFT ", hashp
->SSHIFT
,
"FILL FACTOR ", hashp
->FFACTOR
,
"MAX BUCKET ", hashp
->MAX_BUCKET
,
"HIGH MASK ", hashp
->HIGH_MASK
,
"LOW MASK ", hashp
->LOW_MASK
,
"NKEYS ", hashp
->NKEYS
);
hash_overflows
= hash_accesses
= hash_collisions
= hash_expansions
= 0;
(void) close ( hashp
->fp
);
hashp
= (HTAB
*)dbp
->internal
;
/************************** LOCAL CREATION ROUTINES **********************/
hashp
->LORDER
= BYTE_ORDER
;
hashp
->BSIZE
= DEF_BUCKET_SIZE
;
hashp
->BSHIFT
= DEF_BUCKET_SHIFT
;
hashp
->SGSIZE
= DEF_SEGSIZE
;
hashp
->SSHIFT
= DEF_SEGSIZE_SHIFT
;
hashp
->DSIZE
= DEF_DIRSIZE
;
hashp
->FFACTOR
= DEF_FFACTOR
;
hashp
->hash
= default_hash
;
bzero (hashp
->SPARES
, sizeof (hashp
->SPARES
));
/* Round pagesize up to power of 2 */
hashp
->BSHIFT
= __log2(info
->bsize
);
hashp
->BSIZE
= 1 << hashp
->BSHIFT
;
if ( hashp
->BSIZE
> MAX_BSIZE
) {
if ( info
->ffactor
) hashp
->FFACTOR
= info
->ffactor
;
if ( info
->hash
) hashp
->hash
= info
->hash
;
if ( info
->nelem
) nelem
= info
->nelem
;
if ( info
->lorder
!= BIG_ENDIAN
&&
info
->lorder
!= LITTLE_ENDIAN
) {
hashp
->LORDER
= info
->lorder
;
/* init_htab should destroy the table and set errno if it fails */
if ( init_htab ( nelem
) ) {
This calls alloc_segs which may run out of memory.
Alloc_segs will destroy the table and set errno,
so we just pass the error information along.
* Divide number of elements by the fill factor and determine a desired
* number of buckets. Allocate space for the next greater power of
nelem
= (nelem
- 1) / hashp
->FFACTOR
+ 1;
nbuckets
= MAX ( nbuckets
, 2 );
hashp
->SPARES
[l2
] = l2
+ 1;
hashp
->SPARES
[l2
+1] = l2
+ 1;
__init_bitmap ( OADDR_OF(l2
,1), l2
+1, 0 );
hashp
->MAX_BUCKET
= hashp
->LOW_MASK
= nbuckets
- 1;
hashp
->HIGH_MASK
= (nbuckets
<< 1) - 1;
hashp
->HDRPAGES
= ((MAX(sizeof(HASHHDR
),MINHDRSIZE
) - 1) >>
nsegs
= (nbuckets
- 1) / hashp
->SGSIZE
+ 1;
nsegs
= 1 << __log2(nsegs
);
if ( nsegs
> hashp
->DSIZE
) {
return (alloc_segs ( nsegs
) );
/********************** DESTROY/CLOSE ROUTINES ************************/
Flushes any changes to the file if necessary and
destroys the hashp structure, freeing all allocated
(void) fprintf(stderr
, "hdestroy: accesses %ld collisions %ld\n",
hash_accesses
, hash_collisions
);
(void) fprintf(stderr
, "hdestroy: expansions %ld\n",
(void) fprintf(stderr
, "hdestroy: overflows %ld\n",
(void) fprintf(stderr
, "keys %ld maxp %d segmentcount %d\n",
hashp
->NKEYS
, hashp
->MAX_BUCKET
, hashp
->nsegs
);
for ( i
= 0; i
< NCACHED
; i
++ ) {
(void) fprintf ( stderr
, "spares[%d] = %d\n", i
, hashp
->SPARES
[i
] );
Call on buffer manager to free buffers, and if
required, write them to disk
if (__buf_free(1, hashp
->save_file
)) {
(void)free(*hashp
->dir
); /* Free initial segments */
/* Free extra segments */
while ( hashp
->exsegs
-- ) {
(void)free ( hashp
->dir
[--hashp
->nsegs
] );
if (flush_meta() && !save_errno
) {
for ( i
= 0; i
< hashp
->nmaps
; i
++ ) {
(void) free ( hashp
->mapp
[i
] );
Write modified pages to disk
hashp
= (HTAB
*)dbp
->internal
;
if (!hashp
->save_file
) return(0);
if ( __buf_free ( 0, 1 ) || flush_meta()) {
-1 indicates that errno should be set
if (!hashp
->save_file
) return(0);
hashp
->MAGIC
= HASHMAGIC
;
hashp
->VERSION
= VERSION_NO
;
hashp
->H_CHARKEY
= hashp
->hash ( CHARKEY
, sizeof(CHARKEY
));
#if BYTE_ORDER == LITTLE_ENDIAN
swap_header_copy( &hashp
->hdr
, whdrp
);
if ( (lseek (fp
, 0, SEEK_SET
) == -1 ) ||
((wsize
= write ( fp
, whdrp
, sizeof(HASHHDR
))) == -1)) {
} else if ( wsize
!= sizeof(HASHHDR
) ) {
for ( i
= 0; i
< NCACHED
; i
++ ) {
if (!__put_page((char *)hashp
->mapp
[i
],
hashp
->BITMAPS
[i
], 0, 1)){
/*******************************SEARCH ROUTINES *****************************/
All the access routines return
1 to indicate an external ERROR (i.e. key not found, etc)
-1 to indicate an internal ERROR (i.e. out of memory, etc)
hash_get ( dbp
, key
, data
, flag
)
hashp
= (HTAB
*)dbp
->internal
;
if ( hashp
->flags
& O_WRONLY
) {
return ( hash_access ( HASH_GET
, key
, data
) );
hash_put ( dbp
, key
, data
, flag
)
hashp
= (HTAB
*)dbp
->internal
;
if ( (hashp
->flags
& O_ACCMODE
) == O_RDONLY
) {
if ( flag
== R_NOOVERWRITE
) {
return ( hash_access ( HASH_PUTNEW
, key
, data
) );
return ( hash_access ( HASH_PUT
, key
, data
) );
hash_delete ( dbp
, key
, flag
)
u_int flag
; /* Ignored */
hashp
= (HTAB
*)dbp
->internal
;
if ( (hashp
->flags
& O_ACCMODE
) == O_RDONLY
) {
return ( hash_access ( HASH_DELETE
, key
, NULL
) );
Assume that hashp has been set in wrapper routine
hash_access(action
, key
, val
)
register int off
= hashp
->BSIZE
;
rbufp
= __get_buf ( __call_hash(kp
, size
), NULL
, 0 );
if ( !rbufp
) return(ERROR
);
/* Pin the bucket chain */
for ( bp
= (u_short
*)rbufp
->page
, n
= *bp
++, ndx
= 1; ndx
< n
; ) {
if ( bp
[1] >= REAL_KEY
) {
bcmp(kp
, rbufp
->page
+ *bp
, size
) == 0) {
} else if ( bp
[1] == OVFLPAGE
) {
rbufp
= __get_buf ( *bp
, rbufp
, 0 );
save_bufp
->flags
&= ~BUF_PIN
;
bp
= (u_short
*)rbufp
->page
;
} else if ( bp
[1] < REAL_KEY
) {
if ( (ndx
= __find_bigpair(rbufp
, ndx
, kp
, size
)) > 0 ) {
} else if ( ndx
== -2 ) {
if ( !(pageno
= __find_last_page ( &bufp
)) ) {
rbufp
= __get_buf ( pageno
, bufp
, 0 );
save_bufp
->flags
&= ~BUF_PIN
;
bp
= (u_short
*)rbufp
->page
;
save_bufp
->flags
&= ~BUF_PIN
;
if (__addel(rbufp
, key
, val
)) {
save_bufp
->flags
&= ~BUF_PIN
;
save_bufp
->flags
&= ~BUF_PIN
;
save_bufp
->flags
&= ~BUF_PIN
;
save_bufp
->flags
&= ~BUF_PIN
;
bp
= (u_short
*)rbufp
->page
;
if (bp
[ndx
+1] < REAL_KEY
) __big_return(rbufp
, ndx
, val
, 0);
val
->data
= (u_char
*)rbufp
->page
+ (int) bp
[ndx
+ 1];
val
->size
= bp
[ndx
] - bp
[ndx
+ 1];
if ((__delpair (rbufp
, ndx
)) || (__addel (rbufp
, key
, val
)) ) {
save_bufp
->flags
&= ~BUF_PIN
;
if (__delpair (rbufp
, ndx
))return(ERROR
);
save_bufp
->flags
&= ~BUF_PIN
;
hash_seq(dbp
, key
, data
, flag
)
hashp
= (HTAB
*)dbp
->internal
;
if ( hashp
->flags
& O_WRONLY
) {
if ( (hashp
->cbucket
< 0) || (flag
== R_FIRST
) ) {
if ( !(bufp
= hashp
->cpage
) ) {
for (bucket
= hashp
->cbucket
;
bucket
<= hashp
->MAX_BUCKET
;
bucket
++, hashp
->cndx
= 1 ) {
bufp
= __get_buf ( bucket
, NULL
, 0 );
if (!bufp
) return(ERROR
);
bp
= (u_short
*)bufp
->page
;
if ( hashp
->cbucket
> hashp
->MAX_BUCKET
) {
bp
= (u_short
*)hashp
->cpage
->page
;
while ( bp
[hashp
->cndx
+1] == OVFLPAGE
) {
bufp
= hashp
->cpage
= __get_buf ( bp
[hashp
->cndx
], bufp
, 0 );
if (!bufp
) return(ERROR
);
bp
= (u_short
*)(bufp
->page
);
if (bp
[ndx
+1] < REAL_KEY
) {
if (__big_keydata(bufp
, ndx
, key
, data
, 1)) {
key
->data
= (u_char
*)hashp
->cpage
->page
+ bp
[ndx
];
key
->size
= (ndx
> 1 ? bp
[ndx
-1] : hashp
->BSIZE
) - bp
[ndx
];
data
->data
= (u_char
*)hashp
->cpage
->page
+ bp
[ndx
+ 1];
data
->size
= bp
[ndx
] - bp
[ndx
+ 1];
} else hashp
->cndx
= ndx
;
/********************************* UTILITIES ************************/
u_int old_bucket
, new_bucket
;
register char **old
, **new;
new_bucket
= ++hashp
->MAX_BUCKET
;
old_bucket
= (hashp
->MAX_BUCKET
& hashp
->LOW_MASK
);
new_segnum
= new_bucket
>> hashp
->SSHIFT
;
/* Check if we need a new segment */
if ( new_segnum
>= hashp
->nsegs
) {
/* Check if we need to expand directory */
if ( new_segnum
>= hashp
->DSIZE
) {
/* Reallocate directory */
dirsize
= hashp
->DSIZE
* sizeof ( SEGMENT
* );
if (!hash_realloc ( &hashp
->dir
, dirsize
, (dirsize
<< 1 ) )) {
hashp
->DSIZE
= dirsize
<< 1;
if (!(hashp
->dir
[new_segnum
] =
(SEGMENT
)calloc ( hashp
->SGSIZE
, sizeof(SEGMENT
)))) {
If the split point is increasing (MAX_BUCKET's log
base 2 increases), we need to copy the current contents
of the spare split bucket to the next bucket
spare_ndx
= __log2(hashp
->MAX_BUCKET
);
if ( spare_ndx
!= (__log2(hashp
->MAX_BUCKET
- 1))) {
hashp
->SPARES
[spare_ndx
] = hashp
->SPARES
[spare_ndx
-1];
if ( new_bucket
> hashp
->HIGH_MASK
) {
/* Starting a new doubling */
hashp
->LOW_MASK
= hashp
->HIGH_MASK
;
hashp
->HIGH_MASK
= new_bucket
| hashp
->LOW_MASK
;
* Relocate records to the new bucket
return(__split_page ( old_bucket
, new_bucket
));
If realloc guarantees that the pointer is not destroyed
if the realloc fails, then this routine can go away
hash_realloc ( p_ptr
, oldsize
, newsize
)
if (p
= (char *)malloc ( newsize
) ) {
bcopy ( *p_ptr
, p
, oldsize
);
bzero ( *p_ptr
+ oldsize
, newsize
-oldsize
);
bucket
= n
& hashp
->HIGH_MASK
;
if ( bucket
> hashp
->MAX_BUCKET
) {
bucket
= bucket
& hashp
->LOW_MASK
;
Allocate segment table. On error, destroy the table
if (!(hashp
->dir
= (SEGMENT
*)calloc(hashp
->DSIZE
, sizeof(SEGMENT
*)))) {
store
= (SEGMENT
)calloc ( nsegs
<< hashp
->SSHIFT
, sizeof (SEGMENT
) );
for ( i
=0; i
< nsegs
; i
++, hashp
->nsegs
++ ) {
hashp
->dir
[i
] = &store
[i
<<hashp
->SSHIFT
];
Hashp->hdr needs to be byteswapped.
swap_header_copy ( srcp
, destp
)
BLSWAP_COPY(srcp
->magic
, destp
->magic
);
BLSWAP_COPY(srcp
->version
, destp
->version
);
BLSWAP_COPY(srcp
->lorder
, destp
->lorder
);
BLSWAP_COPY(srcp
->bsize
, destp
->bsize
);
BLSWAP_COPY(srcp
->bshift
, destp
->bshift
);
BLSWAP_COPY(srcp
->dsize
, destp
->dsize
);
BLSWAP_COPY(srcp
->ssize
, destp
->ssize
);
BLSWAP_COPY(srcp
->sshift
, destp
->sshift
);
BLSWAP_COPY(srcp
->max_bucket
, destp
->max_bucket
);
BLSWAP_COPY(srcp
->high_mask
, destp
->high_mask
);
BLSWAP_COPY(srcp
->low_mask
, destp
->low_mask
);
BLSWAP_COPY(srcp
->ffactor
, destp
->ffactor
);
BLSWAP_COPY(srcp
->nkeys
, destp
->nkeys
);
BLSWAP_COPY(srcp
->hdrpages
, destp
->hdrpages
);
BLSWAP_COPY(srcp
->h_charkey
, destp
->h_charkey
);
for ( i
=0; i
< NCACHED
; i
++ ) {
BLSWAP_COPY ( srcp
->spares
[i
] , destp
->spares
[i
]);
BSSWAP_COPY ( srcp
->bitmaps
[i
] , destp
->bitmaps
[i
]);
BLSWAP(hdrp
->max_bucket
);
for ( i
=0; i
< NCACHED
; i
++ ) {
BLSWAP ( hdrp
->spares
[i
] );
BSSWAP ( hdrp
->bitmaps
[i
] );