hashtable.c

来自「Sun公司Dream项目」· C语言 代码 · 共 753 行 · 第 1/2 页

/*
 * The contents of this file are subject to the terms
 * of the Common Development and Distribution License
 * (the "License").  You may not use this file except
 * in compliance with the License.
 *
 * You can obtain a copy of the license at
 * http://www.opensource.org/licenses/cddl1.php
 * See the License for the specific language governing
 * permissions and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL
 * HEADER in each file and include the License file at
 * http://www.opensource.org/licenses/cddl1.php.  If 
 * applicable, add the following below this CDDL HEADER, 
 * with the fields enclosed by brackets "[]" replaced 
 * with your own identifying information: 
 * Portions Copyright [yyyy]
 * [name of copyright owner]
 */ 

/*
 * $(@)HashTable.c $Revision: 1.2 $ $Date: 2006/07/15 00:02:34 $
 * 
 * Copyright 2006 Sun Microsystems, Inc. All Rights Reserved.
 */
/*
 * Copyright (c) 1996 by Sun Microsystems, Inc.
 */

#pragma	ident "@(#)HashTable.c 1.3	99/07/29 SMI"

/*
 * Keyed Hash table
 * 
 * FIXME: Make realloc growth smarter -- at small sizes grow more (*2) than at
 * large sizes (*1.25).
 * 
 * FIXME: Consider keep state in separate bit vector from hashItems to reduce
 * memory usage.
 */
#include <stdlib.h>
#include <string.h>

#include "cobjs/Log.h"
#include "cobjs/Macros.h"
#include "cobjs/Types.h"

#include "cobjs/HashTable.h"

#define	MAX_FILL_FACTOR	0.9		   /* fraction full before resize */
#define	MIN_FILL_FACTOR	0.6		   /* fraction full before resize */
#define	FILL_FACTOR	0.8		   /* fraction full before resize */
#define	INIT_LENGTH	67		   /* initial length */
#define	GROWTH_FACTOR	1.5		   /* growth factor (must be > 1) */

#ifdef	DEBUG
#define	KEEP_STATS
#endif	/* DEBUG */

/*
 * OBJECT HashTable Instance Variables
 */
struct _HashTable {
    HashItem           *hashItems;
#ifdef	KEEP_STATS
    HashStats          *hashStats;
#endif					   /* KEEP_STATS */
    int                 length;
    Boolean             isPrime;
    int                 used;
    int                 deleted;
    int                 maxActive;
    int                 probeCount;
    float               fillFactor;
    int                 reallocates;
    KeyHash             keyHash;
    KeyDup              keyDup;
    KeyIsEqual          keyIsEqual;
    KeyFree             keyFree;
#ifdef	ASSERTS
    Boolean		wasModified;
#endif	/* ASSERTS */
};

/*
 * Private types
 */
typedef enum HashKeyType {
    HASH_COPY_KEY,			   /* must copy key */
    HASH_REF_KEY			   /* ok to just take reference */
} HashKeyType;

typedef enum HashFindType {
    HASH_FIND_FREE,			   /* if not found, return free slot */
    HASH_FIND_ACTIVE			   /* if not found, return NULL */
} HashFindType;

/*
 * Private methods
 */
static void
hashTableInsert(HashTable hashTable, const void *key,
		const void *value, HashKeyType keyType);
static HashItem    *
hashTableFind(HashTable hashTable, const void *key,
	      HashFindType findType);
static int          hashTablePrimeSize(HashTable hashTable, int size);

/*
 * Hash table length is constrained (for best performance) to be prime. Next
 * larger prime than desired size is used.  If no prime in this table is
 * larger, just use size.
 * 
 * Program for generating primes is ifdef'ed out at end of this file.
 */
static const int    primes[] = {
    5, 11, 19, 23, 29, 37, 43, 53, 67, 79, 101, 127, 157, 191, 239, 307,
    367, 461, 577, 719, 907, 1117, 1399, 1741, 2179, 2719, 3407, 4243, 5303,
    6637, 8287, 10357, 12941, 16183, 20219, 25301, 31601, 39499, 49363, 61703,
    77137, 96419, 120503, 150649, 188291, 235369, 294199, 367739, 459677
};

