ceph/src/boost/boost/poly_collection/detail/type_info_map.hpp

   1 /* Copyright 2016-2018 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/poly_collection for library home page.
   7  */
   8
   9 #ifndef BOOST_POLY_COLLECTION_DETAIL_TYPE_INFO_MAP_HPP
  10 #define BOOST_POLY_COLLECTION_DETAIL_TYPE_INFO_MAP_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/detail/workaround.hpp>
  17 #include <functional>
  18 #include <memory>
  19 #include <type_traits>
  20 #include <typeinfo>
  21 #include <unordered_map>
  22 #include <utility>
  23
  24 namespace boost{
  25
  26 namespace poly_collection{
  27
  28 namespace detail{
  29
  30 /* To cope with dynamic modules/libs, the standard allows for different
  31  * std::type_info instances to describe the same type, which implies that
  32  * std::type_info::operator== and std::type_info::hash_code are costly
  33  * operations typically relying on the stored type name.
  34  * type_info_ptr_hash<T> behaves roughly as a
  35  * std::unordered_map<std::type_index,T> but maintains an internal cache of
  36  * passed std::type_info instances so that lookup is performed (when there's a
  37  * cache hit) without invoking std::type_info equality and hashing ops.
  38  */
  39
  40 struct type_info_ptr_hash
  41 {
  42   std::size_t operator()(const std::type_info* p)const noexcept
  43   {return p->hash_code();}
  44 };
  45
  46 struct type_info_ptr_equal_to
  47 {
  48   bool operator()(
  49     const std::type_info* p,const std::type_info* q)const noexcept
  50   {return *p==*q;}
  51 };
  52
  53 template<typename T,typename Allocator>
  54 class type_info_map
  55 {
  56   using map_type=std::unordered_map<
  57     const std::type_info*,T,
  58     type_info_ptr_hash,type_info_ptr_equal_to,
  59     typename std::allocator_traits<Allocator>::template
  60       rebind_alloc<std::pair<const std::type_info* const,T>>
  61   >;
  62
  63 public:
  64   using key_type=std::type_info;
  65   using mapped_type=T;
  66   using value_type=typename map_type::value_type;
  67   using allocator_type=typename map_type::allocator_type;
  68   using iterator=typename map_type::iterator;
  69   using const_iterator=typename map_type::const_iterator;
  70
  71   type_info_map()=default;
  72   type_info_map(const type_info_map& x):
  73     map{x.map},
  74     cache{make<cache_type>(std::allocator_traits<cache_allocator_type>::
  75       select_on_container_copy_construction(x.cache.get_allocator()))}
  76     {build_cache(x.cache);}
  77   type_info_map(type_info_map&& x)=default;
  78   type_info_map(const allocator_type& al):
  79     map{make<map_type>(al)},cache{make<cache_type>(al)}{}
  80   type_info_map(const type_info_map& x,const allocator_type& al):
  81     map{make(x.map,al)},cache{make<cache_type>(al)}
  82     {build_cache(x.cache);}
  83   type_info_map(type_info_map&& x,const allocator_type& al):
  84     map{make(std::move(x.map),al)},
  85     cache{
  86       al==allocator_type{x.map.get_allocator()}&&x.map.empty()?
  87       make(std::move(x.cache),al):
  88       make<cache_type>(al)
  89     }
  90   {
  91     if(!(al==allocator_type{x.map.get_allocator()}&&x.map.empty())){
  92       build_cache(x.cache);
  93     }
  94     x.map.clear();
  95     x.cache.clear();
  96   }
  97
  98   type_info_map& operator=(const type_info_map& x)
  99   {
 100     if(this!=&x)try{
 101       map=x.map;
 102       cache=make<cache_type>(map.get_allocator());
 103       build_cache(x.cache);
 104     }
 105     catch(...){
 106       map.clear();
 107       cache.clear();
 108       throw;
 109     }
 110     return *this;
 111   }
 112
 113   type_info_map& operator=(type_info_map&& x)
 114   {
 115     if(this!=&x)try{
 116       map=std::move(x.map);
 117       if(map.get_allocator()==x.map.get_allocator()){
 118         cache=std::move(x.cache);
 119       }
 120       else{
 121         cache=make<cache_type>(map.get_allocator());
 122         build_cache(x.cache);
 123         x.cache.clear();
 124       }
 125     }
 126     catch(...){
 127       map.clear();
 128       cache.clear();
 129       x.map.clear();
 130       x.cache.clear();
 131       throw;
 132     }
 133     return *this;
 134   }
 135
 136   allocator_type get_allocator()const noexcept{return map.get_allocator();}
 137
 138   iterator       begin()noexcept{return map.begin();}
 139   iterator       end()noexcept{return map.end();}
 140   const_iterator begin()const noexcept{return map.begin();}
 141   const_iterator end()const noexcept{return map.end();}
 142   const_iterator cbegin()const noexcept{return map.cbegin();}
 143   const_iterator cend()const noexcept{return map.cend();}
 144
 145   iterator find(const key_type& key)
 146   {
 147     auto cit=cache.find(&key);
 148     if(cit!=cache.end())return cit->second;
 149     auto mit=map.find(&key);
 150     if(mit!=map.end())cache.insert({&key,mit});
 151     return mit;
 152   }
 153
 154   const_iterator find(const key_type& key)const
 155   {
 156     auto cit=cache.find(&key);
 157     if(cit!=cache.end())return cit->second;
 158     return map.find(&key);
 159   }
 160
 161   template<typename P>
 162   std::pair<iterator,bool> insert(const key_type& key,P&& x)
 163   {
 164     auto c=map.bucket_count();
 165     auto p=map.emplace(&key,std::forward<P>(x));
 166     if(map.bucket_count()!=c)rebuild_cache();
 167     cache.insert({&key,p.first});
 168     return p;
 169   }
 170
 171   void swap(type_info_map& x){map.swap(x.map);cache.swap(x.cache);}
 172
 173 private:
 174   using cache_type=std::unordered_map<
 175     const std::type_info*,iterator,
 176     std::hash<const std::type_info*>,std::equal_to<const std::type_info*>,
 177     typename std::allocator_traits<Allocator>::template
 178       rebind_alloc<std::pair<const std::type_info* const,iterator>>
 179   >;
 180   using cache_allocator_type=typename cache_type::allocator_type;
 181
 182 #if BOOST_WORKAROUND(BOOST_LIBSTDCXX_VERSION,<40900)
 183   /* std::unordered_map(const allocator_type&),
 184    * std::unordered_map(const unordered_map&,const allocator_type&) and
 185    * std::unordered_map(unordered_map&&,const allocator_type&) not available.
 186    * We make move construction decay to copy construction.
 187    */
 188
 189   template<typename UnorderedMap>
 190   static UnorderedMap make(const typename UnorderedMap::allocator_type& al)
 191   {
 192     return UnorderedMap{
 193       10,typename UnorderedMap::hasher{},typename UnorderedMap::key_equal{},al
 194     };
 195   }
 196
 197   template<typename UnorderedMap>
 198   static typename std::decay<UnorderedMap>::type make(
 199     UnorderedMap&& x,
 200     const typename std::decay<UnorderedMap>::type::allocator_type& al)
 201   {
 202     using RawUnorderedMap=typename std::decay<UnorderedMap>::type;
 203
 204     return RawUnorderedMap{
 205       x.begin(),x.end(),0,typename RawUnorderedMap::hasher{},
 206       typename RawUnorderedMap::key_equal{},al
 207     };
 208   }
 209 #else
 210   template<typename UnorderedMap>
 211   static UnorderedMap make(const typename UnorderedMap::allocator_type& al)
 212   {
 213     return UnorderedMap{al};
 214   }
 215
 216   template<typename UnorderedMap>
 217   static typename std::decay<UnorderedMap>::type make(
 218     UnorderedMap&& x,
 219     const typename std::decay<UnorderedMap>::type::allocator_type& al)
 220   {
 221     return {std::forward<UnorderedMap>(x),al};
 222   }
 223 #endif
 224
 225   void build_cache(const cache_type& x)
 226   {
 227     for(const auto& p:x)cache.insert({p.first,map.find(p.first)});
 228   }
 229
 230   void rebuild_cache()
 231   {
 232     for(auto& p:cache)p.second=map.find(p.first);
 233   }
 234
 235   map_type   map;
 236   cache_type cache;
 237 };
 238
 239 template<typename T,typename Allocator>
 240 void swap(type_info_map<T,Allocator>& x,type_info_map<T,Allocator>& y)
 241 {
 242   x.swap(y);
 243 }
 244
 245 } /* namespace poly_collection::detail */
 246
 247 } /* namespace poly_collection */
 248
 249 } /* namespace boost */
 250
 251 #endif