hash.c

操作系统SunOS 4.1.3版本的源码

{
	register Hash	hash;		/* New hash table */
	register int	slots;		/* Number of slots */

	if (check != 7){
		fprintf(stderr, "HASH_CREATE: Wrong number of arguments\n");
		exit(1);
	}

	/* Number of slots must be a power of two. */
	slots = 1;
	while (slots < size)
		slots <<= 1;

	hash = (Hash)memory_allocate(sizeof *hash);
	hash->count = 0;	
	hash->key_empty = key_empty;
	hash->key_equal = (key_equal != NULL) ? key_equal : nse_hash_int_equal;
	hash->key_hash = (key_hash != NULL) ? key_hash : nse_hash_int_hash;
	hash->key_insert =
		(key_insert != NULL) ? key_insert : nse_hash_int_insert;
	hash->value_empty = value_empty;
	hash->value_insert =
		(value_insert != NULL) ? value_insert : nse_hash_int_insert;
	nse_hash_initialize(hash, slots);
	return hash;
}

/*
 * nse_hash_destroy(hash, key_destroy, value_destroy) will deallocate the 
 * storage
 * associated with Hash.  Each key-value pair in Hash will be destroyed by
 * calling Key_Destroy(Key) and Value_Destroy(Value).  If Key_Destroy is NULL,
 * it will not be called.  Likewise, if Value_Destroy is NULL, it will not
 * be called.
 */
void
nse_hash_destroy(hash, key_destroy, value_destroy)
	register Hash		hash;		/* Hash table to destroy */
	register Void_routine	key_destroy;	/* Key destroy routine */
	register Void_routine	value_destroy;	/* Value destroy routine */
{
	register Bucket	bucket;			/* Current bucket */
	register Bucket	*bucket_pointer;	/* Pointer into bucket array */
	register int	slots;			/* Number of slots */

	bucket_pointer = hash->buckets;
	for (slots = hash->slots; slots > 0; slots--){
		bucket = *bucket_pointer++;
		while ((unsigned)bucket > SPECIAL){
			if (key_destroy != NULL)
				key_destroy(bucket->key);
			if (value_destroy != NULL)
				value_destroy(bucket->value);
			bucket_deallocate(bucket);
			bucket = bucket->next;
		}
	}
	data_deallocate((int *)hash->buckets, hash->slots);
	memory_deallocate((char *)hash, sizeof *hash);
}

/*
 * nse_hash_full_insert(hash, key, value, key_pointer, value_pointer)
 * =>{True, False} will insert Key-Value into Hash.  If Key is already in
 * Hash, the key and value already in Hash will not be affected and True will
 * be returned.  If Key is not already in Hash, Key and Value are inserted
 * into Hash and False is returned.  If Key_Pointer is non-NULL, *Key_Pointer
 * will be assigned the key stored in Hash.  If Value_pointer is non-NULL,
 * *Value_Pointer will be assigend the value stored in Hash.
 */
/* VARARGS1 */
bool_t
nse_hash_full_insert(hash, key, value, key_pointer, value_pointer)
	register Hash	hash;		/* Hash table */
	int		key;		/* Key to lookup */
	int		value;		/* Value to store */
	int		*key_pointer;	/* Place to store key */
	int		*value_pointer;	/* Place to store value */
{
	return nse_hash_access(hash, key, value, True, False, 
	    (Void_routine)NULL, key_pointer, value_pointer);
}

/*
 * nse_hash_full_lookup(hash, key, key_pointer, value_pointer)=>{True, False} 
 * will find the key-value pair associated with Key in Hash.  If Key is in 
 * Hash, the
 * key stored with Hash will be returned in *Key_Pointer, the value stored with
 * Hash will be returned in *Value_Pointer, and True will be returned.  If Key
 * is not in Hash, the empty key will be stored into *Key_Pointer, the empty
 * value will be stored into *Value_Pointer.  If Key_Pointer is NULL, no key
 * will be stored into it.  If Value_Pointer is NULL, no value will be stored
 * into it.
 */
/* VARARGS1 */
bool_t
nse_hash_full_lookup(hash, key, key_pointer, value_pointer)
	register Hash	hash;		/* Hash table */
	int		key;		/* Key to lookup */
	int		*key_pointer;	/* Place to store key */
	int		*value_pointer;	/* Place to store value */
{
	return nse_hash_access(hash, key, 0, False, False, (Void_routine)NULL,
	    key_pointer, value_pointer);
}

