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 555
