hash.c

操作系统SunOS 4.1.3版本的源码

		if ((unsigned)bucket > SPECIAL)
			nse_hash_rehash2(hash, bucket);
	}
	return hash->buckets[index & hash->mask];
}

/*
 * nse_hash_rehash1(hash, index, rehash) will scan through the bucket array in
 * Hash and store the buckets than need to be rehashed for Index into Rehash.
 * The number of items to be rehashed is returned.
 */
static int
nse_hash_rehash1(hash, index, rehash)
	Hash		hash;		/* Hash table to use */
	register int	index;		/* Hash index to rehash */
	register Bucket *rehash;	/* Place to store results */
{
	register int	count;		/* Number of buckets to check */
	register Bucket *buckets;	/* Bucket array */
	register Bucket	*pointer;	/* Current bucket pointer */
	register Bucket *last_pointer;	/* Last value of Pointer */
	register int	mask;		/* Current hash mask */

	buckets = hash->buckets;
	count = 0;
	mask = hash->mask;
	last_pointer = NULL;
	while (mask != 0){
		pointer = buckets + (index & mask);
		if (pointer != last_pointer){
			last_pointer = pointer;
			rehash[count++] = *pointer;
			*pointer = NULL;
		}
		mask >>= 1;
	}
	return count;
}
#endif

/*
 * nse_hash_rehash2(hash, bucket) will rehash all of the buckets pointed to by
 * Bucket in Hash.
 */
static void
nse_hash_rehash2(hash, bucket)
	Hash		hash;		/* Hash table to use */
	register Bucket	bucket;		/* Bucket list to rehash */
{
	register Bucket *bucket_pointer;/* Ponter into bucket array */
	register Bucket	*buckets;	/* Bucket array */
	register int	mask;		/* Hash index mask */
	register Bucket	next_bucket;	/* Next bucket to rehash */

	buckets = hash->buckets;
	mask = hash->mask;
	while (bucket != NULL){
		next_bucket = bucket->next;
		bucket_pointer = buckets + (bucket->index & mask);
		bucket->next = *bucket_pointer;
		*bucket_pointer = bucket;
		bucket = next_bucket;
	}	
}

/*
 * nse_hash_replace(hash, key, value)=>{True,False} will attempt to find Key in
 * Hash.  If Key is not in Hash, Key and Value will be inserted into Hash
 * and False will be returned.  Otherwise, Value will replace the Key value
 * already in Hash, and True will be returned.
 */
/* VARARGS1 */
bool_t
nse_hash_replace(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, True, (Void_routine)NULL,
	    (int *)NULL, (int *)NULL);
}

/*
 * nse_hash_resize(Hash) will increase the number of slots in the hash table.
 */
static void
nse_hash_resize(hash)
	register Hash	hash;		/* Hash table to resize. */
{
	register int	count;		/* Loop counter */
	Bucket		*new_buckets;	/* New bucket array */
	register Bucket	*new_pointer;	/* Pointer into new bucket array */
	register int	new_slots;	/* New number of slots */
	Bucket		*old_buckets;	/* Old bucket array */
	register Bucket	*old_pointer;	/* Pointer into old buckedt array */
	register int	old_slots;	/* Old number of slots */

	/* Set up the new bucket array. */
	old_slots = hash->slots;
	old_buckets = hash->buckets;
	new_slots = old_slots << 1;
	new_buckets = (Bucket *)data_allocate(new_slots, (int)EMPTY);
	hash->slots = new_slots;
	hash->buckets = new_buckets;
	hash->limit <<= 1;
	hash->mask = new_slots - 1;

	/* Transfer the buckets from old to new. */
	old_pointer = old_buckets;
	new_pointer = new_buckets;
	for (count = new_slots; count > 0; count--)
		*new_pointer++ = EMPTY;
	for (count = old_slots; count > 0; count--)
		nse_hash_rehash2(hash, *old_pointer++);

	/* Dealloacte the old bucket array. */
	data_deallocate((int *)old_buckets, old_slots);
}

