hashtable.c

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

    return dupStats;
#else					   /* KEEP_STATS */
                        return NULL;
#endif					   /* KEEP_STATS */
}

HashItem           *
hashTableDump(const HashTable hashTable)
{
    /*
     * Returns hash table contents as an array of HashItems End of array is
     * marked by HashItem with key == NULL.
     * 
     * Caller should not modify the data referenced by keys or values returned.
     * 
     * Caller should free() the HashItem array when done.
     */
    HashItem           *itemsDump = NEW(HashItem, hashTable->used + 1);
    HashItem           *item;
    HashItem           *dumpItem;

    for (item = hashTable->hashItems, dumpItem = itemsDump;
	    item < &hashTable->hashItems[hashTable->length];
	    item++) {
	if (item->state == HASHITEM_ACTIVE) {
	    *dumpItem++ = *item;
	}
    }
    dumpItem->key = NULL;
    dumpItem->value = NULL;
    return itemsDump;
}

void
hashTableFree(HashTable hashTable)
{
    /*
     * Frees the hashtable. Does not free the values.
     */
    HashItem           *item;

    if (hashTable->keyFree != NULL) {
	for (item = hashTable->hashItems;
		item < &hashTable->hashItems[hashTable->length];
		item++) {
	    if (item->state == HASHITEM_ACTIVE) {
		(*hashTable->keyFree) ((void *) item->key);
	    }
	}
    }
    free(hashTable->hashItems);
#ifdef	KEEP_STATS
    free(hashTable->hashStats);
#endif					   /* KEEP_STATS */
    free(hashTable);
}

/************************************************************************
 * Useful Hash, Dup, and IsEqual Functions
 ************************************************************************/

unsigned long
strHash(const void *key, unsigned int *incrp)
{
    const unsigned char *kp = (const unsigned char *) key;
    unsigned long       h = 0;
    unsigned            incr = 0;
    unsigned long       g;
    unsigned char       k;

    while ((k = *kp++) != '\0') {
	h = (h << 4) + k;
	incr += k;
	if ((g = h & 0xF0000000) != 0) {
	    h ^= g >> 24;
	}
	h &= ~g;
    }
    *incrp = incr;
    return h;
}

Boolean
strIsEqual(const void *p1, const void *p2)
{
    const char         *s1 = (const char *) p1;
    const char         *s2 = (const char *) p2;
    char                c;

    while ((c = *s1++) == *s2++) {
	if (c == '\0') {
	    return TRUE;
	}
    }
    return FALSE;
}

/* ARGSUSED1 */
const void  *
strDup(const void *p, const void *value)
{
    int                 len = strlen((char *) p) + 1;
    void               *p2 = NEW(char, len);

    return memcpy(p2, p, len);
}

unsigned long
intHash(const void *key, unsigned int *incrp)
{
    *incrp = (unsigned int) key >> 4;
    return ((unsigned long) key * 123821) >> 10;
}

Boolean
intIsEqual(const void *key1, const void *key2)
{
    return Boolean(key1 == key2);
}

/************************************************************************
 * OBJECT HashIter Instance Type
 ************************************************************************/
struct _HashIter {
    HashTable           hashTable;
    int                 index;
};

/************************************************************************
 * OBJECT HashIter Class Interface
 ************************************************************************/

/**
 * Create a HashTable Iterator
 *
 * BEWARE: A hashTable iterator is invalidated by any modification to the
 * referred to hashtable. I.e. removal or addition of an item to the hashtable
 * will cause "undefined" results.
 */
HashIter
hashIterNew(const HashTable hashTable)
{
    HashIter            hi;

    if ((hi = NEW_ZEROED(struct _HashIter, 1)) != NULL) {
	hi->hashTable = hashTable;
	hi->index = -1;
    }
    return hi;
}

/************************************************************************
 * OBJECT HashIter Instance Interface
 ************************************************************************/

/**
 * Initialize iterator to first item in hashtable.
 * Returns TRUE if hashtable is non-empty; FALSE if hashtable is empty.
 */
Boolean
hashIterFirst(HashIter hi)
{
    Boolean             isNonEmpty = Boolean(hashTableUsed(hi->hashTable) != 0);

    hi->index = -1;
    if (isNonEmpty) {
	(void) hashIterNext(hi);
    }
    return isNonEmpty;
}

/**
 * Position iterator at next item in hashtable. Return TRUE if there
 * is a next item; FALSE if wrapping around.
 */
Boolean
hashIterNext(HashIter hi)
{
    HashTable           hashTable = hi->hashTable;


    ASSERT(hi->index == -1 || ! hashTable->wasModified);
    while (++hi->index < hashTable->length) {
	ASSERT(hi->index >= 0 && hi->index < hashTable->length);
	if (hashTable->hashItems[hi->index].state == HASHITEM_ACTIVE) {
#ifdef	ASSERTS
	    hi->hashTable->wasModified = FALSE;
#endif	/* ASSERTS */
	    return TRUE;
	}
    }
    hi->index = -1;
    return FALSE;
}

/**
 * Return a pointer to the item referenced by the iterator.
 * Returns NULL if iterator not positioned at item.
 */
