cdev-1.7.2n/include/StringHash.h

#ifndef _VAR_STRING_HASH_H_
#define _VAR_STRING_HASH_H_ 1

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

class StringHashNode
{
friend class StringHash;
friend class StringHashIterator;

private:
	int              copyKeyFlag;
	char           * hashString;
	void           * hashData;
	StringHashNode * next;

	StringHashNode  ( char * HashString, void * HashData, int copyKey=1);
	~StringHashNode ( void );
};


class StringHash
{
friend class StringHashIterator;

private:
	int               tableSize;
	int               copyKeyFlag;
	StringHashNode ** nodes;
	
public:
	StringHash  (int copyKey = 1, int TableSize = 255 );
	~StringHash ( void );

	inline unsigned int stringHash ( char * hashString );

	inline void insert ( char * hashString, void * hashData );
	inline void remove ( char * hashString );
	inline void * find ( char * hashString );
};


class StringHashIterator
{
private:
	StringHash     * hashTbl;
	StringHashNode * node;
	int              idx;	

public:
	StringHashIterator( StringHash * HashTbl );	
	~StringHashIterator( void );
	
	inline void * first       ( void );
	inline void * operator ++ ( void );
	inline void * operator ++ ( int x );
	inline char * key         ( void );
	inline void * data        ( void );
};


inline StringHashNode::StringHashNode ( char * HashString, void * HashData, int copyKey )
	: next(NULL), copyKeyFlag(copyKey)
	{
	if(copyKeyFlag) hashString = strdup(HashString);
	else            hashString = HashString;
        hashData  = HashData;
	}


inline StringHashNode::~StringHashNode ( void )
	{
	if(copyKeyFlag) delete hashString;
        }


inline StringHash::StringHash  ( int copyKey, int TableSize ) 
	: copyKeyFlag(copyKey), tableSize (TableSize)
	{
	nodes = new StringHashNode * [tableSize];
	memset(nodes, 0, sizeof(StringHashNode *) * tableSize );
	}


inline StringHash::~StringHash ( void )
	{
	for(int i=0; i<tableSize; i++)
		{
		while(nodes[i]!=NULL)
			{
			StringHashNode * node = nodes[i];
			nodes[i] = node->next;
			delete node;
                        }
		}
	delete nodes;
	}

inline unsigned int StringHash::stringHash ( char * hashString )
	{
	unsigned int hash = 0, g;

	for (int i = 0; hashString[i] != '\0'; i++)
		{
		hash = (hash << 4) + hashString[i];
		if (g = hash & 0xf0000000)
			{
			hash ^= g >> 24;
			hash ^= g;
			}
		}
	return (hash % tableSize);
	}

inline void StringHash::insert (char * hashString, void * hashData )
	{
	unsigned int idx = stringHash(hashString);
	StringHashNode * prev    = NULL, * node = nodes[idx];
	StringHashNode * newNode = new StringHashNode(hashString, hashData, copyKeyFlag);

	while(node!=NULL && strcmp(node->hashString, hashString))
		{
		prev = node;
		node = prev->next;
		}
	if(node!=NULL)
		{
		newNode->next = node->next;
		delete node;
		}
	if(prev!=NULL) prev->next = newNode;
	else           nodes[idx] = newNode;
	}

inline void StringHash::remove ( char * hashString )
	{
	unsigned int idx = stringHash(hashString);
	StringHashNode * prev = NULL, * node = nodes[idx];
	while(node!=NULL && strcmp(node->hashString, hashString))
		{
		prev = node;
		node = prev->next;
		}
	if(node!=NULL)
		{
		if(prev!=NULL) prev->next = node->next;
		else           nodes[idx] = node->next;
		delete node;
		}
	}

inline void * StringHash::find ( char * hashString )
	{
	unsigned int idx = stringHash(hashString);
	StringHashNode * prev = NULL, * node = nodes[idx];
	while(node!=NULL && strcmp(node->hashString, hashString))
		{
		prev = node;
		node = prev->next;
		}
	return node!=NULL?node->hashData:NULL;
	}


inline StringHashIterator::StringHashIterator(StringHash * HashTbl)
	: hashTbl(HashTbl), idx(0), node(NULL)
	{
	}
	
inline StringHashIterator::~StringHashIterator( void ) 
	{
	}
	
inline void * StringHashIterator::first ( void )
	{
	if(hashTbl!=NULL)
		{
		for(idx = 0; idx<hashTbl->tableSize &&
		   (node = hashTbl->nodes[idx])==NULL; idx++);
		}
	else node = NULL;
	return (node!=NULL)?node->hashData:NULL;
	}
	
inline void * StringHashIterator::operator ++ ( void )
	{
	if(hashTbl!=NULL)
		{
		if(node==NULL) first();
		else if(node->next!=NULL) node = node->next;
		else 
			{
			node = NULL;
			do 	{
				idx++;
				} while(idx<hashTbl->tableSize && 
				       (node = hashTbl->nodes[idx])==NULL);
			}
		}
	else node = NULL;
	return (node!=NULL)?node->hashData:NULL;
	}
	
inline void * StringHashIterator::operator ++ ( int x )
	{
	if(hashTbl!=NULL && x==0)
		{
		if(node==NULL) first();
		else if(node->next!=NULL) node = node->next;
		else 
			{
			node = NULL;
			do 	{
				idx++;
				} while(idx<hashTbl->tableSize && 
				       (node = hashTbl->nodes[idx])==NULL);
			}
		}
	else node = NULL;
	return (node!=NULL)?node->hashData:NULL;
	}

inline char * StringHashIterator::key ( void )
	{
	return (node!=NULL)?node->hashString:(char *)NULL;
	}
	
inline void * StringHashIterator::data ( void )
	{
	return (node!=NULL)?node->hashData:NULL;
	}
	
#endif /* _VAR_STRING_HASH_H_ */