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 <new>
18 #include <memory>
19 #include <boost/array.hpp>
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
node_base()36 BOOST_FORCEINLINE attribute_value_set::node_base::node_base() :
37 m_pPrev(NULL),
38 m_pNext(NULL)
39 {
40 }
41
node(key_type const & key,mapped_type & data,bool dynamic)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(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;
get_nextboost::attribute_value_set::implementation::node_traits66 static node* get_next(const node* n) { return n->m_pNext; }
set_nextboost::attribute_value_set::implementation::node_traits67 static void set_next(node* n, node* next) { n->m_pNext = next; }
get_previousboost::attribute_value_set::implementation::node_traits68 static node* get_previous(const node* n) { return n->m_pPrev; }
set_previousboost::attribute_value_set::implementation::node_traits69 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
bucketboost::attribute_value_set::implementation::bucket94 bucket() : first(NULL), last(NULL) {}
95 };
96
97 //! A list of buckets
98 typedef boost::array< bucket, 1u << BOOST_LOG_HASH_TABLE_SIZE_LOG > buckets;
99
100 //! Element disposer
101 struct disposer
102 {
103 typedef void result_type;
operator ()boost::attribute_value_set::implementation::disposer104 void operator() (node* p) const BOOST_NOEXCEPT
105 {
106 if (!p->m_DynamicallyAllocated)
107 p->~node();
108 else
109 delete p;
110 }
111 };
112
113 private:
114 //! Pointer to the source-specific attributes
115 attribute_set_impl_type* m_pSourceAttributes;
116 //! Pointer to the thread-specific attributes
117 attribute_set_impl_type* m_pThreadAttributes;
118 //! Pointer to the global attributes
119 attribute_set_impl_type* m_pGlobalAttributes;
120
121 //! The container with elements
122 node_list m_Nodes;
123 //! The pointer to the end of the allocated elements within the storage
124 node* m_pEnd;
125 //! The pointer to the end of storage
126 node* m_pEOS;
127
128 //! Hash table buckets
129 buckets m_Buckets;
130
131 private:
132 //! Constructor
implementationboost::attribute_value_set::implementation133 implementation(
134 node* storage,
135 node* eos,
136 attribute_set_impl_type* source_attrs,
137 attribute_set_impl_type* thread_attrs,
138 attribute_set_impl_type* global_attrs
139 ) :
140 m_pSourceAttributes(source_attrs),
141 m_pThreadAttributes(thread_attrs),
142 m_pGlobalAttributes(global_attrs),
143 m_pEnd(storage),
144 m_pEOS(eos)
145 {
146 }
147
148 //! Destructor
~implementationboost::attribute_value_set::implementation149 ~implementation()
150 {
151 m_Nodes.clear_and_dispose(disposer());
152 }
153
154 //! The function allocates memory and creates the object
createboost::attribute_value_set::implementation155 static implementation* create(
156 size_type element_count,
157 attribute_set_impl_type* source_attrs,
158 attribute_set_impl_type* thread_attrs,
159 attribute_set_impl_type* global_attrs)
160 {
161 // Calculate the buffer size
162 const size_type header_size = sizeof(implementation) +
163 aux::alignment_gap_between< implementation, node >::value;
164 const size_type buffer_size = header_size + element_count * sizeof(node);
165
166 implementation* p = reinterpret_cast< implementation* >(stateless_allocator().allocate(buffer_size));
167 node* const storage = reinterpret_cast< node* >(reinterpret_cast< char* >(p) + header_size);
168 new (p) implementation(storage, storage + element_count, source_attrs, thread_attrs, global_attrs);
169
170 return p;
171 }
172
173 public:
174 //! The function allocates memory and creates the object
createboost::attribute_value_set::implementation175 static implementation* create(
176 attribute_set const& source_attrs,
177 attribute_set const& thread_attrs,
178 attribute_set const& global_attrs,
179 size_type reserve_count)
180 {
181 return create(
182 source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count,
183 source_attrs.m_pImpl,
184 thread_attrs.m_pImpl,
185 global_attrs.m_pImpl);
186 }
187
188 //! The function allocates memory and creates the object
createboost::attribute_value_set::implementation189 static implementation* create(
190 attribute_value_set const& source_attrs,
191 attribute_set const& thread_attrs,
192 attribute_set const& global_attrs,
193 size_type reserve_count)
194 {
195 implementation* p = create(
196 source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count,
197 NULL,
198 thread_attrs.m_pImpl,
199 global_attrs.m_pImpl);
200 p->copy_nodes_from(source_attrs.m_pImpl);
201 return p;
202 }
203
204 //! The function allocates memory and creates the object
createboost::attribute_value_set::implementation205 static implementation* create(
206 BOOST_RV_REF(attribute_value_set) source_attrs,
207 attribute_set const& thread_attrs,
208 attribute_set const& global_attrs,
209 size_type reserve_count)
210 {
211 implementation* p = source_attrs.m_pImpl;
212 source_attrs.m_pImpl = NULL;
213 p->m_pThreadAttributes = thread_attrs.m_pImpl;
214 p->m_pGlobalAttributes = global_attrs.m_pImpl;
215 return p;
216 }
217
218 //! The function allocates memory and creates the object
createboost::attribute_value_set::implementation219 static implementation* create(size_type reserve_count)
220 {
221 return create(reserve_count, NULL, NULL, NULL);
222 }
223
224 //! Creates a copy of the object
copyboost::attribute_value_set::implementation225 static implementation* copy(implementation* that)
226 {
227 // Create new object
228 implementation* p = create(that->size(), NULL, NULL, NULL);
229
230 // Copy all elements
231 p->copy_nodes_from(that);
232
233 return p;
234 }
235
236 //! Destroys the object and releases the memory
destroyboost::attribute_value_set::implementation237 static void destroy(implementation* p)
238 {
239 const size_type buffer_size = reinterpret_cast< char* >(p->m_pEOS) - reinterpret_cast< char* >(p);
240 p->~implementation();
241 stateless_allocator().deallocate(reinterpret_cast< stateless_allocator::pointer >(p), buffer_size);
242 }
243
244 //! Returns the pointer to the first element
beginboost::attribute_value_set::implementation245 node_base* begin()
246 {
247 freeze();
248 return m_Nodes.begin().pointed_node();
249 }
250 //! Returns the pointer after the last element
endboost::attribute_value_set::implementation251 node_base* end()
252 {
253 return m_Nodes.end().pointed_node();
254 }
255
256 //! Returns the number of elements in the container
sizeboost::attribute_value_set::implementation257 size_type size()
258 {
259 freeze();
260 return m_Nodes.size();
261 }
262
263 //! Looks for the element with an equivalent key
findboost::attribute_value_set::implementation264 node_base* find(key_type key)
265 {
266 // First try to find an acquired element
267 bucket& b = get_bucket(key.id());
268 node* p = b.first;
269 if (p)
270 {
271 // The bucket is not empty, search among the elements
272 p = find_in_bucket(key, b);
273 if (p->m_Value.first == key)
274 return p;
275 }
276
277 // Element not found, try to acquire the value from attribute sets
278 return freeze_node(key, b, p);
279 }
280
281 //! Freezes all elements of the container
freezeboost::attribute_value_set::implementation282 void freeze()
283 {
284 if (m_pSourceAttributes)
285 {
286 freeze_nodes_from(m_pSourceAttributes);
287 m_pSourceAttributes = NULL;
288 }
289 if (m_pThreadAttributes)
290 {
291 freeze_nodes_from(m_pThreadAttributes);
292 m_pThreadAttributes = NULL;
293 }
294 if (m_pGlobalAttributes)
295 {
296 freeze_nodes_from(m_pGlobalAttributes);
297 m_pGlobalAttributes = NULL;
298 }
299 }
300
301 //! Inserts an element
insertboost::attribute_value_set::implementation302 std::pair< node*, bool > insert(key_type key, mapped_type const& mapped)
303 {
304 bucket& b = get_bucket(key.id());
305 node* p = find_in_bucket(key, b);
306 if (!p || p->m_Value.first != key)
307 {
308 p = insert_node(key, b, p, mapped);
309 return std::pair< node*, bool >(p, true);
310 }
311 else
312 {
313 return std::pair< node*, bool >(p, false);
314 }
315 }
316
317 private:
318 //! The function returns a bucket for the specified element
get_bucketboost::attribute_value_set::implementation319 bucket& get_bucket(id_type id)
320 {
321 return m_Buckets[id & (buckets::static_size - 1u)];
322 }
323
324 //! Attempts to find an element with the specified key in the bucket
find_in_bucketboost::attribute_value_set::implementation325 node* find_in_bucket(key_type key, bucket const& b)
326 {
327 typedef node_list::node_traits node_traits;
328 typedef node_list::value_traits value_traits;
329
330 // All elements within the bucket are sorted to speedup the search.
331 node* p = b.first;
332 while (p != b.last && p->m_Value.first.id() < key.id())
333 {
334 p = value_traits::to_value_ptr(node_traits::get_next(p));
335 }
336
337 return p;
338 }
339
340 //! Acquires the attribute value from the attribute sets
freeze_nodeboost::attribute_value_set::implementation341 node_base* freeze_node(key_type key, bucket& b, node* where)
342 {
343 attribute_set::iterator it;
344 if (m_pSourceAttributes)
345 {
346 it = m_pSourceAttributes->find(key);
347 if (it != m_pSourceAttributes->end())
348 {
349 // The attribute is found, acquiring the value
350 return insert_node(key, b, where, it->second.get_value());
351 }
352 }
353
354 if (m_pThreadAttributes)
355 {
356 it = m_pThreadAttributes->find(key);
357 if (it != m_pThreadAttributes->end())
358 {
359 // The attribute is found, acquiring the value
360 return insert_node(key, b, where, it->second.get_value());
361 }
362 }
363
364 if (m_pGlobalAttributes)
365 {
366 it = m_pGlobalAttributes->find(key);
367 if (it != m_pGlobalAttributes->end())
368 {
369 // The attribute is found, acquiring the value
370 return insert_node(key, b, where, it->second.get_value());
371 }
372 }
373
374 // The attribute is not found
375 return m_Nodes.end().pointed_node();
376 }
377
378 //! The function inserts a node into the container
insert_nodeboost::attribute_value_set::implementation379 node* insert_node(key_type key, bucket& b, node* where, mapped_type data)
380 {
381 node* p;
382 if (m_pEnd != m_pEOS)
383 {
384 p = m_pEnd++;
385 new (p) node(key, data, false);
386 }
387 else
388 {
389 p = new node(key, data, true);
390 }
391
392 node_list::iterator it;
393 if (b.first == NULL)
394 {
395 // The bucket is empty
396 b.first = b.last = p;
397 it = m_Nodes.end();
398 }
399 else if (where == b.last && key.id() > where->m_Value.first.id())
400 {
401 // The new element should become the last element of the bucket
402 it = m_Nodes.iterator_to(*where);
403 ++it;
404 b.last = p;
405 }
406 else if (where == b.first)
407 {
408 // The new element should become the first element of the bucket
409 it = m_Nodes.iterator_to(*where);
410 b.first = p;
411 }
412 else
413 {
414 // The new element should be within the bucket
415 it = m_Nodes.iterator_to(*where);
416 }
417
418 m_Nodes.insert(it, *p);
419
420 return p;
421 }
422
423 //! Acquires attribute values from the set of attributes
freeze_nodes_fromboost::attribute_value_set::implementation424 void freeze_nodes_from(attribute_set_impl_type* attrs)
425 {
426 attribute_set::const_iterator it = attrs->begin(), end = attrs->end();
427 for (; it != end; ++it)
428 {
429 key_type key = it->first;
430 bucket& b = get_bucket(key.id());
431 node* p = b.first;
432 if (p)
433 {
434 p = find_in_bucket(key, b);
435 if (p->m_Value.first == key)
436 continue; // the element is already frozen
437 }
438
439 insert_node(key, b, p, it->second.get_value());
440 }
441 }
442
443 //! Copies nodes of the container
copy_nodes_fromboost::attribute_value_set::implementation444 void copy_nodes_from(implementation* from)
445 {
446 // Copy all elements
447 node_list::iterator it = from->m_Nodes.begin(), end = from->m_Nodes.end();
448 for (; it != end; ++it)
449 {
450 node* n = m_pEnd++;
451 mapped_type data = it->m_Value.second;
452 new (n) node(it->m_Value.first, data, false);
453 m_Nodes.push_back(*n);
454
455 // Since nodes within buckets are ordered, we can simply append the node to the end of the bucket
456 bucket& b = get_bucket(n->m_Value.first.id());
457 if (b.first == NULL)
458 b.first = b.last = n;
459 else
460 b.last = n;
461 }
462 }
463 };
464
465 //! The constructor creates an empty set
attribute_value_set(size_type reserve_count)466 BOOST_LOG_API attribute_value_set::attribute_value_set(
467 size_type reserve_count
468 ) :
469 m_pImpl(implementation::create(reserve_count))
470 {
471 }
472
473 //! The constructor adopts three attribute sets to the set
attribute_value_set(attribute_set const & source_attrs,attribute_set const & thread_attrs,attribute_set const & global_attrs,size_type reserve_count)474 BOOST_LOG_API attribute_value_set::attribute_value_set(
475 attribute_set const& source_attrs,
476 attribute_set const& thread_attrs,
477 attribute_set const& global_attrs,
478 size_type reserve_count
479 ) :
480 m_pImpl(implementation::create(source_attrs, thread_attrs, global_attrs, reserve_count))
481 {
482 }
483
484 //! The constructor adopts three attribute sets to the set
attribute_value_set(attribute_value_set const & source_attrs,attribute_set const & thread_attrs,attribute_set const & global_attrs,size_type reserve_count)485 BOOST_LOG_API attribute_value_set::attribute_value_set(
486 attribute_value_set const& source_attrs,
487 attribute_set const& thread_attrs,
488 attribute_set const& global_attrs,
489 size_type reserve_count
490 ) :
491 m_pImpl(implementation::create(source_attrs, thread_attrs, global_attrs, reserve_count))
492 {
493 }
494
495 //! The constructor adopts three attribute sets to the set
construct(attribute_value_set & source_attrs,attribute_set const & thread_attrs,attribute_set const & global_attrs,size_type reserve_count)496 BOOST_LOG_API void attribute_value_set::construct(
497 attribute_value_set& source_attrs,
498 attribute_set const& thread_attrs,
499 attribute_set const& global_attrs,
500 size_type reserve_count
501 )
502 {
503 m_pImpl = implementation::create(boost::move(source_attrs), thread_attrs, global_attrs, reserve_count);
504 }
505
506 //! Copy constructor
attribute_value_set(attribute_value_set const & that)507 BOOST_LOG_API attribute_value_set::attribute_value_set(attribute_value_set const& that)
508 {
509 if (that.m_pImpl)
510 m_pImpl = implementation::copy(that.m_pImpl);
511 else
512 m_pImpl = NULL;
513 }
514
515 //! Destructor
~attribute_value_set()516 BOOST_LOG_API attribute_value_set::~attribute_value_set() BOOST_NOEXCEPT
517 {
518 if (m_pImpl)
519 {
520 implementation::destroy(m_pImpl);
521 m_pImpl = NULL;
522 }
523 }
524
525 // Iterator generators
526 BOOST_LOG_API attribute_value_set::const_iterator
begin() const527 attribute_value_set::begin() const
528 {
529 return const_iterator(m_pImpl->begin(), const_cast< attribute_value_set* >(this));
530 }
531
532 BOOST_LOG_API attribute_value_set::const_iterator
end() const533 attribute_value_set::end() const
534 {
535 return const_iterator(m_pImpl->end(), const_cast< attribute_value_set* >(this));
536 }
537
538 //! The method returns number of elements in the container
539 BOOST_LOG_API attribute_value_set::size_type
size() const540 attribute_value_set::size() const
541 {
542 return m_pImpl->size();
543 }
544
545 //! Internal lookup implementation
546 BOOST_LOG_API attribute_value_set::const_iterator
find(key_type key) const547 attribute_value_set::find(key_type key) const
548 {
549 return const_iterator(m_pImpl->find(key), const_cast< attribute_value_set* >(this));
550 }
551
552 //! The method acquires values of all adopted attributes. Users don't need to call it, since will always get an already frozen set.
freeze()553 BOOST_LOG_API void attribute_value_set::freeze()
554 {
555 m_pImpl->freeze();
556 }
557
558 //! Inserts an element into the set
559 BOOST_LOG_API std::pair< attribute_value_set::const_iterator, bool >
insert(key_type key,mapped_type const & mapped)560 attribute_value_set::insert(key_type key, mapped_type const& mapped)
561 {
562 std::pair< node*, bool > res = m_pImpl->insert(key, mapped);
563 return std::pair< const_iterator, bool >(const_iterator(res.first, this), res.second);
564 }
565
566 BOOST_LOG_CLOSE_NAMESPACE // namespace log
567
568 } // namespace boost
569
570 #include <boost/log/detail/footer.hpp>
571