const HashItem           *
hashIterItem(const HashIter hi)
{
    HashTable           hashTable = hi->hashTable;

    ASSERT(! hashTable->wasModified);
    return hashIterValid(hi) ? &hashTable->hashItems[hi->index] : NULL;
}

/**
 * Return a pointer to the key referenced by the iterator.
 * Returns NULL if iterator not positioned at item.
 */
const void           *
hashIterKey(const HashIter hi)
{
    HashTable           hashTable = hi->hashTable;

    ASSERT(! hashTable->wasModified);
    return hashIterValid(hi) ? hashTable->hashItems[hi->index].key : NULL;
}

/**
 * Return a pointer to the key referenced by the iterator.
 * Returns NULL if iterator not positioned at item.
 */
const void           *
hashIterValue(const HashIter hi)
{
    HashTable           hashTable = hi->hashTable;

    ASSERT(! hashTable->wasModified);
    return hashIterValid(hi) ? hashTable->hashItems[hi->index].value : NULL;
}

/**
 * Return TRUE if iterator points to valid item.
 */
Boolean
hashIterValid(const HashIter hi)
{
    HashTable           hashTable = hi->hashTable;

    ASSERT(! hashTable->wasModified);
    return Boolean((hi->index >= 0 && hi->index < hashTable->length
	    && hashTable->hashItems[hi->index].state == HASHITEM_ACTIVE));
}

/**
 * Remove the item referenced by the iterator.
 * Returns TRUE if iterator positioned at valid item.
 * Returns FALSE if iterator not positioned at item.
 */
Boolean
hashIterRemove(HashIter hi)
{
    HashTable           hashTable = hi->hashTable;
    HashItem           *hashItem = (HashItem *)hashIterItem(hi);
    Boolean             isValid = Boolean(hashItem != NULL);

    ASSERT(! hashTable->wasModified);
    if (isValid) {
	if (hashTable->keyFree != NULL) {
	    (*hashTable->keyFree) ((void *) hashItem->key);
	}
	hashItem->state = HASHITEM_DELETED;
	hashTable->used--;
	hashTable->deleted++;
    }
    return isValid;
}

/*
 * Free an iterator
 */
void
hashIterFree(HashIter hi)
{
    free(hi);
}

static void
hashTableInsert(HashTable hashTable, const void *key, const void *value,
		HashKeyType keyType)
{
    /*
     * Insert a new key-value pair into the hash table. keyType indicates
     * whether the key must be copied (user insertion) or may simply be
     * referenced (reallocate -- i.e. it's already been copied).
     */
    HashItem           *newItem = hashTableFind(hashTable, key, HASH_FIND_FREE);

    ASSERT(newItem != NULL);
    if (newItem->state != HASHITEM_ACTIVE) {
	if (newItem->state == HASHITEM_DELETED) {
	    hashTable->deleted--;
	}
	newItem->state = HASHITEM_ACTIVE;
	hashTable->used++;
	newItem->key = (keyType == HASH_REF_KEY || hashTable->keyDup == NULL)
	  ? key : (*hashTable->keyDup)(key, value);
    }
    newItem->value = value;
}

static HashItem    *
hashTableFind(HashTable hashTable, const void *key, HashFindType findType)
{
    /*
     * Look up a key in the hash table. If found, return a pointer to the
     * entry. If not found and findFree, return a pointer to where the entry
     * should go.
     */
    unsigned            incr = 0;	   /* avoid lint complaint */
    unsigned            index = (*hashTable->keyHash) (key, &incr)
    % hashTable->length;
    HashItem           *hip = &hashTable->hashItems[index];
    HashItem           *freeHip = NULL;
    int                 probes = 0;

#ifdef	KEEP_STATS
    int                 oindex = index;

#endif					   /* KEEP_STATS */

    if (hashTable->isPrime && hashTable->length > REHASH_RANGE) {
	incr = incr & (REHASH_RANGE - 1);
	incr = REHASH_RANGE - incr;
    } else {
	incr = 1;
    }

    hashTable->probeCount += 1;
    while (hip->state != HASHITEM_FREE) {
	ASSERT(probes < hashTable->length);
	if (hip->state == HASHITEM_ACTIVE
		&& (*hashTable->keyIsEqual) (key, hip->key)) {
	    return hip;
	} else if (hip->state == HASHITEM_DELETED && freeHip == NULL) {
	    freeHip = hip;
	}
	index = (index + incr) % hashTable->length;
	hip = &hashTable->hashItems[index];
	hashTable->probeCount += 1;
	probes += 1;
    }
    if (freeHip == NULL) {
	freeHip = hip;
    }
#ifdef	KEEP_STATS
    if (findType == HASH_FIND_FREE) {
	hashTable->hashStats[oindex].hits += 1;
	hashTable->hashStats[oindex].rehash[incr - 1] += 1;
    }
#endif					   /* KEEP_STATS */
    return findType == HASH_FIND_FREE ? freeHip : NULL;
}

static int
hashTablePrimeSize(HashTable hashTable, int size)
{
    /*
     * Find the first entry in the prime table that's greater or equal to
     * size.
     */
    int                 i;

    for (i = 0; i < NELEM(primes); i++) {
	if (primes[i] >= size) {
	    hashTable->isPrime = TRUE;
	    return primes[i];
	}
    }
    hashTable->isPrime = FALSE;
    return size;
}