2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_OPT_BUFFER_H
32 #define CDSLIB_OPT_BUFFER_H
35 #include <cds/details/defs.h>
36 #include <cds/user_setup/allocator.h>
37 #include <cds/details/allocator.h>
38 #include <cds/algo/int_algo.h>
40 namespace cds { namespace opt {
42 /// [type-option] Option setter for user-provided plain buffer
44 This option is used by some container as a random access array for storing
45 container's item; for example, a bounded queue may use
46 this option to define underlying buffer implementation.
48 The template parameter \p Type should be rebindable.
51 - \p opt::v::initialized_static_buffer
52 - \p opt::v::uninitialized_static_buffer
53 - \p opt::v::initialized_dynamic_buffer
54 - \p opt::v::uninitialized_dynamic_buffer
56 Uninitialized buffer is just an array of uninitialized elements.
57 Each element should be manually constructed, for example with a placement new operator.
58 When the uninitialized buffer is destroyed the destructor of its element is not called.
60 Initialized buffer contains default-constructed elements. Element destructor is called automatically
61 when the buffer is destroyed.
63 @note Usually, initialized and uninitialized buffers are not interchangeable.
65 template <typename Type>
68 template <typename Base> struct pack: public Base
77 /// Static uninitialized buffer
79 One of available type for \p opt::buffer option.
81 This buffer maintains static array of uninitialized elements.
82 You should manually construct each element when needed.
83 No dynamic memory allocation performed.
85 \par Template parameters:
86 - \p T - item type the buffer stores
87 - \p Capacity - the capacity of buffer. The value must be power of two if \p Exp2 is \p true
88 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
89 Otherwise it can be any positive number. Usually, it is required that the buffer has
90 size of a power of two.
92 template <typename T, size_t Capacity, bool Exp2 = true>
93 class uninitialized_static_buffer
96 typedef T value_type; ///< value type
97 static CDS_CONSTEXPR const size_t c_nCapacity = Capacity; ///< Capacity
98 static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
100 /// Rebind buffer for other template parameters
101 template <typename Q, size_t Capacity2 = c_nCapacity, bool Exp22 = c_bExp2>
103 typedef uninitialized_static_buffer<Q, Capacity2, Exp22> other; ///< Rebind result type
106 // Capacity must be power of 2
107 static_assert(!c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two");
119 element m_buffer[c_nCapacity];
122 /// Construct static buffer
123 uninitialized_static_buffer() CDS_NOEXCEPT
126 /// Construct buffer of given capacity
128 This ctor ignores \p nCapacity argument. The capacity of static buffer
129 is defined by template argument \p Capacity
131 uninitialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT
133 CDS_UNUSED( nCapacity );
136 uninitialized_static_buffer( const uninitialized_static_buffer& ) = delete;
137 uninitialized_static_buffer& operator =( const uninitialized_static_buffer& ) = delete;
140 value_type& operator []( size_t i )
142 assert( i < capacity());
143 return m_buffer[i].v;
146 /// Get item \p i, const version
147 const value_type& operator []( size_t i ) const
149 assert( i < capacity());
150 return m_buffer[i].v;
153 /// Returns buffer capacity
154 CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT
159 /// Zeroize the buffer
162 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
165 /// Returns pointer to buffer array
166 value_type * buffer() CDS_NOEXCEPT
168 return &( m_buffer[0].v );
171 /// Returns pointer to buffer array
172 value_type * buffer() const CDS_NOEXCEPT
174 return &( m_buffer[0].v );
177 /// Returns <tt> idx % capacity() </tt>
179 If the buffer size is a power of two, binary arithmethics is used
180 instead of modulo arithmetics
182 size_t mod( size_t idx )
185 return idx & ( capacity() - 1 );
187 return idx % capacity();
191 template <typename I>
192 typename std::enable_if< sizeof(I) != sizeof(size_t), size_t >::type mod( I idx )
195 return static_cast<size_t>( idx & static_cast<I>( capacity() - 1 ));
197 return static_cast<size_t>( idx % capacity());
202 /// Static initialized buffer
204 One of available type for \p opt::buffer option.
206 This buffer maintains static array of default-constructed elements.
207 No dynamic memory allocation performed.
209 \par Template parameters:
210 - \p T - item type the buffer stores
211 - \p Capacity - the capacity of buffer. The value must be power of two if \p Exp2 is \p true
212 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
213 Otherwise it can be any positive number. Usually, it is required that the buffer has
214 size of a power of two.
216 template <typename T, size_t Capacity, bool Exp2 = true>
217 class initialized_static_buffer
220 typedef T value_type; ///< value type
221 static CDS_CONSTEXPR const size_t c_nCapacity = Capacity; ///< Capacity
222 static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
224 /// Rebind buffer for other template parameters
225 template <typename Q, size_t Capacity2 = c_nCapacity, bool Exp22 = c_bExp2>
227 typedef initialized_static_buffer<Q, Capacity2, Exp22> other; ///< Rebind result type
230 // Capacity must be power of 2
231 static_assert(!c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two");
235 value_type m_buffer[c_nCapacity];
238 /// Construct static buffer
239 initialized_static_buffer() CDS_NOEXCEPT
242 /// Construct buffer of given capacity
244 This ctor ignores \p nCapacity argument. The capacity of static buffer
245 is defined by template argument \p Capacity
247 initialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT
249 CDS_UNUSED( nCapacity );
252 initialized_static_buffer( const initialized_static_buffer& ) = delete;
253 initialized_static_buffer& operator =( const initialized_static_buffer& ) = delete;
256 value_type& operator []( size_t i )
258 assert( i < capacity());
262 /// Get item \p i, const version
263 const value_type& operator []( size_t i ) const
265 assert( i < capacity());
269 /// Returns buffer capacity
270 CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT
275 /// Zeroize the buffer
278 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
281 /// Returns pointer to buffer array
282 value_type * buffer() CDS_NOEXCEPT
287 /// Returns pointer to buffer array
288 value_type * buffer() const CDS_NOEXCEPT
293 /// Returns <tt> idx % capacity() </tt>
295 If the buffer size is a power of two, binary arithmethics is used
296 instead of modulo arithmetics
298 size_t mod( size_t idx )
301 return idx & ( capacity() - 1 );
303 return idx % capacity();
307 template <typename I>
308 typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx )
311 return static_cast<size_t>( idx & static_cast<I>( capacity() - 1 ));
313 return static_cast<size_t>( idx % capacity());
318 /// Dynamically allocated uninitialized buffer
320 One of available type for \p opt::buffer option.
322 This buffer maintains dynamically allocated array of uninitialized elements.
323 You should manually construct each element when needed.
324 Allocation is performed at construction time.
326 \par Template parameters:
327 - \p T - item type storing in the buffer
328 - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface)
329 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
330 Otherwise it can be any positive number. Usually, it is required that the buffer has
331 size of a power of two.
333 template <typename T, class Alloc = CDS_DEFAULT_ALLOCATOR, bool Exp2 = true>
334 class uninitialized_dynamic_buffer
337 typedef T value_type; ///< Value type
338 typedef Alloc allocator; ///< Allocator type;
339 static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
341 /// Rebind buffer for other template parameters
342 template <typename Q, typename Alloc2= allocator, bool Exp22 = c_bExp2>
344 typedef uninitialized_dynamic_buffer<Q, Alloc2, Exp22> other; ///< Rebinding result type
348 typedef typename allocator::template rebind<value_type>::other allocator_type;
353 value_type * m_buffer;
354 size_t const m_nCapacity;
357 /// Allocates dynamic buffer of given \p nCapacity
359 If \p Exp2 class template parameter is \p true then actual capacity
360 of allocating buffer is nearest upper to \p nCapacity power of two.
362 uninitialized_dynamic_buffer( size_t nCapacity )
363 : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity )
365 assert( m_nCapacity >= 2 );
366 // Capacity must be power of 2
367 assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 );
369 m_buffer = allocator_type().allocate( m_nCapacity );
372 /// Destroys dynamically allocated buffer
373 ~uninitialized_dynamic_buffer()
375 allocator_type().deallocate( m_buffer, m_nCapacity );
378 uninitialized_dynamic_buffer( const uninitialized_dynamic_buffer& ) = delete;
379 uninitialized_dynamic_buffer& operator =( const uninitialized_dynamic_buffer& ) = delete;
382 value_type& operator []( size_t i )
384 assert( i < capacity());
388 /// Get item \p i, const version
389 const value_type& operator []( size_t i ) const
391 assert( i < capacity());
395 /// Returns buffer capacity
396 size_t capacity() const CDS_NOEXCEPT
401 /// Zeroize the buffer
404 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
407 /// Returns pointer to buffer array
408 value_type * buffer() CDS_NOEXCEPT
413 /// Returns pointer to buffer array
414 value_type * buffer() const CDS_NOEXCEPT
419 /// Returns <tt> idx % capacity() </tt>
421 If the buffer size is a power of two, binary arithmethics is used
422 instead of modulo arithmetics
424 size_t mod( size_t idx )
426 static_if ( c_bExp2 )
427 return idx & ( capacity() - 1 );
429 return idx % capacity();
433 template <typename I>
434 typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx )
436 static_if ( c_bExp2 )
437 return static_cast<size_t>( idx & static_cast<I>( capacity() - 1 ));
439 return static_cast<size_t>( idx % capacity());
445 /// Dynamically allocated initialized buffer
447 One of available type for \p opt::buffer option.
449 This buffer maintains dynamically allocated array of initialized default-constructed elements.
450 Allocation is performed at construction time.
452 \par Template parameters:
453 - \p T - item type storing in the buffer
454 - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface)
455 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
456 Otherwise it can be any positive number. Usually, it is required that the buffer has
457 size of a power of two.
459 template <typename T, class Alloc = CDS_DEFAULT_ALLOCATOR, bool Exp2 = true>
460 class initialized_dynamic_buffer
463 typedef T value_type; ///< Value type
464 typedef Alloc allocator; ///< Allocator type
465 static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
467 /// Rebind buffer for other template parameters
468 template <typename Q, typename Alloc2= allocator, bool Exp22 = c_bExp2>
470 typedef initialized_dynamic_buffer<Q, Alloc2, Exp22> other; ///< Rebinding result type
474 typedef cds::details::Allocator<value_type, allocator> allocator_type;
479 value_type * m_buffer;
480 size_t const m_nCapacity;
483 /// Allocates dynamic buffer of given \p nCapacity
485 If \p Exp2 class template parameter is \p true then actual capacity
486 of allocating buffer is nearest upper to \p nCapacity power of two.
488 initialized_dynamic_buffer( size_t nCapacity )
489 : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity )
491 assert( m_nCapacity >= 2 );
492 // Capacity must be power of 2
493 assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 );
496 m_buffer = a.NewArray( m_nCapacity );
499 /// Destroys dynamically allocated buffer
500 ~initialized_dynamic_buffer()
503 a.Delete( m_buffer, m_nCapacity );
506 initialized_dynamic_buffer( const initialized_dynamic_buffer& ) = delete;
507 initialized_dynamic_buffer& operator =( const initialized_dynamic_buffer& ) = delete;
510 value_type& operator []( size_t i )
512 assert( i < capacity());
516 /// Get item \p i, const version
517 const value_type& operator []( size_t i ) const
519 assert( i < capacity());
523 /// Returns buffer capacity
524 size_t capacity() const CDS_NOEXCEPT
529 /// Zeroize the buffer
532 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
535 /// Returns pointer to buffer array
536 value_type * buffer() CDS_NOEXCEPT
541 /// Returns pointer to buffer array
542 value_type * buffer() const CDS_NOEXCEPT
547 /// Returns <tt> idx % capacity() </tt>
549 If the buffer size is a power of two, binary arithmethics is used
550 instead of modulo arithmetics
552 size_t mod( size_t idx )
555 return idx & ( capacity() - 1 );
557 return idx % capacity();
561 template <typename I>
562 typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx )
565 return static_cast<size_t>( idx & static_cast<I>( capacity() - 1 ));
567 return static_cast<size_t>( idx % capacity());
574 }} // namespace cds::opt
576 #endif // #ifndef CDSLIB_OPT_BUFFER_H