hash.c

操作系统SunOS 4.1.3版本的源码

#ifndef lint
static char sccsid[] = "@(#)hash.c 1.1 92/07/30 Copyr 1988 Sun Micro";
#endif

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc.
 */

/*
 * This file contains a bunch of routines that implement a general purpose
 * hash table.
 */

#include <stdio.h>		/* Standard I/O definitions */
#include <nse/hash.h>		/* Include hash table exported routines */

#define	EMPTY	((Bucket)NULL)	/* Empty slot */
#define	HASH_MAGIC 0xadff1582	/* Magic number for hash read and write */
#define	REHASH	((Bucket)1)	/* Slot that needs to be rehashed */
#define	SPECIAL	2		/* All special slot values less than this */

#define True TRUE
#define False FALSE
typedef bool_t (*Bool_routine)();
typedef int (*Int_routine)();
typedef void (*Void_routine)();


/*
 * Imported routines:
 */
extern char	*malloc();
extern char	*valloc();

/*
 * Internally used routines:
 */
static Bucket	bucket_allocate();
static void	bucket_deallocate();
static int	*data_allocate();
static void	data_deallocate();
static void	free_memory();
extern bool_t	nse_hash_access();
static void	nse_hash_bucket_deallocate();
static Bucket	nse_hash_bucket_first();
extern int	nse_hash_check();
extern Hash	nse_hash_create();
extern void	nse_hash_destroy();
extern bool_t	nse_hash_full_insert();
extern bool_t	nse_hash_full_lookup();
extern bool_t	nse_hash_full_replace();
extern int	nse_hash_get();
extern int	nse_hash_histogram();
extern void	nse_hash_histogram_display();
static void	nse_hash_initialize();
extern bool_t	nse_hash_insert();
static bool_t	nse_hash_int_equal();
static int	nse_hash_int_hash();
static int	nse_hash_int_insert();
extern void	nse_hash_read();
extern int	nse_hash_lookup();
static void	nse_hash_rehash2();
extern bool_t	nse_hash_replace();
static void	nse_hash_resize();
extern int	nse_hash_scan();
extern void	nse_hash_show();
extern int	nse_hash_size();
extern void	nse_hash_write();
static char	*memory_allocate();
static void	memory_deallocate();
static void	read_magic();
static int	read_word();
static void	write_magic();
static void	write_word();

/* Bucket allocator: */
static	Bucket	free_buckets;		/* Free bucket list */

/*
 * bucket_allocate() will allocate and return a new bucket symbol
 */
static Bucket
bucket_allocate()
{
	Bucket		bucket;		/* Temporary bucket */
	static Bucket	buckets;	/* Current set of bucket objects */
	static int	buckets_per_page; /* Number of buckets per page */
	static int	page_size = 0;	/* System page size */
	static int	remaining;	/* Number of remaining buckets */
	static int	valloc_size;	/* Amount of memory to valloc */

	if (page_size == 0){
		page_size = getpagesize();
		buckets_per_page = page_size / sizeof(*buckets);
		valloc_size = buckets_per_page * sizeof(*buckets);
		remaining = 0;
	}
	if (free_buckets != NULL){
		bucket = free_buckets;
		free_buckets = *(Bucket *)bucket;
		return bucket;
	}
	if (remaining == 0){
		buckets = (Bucket)valloc((unsigned)valloc_size);
		bzero((char *)buckets, valloc_size);
		remaining = buckets_per_page;
	}
	remaining--;
	return buckets++;
}

/*
 * bucket_deallocate(bucket) will deallocate a bucket.
 */
static void
bucket_deallocate(bucket)
	Bucket	bucket;		/* Bucket to deallocate */
{
	*(Bucket *)bucket = free_buckets;
	free_buckets = bucket;
}

/*
 * data_allocate(size, value) will get Size words of data and initialize them
 * to Value.
 */
static int *
data_allocate(size, value)
	register int	size;		/* Number of words to allocate */
	register int	value;		/* Value to initialize to */
{
	register int	*data;		/* Data array */
	register int	*pointer;	/* Pointer into data */

	pointer =
	    (int *)memory_allocate(size * sizeof(int));
	data = pointer;
	while (size-- > 0)
		*pointer++ = value;
	return data;
}

