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 | |
45 | namespace boost { |
46 | |
47 | BOOST_LOG_OPEN_NAMESPACE |
48 | |
49 | //! A simple pooling allocator |
50 | template< typename T > |
51 | class pool_allocator : |
52 | public std::allocator< T > |
53 | { |
54 | public: |
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 | |
73 | private: |
74 | pointer m_Pool[BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE]; |
75 | size_type m_PooledCount; |
76 | |
77 | public: |
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 |
155 | struct attribute_set::implementation |
156 | { |
157 | public: |
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 | |
219 | private: |
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 | |
229 | public: |
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 | |
360 | private: |
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 | |
386 | BOOST_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 | |