/*
 * Create a string keyed hashtable.
 */
HashTable
hashTableStrNew(void)
{
    return hashTableNew(strHash, strIsEqual, strDup, free);
}

/*
 * Create an integer keyed hashtable.
 */
HashTable
hashTableIntNew(void)
{
    return hashTableNew(intHash, intIsEqual, NULL, NULL);
}

/*
 * Create a hashtable with given key type
 */
HashTable
hashTableNew(KeyHash keyHash, KeyIsEqual keyIsEqual, KeyDup keyDup,
	     KeyFree keyFree)
{
    /*
     * Creates and returns a new hash table with default size and fill
     * factor.
     */
    return hashTableNewWithSizeAndFactor(INIT_LENGTH, FILL_FACTOR,
				      keyHash, keyIsEqual, keyDup, keyFree);
}

HashTable
hashTableIntNewWithSizeAndFactor(int size, float factor)
{
    return hashTableNewWithSizeAndFactor(size, factor,
				      intHash, intIsEqual, NULL, NULL);
}

HashTable
hashTableStrNewWithSizeAndFactor(int size, float factor)
{
    return hashTableNewWithSizeAndFactor(size, factor,
					 strHash, strIsEqual, strDup, free);
}

HashTable
hashTableNewWithSizeAndFactor(int size, float factor, KeyHash keyHash,
			      KeyIsEqual keyIsEqual, KeyDup keyDup,
			      KeyFree keyFree)
{
    /*
     * Creates and returns a new hash table
     */
    HashTable           hashTable;

#if (REHASH_RANGE & (REHASH_RANGE - 1)) != 0
#error REHASH_RANGE must be power of two
#endif	/* __lint */
    if (factor < MIN_FILL_FACTOR) {
	factor = MIN_FILL_FACTOR;
    }
    if (factor > MAX_FILL_FACTOR) {
	factor = MAX_FILL_FACTOR;
    }
    if ((hashTable = NEW_ZEROED(struct _HashTable, 1)) != NULL) {
	hashTable->length = hashTablePrimeSize(hashTable, size);
	hashTable->fillFactor = factor;
	hashTable->maxActive = hashTable->fillFactor * hashTable->length;
	if (hashTable->maxActive >= hashTable->length) {
	    hashTable->maxActive = hashTable->length - 1;
	}
	hashTable->keyHash = keyHash;
	hashTable->keyIsEqual = keyIsEqual;
	hashTable->keyDup = keyDup;
	hashTable->keyFree = keyFree;
#ifdef	ASSERTS
	hashTable->wasModified = FALSE;
#endif	/* ASSERTS */
#ifdef	KEEP_STATS
	hashTable->hashStats = NEW_ZEROED(HashStats, hashTable->length);
#endif					   /* KEEP_STATS */
	if ((hashTable->hashItems = NEW_ZEROED(HashItem, hashTable->length))
		== NULL) {
	    free(hashTable);
	    hashTable = NULL;
	}
    }
    return hashTable;
}


