- Main Page
- Classes
- Files
- Directories

- File List
- File Members

# fbxhashmap.h

Go to the documentation of this file.

    00001 /****************************************************************************************
    00002
    00003    Copyright (C) 2013 Autodesk, Inc.
    00004    All rights reserved.
    00005
    00006    Use of this software is subject to the terms of the Autodesk license agreement
    00007    provided at the time of installation or download, or which otherwise accompanies
    00008    this software in either electronic or hard copy form.
    00009
    00010 ****************************************************************************************/
    00011
    00013 #ifndef _FBXSDK_CORE_BASE_HASHMAP_H_
    00014 #define _FBXSDK_CORE_BASE_HASHMAP_H_
    00015
    00016 #include <fbxsdk/fbxsdk_def.h>
    00017
    00018 #include <fbxsdk/core/base/fbxarray.h>
    00019 #include <fbxsdk/core/base/fbxmap.h>
    00020
    00021 #include <fbxsdk/fbxsdk_nsbegin.h>
    00022
    00023 template<class T> class FbxNoOpDestruct { public: static inline void DoIt(T&) {} };
    00024 template<class T> class FbxPtrDestruct  { public: static inline void DoIt(T& v) { FbxDelete(v); v = NULL; } };
    00025
    00026 //True if equal, false otherwise
    00027 template<class T> class FbxDefaultComparator{ public: static inline bool CompareIt( const T& t1, const T& t2 ) { return t1 == t2; } };
    00028
    00044 template< typename KEY, typename VALUE, typename HASH, class Destruct = FbxNoOpDestruct<VALUE>, class Comparator = FbxDefaultComparator<KEY> >
    00045 class FbxHashMap
    00046 {
    00047 public:
    00048     typedef KEY KeyType;
    00049     typedef VALUE ValueType;
    00050     typedef HASH HashFunctorType;
    00051
    00052 private:
    00053
    00054     class ListItem
    00055     {
    00056     public:
    00057         ListItem* mNext;
    00058         ValueType mValue;
    00059         KeyType mKey;
    00060
    00061         ListItem()
    00062             :
    00063         mNext(NULL)
    00064         {
    00065         }
    00066
    00067         ~ListItem()
    00068         {
    00069             Destruct::DoIt(mValue);
    00070         }
    00071     };
    00072
    00073 public:
    00077     class Iterator
    00078     {
    00079     public:
    00080
    00081         typedef ListItem ListItemType;
    00082         typedef FbxPair< KeyType, ValueType > KeyValuePair;
    00083
    00087         Iterator( const Iterator& pOther )
    00088             :
    00089             mMap( pOther.mMap ),
    00090             mBucketIndex( pOther.mBucketIndex ),
    00091             mCurrentItem( pOther.mCurrentItem )
    00092         {
    00093
    00094         }
    00095
    00099         ~Iterator(){};
    00100
    00105         KeyValuePair operator*() const
    00106         {
    00107             KeyValuePair lItem;
    00108
    00109             if( mCurrentItem )
    00110             {
    00111                 lItem.mFirst = mCurrentItem->mKey;
    00112                 lItem.mSecond = mCurrentItem->mValue;
    00113                 return lItem;
    00114             }
    00115
    00116             FBX_ASSERT_NOW("Accessing out of bounds iterator");
    00117
    00118             return lItem;
    00119         }
    00120
    00125         void Next()
    00126         {
    00127             if( !mCurrentItem )
    00128                 return;
    00129
    00130             if( mCurrentItem->mNext )
    00131             {
    00132                 mCurrentItem = mCurrentItem->mNext;
    00133                 return;
    00134             }
    00135             else
    00136             {
    00137                 mBucketIndex++;
    00138                 for( ; mBucketIndex < mMap->mBuckets.GetCount(); ++mBucketIndex )
    00139                 {
    00140                     if( mMap->mBuckets[ mBucketIndex ] )
    00141                     {
    00142                         mCurrentItem = mMap->mBuckets[ mBucketIndex ];
    00143                         return;
    00144                     }
    00145                 }
    00146
    00147                 if( mBucketIndex >= mMap->mBuckets.GetCount() )
    00148                 {
    00149                     *this = mMap->End();
    00150                     return;
    00151                 }
    00152             }
    00153         }
    00154
    00162         bool operator==( const Iterator& pOther ) const
    00163         {
    00164             return  mCurrentItem == pOther.mCurrentItem &&
    00165                     mBucketIndex == pOther.mBucketIndex &&
    00166                     mMap == pOther.mMap;
    00167         }
    00168
    00173         bool operator!=( const Iterator& pOther ) const
    00174         {
    00175             return !(*this == pOther);
    00176         }
    00177
    00183         Iterator& operator=( const Iterator& pOther )
    00184         {
    00185             this->mBucketIndex = pOther.mBucketIndex;
    00186             this->mMap = pOther.mMap;
    00187             this->mCurrentItem = pOther.mCurrentItem;
    00188             return *this;
    00189         }
    00190
    00191     private:
    00192         const FbxHashMap* mMap;
    00193
    00194         int mBucketIndex;
    00195         ListItemType* mCurrentItem;
    00196
    00197         Iterator(const FbxHashMap* pMap, int pBucketIndex, ListItemType* pCurrentItem)
    00198             :
    00199             mMap( pMap ),
    00200             mBucketIndex(pBucketIndex),
    00201             mCurrentItem(pCurrentItem)
    00202         {
    00203
    00204         }
    00205
    00206         friend class FbxHashMap;
    00207     };
    00208
    00213     FbxHashMap( int pBucketSize )
    00214     {
    00215         mBuckets.Resize( pBucketSize );
    00216     }
    00217
    00221     FbxHashMap()
    00222     {
    00223         mBuckets.Resize(30);
    00224     }
    00225
    00229     ~FbxHashMap()
    00230     {
    00231         Clear();
    00232         mBuckets.Clear();
    00233     }
    00234
    00238     void Clear()
    00239     {
    00240         for( int i = 0; i < mBuckets.GetCount(); ++i)
    00241         {
    00242             if( mBuckets[i] )
    00243             {
    00244                 ListItem* lNext = mBuckets[i]->mNext;
    00245                 while( lNext )
    00246                 {
    00247                     ListItem* lNextNext = lNext->mNext;
    00248                     FbxDelete(lNext);
    00249                     lNext = lNextNext;
    00250                 }
    00251
    00252                 FbxDelete(mBuckets[i]);
    00253                 mBuckets[i] = NULL;
    00254             }
    00255         }
    00256     }
    00257
    00264     const Iterator Find( const KeyType& pKey ) const
    00265     {
    00266         unsigned int lIndex = mHashFunctor(pKey);
    00267         lIndex = lIndex % mBuckets.GetCount();
    00268         ListItem* lItem = mBuckets[lIndex];
    00269         while( lItem )
    00270         {
    00271             if( Comparator::CompareIt( lItem->mKey, pKey ) )
    00272             {
    00273                 Iterator lIt( this, lIndex, lItem );
    00274                 return lIt;
    00275             }
    00276             lItem = lItem->mNext;
    00277         }
    00278
    00279         return End();
    00280     }
    00281
    00287     VALUE Remove( const KEY& pKey )
    00288     {
    00289         unsigned int lIndex = mHashFunctor(pKey);
    00290         lIndex = lIndex % mBuckets.GetCount();
    00291         ListItem* lItem = mBuckets.GetAt(lIndex);
    00292         ListItem* lLastItem = NULL;
    00293
    00294         while( lItem )
    00295         {
    00296             if( lItem->mKey == pKey )
    00297             {
    00298                 if( lLastItem )
    00299                     lLastItem->mNext = lItem->mNext;
    00300
    00301                 if( mBuckets.GetAt(lIndex) == lItem )
    00302                     mBuckets.SetAt(lIndex, lItem->mNext );
    00303
    00304                 VALUE lValue = lItem->mValue;
    00305                 FbxDelete(lItem);
    00306
    00307                 return lValue;
    00308             }
    00309
    00310             lLastItem = lItem;
    00311             lItem = lItem->mNext;
    00312         }
    00313
    00314         return VALUE();
    00315     }
    00316
    00324     ValueType& operator[]( const KeyType& pKey )
    00325     {
    00326         unsigned int lIndex = 0;
    00327         Iterator lIt = InternalFind( pKey, lIndex);
    00328         if( lIt != End() )
    00329         {
    00330             return lIt.mCurrentItem->mValue;
    00331         }
    00332
    00333         lIndex = lIndex % mBuckets.GetCount();
    00334         ListItem* lItem = FbxNew< ListItem >();
    00335         lItem->mNext = NULL;
    00336         lItem->mKey = pKey;
    00337
    00338         if( !mBuckets.GetAt(lIndex) )
    00339         {
    00340             mBuckets.SetAt(lIndex, lItem);
    00341         }
    00342         else
    00343         {
    00344             lItem->mNext = mBuckets.GetAt(lIndex);
    00345             mBuckets.SetAt(lIndex, lItem);
    00346         }
    00347
    00348         return lItem->mValue;
    00349     }
    00350
    00354     Iterator Start() const
    00355     {
    00356         for( int i = 0; i < mBuckets.GetCount(); ++i )
    00357         {
    00358             if( mBuckets[i] )
    00359             {
    00360                 Iterator lIt( this, i, mBuckets[i] );
    00361                 return lIt;
    00362             }
    00363         }
    00364
    00365         return End();
    00366     }
    00367
    00372     Iterator End() const
    00373     {
    00374         Iterator lIt( this, 0, NULL );
    00375         return lIt;
    00376     }
    00377
    00378 private:
    00379
    00380     // Avoid calculating the hashvalue twice
    00381     const Iterator InternalFind( const KeyType& pKey, unsigned int& pOutCalculatedIndex ) const
    00382     {
    00383         pOutCalculatedIndex = mHashFunctor(pKey);
    00384         unsigned int lIndex = pOutCalculatedIndex % mBuckets.GetCount();
    00385         ListItem* lItem = mBuckets[lIndex];
    00386         while( lItem )
    00387         {
    00388             if( Comparator::CompareIt( lItem->mKey, pKey ) )
    00389             {
    00390                 Iterator lIt( this, lIndex, lItem );
    00391                 return lIt;
    00392             }
    00393             lItem = lItem->mNext;
    00394         }
    00395
    00396         return End();
    00397     }
    00398
    00399
    00400     // not implemented yet!
    00401     FbxHashMap( const FbxHashMap& pOther ) {};
    00402
    00403     FbxArray<ListItem*> mBuckets;
    00404     HashFunctorType mHashFunctor;
    00405
    00406     friend class Iterator;
    00407 };
    00408
    00409 #include <fbxsdk/fbxsdk_nsend.h>
    00410
    00411 #endif /* _FBXSDK_CORE_BASE_HASHMAP_H_ */