1#ifndef _DEPOOLARRAY_HPP
2#define _DEPOOLARRAY_HPP
3/*-------------------------------------------------------------------------
4 * drawElements C++ Base Library
5 * -----------------------------
6 *
7 * Copyright 2014 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 Array template backed by memory pool.
24 *//*--------------------------------------------------------------------*/
25
26#include "deDefs.hpp"
27#include "deMemPool.hpp"
28#include "deInt32.h"
29
30#include <iterator>
31
32namespace de
33{
34
35//! Self-test for PoolArray
36void PoolArray_selfTest (void);
37
38template<typename T, deUint32 Alignment>
39class PoolArrayConstIterator;
40
41template<typename T, deUint32 Alignment>
42class PoolArrayIterator;
43
44/*--------------------------------------------------------------------*//*!
45 * \brief Array template backed by memory pool
46 *
47 * \note Memory in PoolArray is not contiguous so pointer arithmetic
48 *       to access next element(s) doesn't work.
49 * \todo [2013-02-11 pyry] Make elements per page template argument.
50 *//*--------------------------------------------------------------------*/
51template<typename T, deUint32 Alignment = (sizeof(T) > 4 ? 4 : sizeof(T))>
52class PoolArray
53{
54public:
55	typedef PoolArrayIterator<T, Alignment>			Iterator;
56	typedef PoolArrayConstIterator<T, Alignment>	ConstIterator;
57
58	explicit		PoolArray			(MemPool* pool);
59					PoolArray			(MemPool* pool, const PoolArray<T, Alignment>& other);
60					~PoolArray			(void);
61
62	void			clear				(void);
63
64	void			reserve				(deUintptr capacity);
65	void			resize				(deUintptr size);
66	void			resize				(deUintptr size, const T& value);
67
68	deUintptr		size				(void) const			{ return m_numElements;		}
69	bool			empty				(void) const			{ return m_numElements == 0;}
70
71	void			pushBack			(const T& value);
72	T				popBack				(void);
73
74	const T&		at					(deIntptr ndx) const	{ return *getPtr(ndx);		}
75	T&				at					(deIntptr ndx)			{ return *getPtr(ndx);		}
76
77	const T&		operator[]			(deIntptr ndx) const	{ return at(ndx);			}
78	T&				operator[]			(deIntptr ndx)			{ return at(ndx);			}
79
80	Iterator		begin				(void)					{ return Iterator(this, 0);								}
81	Iterator		end					(void)					{ return Iterator(this, (deIntptr)m_numElements);		}
82
83	ConstIterator	begin				(void) const			{ return ConstIterator(this, 0);						}
84	ConstIterator	end					(void) const			{ return ConstIterator(this, (deIntptr)m_numElements);	}
85
86private:
87	enum
88	{
89		ELEMENTS_PER_PAGE_LOG2	= 4			//!< 16 elements per page.
90	};
91
92					PoolArray			(const PoolArray<T, Alignment>& other); // \note Default copy ctor is not allowed, use PoolArray(pool, copy) instead.
93
94	T*				getPtr				(deIntptr ndx) const;
95
96	MemPool*		m_pool;
97
98	deUintptr		m_numElements;			//!< Number of elements in the array.
99	deUintptr		m_capacity;				//!< Number of allocated elements in the array.
100
101	deUintptr		m_pageTableCapacity;	//!< Size of the page table.
102	void**			m_pageTable;			//!< Pointer to the page table.
103};
104
105template<typename T, deUint32 Alignment>
106class PoolArrayIteratorBase
107{
108public:
109						PoolArrayIteratorBase		(deUintptr ndx) : m_ndx(ndx) {}
110						~PoolArrayIteratorBase		(void) {}
111
112	deIntptr			getNdx						(void) const throw() { return m_ndx;	}
113
114protected:
115	deIntptr			m_ndx;
116};
117
118template<typename T, deUint32 Alignment>
119class PoolArrayConstIterator : public PoolArrayIteratorBase<T, Alignment>
120{
121public:
122											PoolArrayConstIterator		(void);
123											PoolArrayConstIterator		(const PoolArray<T, Alignment>* array, deIntptr ndx);
124											PoolArrayConstIterator		(const PoolArrayIterator<T, Alignment>& iterator);
125											~PoolArrayConstIterator		(void);
126
127	// \note Default assignment and copy-constructor are auto-generated.
128
129	const PoolArray<T, Alignment>*			getArray	(void) const throw() { return m_array;	}
130
131	// De-reference operators.
132	const T*								operator->	(void) const throw()			{ return (*m_array)[this->m_ndx];		}
133	const T&								operator*	(void) const throw()			{ return (*m_array)[this->m_ndx];		}
134	const T&								operator[]	(deUintptr offs) const throw()	{ return (*m_array)[this->m_ndx+offs];	}
135
136	// Pre-increment and decrement.
137	PoolArrayConstIterator<T, Alignment>&	operator++	(void)	{ this->m_ndx += 1; return *this;	}
138	PoolArrayConstIterator<T, Alignment>&	operator--	(void)	{ this->m_ndx -= 1; return *this;	}
139
140	// Post-increment and decrement.
141	PoolArrayConstIterator<T, Alignment>	operator++	(int)	{ PoolArrayConstIterator<T, Alignment> copy(*this); this->m_ndx +=1; return copy; }
142	PoolArrayConstIterator<T, Alignment>	operator--	(int)	{ PoolArrayConstIterator<T, Alignment> copy(*this); this->m_ndx -=1; return copy; }
143
144	// Compound assignment.
145	PoolArrayConstIterator<T, Alignment>&	operator+=	(deIntptr offs)	{ this->m_ndx += offs; return *this; }
146	PoolArrayConstIterator<T, Alignment>&	operator-=	(deIntptr offs)	{ this->m_ndx -= offs; return *this; }
147
148	// Assignment from non-const.
149	PoolArrayConstIterator<T, Alignment>&	operator=	(const PoolArrayIterator<T, Alignment>& iter);
150
151private:
152	const PoolArray<T, Alignment>*			m_array;
153};
154
155template<typename T, deUint32 Alignment>
156class PoolArrayIterator : public PoolArrayIteratorBase<T, Alignment>
157{
158public:
159										PoolArrayIterator	(void);
160										PoolArrayIterator	(PoolArray<T, Alignment>* array, deIntptr ndx);
161										~PoolArrayIterator	(void);
162
163	// \note Default assignment and copy-constructor are auto-generated.
164
165	PoolArray<T, Alignment>*			getArray	(void) const throw() { return m_array;	}
166
167	// De-reference operators.
168	T*									operator->	(void) const throw()			{ return (*m_array)[this->m_ndx];		}
169	T&									operator*	(void) const throw()			{ return (*m_array)[this->m_ndx];		}
170	T&									operator[]	(deUintptr offs) const throw()	{ return (*m_array)[this->m_ndx+offs];	}
171
172	// Pre-increment and decrement.
173	PoolArrayIterator<T, Alignment>&	operator++	(void)	{ this->m_ndx += 1; return *this;	}
174	PoolArrayIterator<T, Alignment>&	operator--	(void)	{ this->m_ndx -= 1; return *this;	}
175
176	// Post-increment and decrement.
177	PoolArrayIterator<T, Alignment>		operator++	(int)	{ PoolArrayIterator<T, Alignment> copy(*this); this->m_ndx +=1; return copy; }
178	PoolArrayIterator<T, Alignment>		operator--	(int)	{ PoolArrayIterator<T, Alignment> copy(*this); this->m_ndx -=1; return copy; }
179
180	// Compound assignment.
181	PoolArrayIterator<T, Alignment>&	operator+=	(deIntptr offs)	{ this->m_ndx += offs; return *this; }
182	PoolArrayIterator<T, Alignment>&	operator-=	(deIntptr offs)	{ this->m_ndx -= offs; return *this; }
183
184private:
185	PoolArray<T, Alignment>*			m_array;
186};
187
188// Initializer helper for array.
189template<typename T>
190struct PoolArrayElement
191{
192	static void constructDefault	(void* ptr)					{ new (ptr) T();	}	//!< Called for non-initialized memory.
193	static void	constructCopy		(void* ptr, const T& val)	{ new (ptr) T(val);	}	//!< Called for non-initialized memory when initial value is provided.
194	static void destruct			(T* ptr)					{ ptr->~T();		}	//!< Called when element is destructed.
195};
196
197// Specialization for basic types.
198#define DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(TYPE)							\
199template<> struct PoolArrayElement<TYPE> {											\
200	static void constructDefault	(void*)					{}						\
201	static void constructCopy		(void* ptr, TYPE val)	{ *(TYPE*)ptr = val; }	\
202	static void destruct			(TYPE*)					{}						\
203}
204
205DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint8);
206DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint16);
207DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint32);
208DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint64);
209DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt8);
210DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt16);
211DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt32);
212DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt64);
213
214// PoolArray<T> implementation.
215
216template<typename T, deUint32 Alignment>
217PoolArray<T, Alignment>::PoolArray (MemPool* pool)
218	: m_pool				(pool)
219	, m_numElements			(0)
220	, m_capacity			(0)
221	, m_pageTableCapacity	(0)
222	, m_pageTable			(0)
223{
224	DE_ASSERT(deIsPowerOfTwo32(Alignment));
225}
226
227template<typename T, deUint32 Alignment>
228PoolArray<T, Alignment>::~PoolArray (void)
229{
230	// Clear resets values to T()
231	clear();
232}
233
234template<typename T, deUint32 Alignment>
235inline void PoolArray<T, Alignment>::clear (void)
236{
237	resize(0);
238}
239
240template<typename T, deUint32 Alignment>
241inline void PoolArray<T, Alignment>::resize (deUintptr newSize)
242{
243	if (newSize < m_numElements)
244	{
245		// Destruct elements that are no longer active.
246		for (deUintptr ndx = newSize; ndx < m_numElements; ndx++)
247			PoolArrayElement<T>::destruct(getPtr(ndx));
248
249		m_numElements = newSize;
250	}
251	else if (newSize > m_numElements)
252	{
253		deUintptr prevSize = m_numElements;
254
255		reserve(newSize);
256		m_numElements = newSize;
257
258		// Fill new elements with default values
259		for (deUintptr ndx = prevSize; ndx < m_numElements; ndx++)
260			PoolArrayElement<T>::constructDefault(getPtr(ndx));
261	}
262}
263
264template<typename T, deUint32 Alignment>
265inline void PoolArray<T, Alignment>::resize (deUintptr newSize, const T& value)
266{
267	if (newSize < m_numElements)
268		resize(newSize); // value is not used
269	else if (newSize > m_numElements)
270	{
271		deUintptr prevSize = m_numElements;
272
273		reserve(newSize);
274		m_numElements = newSize;
275
276		// Fill new elements with copies of value
277		for (deUintptr ndx = prevSize; ndx < m_numElements; ndx++)
278			PoolArrayElement<T>::constructCopy(getPtr(ndx), value);
279	}
280}
281
282template<typename T, deUint32 Alignment>
283inline void PoolArray<T, Alignment>::reserve (deUintptr capacity)
284{
285	if (capacity >= m_capacity)
286	{
287		void*		oldPageTable			= DE_NULL;
288		deUintptr	oldPageTableSize		= 0;
289
290		deUintptr	newCapacity				= (deUintptr)deAlignPtr((void*)capacity, 1 << ELEMENTS_PER_PAGE_LOG2);
291		deUintptr	reqPageTableCapacity	= newCapacity >> ELEMENTS_PER_PAGE_LOG2;
292
293		if (m_pageTableCapacity < reqPageTableCapacity)
294		{
295			deUintptr		newPageTableCapacity	= max(2*m_pageTableCapacity, reqPageTableCapacity);
296			void**			newPageTable			= (void**)m_pool->alloc(newPageTableCapacity * sizeof(void*));
297			deUintptr		i;
298
299			for (i = 0; i < m_pageTableCapacity; i++)
300				newPageTable[i] = m_pageTable[i];
301
302			for (; i < newPageTableCapacity; i++)
303				newPageTable[i] = DE_NULL;
304
305			// Grab information about old page table for recycling purposes.
306			oldPageTable		= m_pageTable;
307			oldPageTableSize	= m_pageTableCapacity * sizeof(T*);
308
309			m_pageTable			= newPageTable;
310			m_pageTableCapacity	= newPageTableCapacity;
311		}
312
313		// Allocate new pages.
314		{
315			deUintptr	elementSize		= (deUintptr)deAlignPtr((void*)(deUintptr)sizeof(T), Alignment);
316			deUintptr	pageAllocSize	= elementSize << ELEMENTS_PER_PAGE_LOG2;
317			deUintptr	pageTableNdx	= m_capacity >> ELEMENTS_PER_PAGE_LOG2;
318
319			// Allocate new pages from recycled old page table.
320			for (;;)
321			{
322				void*		newPage			= deAlignPtr(oldPageTable, Alignment);
323				deUintptr	alignPadding	= (deUintptr)newPage - (deUintptr)oldPageTable;
324
325				if (oldPageTableSize < pageAllocSize+alignPadding)
326					break; // No free space for alloc + alignment.
327
328				DE_ASSERT(m_pageTableCapacity > pageTableNdx);
329				DE_ASSERT(!m_pageTable[pageTableNdx]);
330				m_pageTable[pageTableNdx++] = newPage;
331
332				oldPageTable		 = (void*)((deUint8*)newPage + pageAllocSize);
333				oldPageTableSize	-= pageAllocSize+alignPadding;
334			}
335
336			// Allocate the rest of the needed pages from the pool.
337			for (; pageTableNdx < reqPageTableCapacity; pageTableNdx++)
338			{
339				DE_ASSERT(!m_pageTable[pageTableNdx]);
340				m_pageTable[pageTableNdx] = m_pool->alignedAlloc(pageAllocSize, Alignment);
341			}
342
343			m_capacity = pageTableNdx << ELEMENTS_PER_PAGE_LOG2;
344			DE_ASSERT(m_capacity >= newCapacity);
345		}
346	}
347}
348
349template<typename T, deUint32 Alignment>
350inline void PoolArray<T, Alignment>::pushBack (const T& value)
351{
352	resize(size()+1);
353	at(size()-1) = value;
354}
355
356template<typename T, deUint32 Alignment>
357inline T PoolArray<T, Alignment>::popBack (void)
358{
359	T val = at(size()-1);
360	resize(size()-1);
361	return val;
362}
363
364template<typename T, deUint32 Alignment>
365inline T* PoolArray<T, Alignment>::getPtr (deIntptr ndx) const
366{
367	DE_ASSERT(inBounds<deIntptr>(ndx, 0, (deIntptr)m_numElements));
368	deUintptr	pageNdx		= ((deUintptr)ndx >> ELEMENTS_PER_PAGE_LOG2);
369	deUintptr	subNdx		= (deUintptr)ndx & ((1 << ELEMENTS_PER_PAGE_LOG2) - 1);
370	deUintptr	elemSize	= (deUintptr)deAlignPtr((void*)(deUintptr)sizeof(T), Alignment);
371	T*			ptr			= (T*)((deUint8*)m_pageTable[pageNdx] + (subNdx*elemSize));
372	DE_ASSERT(deIsAlignedPtr(ptr, Alignment));
373	return ptr;
374}
375
376// PoolArrayIteratorBase implementation
377
378template<typename T, deUint32 Alignment>
379inline bool operator== (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
380{
381	// \todo [2013-02-08 pyry] Compare array ptr.
382	return a.getNdx() == b.getNdx();
383}
384
385template<typename T, deUint32 Alignment>
386inline bool operator!= (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
387{
388	// \todo [2013-02-08 pyry] Compare array ptr.
389	return a.getNdx() != b.getNdx();
390}
391
392template<typename T, deUint32 Alignment>
393inline bool operator< (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
394{
395	return a.getNdx() < b.getNdx();
396}
397
398template<typename T, deUint32 Alignment>
399inline bool operator> (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
400{
401	return a.getNdx() > b.getNdx();
402}
403
404template<typename T, deUint32 Alignment>
405inline bool operator<= (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
406{
407	return a.getNdx() <= b.getNdx();
408}
409
410template<typename T, deUint32 Alignment>
411inline bool operator>= (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
412{
413	return a.getNdx() >= b.getNdx();
414}
415
416// PoolArrayConstIterator<T> implementation
417
418template<typename T, deUint32 Alignment>
419inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (void)
420	: PoolArrayIteratorBase<T, Alignment>	(0)
421	, m_array								(DE_NULL)
422{
423}
424
425template<typename T, deUint32 Alignment>
426inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (const PoolArray<T, Alignment>* array, deIntptr ndx)
427	: PoolArrayIteratorBase<T, Alignment>	(ndx)
428	, m_array								(array)
429{
430}
431
432template<typename T, deUint32 Alignment>
433inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (const PoolArrayIterator<T, Alignment>& iter)
434	: PoolArrayIteratorBase<T, Alignment>	(iter)
435	, m_array								(iter.getArray())
436{
437}
438
439template<typename T, deUint32 Alignment>
440inline PoolArrayConstIterator<T, Alignment>::~PoolArrayConstIterator (void)
441{
442}
443
444// Arithmetic operators.
445
446template<typename T, deUint32 Alignment>
447inline PoolArrayConstIterator<T, Alignment> operator+ (const PoolArrayConstIterator<T, Alignment>& iter, deIntptr offs)
448{
449	return PoolArrayConstIterator<T, Alignment>(iter->getArray(), iter->getNdx()+offs);
450}
451
452template<typename T, deUint32 Alignment>
453inline PoolArrayConstIterator<T, Alignment> operator+ (deUintptr offs, const PoolArrayConstIterator<T, Alignment>& iter)
454{
455	return PoolArrayConstIterator<T, Alignment>(iter->getArray(), iter->getNdx()+offs);
456}
457
458template<typename T, deUint32 Alignment>
459PoolArrayConstIterator<T, Alignment> operator- (const PoolArrayConstIterator<T, Alignment>& iter, deIntptr offs)
460{
461	return PoolArrayConstIterator<T, Alignment>(iter.getArray(), iter.getNdx()-offs);
462}
463
464template<typename T, deUint32 Alignment>
465deIntptr operator- (const PoolArrayConstIterator<T, Alignment>& iter, const PoolArrayConstIterator<T, Alignment>& other)
466{
467	return iter.getNdx()-other.getNdx();
468}
469
470// PoolArrayIterator<T> implementation.
471
472template<typename T, deUint32 Alignment>
473inline PoolArrayIterator<T, Alignment>::PoolArrayIterator (void)
474	: PoolArrayIteratorBase<T, Alignment>	(0)
475	, m_array								(DE_NULL)
476{
477}
478
479template<typename T, deUint32 Alignment>
480inline PoolArrayIterator<T, Alignment>::PoolArrayIterator (PoolArray<T, Alignment>* array, deIntptr ndx)
481	: PoolArrayIteratorBase<T, Alignment>	(ndx)
482	, m_array								(array)
483{
484}
485
486template<typename T, deUint32 Alignment>
487inline PoolArrayIterator<T, Alignment>::~PoolArrayIterator (void)
488{
489}
490
491// Arithmetic operators.
492
493template<typename T, deUint32 Alignment>
494inline PoolArrayIterator<T, Alignment> operator+ (const PoolArrayIterator<T, Alignment>& iter, deIntptr offs)
495{
496	return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()+offs);
497}
498
499template<typename T, deUint32 Alignment>
500inline PoolArrayIterator<T, Alignment> operator+ (deUintptr offs, const PoolArrayIterator<T, Alignment>& iter)
501{
502	return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()+offs);
503}
504
505template<typename T, deUint32 Alignment>
506PoolArrayIterator<T, Alignment> operator- (const PoolArrayIterator<T, Alignment>& iter, deIntptr offs)
507{
508	return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()-offs);
509}
510
511template<typename T, deUint32 Alignment>
512deIntptr operator- (const PoolArrayIterator<T, Alignment>& iter, const PoolArrayIterator<T, Alignment>& other)
513{
514	return iter.getNdx()-other.getNdx();
515}
516
517} // de
518
519// std::iterator_traits specializations
520namespace std
521{
522
523template<typename T, deUint32 Alignment>
524struct iterator_traits<de::PoolArrayConstIterator<T, Alignment> >
525{
526	typedef deIntptr					difference_type;
527	typedef T							value_type;
528	typedef const T*					pointer;
529	typedef const T&					reference;
530	typedef random_access_iterator_tag	iterator_category;
531};
532
533template<typename T, deUint32 Alignment>
534struct iterator_traits<de::PoolArrayIterator<T, Alignment> >
535{
536	typedef deIntptr					difference_type;
537	typedef T							value_type;
538	typedef T*							pointer;
539	typedef T&							reference;
540	typedef random_access_iterator_tag	iterator_category;
541};
542
543} // std
544
545#endif // _DEPOOLARRAY_HPP
546