framework/delibs/decpp/dePoolArray.hpp

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