hashtable.h

barcode readers [ from Image]

// 
// CHashTable
//   This is a translation into C++ of Bob Jenkins's 1996 C code from
//   http://burtleburtle.net/bob/hash/hashtab.html. The code has been 
//   extensively modified to follow Symbian coding conventions.
//
// Modifications copyright (C) 2006 by Jon A. Webb 
// (Contact via GMail; username is jonawebb)
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
// 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//
// Copyright notice from original code:
//--------------------------------------------------------------------
//By Bob Jenkins, 1996.  hash.h.  Public Domain.
//
//This implements a hash iTable.
//* Keys are unique.  Adding an item fails if the key is already there.
//* Keys and items are pointed at, not copied.  If you change the value
//  of the key after it is inserted then Find will not be able to find it.
//* The hash iTable maintains a position that can be set and queried.
//* The iTable length doubles dynamically and never shrinks.  The insert
//  that causes iTable doubling may take a long time.
//* The iTable length splits when the iTable length equals the number of items
//  Comparisons usually take 7 instructions.
//  Computing a hash value takes 35+6n instructions for an n-byte key.
//
//  hcreate  - create a hash iTable
//  hdestroy - destroy a hash iTable
//   Count  - The number of items in the hash iTable
//   Key    - key at the current position
//   KeyLength   - key length at the current position
//   Value  - stuff at the current position
//  Find    - find an item in the iTable
//   AddL    - insert an item into the iTable
//   Delete    - delete an item from the iTable
//  Stats    - print statistics about the iTable
//   First  - position at the first item in the iTable
//   Next   - move the position to the next item in the iTable
//--------------------------------------------------------------------

#ifndef CHashTable_h
#define CHashTable_h

#include <e32base.h>
#include <e32def.h>

namespace Core
{
	template<class KeyType, class ValueType>
	class CHashTable: public CBase
	{
	private:
		/* PRIVATE TYPES AND DEFINITIONS */
		struct hitem
		{
			KeyType *key;      /* key that is hashed */
			ValueType stuff;   /* stuff stored in this hitem */
			TUint32 hval;      /* hash value */
			struct hitem *next;     /* next hitem in list */
			int     spos;     /* position in the store */
		};
		typedef  struct hitem  hitem;
	public:
		//
		// Lifecycle
		//
	private:
		// Constructor
		CHashTable();

		/* ConstructL - create a hash iTable
		ARGUMENTS:
			inLogSize - 1<<inLogSize will be the initial iTable length
		RETURNS:
			the new iTable
		*/
		void ConstructL(TInt inLogSize);

	public:
		/* NewL - create a hash iTable
		ARGUMENTS:
			inLogSize - 1<<inLogSize will be the initial iTable length
		RETURNS:
			the new iTable
		*/
		IMPORT_C static CHashTable* NewL(TInt inLogSize);

		// Destructor
		/*   Note that the items and keys
		     will not be freed, the user created them and must destroy
			 them himself.
		*/
		~CHashTable();

		//
		// OPERATIONS
		//
	public:
		/* AddL - add a new item to the hash iTable
				change the position to point at the item with the key
		ARGUMENTS:
			key   - the key to look for
			keyl  - length of the key
			stuff - other stuff to be stored in this item
		RETURNS:
			FALSE if the operation fails (because that key is already there).
		*/
		TInt  AddL(KeyType *key, ValueType stuff);

		/* Clear - remove all elements from the hash table */
		void Clear();

		/* Delete - delete the item at the current position
				change the position to the following item
		ARGUMENTS:
			t    - the hash iTable
		RETURNS:
			FALSE if there is no current item (meaning the iTable is empty)
		NOTE:
			This frees the item, but not the key or stuff stored in the item.
			If you want these then deal with them first.  For example:
			if (Find(tab, key, keyl))
			{
				free(Key(tab));
				free(Value(tab));
				Delete(tab);
			}
		*/
		TInt  DeleteL();

		/* Find - move the current position to a given key
		ARGUMENTS:
			key  - the key to look for
			keyl - length of the key
		RETURNS:
			TRUE if the item exists, FALSE if it does not.
			If the item exists, moves the current position to that item.
		*/
		TInt  Find(KeyType *key);

		/* First - move position to the first item in the iTable
		ARGUMENTS:
			t    - the hash iTable
		RETURNS:
			FALSE if there is no current item (meaning the iTable is empty)
		NOTE:
		*/
		TInt First();	
		/* Next - advance to next item in the iTable */
		TInt Next();
		
	private:
		/*
		* GrowL - Double the size of a hash iTable.
		* Allocate a new, 2x bigger array,
		* move everything from the old array to the new array,
		* then free the old array.
		*/
		void GrowL();
		/* NextBucket - PRIVATE - move to first item in the next nonempty bucket
		ARGUMENTS:
			t    - the hash iTable
		RETURNS:
			FALSE if the position wraps around to the beginning of the iTable
		NOTE:
			This is private to CHashTable_h; do not use it externally.
		*/
		TInt NextBucket();

		//
		// ACCESSORS
		//
	public:
/* Count, Key, KeyLength, Value
RETURNS:
	Count - (TUint32)    The number of items in the hash iTable
	Key   - (TUint8 *)  key for the current item
	KeyLength  - (TUint32)    key length for the current item
	Value - (void *) stuff for the current item
NOTE:
	The current position always has an item as long as there
	are items in the iTable, so hexist can be used to test if the
	iTable is empty.
	Key, KeyLength, and Value will crash if Count returns 0
*/
	TUint32 Count() const; 
	KeyType* Key() const;
	ValueType& Value();
	ValueType Value() const;

		/* sanity check -- make sure iPos, iAPos, and inCount make sense */
		void  Sanity() const;

		/* Stats - print statistics about the hash iTable
		ARGUMENTS:
			t    - the hash iTable
		NOTE:
			items <0>:  <#buckets with zero items> buckets
			items <1>:  <#buckets with 1 item> buckets
			...
			buckets: #buckets  items: #items  existing: x
			( x is the average length of the list when you look for an
			item that exists.  When the item does not exists, the average
			length is #items/#buckets. )

			If you put n items into n buckets, expect 1/(n!)e buckets to
			have n items.  That is, .3678 0, .3678 1, .1839 2, ...
			Also expect "existing" to be about 2.
		*/
		void Stats() const;

		//
		// UTILITY FUNCTIONS
		//-
	private:
		static TUint32 Lookup(KeyType *k, TUint32 level);

	public:



	private:
		// Attributes
		CArrayFixFlat<int>* iFreeList; // list of free hitem's in iStore
		CArrayFixSeg<hitem>* iStore; // storage area for hitem's
		struct hitem **iTable;   /* hash iTable, array of size 2^inLogSize */
		TInt           inLogSize; /* log of size of iTable */
		TUint          inMask;    /* (hashval & inMask) is position in iTable */
		TUint32        inCount;   /* how many items in this hash iTable so far? */
		TUint32        iAPos;    /* position in the array */
		struct hitem  *iPos;    /* current item in the array */
	};
};

// instantiate templated class
#include "HashTable.cpp"
#endif   /* CHashTable_h */