1/*
2 * Copyright Andrey Semashev 2007 - 2020.
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_set_impl.hpp
9 * \author Andrey Semashev
10 * \date 03.07.2010
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#ifndef BOOST_LOG_ATTRIBUTE_SET_IMPL_HPP_INCLUDED_
17#define BOOST_LOG_ATTRIBUTE_SET_IMPL_HPP_INCLUDED_
18
19#include <boost/log/detail/config.hpp>
20#include <cstddef>
21#include <new>
22#include <memory>
23#include <limits>
24#include <utility>
25#include <algorithm>
26#include <boost/assert.hpp>
27#include <boost/intrusive/options.hpp>
28#include <boost/intrusive/list.hpp>
29#include <boost/intrusive/link_mode.hpp>
30#include <boost/intrusive/derivation_value_traits.hpp>
31#include <boost/log/attributes/attribute_set.hpp>
32#include <boost/log/detail/allocator_traits.hpp>
33#include <boost/log/detail/header.hpp>
34
35#ifndef BOOST_LOG_HASH_TABLE_SIZE_LOG
36// Hash table size will be 2 ^ this value
37#define BOOST_LOG_HASH_TABLE_SIZE_LOG 4
38#endif
39
40#ifndef BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE
41// Maximum pool size that each attribute set maintains
42#define BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE 8
43#endif
44
45namespace boost {
46
47BOOST_LOG_OPEN_NAMESPACE
48
49//! A simple pooling allocator
50template< typename T >
51class pool_allocator :
52 public std::allocator< T >
53{
54public:
55 template< typename U >
56 struct rebind
57 {
58 typedef pool_allocator< U > other;
59 };
60
61 typedef std::allocator< T > base_type;
62
63#if BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE > 0
64
65 typedef typename log::aux::allocator_traits< base_type >::value_type value_type;
66 typedef typename log::aux::allocator_traits< base_type >::size_type size_type;
67 typedef typename log::aux::allocator_traits< base_type >::difference_type difference_type;
68 typedef typename log::aux::allocator_traits< base_type >::pointer pointer;
69 typedef typename log::aux::allocator_traits< base_type >::const_pointer const_pointer;
70 typedef value_type& reference;
71 typedef value_type const& const_reference;
72
73private:
74 pointer m_Pool[BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE];
75 size_type m_PooledCount;
76
77public:
78 pool_allocator() : m_PooledCount(0)
79 {
80 }
81
82 pool_allocator(pool_allocator const& that) :
83 base_type(static_cast< base_type const& >(that)),
84 m_PooledCount(0)
85 {
86 }
87
88 template< typename U >
89 pool_allocator(pool_allocator< U > const& that) :
90 base_type(static_cast< typename pool_allocator< U >::base_type const& >(that)),
91 m_PooledCount(0)
92 {
93 }
94
95 ~pool_allocator()
96 {
97 for (size_type i = 0; i < m_PooledCount; ++i)
98 {
99 log::aux::allocator_traits< base_type >::deallocate(*static_cast< base_type* >(this), m_Pool[i], 1);
100 }
101 }
102
103 pool_allocator& operator= (pool_allocator const& that)
104 {
105 base_type::operator= (static_cast< base_type const& >(that));
106 return *this;
107 }
108
109 template< typename U >
110 pool_allocator& operator= (pool_allocator< U > const& that)
111 {
112 base_type::operator= (
113 static_cast< typename pool_allocator< U >::base_type const& >(that));
114 return *this;
115 }
116
117 pointer allocate(size_type n, const void* hint = NULL)
118 {
119 if (BOOST_LIKELY(m_PooledCount > 0))
120 {
121 --m_PooledCount;
122 return m_Pool[m_PooledCount];
123 }
124 else
125 {
126 return log::aux::allocator_traits< base_type >::allocate(*static_cast< base_type* >(this), n, hint);
127 }
128 }
129
130 void deallocate(pointer p, size_type n)
131 {
132 if (BOOST_LIKELY(m_PooledCount < (sizeof(m_Pool) / sizeof(*m_Pool))))
133 {
134 m_Pool[m_PooledCount] = p;
135 ++m_PooledCount;
136 }
137 else
138 {
139 log::aux::allocator_traits< base_type >::deallocate(*static_cast< base_type* >(this), p, n);
140 }
141 }
142
143#else
144
145 template< typename U >
146 pool_allocator(pool_allocator< U > const& that) :
147 base_type(static_cast< typename pool_allocator< U >::base_type const& >(that))
148 {
149 }
150
151#endif // BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE > 0
152};
153
154//! Attribute set implementation
155struct attribute_set::implementation
156{
157public:
158 //! Attribute name identifier type
159 typedef key_type::id_type id_type;
160
161 //! Allocator type
162 typedef pool_allocator< node > node_allocator;
163
164 //! Node base class traits for the intrusive list
165 struct node_traits
166 {
167 typedef node_base node;
168 typedef node* node_ptr;
169 typedef node const* const_node_ptr;
170 static node* get_next(const node* n) { return n->m_pNext; }
171 static void set_next(node* n, node* next) { n->m_pNext = next; }
172 static node* get_previous(const node* n) { return n->m_pPrev; }
173 static void set_previous(node* n, node* prev) { n->m_pPrev = prev; }
174 };
175
176 //! Contained node traits for the intrusive list
177 typedef intrusive::derivation_value_traits<
178 node,
179 node_traits,
180 intrusive::normal_link
181 > value_traits;
182
183 //! The container that allows to iterate through elements
184 typedef intrusive::list<
185 node,
186 intrusive::value_traits< value_traits >,
187 intrusive::constant_time_size< true >
188 > node_list;
189
190 //! A hash table bucket
191 struct bucket
192 {
193 //! Points to the first element in the bucket
194 node* first;
195 //! Points to the last element in the bucket (not the one after the last!)
196 node* last;
197
198 bucket() : first(NULL), last(NULL) {}
199 };
200
201 //! Cleanup function object used to erase elements from the container
202 struct disposer
203 {
204 typedef void result_type;
205
206 explicit disposer(node_allocator& alloc) : m_Allocator(alloc)
207 {
208 }
209 void operator() (node* p) const
210 {
211 p->~node();
212 m_Allocator.deallocate(p, n: 1);
213 }
214
215 private:
216 node_allocator& m_Allocator;
217 };
218
219private:
220 //! List of nodes
221 node_list m_Nodes;
222 //! Node allocator
223 node_allocator m_Allocator;
224 //! Number of buckets in the hash table
225 static BOOST_CONSTEXPR_OR_CONST std::size_t bucket_count = static_cast< std::size_t >(1u) << BOOST_LOG_HASH_TABLE_SIZE_LOG;
226 //! Hash table buckets
227 bucket m_Buckets[bucket_count];
228
229public:
230 implementation()
231 {
232 }
233
234 implementation(implementation const& that) : m_Allocator(that.m_Allocator)
235 {
236 node_list::const_iterator it = that.m_Nodes.begin(), end = that.m_Nodes.end();
237 for (; it != end; ++it)
238 {
239 node* const n = m_Allocator.allocate(n: 1, NULL);
240 new (n) node(it->m_Value.first, it->m_Value.second);
241 m_Nodes.push_back(value&: *n);
242
243 bucket& b = get_bucket(id: it->m_Value.first.id());
244 if (b.first == NULL)
245 b.first = b.last = n;
246 else
247 b.last = n;
248 }
249 }
250
251 ~implementation()
252 {
253 m_Nodes.clear_and_dispose(disposer: disposer(m_Allocator));
254 }
255
256 size_type size() const { return m_Nodes.size(); }
257 iterator begin() { return iterator(m_Nodes.begin().pointed_node()); }
258 iterator end() { return iterator(m_Nodes.end().pointed_node()); }
259
260 void clear()
261 {
262 m_Nodes.clear_and_dispose(disposer: disposer(m_Allocator));
263 std::fill_n(first: m_Buckets, n: bucket_count, value: bucket());
264 }
265
266 std::pair< iterator, bool > insert(key_type key, mapped_type const& data)
267 {
268 BOOST_ASSERT(!!key);
269
270 bucket& b = get_bucket(id: key.id());
271 node* p = b.first;
272 if (p)
273 {
274 // The bucket is not empty, search among the elements
275 p = find_in_bucket(key, b);
276 if (p->m_Value.first == key)
277 return std::make_pair(x: iterator(p), y: false);
278 }
279
280 node* const n = m_Allocator.allocate(n: 1, NULL);
281 new (n) node(key, data);
282
283 node_list::iterator it;
284 if (b.first == NULL)
285 {
286 // The bucket is empty
287 b.first = b.last = n;
288 it = m_Nodes.end();
289 }
290 else if (p == b.last && key.id() > p->m_Value.first.id())
291 {
292 // The new element should become the last element of the bucket
293 it = m_Nodes.iterator_to(value&: *p);
294 ++it;
295 b.last = n;
296 }
297 else if (p == b.first)
298 {
299 // The new element should become the first element of the bucket
300 it = m_Nodes.iterator_to(value&: *p);
301 b.first = n;
302 }
303 else
304 {
305 // The new element should be within the bucket
306 it = m_Nodes.iterator_to(value&: *p);
307 }
308
309 m_Nodes.insert(p: it, value&: *n);
310
311 return std::make_pair(x: iterator(n), y: true);
312 }
313
314 void erase(iterator it)
315 {
316 typedef node_list::node_traits node_traits;
317 typedef node_list::value_traits value_traits;
318
319 node* p = static_cast< node* >(it.base());
320
321 // Adjust bucket boundaries, if needed
322 bucket& b = get_bucket(id: it->first.id());
323 if (p == b.first)
324 {
325 if (p == b.last)
326 {
327 // The erased element is the only one in the bucket
328 b.first = b.last = NULL;
329 }
330 else
331 {
332 // The erased element is the first one in the bucket
333 b.first = value_traits::to_value_ptr(n: node_traits::get_next(n: b.first));
334 }
335 }
336 else if (p == b.last)
337 {
338 // The erased element is the last one in the bucket
339 b.last = value_traits::to_value_ptr(n: node_traits::get_previous(n: b.last));
340 }
341
342 m_Nodes.erase_and_dispose(i: m_Nodes.iterator_to(value&: *p), disposer: disposer(m_Allocator));
343 }
344
345 iterator find(key_type key)
346 {
347 bucket& b = get_bucket(id: key.id());
348 node* p = b.first;
349 if (p)
350 {
351 // The bucket is not empty, search among the elements
352 p = find_in_bucket(key, b);
353 if (p->m_Value.first == key)
354 return iterator(p);
355 }
356
357 return end();
358 }
359
360private:
361 implementation& operator= (implementation const&);
362
363 //! The function returns a bucket for the specified element
364 bucket& get_bucket(id_type id)
365 {
366 return m_Buckets[id & (bucket_count - 1u)];
367 }
368
369 //! Attempts to find an element with the specified key in the bucket
370 node* find_in_bucket(key_type key, bucket const& b)
371 {
372 typedef node_list::node_traits node_traits;
373 typedef node_list::value_traits value_traits;
374
375 // All elements within the bucket are sorted to speedup the search.
376 node* p = b.first;
377 while (p != b.last && p->m_Value.first.id() < key.id())
378 {
379 p = value_traits::to_value_ptr(n: node_traits::get_next(n: p));
380 }
381
382 return p;
383 }
384};
385
386BOOST_LOG_CLOSE_NAMESPACE // namespace log
387
388} // namespace boost
389
390#include <boost/log/detail/footer.hpp>
391
392#endif // BOOST_LOG_ATTRIBUTE_SET_IMPL_HPP_INCLUDED_
393

source code of boost/libs/log/src/attribute_set_impl.hpp