|
1 // Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
2 // All rights reserved. |
|
3 // This component and the accompanying materials are made available |
|
4 // under the terms of "Eclipse Public License v1.0" |
|
5 // which accompanies this distribution, and is available |
|
6 // at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
7 // |
|
8 // Initial Contributors: |
|
9 // Nokia Corporation - initial contribution. |
|
10 // |
|
11 // Contributors: |
|
12 // |
|
13 // Description: |
|
14 // |
|
15 // |
|
16 // |
|
17 |
|
18 // HASHMAP.CPP |
|
19 // |
|
20 // This file holds the class methods for the CHashMap |
|
21 // A hash function for hash table lookup. Assumes input data length is a multiple of 8-bits. |
|
22 // |
|
23 // The original hash function was sourced from http://burtleburtle.net/bob/hash/index.html |
|
24 // "By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this code any way you wish, |
|
25 // private, educational, or commercial. It's free." |
|
26 // portions Copyright (c) 1995 - 2009 Nokia Corporation. All rights reserved. |
|
27 // |
|
28 |
|
29 #include "SERVER.H" |
|
30 |
|
31 CHashMap::CHashMap() : |
|
32 iTableSize(sizeof(iHashTable)/sizeof(CSharedBitmapObject*)), |
|
33 iMask(iTableSize-1) |
|
34 { |
|
35 } |
|
36 |
|
37 |
|
38 CHashMap::~CHashMap() |
|
39 { |
|
40 for (TInt i=0; i<iTableSize; i++) |
|
41 { |
|
42 __ASSERT_DEBUG(iHashTable[i]==NULL, User::Invariant()); |
|
43 } |
|
44 } |
|
45 |
|
46 |
|
47 /* This function inserts a pointer to the CSharedBitmapObject into the hashmap. |
|
48 The hashmap does not acquire ownership of the CSharedBitmapObject. |
|
49 The key used for insertion is a pre-existing member of the CSharedBitmapObject. |
|
50 The caller must ensure the key does not already exist in the hashmap prior to calling this function. |
|
51 |
|
52 @param aBmpObj The CSharedBitmapObject to insert. |
|
53 @param aHash The hash of the key of the CSharedBitmapObject. This is provided for performance reasons explained in CFbTop::ShareBitmap. |
|
54 @internalComponent |
|
55 */ |
|
56 void CHashMap::Insert(CSharedBitmapObject& aBmpObj, TUint aHash) |
|
57 { |
|
58 __ASSERT_DEBUG(aHash==Hash(*(aBmpObj.iKey)), User::Invariant()); // Verify the hash value |
|
59 __ASSERT_DEBUG(!Lookup(*(aBmpObj.iKey), aHash), User::Invariant()); // Duplicate keys are not allowed |
|
60 |
|
61 const TUint index = aHash & iMask; |
|
62 |
|
63 // Insert aBmpObj at head of list |
|
64 aBmpObj.iNext = iHashTable[index]; |
|
65 iHashTable[index] = &aBmpObj; |
|
66 } |
|
67 |
|
68 |
|
69 /* This function looks up a CSharedBitmapObject in the hashmap using a key. |
|
70 Lookup is case sensitive. |
|
71 |
|
72 @param aKey The key of the CSharedBitmapObject to be found. |
|
73 @param aHash The hash of the key. This is provided for performance reasons explained in CFbTop::ShareBitmap. |
|
74 @return A pointer to the CSharedBitmapObject if the key is found. NULL otherwise. |
|
75 @internalComponent |
|
76 */ |
|
77 CSharedBitmapObject* CHashMap::Lookup(const TDesC& aKey, TUint aHash) const |
|
78 { |
|
79 const TUint index = aHash & iMask; |
|
80 |
|
81 for (CSharedBitmapObject* n=iHashTable[index]; n!=NULL; n=n->iNext) // n walks the links of the linked list. |
|
82 { |
|
83 if (n->iKey->Length()==aKey.Length() && !n->iKey->Compare(aKey)) |
|
84 { |
|
85 return n; // Key found |
|
86 } |
|
87 } |
|
88 |
|
89 return NULL; // Key not found |
|
90 } |
|
91 |
|
92 |
|
93 /* Removes a specific object from the hashmap. |
|
94 The object is discovered using its key and address. |
|
95 This function does not destroy the object. |
|
96 |
|
97 @param aBmpObj The specific CSharedBitmapObject to be removed. |
|
98 @return KErrNone if the object is found and removed. An standard error otherwise. |
|
99 @internalComponent |
|
100 */ |
|
101 TInt CHashMap::Remove(const CSharedBitmapObject& aBmpObj) |
|
102 { |
|
103 const TUint hash = Hash(*(aBmpObj.iKey)); |
|
104 const TUint index = hash & iMask; |
|
105 |
|
106 for (CSharedBitmapObject** n=&iHashTable[index]; *n!=NULL; n=&((*n)->iNext)) // *n walks the links of the linked list. |
|
107 { |
|
108 if (&aBmpObj==*n) |
|
109 { |
|
110 *n = aBmpObj.iNext; // Key found. The link that was pointing to aBmpObj nows points to the successor of aBmpObj. |
|
111 return KErrNone; |
|
112 } |
|
113 } |
|
114 |
|
115 return KErrNotFound; |
|
116 } |
|
117 |
|
118 |
|
119 // Utility macro for the hash function |
|
120 #define mix(a,b,c) \ |
|
121 { \ |
|
122 a -= b; a -= c; a ^= (c>>13); \ |
|
123 b -= c; b -= a; b ^= (a<<8); \ |
|
124 c -= a; c -= b; c ^= (b>>13); \ |
|
125 a -= b; a -= c; a ^= (c>>12); \ |
|
126 b -= c; b -= a; b ^= (a<<16); \ |
|
127 c -= a; c -= b; c ^= (b>>5); \ |
|
128 a -= b; a -= c; a ^= (c>>3); \ |
|
129 b -= c; b -= a; b ^= (a<<10); \ |
|
130 c -= a; c -= b; c ^= (b>>15); \ |
|
131 } |
|
132 |
|
133 /* A hash function for hash table lookup. |
|
134 Assumes input data length is a multiple of 8-bits. |
|
135 |
|
136 The original hash function was sourced from |
|
137 http://burtleburtle.net/bob/hash/index.html |
|
138 "By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this |
|
139 code any way you wish, private, educational, or commercial. It's free." |
|
140 |
|
141 TUint CHashMap::Hash(const TDesC8& aKey) |
|
142 { |
|
143 const TUint8* k = aKey.Ptr(); |
|
144 const TUint length = aKey.Length(); |
|
145 const TUint initval = 0; |
|
146 |
|
147 TUint len = length; |
|
148 TUint a = 0x9e3779b9; |
|
149 TUint b = 0x9e3779b9; |
|
150 TUint c = initval; |
|
151 |
|
152 while (len >= 12) |
|
153 { |
|
154 a += (k[0] + ((TUint)k[1]<<8) + ((TUint)k[2] <<16) + ((TUint)k[3] <<24)); |
|
155 b += (k[4] + ((TUint)k[5]<<8) + ((TUint)k[6] <<16) + ((TUint)k[7] <<24)); |
|
156 c += (k[8] + ((TUint)k[9]<<8) + ((TUint)k[10]<<16) + ((TUint)k[11]<<24)); |
|
157 mix(a,b,c); |
|
158 k += 12; len -= 12; |
|
159 } |
|
160 |
|
161 c += length; |
|
162 switch(len) |
|
163 { |
|
164 case 11: c+=((TUint)k[10]<<24); |
|
165 case 10: c+=((TUint)k[9]<<16); |
|
166 case 9 : c+=((TUint)k[8]<<8); |
|
167 // the first byte of c is reserved for the length |
|
168 case 8 : b+=((TUint)k[7]<<24); |
|
169 case 7 : b+=((TUint)k[6]<<16); |
|
170 case 6 : b+=((TUint)k[5]<<8); |
|
171 case 5 : b+=k[4]; |
|
172 case 4 : a+=((TUint)k[3]<<24); |
|
173 case 3 : a+=((TUint)k[2]<<16); |
|
174 case 2 : a+=((TUint)k[1]<<8); |
|
175 case 1 : a+=k[0]; |
|
176 // case 0: nothing left to add |
|
177 } |
|
178 mix(a,b,c); |
|
179 |
|
180 return c; |
|
181 } |
|
182 |
|
183 */ |
|
184 |
|
185 |
|
186 /* A hash function for hash table lookup. |
|
187 Assumes input data length is a multiple of 16-bits. |
|
188 @param aKey The data to be hashed |
|
189 @return The hash value |
|
190 @internalComponent |
|
191 */ |
|
192 TUint CHashMap::Hash(const TDesC16& aKey) |
|
193 { |
|
194 const TUint16* k = aKey.Ptr(); |
|
195 const TUint length = aKey.Length(); |
|
196 const TUint initval = 0; |
|
197 |
|
198 TUint len = length; |
|
199 TUint a = 0x9e3779b9; |
|
200 TUint b = 0x9e3779b9; |
|
201 TUint c = initval; |
|
202 |
|
203 while (len >= 6) |
|
204 { |
|
205 a += (k[0] + ((TUint)k[1]<<16)); |
|
206 b += (k[2] + ((TUint)k[3]<<16)); |
|
207 c += (k[4] + ((TUint)k[5]<<16)); |
|
208 mix(a,b,c); |
|
209 k += 6; len -= 6; |
|
210 } |
|
211 |
|
212 c += length; |
|
213 switch(len) |
|
214 { |
|
215 case 5 : c+=((TUint)k[4]<<16); |
|
216 // the first byte of c is reserved for the length |
|
217 case 4 : b+=((TUint)k[3]<<16); |
|
218 case 3 : b+=k[2]; |
|
219 case 2 : a+=((TUint)k[1]<<16); |
|
220 case 1 : a+=k[0]; |
|
221 // case 0: nothing left to add |
|
222 } |
|
223 mix(a,b,c); |
|
224 |
|
225 return c; |
|
226 } |