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 <new>
17 #include <memory>
18 #include <boost/array.hpp>
19 #include <boost/intrusive/options.hpp>
20 #include <boost/intrusive/list.hpp>
21 #include <boost/intrusive/link_mode.hpp>
22 #include <boost/intrusive/derivation_value_traits.hpp>
23 #include <boost/log/attributes/attribute_name.hpp>
24 #include <boost/log/attributes/attribute_value.hpp>
25 #include <boost/log/attributes/attribute_value_set.hpp>
26 #include "alignment_gap_between.hpp"
27 #include "attribute_set_impl.hpp"
28 #include "stateless_allocator.hpp"
29 #include <boost/log/detail/header.hpp>
30
31 namespace boost {
32
33 BOOST_LOG_OPEN_NAMESPACE
34
node_base()35 BOOST_FORCEINLINE attribute_value_set::node_base::node_base() :
36 m_pPrev(NULL),
37 m_pNext(NULL)
38 {
39 }
40
node(key_type const & key,mapped_type & data,bool dynamic)41 BOOST_FORCEINLINE attribute_value_set::node::node(key_type const& key, mapped_type& data, bool dynamic) :
42 node_base(),
43 m_Value(key, mapped_type()),
44 m_DynamicallyAllocated(dynamic)
45 {
46 m_Value.second.swap(data);
47 }
48
49 //! Container implementation
50 struct attribute_value_set::implementation
51 {
52 public:
53 typedef key_type::id_type id_type;
54
55 private:
56 typedef attribute_set::implementation attribute_set_impl_type;
57 typedef boost::log::aux::stateless_allocator< char > stateless_allocator;
58
59 //! Node base class traits for the intrusive list
60 struct node_traits
61 {
62 typedef node_base node;
63 typedef node* node_ptr;
64 typedef node const* const_node_ptr;
get_nextboost::attribute_value_set::implementation::node_traits65 static node* get_next(const node* n) { return n->m_pNext; }
set_nextboost::attribute_value_set::implementation::node_traits66 static void set_next(node* n, node* next) { n->m_pNext = next; }
get_previousboost::attribute_value_set::implementation::node_traits67 static node* get_previous(const node* n) { return n->m_pPrev; }
set_previousboost::attribute_value_set::implementation::node_traits68 static void set_previous(node* n, node* prev) { n->m_pPrev = prev; }
69 };
70
71 //! Contained node traits for the intrusive list
72 typedef intrusive::derivation_value_traits<
73 node,
74 node_traits,
75 intrusive::normal_link
76 > value_traits;
77
78 //! A container that provides iteration through elements of the container
79 typedef intrusive::list<
80 node,
81 intrusive::value_traits< value_traits >,
82 intrusive::constant_time_size< true >
83 > node_list;
84
85 //! A hash table bucket
86 struct bucket
87 {
88 //! Points to the first element in the bucket
89 node* first;
90 //! Points to the last element in the bucket (not the one after the last!)
91 node* last;
92
bucketboost::attribute_value_set::implementation::bucket93 bucket() : first(NULL), last(NULL) {}
94 };
95
96 //! A list of buckets
97 typedef boost::array< bucket, 1u << BOOST_LOG_HASH_TABLE_SIZE_LOG > buckets;
98
99 //! Element disposer
100 struct disposer
101 {
102 typedef void result_type;
operator ()boost::attribute_value_set::implementation::disposer103 void operator() (node* p) const BOOST_NOEXCEPT
104 {
105 if (!p->m_DynamicallyAllocated)
106 p->~node();
107 else
108 delete p;
109 }
110 };
111
112 private:
113 //! Pointer to the source-specific attributes
114 attribute_set_impl_type* m_pSourceAttributes;
115 //! Pointer to the thread-specific attributes
116 attribute_set_impl_type* m_pThreadAttributes;
117 //! Pointer to the global attributes
118 attribute_set_impl_type* m_pGlobalAttributes;
119
120 //! The container with elements
121 node_list m_Nodes;
122 //! The pointer to the end of the allocated elements within the storage
123 node* m_pEnd;
124 //! The pointer to the end of storage
125 node* m_pEOS;
126
127 //! Hash table buckets
128 buckets m_Buckets;
129
130 private:
131 //! Constructor
implementationboost::attribute_value_set::implementation132 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
~implementationboost::attribute_value_set::implementation148 ~implementation()
149 {
150 m_Nodes.clear_and_dispose(disposer());
151 }
152
153 //! The function allocates memory and creates the object
createboost::attribute_value_set::implementation154 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 header_size = 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(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
createboost::attribute_value_set::implementation174 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 source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count,
182 source_attrs.m_pImpl,
183 thread_attrs.m_pImpl,
184 global_attrs.m_pImpl);
185 }
186
187 //! The function allocates memory and creates the object
createboost::attribute_value_set::implementation188 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 source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count,
196 NULL,
197 thread_attrs.m_pImpl,
198 global_attrs.m_pImpl);
199 p->copy_nodes_from(source_attrs.m_pImpl);
200 return p;
201 }
202
203 //! The function allocates memory and creates the object
createboost::attribute_value_set::implementation204 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
createboost::attribute_value_set::implementation218 static implementation* create(size_type reserve_count)
219 {
220 return create(reserve_count, NULL, NULL, NULL);
221 }
222
223 //! Creates a copy of the object
copyboost::attribute_value_set::implementation224 static implementation* copy(implementation* that)
225 {
226 // Create new object
227 implementation* p = create(that->size(), NULL, NULL, NULL);
228
229 // Copy all elements
230 p->copy_nodes_from(that);
231
232 return p;
233 }
234
235 //! Destroys the object and releases the memory
destroyboost::attribute_value_set::implementation236 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(reinterpret_cast< stateless_allocator::pointer >(p), buffer_size);
241 }
242
243 //! Returns the pointer to the first element
beginboost::attribute_value_set::implementation244 node_base* begin()
245 {
246 freeze();
247 return m_Nodes.begin().pointed_node();
248 }
249 //! Returns the pointer after the last element
endboost::attribute_value_set::implementation250 node_base* end()
251 {
252 return m_Nodes.end().pointed_node();
253 }
254
255 //! Returns the number of elements in the container
sizeboost::attribute_value_set::implementation256 size_type size()
257 {
258 freeze();
259 return m_Nodes.size();
260 }
261
262 //! Looks for the element with an equivalent key
findboost::attribute_value_set::implementation263 node_base* find(key_type key)
264 {
265 // First try to find an acquired element
266 bucket& b = get_bucket(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, p);
278 }
279
280 //! Freezes all elements of the container
freezeboost::attribute_value_set::implementation281 void freeze()
282 {
283 if (m_pSourceAttributes)
284 {
285 freeze_nodes_from(m_pSourceAttributes);
286 m_pSourceAttributes = NULL;
287 }
288 if (m_pThreadAttributes)
289 {
290 freeze_nodes_from(m_pThreadAttributes);
291 m_pThreadAttributes = NULL;
292 }
293 if (m_pGlobalAttributes)
294 {
295 freeze_nodes_from(m_pGlobalAttributes);
296 m_pGlobalAttributes = NULL;
297 }
298 }
299
300 //! Inserts an element
insertboost::attribute_value_set::implementation301 std::pair< node*, bool > insert(key_type key, mapped_type const& mapped)
302 {
303 bucket& b = get_bucket(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, p, 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
get_bucketboost::attribute_value_set::implementation318 bucket& get_bucket(id_type id)
319 {
320 return m_Buckets[id & (buckets::static_size - 1u)];
321 }
322
323 //! Attempts to find an element with the specified key in the bucket
find_in_bucketboost::attribute_value_set::implementation324 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(node_traits::get_next(p));
334 }
335
336 return p;
337 }
338
339 //! Acquires the attribute value from the attribute sets
freeze_nodeboost::attribute_value_set::implementation340 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, 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, 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, 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
insert_nodeboost::attribute_value_set::implementation378 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(*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(*where);
409 b.first = p;
410 }
411 else
412 {
413 // The new element should be within the bucket
414 it = m_Nodes.iterator_to(*where);
415 }
416
417 m_Nodes.insert(it, *p);
418
419 return p;
420 }
421
422 //! Acquires attribute values from the set of attributes
freeze_nodes_fromboost::attribute_value_set::implementation423 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(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, p, it->second.get_value());
439 }
440 }
441
442 //! Copies nodes of the container
copy_nodes_fromboost::attribute_value_set::implementation443 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(*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(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
attribute_value_set(size_type reserve_count)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
attribute_value_set(attribute_set const & source_attrs,attribute_set const & thread_attrs,attribute_set const & global_attrs,size_type reserve_count)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
attribute_value_set(attribute_value_set const & source_attrs,attribute_set const & thread_attrs,attribute_set const & global_attrs,size_type reserve_count)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
construct(attribute_value_set & source_attrs,attribute_set const & thread_attrs,attribute_set const & global_attrs,size_type reserve_count)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(boost::move(source_attrs), thread_attrs, global_attrs, reserve_count);
503 }
504
505 //! Copy constructor
attribute_value_set(attribute_value_set const & that)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.m_pImpl);
510 else
511 m_pImpl = NULL;
512 }
513
514 //! Destructor
~attribute_value_set()515 BOOST_LOG_API attribute_value_set::~attribute_value_set() BOOST_NOEXCEPT
516 {
517 if (m_pImpl)
518 {
519 implementation::destroy(m_pImpl);
520 m_pImpl = NULL;
521 }
522 }
523
524 // Iterator generators
525 BOOST_LOG_API attribute_value_set::const_iterator
begin() const526 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
end() const532 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
size() const539 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
find(key_type key) const546 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.
freeze()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 >
insert(key_type key,mapped_type const & mapped)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