]>
Commit | Line | Data |
---|---|---|
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 | { | |
69 | 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 | ||
76 | 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 | ||
83 | 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 | { | |
94 | 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 | ||
101 | 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 | { | |
121 | 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 | ||
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 | ||
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 | ||
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 | ||
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 | ||
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 | |
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 | ||
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 | |
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. | |
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 | ||
326 | iterator find(const intrusive_compare_key_type &key) | |
327 | { return index_type::find(key, hash_function(), equal_function()); } | |
328 | ||
329 | const_iterator find(const intrusive_compare_key_type &key) const | |
330 | { return index_type::find(key, hash_function(), equal_function()); } | |
331 | ||
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 | ||
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 |