// Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies).
// All rights reserved.
// This component and the accompanying materials are made available
// under the terms of "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:
// 
// 
//

// HASHMAP.CPP
//
// This file holds the class methods for the CHashMap
// A hash function for hash table lookup.  Assumes input data length is a multiple of 8-bits.
// 
// The original hash function was sourced from http://burtleburtle.net/bob/hash/index.html
// "By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this code any way you wish, 
// private, educational, or commercial.  It's free."
//  portions Copyright (c) 1995 - 2009 Nokia Corporation. All rights reserved.
//

#include "SERVER.H"

CHashMap::CHashMap() :
	iTableSize(sizeof(iHashTable)/sizeof(CSharedBitmapObject*)),
	iMask(iTableSize-1)
	{
	}
	

CHashMap::~CHashMap()
	{
	for (TInt i=0; i<iTableSize; i++)
		{
		__ASSERT_DEBUG(iHashTable[i]==NULL, User::Invariant());
		}
	}


/* This function inserts a pointer to the CSharedBitmapObject into the hashmap.
The hashmap does not acquire ownership of the CSharedBitmapObject.
The key used for insertion is a pre-existing member of the CSharedBitmapObject.
The caller must ensure the key does not already exist in the hashmap prior to calling this function.

@param aBmpObj The CSharedBitmapObject to insert.
@param aHash The hash of the key of the CSharedBitmapObject.  This is provided for performance reasons explained in CFbTop::ShareBitmap.
@internalComponent
*/
void CHashMap::Insert(CSharedBitmapObject& aBmpObj, TUint aHash)
	{
	__ASSERT_DEBUG(aHash==Hash(*(aBmpObj.iKey)), User::Invariant());     // Verify the hash value
	__ASSERT_DEBUG(!Lookup(*(aBmpObj.iKey), aHash), User::Invariant());  // Duplicate keys are not allowed
	
	const TUint index = aHash & iMask;

	// Insert aBmpObj at head of list
	aBmpObj.iNext = iHashTable[index];
	iHashTable[index] = &aBmpObj;
	}


/* This function looks up a CSharedBitmapObject in the hashmap using a key.
Lookup is case sensitive.

@param aKey The key of the CSharedBitmapObject to be found.
@param aHash The hash of the key.  This is provided for performance reasons explained in CFbTop::ShareBitmap.
@return A pointer to the CSharedBitmapObject if the key is found.  NULL otherwise.
@internalComponent
*/
CSharedBitmapObject* CHashMap::Lookup(const TDesC& aKey, TUint aHash) const
	{
	const TUint index = aHash & iMask;

	for (CSharedBitmapObject* n=iHashTable[index]; n!=NULL; n=n->iNext) // n walks the links of the linked list.
		{
		if (n->iKey->Length()==aKey.Length() && !n->iKey->Compare(aKey))
			{
			return n;  // Key found
			}
		}

	return NULL;   // Key not found
	}


/* Removes a specific object from the hashmap.
The object is discovered using its key and address.
This function does not destroy the object.

@param aBmpObj The specific CSharedBitmapObject to be removed.
@return KErrNone if the object is found and removed.  An standard error otherwise.
@internalComponent
*/
TInt CHashMap::Remove(const CSharedBitmapObject& aBmpObj)
	{
	const TUint hash = Hash(*(aBmpObj.iKey));
	const TUint index = hash & iMask;

	for (CSharedBitmapObject** n=&iHashTable[index]; *n!=NULL; n=&((*n)->iNext))  // *n walks the links of the linked list.
		{
		if (&aBmpObj==*n)
			{
			*n = aBmpObj.iNext;  // Key found.  The link that was pointing to aBmpObj nows points to the successor of aBmpObj.
			return KErrNone;
			}	
		}

	return KErrNotFound;
	}


// Utility macro for the hash function
#define mix(a,b,c) \
{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<<8);  \
  c -= a; c -= b; c ^= (b>>13); \
  a -= b; a -= c; a ^= (c>>12); \
  b -= c; b -= a; b ^= (a<<16); \
  c -= a; c -= b; c ^= (b>>5);  \
  a -= b; a -= c; a ^= (c>>3);  \
  b -= c; b -= a; b ^= (a<<10); \
  c -= a; c -= b; c ^= (b>>15); \
}

/* A hash function for hash table lookup.
Assumes input data length is a multiple of 8-bits.

The original hash function was sourced from
http://burtleburtle.net/bob/hash/index.html
"By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
code any way you wish, private, educational, or commercial.  It's free."

TUint CHashMap::Hash(const TDesC8& aKey)
	{
	const TUint8* k = aKey.Ptr();
	const TUint length = aKey.Length();
	const TUint initval = 0;

	TUint len = length;
	TUint a = 0x9e3779b9;
	TUint b = 0x9e3779b9;
	TUint c = initval;

	while (len >= 12)
		{
		a += (k[0] + ((TUint)k[1]<<8) + ((TUint)k[2] <<16) + ((TUint)k[3] <<24));
		b += (k[4] + ((TUint)k[5]<<8) + ((TUint)k[6] <<16) + ((TUint)k[7] <<24));
		c += (k[8] + ((TUint)k[9]<<8) + ((TUint)k[10]<<16) + ((TUint)k[11]<<24));
		mix(a,b,c);
		k += 12; len -= 12;
		}

	c += length;
	switch(len)
		{
		case 11: c+=((TUint)k[10]<<24);
		case 10: c+=((TUint)k[9]<<16);
		case 9 : c+=((TUint)k[8]<<8);
      // the first byte of c is reserved for the length
		case 8 : b+=((TUint)k[7]<<24);
		case 7 : b+=((TUint)k[6]<<16);
		case 6 : b+=((TUint)k[5]<<8);
		case 5 : b+=k[4];
		case 4 : a+=((TUint)k[3]<<24);
		case 3 : a+=((TUint)k[2]<<16);
		case 2 : a+=((TUint)k[1]<<8);
		case 1 : a+=k[0];
     // case 0: nothing left to add
		}
	mix(a,b,c);

	return c;
	}
	
*/


/* A hash function for hash table lookup.
Assumes input data length is a multiple of 16-bits.
@param aKey The data to be hashed
@return The hash value
@internalComponent
*/
TUint CHashMap::Hash(const TDesC16& aKey)
	{
	const TUint16* k = aKey.Ptr();
	const TUint length = aKey.Length();
	const TUint initval = 0;

	TUint len = length;
	TUint a = 0x9e3779b9;
	TUint b = 0x9e3779b9;
	TUint c = initval;

	while (len >= 6)
		{
		a += (k[0] + ((TUint)k[1]<<16));
		b += (k[2] + ((TUint)k[3]<<16));
		c += (k[4] + ((TUint)k[5]<<16));
		mix(a,b,c);
		k += 6; len -= 6;
		}

	c += length;
	switch(len)
		{
		case 5 : c+=((TUint)k[4]<<16);
      // the first byte of c is reserved for the length
		case 4 : b+=((TUint)k[3]<<16);
		case 3 : b+=k[2];
		case 2 : a+=((TUint)k[1]<<16);
		case 1 : a+=k[0];
     // case 0: nothing left to add
		}
	mix(a,b,c);

	return c;
	}