Ignore:
Timestamp:
Mar 19, 2012, 1:59:48 AM (12 years ago)
Author:
イグトランス (egtra)
Message:

egtraブランチの内容をマージ。

Location:
trunk
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk

  • trunk/ab5.0/jenga/include/common/Hashmap.h

    r639 r828  
     1#include <stdexcept>
     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>
     7#include <boost/serialization/serialization.hpp>
     8#include <boost/serialization/split_member.hpp>
     9
    110#pragma once
    211
    … …  
    514namespace Common{
    615
     16template<class T>
     17class ObjectInHashmap;
     18template<class T>
     19struct ObjectInHashmapHash;
     20template<class T>
     21struct ObjectInHashmapEqualTo;
    722
    823#define MAX_HASHMAP 65535
    9 template<class T> class Hashmap
    10 {
    11     T* hashArray[MAX_HASHMAP];
     24template<class T> class Hashmap : boost::noncopyable
     25{
     26    typedef std::unordered_set<ObjectInHashmap<T>*, ObjectInHashmapHash<T>, ObjectInHashmapEqualTo<T>> MapType;
     27    MapType map;
     28
     29    struct downcast
     30    {
     31        typedef T* result_type;
     32        T* operator ()(ObjectInHashmap<T>* p) const
     33        {
     34            return boost::polymorphic_cast<T*>(p);
     35        }
     36    };
     37    struct const_downcast
     38    {
     39        typedef T const* result_type;
     40        T const* operator ()(ObjectInHashmap<T> const* p) const
     41        {
     42            return boost::polymorphic_cast<T const*>(p);
     43        }
     44    };
    1245
    1346public:
    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     }
    2247
    2348    Hashmap()
    24         : isIteratorReady( false )
    25     {
    26         memset( hashArray, 0, MAX_HASHMAP*sizeof(T*) );
     49    {
    2750    }
    2851    ~Hashmap()
    … …  
    3255    void Clear()
    3356    {
    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*) );
     57        boost::for_each(*this, boost::checked_deleter<T const>());
     58        map.clear();
    4359    }
    4460
    … …  
    4662    void PullOutAll()
    4763    {
    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;
     64        map.clear();
     65    }
     66
     67    bool Put(T* value)
     68    {
     69        if (value == nullptr)
     70        {
     71            throw std::invalid_argument("Hashmap::Put");
     72        }
     73        return map.insert(value).second;
     74    }
     75
     76    typedef boost::transform_iterator<downcast, typename MapType::local_iterator> local_iterator;
     77    typedef boost::transform_iterator<const_downcast, typename MapType::const_local_iterator> const_local_iterator;
     78
     79    boost::iterator_range<local_iterator> GetHashArrayElement(std::string const& keyName)
     80    {
     81        ObjectInHashmapDummy<T> t(keyName);
     82        return boost::iterator_range<local_iterator>(
     83            local_iterator(map.begin(map.bucket(&t)), downcast()),
     84            local_iterator(map.end(map.bucket(&t)), downcast()));
     85    }
     86
     87    boost::iterator_range<const_local_iterator> GetHashArrayElement(std::string const& keyName) const
     88    {
     89        ObjectInHashmapDummy<T> t(keyName);
     90        return boost::iterator_range<const_local_iterator>(
     91            const_local_iterator(map.begin(map.bucket(&t)), const_downcast()),
     92            const_local_iterator(map.end(map.bucket(&t)), const_downcast()));
     93    }
     94
     95    bool IsExistDuplicationKeyName(const std::string &keyName) const
     96    {
     97        ObjectInHashmapDummy<T> t(keyName);
     98        return map.find(&t) != map.end();
    11099    }
    111100
    112101    bool IsExist( const T* value ) const
    113102    {
    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;
     103        return map.find(const_cast<T*>(value)) != map.end();
     104    }
     105
     106    const T *FindLike( const ObjectInHashmap<T>* value ) const
     107    {
     108        auto it = map.find(const_cast<ObjectInHashmap<T>*>(value));
     109        return it != map.end()
     110            ? boost::polymorphic_downcast<T const*>(*it)
     111            : nullptr;
    158112    }
    159113
    … …  
    162116    // イテレータ
    163117    /////////////////////////////////////////////////////////////////
    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 
     118    //typedef boost::transform_iterator<downcast, typename MapType::iterator> iterator;
     119    typedef boost::transform_iterator<downcast, typename MapType::const_iterator> const_iterator;
     120    typedef const_iterator iterator;
     121    typedef typename MapType::size_type size_type;
     122    typedef typename MapType::difference_type difference_type;
     123    //iterator begin()
     124    //{
     125    //  return iterator(map.begin(), downcast());
     126    //}
     127    //iterator end()
     128    //{
     129    //  return iterator(map.end(), downcast());
     130    //}
     131    const_iterator begin() const
     132    {
     133        return const_iterator(map.begin(), downcast());
     134    }
     135    const_iterator end() const
     136    {
     137        return const_iterator(map.end(), downcast());
     138    }
    209139
    210140    // XMLシリアライズ用
    … …  
    215145    {
    216146        std::vector<T *> objects;
    217         ar & BOOST_SERIALIZATION_NVP( objects );
    218 
    219         // 読み込み後の処理
     147        ar & BOOST_SERIALIZATION_NVP(objects);
    220148        Clear();
    221         BOOST_FOREACH( T *object, objects )
    222         {
    223             Put( object );
    224         }
    225         Iterator_Init();
     149        map = boost::copy_range<MapType>(objects);
    226150    }
    227151    template<class Archive> void save(Archive& ar, const unsigned int version) const
    228152    {
    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;
     153        std::vector<T *> objects(begin(), end());
     154        ar & BOOST_SERIALIZATION_NVP(objects);
     155    }
     156};
     157
     158template<class T>
     159class ObjectInHashmap
     160{
     161protected:
     162    ObjectInHashmap()
     163    {
     164    }
     165    ~ObjectInHashmap()
     166    {
     167    }
     168
    245169public:
    246 
    247     ObjectInHashmap()
    248         : pNextObject( NULL )
    249     {
    250     }
    251     ~ObjectInHashmap()
    252     {
    253         if( pNextObject )
    254         {
    255             delete pNextObject;
    256         }
    257     }
    258 
    259170    virtual const std::string &GetKeyName() const = 0;
    260171    virtual bool IsDuplication( const T *value ) const
    … …  
    266177        return ( GetKeyName() == keyName );
    267178    }
    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;
     179};
     180
     181template<class T>
     182struct ObjectInHashmapHash
     183{
     184    typedef std::size_t result_type;
     185    std::size_t operator ()(ObjectInHashmap<T> const* x) const
     186    {
     187        return std::hash<std::string>()(x->GetKeyName());
     188    }
     189};
     190
     191// GetHashArrayElementなどで文字列から検索するために用いる。
     192template<class T>
     193class ObjectInHashmapDummy : public ObjectInHashmap<T>, boost::noncopyable
     194{
     195public:
     196    explicit ObjectInHashmapDummy(std::string const& s) : str(s) {}
     197
     198    virtual std::string const& GetKeyName() const override
     199    {
     200        return str;
     201    }
     202
     203    virtual bool IsDuplication(T const* value) const override
     204    {
     205        return value != nullptr
     206            && value->ObjectInHashmap<T>::IsDuplication(str);
     207    }
     208
     209private:
     210    std::string const& str;
     211};
     212
     213template<class T>
     214struct ObjectInHashmapEqualTo
     215{
     216    typedef bool result_type;
     217    bool operator ()(_In_ ObjectInHashmap<T> const* lhs, _In_ ObjectInHashmap<T> const* rhs) const
     218    {
     219        assert(lhs != nullptr);
     220        assert(rhs != nullptr);
     221        if (auto pl = dynamic_cast<T const*>(rhs))
     222        {
     223            return lhs->IsDuplication(pl);
     224        }
     225        else
     226        {
     227            return rhs->IsDuplication(dynamic_cast<T const*>(lhs));
     228        }
    280229    }
    281230};
Note: See TracChangeset for help on using the changeset viewer.