git.cworth.org Git - vogl/blob - src/voglcore/vogl_object_pool.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_object_pool.h
  28 // vogl_object_pool is a straightforward freelist class.
  29 // It's fast, but it's very greedy. It never frees allocated blocks unless you explictly call clear() (fast) or free_unused_blocks() (not as fast if some blocks are still allocated).
  30
  31 #ifndef VOGL_OBJECT_POOL_H
  32 #define VOGL_OBJECT_POOL_H
  33
  34 #include "vogl_core.h"
  35 #include "vogl_console.h"
  36
  37 // Set to 1 to enable allocation debugging using rmalloc.c (much slower)
  38 #ifndef VOGL_OBJECT_POOL_DEBUGGING
  39 #define VOGL_OBJECT_POOL_DEBUGGING 1
  40 #endif
  41
  42 #if VOGL_OBJECT_POOL_DEBUGGING
  43 //   #warning vogl_object_pool.h: Object pool debugging enabled
  44 #endif
  45
  46 VOGL_NAMESPACE_BEGIN(vogl)
  47
  48 #define CHECK_FAILURE check_failure(__LINE__);
  49
  50 class object_pool_no_lock_policy
  51 {
  52 public:
  53     void lock() const
  54     {
  55     }
  56
  57     void unlock() const
  58     {
  59     }
  60 };
  61
  62 class object_pool_spinlock_locking_policy
  63 {
  64     mutable spinlock m_lock;
  65
  66 public:
  67     void lock() const
  68     {
  69         m_lock.lock();
  70     }
  71
  72     void unlock() const
  73     {
  74         m_lock.unlock();
  75     }
  76 };
  77
  78 class object_pool_mutex_locking_policy
  79 {
  80     mutable mutex m_lock;
  81
  82 public:
  83     void lock() const
  84     {
  85         m_lock.lock();
  86     }
  87
  88     void unlock() const
  89     {
  90         m_lock.unlock();
  91     }
  92 };
  93
  94 enum object_pool_flags
  95 {
  96     cObjectPoolGrowExponential = 1,
  97     cObjectPoolClearOnDestruction = 2
  98 };
  99
 100 template <typename T, typename LockingPolicy = object_pool_no_lock_policy>
 101 class object_pool : public LockingPolicy
 102 {
 103     VOGL_NO_COPY_OR_ASSIGNMENT_OP(object_pool);
 104
 105     typedef object_pool<T, LockingPolicy> base;
 106
 107     class scoped_lock
 108     {
 109         const object_pool &m_pool;
 110
 111     public:
 112         scoped_lock(const object_pool &pool)
 113             : m_pool(pool)
 114         {
 115             pool.lock();
 116         }
 117         ~scoped_lock()
 118         {
 119             m_pool.unlock();
 120         }
 121     };
 122
 123 public:
 124     object_pool(size_t grow_size = 0, uint flags = cObjectPoolGrowExponential | cObjectPoolClearOnDestruction)
 125         : m_flags(flags),
 126           m_grow_size(grow_size),
 127           m_next_grow_size(math::maximum<size_t>(1U, grow_size)),
 128           m_total_blocks(0),
 129           m_total_heap_bytes(0),
 130           m_pFirst_free_node(NULL),
 131           m_total_nodes(0),
 132           m_total_free_nodes(0),
 133           m_update_flag(false)
 134     {
 135         utils::zero_object(m_blocks);
 136         m_blocks.m_pPrev = &m_blocks;
 137         m_blocks.m_pNext = &m_blocks;
 138     }
 139
 140     ~object_pool()
 141     {
 142         if (m_flags & cObjectPoolClearOnDestruction)
 143             clear();
 144     }
 145
 146     inline T *alloc()
 147     {
 148         node *pNode = alloc_node();
 149         T *pObj = pNode->get_object_ptr();
 150         scalar_type<T>::construct(pObj);
 151         return pObj;
 152     }
 153
 154     template <typename U>
 155     inline T *alloc(const U &a)
 156     {
 157         node *pNode = alloc_node();
 158         T *pObj = pNode->get_object_ptr();
 159         scalar_type<T>::construct(pObj, a);
 160         return pObj;
 161     }
 162
 163     template <typename U, typename V>
 164     inline T *alloc(const U &a, const V &b)
 165     {
 166         node *pNode = alloc_node();
 167         T *pObj = pNode->get_object_ptr();
 168         new (static_cast<void *>(pObj)) T(a, b);
 169         return pObj;
 170     }
 171
 172     template <typename U, typename V, typename W>
 173     inline T *alloc(const U &a, const V &b, const W &c)
 174     {
 175         node *pNode = alloc_node();
 176         T *pObj = pNode->get_object_ptr();
 177         new (static_cast<void *>(pObj)) T(a, b, c);
 178         return pObj;
 179     }
 180
 181     template <typename U, typename V, typename W, typename X>
 182     inline T *alloc(const U &a, const V &b, const W &c, const X &d)
 183     {
 184         node *pNode = alloc_node();
 185         T *pObj = pNode->get_object_ptr();
 186         new (static_cast<void *>(pObj)) T(a, b, c, d);
 187         return pObj;
 188     }
 189
 190     template <typename U, typename V, typename W, typename X, typename Y>
 191     inline T *alloc(const U &a, const V &b, const W &c, const X &d, const Y &e)
 192     {
 193         node *pNode = alloc_node();
 194         T *pObj = pNode->get_object_ptr();
 195         new (static_cast<void *>(pObj)) T(a, b, c, d, e);
 196         return pObj;
 197     }
 198
 199     inline T *alloc_no_construction()
 200     {
 201         node *pNode = alloc_node();
 202         return pNode->get_object_ptr();
 203     }
 204
 205     inline void destroy_no_destruction(T *p)
 206     {
 207         VOGL_ASSERT(!m_update_flag);
 208         VOGL_ASSERT(m_total_blocks);
 209
 210         if (!p)
 211             return;
 212
 213         node *pNode = reinterpret_cast<node *>(reinterpret_cast<uint8 *>(p) - static_cast<int>(VOGL_OFFSETOF(node, m_obj)));
 214
 215 #if VOGL_OBJECT_POOL_DEBUGGING
 216         VOGL_ASSERT(pNode->m_marker == cUsedNodeMarker);
 217         pNode->m_marker = cFreeNodeMarker;
 218 #endif
 219
 220         LockingPolicy::lock();
 221
 222         pNode->m_pNext = m_pFirst_free_node;
 223         m_pFirst_free_node = pNode;
 224
 225         ++m_total_free_nodes;
 226
 227         LockingPolicy::unlock();
 228     }
 229
 230     inline void destroy(T *p)
 231     {
 232         if (p)
 233         {
 234             scalar_type<T>::destruct(p);
 235             destroy_no_destruction(p);
 236         }
 237     }
 238
 239     // This frees all allocated memory, but does NOT destroy all objects. That's the caller's responsibility.
 240     size_t clear()
 241     {
 242         scoped_lock lock(*this);
 243         return clear_internal();
 244     }
 245
 246     // TODO: until vogl::vector supports size_t sizes there are some ugly casts in here.
 247     // This is a lot more complex than I originally thought it would be, and we're probably not going to need it.
 248     // If the free lists were hung off each block this would be much simpler, but that would require more node overhead (or more costly frees).
 249     size_t free_unused_blocks()
 250     {
 251         scoped_lock lock(*this);
 252
 253         VOGL_ASSERT(!m_update_flag);
 254
 255         if (!m_total_free_nodes)
 256             return 0;
 257
 258         if (m_total_free_nodes == m_total_nodes)
 259             return clear_internal();
 260
 261         if ((m_total_free_nodes > cUINT32_MAX) || (m_total_nodes > cUINT32_MAX) || (m_total_blocks > cUINT32_MAX))
 262         {
 263             VOGL_ASSERT_ALWAYS;
 264             return 0;
 265         }
 266
 267         m_update_flag = true;
 268
 269         vogl::vector<node *> free_nodes;
 270         free_nodes.reserve((uint)m_total_free_nodes);
 271
 272         // Put all freelist nodes into the free_nodes array and sort it by pointer address
 273         node *pCur_node = m_pFirst_free_node;
 274         while (pCur_node)
 275         {
 276 #if VOGL_OBJECT_POOL_DEBUGGING
 277             if (pCur_node->m_marker != cFreeNodeMarker)
 278             {
 279                 CHECK_FAILURE;
 280                 m_update_flag = false;
 281                 return 0;
 282             }
 283 #endif
 284             free_nodes.push_back(pCur_node);
 285             pCur_node = pCur_node->m_pNext;
 286         }
 287
 288         free_nodes.sort();
 289
 290         VOGL_ASSERT(free_nodes.size() == m_total_free_nodes);
 291
 292         // Now put all block pointers into the blocks array and sort it by address
 293         vogl::vector<block *> blocks;
 294         blocks.reserve((uint)m_total_blocks);
 295
 296         block *pCur_block = m_blocks.m_pNext;
 297         while (pCur_block != &m_blocks)
 298         {
 299             blocks.push_back(pCur_block);
 300             pCur_block = pCur_block->m_pNext;
 301         }
 302
 303         VOGL_ASSERT(blocks.size() == m_total_blocks);
 304
 305         blocks.sort();
 306
 307         // Now find which block each free node pointer belongs in, and keep a tally of the # of free nodes we've found in each block (along with the first block index for each block)
 308         vogl::vector<uint> free_nodes_in_block(blocks.size());
 309         vogl::vector<uint> first_node_indices(blocks.size());
 310
 311         int prev_block_index = -1;
 312
 313         for (uint i = 0; i < free_nodes.size(); i++)
 314         {
 315             node *pNode = free_nodes[i];
 316
 317             if (prev_block_index >= 0)
 318             {
 319                 node *pFirst_node = blocks[prev_block_index]->get_first_node_ptr();
 320                 node *pEnd_node = blocks[prev_block_index]->get_end_node_ptr();
 321
 322                 if ((pNode >= pFirst_node) && (pNode < pEnd_node))
 323                 {
 324                     free_nodes_in_block[prev_block_index]++;
 325                     continue;
 326                 }
 327             }
 328
 329             // Binary search to find which block this node belongs in
 330             int l = 0, h = blocks.size() - 1;
 331             while (l <= h)
 332             {
 333                 int m = l + ((h - l) >> 1);
 334                 node *pFirst_node = blocks[m]->get_first_node_ptr();
 335                 node *pEnd_node = blocks[m]->get_end_node_ptr();
 336
 337                 if ((pNode >= pFirst_node) && (pNode < pEnd_node))
 338                 {
 339                     // We've found which block this node belongs to. See if all nodes in this block are free.
 340                     first_node_indices[m] = i;
 341                     free_nodes_in_block[m]++;
 342                     prev_block_index = m;
 343
 344                     size_t n = blocks[m]->m_total_nodes;
 345                     if ((n > 1) && ((i + n - 1) < free_nodes.size()))
 346                     {
 347                         pNode = free_nodes[(uint)(i + n - 1)];
 348                         if (pNode == (pEnd_node - 1))
 349                         {
 350                             free_nodes_in_block[m] = (uint)n;
 351                             i += (n - 1);
 352                         }
 353                     }
 354
 355                     break;
 356                 }
 357                 else if (pNode >= pEnd_node)
 358                     l = m + 1;
 359                 else
 360                     h = m - 1;
 361             }
 362
 363             if (l > h)
 364             {
 365                 CHECK_FAILURE;
 366                 m_update_flag = false;
 367                 return 0;
 368             }
 369         }
 370
 371         // Now loop through each block and free the ones that have all-freed nodes
 372         size_t total_nodes_freed = 0;
 373         size_t total_blocks_freed = 0;
 374         size_t total_bytes_freed = 0;
 375
 376         size_t prev_highwater_free_node_index = 0;
 377
 378         for (uint block_index = 0; block_index < blocks.size(); ++block_index)
 379         {
 380             block *pBlock = blocks[block_index];
 381
 382             if (pBlock->m_total_nodes != free_nodes_in_block[block_index])
 383                 continue;
 384
 385             size_t total_nodes = pBlock->m_total_nodes;
 386
 387             VOGL_ASSERT(m_total_nodes >= total_nodes);
 388             m_total_nodes -= total_nodes;
 389
 390             VOGL_ASSERT(m_total_free_nodes >= total_nodes);
 391             m_total_free_nodes -= total_nodes;
 392
 393             VOGL_ASSERT(m_total_blocks);
 394             m_total_blocks--;
 395
 396             size_t block_size_in_bytes = vogl_msize(pBlock);
 397             total_bytes_freed += block_size_in_bytes;
 398
 399             VOGL_ASSERT(m_total_heap_bytes >= block_size_in_bytes);
 400             m_total_heap_bytes -= block_size_in_bytes;
 401
 402             total_nodes_freed += total_nodes;
 403
 404             uint first_node_index = first_node_indices[block_index];
 405
 406             VOGL_ASSERT(first_node_index >= prev_highwater_free_node_index);
 407
 408             if (!total_blocks_freed)
 409                 m_pFirst_free_node = NULL;
 410
 411             // Put any free nodes before the ones we're removing back into the freelist
 412             // TODO: This just puts the nodes back in any old order. This should prioritize the freelist order by those blocks which are must occupied.
 413             size_t n = first_node_index - prev_highwater_free_node_index;
 414             for (size_t i = 0; i < n; i++)
 415             {
 416                 node *pFree_node = free_nodes[(uint)(prev_highwater_free_node_index + i)];
 417                 pFree_node->m_pNext = m_pFirst_free_node;
 418                 m_pFirst_free_node = pFree_node;
 419             }
 420
 421             prev_highwater_free_node_index = first_node_index + total_nodes;
 422
 423             vogl_free(pBlock);
 424
 425             total_blocks_freed++;
 426
 427             blocks[block_index] = NULL;
 428         }
 429
 430         if (!total_blocks_freed)
 431         {
 432             m_update_flag = false;
 433             return 0;
 434         }
 435
 436         if (prev_highwater_free_node_index != free_nodes.size())
 437         {
 438             // Put any remaining free nodes before the ones we're removing back into the freelist
 439             size_t n = free_nodes.size() - prev_highwater_free_node_index;
 440             for (size_t i = 0; i < n; i++)
 441             {
 442                 node *pFree_node = free_nodes[(uint)(prev_highwater_free_node_index + i)];
 443                 pFree_node->m_pNext = m_pFirst_free_node;
 444                 m_pFirst_free_node = pFree_node;
 445             }
 446         }
 447
 448         m_blocks.m_pPrev = &m_blocks;
 449         m_blocks.m_pNext = &m_blocks;
 450
 451         if (m_total_blocks)
 452         {
 453             // Now fix up the block list
 454             for (uint block_index = 0; block_index < blocks.size(); ++block_index)
 455             {
 456                 block *pBlock = blocks[block_index];
 457                 if (pBlock)
 458                 {
 459                     pBlock->m_pPrev = &m_blocks;
 460                     pBlock->m_pNext = m_blocks.m_pNext;
 461
 462                     m_blocks.m_pNext->m_pPrev = pBlock;
 463                     m_blocks.m_pNext = pBlock;
 464                 }
 465             }
 466         }
 467
 468         m_update_flag = false;
 469
 470         return total_bytes_freed;
 471     }
 472
 473     bool is_valid_ptr(const T *p, bool check_freelist = false) const
 474     {
 475         if (!p)
 476             return false;
 477
 478         scoped_lock lock(*this);
 479
 480         block *pCur_block = m_blocks.m_pNext;
 481         while (pCur_block != &m_blocks)
 482         {
 483             if (pCur_block->m_begin_marker != cBlockBeginMarker)
 484             {
 485                 CHECK_FAILURE;
 486                 return false;
 487             }
 488
 489             if (pCur_block->m_end_marker != cBlockEndMarker)
 490             {
 491                 CHECK_FAILURE;
 492                 return false;
 493             }
 494
 495             if (!pCur_block->m_total_nodes)
 496             {
 497                 CHECK_FAILURE;
 498                 return false;
 499             }
 500
 501             if ((p >= pCur_block->get_first_node_ptr()->get_object_ptr()) && (p <= (pCur_block->get_first_node_ptr() + pCur_block->m_total_nodes - 1)->get_object_ptr()))
 502             {
 503                 std::ptrdiff_t ofs = reinterpret_cast<const uint8 *>(p) - reinterpret_cast<uint8 *>(pCur_block->get_first_node_ptr()->get_object_ptr());
 504                 if (ofs % sizeof(node))
 505                 {
 506                     CHECK_FAILURE;
 507                     return false;
 508                 }
 509
 510                 if (check_freelist)
 511                 {
 512                     node *pCur_node = m_pFirst_free_node;
 513                     while (pCur_node)
 514                     {
 515                         if (p == pCur_node->get_object_ptr())
 516                         {
 517                             CHECK_FAILURE;
 518                             return false;
 519                         }
 520                         pCur_node = pCur_node->m_pNext;
 521                     }
 522                 }
 523                 return true;
 524             }
 525
 526             pCur_block = pCur_block->m_pNext;
 527         }
 528
 529         return false;
 530     }
 531
 532     bool check()
 533     {
 534         scoped_lock lock(*this);
 535
 536         VOGL_ASSERT(!m_update_flag);
 537
 538         if (m_total_blocks > static_cast<size_t>(cINT32_MAX))
 539         {
 540             VOGL_ASSERT_ALWAYS;
 541             return false;
 542         }
 543
 544         m_update_flag = true;
 545
 546         bool success = true;
 547
 548         size_t total_blocks_found = 0;
 549         size_t total_heap_bytes_found = 0;
 550
 551         size_t total_nodes_found = 0;
 552
 553         vogl::vector<block *> blocks;
 554         blocks.reserve(static_cast<uint>(m_total_blocks));
 555
 556         block *pCur_block = m_blocks.m_pNext;
 557         while (pCur_block != &m_blocks)
 558         {
 559             if (pCur_block->m_begin_marker != cBlockBeginMarker)
 560             {
 561                 CHECK_FAILURE;
 562                 success = false;
 563                 break;
 564             }
 565
 566             if (pCur_block->m_end_marker != cBlockEndMarker)
 567             {
 568                 CHECK_FAILURE;
 569                 success = false;
 570                 break;
 571             }
 572
 573             if (!pCur_block->m_total_nodes)
 574             {
 575                 CHECK_FAILURE;
 576                 success = false;
 577                 break;
 578             }
 579
 580             size_t block_heap_size = vogl_msize(pCur_block);
 581             if (block_heap_size < (sizeof(block) + pCur_block->m_total_nodes * sizeof(node)))
 582             {
 583                 CHECK_FAILURE;
 584                 success = false;
 585                 break;
 586             }
 587
 588             total_heap_bytes_found += block_heap_size;
 589
 590             total_blocks_found++;
 591             if (total_blocks_found > m_total_blocks)
 592             {
 593                 CHECK_FAILURE;
 594                 success = false;
 595                 break;
 596             }
 597
 598             total_nodes_found += pCur_block->m_total_nodes;
 599
 600             blocks.push_back(pCur_block);
 601
 602             pCur_block = pCur_block->m_pNext;
 603         }
 604
 605         blocks.sort();
 606
 607         if (!success)
 608         {
 609             m_update_flag = false;
 610             return false;
 611         }
 612
 613         if (total_blocks_found != m_total_blocks)
 614         {
 615             CHECK_FAILURE;
 616             success = false;
 617         }
 618
 619         if (total_heap_bytes_found != m_total_heap_bytes)
 620         {
 621             CHECK_FAILURE;
 622             success = false;
 623         }
 624
 625         size_t total_free_nodes_found = 0;
 626
 627         node *pCur_node = m_pFirst_free_node;
 628         while (pCur_node)
 629         {
 630 #if VOGL_OBJECT_POOL_DEBUGGING
 631             if (pCur_node->m_marker != cFreeNodeMarker)
 632             {
 633                 CHECK_FAILURE;
 634                 success = false;
 635                 break;
 636             }
 637 #endif
 638
 639             total_free_nodes_found++;
 640             if (total_free_nodes_found > total_nodes_found)
 641             {
 642                 CHECK_FAILURE;
 643                 success = false;
 644                 break;
 645             }
 646
 647             int l = 0, h = blocks.size() - 1;
 648             while (l <= h)
 649             {
 650                 int m = l + ((h - l) >> 1);
 651                 node *pFirst_node = blocks[m]->get_first_node_ptr();
 652                 node *pEnd_node = blocks[m]->get_end_node_ptr();
 653
 654                 if ((pCur_node >= pFirst_node) && (pCur_node < pEnd_node))
 655                     break;
 656                 else if (pCur_node >= pEnd_node)
 657                     l = m + 1;
 658                 else
 659                     h = m - 1;
 660             }
 661
 662             if (l > h)
 663             {
 664                 CHECK_FAILURE;
 665                 success = false;
 666                 break;
 667             }
 668
 669             pCur_node = pCur_node->m_pNext;
 670         }
 671
 672         if (total_free_nodes_found != m_total_free_nodes)
 673         {
 674             CHECK_FAILURE;
 675             success = false;
 676         }
 677
 678         m_update_flag = false;
 679
 680         return success;
 681     }
 682
 683     uint get_flags() const
 684     {
 685         return m_flags;
 686     }
 687     size_t get_grow_size() const
 688     {
 689         return m_grow_size;
 690     }
 691     size_t get_total_blocks() const
 692     {
 693         return m_total_blocks;
 694     }
 695     size_t get_total_heap_bytes() const
 696     {
 697         return m_total_heap_bytes;
 698     }
 699     size_t get_total_nodes() const
 700     {
 701         return m_total_nodes;
 702     }
 703     size_t get_total_free_nodes() const
 704     {
 705         return m_total_free_nodes;
 706     }
 707     size_t get_total_used_nodes() const
 708     {
 709         return m_total_nodes - m_total_free_nodes;
 710     }
 711
 712     void swap(object_pool &other)
 713     {
 714         std::swap(m_flags, other.m_flags);
 715         std::swap(m_grow_size, other.m_grow_size);
 716
 717         std::swap(m_next_grow_size, other.m_next_grow_size);
 718
 719         std::swap(m_total_blocks, other.m_total_blocks);
 720         std::swap(m_total_heap_bytes, other.m_total_heap_bytes);
 721
 722         std::swap(m_pFirst_free_node, other.m_pFirst_free_node);
 723         std::swap(m_total_nodes, other.m_total_nodes);
 724         std::swap(m_total_free_nodes, other.m_total_free_nodes);
 725
 726         std::swap(m_update_flag, other.m_update_flag);
 727
 728         // Now swap m_blocks and other.m_blocks, which is tricky because nodes can point into either.
 729         block temp_blocks(other.m_blocks);
 730
 731         // move m_blocks into other.m_blocks
 732         if (m_blocks.m_pNext == &m_blocks)
 733             other.m_blocks.m_pNext = &other.m_blocks;
 734         else
 735         {
 736             other.m_blocks.m_pNext = m_blocks.m_pNext;
 737             VOGL_ASSERT(m_blocks.m_pNext->m_pPrev == &m_blocks);
 738             m_blocks.m_pNext->m_pPrev = &other.m_blocks;
 739         }
 740
 741         if (m_blocks.m_pPrev == &m_blocks)
 742             other.m_blocks.m_pPrev = &other.m_blocks;
 743         else
 744         {
 745             other.m_blocks.m_pPrev = m_blocks.m_pPrev;
 746             VOGL_ASSERT(m_blocks.m_pPrev->m_pNext == &m_blocks);
 747             m_blocks.m_pPrev->m_pNext = &other.m_blocks;
 748         }
 749
 750         // move other.m_blocks into m_blocks
 751         if (temp_blocks.m_pNext == &other.m_blocks)
 752             m_blocks.m_pNext = &m_blocks;
 753         else
 754         {
 755             m_blocks.m_pNext = temp_blocks.m_pNext;
 756             VOGL_ASSERT(temp_blocks.m_pNext->m_pPrev == &other.m_blocks);
 757             temp_blocks.m_pNext->m_pPrev = &m_blocks;
 758         }
 759
 760         if (temp_blocks.m_pPrev == &other.m_blocks)
 761             m_blocks.m_pPrev = &m_blocks;
 762         else
 763         {
 764             m_blocks.m_pPrev = temp_blocks.m_pPrev;
 765             VOGL_ASSERT(temp_blocks.m_pPrev->m_pNext == &other.m_blocks);
 766             temp_blocks.m_pPrev->m_pNext = &m_blocks;
 767         }
 768
 769         std::swap(m_blocks.m_total_nodes, other.m_blocks.m_total_nodes);
 770     }
 771
 772 private:
 773     enum
 774     {
 775         cBlockBeginMarker = 0x1234ABCD,
 776         cBlockEndMarker = 0xEABC5678,
 777         cUsedNodeMarker = 0xCC139876,
 778         cFreeNodeMarker = 0xFF137654
 779     };
 780
 781     struct raw_obj
 782     {
 783         uint64_t m_bytes[(sizeof(T) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
 784     };
 785
 786     struct node
 787     {
 788 #if VOGL_OBJECT_POOL_DEBUGGING
 789         uint m_marker;
 790 #endif
 791
 792         union
 793         {
 794             node *m_pNext;
 795             raw_obj m_obj;
 796         };
 797
 798         const T *get_object_ptr() const
 799         {
 800             return reinterpret_cast<const T *>(&m_obj);
 801         }
 802
 803         T *get_object_ptr()
 804         {
 805             return reinterpret_cast<T *>(&m_obj);
 806         }
 807     };
 808
 809     struct block
 810     {
 811         uint m_begin_marker;
 812
 813         block *m_pPrev;
 814         block *m_pNext;
 815
 816         size_t m_total_nodes;
 817
 818         uint m_end_marker;
 819
 820         node *get_first_node_ptr()
 821         {
 822             return reinterpret_cast<node *>(reinterpret_cast<uint8 *>(this) + sizeof(block));
 823         }
 824         node *get_end_node_ptr()
 825         {
 826             return reinterpret_cast<node *>(reinterpret_cast<uint8 *>(this) + sizeof(block)) + m_total_nodes;
 827         }
 828     };
 829
 830     uint m_flags;
 831     size_t m_grow_size;
 832
 833     size_t m_next_grow_size;
 834
 835     block m_blocks;
 836     size_t m_total_blocks;
 837     size_t m_total_heap_bytes;
 838
 839     node *m_pFirst_free_node;
 840     size_t m_total_nodes;
 841     size_t m_total_free_nodes;
 842
 843     mutable bool m_update_flag;
 844
 845     void check_failure(uint line) const
 846     {
 847         console::debug("%s: check_failure() obj %p on line %u\n", VOGL_METHOD_NAME, this, line);
 848         VOGL_ASSERT_ALWAYS;
 849     }
 850
 851     block *add_block(size_t size)
 852     {
 853         VOGL_ASSERT(size);
 854         size = math::maximum<size_t>(1U, size);
 855
 856         block *pBlock = static_cast<block *>(vogl_malloc(sizeof(block) + size * sizeof(node)));
 857
 858         m_total_blocks++;
 859         m_total_heap_bytes += vogl_msize(pBlock);
 860
 861         m_total_nodes += size;
 862         m_total_free_nodes += size;
 863
 864         pBlock->m_begin_marker = cBlockBeginMarker;
 865         pBlock->m_end_marker = cBlockEndMarker;
 866
 867         pBlock->m_total_nodes = size;
 868
 869         pBlock->m_pPrev = &m_blocks;
 870         pBlock->m_pNext = m_blocks.m_pNext;
 871
 872         VOGL_ASSERT(m_blocks.m_pNext->m_pPrev == &m_blocks);
 873         m_blocks.m_pNext->m_pPrev = pBlock;
 874
 875         m_blocks.m_pNext = pBlock;
 876
 877         for (size_t i = size; i; --i)
 878         {
 879             node *pNode = pBlock->get_first_node_ptr() + i - 1;
 880
 881 #if VOGL_OBJECT_POOL_DEBUGGING
 882             pNode->m_marker = cFreeNodeMarker;
 883 #endif
 884
 885             pNode->m_pNext = m_pFirst_free_node;
 886             m_pFirst_free_node = pNode;
 887         }
 888
 889         return pBlock;
 890     }
 891
 892     block *grow()
 893     {
 894         add_block(m_next_grow_size);
 895
 896         if (m_flags & cObjectPoolGrowExponential)
 897         {
 898             size_t prev_grow_size = m_next_grow_size;
 899
 900             m_next_grow_size <<= 1U;
 901
 902             if ((m_next_grow_size >> 1U) != prev_grow_size)
 903                 m_next_grow_size = prev_grow_size;
 904         }
 905
 906         return m_blocks.m_pNext;
 907     }
 908
 909     inline node *alloc_node()
 910     {
 911         VOGL_ASSERT(!m_update_flag);
 912
 913         LockingPolicy::lock();
 914
 915         if (!m_pFirst_free_node)
 916             grow();
 917
 918         VOGL_ASSERT(m_total_free_nodes);
 919
 920         node *pNode = m_pFirst_free_node;
 921
 922 #if VOGL_OBJECT_POOL_DEBUGGING
 923         VOGL_ASSERT(pNode->m_marker == cFreeNodeMarker);
 924         pNode->m_marker = cUsedNodeMarker;
 925 #endif
 926
 927         m_pFirst_free_node = pNode->m_pNext;
 928
 929         --m_total_free_nodes;
 930
 931         LockingPolicy::unlock();
 932
 933         return pNode;
 934     }
 935
 936     size_t clear_internal()
 937     {
 938         VOGL_ASSERT(!m_update_flag);
 939
 940         m_update_flag = true;
 941
 942         size_t total_bytes_freed = m_total_heap_bytes;
 943
 944         size_t total_blocks_found = 0;
 945         VOGL_NOTE_UNUSED(total_blocks_found);
 946
 947         block *pCur_block = m_blocks.m_pNext;
 948         while (pCur_block != &m_blocks)
 949         {
 950             VOGL_ASSERT(pCur_block->m_begin_marker == cBlockBeginMarker);
 951             VOGL_ASSERT(pCur_block->m_end_marker == cBlockEndMarker);
 952
 953             total_blocks_found++;
 954             VOGL_ASSERT(total_blocks_found <= m_total_blocks);
 955
 956             block *pNext_block = pCur_block->m_pNext;
 957
 958             vogl_free(pCur_block);
 959
 960             pCur_block = pNext_block;
 961         }
 962
 963         VOGL_ASSERT(total_blocks_found == m_total_blocks);
 964
 965         m_next_grow_size = math::maximum<size_t>(1U, m_grow_size);
 966
 967         m_blocks.m_pPrev = &m_blocks;
 968         m_blocks.m_pNext = &m_blocks;
 969
 970         m_pFirst_free_node = NULL;
 971         m_total_nodes = 0;
 972         m_total_free_nodes = 0;
 973
 974         m_total_blocks = 0;
 975         m_total_heap_bytes = 0;
 976
 977         m_update_flag = false;
 978
 979         return total_bytes_freed;
 980     }
 981 };
 982
 983 #undef CHECK_FAILURE
 984
 985 bool object_pool_test();
 986
 987 VOGL_NAMESPACE_END(vogl)
 988
 989 #endif // VOGL_OBJECT_POOL_H