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 : 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
