Home | History | Annotate | Download | only in decpp
      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 
     32 namespace de
     33 {
     34 
     35 //! Self-test for PoolArray
     36 void PoolArray_selfTest (void);
     37 
     38 template<typename T, deUint32 Alignment>
     39 class PoolArrayConstIterator;
     40 
     41 template<typename T, deUint32 Alignment>
     42 class 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  *//*--------------------------------------------------------------------*/
     51 template<typename T, deUint32 Alignment = (sizeof(T) > 4 ? 4 : (deUint32)sizeof(T))>
     52 class PoolArray
     53 {
     54 public:
     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 
     86 private:
     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 
    105 template<typename T, deUint32 Alignment>
    106 class PoolArrayIteratorBase
    107 {
    108 public:
    109 						PoolArrayIteratorBase		(deUintptr ndx) : m_ndx(ndx) {}
    110 						~PoolArrayIteratorBase		(void) {}
    111 
    112 	deIntptr			getNdx						(void) const throw() { return m_ndx;	}
    113 
    114 protected:
    115 	deIntptr			m_ndx;
    116 };
    117 
    118 template<typename T, deUint32 Alignment>
    119 class PoolArrayConstIterator : public PoolArrayIteratorBase<T, Alignment>
    120 {
    121 public:
    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 
    151 private:
    152 	const PoolArray<T, Alignment>*			m_array;
    153 };
    154 
    155 template<typename T, deUint32 Alignment>
    156 class PoolArrayIterator : public PoolArrayIteratorBase<T, Alignment>
    157 {
    158 public:
    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 
    184 private:
    185 	PoolArray<T, Alignment>*			m_array;
    186 };
    187 
    188 // Initializer helper for array.
    189 template<typename T>
    190 struct 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)							\
    199 template<> 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 
    205 DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint8);
    206 DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint16);
    207 DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint32);
    208 DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deUint64);
    209 DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt8);
    210 DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt16);
    211 DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt32);
    212 DE_SPECIALIZE_POOL_ARRAY_ELEMENT_BASIC_TYPE(deInt64);
    213 
    214 // PoolArray<T> implementation.
    215 
    216 template<typename T, deUint32 Alignment>
    217 PoolArray<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 
    227 template<typename T, deUint32 Alignment>
    228 PoolArray<T, Alignment>::~PoolArray (void)
    229 {
    230 	// Clear resets values to T()
    231 	clear();
    232 }
    233 
    234 template<typename T, deUint32 Alignment>
    235 inline void PoolArray<T, Alignment>::clear (void)
    236 {
    237 	resize(0);
    238 }
    239 
    240 template<typename T, deUint32 Alignment>
    241 inline 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 
    264 template<typename T, deUint32 Alignment>
    265 inline 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 
    282 template<typename T, deUint32 Alignment>
    283 inline 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 
    349 template<typename T, deUint32 Alignment>
    350 inline void PoolArray<T, Alignment>::pushBack (const T& value)
    351 {
    352 	resize(size()+1);
    353 	at(size()-1) = value;
    354 }
    355 
    356 template<typename T, deUint32 Alignment>
    357 inline T PoolArray<T, Alignment>::popBack (void)
    358 {
    359 	T val = at(size()-1);
    360 	resize(size()-1);
    361 	return val;
    362 }
    363 
    364 template<typename T, deUint32 Alignment>
    365 inline 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 
    378 template<typename T, deUint32 Alignment>
    379 inline 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 
    385 template<typename T, deUint32 Alignment>
    386 inline 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 
    392 template<typename T, deUint32 Alignment>
    393 inline bool operator< (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
    394 {
    395 	return a.getNdx() < b.getNdx();
    396 }
    397 
    398 template<typename T, deUint32 Alignment>
    399 inline bool operator> (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
    400 {
    401 	return a.getNdx() > b.getNdx();
    402 }
    403 
    404 template<typename T, deUint32 Alignment>
    405 inline bool operator<= (const PoolArrayIteratorBase<T, Alignment>& a, const PoolArrayIteratorBase<T, Alignment>& b)
    406 {
    407 	return a.getNdx() <= b.getNdx();
    408 }
    409 
    410 template<typename T, deUint32 Alignment>
    411 inline 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 
    418 template<typename T, deUint32 Alignment>
    419 inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (void)
    420 	: PoolArrayIteratorBase<T, Alignment>	(0)
    421 	, m_array								(DE_NULL)
    422 {
    423 }
    424 
    425 template<typename T, deUint32 Alignment>
    426 inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (const PoolArray<T, Alignment>* array, deIntptr ndx)
    427 	: PoolArrayIteratorBase<T, Alignment>	(ndx)
    428 	, m_array								(array)
    429 {
    430 }
    431 
    432 template<typename T, deUint32 Alignment>
    433 inline PoolArrayConstIterator<T, Alignment>::PoolArrayConstIterator (const PoolArrayIterator<T, Alignment>& iter)
    434 	: PoolArrayIteratorBase<T, Alignment>	(iter)
    435 	, m_array								(iter.getArray())
    436 {
    437 }
    438 
    439 template<typename T, deUint32 Alignment>
    440 inline PoolArrayConstIterator<T, Alignment>::~PoolArrayConstIterator (void)
    441 {
    442 }
    443 
    444 // Arithmetic operators.
    445 
    446 template<typename T, deUint32 Alignment>
    447 inline PoolArrayConstIterator<T, Alignment> operator+ (const PoolArrayConstIterator<T, Alignment>& iter, deIntptr offs)
    448 {
    449 	return PoolArrayConstIterator<T, Alignment>(iter->getArray(), iter->getNdx()+offs);
    450 }
    451 
    452 template<typename T, deUint32 Alignment>
    453 inline PoolArrayConstIterator<T, Alignment> operator+ (deUintptr offs, const PoolArrayConstIterator<T, Alignment>& iter)
    454 {
    455 	return PoolArrayConstIterator<T, Alignment>(iter->getArray(), iter->getNdx()+offs);
    456 }
    457 
    458 template<typename T, deUint32 Alignment>
    459 PoolArrayConstIterator<T, Alignment> operator- (const PoolArrayConstIterator<T, Alignment>& iter, deIntptr offs)
    460 {
    461 	return PoolArrayConstIterator<T, Alignment>(iter.getArray(), iter.getNdx()-offs);
    462 }
    463 
    464 template<typename T, deUint32 Alignment>
    465 deIntptr 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 
    472 template<typename T, deUint32 Alignment>
    473 inline PoolArrayIterator<T, Alignment>::PoolArrayIterator (void)
    474 	: PoolArrayIteratorBase<T, Alignment>	(0)
    475 	, m_array								(DE_NULL)
    476 {
    477 }
    478 
    479 template<typename T, deUint32 Alignment>
    480 inline PoolArrayIterator<T, Alignment>::PoolArrayIterator (PoolArray<T, Alignment>* array, deIntptr ndx)
    481 	: PoolArrayIteratorBase<T, Alignment>	(ndx)
    482 	, m_array								(array)
    483 {
    484 }
    485 
    486 template<typename T, deUint32 Alignment>
    487 inline PoolArrayIterator<T, Alignment>::~PoolArrayIterator (void)
    488 {
    489 }
    490 
    491 // Arithmetic operators.
    492 
    493 template<typename T, deUint32 Alignment>
    494 inline PoolArrayIterator<T, Alignment> operator+ (const PoolArrayIterator<T, Alignment>& iter, deIntptr offs)
    495 {
    496 	return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()+offs);
    497 }
    498 
    499 template<typename T, deUint32 Alignment>
    500 inline PoolArrayIterator<T, Alignment> operator+ (deUintptr offs, const PoolArrayIterator<T, Alignment>& iter)
    501 {
    502 	return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()+offs);
    503 }
    504 
    505 template<typename T, deUint32 Alignment>
    506 PoolArrayIterator<T, Alignment> operator- (const PoolArrayIterator<T, Alignment>& iter, deIntptr offs)
    507 {
    508 	return PoolArrayIterator<T, Alignment>(iter.getArray(), iter.getNdx()-offs);
    509 }
    510 
    511 template<typename T, deUint32 Alignment>
    512 deIntptr 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
    520 namespace std
    521 {
    522 
    523 template<typename T, deUint32 Alignment>
    524 struct 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 
    533 template<typename T, deUint32 Alignment>
    534 struct 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