hash.c

早期freebsd实现

/*
 * Copyright (c) 1983, 1985, 1991 Peter J. Nicklin.
 * Copyright (c) 1991 Version Technology.
 * All Rights Reserved.
 *
 * $License: VT.1.1 $
 * Redistribution and use in source and binary forms,  with or without
 * modification,  are permitted provided that the following conditions
 * are met:  (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
 * Version Technology.''  Neither the name of Version  Technology  nor
 * the  name  of  Peter J. Nicklin  may  be used to endorse or promote
 * products derived from this software without specific prior  written
 * permission.
 *
 * THIS SOFTWARE IS PROVIDED BY VERSION TECHNOLOGY ``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  VERSION  TECHNOLOGY  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 SUCH
 * DAMAGE.
 *
 * Report problems and direct questions to [e-mail]
 *
 * $Header: hash.c,v 4.3 91/11/25 19:44:59 nicklin Exp $
 *
 * Author: Peter J. Nicklin
 */
#include "null.h"
#include "hash.h"
#include "macro.h"
#include "true.h"

/*
 * hthash() returns a hash value for string, s.
 */
hthash(s, hash)
	register char *s;		/* string */
	HASH *hash;			/* hash table */
{
	register int hashval;		/* hash value for string */

	for (hashval = 0; *s != '\0'; s++)
		hashval += *s;
	return(hashval % hash->hashsiz);
}



/*
 * htinit() returns a pointer to a new hash table, or a null pointer if
 * out of memory.
 */
HASH *
htinit(hashsiz)
	unsigned int hashsiz;		/* hash table size */
{
	char *malloc();			/* allocate memory */
	char *calloc();			/* allocate and zero memory */
	HASH *ht;			/* pointer to hash table struct */
	HASHBLK **pt;			/* pointer to hash pointer table */

	if ((ht = (HASH *) malloc(sizeof(HASH))) == NULL ||
	    (pt = (HASHBLK **) calloc(hashsiz, sizeof(HASHBLK *))) == NULL)
		{
		nocore();
		return(NULL);
		}
	ht->hashtab = pt;
	ht->headblk = -1;
	ht->thisblk = NULL;
	ht->hashsiz = hashsiz;
	ht->nk = 0;
	return(ht);
}



/*
 * htinstall() installs a new entry in a hash table if it doesn't already
 * exist. If it does, the old definition and value is superseded. Returns
 * a pointer to the entry, or null if out of memory.
 */
HASHBLK *
htinstall(key, def, val, hash)
	char *key;			/* key for hash table entry */
	char *def;			/* definition string */
	int val;			/* integer value */
	HASH *hash;			/* hash table */
{
	char *malloc();			/* memory allocator */
	char *strsav();			/* save string somewhere */
	HASHBLK *htb;			/* hash table entry block */
	HASHBLK *htlookup();		/* find hash table entry */
	int hashval;			/* hash value for key */
	int hthash();			/* calculate hash value */

	if ((htb = htlookup(key, hash)) == NULL)
		{			/* not found */
		if ((htb = (HASHBLK *) malloc(sizeof(HASHBLK))) == NULL)
			return(NULL);
		if ((htb->h_key = strsav(key)) == NULL)
			return(NULL);
		hashval = hthash(key, hash);
		htb->h_next = (hash->hashtab)[hashval];
		hash->thisblk = (hash->hashtab)[hashval] = htb;
		htb->h_sub = NULL;
		htb->h_tag = NULL;
		}
	else	{			/* found: free previous definition */
		if (htb->h_def != NULL)
			free(htb->h_def);
		}
	if (def == NULL)
		htb->h_def = NULL;
	else if ((htb->h_def = strsav(def)) == NULL)
		return(NULL);
	htb->h_val = val;
	hash->nk++;
	return(htb);
}



/*
 * htlookup() returns a pointer to a hash table entry if found, otherwise null.
 */
