- Main Page
- Classes
- Files
- Directories
- Examples

- File List
- File Members

# fbxhashmap.h

Go to the documentation of this file.

    00001 /****************************************************************************************
    00002
    00003    Copyright (C) 2012 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
    00029 template< typename KEY, typename VALUE, typename HASH, class Destruct = FbxNoOpDestruct<VALUE>, class Comparator = FbxDefaultComparator<KEY> >
    00030 class FbxHashMap
    00031 {
    00032 public:
    00033     typedef KEY KeyType;
    00034     typedef VALUE ValueType;
    00035     typedef HASH HashFunctorType;
    00036
    00037 private:
    00038
    00039     class ListItem
    00040     {
    00041     public:
    00042         ListItem* mNext;
    00043         ValueType mValue;
    00044         KeyType mKey;
    00045
    00046         ListItem()
    00047             :
    00048         mNext(NULL)
    00049         {
    00050         }
    00051
    00052         ~ListItem()
    00053         {
    00054             Destruct::DoIt(mValue);
    00055         }
    00056     };
    00057
    00058 public:
    00059
    00060     class Iterator
    00061     {
    00062     public:
    00063
    00064         typedef ListItem ListItemType;
    00065         typedef FbxPair< KeyType, ValueType > KeyValuePair;
    00066
    00067         Iterator( const Iterator& pOther )
    00068             :
    00069             mMap( pOther.mMap ),
    00070             mBucketIndex( pOther.mBucketIndex ),
    00071             mCurrentItem( pOther.mCurrentItem )
    00072         {
    00073
    00074         }
    00075
    00076         ~Iterator(){};
    00077
    00078         KeyValuePair operator*() const
    00079         {
    00080             KeyValuePair lItem;
    00081
    00082             if( mCurrentItem )
    00083             {
    00084                 lItem.mFirst = mCurrentItem->mKey;
    00085                 lItem.mSecond = mCurrentItem->mValue;
    00086                 return lItem;
    00087             }
    00088
    00089             FBX_ASSERT_NOW("Accessing out of bounds iterator");
    00090
    00091             return lItem;
    00092         }
    00093
    00094         void Next()
    00095         {
    00096             if( !mCurrentItem )
    00097                 return;
    00098
    00099             if( mCurrentItem->mNext )
    00100             {
    00101                 mCurrentItem = mCurrentItem->mNext;
    00102                 return;
    00103             }
    00104             else
    00105             {
    00106                 mBucketIndex++;
    00107                 for( ; mBucketIndex < mMap->mBuckets.GetCount(); ++mBucketIndex )
    00108                 {
    00109                     if( mMap->mBuckets[ mBucketIndex ] )
    00110                     {
    00111                         mCurrentItem = mMap->mBuckets[ mBucketIndex ];
    00112                         return;
    00113                     }
    00114                 }
    00115
    00116                 if( mBucketIndex >= mMap->mBuckets.GetCount() )
    00117                 {
    00118                     *this = mMap->End();
    00119                     return;
    00120                 }
    00121             }
    00122         }
    00123
    00124         bool operator==( const Iterator& pOther ) const
    00125         {
    00126             return  mCurrentItem == pOther.mCurrentItem &&
    00127                     mBucketIndex == pOther.mBucketIndex &&
    00128                     mMap == pOther.mMap;
    00129         }
    00130
    00131         bool operator!=( const Iterator& pOther ) const
    00132         {
    00133             return !(*this == pOther);
    00134         }
    00135
    00136
    00137         Iterator& operator=( const Iterator& pOther )
    00138         {
    00139             this->mBucketIndex = pOther.mBucketIndex;
    00140             this->mMap = pOther.mMap;
    00141             this->mCurrentItem = pOther.mCurrentItem;
    00142             return *this;
    00143         }
    00144
    00145     private:
    00146         const FbxHashMap* mMap;
    00147
    00148         int mBucketIndex;
    00149         ListItemType* mCurrentItem;
    00150
    00151         Iterator(const FbxHashMap* pMap, int pBucketIndex, ListItemType* pCurrentItem)
    00152             :
    00153             mMap( pMap ),
    00154             mBucketIndex(pBucketIndex),
    00155             mCurrentItem(pCurrentItem)
    00156         {
    00157
    00158         }
    00159
    00160         friend class FbxHashMap;
    00161     };
    00162
    00163
    00164     FbxHashMap( int pBucketSize )
    00165     {
    00166         mBuckets.Resize( pBucketSize );
    00167     }
    00168
    00169     FbxHashMap()
    00170     {
    00171         mBuckets.Resize(30);
    00172     }
    00173
    00174     ~FbxHashMap()
    00175     {
    00176         Clear();
    00177         mBuckets.Resize(0);
    00178     }
    00179
    00180     void Clear()
    00181     {
    00182         for( int i = 0; i < mBuckets.GetCount(); ++i)
    00183         {
    00184             if( mBuckets[i] )
    00185             {
    00186                 ListItem* lNext = mBuckets[i]->mNext;
    00187                 while( lNext )
    00188                 {
    00189                     ListItem* lNextNext = lNext->mNext;
    00190                     FbxDelete(lNext);
    00191                     lNext = lNextNext;
    00192                 }
    00193
    00194                 FbxDelete(mBuckets[i]);
    00195                 mBuckets[i] = NULL;
    00196             }
    00197         }
    00198     }
    00199
    00200     const Iterator Find( const KeyType& pKey ) const
    00201     {
    00202         unsigned int lIndex = mHashFunctor(pKey);
    00203         lIndex = lIndex % mBuckets.GetCount();
    00204         ListItem* lItem = mBuckets[lIndex];
    00205         while( lItem )
    00206         {
    00207             if( Comparator::CompareIt( lItem->mKey, pKey ) )
    00208             {
    00209                 Iterator lIt( this, lIndex, lItem );
    00210                 return lIt;
    00211             }
    00212             lItem = lItem->mNext;
    00213         }
    00214
    00215         return End();
    00216     }
    00217
    00218     VALUE Remove( const KEY& pKey )
    00219     {
    00220         unsigned int lIndex = mHashFunctor(pKey);
    00221         lIndex = lIndex % mBuckets.GetCount();
    00222         ListItem* lItem = mBuckets.GetAt(lIndex);
    00223         ListItem* lLastItem = NULL;
    00224
    00225         while( lItem )
    00226         {
    00227             if( lItem->mKey == pKey )
    00228             {
    00229                 if( lLastItem )
    00230                     lLastItem->mNext = lItem->mNext;
    00231
    00232                 if( mBuckets.GetAt(lIndex) == lItem )
    00233                     mBuckets.SetAt(lIndex, lItem->mNext );
    00234
    00235                 VALUE lValue = lItem->mValue;
    00236                 FbxDelete(lItem);
    00237
    00238                 return lValue;
    00239             }
    00240
    00241             lLastItem = lItem;
    00242             lItem = lItem->mNext;
    00243         }
    00244
    00245         return VALUE();
    00246     }
    00247
    00248     ValueType& operator[]( const KeyType& pKey )
    00249     {
    00250         Iterator lIt = Find( pKey );
    00251         if( lIt != End() )
    00252         {
    00253             return lIt.mCurrentItem->mValue;
    00254         }
    00255
    00256         unsigned int lIndex = mHashFunctor(pKey);
    00257         lIndex = lIndex % mBuckets.GetCount();
    00258         ListItem* lItem = FbxNew< ListItem >();
    00259         lItem->mNext = NULL;
    00260         lItem->mKey = pKey;
    00261
    00262         if( !mBuckets.GetAt(lIndex) )
    00263         {
    00264             mBuckets.SetAt(lIndex, lItem);
    00265         }
    00266         else
    00267         {
    00268             lItem->mNext = mBuckets.GetAt(lIndex);
    00269             mBuckets.SetAt(lIndex, lItem);
    00270         }
    00271
    00272         return lItem->mValue;
    00273     }
    00274
    00275     Iterator Start() const
    00276     {
    00277         for( int i = 0; i < mBuckets.GetCount(); ++i )
    00278         {
    00279             if( mBuckets[i] )
    00280             {
    00281                 Iterator lIt( this, i, mBuckets[i] );
    00282                 return lIt;
    00283             }
    00284         }
    00285
    00286         return End();
    00287     }
    00288
    00289     Iterator End() const
    00290     {
    00291         Iterator lIt( this, 0, NULL );
    00292         return lIt;
    00293     }
    00294
    00295 private:
    00296
    00297     // not implemented yet!
    00298     FbxHashMap( const FbxHashMap& pOther ) {};
    00299
    00300     FbxArray<ListItem*> mBuckets;
    00301     HashFunctorType mHashFunctor;
    00302
    00303     friend class Iterator;
    00304 };
    00305
    00306 #include <fbxsdk/fbxsdk_nsend.h>
    00307
    00308 #endif /* _FBXSDK_CORE_BASE_HASHMAP_H_ */