1 | /* |
2 | * Copyright Andrey Semashev 2007 - 2015. |
3 | * Distributed under the Boost Software License, Version 1.0. |
4 | * (See accompanying file LICENSE_1_0.txt or copy at |
5 | * http://www.boost.org/LICENSE_1_0.txt) |
6 | */ |
7 | /*! |
8 | * \file attribute_value_set.cpp |
9 | * \author Andrey Semashev |
10 | * \date 19.04.2007 |
11 | * |
12 | * \brief This header is the Boost.Log library implementation, see the library documentation |
13 | * at http://www.boost.org/doc/libs/release/libs/log/doc/html/index.html. |
14 | */ |
15 | |
16 | #include <boost/log/detail/config.hpp> |
17 | #include <cstddef> |
18 | #include <new> |
19 | #include <memory> |
20 | #include <boost/intrusive/options.hpp> |
21 | #include <boost/intrusive/list.hpp> |
22 | #include <boost/intrusive/link_mode.hpp> |
23 | #include <boost/intrusive/derivation_value_traits.hpp> |
24 | #include <boost/log/attributes/attribute_name.hpp> |
25 | #include <boost/log/attributes/attribute_value.hpp> |
26 | #include <boost/log/attributes/attribute_value_set.hpp> |
27 | #include "alignment_gap_between.hpp" |
28 | #include "attribute_set_impl.hpp" |
29 | #include "stateless_allocator.hpp" |
30 | #include <boost/log/detail/header.hpp> |
31 | |
32 | namespace boost { |
33 | |
34 | BOOST_LOG_OPEN_NAMESPACE |
35 | |
36 | BOOST_FORCEINLINE attribute_value_set::node_base::node_base() : |
37 | m_pPrev(NULL), |
38 | m_pNext(NULL) |
39 | { |
40 | } |
41 | |
42 | BOOST_FORCEINLINE attribute_value_set::node::node(key_type const& key, mapped_type& data, bool dynamic) : |
43 | node_base(), |
44 | m_Value(key, mapped_type()), |
45 | m_DynamicallyAllocated(dynamic) |
46 | { |
47 | m_Value.second.swap(that&: data); |
48 | } |
49 | |
50 | //! Container implementation |
51 | struct attribute_value_set::implementation |
52 | { |
53 | public: |
54 | typedef key_type::id_type id_type; |
55 | |
56 | private: |
57 | typedef attribute_set::implementation attribute_set_impl_type; |
58 | typedef boost::log::aux::stateless_allocator< char > stateless_allocator; |
59 | |
60 | //! Node base class traits for the intrusive list |
61 | struct node_traits |
62 | { |
63 | typedef node_base node; |
64 | typedef node* node_ptr; |
65 | typedef node const* const_node_ptr; |
66 | static node* get_next(const node* n) { return n->m_pNext; } |
67 | static void set_next(node* n, node* next) { n->m_pNext = next; } |
68 | static node* get_previous(const node* n) { return n->m_pPrev; } |
69 | static void set_previous(node* n, node* prev) { n->m_pPrev = prev; } |
70 | }; |
71 | |
72 | //! Contained node traits for the intrusive list |
73 | typedef intrusive::derivation_value_traits< |
74 | node, |
75 | node_traits, |
76 | intrusive::normal_link |
77 | > value_traits; |
78 | |
79 | //! A container that provides iteration through elements of the container |
80 | typedef intrusive::list< |
81 | node, |
82 | intrusive::value_traits< value_traits >, |
83 | intrusive::constant_time_size< true > |
84 | > node_list; |
85 | |
86 | //! A hash table bucket |
87 | struct bucket |
88 | { |
89 | //! Points to the first element in the bucket |
90 | node* first; |
91 | //! Points to the last element in the bucket (not the one after the last!) |
92 | node* last; |
93 | |
94 | bucket() : first(NULL), last(NULL) {} |
95 | }; |
96 | |
97 | //! Element disposer |
98 | struct disposer |
99 | { |
100 | typedef void result_type; |
101 | void operator() (node* p) const BOOST_NOEXCEPT |
102 | { |
103 | if (!p->m_DynamicallyAllocated) |
104 | p->~node(); |
105 | else |
106 | delete p; |
107 | } |
108 | }; |
109 | |
110 | private: |
111 | //! Pointer to the source-specific attributes |
112 | attribute_set_impl_type* m_pSourceAttributes; |
113 | //! Pointer to the thread-specific attributes |
114 | attribute_set_impl_type* m_pThreadAttributes; |
115 | //! Pointer to the global attributes |
116 | attribute_set_impl_type* m_pGlobalAttributes; |
117 | |
118 | //! The container with elements |
119 | node_list m_Nodes; |
120 | //! The pointer to the end of the allocated elements within the storage |
121 | node* m_pEnd; |
122 | //! The pointer to the end of storage |
123 | node* m_pEOS; |
124 | |
125 | //! Number of buckets in the hash table |
126 | static BOOST_CONSTEXPR_OR_CONST std::size_t bucket_count = static_cast< std::size_t >(1u) << BOOST_LOG_HASH_TABLE_SIZE_LOG; |
127 | //! Hash table buckets |
128 | bucket m_Buckets[bucket_count]; |
129 | |
130 | private: |
131 | //! Constructor |
132 | implementation( |
133 | node* storage, |
134 | node* eos, |
135 | attribute_set_impl_type* source_attrs, |
136 | attribute_set_impl_type* thread_attrs, |
137 | attribute_set_impl_type* global_attrs |
138 | ) : |
139 | m_pSourceAttributes(source_attrs), |
140 | m_pThreadAttributes(thread_attrs), |
141 | m_pGlobalAttributes(global_attrs), |
142 | m_pEnd(storage), |
143 | m_pEOS(eos) |
144 | { |
145 | } |
146 | |
147 | //! Destructor |
148 | ~implementation() |
149 | { |
150 | m_Nodes.clear_and_dispose(disposer: disposer()); |
151 | } |
152 | |
153 | //! The function allocates memory and creates the object |
154 | static implementation* create( |
155 | size_type element_count, |
156 | attribute_set_impl_type* source_attrs, |
157 | attribute_set_impl_type* thread_attrs, |
158 | attribute_set_impl_type* global_attrs) |
159 | { |
160 | // Calculate the buffer size |
161 | const size_type = sizeof(implementation) + |
162 | aux::alignment_gap_between< implementation, node >::value; |
163 | const size_type buffer_size = header_size + element_count * sizeof(node); |
164 | |
165 | implementation* p = reinterpret_cast< implementation* >(stateless_allocator().allocate(n: buffer_size)); |
166 | node* const storage = reinterpret_cast< node* >(reinterpret_cast< char* >(p) + header_size); |
167 | new (p) implementation(storage, storage + element_count, source_attrs, thread_attrs, global_attrs); |
168 | |
169 | return p; |
170 | } |
171 | |
172 | public: |
173 | //! The function allocates memory and creates the object |
174 | static implementation* create( |
175 | attribute_set const& source_attrs, |
176 | attribute_set const& thread_attrs, |
177 | attribute_set const& global_attrs, |
178 | size_type reserve_count) |
179 | { |
180 | return create( |
181 | element_count: source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count, |
182 | source_attrs: source_attrs.m_pImpl, |
183 | thread_attrs: thread_attrs.m_pImpl, |
184 | global_attrs: global_attrs.m_pImpl); |
185 | } |
186 | |
187 | //! The function allocates memory and creates the object |
188 | static implementation* create( |
189 | attribute_value_set const& source_attrs, |
190 | attribute_set const& thread_attrs, |
191 | attribute_set const& global_attrs, |
192 | size_type reserve_count) |
193 | { |
194 | implementation* p = create( |
195 | element_count: source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count, |
196 | NULL, |
197 | thread_attrs: thread_attrs.m_pImpl, |
198 | global_attrs: global_attrs.m_pImpl); |
199 | p->copy_nodes_from(from: source_attrs.m_pImpl); |
200 | return p; |
201 | } |
202 | |
203 | //! The function allocates memory and creates the object |
204 | static implementation* create( |
205 | BOOST_RV_REF(attribute_value_set) source_attrs, |
206 | attribute_set const& thread_attrs, |
207 | attribute_set const& global_attrs, |
208 | size_type reserve_count) |
209 | { |
210 | implementation* p = source_attrs.m_pImpl; |
211 | source_attrs.m_pImpl = NULL; |
212 | p->m_pThreadAttributes = thread_attrs.m_pImpl; |
213 | p->m_pGlobalAttributes = global_attrs.m_pImpl; |
214 | return p; |
215 | } |
216 | |
217 | //! The function allocates memory and creates the object |
218 | static implementation* create(size_type reserve_count) |
219 | { |
220 | return create(element_count: reserve_count, NULL, NULL, NULL); |
221 | } |
222 | |
223 | //! Creates a copy of the object |
224 | static implementation* copy(implementation* that) |
225 | { |
226 | // Create new object |
227 | implementation* p = create(element_count: that->size(), NULL, NULL, NULL); |
228 | |
229 | // Copy all elements |
230 | p->copy_nodes_from(from: that); |
231 | |
232 | return p; |
233 | } |
234 | |
235 | //! Destroys the object and releases the memory |
236 | static void destroy(implementation* p) |
237 | { |
238 | const size_type buffer_size = reinterpret_cast< char* >(p->m_pEOS) - reinterpret_cast< char* >(p); |
239 | p->~implementation(); |
240 | stateless_allocator().deallocate(p: reinterpret_cast< stateless_allocator::pointer >(p), buffer_size); |
241 | } |
242 | |
243 | //! Returns the pointer to the first element |
244 | node_base* begin() |
245 | { |
246 | freeze(); |
247 | return m_Nodes.begin().pointed_node(); |
248 | } |
249 | //! Returns the pointer after the last element |
250 | node_base* end() |
251 | { |
252 | return m_Nodes.end().pointed_node(); |
253 | } |
254 | |
255 | //! Returns the number of elements in the container |
256 | size_type size() |
257 | { |
258 | freeze(); |
259 | return m_Nodes.size(); |
260 | } |
261 | |
262 | //! Looks for the element with an equivalent key |
263 | node_base* find(key_type key) |
264 | { |
265 | // First try to find an acquired element |
266 | bucket& b = get_bucket(id: key.id()); |
267 | node* p = b.first; |
268 | if (p) |
269 | { |
270 | // The bucket is not empty, search among the elements |
271 | p = find_in_bucket(key, b); |
272 | if (p->m_Value.first == key) |
273 | return p; |
274 | } |
275 | |
276 | // Element not found, try to acquire the value from attribute sets |
277 | return freeze_node(key, b, where: p); |
278 | } |
279 | |
280 | //! Freezes all elements of the container |
281 | void freeze() |
282 | { |
283 | if (m_pSourceAttributes) |
284 | { |
285 | freeze_nodes_from(attrs: m_pSourceAttributes); |
286 | m_pSourceAttributes = NULL; |
287 | } |
288 | if (m_pThreadAttributes) |
289 | { |
290 | freeze_nodes_from(attrs: m_pThreadAttributes); |
291 | m_pThreadAttributes = NULL; |
292 | } |
293 | if (m_pGlobalAttributes) |
294 | { |
295 | freeze_nodes_from(attrs: m_pGlobalAttributes); |
296 | m_pGlobalAttributes = NULL; |
297 | } |
298 | } |
299 | |
300 | //! Inserts an element |
301 | std::pair< node*, bool > insert(key_type key, mapped_type const& mapped) |
302 | { |
303 | bucket& b = get_bucket(id: key.id()); |
304 | node* p = find_in_bucket(key, b); |
305 | if (!p || p->m_Value.first != key) |
306 | { |
307 | p = insert_node(key, b, where: p, data: mapped); |
308 | return std::pair< node*, bool >(p, true); |
309 | } |
310 | else |
311 | { |
312 | return std::pair< node*, bool >(p, false); |
313 | } |
314 | } |
315 | |
316 | private: |
317 | //! The function returns a bucket for the specified element |
318 | bucket& get_bucket(id_type id) |
319 | { |
320 | return m_Buckets[id & (bucket_count - 1u)]; |
321 | } |
322 | |
323 | //! Attempts to find an element with the specified key in the bucket |
324 | node* find_in_bucket(key_type key, bucket const& b) |
325 | { |
326 | typedef node_list::node_traits node_traits; |
327 | typedef node_list::value_traits value_traits; |
328 | |
329 | // All elements within the bucket are sorted to speedup the search. |
330 | node* p = b.first; |
331 | while (p != b.last && p->m_Value.first.id() < key.id()) |
332 | { |
333 | p = value_traits::to_value_ptr(n: node_traits::get_next(n: p)); |
334 | } |
335 | |
336 | return p; |
337 | } |
338 | |
339 | //! Acquires the attribute value from the attribute sets |
340 | node_base* freeze_node(key_type key, bucket& b, node* where) |
341 | { |
342 | attribute_set::iterator it; |
343 | if (m_pSourceAttributes) |
344 | { |
345 | it = m_pSourceAttributes->find(key); |
346 | if (it != m_pSourceAttributes->end()) |
347 | { |
348 | // The attribute is found, acquiring the value |
349 | return insert_node(key, b, where, data: it->second.get_value()); |
350 | } |
351 | } |
352 | |
353 | if (m_pThreadAttributes) |
354 | { |
355 | it = m_pThreadAttributes->find(key); |
356 | if (it != m_pThreadAttributes->end()) |
357 | { |
358 | // The attribute is found, acquiring the value |
359 | return insert_node(key, b, where, data: it->second.get_value()); |
360 | } |
361 | } |
362 | |
363 | if (m_pGlobalAttributes) |
364 | { |
365 | it = m_pGlobalAttributes->find(key); |
366 | if (it != m_pGlobalAttributes->end()) |
367 | { |
368 | // The attribute is found, acquiring the value |
369 | return insert_node(key, b, where, data: it->second.get_value()); |
370 | } |
371 | } |
372 | |
373 | // The attribute is not found |
374 | return m_Nodes.end().pointed_node(); |
375 | } |
376 | |
377 | //! The function inserts a node into the container |
378 | node* insert_node(key_type key, bucket& b, node* where, mapped_type data) |
379 | { |
380 | node* p; |
381 | if (m_pEnd != m_pEOS) |
382 | { |
383 | p = m_pEnd++; |
384 | new (p) node(key, data, false); |
385 | } |
386 | else |
387 | { |
388 | p = new node(key, data, true); |
389 | } |
390 | |
391 | node_list::iterator it; |
392 | if (b.first == NULL) |
393 | { |
394 | // The bucket is empty |
395 | b.first = b.last = p; |
396 | it = m_Nodes.end(); |
397 | } |
398 | else if (where == b.last && key.id() > where->m_Value.first.id()) |
399 | { |
400 | // The new element should become the last element of the bucket |
401 | it = m_Nodes.iterator_to(value&: *where); |
402 | ++it; |
403 | b.last = p; |
404 | } |
405 | else if (where == b.first) |
406 | { |
407 | // The new element should become the first element of the bucket |
408 | it = m_Nodes.iterator_to(value&: *where); |
409 | b.first = p; |
410 | } |
411 | else |
412 | { |
413 | // The new element should be within the bucket |
414 | it = m_Nodes.iterator_to(value&: *where); |
415 | } |
416 | |
417 | m_Nodes.insert(p: it, value&: *p); |
418 | |
419 | return p; |
420 | } |
421 | |
422 | //! Acquires attribute values from the set of attributes |
423 | void freeze_nodes_from(attribute_set_impl_type* attrs) |
424 | { |
425 | attribute_set::const_iterator it = attrs->begin(), end = attrs->end(); |
426 | for (; it != end; ++it) |
427 | { |
428 | key_type key = it->first; |
429 | bucket& b = get_bucket(id: key.id()); |
430 | node* p = b.first; |
431 | if (p) |
432 | { |
433 | p = find_in_bucket(key, b); |
434 | if (p->m_Value.first == key) |
435 | continue; // the element is already frozen |
436 | } |
437 | |
438 | insert_node(key, b, where: p, data: it->second.get_value()); |
439 | } |
440 | } |
441 | |
442 | //! Copies nodes of the container |
443 | void copy_nodes_from(implementation* from) |
444 | { |
445 | // Copy all elements |
446 | node_list::iterator it = from->m_Nodes.begin(), end = from->m_Nodes.end(); |
447 | for (; it != end; ++it) |
448 | { |
449 | node* n = m_pEnd++; |
450 | mapped_type data = it->m_Value.second; |
451 | new (n) node(it->m_Value.first, data, false); |
452 | m_Nodes.push_back(value&: *n); |
453 | |
454 | // Since nodes within buckets are ordered, we can simply append the node to the end of the bucket |
455 | bucket& b = get_bucket(id: n->m_Value.first.id()); |
456 | if (b.first == NULL) |
457 | b.first = b.last = n; |
458 | else |
459 | b.last = n; |
460 | } |
461 | } |
462 | }; |
463 | |
464 | //! The constructor creates an empty set |
465 | BOOST_LOG_API attribute_value_set::attribute_value_set( |
466 | size_type reserve_count |
467 | ) : |
468 | m_pImpl(implementation::create(reserve_count)) |
469 | { |
470 | } |
471 | |
472 | //! The constructor adopts three attribute sets to the set |
473 | BOOST_LOG_API attribute_value_set::attribute_value_set( |
474 | attribute_set const& source_attrs, |
475 | attribute_set const& thread_attrs, |
476 | attribute_set const& global_attrs, |
477 | size_type reserve_count |
478 | ) : |
479 | m_pImpl(implementation::create(source_attrs, thread_attrs, global_attrs, reserve_count)) |
480 | { |
481 | } |
482 | |
483 | //! The constructor adopts three attribute sets to the set |
484 | BOOST_LOG_API attribute_value_set::attribute_value_set( |
485 | attribute_value_set const& source_attrs, |
486 | attribute_set const& thread_attrs, |
487 | attribute_set const& global_attrs, |
488 | size_type reserve_count |
489 | ) : |
490 | m_pImpl(implementation::create(source_attrs, thread_attrs, global_attrs, reserve_count)) |
491 | { |
492 | } |
493 | |
494 | //! The constructor adopts three attribute sets to the set |
495 | BOOST_LOG_API void attribute_value_set::construct( |
496 | attribute_value_set& source_attrs, |
497 | attribute_set const& thread_attrs, |
498 | attribute_set const& global_attrs, |
499 | size_type reserve_count |
500 | ) |
501 | { |
502 | m_pImpl = implementation::create(source_attrs: boost::move(t&: source_attrs), thread_attrs, global_attrs, reserve_count); |
503 | } |
504 | |
505 | //! Copy constructor |
506 | BOOST_LOG_API attribute_value_set::attribute_value_set(attribute_value_set const& that) |
507 | { |
508 | if (that.m_pImpl) |
509 | m_pImpl = implementation::copy(that: that.m_pImpl); |
510 | else |
511 | m_pImpl = NULL; |
512 | } |
513 | |
514 | //! Destructor |
515 | BOOST_LOG_API attribute_value_set::~attribute_value_set() BOOST_NOEXCEPT |
516 | { |
517 | if (m_pImpl) |
518 | { |
519 | implementation::destroy(p: m_pImpl); |
520 | m_pImpl = NULL; |
521 | } |
522 | } |
523 | |
524 | // Iterator generators |
525 | BOOST_LOG_API attribute_value_set::const_iterator |
526 | attribute_value_set::begin() const |
527 | { |
528 | return const_iterator(m_pImpl->begin(), const_cast< attribute_value_set* >(this)); |
529 | } |
530 | |
531 | BOOST_LOG_API attribute_value_set::const_iterator |
532 | attribute_value_set::end() const |
533 | { |
534 | return const_iterator(m_pImpl->end(), const_cast< attribute_value_set* >(this)); |
535 | } |
536 | |
537 | //! The method returns number of elements in the container |
538 | BOOST_LOG_API attribute_value_set::size_type |
539 | attribute_value_set::size() const |
540 | { |
541 | return m_pImpl->size(); |
542 | } |
543 | |
544 | //! Internal lookup implementation |
545 | BOOST_LOG_API attribute_value_set::const_iterator |
546 | attribute_value_set::find(key_type key) const |
547 | { |
548 | return const_iterator(m_pImpl->find(key), const_cast< attribute_value_set* >(this)); |
549 | } |
550 | |
551 | //! The method acquires values of all adopted attributes. Users don't need to call it, since will always get an already frozen set. |
552 | BOOST_LOG_API void attribute_value_set::freeze() |
553 | { |
554 | m_pImpl->freeze(); |
555 | } |
556 | |
557 | //! Inserts an element into the set |
558 | BOOST_LOG_API std::pair< attribute_value_set::const_iterator, bool > |
559 | attribute_value_set::insert(key_type key, mapped_type const& mapped) |
560 | { |
561 | std::pair< node*, bool > res = m_pImpl->insert(key, mapped); |
562 | return std::pair< const_iterator, bool >(const_iterator(res.first, this), res.second); |
563 | } |
564 | |
565 | BOOST_LOG_CLOSE_NAMESPACE // namespace log |
566 | |
567 | } // namespace boost |
568 | |
569 | #include <boost/log/detail/footer.hpp> |
570 | |