hashtable.cpp

barcode readers [ from Image]

// 
// CHashTable
//   This is a translation into C++ of Bob Jenkins's 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
//--------------------------------------------------------------------
// We implement a separate store for the hitem objects, instead of
// using new and delete. This is to reduce the number of accesses to the
// user heap, which gives poor performance for many small objects.
// The hitem objects are stored in a segmented array called iStore.
// The list of free objects in that list is iFreeList.
// When we use a new hitem we take the first index from iFreeList.
// When we free a hitem we add its index to iFreeList.
// When there are no indices in iFreeList we double the size of iStore
// and add all the new indices to iFreeList.

#include <e32base.h>
#include <e32std.h>

using namespace Core;

//
// Lifecycle
//
template<class KeyType, class ValueType>
CHashTable<KeyType, ValueType>::CHashTable()
{
}

/* ConstructL - create a hash iTable initially of size power(2,inLogSize) */
template<class KeyType, class ValueType>
void CHashTable<KeyType, ValueType>::ConstructL(TInt  inLogSize /* log base 2 of the size of the hash iTable */)
{
  TUint32 len = ((TUint32)1<<inLogSize);
  this->iStore = new CArrayFixSeg<hitem>(len);
  this->iFreeList = new CArrayFixFlat<int>(len);
  this->iTable = new (ELeave) hitem* [len];
  Mem::FillZ((TAny*)this->iTable, len * sizeof(hitem *));
  TUint32 i;
  // add all entries in the store to the free list
  for (i=0; i<len; ++i) {
	  this->iFreeList->AppendL(i);
  }
  this->inLogSize = inLogSize;
  this->inMask = len-1;
  this->inCount = 0;
  this->iAPos = (TUint32)0;
  this->iPos = (hitem *)0;
}

template<class KeyType, class ValueType>
EXPORT_C CHashTable<KeyType, ValueType>* CHashTable<KeyType, ValueType>::NewL(TInt inLogSize)
{
	CHashTable<KeyType, ValueType>* pMe = new (ELeave) CHashTable<KeyType, ValueType>;
	CleanupStack::PushL(pMe);
	pMe->ConstructL(inLogSize);
	CleanupStack::Pop(pMe);
	return pMe;
}

/* Destructor - destroy the hash iTable and free all its memory */
template<class KeyType, class ValueType>
CHashTable<KeyType, ValueType>::~CHashTable()
{
  this->iStore->Reset();
  delete this->iStore;
  this->iStore = NULL;
  this->iFreeList->Reset();
  delete this->iFreeList;
  this->iFreeList = NULL;
  delete [] this->iTable;
  this->iTable = NULL;
}

//
// OPERATIONS
//

/*
 * AddL - add an item to a hash iTable.
 * return FALSE if the key is already there, otherwise TRUE.
 */
template<class KeyType, class ValueType>
TInt CHashTable<KeyType, ValueType>::AddL(
	KeyType *key /* key to add to hash iTable */, 
	ValueType stuff /* stuff to associate with this key */)
{
  hitem  *h,**hp;
  TUint32     y, x = Lookup(key,0);

  /* make sure the key is not already there */
  for (h = this->iTable[(y=(x&this->inMask))]; h; h = h->next)
  {
    if ((x == h->hval) && 
		!Mem::Compare((TUint8*)key, sizeof(KeyType), (TUint8*)h->key, sizeof(KeyType)))
    {
      this->iAPos = y;
      this->iPos = h;
      return FALSE;
    }
  }

  /* find space for a new item */
  if (!this->iFreeList->Count()) {
	  int size = this->iStore->Count();
	  int i;
	  for (i=size; i<size*2; i++) {
		  this->iFreeList->AppendL(i);
	  }
  }
  int pos = this->iFreeList->At(0);
  this->iFreeList->Delete(0);
  while (pos+1 >= this->iStore->Count()) {
	  this->iStore->ExtendL();
  }
  h = &this->iStore->At(pos);

  /* make the hash iTable bigger if it is getting full */
  if (++this->inCount > (TUint32)1<<(this->inLogSize))
  {
    GrowL();
    y = (x&this->inMask);
  }

  /* add the new key to the iTable */
  h->spos = pos;
  h->key   = key;
  h->stuff = stuff;
  h->hval  = x;
  hp = &this->iTable[y];
  h->next = *hp;
  *hp = h;
  this->iPos = h;
  this->iAPos = y;

#ifdef HSANITY
  Sanity();
#endif  /* HSANITY */
  return TRUE;
}

