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 { 93 typedef value_type argument_type; 94 typedef std::size_t result_type; 95 operator ()boost::interprocess::iunordered_set_index_aux::hash_function96 std::size_t operator()(const value_type &val) const 97 { 98 const char_type *beg = ipcdetail::to_raw_pointer(val.name()), 99 *end = beg + val.name_length(); 100 return boost::hash_range(beg, end); 101 } 102 operator ()boost::interprocess::iunordered_set_index_aux::hash_function103 std::size_t operator()(const intrusive_compare_key_type &i) const 104 { 105 const char_type *beg = i.mp_str, 106 *end = beg + i.m_len; 107 return boost::hash_range(beg, end); 108 } 109 }; 110 111 typedef typename bi::make_unordered_set 112 < value_type 113 , bi::hash<hash_function> 114 , bi::equal<equal_function> 115 , bi::size_type<typename segment_manager_base::size_type> 116 >::type index_t; 117 typedef typename index_t::bucket_type bucket_type; 118 typedef allocator 119 <bucket_type, segment_manager_base> allocator_type; 120 121 struct allocator_holder 122 { allocator_holderboost::interprocess::iunordered_set_index_aux::allocator_holder123 allocator_holder(segment_manager_base *mngr) 124 : alloc(mngr) 125 {} 126 allocator_type alloc; 127 bucket_type init_bucket; 128 }; 129 }; 130 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED 131 132 //!Index type based in boost::intrusive::set. 133 //!Just derives from boost::intrusive::set 134 //!and defines the interface needed by managed memory segments 135 template <class MapConfig> 136 class iunordered_set_index 137 //Derive class from map specialization 138 : private iunordered_set_index_aux<MapConfig>::allocator_holder 139 , public iunordered_set_index_aux<MapConfig>::index_t 140 { 141 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED) 142 typedef iunordered_set_index_aux<MapConfig> index_aux; 143 typedef typename index_aux::index_t index_type; 144 typedef typename MapConfig:: 145 intrusive_compare_key_type intrusive_compare_key_type; 146 typedef typename index_aux::equal_function equal_function; 147 typedef typename index_aux::hash_function hash_function; 148 typedef typename MapConfig::char_type char_type; 149 typedef typename 150 iunordered_set_index_aux<MapConfig>::allocator_type allocator_type; 151 typedef typename 152 iunordered_set_index_aux<MapConfig>::allocator_holder allocator_holder; 153 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED 154 155 public: 156 typedef typename index_type::iterator iterator; 157 typedef typename index_type::const_iterator const_iterator; 158 typedef typename index_type::insert_commit_data insert_commit_data; 159 typedef typename index_type::value_type value_type; 160 typedef typename index_type::bucket_ptr bucket_ptr; 161 typedef typename index_type::bucket_type bucket_type; 162 typedef typename index_type::bucket_traits bucket_traits; 163 typedef typename index_type::size_type size_type; 164 165 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED) 166 private: 167 typedef typename index_aux:: 168 segment_manager_base segment_manager_base; 169 170 static const std::size_t InitBufferSize = 64; 171 create_buckets(allocator_type & alloc,size_type num)172 static bucket_ptr create_buckets(allocator_type &alloc, size_type num) 173 { 174 num = index_type::suggested_upper_bucket_count(num); 175 bucket_ptr buckets = alloc.allocate(num); 176 bucket_ptr buckets_init = buckets; 177 for(size_type i = 0; i < num; ++i){ 178 ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type(); 179 } 180 return buckets; 181 } 182 shrink_buckets(bucket_ptr buckets,size_type old_size,allocator_type & alloc,size_type new_size)183 static size_type shrink_buckets 184 ( bucket_ptr buckets, size_type old_size 185 , allocator_type &alloc, size_type new_size) 186 { 187 if(old_size <= new_size ) 188 return old_size; 189 size_type received_size = new_size; 190 if(!alloc.allocation_command 191 (boost::interprocess::try_shrink_in_place | boost::interprocess::nothrow_allocation, old_size, received_size, buckets)){ 192 return old_size; 193 } 194 195 for( bucket_type *p = ipcdetail::to_raw_pointer(buckets) + received_size 196 , *pend = ipcdetail::to_raw_pointer(buckets) + old_size 197 ; p != pend 198 ; ++p){ 199 p->~bucket_type(); 200 } 201 202 bucket_ptr shunk_p = alloc.allocation_command 203 (boost::interprocess::shrink_in_place | boost::interprocess::nothrow_allocation, received_size, received_size, buckets); 204 BOOST_ASSERT(buckets == shunk_p); (void)shunk_p; 205 206 bucket_ptr buckets_init = buckets + received_size; 207 for(size_type i = 0; i < (old_size - received_size); ++i){ 208 to_raw_pointer(buckets_init++)->~bucket_type(); 209 } 210 return received_size; 211 } 212 expand_or_create_buckets(bucket_ptr old_buckets,const size_type old_num,allocator_type & alloc,const size_type new_num)213 static bucket_ptr expand_or_create_buckets 214 ( bucket_ptr old_buckets, const size_type old_num 215 , allocator_type &alloc, const size_type new_num) 216 { 217 size_type received_size = new_num; 218 bucket_ptr reuse(old_buckets); 219 bucket_ptr ret = alloc.allocation_command 220 (boost::interprocess::expand_fwd | boost::interprocess::allocate_new, new_num, received_size, reuse); 221 if(ret == old_buckets){ 222 bucket_ptr buckets_init = old_buckets + old_num; 223 for(size_type i = 0; i < (new_num - old_num); ++i){ 224 ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type(); 225 } 226 } 227 else{ 228 bucket_ptr buckets_init = ret; 229 for(size_type i = 0; i < new_num; ++i){ 230 ::new(to_raw_pointer(buckets_init++), boost_container_new_t())bucket_type(); 231 } 232 } 233 return ret; 234 } 235 destroy_buckets(allocator_type & alloc,bucket_ptr buckets,size_type num)236 static void destroy_buckets 237 (allocator_type &alloc, bucket_ptr buckets, size_type num) 238 { 239 bucket_ptr buckets_destroy = buckets; 240 for(size_type i = 0; i < num; ++i){ 241 to_raw_pointer(buckets_destroy++)->~bucket_type(); 242 } 243 alloc.deallocate(buckets, num); 244 } 245 get_this_pointer()246 iunordered_set_index<MapConfig>* get_this_pointer() 247 { return this; } 248 249 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED 250 251 public: 252 //!Constructor. Takes a pointer to the 253 //!segment manager. Can throw iunordered_set_index(segment_manager_base * mngr)254 iunordered_set_index(segment_manager_base *mngr) 255 : allocator_holder(mngr) 256 , index_type(bucket_traits(&get_this_pointer()->init_bucket, 1)) 257 {} 258 ~iunordered_set_index()259 ~iunordered_set_index() 260 { 261 index_type::clear(); 262 if(index_type::bucket_pointer() != bucket_ptr(&this->init_bucket)){ 263 destroy_buckets(this->alloc, index_type::bucket_pointer(), index_type::bucket_count()); 264 } 265 } 266 267 //!This reserves memory to optimize the insertion of n 268 //!elements in the index reserve(size_type new_n)269 void reserve(size_type new_n) 270 { 271 //Let's maintain a 1.0f load factor 272 size_type old_n = this->bucket_count(); 273 if(new_n <= old_n) 274 return; 275 bucket_ptr old_p = this->bucket_pointer(); 276 new_n = index_type::suggested_upper_bucket_count(new_n); 277 bucket_ptr new_p; 278 //This can throw 279 try{ 280 if(old_p != bucket_ptr(&this->init_bucket)) 281 new_p = expand_or_create_buckets(old_p, old_n, this->alloc, new_n); 282 else 283 new_p = create_buckets(this->alloc, new_n); 284 } 285 catch(...){ 286 return; 287 } 288 //Rehashing does not throw, since neither the hash nor the 289 //comparison function can throw 290 this->rehash(bucket_traits(new_p, new_n)); 291 if(new_p != old_p && old_p != bucket_ptr(&this->init_bucket)){ 292 destroy_buckets(this->alloc, old_p, old_n); 293 } 294 } 295 296 //!This tries to free unused memory 297 //!previously allocated. shrink_to_fit()298 void shrink_to_fit() 299 { 300 size_type cur_size = this->size(); 301 size_type cur_count = this->bucket_count(); 302 bucket_ptr old_p = this->bucket_pointer(); 303 304 if(!this->size() && old_p != bucket_ptr(&this->init_bucket)){ 305 this->rehash(bucket_traits(bucket_ptr(&this->init_bucket), 1)); 306 destroy_buckets(this->alloc, old_p, cur_count); 307 } 308 else{ 309 size_type sug_count = 0; //gcc warning 310 sug_count = index_type::suggested_upper_bucket_count(cur_size); 311 312 if(sug_count >= cur_count) 313 return; 314 315 try{ 316 shrink_buckets(old_p, cur_count, this->alloc, sug_count); 317 } 318 catch(...){ 319 return; 320 } 321 322 //Rehashing does not throw, since neither the hash nor the 323 //comparison function can throw 324 this->rehash(bucket_traits(old_p, sug_count)); 325 } 326 } 327 find(const intrusive_compare_key_type & key)328 iterator find(const intrusive_compare_key_type &key) 329 { return index_type::find(key, hash_function(), equal_function()); } 330 find(const intrusive_compare_key_type & key) const331 const_iterator find(const intrusive_compare_key_type &key) const 332 { return index_type::find(key, hash_function(), equal_function()); } 333 insert_check(const intrusive_compare_key_type & key,insert_commit_data & commit_data)334 std::pair<iterator, bool>insert_check 335 (const intrusive_compare_key_type &key, insert_commit_data &commit_data) 336 { return index_type::insert_check(key, hash_function(), equal_function(), commit_data); } 337 insert_commit(value_type & val,insert_commit_data & commit_data)338 iterator insert_commit(value_type &val, insert_commit_data &commit_data) 339 { 340 iterator it = index_type::insert_commit(val, commit_data); 341 size_type cur_size = this->size(); 342 if(cur_size > this->bucket_count()){ 343 try{ 344 this->reserve(cur_size); 345 } 346 catch(...){ 347 //Strong guarantee: if something goes wrong 348 //we should remove the insertion. 349 // 350 //We can use the iterator because the hash function 351 //can't throw and this means that "reserve" will 352 //throw only because of the memory allocation: 353 //the iterator has not been invalidated. 354 index_type::erase(it); 355 throw; 356 } 357 } 358 return it; 359 } 360 }; 361 362 #if !defined(BOOST_INTERPROCESS_DOXYGEN_INVOKED) 363 364 //!Trait class to detect if an index is an intrusive 365 //!index 366 template<class MapConfig> 367 struct is_intrusive_index 368 <boost::interprocess::iunordered_set_index<MapConfig> > 369 { 370 static const bool value = true; 371 }; 372 #endif //#ifndef BOOST_INTERPROCESS_DOXYGEN_INVOKED 373 374 }} //namespace boost { namespace interprocess { 375 376 #include <boost/interprocess/detail/config_end.hpp> 377 378 #endif //#ifndef BOOST_INTERPROCESS_IUNORDERED_SET_INDEX_HPP 379