src/base/circular_queue.test.cc

   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
  38 #include <gtest/gtest.h>
  39
  40 #include "base/circular_queue.hh"
  41
  42 /** Testing that once instantiated with a fixed size,
  43  * the queue is still empty */
  44 TEST(CircularQueueTest, Empty)
  45 {
  46     const auto cq_size = 8;
  47     CircularQueue<uint32_t> cq(cq_size);
  48
  49     ASSERT_EQ(cq.capacity(), cq_size);
  50     ASSERT_EQ(cq.size(), 0);
  51     ASSERT_TRUE(cq.empty());
  52 }
  53
  54 /** Testing that once instantiated with a fixed size,
  55  * the queue has Head = Tail + 1 */
  56 TEST(CircularQueueTest, HeadTailEmpty)
  57 {
  58     const auto cq_size = 8;
  59     CircularQueue<uint32_t> cq(cq_size);
  60     ASSERT_EQ(cq.head(), cq.tail() + 1);
  61 }
  62
  63 /** Adding elements to the circular queue.
  64  * Once an element has been added we test the new value
  65  * of front() and back() (head an tail). Since we are just
  66  * adding elements and not removing them, we expect the front
  67  * value to be fixed and the back value to change, matching
  68  * the latest pushed value.*/
  69 TEST(CircularQueueTest, AddingElements)
  70 {
  71     const auto cq_size = 8;
  72     CircularQueue<uint32_t> cq(cq_size);
  73
  74     const auto first_element = 0xAAAAAAAA;
  75     cq.push_back(first_element);
  76     ASSERT_EQ(cq.front(), first_element);
  77     ASSERT_EQ(cq.back(), first_element);
  78
  79     const auto second_element = 0x55555555;
  80     cq.push_back(second_element);
  81     ASSERT_EQ(cq.front(), first_element);
  82     ASSERT_EQ(cq.back(), second_element);
  83
  84     ASSERT_EQ(cq.size(), 2);
  85 }
  86
  87 /** Removing elements from the circular queue.
  88  * We add two elements and we consequently remove them.
  89  * After removing them we check that the elements have been
  90  * effectively removed, which means the circular queue is
  91  * empty */
  92 TEST(CircularQueueTest, RemovingElements)
  93 {
  94     const auto cq_size = 8;
  95     CircularQueue<uint32_t> cq(cq_size);
  96
  97     // Adding first element
  98     const auto first_element = 0xAAAAAAAA;
  99     cq.push_back(first_element);
 100
 101     // Adding second element
 102     const auto second_element = 0x55555555;
 103     cq.push_back(second_element);
 104
 105     auto initial_head = cq.head();
 106     auto initial_tail = cq.tail();
 107
 108     // Removing first and second element
 109     cq.pop_front();
 110     ASSERT_EQ(cq.head(), initial_head + 1);
 111     ASSERT_EQ(cq.tail(), initial_tail);
 112
 113     cq.pop_front();
 114     ASSERT_EQ(cq.head(), initial_head + 2);
 115     ASSERT_EQ(cq.tail(), initial_tail);
 116
 117     ASSERT_EQ(cq.size(), 0);
 118     ASSERT_TRUE(cq.empty());
 119 }
 120
 121 /** Testing CircularQueue::full
 122  * This tests adds elements to the queue and checks that it is full,
 123  * which means:
 124  *    - CircularQueue::full == true
 125  *    - Head = Tail + 1
 126  */
 127 TEST(CircularQueueTest, Full)
 128 {
 129     const auto cq_size = 8;
 130     CircularQueue<uint32_t> cq(cq_size);
 131
 132     const auto value = 0xAAAAAAAA;
 133     for (auto idx = 0; idx < cq_size; idx++) {
 134         cq.push_back(value);
 135     }
 136
 137     ASSERT_TRUE(cq.full());
 138     ASSERT_EQ(cq.head(), cq.tail() + 1);
 139 }
 140
 141 /** Testing CircularQueue::begin(), CircularQueue::end()
 142  * This tests the following:
 143  *     - In an empty queue, begin() == end()
 144  *     - After pushing some elements in the queue, the begin()
 145  *       and end() iterators are correctly misaligned
 146  */
 147 TEST(CircularQueueTest, BeginEnd)
 148 {
 149     const auto cq_size = 8;
 150     CircularQueue<uint32_t> cq(cq_size);
 151
 152     // Begin/End are the same (empty)
 153     ASSERT_EQ(cq.begin(), cq.end());
 154
 155     const auto first_value = 0xAAAAAAAA;
 156     const auto second_value = 0x55555555;
 157
 158     cq.push_back(first_value);
 159     cq.push_back(second_value);
 160
 161     // End = Begin + 2
 162     ASSERT_EQ(cq.begin() + 2, cq.end());
 163 }
 164
 165 /** Testing that begin() and end() (-1) iterators
 166  * actually point to the correct values
 167  * so that dereferencing them leads to a match with the
 168  * values of (front() and back())
 169  */
 170 TEST(CircularQueueTest, BeginFrontEndBack)
 171 {
 172     const auto cq_size = 8;
 173     CircularQueue<uint32_t> cq(cq_size);
 174
 175     const auto front_value = 0xAAAAAAAA;
 176     const auto back_value = 0x55555555;
 177
 178     cq.push_back(front_value);
 179     cq.push_back(back_value);
 180
 181     ASSERT_EQ(*(cq.begin()), cq.front());
 182     ASSERT_EQ(*(cq.end() - 1), cq.back());
 183 }
 184
 185 /** Testing circular queue iterators:
 186  * By allocating two iterators to a queue we test several
 187  * operators.
 188  */
 189 TEST(CircularQueueTest, IteratorsOp)
 190 {
 191     const auto cq_size = 8;
 192     CircularQueue<uint32_t> cq(cq_size);
 193
 194     const auto first_value = 0xAAAAAAAA;
 195     const auto second_value = 0x55555555;
 196     cq.push_back(first_value);
 197     cq.push_back(second_value);
 198
 199     auto negative_offset = -(cq_size + 1);
 200     auto it_1 = cq.begin();
 201     auto it_2 = cq.begin() + 1;
 202     auto it_3 = cq.begin() - negative_offset;
 203
 204     // Operators test
 205     ASSERT_TRUE(it_1 != it_2);
 206     ASSERT_FALSE(it_1 == it_2);
 207     ASSERT_FALSE(it_1 > it_2);
 208     ASSERT_FALSE(it_1 >= it_2);
 209     ASSERT_TRUE(it_1 < it_2);
 210     ASSERT_TRUE(it_1 <= it_2);
 211     ASSERT_EQ(*it_1, first_value);
 212     ASSERT_EQ(it_1 + 1, it_2);
 213     ASSERT_EQ(it_1, it_2 - 1);
 214     ASSERT_EQ(it_2 - it_1, 1);
 215     ASSERT_EQ(it_1 - it_2, -1);
 216     ASSERT_EQ(it_3._round, 1);
 217
 218     auto temp_it = it_1;
 219     ASSERT_EQ(++temp_it, it_2);
 220     ASSERT_EQ(--temp_it, it_1);
 221     ASSERT_EQ(temp_it++, it_1);
 222     ASSERT_EQ(temp_it, it_2);
 223     ASSERT_EQ(temp_it--, it_2);
 224     ASSERT_EQ(temp_it, it_1);
 225 }
 226
 227 /**
 228  * Testing a full loop, which is incrementing one iterator until
 229  * it wraps and has the same index as the starting iterator.
 230  * This test checks that even if they have the same index, they are
 231  * not the same iterator since they have different round.
 232  */
 233 TEST(CircularQueueTest, FullLoop)
 234 {
 235     const auto cq_size = 8;
 236     CircularQueue<uint32_t> cq(cq_size);
 237
 238     // ending_it does a full loop and points at the same
 239     // index as starting_it but with a different round
 240     auto starting_it = cq.begin();
 241     auto ending_it = starting_it + cq_size;
 242
 243     ASSERT_EQ(starting_it._idx, ending_it._idx);
 244     ASSERT_TRUE(starting_it != ending_it);
 245 }
 246
 247 /**
 248  * Testing correct behaviour when rounding multiple times:
 249  * - Round indexes in sync
 250  * - Difference between begin() and end() iterator is still
 251  * equal to the CircularQueue size.
 252  */
 253 TEST(CircularQueueTest, MultipleRound)
 254 {
 255     const auto cq_size = 8;
 256     CircularQueue<uint32_t> cq(cq_size);
 257
 258     // Filling the queue making it round multiple times
 259     auto items_added = cq_size * 3;
 260     for (auto idx = 0; idx < items_added; idx++) {
 261         cq.push_back(0);
 262     }
 263
 264     auto starting_it = cq.begin();
 265     auto ending_it = cq.end();
 266
 267     ASSERT_EQ(starting_it._round + 1, ending_it._round);
 268     ASSERT_EQ(ending_it - starting_it, cq_size);
 269 }