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
32namespace boost {
33
34BOOST_LOG_OPEN_NAMESPACE
35
36BOOST_FORCEINLINE attribute_value_set::node_base::node_base() :
37 m_pPrev(NULL),
38 m_pNext(NULL)
39{
40}
41
42BOOST_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
51struct attribute_value_set::implementation
52{
53public:
54 typedef key_type::id_type id_type;
55
56private:
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
110private:
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
130private:
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 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(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
172public:
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
316private:
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
465BOOST_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
473BOOST_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
484BOOST_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
495BOOST_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
506BOOST_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
515BOOST_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
525BOOST_LOG_API attribute_value_set::const_iterator
526attribute_value_set::begin() const
527{
528 return const_iterator(m_pImpl->begin(), const_cast< attribute_value_set* >(this));
529}
530
531BOOST_LOG_API attribute_value_set::const_iterator
532attribute_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
538BOOST_LOG_API attribute_value_set::size_type
539attribute_value_set::size() const
540{
541 return m_pImpl->size();
542}
543
544//! Internal lookup implementation
545BOOST_LOG_API attribute_value_set::const_iterator
546attribute_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.
552BOOST_LOG_API void attribute_value_set::freeze()
553{
554 m_pImpl->freeze();
555}
556
557//! Inserts an element into the set
558BOOST_LOG_API std::pair< attribute_value_set::const_iterator, bool >
559attribute_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
565BOOST_LOG_CLOSE_NAMESPACE // namespace log
566
567} // namespace boost
568
569#include <boost/log/detail/footer.hpp>
570

source code of boost/libs/log/src/attribute_value_set.cpp