--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fbs/fontandbitmapserver/sfbs/HASHMAP.CPP	Tue Feb 02 01:47:50 2010 +0200
@@ -0,0 +1,226 @@
+// 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;
+	}