/*
 * nse_hash_full_replace(hash, key, value, key_pointer, value_pointer)
 * =>{True, False} will insert Key-Value into Hash.  If Key is already in
 * Hash, the key and value will just be replaced and True will be returned.
 *  If Key is not already in Hash, Key and Value are inserted into Hash and
 * False is returned.  If Key_Pointer is non-NULL, *Key_Pointer will be
 * assigned the key stored in Hash.  If Value_pointer is non-NULL,
 * *Value_Pointer will be assigend the value stored in Hash.
 */
/* VARARGS1 */
bool_t
nse_hash_full_replace(hash, key, value, key_pointer, value_pointer)
	register Hash	hash;		/* Hash table */
	int		key;		/* Key to lookup */
	int		value;		/* Value to store */
	int		*key_pointer;	/* Place to store key */
	int		*value_pointer;	/* Place to store value */
{
	return nse_hash_access(hash, key, value, True, True, (Void_routine)NULL,
	    key_pointer, value_pointer);
}

/*
 * nse_hash_get(Hash, Key)=>Value will lookup the value for Key in Hash.  If Key
 * is not in Hash, a fatal error occurs.
 */
/* VARARGS1 */
int
nse_hash_get(hash, key)
	register Hash	hash;	/* Hash table */
	int		key;	/* Key to lookup */
{
	int		value;	/* Return value */

	if (nse_hash_access(hash,
	    key, 0, False, False, (Void_routine)NULL, (int *)NULL, &value))
		return value;
	else {
		fprintf(stderr,
			"HASH_GET:Could not find key (0x%x) in table (0x%x)\n",
			key, hash);
		exit(1);
		/* NOTREACHED */
	}
}

#ifdef UNUSED
/*
 * nse_hash_histogram(hash, histogram, size) will scan through Hash generating
 * a histogram of the bucket length and storing the result into the Size
 * words starting at Histogram.  The maximum desired histogram value will
 * be returned.
 */
int
nse_hash_histogram(hash, histogram, size)
	Hash		hash;		/* Hash table */
	register int	*histogram;	/* Place to store histogram */
	register int	size;		/* Maximum size of histogram */
{
	register Bucket	bucket;		/* Current bucket */
	register Bucket *buckets;	/* Bucket array */
	register int	count;		/* Number of buckets */
	register int	maximum;	/* Maximum histogram value */
	register int	slots;		/* Slots in bucket array */

	bzero((char *)histogram, size * sizeof(int));
	buckets = hash->buckets;
	maximum = 0;
	for (slots = hash->slots; slots > 0; slots--){
		count = 0;
		for (bucket = *buckets++;
		    (unsigned)bucket > SPECIAL; bucket = bucket->next)
			count++;
		if (count < size)
			histogram[count]++;
		if (count > maximum)
			maximum = count;
	}
	return maximum;
}

/*
 * nse_hash_histogram_display(hash, out_file) will print a histogram of Hash to
 * Out_File.
 */
void
nse_hash_histogram_display(hash, out_file)
	Hash		hash;		/* Hash table */
	register FILE	*out_file;	/* Output file */
{
	register int	*histogram;	/* Histogram */
	register int	index;		/* Index into histogram */
	register int	size;		/* Histogram size */

	size = nse_hash_histogram(hash, (int *)NULL, 0) + 1;
	histogram = (int *)memory_allocate(size * sizeof(int));
	nse_hash_histogram(hash, histogram, size);
	fprintf(out_file, "Length\tCount\n");
	for (index = 0; index < size; index++)
		fprintf(out_file, "[%d]:\t%d\n", index, histogram[index]);
	memory_deallocate((char *)histogram, size * sizeof(int));
}
#endif

/*
 * nse_hash_insert(hash, key, value)=>{True,False} will attempt to find Key in
 * Hash.  If Key is already in Hash, True will be returned without affecting
 * Key's associated value.  Otherwise, Key and Value will be inserted into
 * Hash and False will be returned.
 */
/* VARARGS1 */
bool_t
nse_hash_insert(hash, key, value)
	register Hash	hash;	/* Hash table */
	int		key;	/* Key to insert under */
	int		value;	/* Value to insert */
{
	return nse_hash_access(hash, key, value, True, False, 
	    (Void_routine)NULL, (int *)NULL, (int *)NULL);
}

/*
 * nse_hash_initialize(Hash, Size) will initialize Hash to contain Size table
 * entries.
 */
