raptor/util/caseless/hashtable.c

/*
 * Copyright (c) 2011-2012 Nokia Corporation and/or its subsidiary(-ies).
 * All rights reserved.
 * This component and the accompanying materials are made available
 * under the terms of the License "Eclipse Public License v1.0"
 * which accompanies this distribution, and is available
 * at the URL "http://www.eclipse.org/legal/epl-v10.html".
 *
 * Initial Contributors:
 * Nokia Corporation - initial contribution.
 *
 * Contributors:
 *
 * Description: 
 *
 * HashTable - basic hashtable, designed with the idea
 * of helping to cache filenames for case-independent lookup
 * so the keys are strings and the values are filenames.
 */

#include <assert.h>
#include <malloc.h>
#include <string.h>
#include "hashtable.h"

/*******************************
 Create a new chaining hashtable
 size - an estimate of how many entries it may need to contain.
*/
HashTable *hashtable_new(size_t size)
{
	assert(size > 0);
	HashTable *h = (HashTable *)malloc(sizeof(HashTable));
	if (!h)
		return NULL;

	h->size = size;
	h->free = h->size;
	h->entries = (HashNode **)calloc(size * sizeof(HashNode *), 1);

	if (! h->entries)
	{
		free(h);
		return NULL;
	}

	return h;
}

void hashtable_del(HashTable **h)
/*
   Delete an entry in the Hashtable.  
   Sets the hashtable pointer passed in as a parameter to NULL so that
   there is less likelihood of a "dangling pointer" happening during
   normal use of this data structure.
*/
{
	assert(*h);
	size_t i;

	for (i = 0; i < (*h)->size; i++)
	{
		HashNode *n = (*h)->entries[i];
		while (n != NULL)
		{
			if (NULL != n->value)
			{ free(n->value); n->value = NULL; }
			if (NULL != n->key)
			{ free(n->key); n->key = NULL; }
			HashNode *t  = n->next;
			n->next = NULL; // Even if there are dangling pointers this will help to prevent trouble.
			free(n);
			n = t;
		}
	}
	free((*h)->entries);
	(*h)->entries = 0;
	free(*h);
	*h = NULL;
}

/* return a hash code for a given key or name */
size_t hashtable_gethash(const char *name)
{
	assert(name);
	const char *l = name;
	char last = 0;
	size_t hash = 0;
	
	while (*l != '\0')
	{
		last = *l;
		hash += last;
		l++;
	}
	/*
	 Make the last character twice as important since absolute filenames
	 tend to differ most at the end.
	*/
	hash += last;

	return hash;
}

char *hashtable_lookup(HashTable *ht, const char *name)
{
	assert(ht);

	size_t h = hashtable_gethash(name);

	if (h == 0)
		return NULL;

	/*
	   Look for the correct chain which
	   this key would be in if it's actually
	   present.  To do this, take the hash
	   of the key and wrap it so it's within
	   the array of chains.
	*/
	HashNode *chainlink = ht->entries[h % ht->size];

	/*
	   We now know which chain to look in
	   so search through the keys in it for
	   the one we're looking for
    */
	while (chainlink != NULL)
	{
		if (strcmp(chainlink->key, name) == 0)
			return chainlink->value;
		chainlink = chainlink->next;
	}

	return NULL;
}


size_t hashtable_store(HashTable *ht, const char *key, const char *value)
/* Copies the key and value into the hash table */
{
	assert(ht);

	size_t h = hashtable_gethash(key);

	if (h == 0)
		return 2;

	/* 
	   Entries in a hash chain (HashNodes) have
	   "next" pointers and to insert a new item into
	   the chain it is necessary to look through the
	   chain item by item for a possible duplicate key.
	   This hashtable departs from "normality" by not
	   replacing the old value with the new.  Instead
	   the old value wins. This is arguably desirable
	   in a filesystem (consistency) but the real
	   reason is that it requires less operations to
	   do this.

	   It is desirable to insert the new HashNode
	   it at the top of the chain if possible - on
	   the theory that any newly added filename has
	   a high chance of being looked several more
	   times by successive operations and that this
	   will ensure that the second and following 
	   operations will not need to search through
	   the chain very far.

	   If a duplicate is found it is "flipped" up to
	   the head of the chain.  If no duplicate exists
	   then a new HashNode is merely inserted at the
	   head of the chain.

	   A pointer to the head of this chain is stored
	   so that it's relatively easy to alter the head
	   later on without writing a lot of repeated
	   code to access it via the array of chains.
	   i.e. a pointer to the head pointer is needed.
    */
	HashNode **head = &ht->entries[h % ht->size];

	/* Keep track of the next pointer of the 
	   last node we visited so that we can
	   alter it if we need to delete a 
	   duplicate.
    */
	HashNode **parent_next = head;

	/* iterator used to look for a duplicate */
	HashNode *dupe = *head; 

	HashNode *newnode = NULL;

	/* Search for a possible duplicate */
	while (dupe)
	{
		if (strcmp(dupe->key, key) == 0)
		{
			free(dupe->value);
			dupe->value = strdup(value);

			break;
		}

		parent_next = &dupe->next;
		dupe = dupe->next;
	}

	if (!dupe)
	{
		/* Put the new Node at the top 
		   of the chain. */
		newnode = (HashNode *)calloc(sizeof(HashNode),1);
		newnode->key = strdup(key);
		newnode->value = strdup(value);
		newnode->next = *head;
		*head = newnode;
	} else {
		/*
		 Flip the duplicate up to the head of the
		 list so the Most Recently Used HashNode
		 is on top.
		 */
		*parent_next = dupe->next;
		dupe->next = *head;
		*head = dupe;
	}

	return 0;
}