1/*
2 * Copyright (c) 2018 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder.  You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions are
16 * met: redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer;
18 * redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution;
21 * neither the name of the copyright holders nor the names of its
22 * contributors may be used to endorse or promote products derived from
23 * this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * Authors: Giacomo Travaglini
38 */
39
40#include <gtest/gtest.h>
41
42#include "base/circular_queue.hh"
43
44/** Testing that once instantiated with a fixed size,
45 * the queue is still empty */
46TEST(CircularQueueTest, Empty)
47{
48    const auto cq_size = 8;
49    CircularQueue<uint32_t> cq(cq_size);
50
51    ASSERT_EQ(cq.capacity(), cq_size);
52    ASSERT_EQ(cq.size(), 0);
53    ASSERT_TRUE(cq.empty());
54}
55
56/** Testing that once instantiated with a fixed size,
57 * the queue has Head = Tail + 1 */
58TEST(CircularQueueTest, HeadTailEmpty)
59{
60    const auto cq_size = 8;
61    CircularQueue<uint32_t> cq(cq_size);
62    ASSERT_EQ(cq.head(), cq.tail() + 1);
63}
64
65/** Adding elements to the circular queue.
66 * Once an element has been added we test the new value
67 * of front() and back() (head an tail). Since we are just
68 * adding elements and not removing them, we expect the front
69 * value to be fixed and the back value to change, matching
70 * the latest pushed value.*/
71TEST(CircularQueueTest, AddingElements)
72{
73    const auto cq_size = 8;
74    CircularQueue<uint32_t> cq(cq_size);
75
76    const auto first_element = 0xAAAAAAAA;
77    cq.push_back(first_element);
78    ASSERT_EQ(cq.front(), first_element);
79    ASSERT_EQ(cq.back(), first_element);
80
81    const auto second_element = 0x55555555;
82    cq.push_back(second_element);
83    ASSERT_EQ(cq.front(), first_element);
84    ASSERT_EQ(cq.back(), second_element);
85
86    ASSERT_EQ(cq.size(), 2);
87}
88
89/** Removing elements from the circular queue.
90 * We add two elements and we consequently remove them.
91 * After removing them we check that the elements have been
92 * effectively removed, which means the circular queue is
93 * empty */
94TEST(CircularQueueTest, RemovingElements)
95{
96    const auto cq_size = 8;
97    CircularQueue<uint32_t> cq(cq_size);
98
99    // Adding first element
100    const auto first_element = 0xAAAAAAAA;
101    cq.push_back(first_element);
102
103    // Adding second element
104    const auto second_element = 0x55555555;
105    cq.push_back(second_element);
106
107    auto initial_head = cq.head();
108    auto initial_tail = cq.tail();
109
110    // Removing first and second element
111    cq.pop_front();
112    ASSERT_EQ(cq.head(), initial_head + 1);
113    ASSERT_EQ(cq.tail(), initial_tail);
114
115    cq.pop_front();
116    ASSERT_EQ(cq.head(), initial_head + 2);
117    ASSERT_EQ(cq.tail(), initial_tail);
118
119    ASSERT_EQ(cq.size(), 0);
120    ASSERT_TRUE(cq.empty());
121}
122
123/** Testing CircularQueue::full
124 * This tests adds elements to the queue and checks that it is full,
125 * which means:
126 *    - CircularQueue::full == true
127 *    - Head = Tail + 1
128 */
129TEST(CircularQueueTest, Full)
130{
131    const auto cq_size = 8;
132    CircularQueue<uint32_t> cq(cq_size);
133
134    const auto value = 0xAAAAAAAA;
135    for (auto idx = 0; idx < cq_size; idx++) {
136        cq.push_back(value);
137    }
138
139    ASSERT_TRUE(cq.full());
140    ASSERT_EQ(cq.head(), cq.tail() + 1);
141}
142
143/** Testing CircularQueue::begin(), CircularQueue::end()
144 * This tests the following:
145 *     - In an empty queue, begin() == end()
146 *     - After pushing some elements in the queue, the begin()
147 *       and end() iterators are correctly misaligned
148 */
149TEST(CircularQueueTest, BeginEnd)
150{
151    const auto cq_size = 8;
152    CircularQueue<uint32_t> cq(cq_size);
153
154    // Begin/End are the same (empty)
155    ASSERT_EQ(cq.begin(), cq.end());
156
157    const auto first_value = 0xAAAAAAAA;
158    const auto second_value = 0x55555555;
159
160    cq.push_back(first_value);
161    cq.push_back(second_value);
162
163    // End = Begin + 2
164    ASSERT_EQ(cq.begin() + 2, cq.end());
165}
166
167/** Testing that begin() and end() (-1) iterators
168 * actually point to the correct values
169 * so that dereferencing them leads to a match with the
170 * values of (front() and back())
171 */
172TEST(CircularQueueTest, BeginFrontEndBack)
173{
174    const auto cq_size = 8;
175    CircularQueue<uint32_t> cq(cq_size);
176
177    const auto front_value = 0xAAAAAAAA;
178    const auto back_value = 0x55555555;
179
180    cq.push_back(front_value);
181    cq.push_back(back_value);
182
183    ASSERT_EQ(*(cq.begin()), cq.front());
184    ASSERT_EQ(*(cq.end() - 1), cq.back());
185}
186
187/** Testing circular queue iterators:
188 * By allocating two iterators to a queue we test several
189 * operators.
190 */
191TEST(CircularQueueTest, IteratorsOp)
192{
193    const auto cq_size = 8;
194    CircularQueue<uint32_t> cq(cq_size);
195
196    const auto first_value = 0xAAAAAAAA;
197    const auto second_value = 0x55555555;
198    cq.push_back(first_value);
199    cq.push_back(second_value);
200
201    auto negative_offset = -(cq_size + 1);
202    auto it_1 = cq.begin();
203    auto it_2 = cq.begin() + 1;
204    auto it_3 = cq.begin() - negative_offset;
205
206    // Operators test
207    ASSERT_TRUE(it_1 != it_2);
208    ASSERT_FALSE(it_1 == it_2);
209    ASSERT_FALSE(it_1 > it_2);
210    ASSERT_FALSE(it_1 >= it_2);
211    ASSERT_TRUE(it_1 < it_2);
212    ASSERT_TRUE(it_1 <= it_2);
213    ASSERT_EQ(*it_1, first_value);
214    ASSERT_EQ(it_1 + 1, it_2);
215    ASSERT_EQ(it_1, it_2 - 1);
216    ASSERT_EQ(it_2 - it_1, 1);
217    ASSERT_EQ(it_1 - it_2, -1);
218    ASSERT_EQ(it_3._round, 1);
219
220    auto temp_it = it_1;
221    ASSERT_EQ(++temp_it, it_2);
222    ASSERT_EQ(--temp_it, it_1);
223    ASSERT_EQ(temp_it++, it_1);
224    ASSERT_EQ(temp_it, it_2);
225    ASSERT_EQ(temp_it--, it_2);
226    ASSERT_EQ(temp_it, it_1);
227}
228
229/**
230 * Testing a full loop, which is incrementing one iterator until
231 * it wraps and has the same index as the starting iterator.
232 * This test checks that even if they have the same index, they are
233 * not the same iterator since they have different round.
234 */
235TEST(CircularQueueTest, FullLoop)
236{
237    const auto cq_size = 8;
238    CircularQueue<uint32_t> cq(cq_size);
239
240    // ending_it does a full loop and points at the same
241    // index as starting_it but with a different round
242    auto starting_it = cq.begin();
243    auto ending_it = starting_it + cq_size;
244
245    ASSERT_EQ(starting_it._idx, ending_it._idx);
246    ASSERT_TRUE(starting_it != ending_it);
247}
248
249/**
250 * Testing correct behaviour when rounding multiple times:
251 * - Round indexes in sync
252 * - Difference between begin() and end() iterator is still
253 * equal to the CircularQueue size.
254 */
255TEST(CircularQueueTest, MultipleRound)
256{
257    const auto cq_size = 8;
258    CircularQueue<uint32_t> cq(cq_size);
259
260    // Filling the queue making it round multiple times
261    auto items_added = cq_size * 3;
262    for (auto idx = 0; idx < items_added; idx++) {
263        cq.push_back(0);
264    }
265
266    auto starting_it = cq.begin();
267    auto ending_it = cq.end();
268
269    ASSERT_EQ(starting_it._round + 1, ending_it._round);
270    ASSERT_EQ(ending_it - starting_it, cq_size);
271}
272