1 /*
2 * Copyright (c) 2014-2017, Siemens AG. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * 1. Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 *
10 * 2. Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 * POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 #ifndef EMBB_CONTAINERS_INTERNAL_WAIT_FREE_SPSC_QUEUE_INL_H_
28 #define EMBB_CONTAINERS_INTERNAL_WAIT_FREE_SPSC_QUEUE_INL_H_
29
30 /*
31 * The following algorithm is described in:
32 * Maurice Herlihy and Nir Shavit. "The Art of Multiprocessor Programming."
33 * Page 46. Morgan Kaufmann, 2008. (original: L. Lamport. "Specifying concurrent
34 * programs").
35 */
36
37 namespace embb {
38 namespace containers {
39 template<typename Type, class Allocator>
40 size_t WaitFreeSPSCQueue<Type, Allocator>::
AlignCapacityToPowerOfTwo(size_t capacity)41 AlignCapacityToPowerOfTwo(size_t capacity) {
42 size_t result = 1;
43 while (result < capacity) result <<= 1;
44 return result;
45 }
46
47 template<typename Type, class Allocator>
WaitFreeSPSCQueue(size_t capacity)48 WaitFreeSPSCQueue<Type, Allocator>::WaitFreeSPSCQueue(size_t capacity)
49 : capacity(AlignCapacityToPowerOfTwo(capacity)),
50 head_index(0),
51 tail_index(0) {
52 queue_array = allocator.allocate(this->capacity);
53 }
54
55 template<typename Type, class Allocator>
GetCapacity()56 size_t WaitFreeSPSCQueue<Type, Allocator>::GetCapacity() {
57 return capacity;
58 }
59
60 template<typename Type, class Allocator>
TryEnqueue(Type const & element)61 bool WaitFreeSPSCQueue<Type, Allocator>::TryEnqueue(Type const & element) {
62 if (tail_index - head_index == capacity)
63 return false;
64
65 queue_array[tail_index % capacity] = element;
66 this->tail_index++;
67 return true;
68 }
69
70 template<typename Type, class Allocator>
TryDequeue(Type & element)71 bool WaitFreeSPSCQueue<Type, Allocator>::TryDequeue(Type & element) {
72 if (tail_index - head_index == 0)
73 return false;
74
75 Type x = queue_array[head_index % capacity];
76 this->head_index++;
77 element = x;
78 return true;
79 }
80
81 template<typename Type, class Allocator>
~WaitFreeSPSCQueue()82 WaitFreeSPSCQueue<Type, Allocator>::~WaitFreeSPSCQueue() {
83 allocator.deallocate(queue_array, capacity);
84 }
85 } // namespace containers
86 } // namespace embb
87
88 #endif // EMBB_CONTAINERS_INTERNAL_WAIT_FREE_SPSC_QUEUE_INL_H_
89