/* set the hash table to its initial state */
template<class KeyType, class ValueType>
void CHashTable<KeyType, ValueType>::Clear()
{
  TUint32 len = ((TUint32)1<<inLogSize);
  this->iStore->Reset();
  this->iFreeList->Reset();
  Mem::FillZ((TAny*)this->iTable, len * sizeof(hitem *));
  TUint32 i;
  // add all entries in the store to the free list
  for (i=0; i<len; ++i) {
	  this->iFreeList->AppendL(i);
  }
  this->inLogSize = inLogSize;
  this->inMask = len-1;
  this->inCount = 0;
  this->iAPos = (TUint32)0;
  this->iPos = (hitem *)0;
}

/* Delete - delete the item at the current position */
template<class KeyType, class ValueType>
TInt  CHashTable<KeyType, ValueType>::DeleteL()
{
  hitem  *h;    /* item being deleted */
  hitem **ip;   /* a counter */

  /* check for item not existing */
  h = this->iPos;
  if (!h) return FALSE;

  /* remove item from its list */
  for (ip = &this->iTable[this->iAPos]; *ip != h; ip = &(*ip)->next)
    ;
  *ip = (*ip)->next;
  --(this->inCount);

  /* adjust position to something that exists */
  this->iPos = h->next;
  if (!this->iPos) NextBucket();

  /* recycle the deleted hitem node */
  this->iFreeList->AppendL(h->spos);

#ifdef HSANITY
  Sanity();
#endif  /* HSANITY */
  if (this->iPos) {
      return TRUE;
  } else {
	  return FALSE;
  }
}

/* Find - find an item with a given key in a hash iTable */
template<class KeyType, class ValueType>
TInt   CHashTable<KeyType, ValueType>::Find(
	KeyType *key /* key to find */) 
{
  hitem *h;
  TUint32    x = Lookup(key,0);
  TUint32    y;
  for (h = this->iTable[y=(x&this->inMask)]; h; h = h->next)
  {
    if ((x == h->hval) && 
		!Mem::Compare((TUint8*)key, sizeof(KeyType), (TUint8*)h->key, sizeof(KeyType)))
    {
      this->iAPos = y;
      this->iPos = h;
      return TRUE;
    }
  }
  return FALSE;
}

/* First - position on the first element in the iTable */
template<class KeyType, class ValueType>
TInt CHashTable<KeyType, ValueType>::First()
{
  this->iAPos = this->inMask;
  (void)NextBucket();
  return (this->iPos != (hitem *)0);
}

// Next advances to next item in hash iTable
template<class KeyType, class ValueType>
TInt CHashTable<KeyType, ValueType>::Next()
{
	if (this->iPos) {
		this->iPos = this->iPos->next;
		if (this->iPos) { // chain not at end yet
			return TRUE;
		} else { // chain at end, go to next bucket
			return NextBucket();
		}
	} else { // at end
		return FALSE;
	}
};

/*
 * 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.
 */
template<class KeyType, class ValueType>
void CHashTable<KeyType, ValueType>::GrowL()
{
  TUint32     newsize = (TUint32)1<<(++this->inLogSize);
  TUint32     newmask = newsize-1;
  TUint32     i;
  hitem **oldtab = this->iTable;
  hitem **newtab = new (ELeave) hitem* [newsize];

  // note that the code below cannot leave, so we don't