HASHBLK *
htlookup(key, hash)
	char *key;			/* key for hash table entry */
	HASH *hash;			/* hash table */
{
	HASHBLK *htb;			/* hash table entry block */
	int hthash();			/* calculate hash value */

	for (htb = (hash->hashtab)[hthash(key, hash)]; htb != NULL; htb = htb->h_next)
		if (EQUAL(htb->h_key, key))
			return(hash->thisblk = htb);	/* found */
	return(hash->thisblk = NULL);			/* not found */
}



/*
 * htrm() removes a hash table entry. If key is null, the entire hash
 * table is removed.
 */
void
htrm(key, hash)
	char *key;			/* key for hash table entry */
	HASH *hash;			/* hash table */
{
	HASHBLK *htbrm();		/* remove hash table block */
	HASHBLK *htc;			/* first hash table block in chain */
	int hashval;			/* hash value for key */
	int hthash();			/* compute hash value */
	int i;				/* hash table index */

	if (key == NULL)
		{
		for (i = 0; i < hash->hashsiz; i++)
			if ((htc = (hash->hashtab)[i]) != NULL)
				(void) htbrm(key, htc);
		free((char *) hash);
		}
	else	{
		hashval = hthash(key, hash);
		if ((htc = (hash->hashtab)[hashval]) != NULL)
			(hash->hashtab)[hashval] = htbrm(key, htc);
		hash->nk--;
		}
}



/*
 * htbrm() removes a hash table block identified by key. If key is null, the
 * entire chain is removed. Returns a pointer to the first block in the chain.
 */
HASHBLK *
htbrm(key, htc)
	char *key;			/* key string */
	HASHBLK *htc;			/* hash table block chain */
{
	HASHBLK *curblk;		/* current list block */
	HASHBLK *nxtblk;		/* next list block */
	HASHBLK *prvblk;		/* previous list block */

	if (key == NULL)
		while (htc != NULL)
			{
			nxtblk = htc->h_next;
			free(htc->h_key);
			if (htc->h_def != NULL)
				free(htc->h_def);
			free((char *) htc);
			htc = nxtblk;
			}
	else	{
		/* first block is a special case */
		if (EQUAL(htc->h_key, key))
			{
			nxtblk = htc->h_next;
			free(htc->h_key);
			if (htc->h_def != NULL)
				free(htc->h_def);
			free((char *) htc);
			htc = nxtblk;
			}
		else	{
			/* remainder of list */
			prvblk = htc;
			curblk = htc->h_next;
			while (curblk != NULL)
				if (EQUAL(curblk->h_key, key))
					{
					prvblk->h_next = curblk->h_next;
					free(curblk->h_key);
					if (htc->h_def != NULL)
						free(curblk->h_def);
					free((char *) curblk);
					break;
					}
				else	{
					prvblk = curblk;
					curblk = curblk->h_next;
					}
			}
		}
	return(htc);
}



/*
 * htnext() positions the current hash table pointer at the next hash
 * table block. Returns FALSE if no more blocks, otherwise TRUE.
 */
int
htnext(hash)
	HASH *hash;			/* hash table */
{
	register int i;			/* hash table index */

	if (hash->thisblk == NULL ||
	   ((hash->thisblk = hash->thisblk->h_next) == NULL))
		{
		for (i = hash->headblk+1; i < hash->hashsiz; i++)
			{
			if ((hash->hashtab)[i] != NULL)
				{
				  hash->thisblk = (hash->hashtab)[i];
				  break;
				}
			}
		hash->headblk = i;
		}
	return((hash->thisblk != NULL) ? TRUE : FALSE);
}



/*
 * htrewind() resets the current hash table block pointer to the beginning
 * of the hash table (actually one element before the beginning, so that
 * htnext() can increment the current hash table block pointer to the
 * first element.
 */
void
htrewind(hash)
	HASH *hash;			/* hash table */
{
	hash->headblk = -1;
	hash->thisblk = NULL;
}