/*
 * nse_hash_scan(hash, routine, data) will scan the entire contents of Hash
 * calling Routine(Key, Value, Data)=>int for each key-value pair in Hash.
 * The sum of the values returned by Routine will be returned.
 */
/* VARARGS1 */
int
nse_hash_scan(hash, routine, data)
	register Hash		hash;		/* Hash table */
	register Int_routine	routine;	/* Routine to scan with */
	register int		data;		/* Data value */
{
	register Bucket		bucket;		/* Current bucket */
	register Bucket 	*buckets;	/* Bucket array */
	register int		slots;		/* Slots in bucket array */
	register int		sum;		/* Sum from routine */

	buckets = hash->buckets;
	sum = 0;
	for (slots = hash->slots; slots > 0; slots--)
		for (bucket = *buckets++;
		    (unsigned)bucket > SPECIAL; bucket = bucket->next)
			sum += routine(bucket->key, bucket->value, data);
	return sum;
}

/*
 * nse_hash_show(hash) will show the contents of Hash on the console.  This
 * routine is used for testing and debugging purposes only.
 */
void
nse_hash_show(hash)
	register Hash	hash;		/* Hash table */
{
	register Bucket	bucket;		/* Current bucket */
	register Bucket *buckets;	/* Bucket array */
	register int	slot;		/* Current slot in bucket array */
	register int	slots;		/* Slots in bucket array */

	printf("Hash:0x%x Count:%d Limit:%d Slots:%d\n",
			hash, hash->count, hash->limit, hash->slots);
	printf("Key_Empty:%d Key_Equal:0x%x Key_Hash:0x%x Key_Insert:0x%x\n",
		hash->key_empty, hash->key_equal,
		hash->key_hash, hash->key_insert);
	printf("Value_Empty:%d Value_Insert:%d Buckets:0x%x\n",
		hash->value_empty, hash->value_insert, hash->buckets);

	buckets = hash->buckets;
	slots = hash->slots;
	for (slot = 0; slot < slots; slot++){
		printf("[%d]", slot);
		bucket = buckets[slot];
		if (bucket == EMPTY)
			printf("\tEmpty\n");
		else if (bucket == REHASH)
			printf("\tRehash\n");
		else {	while (bucket != NULL){
				printf("\tBucket:0x%x Index:0x%x",
					bucket, bucket->index);
				printf(" Key:0x%x Value:0x%x\n",
					bucket->key, bucket->value);
				bucket = bucket->next;
			}
		}
	}
}

/*
 * nse_hash_size(hash) returns the number of entries in Hash.
 */
int
nse_hash_size(hash)
	Hash hash;		/* Hash table to use */
{
	return hash->count;
}

#ifdef UNUSED
/*
 * nse_hash_write(hash, out_file, key_write, key_handle, value_write, value_handle)
 * will write out Hash to Out_File by calling
 * Key_Write(Out_File, Key, Key_Handle) to write Key to Out_File
 * Value_Write(Out_File, Value, Value_Handle) to write Valut to Out_File.
 * If Key_Write or Value_Write are NULL, integer write routines will be used.
 */
void
nse_hash_write(hash, out_file, key_write, key_handle, value_write, value_handle)
	register Hash	hash;		/* Hash table to use */
	register FILE	*out_file;	/* File to output to */
	Void_routine	key_write;	/* Key write routine */
	int		key_handle;	/* Key handle */
	Void_routine	value_write;	/* Value write routine */
	int		value_handle;	/* Value handle */
{
	register Bucket	bucket;		/* Current bucket */
	register Bucket	*buckets;	/* Buckets array pointer */
	register int	count;		/* Loop counter */
	register int	length;		/* Bucket length */

	write_magic(out_file, HASH_MAGIC);
	write_word(out_file, hash->count);
	write_word(out_file, hash->limit);
	write_word(out_file, hash->mask);
	write_word(out_file, hash->slots);

	if (key_write == NULL)
		key_write = write_word;
	if (value_write == NULL)
		value_write = write_word;
	buckets = hash->buckets;
	count = hash->slots;
	while (count-- > 0){
		length = 0;
		for (bucket = *buckets; bucket != NULL; bucket = bucket->next)
			length++;
		write_word(out_file, length);
		for (bucket = *buckets++; bucket != NULL;
					 bucket = bucket->next){
			write_word(out_file, bucket->index);
			key_write(out_file, bucket->key, key_handle);
			value_write(out_file, bucket->value, value_handle);
		}
	}
	write_magic(out_file, HASH_MAGIC);
}
#endif

