1/****************************************************************************************
2
3 Copyright (C) 2015 Autodesk, Inc.
4 All rights reserved.
5
6 Use of this software is subject to the terms of the Autodesk license agreement
7 provided at the time of installation or download, or which otherwise accompanies
8 this software in either electronic or hard copy form.
9
10****************************************************************************************/
11
12//! \file fbxhashmap.h
13#ifndef _FBXSDK_CORE_BASE_HASHMAP_H_
14#define _FBXSDK_CORE_BASE_HASHMAP_H_
15
16#include <fbxsdk/fbxsdk_def.h>
17
18#include <fbxsdk/core/base/fbxarray.h>
19#include <fbxsdk/core/base/fbxmap.h>
20
21#include <fbxsdk/fbxsdk_nsbegin.h>
22
23template<class T> class FbxNoOpDestruct { public: static inline void DoIt(T&) {} };
24template<class T> class FbxPtrDestruct { public: static inline void DoIt(T& v) { FbxDelete(v); v = NULL; } };
25
26//True if equal, false otherwise
27template<class T> class FbxDefaultComparator{ public: static inline bool CompareIt( const T& t1, const T& t2 ) { return t1 == t2; } };
28
29/** \brief This object represents a standard hash map. You must provide the typename of KEY and VALUE as well
30 as the typename of the class that contains the hash function to use to hash values. The hash class must
31 overload operator() and be built like this.
32 \code
33 class SimpleHash
34 {
35 public:
36 inline unsigned int operator() ( const int pKey ) const
37 {
38 return pKey;
39 }
40 };
41 \endcode
42 * \nosubgrouping
43 */
44template< typename KEY, typename VALUE, typename HASH, class Destruct = FbxNoOpDestruct<VALUE>, class Comparator = FbxDefaultComparator<KEY> >
45class FbxHashMap
46{
47public:
48 typedef KEY KeyType;
49 typedef VALUE ValueType;
50 typedef HASH HashFunctorType;
51
52private:
53
54 class ListItem
55 {
56 public:
57 ListItem* mNext;
58 ValueType mValue;
59 KeyType mKey;
60
61 ListItem()
62 :
63 mNext(NULL)
64 {
65 }
66
67 ~ListItem()
68 {
69 Destruct::DoIt(mValue);
70 }
71 };
72
73public:
74 /**
75 Iterate through every element in a hash map.
76 */
77 class Iterator
78 {
79 public:
80
81 typedef ListItem ListItemType;
82 typedef FbxPair< KeyType, ValueType > KeyValuePair;
83
84 /**
85 Copy constructor
86 */
87 Iterator( const Iterator& pOther )
88 :
89 mMap( pOther.mMap ),
90 mBucketIndex( pOther.mBucketIndex ),
91 mCurrentItem( pOther.mCurrentItem )
92 {
93
94 }
95
96 /**
97 Destructor
98 */
99 ~Iterator(){};
100
101 /**
102 Used to dereference an iterator and give it a behavior more similar to a pointer.
103 \return The KeyValuePair currently referenced by the iterator
104 */
105 KeyValuePair operator*() const
106 {
107 KeyValuePair lItem;
108
109 if( mCurrentItem )
110 {
111 lItem.mFirst = mCurrentItem->mKey;
112 lItem.mSecond = mCurrentItem->mValue;
113 return lItem;
114 }
115
116 FBX_ASSERT_NOW("Accessing out of bounds iterator");
117
118 return lItem;
119 }
120
121 /**
122 Advances the iterator to the next keyvaluepair in the hashmap. It does not wrap around so
123 advancing after reaching the last element will not point back to the first one.
124 */
125 void Next()
126 {
127 if( !mCurrentItem )
128 return;
129
130 if( mCurrentItem->mNext )
131 {
132 mCurrentItem = mCurrentItem->mNext;
133 return;
134 }
135 else
136 {
137 mBucketIndex++;
138 for( ; mBucketIndex < mMap->mBuckets.GetCount(); ++mBucketIndex )
139 {
140 if( mMap->mBuckets[ mBucketIndex ] )
141 {
142 mCurrentItem = mMap->mBuckets[ mBucketIndex ];
143 return;
144 }
145 }
146
147 if( mBucketIndex >= mMap->mBuckets.GetCount() )
148 {
149 *this = mMap->End();
150 return;
151 }
152 }
153 }
154
155 /**
156 Check equivalence between two iterators. There are 3 conditions for equivalence between 2 iterators:
157 1) Item being referenced by the iterator must be equivalent
158 2) They must point at the same index
159 3) They must point on the same map
160 \return true if both iterators are equal, false otherwise
161 */
162 bool operator==( const Iterator& pOther ) const
163 {
164 return mCurrentItem == pOther.mCurrentItem &&
165 mBucketIndex == pOther.mBucketIndex &&
166 mMap == pOther.mMap;
167 }
168
169 /**
170 Check inequivalence between 2 iterators. Please see operator== for more information.
171 \return true if both iterators are NOT equal, false if they are
172 */
173 bool operator!=( const Iterator& pOther ) const
174 {
175 return !(*this == pOther);
176 }
177
178 /**
179 Assign the current iterator to the one on the right hand side of the operator. After assignment they will
180 reference the same object, at the same index, in the same map.
181 \return The new iterator
182 */
183 Iterator& operator=( const Iterator& pOther )
184 {
185 this->mBucketIndex = pOther.mBucketIndex;
186 this->mMap = pOther.mMap;
187 this->mCurrentItem = pOther.mCurrentItem;
188 return *this;
189 }
190
191 private:
192 const FbxHashMap* mMap;
193
194 int mBucketIndex;
195 ListItemType* mCurrentItem;
196
197 Iterator(const FbxHashMap* pMap, int pBucketIndex, ListItemType* pCurrentItem)
198 :
199 mMap( pMap ),
200 mBucketIndex(pBucketIndex),
201 mCurrentItem(pCurrentItem)
202 {
203
204 }
205
206 friend class FbxHashMap;
207 };
208
209 /**
210 Construct a FbxHashMap with an user-defined maximum number of elements.
211 \param pBucketSize Initial maximum number of elements.
212 */
213 FbxHashMap( int pBucketSize )
214 {
215 mBuckets.Resize( pBucketSize );
216 }
217
218 /**
219 Construct a FbxHashMap with the default maximum number of elements (30)
220 */
221 FbxHashMap()
222 {
223 mBuckets.Resize(30);
224 }
225
226 /**
227 Clear all elements in the hash map before destroying itself
228 */
229 ~FbxHashMap()
230 {
231 Clear();
232 mBuckets.Clear();
233 }
234
235 /**
236 Calls operator delete on all elements of the hashmap, de-allocating all memory and destroying them
237 */
238 void Clear()
239 {
240 for( int i = 0; i < mBuckets.GetCount(); ++i)
241 {
242 if( mBuckets[i] )
243 {
244 ListItem* lNext = mBuckets[i]->mNext;
245 while( lNext )
246 {
247 ListItem* lNextNext = lNext->mNext;
248 FbxDelete(lNext);
249 lNext = lNextNext;
250 }
251
252 FbxDelete(mBuckets[i]);
253 mBuckets[i] = NULL;
254 }
255 }
256 }
257
258 /**
259 Find an element in the hashmap. If no element exist with the specified key, returns an iterator pointing on the
260 end of the map (not an actual KeyValuePair).
261 \param pKey The value of the key corresponding to the element
262 \return An Iterator referencing that element
263 */
264 const Iterator Find( const KeyType& pKey ) const
265 {
266 unsigned int lIndex = mHashFunctor(pKey);
267 lIndex = lIndex % mBuckets.GetCount();
268 ListItem* lItem = mBuckets[lIndex];
269 while( lItem )
270 {
271 if( Comparator::CompareIt( lItem->mKey, pKey ) )
272 {
273 Iterator lIt( this, lIndex, lItem );
274 return lIt;
275 }
276 lItem = lItem->mNext;
277 }
278
279 return End();
280 }
281
282 /**
283 Remove an element in the hashmap.
284 \param pKey The key value of the element to remove
285 \return The value of the element that was just deleted. If the element does not exist, a value created with its default constructor will be returned
286 */
287 VALUE Remove( const KEY& pKey )
288 {
289 unsigned int lIndex = mHashFunctor(pKey);
290 lIndex = lIndex % mBuckets.GetCount();
291 ListItem* lItem = mBuckets.GetAt(lIndex);
292 ListItem* lLastItem = NULL;
293
294 while( lItem )
295 {
296 if( lItem->mKey == pKey )
297 {
298 if( lLastItem )
299 lLastItem->mNext = lItem->mNext;
300
301 if( mBuckets.GetAt(lIndex) == lItem )
302 mBuckets.SetAt(lIndex, lItem->mNext );
303
304 VALUE lValue = lItem->mValue;
305 FbxDelete(lItem);
306
307 return lValue;
308 }
309
310 lLastItem = lItem;
311 lItem = lItem->mNext;
312 }
313
314 return VALUE();
315 }
316
317 /** Add or retrieve a KeyValuePair from the Hashmap. If there is already an entry in the map for an element
318 with key value specified in parameter, the value will be returned. Otherwise, a new entry will be created
319 with this key value and the default value for ValueType will be returned. It can be modified using the
320 assignment operator
321 \param pKey The key for which to retrieve/add a value.
322 \return Value of the element referenced by the key specified in parameter.
323 */
324 ValueType& operator[]( const KeyType& pKey )
325 {
326 unsigned int lIndex = 0;
327 Iterator lIt = InternalFind( pKey, lIndex);
328 if( lIt != End() )
329 {
330 return lIt.mCurrentItem->mValue;
331 }
332
333 lIndex = lIndex % mBuckets.GetCount();
334 ListItem* lItem = FbxNew< ListItem >();
335 lItem->mNext = NULL;
336 lItem->mKey = pKey;
337
338 if( !mBuckets.GetAt(lIndex) )
339 {
340 mBuckets.SetAt(lIndex, lItem);
341 }
342 else
343 {
344 lItem->mNext = mBuckets.GetAt(lIndex);
345 mBuckets.SetAt(lIndex, lItem);
346 }
347
348 return lItem->mValue;
349 }
350
351 /** Returns an iterator pointing on the first non-null element in the map
352 \return An iterator pointing on the first non-null element in the map.
353 */
354 Iterator Start() const
355 {
356 for( int i = 0; i < mBuckets.GetCount(); ++i )
357 {
358 if( mBuckets[i] )
359 {
360 Iterator lIt( this, i, mBuckets[i] );
361 return lIt;
362 }
363 }
364
365 return End();
366 }
367
368 /** Returns an iterator pointing on the last element in the map. This is not an actual KeyValuePair but
369 * but an iterator pointing on a null element.
370 \return Iterator pointing on a null value at the end of the map
371 */
372 Iterator End() const
373 {
374 Iterator lIt( this, 0, NULL );
375 return lIt;
376 }
377
378private:
379
380 // Avoid calculating the hashvalue twice
381 const Iterator InternalFind( const KeyType& pKey, unsigned int& pOutCalculatedIndex ) const
382 {
383 pOutCalculatedIndex = mHashFunctor(pKey);
384 unsigned int lIndex = pOutCalculatedIndex % mBuckets.GetCount();
385 ListItem* lItem = mBuckets[lIndex];
386 while( lItem )
387 {
388 if( Comparator::CompareIt( lItem->mKey, pKey ) )
389 {
390 Iterator lIt( this, lIndex, lItem );
391 return lIt;
392 }
393 lItem = lItem->mNext;
394 }
395
396 return End();
397 }
398
399
400 // not implemented yet!
401 FbxHashMap( const FbxHashMap& pOther ) {};
402
403 FbxArray<ListItem*> mBuckets;
404 HashFunctorType mHashFunctor;
405
406 friend class Iterator;
407};
408
409#include <fbxsdk/fbxsdk_nsend.h>
410
411#endif /* _FBXSDK_CORE_BASE_HASHMAP_H_ */
412