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
TestElemde::__anona6e63a3d0111::TestElem45 TestElem (deUint32 threadNdx_, deUint32 elemNdx_)
46 : threadNdx (threadNdx_)
47 , elemNdx (elemNdx_)
48 {}
49
TestElemde::__anona6e63a3d0111::TestElem50 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
SharedStatede::__anona6e63a3d0111::SharedState62 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:
TestThread(SharedState * shared,deUint32 threadNdx)72 TestThread (SharedState* shared, deUint32 threadNdx)
73 : m_shared (shared)
74 , m_threadNdx (threadNdx)
75 {}
76
run(void)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
runAppendListTest(deUint32 numThreads,deUint32 numElements,deUint32 numElementsHint)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:
ObjCountElem(int * liveCount)138 ObjCountElem (int* liveCount)
139 : m_liveCount(liveCount)
140 {
141 *m_liveCount += 1;
142 }
143
~ObjCountElem(void)144 ~ObjCountElem (void)
145 {
146 *m_liveCount -= 1;
147 }
148
ObjCountElem(const ObjCountElem & other)149 ObjCountElem (const ObjCountElem& other)
150 : m_liveCount(other.m_liveCount)
151 {
152 *m_liveCount += 1;
153 }
154
operator =(const ObjCountElem & other)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
runClearTest(deUint32 numElements1,deUint32 numElements2,deUint32 numElementsHint)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
AppendList_selfTest(void)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
221