1#ifndef _DEAPPENDLIST_HPP
2#define _DEAPPENDLIST_HPP
3/*-------------------------------------------------------------------------
4 * drawElements C++ Base Library
5 * -----------------------------
6 *
7 * Copyright 2015 The Android Open Source Project
8 *
9 * Licensed under the Apache License, Version 2.0 (the "License");
10 * you may not use this file except in compliance with the License.
11 * You may obtain a copy of the License at
12 *
13 *      http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 *
21 *//*!
22 * \file
23 * \brief Fast ordered append-only container
24 *//*--------------------------------------------------------------------*/
25
26#include "deDefs.hpp"
27#include "deAtomic.h"
28#include "deThread.h"
29#include "deMemory.h"
30#include "deInt32.h"
31
32namespace de
33{
34
35/*--------------------------------------------------------------------*//*!
36 * \brief Fast ordered append-only container
37 *
38 * AppendList provides data structure for recording ordered list of elements
39 * quickly, while still providing good sequential read access speed.
40 * It is good for example logging.
41 *
42 * AppendList allocates memory in blocks of blockSize elements. Choosing
43 * too small blockSize will affect performance.
44 *
45 * Elements can be appended from multiple threads simultaneously but if
46 * current block runs out, allocation of next block will happen in a single
47 * thread and block others from inserting further elements until completed.
48 * For that reason shared AppendList should not be used if there is a lot
49 * of contention and instead per-thread AppendList's are recommended.
50 *//*--------------------------------------------------------------------*/
51template<typename ElementType>
52class AppendList
53{
54public:
55								AppendList		(size_t blockSize);
56								~AppendList		(void);
57
58	void						append			(const ElementType& value);
59
60	size_t						size			(void) const { return m_numElements;	}
61
62	void						clear			(void);
63
64private:
65								AppendList		(const AppendList<ElementType>&);
66	AppendList<ElementType>&	operator=		(const AppendList<ElementType>&);
67
68	struct Block
69	{
70		const size_t		blockNdx;
71		ElementType*		elements;
72		Block* volatile		next;
73
74		Block (size_t blockNdx_, size_t size)
75			: blockNdx	(blockNdx_)
76			, elements	(reinterpret_cast<ElementType*>(deAlignedMalloc(sizeof(ElementType)*size,
77																		deAlign32((deUint32)alignOf<ElementType>(), (deUint32)sizeof(void*)))))
78			, next		(DE_NULL)
79		{
80		}
81
82		~Block (void)
83		{
84			deAlignedFree(reinterpret_cast<void*>(elements));
85		}
86	};
87
88	const size_t				m_blockSize;
89	volatile size_t				m_numElements;
90	Block*						m_first;
91	Block* volatile				m_last;
92
93public:
94	template<typename CompatibleType>
95	class Iterator
96	{
97	public:
98									Iterator						(Block* curBlock_, size_t blockSize_, size_t slotNdx_)
99																		: m_curBlock	(curBlock_)
100																		, m_blockSize	(blockSize_)
101																		, m_slotNdx		(slotNdx_)
102		{}
103
104		bool						operator!=						(const Iterator<CompatibleType>& other) const
105		{
106			return m_curBlock != other.m_curBlock || m_slotNdx != other.m_slotNdx;
107		}
108		bool						operator==						(const Iterator<CompatibleType>& other) const
109		{
110			return m_curBlock == other.m_curBlock && m_slotNdx == other.m_slotNdx;
111		}
112
113		Iterator<CompatibleType>&	operator++						(void)
114		{
115			++m_slotNdx;
116
117			if (m_slotNdx == m_blockSize)
118			{
119				m_slotNdx = 0;
120				m_curBlock = m_curBlock->next;
121			}
122
123			return *this;
124		}
125
126		Iterator<CompatibleType>	operator++						(int) const
127		{
128			Iterator<CompatibleType> copy(*this);
129			return ++copy;
130		}
131
132		CompatibleType&				operator*						(void) const
133		{
134			return m_curBlock->elements[m_slotNdx];
135		}
136
137		CompatibleType*				operator->						(void) const
138		{
139			return &m_curBlock->elements[m_slotNdx];
140		}
141
142		operator					Iterator<const CompatibleType>	(void) const
143		{
144			return Iterator<const CompatibleType>(m_curBlock, m_blockSize, m_slotNdx);
145		}
146
147	private:
148		Block*			m_curBlock;
149		size_t			m_blockSize;
150		size_t			m_slotNdx;
151	};
152
153	typedef Iterator<const ElementType>	const_iterator;
154	typedef Iterator<ElementType>		iterator;
155
156	const_iterator				begin			(void) const;
157	iterator					begin			(void);
158
159	const_iterator				end				(void) const;
160	iterator					end				(void);
161};
162
163template<typename ElementType>
164AppendList<ElementType>::AppendList (size_t blockSize)
165	: m_blockSize	(blockSize)
166	, m_numElements	(0)
167	, m_first		(new Block(0, blockSize))
168	, m_last		(m_first)
169{
170}
171
172template<typename ElementType>
173AppendList<ElementType>::~AppendList (void)
174{
175	size_t	elementNdx	= 0;
176	Block*	curBlock	= m_first;
177
178	while (curBlock)
179	{
180		Block* const	delBlock	= curBlock;
181
182		curBlock = delBlock->next;
183
184		// Call destructor for allocated elements
185		for (; elementNdx < min(m_numElements, (delBlock->blockNdx+1)*m_blockSize); ++elementNdx)
186			delBlock->elements[elementNdx%m_blockSize].~ElementType();
187
188		delete delBlock;
189	}
190
191	DE_ASSERT(elementNdx == m_numElements);
192}
193
194template<typename ElementType>
195void AppendList<ElementType>::clear (void)
196{
197	// \todo [2016-03-28 pyry] Make thread-safe, if possible
198
199	size_t	elementNdx	= 0;
200	Block*	curBlock	= m_first;
201
202	while (curBlock)
203	{
204		Block* const	delBlock	= curBlock;
205
206		curBlock = delBlock->next;
207
208		// Call destructor for allocated elements
209		for (; elementNdx < min(m_numElements, (delBlock->blockNdx+1)*m_blockSize); ++elementNdx)
210			delBlock->elements[elementNdx%m_blockSize].~ElementType();
211
212		if (delBlock != m_first)
213			delete delBlock;
214	}
215
216	DE_ASSERT(elementNdx == m_numElements);
217
218	m_numElements	= 0;
219	m_first->next	= DE_NULL;
220	m_last			= m_first;
221}
222
223template<typename ElementType>
224void AppendList<ElementType>::append (const ElementType& value)
225{
226	// Fetch curBlock first before allocating slot. Otherwise m_last might get updated before
227	// this thread gets chance of reading it, leading to curBlock->blockNdx > blockNdx.
228	Block*			curBlock	= m_last;
229
230	deMemoryReadWriteFence();
231
232	{
233		const size_t	elementNdx	= deAtomicIncrementUSize(&m_numElements) - 1;
234		const size_t	blockNdx	= elementNdx / m_blockSize;
235		const size_t	slotNdx		= elementNdx - (blockNdx * m_blockSize);
236
237		while (curBlock->blockNdx != blockNdx)
238		{
239			if (curBlock->next)
240				curBlock = curBlock->next;
241			else
242			{
243				// Other thread(s) are currently allocating additional block(s)
244				deYield();
245			}
246		}
247
248		// Did we allocate last slot? If so, add a new block
249		if (slotNdx+1 == m_blockSize)
250		{
251			Block* const	newBlock	= new Block(blockNdx+1, m_blockSize);
252
253			deMemoryReadWriteFence();
254
255			// At this point if any other thread is trying to allocate more blocks
256			// they are being blocked by curBlock->next being null. This guarantees
257			// that this thread has exclusive modify access to m_last.
258			m_last = newBlock;
259			deMemoryReadWriteFence();
260
261			// At this point other threads might have skipped to newBlock, but we
262			// still have exclusive modify access to curBlock->next.
263			curBlock->next = newBlock;
264			deMemoryReadWriteFence();
265		}
266
267		new (&curBlock->elements[slotNdx]) ElementType(value);
268	}
269}
270
271template<typename ElementType>
272typename AppendList<ElementType>::const_iterator AppendList<ElementType>::begin (void) const
273{
274	return const_iterator(m_first, m_blockSize, 0);
275}
276
277template<typename ElementType>
278typename AppendList<ElementType>::iterator AppendList<ElementType>::begin (void)
279{
280	return iterator(m_first, m_blockSize, 0);
281}
282
283template<typename ElementType>
284typename AppendList<ElementType>::const_iterator AppendList<ElementType>::end (void) const
285{
286	return const_iterator(m_last, m_blockSize, m_numElements%m_blockSize);
287}
288
289template<typename ElementType>
290typename AppendList<ElementType>::iterator AppendList<ElementType>::end (void)
291{
292	return iterator(m_last, m_blockSize, m_numElements%m_blockSize);
293}
294
295void	AppendList_selfTest		(void);
296
297} // de
298
299#endif // _DEAPPENDLIST_HPP
300