threadSafePriorityQueueTest.cpp

Engine/source/platform/threads/test/threadSafePriorityQueueTest.cpp

More...

Detailed Description

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2014 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifdef TORQUE_TESTS_ENABLED
 25#include "testing/unitTesting.h"
 26#include "platform/threads/threadSafePriorityQueue.h"
 27#include "platform/threads/thread.h"
 28#include "core/util/tVector.h"
 29#include "console/console.h"
 30
 31// Test queue without concurrency.
 32TEST(ThreadSafePriorityQueue, Serial)
 33{
 34   const U32 min = 0;
 35   const U32 max = 9;
 36   const U32 len = 11;
 37
 38   U32 indices[len]    = {  2,   7,   4,   6,   1,   5,   3,   8,   6,   9, 0};
 39   F32 priorities[len] = {0.2, 0.7, 0.4, 0.6, 0.1, 0.5, 0.3, 0.8, 0.6, 0.9, 0};
 40   
 41   ThreadSafePriorityQueue<U32, F32, true>  minQueue;
 42   ThreadSafePriorityQueue<U32, F32, false> maxQueue;
 43
 44   for(U32 i = 0; i < len; i++)
 45   {
 46      minQueue.insert(priorities[i], indices[i]);
 47      maxQueue.insert(priorities[i], indices[i]);
 48   }
 49
 50   EXPECT_FALSE(minQueue.isEmpty());
 51   EXPECT_FALSE(maxQueue.isEmpty());
 52   
 53   U32 index = min;
 54   for(U32 i = 0; i < len; i++)
 55   {
 56      U32 popped;
 57      EXPECT_TRUE(minQueue.takeNext(popped))
 58         << "Failed to pop element from minQueue";
 59      EXPECT_LE(index, popped)
 60         << "Element from minQueue was not in sort order";
 61      index = popped;
 62   }
 63   
 64   index = max;
 65   for(U32 i = 0; i < len; i++)
 66   {
 67      U32 popped;
 68      EXPECT_TRUE(maxQueue.takeNext(popped))
 69         << "Failed to pop element from maxQueue";
 70      EXPECT_GE(index, popped)
 71         << "Element from maxQueue was not in sort order";
 72      index = popped;
 73   }
 74}
 75
 76// Test queue with concurrency.
 77TEST(ThreadSafePriorityQueue, Concurrent)
 78{
 79#define MIN 0
 80#define MAX 9
 81#define LEN 11
 82
 83   typedef ThreadSafePriorityQueue<U32, F32, true>  MinQueue;
 84   typedef ThreadSafePriorityQueue<U32, F32, false> MaxQueue;
 85
 86   struct ProducerThread : public Thread
 87   {
 88      MinQueue& minQueue;
 89      MaxQueue& maxQueue;
 90      ProducerThread(MinQueue& min, MaxQueue& max)
 91         : minQueue(min), maxQueue(max) {}
 92
 93      virtual void run(void*)
 94      {
 95         U32 indices[LEN]    = {  2,   7,   4,   6,   1,   5,   3,   8,   6,   9, 0};
 96         F32 priorities[LEN] = {0.2, 0.7, 0.4, 0.6, 0.1, 0.5, 0.3, 0.8, 0.6, 0.9, 0};
 97
 98         for(U32 i = 0; i < LEN; i++)
 99         {
100            minQueue.insert(priorities[i], indices[i]);
101            maxQueue.insert(priorities[i], indices[i]);
102         }
103      }
104   };
105
106   MinQueue minQueue;
107   MaxQueue maxQueue;
108   ProducerThread producers[] = {
109      ProducerThread(minQueue, maxQueue),
110      ProducerThread(minQueue, maxQueue),
111      ProducerThread(minQueue, maxQueue)
112   };
113
114   const U32 len = sizeof(producers) / sizeof(ProducerThread);
115   for(U32 i = 0; i < len; i++)
116      producers[i].start();
117   for(U32 i = 0; i < len; i++)
118      producers[i].join();
119
120   U32 index = MIN;
121   for(U32 i = 0; i < LEN * len; i++)
122   {
123      U32 popped;
124      EXPECT_TRUE(minQueue.takeNext(popped))
125         << "Failed to pop element from minQueue";
126      EXPECT_LE(index, popped)
127         << "Element from minQueue was not in sort order";
128      index = popped;
129   }
130   
131   index = MAX;
132   for(U32 i = 0; i < LEN * len; i++)
133   {
134      U32 popped;
135      EXPECT_TRUE(maxQueue.takeNext(popped))
136         << "Failed to pop element from maxQueue";
137      EXPECT_GE(index, popped)
138         << "Element from maxQueue was not in sort order";
139      index = popped;
140   }
141
142#undef MIN
143#undef MAX
144#undef LEN
145}
146
147#endif
148