/*
 * data_deallocate(data, size) will deallocate Size words of Data.
 */
static void
data_deallocate(data, size)
	int		*data;		/* Data to free */
	int		size;		/* Number of words to free */
{
	memory_deallocate((char *)data, size * sizeof(int));
}

/*
 * nse_hash_access(hash, key, value, create, replace, value_destroy, 
 * key_pointer, * value_pointer) =>{True, False} is used to access the a 
 * key-value pair in
 * Hash.  There are two cases that need to be considered.  The first case is
 * if Key is already in Hash.  In this case, if Create is True a Key and Value
 * will be inserted into Hash; otherwise key and value will not be inserted.
 * No matter what, False will be returned in this first case.  The second case
 * is if Key and Value are already in  Hash.  In this case, if Replace is True,
 * the value in hash will be replaced with Value.  If Value_Destroy is
 * non-NULL, the previous value will be destroyed by calling
 * Value_Destroy(Previous_Value).  No matter what, True will be returned in
 * this second case.  If Key_Pointer is non-NULL, the key in Hash will be
 * stored into *Key_Pointer.  If there is no Key in Hash, Key_Empty (from
 * hash_create) will be stored into *Key_Pointer.  Similarly, if Value_Pointer
 * is non-NULL, the value in Hash will be stored into *Value_Pointer.  If there
 * is no value in Hash, Value_Empty (from hash_create) will be stored into
 * *Value_Pointer.
 */
bool_t
nse_hash_access(hash, key, value, create, replace, value_destroy,
    key_pointer, value_pointer)
	register Hash	hash;		/* Hash table */
	int		key;		/* Key */
	int		value;		/* Value */
	bool_t		create;		/* True => Create new entry */
	bool_t		replace;	/* True => Replace value */
	Void_routine	value_destroy;	/* Value destroy routine */
	int		*key_pointer;	/* Place to store key */
	int		*value_pointer;	/* Place to store value */
{
	register Bucket	bucket;		/* Bucket to use */
	Bucket		*buckets;	/* Pointer into bucket array */
	register int	index;		/* Hash index */
	register Bool_routine key_equal;/* Key equality test routine */
	register int	mask;		/* Hash index mask */
	register bool_t return_value;	/* Return value */

	/* Fetch the starting bucket. */
	index = hash->key_hash(key);
	mask = hash->mask;
	buckets = &hash->buckets[index & mask];
	bucket = *buckets;

	/* Rehash, if necessary. 
	if (bucket == REHASH)
		bucket = nse_hash_rehash(hash, index); */

	/* Scan the hash table looking for Key. */
	key_equal = hash->key_equal;
	while (bucket != NULL){
		if ((bucket->index == index) && key_equal(bucket->key, key))
			break;
		bucket = bucket->next;
	}

	if (bucket == NULL){
		/* Create a new entry in Hash. */
		if (create){
			bucket = bucket_allocate();
			bucket->index = index;
			bucket->key = hash->key_insert(key);
			bucket->value = hash->value_insert(value);
			bucket->next = *buckets;
			*buckets = bucket;
			if (hash->count++ > hash->limit)
				nse_hash_resize(hash);
		}
		return_value = False;
	} else {
		/* Replace the value in Hash. */
		if (replace){
			if (value_destroy != NULL)
				value_destroy(bucket->value);
			bucket->value = hash->value_insert(value);
		}
		return_value = True;
	}

	/* Return everything. */
	if (key_pointer != NULL)
		*key_pointer =
		    (bucket == NULL) ? hash->key_empty : bucket->key;
	if (value_pointer != NULL)
		*value_pointer =
		    (bucket == NULL) ? hash->value_empty : bucket->value;
	return return_value;
}

#ifdef UNUSED
/*
 * nse_hash_bucket_deallocate(hash, bucket) will deallocate the Bucket for Hash.
 */
/* ARGSUSED */
static void
nse_hash_bucket_deallocate(hash, bucket)
	Hash		hash;		/* Hash table */
	Bucket		bucket;		/* Bucket to deallocate */
{
}

/*
 * nse_hash_bucket_first(hash, index) will fetch the first bucket from Hash
 * correspondint to Index.  This routine performs any rehashing that needs
 * to be done.
 */