/*
 * memory_allocate(size) will allocate Size bytes of memory.  If insufficient
 * memory is available, a fatal error will occur.
 */
static char *
memory_allocate(size)
	int		size;		/* Number of bytes to allocate */
{
	register char	*data;		/* Newly allocated data */

	data = malloc((unsigned)size);
	if (data != NULL)
		return data;
	else {
		fprintf(stderr,
			"Could not allcoate %d bytes (Out of swap space?)\n",
			size);
		exit(1);
		/* NOTREACHED */
	}
}

/*
 * memory_deallocate(memory, size) will free the Size bytes of Memory.
 */
/* ARGSUSED */
static void
memory_deallocate(memory, size)
	char		*memory;	/* Data to free */
	int		size;		/* Number of bytes to free */
{
	free(memory);
}

#ifdef UNUSED
/*
 * read_magic(in_file, magic) will make sure that the next word from In_File
 * is Magic.
 */
static void
read_magic(in_file, magic)
	FILE		*in_file;	/* Input file */
	int		magic;		/* Magic number */
{
	int		temp;		/* Temporary */

	temp = read_word(in_file);
	if (temp != magic){
		fprintf(stderr, "0x%x found instead of 0x%x\n", temp, magic);
		exit(1);
	}
}

/*
 * read_word(in_file) will read in a word from In_File.
 */
static int
read_word(in_file)
	register FILE	*in_file;	/* Input file */
{
	return getw(in_file);
}

/*
 * write_magic(out_file, magic) will write Magic to Out_File.
 */
static void
write_magic(out_file, magic)
	FILE		*out_file;	/* Output file */
	int		magic;		/* Magic number */
{
	write_word(out_file, magic);
}

/*
 * write_word(out_file, word) will write Word to Out_file.
 */
static void
write_word(out_file, word)
	register FILE	*out_file;	/* Output file */
	int		word;		/* Word to output */
{
	putw(word, out_file);
}
#endif

/*
 * Generic routine for printing out stats about a hash table.
 * Gives total number of elements, the number of bytes occupied by
 * the keys and values, the number of bytes private to the data structure
 * for the keys and values (strings for instances), and the amount of 
 * hash overhead.
 */
void
nse_hash_print_stats(fp, hash, keysize, valsize, func, str)
	FILE		*fp;
	Hash		hash;
	int		keysize;
	int		valsize;
	Nse_intfunc	func;
	char		*str;
{
	int		n;
	int		data_bytes;
	int		private_bytes;
	int		hash_bytes;

	if (hash == NULL) {
		return;
	}
	n = hash->count;
	fprintf(fp, "\n");
	fprintf(fp, "%s\n", str);
	fprintf(fp, "\t%-20s %6d\n", "# elements in hash", n);
	fprintf(fp, "\t%-20s %6d\n", "hash table size", hash->slots);
	data_bytes = n * (keysize + valsize);
	fprintf(fp, "\t%-20s %6d\n", "bytes in hash data", data_bytes);
	if (func != NULL) {
		private_bytes = nse_hash_scan(hash, func, NULL);
	} else {
		private_bytes = 0;
	}
	fprintf(fp, "\t%-20s %6d\n", "data-specific bytes", private_bytes);
	hash_bytes = sizeof(struct _hash) +
		hash->slots * sizeof(Bucket) +
		n * sizeof(struct _bucket);
	fprintf(fp, "\t%-20s %6d\n", "hash overhead", hash_bytes);
	fprintf(fp, "\t%-20s %6d\n", "total bytes", 
	    data_bytes + private_bytes + hash_bytes);
}