1 ////////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost 4 // Software License, Version 1.0. (See accompanying file 5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 // 7 // See http://www.boost.org/libs/interprocess for documentation. 8 // 9 ////////////////////////////////////////////////////////////////////////////// 10 11 #ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP 12 #define BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP 13 14 #ifndef BOOST_CONFIG_HPP 15 # include <boost/config.hpp> 16 #endif 17 # 18 #if defined(BOOST_HAS_PRAGMA_ONCE) 19 # pragma once 20 #endif 21 22 #include <boost/interprocess/detail/config_begin.hpp> 23 #include <boost/interprocess/detail/workaround.hpp> 24 25 #include <boost/interprocess/detail/utilities.hpp> 26 #include <boost/interprocess/allocators/allocator.hpp> 27 #include <boost/interprocess/containers/vector.hpp> 28 #include <boost/intrusive/unordered_set.hpp> 29 #include <boost/intrusive/detail/minimal_pair_header.hpp> 30 #include <boost/intrusive/detail/minimal_less_equal_header.hpp> //std::less 31 #include <boost/container/detail/minimal_char_traits_header.hpp> //std::char_traits 32 #include <boost/container/detail/placement_new.hpp> 33 34 //!\file 35 //!Describes index adaptor of boost::intrusive::unordered_set container, to use it 36 //!as name/shared memory index 37 38 namespace boost { namespace interprocess { 39 40 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED) 41 42 //!Helper class to define typedefs 43 //!from IndexTraits 44 template <class MapConfig> 45 struct iunordered_set_index_aux 46 { 47 typedef typename 48 MapConfig::segment_manager_base segment_manager_base; 49 50 typedef typename 51 segment_manager_base::void_pointer void_pointer; 52 53 typedef typename bi::make_unordered_set_base_hook 54 < bi::void_pointer<void_pointer> 55 >::type derivation_hook; 56 57 typedef typename MapConfig::template 58 intrusive_value_type<derivation_hook>::type value_type; 59 60 typedef typename MapConfig:: 61 intrusive_compare_key_type intrusive_compare_key_type; 62 63 typedef std::equal_to<value_type> value_equal; 64 65 typedef typename MapConfig::char_type char_type; 66 67 struct equal_function 68 { operator ()boost::interprocess::iunordered_set_index_aux::equal_function69 bool operator()(const intrusive_compare_key_type &i, const value_type &b) const 70 { 71 return (i.m_len == b.name_length()) && 72 (std::char_traits<char_type>::compare 73 (i.mp_str, b.name(), i.m_len) == 0); 74 } 75 operator ()boost::interprocess::iunordered_set_index_aux::equal_function76 bool operator()(const value_type &b, const intrusive_compare_key_type &i) const 77 { 78 return (i.m_len == b.name_length()) && 79 (std::char_traits<char_type>::compare 80 (i.mp_str, b.name(), i.m_len) == 0); 81 } 82 operator ()boost::interprocess::iunordered_set_index_aux::equal_function83 bool operator()(const value_type &b1, const value_type &b2) const 84 { 85 return (b1.name_length() == b2.name_length()) && 86 (std::char_traits<char_type>::compare 87 (b1.name(), b2.name(), b1.name_length()) == 0); 88 } 89 }; 90 91 struct hash_function 92 : std::unary_function<value_type, std::size_t> 93 { operator ()boost::interprocess::iunordered_set_index_aux::hash_function94 std::size_t operator()(const value_type &val) const 95 { 96 const char_type *beg = ipcdetail::to_raw_pointer(val.name()), 97 *end = beg + val.name_length(); 98 return boost::hash_range(beg, end); 99 } 100 operator ()boost::interprocess::iunordered_set_index_aux::hash_function101 std::size_t operator()(const intrusive_compare_key_type &i) const 102 { 103 const char_type *beg = i.mp_str, 104 *end = beg + i.m_len; 105 return boost::hash_range(beg, end); 106 } 107 }; 108 109 typedef typename bi::make_unordered_set 110 < value_type 111 , bi::hash<hash_function> 112 , bi::equal<equal_function> 113 , bi::size_type<typename segment_manager_base::size_type> 114 >::type index_t; 115 typedef typename index_t::bucket_type bucket_type; 116 typedef allocator 117 <bucket_type, segment_manager_base> allocator_type; 118 119 struct allocator_holder 120 { allocator_holderboost::interprocess::iunordered_set_index_aux::allocator_holder121 allocator_holder(segment_manager_base *mngr) 122 : alloc(mngr) 123 {} 124 allocator_type alloc; 125 bucket_type init_bucket; 126 }; 127 }; 128 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED 129 130 //!Index type based in boost::intrusive::set. 131 //!Just derives from boost::intrusive::set 132 //!and defines the interface needed by managed memory segments 133 template <class MapConfig> 134 class iunordered_set_index 135 //Derive class from map specialization 136 : private iunordered_set_index_aux<MapConfig>::allocator_holder 137 , public iunordered_set_index_aux<MapConfig>::index_t 138 { 139 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED) 140 typedef iunordered_set_index_aux<MapConfig> index_aux; 141 typedef typename index_aux::index_t index_type; 142 typedef typename MapConfig:: 143 intrusive_compare_key_type intrusive_compare_key_type; 144 typedef typename index_aux::equal_function equal_function; 145 typedef typename index_aux::hash_function hash_function; 146 typedef typename MapConfig::char_type char_type; 147 typedef typename 148 iunordered_set_index_aux<MapConfig>::allocator_type allocator_type; 149 typedef typename 150 iunordered_set_index_aux<MapConfig>::allocator_holder allocator_holder; 151 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED 152 153 public: 154 typedef typename index_type::iterator iterator; 155 typedef typename index_type::const_iterator const_iterator; 156 typedef typename index_type::insert_commit_data insert_commit_data; 157 typedef typename index_type::value_type value_type; 158 typedef typename index_type::bucket_ptr bucket_ptr; 159 typedef typename index_type::bucket_type bucket_type; 160 typedef typename index_type::bucket_traits bucket_traits; 161 typedef typename index_type::size_type size_type; 162 163 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED) 164 private: 165 typedef typename index_aux:: 166 segment_manager_base segment_manager_base; 167 168 static const std::size_t InitBufferSize = 64; 169 create_buckets(allocator_type & alloc,size_type num)170 static bucket_ptr create_buckets(allocator_type &alloc, size_type num) 171 { 172 num = index_type::suggested_upper_bucket_count(num); 173 bucket_ptr buckets = alloc.allocate(num); 174 bucket_ptr buckets_init = buckets; 175 for(size_type i = 0; i < num; ++i){ 176 ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type(); 177 } 178 return buckets; 179 } 180 shrink_buckets(bucket_ptr buckets,size_type old_size,allocator_type & alloc,size_type new_size)181 static size_type shrink_buckets 182 ( bucket_ptr buckets, size_type old_size 183 , allocator_type &alloc, size_type new_size) 184 { 185 if(old_size <= new_size ) 186 return old_size; 187 size_type received_size = new_size; 188 if(!alloc.allocation_command 189 (boost::interprocess::try_shrink_in_place | boost::interprocess::nothrow_allocation, old_size, received_size, buckets)){ 190 return old_size; 191 } 192 193 for( bucket_type *p = ipcdetail::to_raw_pointer(buckets) + received_size 194 , *pend = ipcdetail::to_raw_pointer(buckets) + old_size 195 ; p != pend 196 ; ++p){ 197 p->~bucket_type(); 198 } 199 200 bucket_ptr shunk_p = alloc.allocation_command 201 (boost::interprocess::shrink_in_place | boost::interprocess::nothrow_allocation, received_size, received_size, buckets); 202 BOOST_ASSERT(buckets == shunk_p); (void)shunk_p; 203 204 bucket_ptr buckets_init = buckets + received_size; 205 for(size_type i = 0; i < (old_size - received_size); ++i){ 206 to_raw_pointer(buckets_init++)->~bucket_type(); 207 } 208 return received_size; 209 } 210 expand_or_create_buckets(bucket_ptr old_buckets,const size_type old_num,allocator_type & alloc,const size_type new_num)211 static bucket_ptr expand_or_create_buckets 212 ( bucket_ptr old_buckets, const size_type old_num 213 , allocator_type &alloc, const size_type new_num) 214 { 215 size_type received_size = new_num; 216 bucket_ptr reuse(old_buckets); 217 bucket_ptr ret = alloc.allocation_command 218 (boost::interprocess::expand_fwd | boost::interprocess::allocate_new, new_num, received_size, reuse); 219 if(ret == old_buckets){ 220 bucket_ptr buckets_init = old_buckets + old_num; 221 for(size_type i = 0; i < (new_num - old_num); ++i){ 222 ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type(); 223 } 224 } 225 else{ 226 bucket_ptr buckets_init = ret; 227 for(size_type i = 0; i < new_num; ++i){ 228 ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type(); 229 } 230 } 231 return ret; 232 } 233 destroy_buckets(allocator_type & alloc,bucket_ptr buckets,size_type num)234 static void destroy_buckets 235 (allocator_type &alloc, bucket_ptr buckets, size_type num) 236 { 237 bucket_ptr buckets_destroy = buckets; 238 for(size_type i = 0; i < num; ++i){ 239 to_raw_pointer(buckets_destroy++)->~bucket_type(); 240 } 241 alloc.deallocate(buckets, num); 242 } 243 get_this_pointer()244 iunordered_set_index<MapConfig>* get_this_pointer() 245 { return this; } 246 247 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED 248 249 public: 250 //!Constructor. Takes a pointer to the 251 //!segment manager. Can throw iunordered_set_index(segment_manager_base * mngr)252 iunordered_set_index(segment_manager_base *mngr) 253 : allocator_holder(mngr) 254 , index_type(bucket_traits(&get_this_pointer()->init_bucket, 1)) 255 {} 256 ~iunordered_set_index()257 ~iunordered_set_index() 258 { 259 index_type::clear(); 260 if(index_type::bucket_pointer() != bucket_ptr(&this->init_bucket)){ 261 destroy_buckets(this->alloc, index_type::bucket_pointer(), index_type::bucket_count()); 262 } 263 } 264 265 //!This reserves memory to optimize the insertion of n 266 //!elements in the index reserve(size_type new_n)267 void reserve(size_type new_n) 268 { 269 //Let's maintain a 1.0f load factor 270 size_type old_n = this->bucket_count(); 271 if(new_n <= old_n) 272 return; 273 bucket_ptr old_p = this->bucket_pointer(); 274 new_n = index_type::suggested_upper_bucket_count(new_n); 275 bucket_ptr new_p; 276 //This can throw 277 try{ 278 if(old_p != bucket_ptr(&this->init_bucket)) 279 new_p = expand_or_create_buckets(old_p, old_n, this->alloc, new_n); 280 else 281 new_p = create_buckets(this->alloc, new_n); 282 } 283 catch(...){ 284 return; 285 } 286 //Rehashing does not throw, since neither the hash nor the 287 //comparison function can throw 288 this->rehash(bucket_traits(new_p, new_n)); 289 if(new_p != old_p && old_p != bucket_ptr(&this->init_bucket)){ 290 destroy_buckets(this->alloc, old_p, old_n); 291 } 292 } 293 294 //!This tries to free unused memory 295 //!previously allocated. shrink_to_fit()296 void shrink_to_fit() 297 { 298 size_type cur_size = this->size(); 299 size_type cur_count = this->bucket_count(); 300 bucket_ptr old_p = this->bucket_pointer(); 301 302 if(!this->size() && old_p != bucket_ptr(&this->init_bucket)){ 303 this->rehash(bucket_traits(bucket_ptr(&this->init_bucket), 1)); 304 destroy_buckets(this->alloc, old_p, cur_count); 305 } 306 else{ 307 size_type sug_count = 0; //gcc warning 308 sug_count = index_type::suggested_upper_bucket_count(cur_size); 309 310 if(sug_count >= cur_count) 311 return; 312 313 try{ 314 shrink_buckets(old_p, cur_count, this->alloc, sug_count); 315 } 316 catch(...){ 317 return; 318 } 319 320 //Rehashing does not throw, since neither the hash nor the 321 //comparison function can throw 322 this->rehash(bucket_traits(old_p, sug_count)); 323 } 324 } 325 find(const intrusive_compare_key_type & key)326 iterator find(const intrusive_compare_key_type &key) 327 { return index_type::find(key, hash_function(), equal_function()); } 328 find(const intrusive_compare_key_type & key) const329 const_iterator find(const intrusive_compare_key_type &key) const 330 { return index_type::find(key, hash_function(), equal_function()); } 331 insert_check(const intrusive_compare_key_type & key,insert_commit_data & commit_data)332 std::pair<iterator, bool>insert_check 333 (const intrusive_compare_key_type &key, insert_commit_data &commit_data) 334 { return index_type::insert_check(key, hash_function(), equal_function(), commit_data); } 335 insert_commit(value_type & val,insert_commit_data & commit_data)336 iterator insert_commit(value_type &val, insert_commit_data &commit_data) 337 { 338 iterator it = index_type::insert_commit(val, commit_data); 339 size_type cur_size = this->size(); 340 if(cur_size > this->bucket_count()){ 341 try{ 342 this->reserve(cur_size); 343 } 344 catch(...){ 345 //Strong guarantee: if something goes wrong 346 //we should remove the insertion. 347 // 348 //We can use the iterator because the hash function 349 //can't throw and this means that "reserve" will 350 //throw only because of the memory allocation: 351 //the iterator has not been invalidated. 352 index_type::erase(it); 353 throw; 354 } 355 } 356 return it; 357 } 358 }; 359 360 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED) 361 362 //!Trait class to detect if an index is an intrusive 363 //!index 364 template<class MapConfig> 365 struct is_intrusive_index 366 <boost::interprocess::iunordered_set_index<MapConfig> > 367 { 368 static const bool value = true; 369 }; 370 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED 371 372 }} //namespace boost { namespace interprocess { 373 374 #include <boost/interprocess/detail/config_end.hpp> 375 376 #endif //#ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP 377