Update contrib.
3 // This file holds the class methods for the CHashMap
4 // A hash function for hash table lookup. Assumes input data length is a multiple of 8-bits.
6 // The original hash function was sourced from http://burtleburtle.net/bob/hash/index.html
7 // "By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this code any way you wish,
8 // private, educational, or commercial. It's free."
9 // portions Copyright (c) 1995 - 2010 Nokia Corporation and/or its subsidiary(-ies).
14 CHashMap::CHashMap() :
15 iTableSize(sizeof(iHashTable)/sizeof(CSharedBitmapObject*)),
23 for (TInt i=0; i<iTableSize; i++)
25 __ASSERT_DEBUG(iHashTable[i]==NULL, User::Invariant());
30 /* This function inserts a pointer to the CSharedBitmapObject into the hashmap.
31 The hashmap does not acquire ownership of the CSharedBitmapObject.
32 The key used for insertion is a pre-existing member of the CSharedBitmapObject.
33 The caller must ensure the key does not already exist in the hashmap prior to calling this function.
35 @param aBmpObj The CSharedBitmapObject to insert.
36 @param aHash The hash of the key of the CSharedBitmapObject. This is provided for performance reasons explained in CFbTop::ShareBitmap.
39 void CHashMap::Insert(CSharedBitmapObject& aBmpObj, TUint aHash)
41 __ASSERT_DEBUG(aHash==Hash(*(aBmpObj.iKey)), User::Invariant()); // Verify the hash value
42 __ASSERT_DEBUG(!Lookup(*(aBmpObj.iKey), aHash), User::Invariant()); // Duplicate keys are not allowed
44 const TUint index = aHash & iMask;
46 // Insert aBmpObj at head of list
47 aBmpObj.iNext = iHashTable[index];
48 iHashTable[index] = &aBmpObj;
52 /* This function looks up a CSharedBitmapObject in the hashmap using a key.
53 Lookup is case sensitive.
55 @param aKey The key of the CSharedBitmapObject to be found.
56 @param aHash The hash of the key. This is provided for performance reasons explained in CFbTop::ShareBitmap.
57 @return A pointer to the CSharedBitmapObject if the key is found. NULL otherwise.
60 CSharedBitmapObject* CHashMap::Lookup(const TDesC& aKey, TUint aHash) const
62 const TUint index = aHash & iMask;
64 for (CSharedBitmapObject* n=iHashTable[index]; n!=NULL; n=n->iNext) // n walks the links of the linked list.
66 if (n->iKey->Length()==aKey.Length() && !n->iKey->Compare(aKey))
68 return n; // Key found
72 return NULL; // Key not found
76 /* Removes a specific object from the hashmap.
77 The object is discovered using its key and address.
78 This function does not destroy the object.
80 @param aBmpObj The specific CSharedBitmapObject to be removed.
81 @return KErrNone if the object is found and removed. An standard error otherwise.
84 TInt CHashMap::Remove(const CSharedBitmapObject& aBmpObj)
86 const TUint hash = Hash(*(aBmpObj.iKey));
87 const TUint index = hash & iMask;
89 for (CSharedBitmapObject** n=&iHashTable[index]; *n!=NULL; n=&((*n)->iNext)) // *n walks the links of the linked list.
93 *n = aBmpObj.iNext; // Key found. The link that was pointing to aBmpObj nows points to the successor of aBmpObj.
102 // Utility macro for the hash function
105 a -= b; a -= c; a ^= (c>>13); \
106 b -= c; b -= a; b ^= (a<<8); \
107 c -= a; c -= b; c ^= (b>>13); \
108 a -= b; a -= c; a ^= (c>>12); \
109 b -= c; b -= a; b ^= (a<<16); \
110 c -= a; c -= b; c ^= (b>>5); \
111 a -= b; a -= c; a ^= (c>>3); \
112 b -= c; b -= a; b ^= (a<<10); \
113 c -= a; c -= b; c ^= (b>>15); \
116 /* A hash function for hash table lookup.
117 Assumes input data length is a multiple of 8-bits.
119 The original hash function was sourced from
120 http://burtleburtle.net/bob/hash/index.html
121 "By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
122 code any way you wish, private, educational, or commercial. It's free."
124 TUint CHashMap::Hash(const TDesC8& aKey)
126 const TUint8* k = aKey.Ptr();
127 const TUint length = aKey.Length();
128 const TUint initval = 0;
131 TUint a = 0x9e3779b9;
132 TUint b = 0x9e3779b9;
137 a += (k[0] + ((TUint)k[1]<<8) + ((TUint)k[2] <<16) + ((TUint)k[3] <<24));
138 b += (k[4] + ((TUint)k[5]<<8) + ((TUint)k[6] <<16) + ((TUint)k[7] <<24));
139 c += (k[8] + ((TUint)k[9]<<8) + ((TUint)k[10]<<16) + ((TUint)k[11]<<24));
147 case 11: c+=((TUint)k[10]<<24);
148 case 10: c+=((TUint)k[9]<<16);
149 case 9 : c+=((TUint)k[8]<<8);
150 // the first byte of c is reserved for the length
151 case 8 : b+=((TUint)k[7]<<24);
152 case 7 : b+=((TUint)k[6]<<16);
153 case 6 : b+=((TUint)k[5]<<8);
155 case 4 : a+=((TUint)k[3]<<24);
156 case 3 : a+=((TUint)k[2]<<16);
157 case 2 : a+=((TUint)k[1]<<8);
159 // case 0: nothing left to add
169 /* A hash function for hash table lookup.
170 Assumes input data length is a multiple of 16-bits.
171 @param aKey The data to be hashed
172 @return The hash value
175 TUint CHashMap::Hash(const TDesC16& aKey)
177 const TUint16* k = aKey.Ptr();
178 const TUint length = aKey.Length();
179 const TUint initval = 0;
182 TUint a = 0x9e3779b9;
183 TUint b = 0x9e3779b9;
188 a += (k[0] + ((TUint)k[1]<<16));
189 b += (k[2] + ((TUint)k[3]<<16));
190 c += (k[4] + ((TUint)k[5]<<16));
198 case 5 : c+=((TUint)k[4]<<16);
199 // the first byte of c is reserved for the length
200 case 4 : b+=((TUint)k[3]<<16);
202 case 2 : a+=((TUint)k[1]<<16);
204 // case 0: nothing left to add