framework/delibs/decpp/deAppendList.cpp

   1 /*-------------------------------------------------------------------------
   2  * drawElements C++ Base Library
   3  * -----------------------------
   4  *
   5  * Copyright 2015 The Android Open Source Project
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *      http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  *
  19  *//*!
  20  * \file
  21  * \brief Fast ordered append-only container
  22  *//*--------------------------------------------------------------------*/
  23
  24 #include "deAppendList.hpp"
  25 #include "deThread.hpp"
  26 #include "deSpinBarrier.hpp"
  27 #include "deSharedPtr.hpp"
  28
  29 #include <vector>
  30 #include <algorithm>
  31
  32 namespace de
  33 {
  34
  35 namespace
  36 {
  37
  38 using std::vector;
  39
  40 struct TestElem
  41 {
  42         deUint32        threadNdx;
  43         deUint32        elemNdx;
  44
  45         TestElem (deUint32 threadNdx_, deUint32 elemNdx_)
  46                 : threadNdx     (threadNdx_)
  47                 , elemNdx       (elemNdx_)
  48         {}
  49
  50         TestElem (void)
  51                 : threadNdx     (0)
  52                 , elemNdx       (0)
  53         {}
  54 };
  55
  56 struct SharedState
  57 {
  58         deUint32                                numElements;
  59         SpinBarrier                             barrier;
  60         AppendList<TestElem>    testList;
  61
  62         SharedState (deUint32 numThreads, deUint32 numElements_, deUint32 numElementsHint)
  63                 : numElements   (numElements_)
  64                 , barrier               (numThreads)
  65                 , testList              (numElementsHint)
  66         {}
  67 };
  68
  69 class TestThread : public Thread
  70 {
  71 public:
  72         TestThread (SharedState* shared, deUint32 threadNdx)
  73                 : m_shared              (shared)
  74                 , m_threadNdx   (threadNdx)
  75         {}
  76
  77         void run (void)
  78         {
  79                 const deUint32  syncPerElems    = 10000;
  80
  81                 for (deUint32 elemNdx = 0; elemNdx < m_shared->numElements; elemNdx++)
  82                 {
  83                         if (elemNdx % syncPerElems == 0)
  84                                 m_shared->barrier.sync(SpinBarrier::WAIT_MODE_AUTO);
  85
  86                         m_shared->testList.append(TestElem(m_threadNdx, elemNdx));
  87                 }
  88         }
  89
  90 private:
  91         SharedState* const      m_shared;
  92         const deUint32          m_threadNdx;
  93 };
  94
  95 typedef SharedPtr<TestThread> TestThreadSp;
  96
  97 void runAppendListTest (deUint32 numThreads, deUint32 numElements, deUint32 numElementsHint)
  98 {
  99         SharedState                             sharedState             (numThreads, numElements, numElementsHint);
 100         vector<TestThreadSp>    threads                 (numThreads);
 101
 102         for (deUint32 threadNdx = 0; threadNdx < numThreads; ++threadNdx)
 103         {
 104                 threads[threadNdx] = TestThreadSp(new TestThread(&sharedState, threadNdx));
 105                 threads[threadNdx]->start();
 106         }
 107
 108         for (deUint32 threadNdx = 0; threadNdx < numThreads; ++threadNdx)
 109                 threads[threadNdx]->join();
 110
 111         DE_TEST_ASSERT(sharedState.testList.size() == (size_t)numElements*(size_t)numThreads);
 112
 113         {
 114                 vector<deUint32>        countByThread   (numThreads);
 115
 116                 std::fill(countByThread.begin(), countByThread.end(), 0);
 117
 118                 for (AppendList<TestElem>::const_iterator elemIter = sharedState.testList.begin();
 119                          elemIter != sharedState.testList.end();
 120                          ++elemIter)
 121                 {
 122                         const TestElem& elem    = *elemIter;
 123
 124                         DE_TEST_ASSERT(de::inBounds(elem.threadNdx, 0u, numThreads));
 125                         DE_TEST_ASSERT(countByThread[elem.threadNdx] == elem.elemNdx);
 126
 127                         countByThread[elem.threadNdx] += 1;
 128                 }
 129
 130                 for (deUint32 threadNdx = 0; threadNdx < numThreads; ++threadNdx)
 131                         DE_TEST_ASSERT(countByThread[threadNdx] == numElements);
 132         }
 133 }
 134
 135 class ObjCountElem
 136 {
 137 public:
 138         ObjCountElem (int* liveCount)
 139                 : m_liveCount(liveCount)
 140         {
 141                 *m_liveCount += 1;
 142         }
 143
 144         ~ObjCountElem (void)
 145         {
 146                 *m_liveCount -= 1;
 147         }
 148
 149         ObjCountElem (const ObjCountElem& other)
 150                 : m_liveCount(other.m_liveCount)
 151         {
 152                 *m_liveCount += 1;
 153         }
 154
 155         ObjCountElem& operator= (const ObjCountElem& other)
 156         {
 157                 m_liveCount = other.m_liveCount;
 158                 *m_liveCount += 1;
 159                 return *this;
 160         }
 161
 162 private:
 163         int* m_liveCount;
 164 };
 165
 166 void runClearTest (deUint32 numElements1, deUint32 numElements2, deUint32 numElementsHint)
 167 {
 168         int             liveCount       = 0;
 169
 170         {
 171                 de::AppendList<ObjCountElem>    testList        (numElementsHint);
 172
 173                 for (deUint32 ndx = 0; ndx < numElements1; ++ndx)
 174                         testList.append(ObjCountElem(&liveCount));
 175
 176                 DE_TEST_ASSERT(liveCount == (int)numElements1);
 177
 178                 testList.clear();
 179
 180                 DE_TEST_ASSERT(liveCount == 0);
 181
 182                 for (deUint32 ndx = 0; ndx < numElements2; ++ndx)
 183                         testList.append(ObjCountElem(&liveCount));
 184
 185                 DE_TEST_ASSERT(liveCount == (int)numElements2);
 186         }
 187
 188         DE_TEST_ASSERT(liveCount == 0);
 189 }
 190
 191 } // anonymous
 192
 193 void AppendList_selfTest (void)
 194 {
 195         // Single-threaded
 196         runAppendListTest(1, 1000, 500);
 197         runAppendListTest(1, 1000, 2000);
 198         runAppendListTest(1, 35, 1);
 199
 200         // Multi-threaded
 201         runAppendListTest(2, 10000, 500);
 202         runAppendListTest(2, 100, 10);
 203
 204         if (deGetNumAvailableLogicalCores() >= 4)
 205         {
 206                 runAppendListTest(4, 10000, 500);
 207                 runAppendListTest(4, 100, 10);
 208         }
 209
 210         // Dtor + clear()
 211         runClearTest(1, 1, 1);
 212         runClearTest(1, 2, 10);
 213         runClearTest(50, 25, 10);
 214         runClearTest(9, 50, 10);
 215         runClearTest(10, 50, 10);
 216         runClearTest(50, 9, 10);
 217         runClearTest(50, 10, 10);
 218 }
 219
 220 } // de