circular_queue.test.cc revision 13796
113482Srekai.gonzalezalberquilla@arm.com/* 213482Srekai.gonzalezalberquilla@arm.com * Copyright (c) 2018 ARM Limited 313482Srekai.gonzalezalberquilla@arm.com * All rights reserved 413482Srekai.gonzalezalberquilla@arm.com * 513482Srekai.gonzalezalberquilla@arm.com * The license below extends only to copyright in the software and shall 613482Srekai.gonzalezalberquilla@arm.com * not be construed as granting a license to any other intellectual 713482Srekai.gonzalezalberquilla@arm.com * property including but not limited to intellectual property relating 813482Srekai.gonzalezalberquilla@arm.com * to a hardware implementation of the functionality of the software 913482Srekai.gonzalezalberquilla@arm.com * licensed hereunder. You may use the software subject to the license 1013482Srekai.gonzalezalberquilla@arm.com * terms below provided that you ensure that this notice is replicated 1113482Srekai.gonzalezalberquilla@arm.com * unmodified and in its entirety in all distributions of the software, 1213482Srekai.gonzalezalberquilla@arm.com * modified or unmodified, in source code or in binary form. 1313482Srekai.gonzalezalberquilla@arm.com * 1413482Srekai.gonzalezalberquilla@arm.com * Redistribution and use in source and binary forms, with or without 1513482Srekai.gonzalezalberquilla@arm.com * modification, are permitted provided that the following conditions are 1613482Srekai.gonzalezalberquilla@arm.com * met: redistributions of source code must retain the above copyright 1713482Srekai.gonzalezalberquilla@arm.com * notice, this list of conditions and the following disclaimer; 1813482Srekai.gonzalezalberquilla@arm.com * redistributions in binary form must reproduce the above copyright 1913482Srekai.gonzalezalberquilla@arm.com * notice, this list of conditions and the following disclaimer in the 2013482Srekai.gonzalezalberquilla@arm.com * documentation and/or other materials provided with the distribution; 2113482Srekai.gonzalezalberquilla@arm.com * neither the name of the copyright holders nor the names of its 2213482Srekai.gonzalezalberquilla@arm.com * contributors may be used to endorse or promote products derived from 2313482Srekai.gonzalezalberquilla@arm.com * this software without specific prior written permission. 2413482Srekai.gonzalezalberquilla@arm.com * 2513482Srekai.gonzalezalberquilla@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2613482Srekai.gonzalezalberquilla@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2713482Srekai.gonzalezalberquilla@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2813482Srekai.gonzalezalberquilla@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2913482Srekai.gonzalezalberquilla@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3013482Srekai.gonzalezalberquilla@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3113482Srekai.gonzalezalberquilla@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3213482Srekai.gonzalezalberquilla@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3313482Srekai.gonzalezalberquilla@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3413482Srekai.gonzalezalberquilla@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3513482Srekai.gonzalezalberquilla@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3613482Srekai.gonzalezalberquilla@arm.com * 3713482Srekai.gonzalezalberquilla@arm.com * Authors: Giacomo Travaglini 3813482Srekai.gonzalezalberquilla@arm.com */ 3913482Srekai.gonzalezalberquilla@arm.com 4013482Srekai.gonzalezalberquilla@arm.com#include <gtest/gtest.h> 4113482Srekai.gonzalezalberquilla@arm.com 4213482Srekai.gonzalezalberquilla@arm.com#include "base/circular_queue.hh" 4313482Srekai.gonzalezalberquilla@arm.com 4413482Srekai.gonzalezalberquilla@arm.com/** Testing that once instantiated with a fixed size, 4513482Srekai.gonzalezalberquilla@arm.com * the queue is still empty */ 4613482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, Empty) 4713482Srekai.gonzalezalberquilla@arm.com{ 4813482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 4913482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 5013482Srekai.gonzalezalberquilla@arm.com 5113482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.capacity(), cq_size); 5213482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.size(), 0); 5313482Srekai.gonzalezalberquilla@arm.com ASSERT_TRUE(cq.empty()); 5413482Srekai.gonzalezalberquilla@arm.com} 5513482Srekai.gonzalezalberquilla@arm.com 5613482Srekai.gonzalezalberquilla@arm.com/** Testing that once instantiated with a fixed size, 5713482Srekai.gonzalezalberquilla@arm.com * the queue has Head = Tail + 1 */ 5813482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, HeadTailEmpty) 5913482Srekai.gonzalezalberquilla@arm.com{ 6013482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 6113482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 6213482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.head(), cq.tail() + 1); 6313482Srekai.gonzalezalberquilla@arm.com} 6413482Srekai.gonzalezalberquilla@arm.com 6513482Srekai.gonzalezalberquilla@arm.com/** Adding elements to the circular queue. 6613482Srekai.gonzalezalberquilla@arm.com * Once an element has been added we test the new value 6713482Srekai.gonzalezalberquilla@arm.com * of front() and back() (head an tail). Since we are just 6813482Srekai.gonzalezalberquilla@arm.com * adding elements and not removing them, we expect the front 6913482Srekai.gonzalezalberquilla@arm.com * value to be fixed and the back value to change, matching 7013482Srekai.gonzalezalberquilla@arm.com * the latest pushed value.*/ 7113482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, AddingElements) 7213482Srekai.gonzalezalberquilla@arm.com{ 7313482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 7413482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 7513482Srekai.gonzalezalberquilla@arm.com 7613482Srekai.gonzalezalberquilla@arm.com const auto first_element = 0xAAAAAAAA; 7713482Srekai.gonzalezalberquilla@arm.com cq.push_back(first_element); 7813482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.front(), first_element); 7913482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.back(), first_element); 8013482Srekai.gonzalezalberquilla@arm.com 8113482Srekai.gonzalezalberquilla@arm.com const auto second_element = 0x55555555; 8213482Srekai.gonzalezalberquilla@arm.com cq.push_back(second_element); 8313482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.front(), first_element); 8413482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.back(), second_element); 8513482Srekai.gonzalezalberquilla@arm.com 8613482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.size(), 2); 8713482Srekai.gonzalezalberquilla@arm.com} 8813482Srekai.gonzalezalberquilla@arm.com 8913482Srekai.gonzalezalberquilla@arm.com/** Removing elements from the circular queue. 9013482Srekai.gonzalezalberquilla@arm.com * We add two elements and we consequently remove them. 9113482Srekai.gonzalezalberquilla@arm.com * After removing them we check that the elements have been 9213482Srekai.gonzalezalberquilla@arm.com * effectively removed, which means the circular queue is 9313482Srekai.gonzalezalberquilla@arm.com * empty */ 9413482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, RemovingElements) 9513482Srekai.gonzalezalberquilla@arm.com{ 9613482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 9713482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 9813482Srekai.gonzalezalberquilla@arm.com 9913482Srekai.gonzalezalberquilla@arm.com // Adding first element 10013482Srekai.gonzalezalberquilla@arm.com const auto first_element = 0xAAAAAAAA; 10113482Srekai.gonzalezalberquilla@arm.com cq.push_back(first_element); 10213482Srekai.gonzalezalberquilla@arm.com 10313482Srekai.gonzalezalberquilla@arm.com // Adding second element 10413482Srekai.gonzalezalberquilla@arm.com const auto second_element = 0x55555555; 10513482Srekai.gonzalezalberquilla@arm.com cq.push_back(second_element); 10613482Srekai.gonzalezalberquilla@arm.com 10713482Srekai.gonzalezalberquilla@arm.com auto initial_head = cq.head(); 10813482Srekai.gonzalezalberquilla@arm.com auto initial_tail = cq.tail(); 10913482Srekai.gonzalezalberquilla@arm.com 11013482Srekai.gonzalezalberquilla@arm.com // Removing first and second element 11113482Srekai.gonzalezalberquilla@arm.com cq.pop_front(); 11213482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.head(), initial_head + 1); 11313482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.tail(), initial_tail); 11413482Srekai.gonzalezalberquilla@arm.com 11513482Srekai.gonzalezalberquilla@arm.com cq.pop_front(); 11613482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.head(), initial_head + 2); 11713482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.tail(), initial_tail); 11813482Srekai.gonzalezalberquilla@arm.com 11913482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.size(), 0); 12013482Srekai.gonzalezalberquilla@arm.com ASSERT_TRUE(cq.empty()); 12113482Srekai.gonzalezalberquilla@arm.com} 12213482Srekai.gonzalezalberquilla@arm.com 12313482Srekai.gonzalezalberquilla@arm.com/** Testing CircularQueue::full 12413482Srekai.gonzalezalberquilla@arm.com * This tests adds elements to the queue and checks that it is full, 12513482Srekai.gonzalezalberquilla@arm.com * which means: 12613482Srekai.gonzalezalberquilla@arm.com * - CircularQueue::full == true 12713482Srekai.gonzalezalberquilla@arm.com * - Head = Tail + 1 12813482Srekai.gonzalezalberquilla@arm.com */ 12913482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, Full) 13013482Srekai.gonzalezalberquilla@arm.com{ 13113482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 13213482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 13313482Srekai.gonzalezalberquilla@arm.com 13413482Srekai.gonzalezalberquilla@arm.com const auto value = 0xAAAAAAAA; 13513482Srekai.gonzalezalberquilla@arm.com for (auto idx = 0; idx < cq_size; idx++) { 13613482Srekai.gonzalezalberquilla@arm.com cq.push_back(value); 13713482Srekai.gonzalezalberquilla@arm.com } 13813482Srekai.gonzalezalberquilla@arm.com 13913482Srekai.gonzalezalberquilla@arm.com ASSERT_TRUE(cq.full()); 14013482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.head(), cq.tail() + 1); 14113482Srekai.gonzalezalberquilla@arm.com} 14213482Srekai.gonzalezalberquilla@arm.com 14313482Srekai.gonzalezalberquilla@arm.com/** Testing CircularQueue::begin(), CircularQueue::end() 14413482Srekai.gonzalezalberquilla@arm.com * This tests the following: 14513482Srekai.gonzalezalberquilla@arm.com * - In an empty queue, begin() == end() 14613482Srekai.gonzalezalberquilla@arm.com * - After pushing some elements in the queue, the begin() 14713482Srekai.gonzalezalberquilla@arm.com * and end() iterators are correctly misaligned 14813482Srekai.gonzalezalberquilla@arm.com */ 14913482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, BeginEnd) 15013482Srekai.gonzalezalberquilla@arm.com{ 15113482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 15213482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 15313482Srekai.gonzalezalberquilla@arm.com 15413482Srekai.gonzalezalberquilla@arm.com // Begin/End are the same (empty) 15513482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.begin(), cq.end()); 15613482Srekai.gonzalezalberquilla@arm.com 15713482Srekai.gonzalezalberquilla@arm.com const auto first_value = 0xAAAAAAAA; 15813482Srekai.gonzalezalberquilla@arm.com const auto second_value = 0x55555555; 15913482Srekai.gonzalezalberquilla@arm.com 16013482Srekai.gonzalezalberquilla@arm.com cq.push_back(first_value); 16113482Srekai.gonzalezalberquilla@arm.com cq.push_back(second_value); 16213482Srekai.gonzalezalberquilla@arm.com 16313482Srekai.gonzalezalberquilla@arm.com // End = Begin + 2 16413482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(cq.begin() + 2, cq.end()); 16513482Srekai.gonzalezalberquilla@arm.com} 16613482Srekai.gonzalezalberquilla@arm.com 16713482Srekai.gonzalezalberquilla@arm.com/** Testing that begin() and end() (-1) iterators 16813482Srekai.gonzalezalberquilla@arm.com * actually point to the correct values 16913482Srekai.gonzalezalberquilla@arm.com * so that dereferencing them leads to a match with the 17013482Srekai.gonzalezalberquilla@arm.com * values of (front() and back()) 17113482Srekai.gonzalezalberquilla@arm.com */ 17213482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, BeginFrontEndBack) 17313482Srekai.gonzalezalberquilla@arm.com{ 17413482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 17513482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 17613482Srekai.gonzalezalberquilla@arm.com 17713482Srekai.gonzalezalberquilla@arm.com const auto front_value = 0xAAAAAAAA; 17813482Srekai.gonzalezalberquilla@arm.com const auto back_value = 0x55555555; 17913482Srekai.gonzalezalberquilla@arm.com 18013482Srekai.gonzalezalberquilla@arm.com cq.push_back(front_value); 18113482Srekai.gonzalezalberquilla@arm.com cq.push_back(back_value); 18213482Srekai.gonzalezalberquilla@arm.com 18313482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(*(cq.begin()), cq.front()); 18413482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(*(cq.end() - 1), cq.back()); 18513482Srekai.gonzalezalberquilla@arm.com} 18613482Srekai.gonzalezalberquilla@arm.com 18713482Srekai.gonzalezalberquilla@arm.com/** Testing circular queue iterators: 18813482Srekai.gonzalezalberquilla@arm.com * By allocating two iterators to a queue we test several 18913482Srekai.gonzalezalberquilla@arm.com * operators. 19013482Srekai.gonzalezalberquilla@arm.com */ 19113482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, IteratorsOp) 19213482Srekai.gonzalezalberquilla@arm.com{ 19313482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 19413482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 19513482Srekai.gonzalezalberquilla@arm.com 19613482Srekai.gonzalezalberquilla@arm.com const auto first_value = 0xAAAAAAAA; 19713482Srekai.gonzalezalberquilla@arm.com const auto second_value = 0x55555555; 19813482Srekai.gonzalezalberquilla@arm.com cq.push_back(first_value); 19913482Srekai.gonzalezalberquilla@arm.com cq.push_back(second_value); 20013482Srekai.gonzalezalberquilla@arm.com 20113482Srekai.gonzalezalberquilla@arm.com auto it_1 = cq.begin(); 20213482Srekai.gonzalezalberquilla@arm.com auto it_2 = cq.begin() + 1; 20313482Srekai.gonzalezalberquilla@arm.com 20413482Srekai.gonzalezalberquilla@arm.com // Operators test 20513482Srekai.gonzalezalberquilla@arm.com ASSERT_TRUE(it_1 != it_2); 20613482Srekai.gonzalezalberquilla@arm.com ASSERT_FALSE(it_1 == it_2); 20713482Srekai.gonzalezalberquilla@arm.com ASSERT_FALSE(it_1 > it_2); 20813482Srekai.gonzalezalberquilla@arm.com ASSERT_FALSE(it_1 >= it_2); 20913482Srekai.gonzalezalberquilla@arm.com ASSERT_TRUE(it_1 < it_2); 21013482Srekai.gonzalezalberquilla@arm.com ASSERT_TRUE(it_1 <= it_2); 21113482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(*it_1, first_value); 21213482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(it_1 + 1, it_2); 21313482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(it_1, it_2 - 1); 21413482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(it_2 - it_1, 1); 21513796Sgiacomo.travaglini@arm.com ASSERT_EQ(it_1 - it_2, -1); 21613482Srekai.gonzalezalberquilla@arm.com 21713482Srekai.gonzalezalberquilla@arm.com auto temp_it = it_1; 21813482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(++temp_it, it_2); 21913482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(--temp_it, it_1); 22013482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(temp_it++, it_1); 22113482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(temp_it, it_2); 22213482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(temp_it--, it_2); 22313482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(temp_it, it_1); 22413482Srekai.gonzalezalberquilla@arm.com} 22513482Srekai.gonzalezalberquilla@arm.com 22613482Srekai.gonzalezalberquilla@arm.com/** 22713482Srekai.gonzalezalberquilla@arm.com * Testing a full loop, which is incrementing one iterator until 22813482Srekai.gonzalezalberquilla@arm.com * it wraps and has the same index as the starting iterator. 22913482Srekai.gonzalezalberquilla@arm.com * This test checks that even if they have the same index, they are 23013482Srekai.gonzalezalberquilla@arm.com * not the same iterator since they have different round. 23113482Srekai.gonzalezalberquilla@arm.com */ 23213482Srekai.gonzalezalberquilla@arm.comTEST(CircularQueueTest, FullLoop) 23313482Srekai.gonzalezalberquilla@arm.com{ 23413482Srekai.gonzalezalberquilla@arm.com const auto cq_size = 8; 23513482Srekai.gonzalezalberquilla@arm.com CircularQueue<uint32_t> cq(cq_size); 23613482Srekai.gonzalezalberquilla@arm.com 23713482Srekai.gonzalezalberquilla@arm.com // ending_it does a full loop and points at the same 23813482Srekai.gonzalezalberquilla@arm.com // index as starting_it but with a different round 23913482Srekai.gonzalezalberquilla@arm.com auto starting_it = cq.begin(); 24013482Srekai.gonzalezalberquilla@arm.com auto ending_it = starting_it + cq_size; 24113482Srekai.gonzalezalberquilla@arm.com 24213482Srekai.gonzalezalberquilla@arm.com ASSERT_EQ(starting_it._idx, ending_it._idx); 24313482Srekai.gonzalezalberquilla@arm.com ASSERT_TRUE(starting_it != ending_it); 24413482Srekai.gonzalezalberquilla@arm.com} 24513796Sgiacomo.travaglini@arm.com 24613796Sgiacomo.travaglini@arm.com/** 24713796Sgiacomo.travaglini@arm.com * Testing correct behaviour when rounding multiple times: 24813796Sgiacomo.travaglini@arm.com * - Round indexes in sync 24913796Sgiacomo.travaglini@arm.com * - Difference between begin() and end() iterator is still 25013796Sgiacomo.travaglini@arm.com * equal to the CircularQueue size. 25113796Sgiacomo.travaglini@arm.com */ 25213796Sgiacomo.travaglini@arm.comTEST(CircularQueueTest, MultipleRound) 25313796Sgiacomo.travaglini@arm.com{ 25413796Sgiacomo.travaglini@arm.com const auto cq_size = 8; 25513796Sgiacomo.travaglini@arm.com CircularQueue<uint32_t> cq(cq_size); 25613796Sgiacomo.travaglini@arm.com 25713796Sgiacomo.travaglini@arm.com // Filling the queue making it round multiple times 25813796Sgiacomo.travaglini@arm.com auto items_added = cq_size * 3; 25913796Sgiacomo.travaglini@arm.com for (auto idx = 0; idx < items_added; idx++) { 26013796Sgiacomo.travaglini@arm.com cq.push_back(0); 26113796Sgiacomo.travaglini@arm.com } 26213796Sgiacomo.travaglini@arm.com 26313796Sgiacomo.travaglini@arm.com auto starting_it = cq.begin(); 26413796Sgiacomo.travaglini@arm.com auto ending_it = cq.end(); 26513796Sgiacomo.travaglini@arm.com 26613796Sgiacomo.travaglini@arm.com ASSERT_EQ(starting_it._round + 1, ending_it._round); 26713796Sgiacomo.travaglini@arm.com ASSERT_EQ(ending_it - starting_it, cq_size); 26813796Sgiacomo.travaglini@arm.com} 269