Below is the file 'src/common/hash.c' from this revision. You can also download the file.

/* hash.c */

#include <stdlib.h>
#include <string.h>
#include "hash.h"
#include "mem.h"

/*
 * Declare hash as:
 *   struct hashentry hash[HASHSIZE];
 *
 * Initialise with hash_init(hash);
 * free all hash items with hash_clear(hash);
 */

/*
 * Based on Jenkins one-at-a-time hash, from
 * http://en.wikipedia.org/wiki/Hash_table
 */

int hashfn(char *key)
{
	uint32_t hash = 0;
	size_t i;
	size_t len = strlen(key);
     
	for (i = 0; i < len; i++)
	{
		hash += key[i];
		hash += (hash << 10);
		hash ^= (hash >> 6);
	}

	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);

	return hash & HASHMASK;
}


void hash_iterate(struct hashentry **hash, void (*fn)(struct hashentry *))
{
	int i;
	struct hashentry *hashptr;

	for (i = 0; i < HASHSIZE; i++)
		if (hash[i]) {
			hashptr = hash[i];
			while (hashptr) {
				fn(hashptr);
				hashptr = hashptr->next;
			}
		}
}

void hash_clear(struct hashentry **hash)
{
	int i;
	struct hashentry *hashptr;
	struct hashentry *last;

	for (i = 0; i < HASHSIZE; i++)
		if (hash[i]) {
			hashptr = hash[i];
			while (hashptr) {
				last = hashptr;
				hashptr = hashptr->next;
				free(last);
			}
		}
}

void hash_init(struct hashentry **hash)
{
	bzero(hash, sizeof(struct hashentry *) * HASHSIZE);
}


struct hashentry *hash_lookup(struct hashentry **base, char *key, int create)
{
	struct hashentry *hashptr;
	int hash;
	int found;

	hash = hashfn(key);
	hashptr = base[hash];
	found = 0;

	while (hashptr) {
		if (strcmp(key, hashptr->name) == 0)
			return hashptr;
		hashptr = hashptr->next;
	}

	if (!create)
		return NULL;

	hashptr = safe_malloc(sizeof(struct hashentry));
	hashptr->next = base[hash];
	hashptr->name = NULL;	/* Signal that this is new */
	base[hash] = hashptr;

	return hashptr;
}