Boolean
_hashTablePut(HashTable hashTable, const void *key, const void *value)
{
    /*
     * Enters key-value pair into hash table. If key already exists, it's
     * value is overwritten.
     */
    hashTable->probeCount = 0;
    if (hashTable->used + hashTable->deleted >= hashTable->maxActive) {
	HashItem           *oldItems = hashTable->hashItems;
	int                 oldMaxActive = hashTable->maxActive;

#ifdef	KEEP_STATS
	HashStats          *oldStats = hashTable->hashStats;

#endif					   /* KEEP_STATS */
	int                 oldLength = hashTable->length;
	HashItem           *item;

	if (hashTable->deleted * 3 <= hashTable->used) {
	    hashTable->length = hashTablePrimeSize(hashTable, 1 +
				 (int) (hashTable->length * GROWTH_FACTOR));
	    hashTable->maxActive = hashTable->fillFactor * hashTable->length;
	    if (hashTable->maxActive >= hashTable->length) {
		hashTable->maxActive = hashTable->length - 1;
	    }
	}
	if ((hashTable->hashItems = NEW_ZEROED(HashItem, hashTable->length))
		== NULL) {
	    hashTable->length = oldLength;
	    hashTable->maxActive = oldMaxActive;
	    hashTable->hashItems = oldItems;
#ifdef	KEEP_STATS
	    hashTable->hashStats = oldStats;
#endif					   /* KEEP_STATS */
	    return FALSE;
	}
#ifdef	KEEP_STATS
	hashTable->hashStats = NEW_ZEROED(HashStats, hashTable->length);
#endif					   /* KEEP_STATS */
	hashTable->used = 0;
	hashTable->deleted = 0;

	for (item = oldItems; item < &oldItems[oldLength]; item++) {
	    if (item->state == HASHITEM_ACTIVE) {
		hashTableInsert(hashTable, item->key,
				item->value, HASH_REF_KEY);
	    }
	}
	free(oldItems);
#ifdef	KEEP_STATS
	free(oldStats);
#endif					   /* KEEP_STATS */
	hashTable->reallocates += 1;
    }
    hashTableInsert(hashTable, key, value, HASH_COPY_KEY);
#ifdef	ASSERTS
    hashTable->wasModified = TRUE;
#endif	/* ASSERTS */
    return TRUE;
}

void               *
_hashTableGet(HashTable hashTable, const void *key)
{
    /*
     * Returns the value associated with key. Returns NULL if the key is not
     * found.
     */
    HashItem           *hashItem;

    hashTable->probeCount = 0;
    hashItem = hashTableFind(hashTable, key, HASH_FIND_ACTIVE);
    return hashItem != NULL ? (void *) hashItem->value : NULL;
}

Boolean
_hashTableIsMember(HashTable hashTable, const void *key)
{
    /*
     * Returns TRUE if key is in hashtable.
     */
    HashItem           *hashItem;

    hashTable->probeCount = 0;
    hashItem = hashTableFind(hashTable, key, HASH_FIND_ACTIVE);
    return Boolean(hashItem != NULL);
}

void               *
_hashTableRemove(HashTable hashTable, const void *key)
{
    /*
     * Remove the key-value pair from the hash table. It is not an error if
     * key does not exist. Returns the value associated with the removed
     * key-value pair. Returns NULL if the key is not found.
     */
    HashItem           *hashItem;
    void               *value = NULL;

    hashTable->probeCount = 0;
    hashItem = hashTableFind(hashTable, key, HASH_FIND_ACTIVE);

    if (hashItem != NULL) {
	value = (void *) hashItem->value;
	if (hashTable->keyFree != NULL) {
	    (*hashTable->keyFree) ((void *) hashItem->key);
	}
	hashItem->state = HASHITEM_DELETED;
	hashTable->used--;
	hashTable->deleted++;
    }
#ifdef	ASSERTS
    hashTable->wasModified = TRUE;
#endif	/* ASSERTS */
    return value;
}

int
hashTableProbeCount(const HashTable hashTable)
{
    return hashTable->probeCount;
}

int
hashTableLength(const HashTable hashTable)
{
    /*
     * Returns the current length of the hash table.
     */
    return hashTable->length;
}

int
hashTableUsed(const HashTable hashTable)
{
    /*
     * Returns the current number of entries used in the hash table.
     */
    return hashTable->used;
}

int
hashTableReallocates(const HashTable hashTable)
{
    /*
     * Returns the number of times the hash table was reallocated.
     */
    return hashTable->reallocates;
}

/* ARGSUSED */
HashStats          *
hashTableStats(const HashTable hashTable)
{
#ifdef	KEEP_STATS
    HashStats          *dupStats;

    dupStats = NEW_ZEROED(HashStats, hashTable->length);
    (void) memcpy(dupStats, hashTable->hashStats,
		  sizeof(HashStats) * hashTable->length);