Ignore:
Timestamp:
Feb 11, 2011, 10:05:14 PM (14 years ago)
Author:
イグトランス (egtra)
Message:

Hashmapの実装にunorderedを用いるよう変更

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/egtra/ab5.0/jenga/include/common/Hashmap.h

    r639 r803  
    11#pragma once
    2 
     2#include <unordered_set>
     3#include <boost/range/algorithm.hpp>
     4#include <boost/checked_delete.hpp>
     5#include <boost/iterator/transform_iterator.hpp>
     6#include <boost/cast.hpp>
    37
    48namespace Jenga{
    59namespace Common{
    610
     11template<class T>
     12class ObjectInHashmap;
     13template<class T>
     14struct ObjectInHashmapHash;
     15template<class T>
     16struct ObjectInHashmapEqualTo;
    717
    818#define MAX_HASHMAP 65535
    9 template<class T> class Hashmap
    10 {
    11     T* hashArray[MAX_HASHMAP];
     19template<class T> class Hashmap : boost::noncopyable
     20{
     21    typedef std::unordered_set<ObjectInHashmap<T>*, ObjectInHashmapHash<T>, ObjectInHashmapEqualTo<T>> MapType;
     22    MapType map;
     23
     24    struct downcast
     25    {
     26        typedef T* result_type;
     27        T* operator ()(ObjectInHashmap<T>* p) const
     28        {
     29            return boost::polymorphic_cast<T*>(p);
     30        }
     31    };
     32    struct const_downcast
     33    {
     34        typedef T const* result_type;
     35        T const* operator ()(ObjectInHashmap<T> const* p) const
     36        {
     37            return boost::polymorphic_cast<T const*>(p);
     38        }
     39    };
    1240
    1341public:
    14     virtual int GetHash( const char *keyName ) const
    15     {
    16         int key;
    17         for(key=0;*keyName!='\0';keyName++){
    18             key=((key<<8)+ *keyName )%MAX_HASHMAP;
    19         }
    20         return key;
    21     }
    2242
    2343    Hashmap()
    24         : isIteratorReady( false )
    25     {
    26         memset( hashArray, 0, MAX_HASHMAP*sizeof(T*) );
     44    {
    2745    }
    2846    ~Hashmap()
    … …  
    3250    void Clear()
    3351    {
    34         for( int i=0; i<MAX_HASHMAP; i++ )
    35         {
    36             T* temp = hashArray[i];
    37             if( temp )
    38             {
    39                 delete temp;
    40             }
    41         }
    42         memset( hashArray, 0, MAX_HASHMAP*sizeof(T*) );
     52        boost::for_each(*this, boost::checked_deleter<T const>());
     53        map.clear();
    4354    }
    4455
    … …  
    4657    void PullOutAll()
    4758    {
    48         memset( hashArray, 0, MAX_HASHMAP*sizeof(T*) );
    49     }
    50 
    51     bool Put( T* value )
    52     {
    53         int key = GetHash( value->GetKeyName().c_str() );
    54 
    55         if(hashArray[key]){
    56             T *temp = hashArray[key];
    57             while( true ){
    58                 if( temp->IsDuplication( value ) )
    59                 {
    60                     // 重複している
    61                     return false;
    62                 }
    63 
    64                 if( temp->GetChainNext() == NULL )
    65                 {
    66                     break;
    67                 }
    68                 temp = temp->GetChainNext();
    69             }
    70             temp->SetChainNext( value );
    71         }
    72         else{
    73             hashArray[key] = value;
    74         }
    75 
    76         return true;
    77     }
    78 
    79     T* GetHashArrayElement( const char *keyName )
    80     {
    81         return hashArray[GetHash(keyName)];
    82     }
    83     const T* GetHashArrayElement( const char *keyName ) const
    84     {
    85         return hashArray[GetHash(keyName)];
    86     }
    87 
    88     bool IsExistDuplicationKeyName( const std::string &keyName ) const
    89     {
    90         int key = GetHash( keyName.c_str() );
    91 
    92         if(hashArray[key]){
    93             const T *temp = hashArray[key];
    94             while( true ){
    95                 if( temp->IsDuplication( keyName ) )
    96                 {
    97                     // 重複している
    98                     return true;
    99                 }
    100 
    101                 if( temp->GetChainNext() == NULL )
    102                 {
    103                     break;
    104                 }
    105                 temp = temp->GetChainNext();
    106             }
    107         }
    108 
    109         return false;
     59        map.clear();
     60    }
     61
     62    bool Put(T* value)
     63    {
     64        if (value == nullptr)
     65        {
     66            throw std::invalid_argument("Hashmap::Put");
     67        }
     68        return map.insert(value).second;
     69    }
     70
     71    typedef boost::transform_iterator<downcast, typename MapType::local_iterator> local_iterator;
     72    typedef boost::transform_iterator<const_downcast, typename MapType::const_local_iterator> const_local_iterator;
     73
     74    boost::iterator_range<local_iterator> GetHashArrayElement(std::string const& keyName)
     75    {
     76        ObjectInHashmapDummy<T> t(keyName);
     77        return boost::iterator_range<local_iterator>(
     78            local_iterator(map.begin(map.bucket(&t)), downcast()),
     79            local_iterator(map.end(map.bucket(&t)), downcast()));
     80    }
     81
     82    boost::iterator_range<const_local_iterator> GetHashArrayElement(std::string const& keyName) const
     83    {
     84        ObjectInHashmapDummy<T> t(keyName);
     85        return boost::iterator_range<const_local_iterator>(
     86            const_local_iterator(map.begin(map.bucket(&t)), const_downcast()),
     87            const_local_iterator(map.end(map.bucket(&t)), const_downcast()));
     88    }
     89
     90    bool IsExistDuplicationKeyName(const std::string &keyName) const
     91    {
     92        ObjectInHashmapDummy<T> t(keyName);
     93        return map.find(&t) != map.end();
    11094    }
    11195
    11296    bool IsExist( const T* value ) const
    11397    {
    114         int key = GetHash( value->GetKeyName().c_str() );
    115 
    116         if(hashArray[key]){
    117             const T *temp = hashArray[key];
    118             while( true ){
    119                 if( temp->IsDuplication( value ) )
    120                 {
    121                     // 重複している
    122                     return true;
    123                 }
    124 
    125                 if( temp->GetChainNext() == NULL )
    126                 {
    127                     break;
    128                 }
    129                 temp = temp->GetChainNext();
    130             }
    131         }
    132 
    133         return false;
    134     }
    135 
    136     const T *FindLike( const T* value ) const
    137     {
    138         int key = GetHash( value->GetKeyName().c_str() );
    139 
    140         if(hashArray[key]){
    141             const T *temp = hashArray[key];
    142             while( true ){
    143                 if( temp->IsDuplication( value ) )
    144                 {
    145                     // 重複している
    146                     return temp;
    147                 }
    148 
    149                 if( temp->GetChainNext() == NULL )
    150                 {
    151                     break;
    152                 }
    153                 temp = temp->GetChainNext();
    154             }
    155         }
    156 
    157         return NULL;
     98        return map.find(const_cast<T*>(value)) != map.end();
     99    }
     100
     101    const T *FindLike( const ObjectInHashmap<T>* value ) const
     102    {
     103        auto it = map.find(const_cast<ObjectInHashmap<T>*>(value));
     104        return it != map.end()
     105            ? boost::polymorphic_downcast<T const*>(*it)
     106            : nullptr;
    158107    }
    159108
    … …  
    162111    // イテレータ
    163112    /////////////////////////////////////////////////////////////////
    164 private:
    165     mutable std::vector<T*> iterator_Objects;
    166     mutable int iterator_CurrentNext;
    167     mutable bool isIteratorReady;
    168 public:
    169     void Iterator_Init() const
    170     {
    171         iterator_Objects.clear();
    172         iterator_CurrentNext = 0;
    173 
    174         for( int i=0; i<MAX_HASHMAP; i++ ){
    175             if( hashArray[i] ){
    176                 T* temp = hashArray[i];
    177                 while( temp )
    178                 {
    179                     iterator_Objects.push_back( temp );
    180 
    181                     temp = (T*)temp->GetChainNext();
    182                 }
    183             }
    184         }
    185 
    186         isIteratorReady = true;
    187     }
    188     void Iterator_Reset() const
    189     {
    190         if( !isIteratorReady )
    191         {
    192             Jenga::Throw( "イテレータの準備ができていない" );
    193         }
    194         iterator_CurrentNext = 0;
    195     }
    196     bool Iterator_HasNext() const
    197     {
    198         return ( iterator_CurrentNext < (int)iterator_Objects.size() );
    199     }
    200     T *Iterator_GetNext() const
    201     {
    202         return iterator_Objects[iterator_CurrentNext++];
    203     }
    204     int Iterator_GetMaxCount() const
    205     {
    206         return (int)iterator_Objects.size();
    207     }
    208 
     113    //typedef boost::transform_iterator<downcast, typename MapType::iterator> iterator;
     114    typedef boost::transform_iterator<downcast, typename MapType::const_iterator> const_iterator;
     115    typedef const_iterator iterator;
     116    typedef typename MapType::size_type size_type;
     117    typedef typename MapType::difference_type difference_type;
     118    //iterator begin()
     119    //{
     120    //  return iterator(map.begin(), downcast());
     121    //}
     122    //iterator end()
     123    //{
     124    //  return iterator(map.end(), downcast());
     125    //}
     126    const_iterator begin() const
     127    {
     128        return const_iterator(map.begin(), downcast());
     129    }
     130    const_iterator end() const
     131    {
     132        return const_iterator(map.end(), downcast());
     133    }
    209134
    210135    // XMLシリアライズ用
    … …  
    215140    {
    216141        std::vector<T *> objects;
    217         ar & BOOST_SERIALIZATION_NVP( objects );
    218 
    219         // 読み込み後の処理
     142        ar & BOOST_SERIALIZATION_NVP(objects);
    220143        Clear();
    221         BOOST_FOREACH( T *object, objects )
    222         {
    223             Put( object );
    224         }
    225         Iterator_Init();
     144        map = boost::copy_range<MapType>(objects);
    226145    }
    227146    template<class Archive> void save(Archive& ar, const unsigned int version) const
    228147    {
    229         // 保存準備
    230         std::vector<T *> objects;
    231         objects.clear();
    232         Iterator_Reset();
    233         while( Iterator_HasNext() )
    234         {
    235             objects.push_back( Iterator_GetNext() );
    236         }
    237 
    238         ar & BOOST_SERIALIZATION_NVP( objects );
    239     }
    240 };
    241 
    242 template<class T> class ObjectInHashmap
    243 {
    244     T *pNextObject;
     148        std::vector<T *> objects(begin(), end());
     149        ar & BOOST_SERIALIZATION_NVP(objects);
     150    }
     151};
     152
     153template<class T>
     154class ObjectInHashmap
     155{
    245156public:
    246157
    247158    ObjectInHashmap()
    248         : pNextObject( NULL )
    249159    {
    250160    }
    251161    ~ObjectInHashmap()
    252162    {
    253         if( pNextObject )
    254         {
    255             delete pNextObject;
    256         }
    257163    }
    258164
    … …  
    266172        return ( GetKeyName() == keyName );
    267173    }
    268 
    269     T *GetChainNext()
    270     {
    271         return pNextObject;
    272     }
    273     const T *GetChainNext() const
    274     {
    275         return pNextObject;
    276     }
    277     void SetChainNext( T *pNextObject )
    278     {
    279         this->pNextObject = pNextObject;
     174};
     175
     176template<class T>
     177struct ObjectInHashmapHash
     178{
     179    typedef std::size_t result_type;
     180    std::size_t operator ()(ObjectInHashmap<T> const* x) const
     181    {
     182        return std::hash<std::string>()(x->GetKeyName());
     183    }
     184};
     185
     186// GetHashArrayElementなどで文字列から検索するために用いる。
     187template<class T>
     188class ObjectInHashmapDummy : public ObjectInHashmap<T>, boost::noncopyable
     189{
     190public:
     191    explicit ObjectInHashmapDummy(std::string const& s) : str(s) {}
     192
     193    virtual std::string const& GetKeyName() const override
     194    {
     195        return str;
     196    }
     197
     198    virtual bool IsDuplication(T const* value) const override
     199    {
     200        return value != nullptr
     201            && value->ObjectInHashmap<T>::IsDuplication(str);
     202    }
     203
     204private:
     205    std::string const& str;
     206};
     207
     208template<class T>
     209struct ObjectInHashmapEqualTo
     210{
     211    typedef bool result_type;
     212    bool operator ()(ObjectInHashmap<T> const* lhs, ObjectInHashmap<T> const* rhs) const
     213    {
     214        assert(lhs != nullptr);
     215        assert(rhs != nullptr);
     216        if (auto pl = dynamic_cast<T const*>(rhs))
     217        {
     218            return lhs->IsDuplication(pl);
     219        }
     220        else
     221        {
     222            return rhs->IsDuplication(dynamic_cast<T const*>(lhs));
     223        }
    280224    }
    281225};
Note: See TracChangeset for help on using the changeset viewer.