static void
nse_hash_initialize(hash, size)
	register Hash	hash;		/* Hash table */
	register int	size;		/* Number of slots */
{
	hash->buckets = (Bucket *)data_allocate(size, (int)EMPTY);
	hash->slots = size;
	hash->limit = (size << 3) / 10;
	hash->mask = size - 1;
}

/*
 * nse_hash_int_equal(Int1, Int2) will return True if Int1 equals Int2.
 */
static bool_t
nse_hash_int_equal(int1, int2)
	int	int1;		/* First integer */
	int	int2;		/* Second integer */
{
	return (bool_t)(int1 == int2);
}

/*
 * nse_hash_int_hash(number) will return a hash on number.
 */
static int
nse_hash_int_hash(number)
	int	number;		/* Number to hash */
{
	return number;
}

/*
 * nse_hash_int_insert(number) will return a copy of number.
 */

static int
nse_hash_int_insert(number)
	int	number;		/* Number to insert */
{
	return number;
}

/*
 * nse_hash_lookup(Hash, Key)=>value will lookup Key in Hash.  If Key is not
 * in Hash, Empty_Value will be returned.
 */
/* VARARGS1 */
int
nse_hash_lookup(hash, key)
	register Hash	hash;	/* Hash table */
	int		key;	/* Key to lookup */
{
	int		value;	/* Value with Key */

	nse_hash_access(hash, key, 0, False, False, (Void_routine)NULL,
	    (int *)NULL, &value);
	return value;
}

#ifdef UNUSED
/*
 * nse_hash_read(hash, in_file, key_read, key_handle, value_read, value_handle)
 * will read a hash table from In_File into Hash.  Hash must be an empty
 * that was created in the same what that it was originally written out.
 * Key_Read(In_File, Key_Handle)=>Key to read a key from In_File and
 * Value_Read(In_File, Value_Handle, Key)=>Value to read a value from In_File.
 * The Key that was just read in is passed as the third argument to Value_Read.
 * If Key_Read or Value_Read are NULL, integer read routines will be used.
 */
void
nse_hash_read(hash, in_file, key_read, key_handle, value_read, value_handle)
	register Hash	hash;		/* Hash table to use */
	register FILE	*in_file;	/* File to input from */
	Int_routine	key_read;	/* Key read routine */
	int		key_handle;	/* Key handle */
	Int_routine	value_read;	/* Value read routine */
	int		value_handle;	/* Value handle */
{
	register Bucket	bucket;		/* Current bucket */
	register Bucket	*buckets;	/* Buckets array pointer */
	register int	count;		/* Loop counter */
	register int	key;		/* Key */
	register int	length;		/* Bucket length */

	if (hash->count != 0){
		fprintf(stderr, "hash_read: reading into non-empty table\n");
		exit(1);
	}
	data_deallocate((int *)hash->buckets, hash->slots);

	read_magic(in_file, HASH_MAGIC);
	hash->count = read_word(in_file);
	hash->limit = read_word(in_file);
	hash->mask = read_word(in_file);
	hash->slots = read_word(in_file);
	hash->buckets = (Bucket *)data_allocate(hash->slots, (int)EMPTY);

	if (key_read == NULL)
		key_read = read_word;
	if (value_read == NULL)
		value_read = read_word;
	buckets = hash->buckets;
	count = hash->slots;
	while (count-- > 0){
		length = read_word(in_file);
		bucket = NULL;
		while (length-- > 0){
			if (bucket == NULL){
				bucket = bucket_allocate();
				*buckets = bucket;
			} else {
				bucket->next = bucket_allocate();
				bucket = bucket->next;
			}
			bucket->index = read_word(in_file);
			key = key_read(in_file, key_handle);
			bucket->key = key;
			bucket->value = value_read(in_file, value_handle, key);
		}
		buckets++;
	}
	read_magic(in_file, HASH_MAGIC);
}
#endif


#ifdef UNUSED
/*
 * nse_hash_rehash(hash, index) will rehash all of the hash table entires that
 * might conflict with Index in Hash.
 */
static Bucket
nse_hash_rehash(hash, index)
	register Hash	hash;		/* Hash table to use */
	register int	index;		/* Hash index to work on */
{
	register Bucket	bucket;		/* Current bucket */
	register int	count;		/* Number of buckets to check */
	register Bucket	*pointer;	/* Current bucket pointer */
	Bucket		rehash[32];	/* Number of buckets to rehash */

	pointer = rehash;
	count = nse_hash_rehash1(hash, index, pointer);
	while (count-- > 0){
		bucket = *pointer++;