static Bucket
nse_hash_bucket_first(hash, index)
	register Hash	hash;		/* Hash table */
	register int	index;		/* Index into hash slots */
{
	register Bucket *buckets;	/* Bucket array */

	index &= hash->mask;
	buckets = hash->buckets;
	return buckets[index];
}

/*
 * nse_hash_bucket_insert(hash, key, create) will attempt to find Key in Hash.
 * If Key is in Hash, the associated bucket will be returned.  If Key is
 * not in Hash and Create is True, a new bucket will be allocated and inserted
 * into Hash.  Otherwise, NULL will be returned.
 */
static Bucket *
nse_hash_bucket_find(hash, key, create)
	register Hash	hash;		/* Hash table */
	register int	key;		/* Key to lookup */
	bool_t		create;		/* True => create new bucket */
{
	register Bucket	bucket;		/* Current bucket */
	register int	index;		/* Hash index */
	register Bool_routine key_equal;/* Key equality routine */

	/* Go searching for the bucket */
/*	index = hash->key_hash(key);
	key_equal = hash->key_equal;
	bucket = nse_hash_bucket_first(hash, index);
	while ((unsigned)bucket > SPECIAL){
		if ((index == bucket->index) && key_equal(key, bucket->key))
			return bucket;
		bucket = bucket->next;
	}
	if (create){
		bucket = nse_hash_bucket_allocate(hash);
		bucket->index = index;
		bucket->key = hash->key_empty;
		bucket->value = hash->value_empty;
		index &= hash->mask;
		bucket->next = hash->buckets[index];
		hash->buckets[index] = bucket;
	}
	return bucket;
*/
}

/*
 * nse_hash_bucket_lookup(hash, key) will return the bucket assocated with Key
 * from Hash.  If Key is not in Hash, NULL will be returned.
 */
static Bucket
nse_hash_bucket_lookup(hash, key)
	register Hash	hash;		/* Hash table */
	register int	key;		/* Key to lookup */
{
	register Bucket	bucket;		/* Current bucket */
	register int	index;		/* Hash index */
	register Bool_routine key_equal;/* Key equality routine */

	index = hash->key_hash(key);
	bucket = nse_hash_bucket_first(hash, index);
	key_equal = hash->key_equal;
	while ((unsigned)bucket > SPECIAL){
		if ((index == bucket->index) && key_equal(key, bucket->key))
			return bucket;
		bucket = bucket->next;
	}
	return NULL;
}
#endif

/*
 * nse_hash_check(hash) will check hash for consistency.
 */
int
nse_hash_check(hash)
	Hash		hash;		/* Hash table to check */
{	
	register Bucket	bucket;		/* Current bucket */
	register Bucket *buckets;	/* Bucket array */
	register int	index;		/* Loop index */
	register int	slots;		/* Slots in bucket array */

	buckets = hash->buckets;
	slots = hash->slots;
	for (index = 0; index < slots; index++)
		for (bucket = buckets[index];
		    (unsigned)bucket > SPECIAL; bucket = bucket->next)
			if ((unsigned)bucket >= 0x1000000){
				fprintf(stderr, "bkt:%x index:%d\n",
							bucket, index);
				fflush(stderr);
				abort();
			}
}

/*
 * nse_hash_create(Size, Key_Empty, Key_Equal, Key_Hash, Key_Insert, 
 * Value_Empty, Value_Insert, 7) will create and return a hash table 
 * using the parameters.
 * Due to the large  number of arguments, the last argument must be the number
 * 7 so that a quick check can be made to make sure that they are all there.
 * All of the arguments except the last one can be NULL'ed out.
 */
Hash
nse_hash_create(size, key_empty, key_equal, key_hash, key_insert,
				value_empty, value_insert, check)
	register int	size;		/* Number of initial slots */
	int		key_empty;	/* Empty key value */
	Bool_routine	key_equal;	/* Key equality routine */
	Int_routine	key_hash;	/* Key hash function */
	Int_routine	key_insert;	/* Key insertion routine */
	int		value_empty;	/* Empty value */
	Int_routine	value_insert;	/* Value insertion routine */
	int		check;		/* Argument count check */