git.cworth.org Git - vogl/blob - src/extlib/loki/src/SmallObj.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 // The Loki Library
   3 // Copyright (c) 2001 by Andrei Alexandrescu
   4 // This code accompanies the book:
   5 // Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design
   6 //     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
   7 // Permission to use, copy, modify, distribute and sell this software for any
   8 //     purpose is hereby granted without fee, provided that the above  copyright
   9 //     notice appear in all copies and that both that copyright notice and this
  10 //     permission notice appear in supporting documentation.
  11 // The author or Addison-Wesley Longman make no representations about the
  12 //     suitability of this software for any purpose. It is provided "as is"
  13 //     without express or implied warranty.
  14 ////////////////////////////////////////////////////////////////////////////////
  15
  16 // $Id: SmallObj.cpp 823 2007-05-08 10:48:40Z lfittl $
  17
  18
  19 #include <loki/SmallObj.h>
  20
  21 #include <cassert>
  22 #include <climits>
  23 #include <vector>
  24 #include <bitset>
  25
  26 //#define DO_EXTRA_LOKI_TESTS
  27 //#define USE_NEW_TO_ALLOCATE
  28 //#define LOKI_CHECK_FOR_CORRUPTION
  29
  30 #ifdef DO_EXTRA_LOKI_TESTS
  31 #include <iostream>
  32 #endif
  33
  34 namespace Loki
  35 {
  36
  37 /** @struct Chunk
  38     @ingroup SmallObjectGroupInternal
  39  Contains info about each allocated Chunk - which is a collection of
  40  contiguous blocks.  Each block is the same size, as specified by the
  41  FixedAllocator.  The number of blocks in a Chunk depends upon page size.
  42  This is a POD-style struct with value-semantics.  All functions and data
  43  are private so that they can not be changed by anything other than the
  44  FixedAllocator which owns the Chunk.
  45
  46  @par Minimal Interface
  47  For the sake of runtime efficiency, no constructor, destructor, or
  48  copy-assignment operator is defined. The inline functions made by the
  49  compiler should be sufficient, and perhaps faster than hand-crafted
  50  functions.  The lack of these functions allows vector to create and copy
  51  Chunks as needed without overhead.  The Init and Release functions do
  52  what the default constructor and destructor would do.  A Chunk is not in
  53  a usable state after it is constructed and before calling Init.  Nor is
  54  a Chunk usable after Release is called, but before the destructor.
  55
  56  @par Efficiency
  57  Down near the lowest level of the allocator, runtime efficiencies trump
  58  almost all other considerations.  Each function does the minimum required
  59  of it.  All functions should execute in constant time to prevent higher-
  60  level code from unwittingly using a version of Shlemiel the Painter's
  61  Algorithm.
  62
  63  @par Stealth Indexes
  64  The first char of each empty block contains the index of the next empty
  65  block.  These stealth indexes form a singly-linked list within the blocks.
  66  A Chunk is corrupt if this singly-linked list has a loop or is shorter
  67  than blocksAvailable_.  Much of the allocator's time and space efficiency
  68  comes from how these stealth indexes are implemented.
  69  */
  70 class Chunk
  71 {
  72 private:
  73         friend class FixedAllocator;
  74
  75         /** Initializes a just-constructed Chunk.
  76          @param blockSize Number of bytes per block.
  77          @param blocks Number of blocks per Chunk.
  78          @return True for success, false for failure.
  79          */
  80         bool Init( std::size_t blockSize, unsigned char blocks );
  81
  82         /** Allocate a block within the Chunk.  Complexity is always O(1), and
  83          this will never throw.  Does not actually "allocate" by calling
  84          malloc, new, or any other function, but merely adjusts some internal
  85          indexes to indicate an already allocated block is no longer available.
  86          @return Pointer to block within Chunk.
  87          */
  88         void *Allocate( std::size_t blockSize );
  89
  90         /** Deallocate a block within the Chunk. Complexity is always O(1), and
  91          this will never throw.  For efficiency, this assumes the address is
  92          within the block and aligned along the correct byte boundary.  An
  93          assertion checks the alignment, and a call to HasBlock is done from
  94          within VicinityFind.  Does not actually "deallocate" by calling free,
  95          delete, or other function, but merely adjusts some internal indexes to
  96          indicate a block is now available.
  97          */
  98         void Deallocate( void *p, std::size_t blockSize );
  99
 100         /** Resets the Chunk back to pristine values. The available count is
 101          set back to zero, and the first available index is set to the zeroth
 102          block.  The stealth indexes inside each block are set to point to the
 103          next block. This assumes the Chunk's data was already using Init.
 104          */
 105         void Reset( std::size_t blockSize, unsigned char blocks );
 106
 107         /// Releases the allocated block of memory.
 108         void Release();
 109
 110         /** Determines if the Chunk has been corrupted.
 111          @param numBlocks Total # of blocks in the Chunk.
 112          @param blockSize # of bytes in each block.
 113          @param checkIndexes True if caller wants to check indexes of available
 114           blocks for corruption.  If false, then caller wants to skip some
 115           tests tests just to run faster.  (Debug version does more checks, but
 116           release version runs faster.)
 117          @return True if Chunk is corrupt.
 118          */
 119         bool IsCorrupt( unsigned char numBlocks, std::size_t blockSize,
 120                         bool checkIndexes ) const;
 121
 122         /** Determines if block is available.
 123          @param p Address of block managed by Chunk.
 124          @param numBlocks Total # of blocks in the Chunk.
 125          @param blockSize # of bytes in each block.
 126          @return True if block is available, else false if allocated.
 127          */
 128         bool IsBlockAvailable( void *p, unsigned char numBlocks,
 129                                std::size_t blockSize ) const;
 130
 131         /// Returns true if block at address P is inside this Chunk.
 132         inline bool HasBlock( void *p, std::size_t chunkLength ) const
 133         {
 134                 unsigned char *pc = static_cast< unsigned char * >( p );
 135                 return ( pData_ <= pc ) && ( pc < pData_ + chunkLength );
 136         }
 137
 138         inline bool HasAvailable( unsigned char numBlocks ) const
 139         {
 140                 return ( blocksAvailable_ == numBlocks );
 141         }
 142
 143         inline bool IsFilled( void ) const
 144         {
 145                 return ( 0 == blocksAvailable_ );
 146         }
 147
 148         /// Pointer to array of allocated blocks.
 149         unsigned char *pData_;
 150         /// Index of first empty block.
 151         unsigned char firstAvailableBlock_;
 152         /// Count of empty blocks.
 153         unsigned char blocksAvailable_;
 154 };
 155
 156 /** @class FixedAllocator
 157     @ingroup SmallObjectGroupInternal
 158  Offers services for allocating fixed-sized objects.  It has a container
 159  of "containers" of fixed-size blocks.  The outer container has all the
 160  Chunks.  The inner container is a Chunk which owns some blocks.
 161
 162  @par Class Level Invariants
 163  - There is always either zero or one Chunk which is empty.
 164  - If this has no empty Chunk, then emptyChunk_ is NULL.
 165  - If this has an empty Chunk, then emptyChunk_ points to it.
 166  - If the Chunk container is empty, then deallocChunk_ and allocChunk_
 167    are NULL.
 168  - If the Chunk container is not-empty, then deallocChunk_ and allocChunk_
 169    are either NULL or point to Chunks within the container.
 170  - allocChunk_ will often point to the last Chunk in the container since
 171    it was likely allocated most recently, and therefore likely to have an
 172    available block.
 173  */
 174 class FixedAllocator
 175 {
 176 private:
 177
 178         /** Deallocates the block at address p, and then handles the internal
 179          bookkeeping needed to maintain class invariants.  This assumes that
 180          deallocChunk_ points to the correct chunk.
 181          */
 182         void DoDeallocate( void *p );
 183
 184         /** Creates an empty Chunk and adds it to the end of the ChunkList.
 185          All calls to the lower-level memory allocation functions occur inside
 186          this function, and so the only try-catch block is inside here.
 187          @return true for success, false for failure.
 188          */
 189         bool MakeNewChunk( void );
 190
 191         /** Finds the Chunk which owns the block at address p.  It starts at
 192          deallocChunk_ and searches in both forwards and backwards directions
 193          from there until it finds the Chunk which owns p.  This algorithm
 194          should find the Chunk quickly if it is deallocChunk_ or is close to it
 195          in the Chunks container.  This goes both forwards and backwards since
 196          that works well for both same-order and opposite-order deallocations.
 197          (Same-order = objects are deallocated in the same order in which they
 198          were allocated.  Opposite order = objects are deallocated in a last to
 199          first order.  Complexity is O(C) where C is count of all Chunks.  This
 200          never throws.
 201          @return Pointer to Chunk that owns p, or NULL if no owner found.
 202          */
 203         Chunk *VicinityFind( void *p ) const;
 204
 205         /// Not implemented.
 206         FixedAllocator(const FixedAllocator &);
 207         /// Not implemented.
 208         FixedAllocator &operator=(const FixedAllocator &);
 209
 210         /// Type of container used to hold Chunks.
 211         typedef std::vector< Chunk > Chunks;
 212         /// Iterator through container of Chunks.
 213         typedef Chunks::iterator ChunkIter;
 214         /// Iterator through const container of Chunks.
 215         typedef Chunks::const_iterator ChunkCIter;
 216
 217         /// Fewest # of objects managed by a Chunk.
 218         static unsigned char MinObjectsPerChunk_;
 219
 220         /// Most # of objects managed by a Chunk - never exceeds UCHAR_MAX.
 221         static unsigned char MaxObjectsPerChunk_;
 222
 223         /// Number of bytes in a single block within a Chunk.
 224         std::size_t blockSize_;
 225         /// Number of blocks managed by each Chunk.
 226         unsigned char numBlocks_;
 227
 228         /// Container of Chunks.
 229         Chunks chunks_;
 230         /// Pointer to Chunk used for last or next allocation.
 231         Chunk *allocChunk_;
 232         /// Pointer to Chunk used for last or next deallocation.
 233         Chunk *deallocChunk_;
 234         /// Pointer to the only empty Chunk if there is one, else NULL.
 235         Chunk *emptyChunk_;
 236
 237 public:
 238         /// Create a FixedAllocator which manages blocks of 'blockSize' size.
 239         FixedAllocator();
 240
 241         /// Destroy the FixedAllocator and release all its Chunks.
 242         ~FixedAllocator();
 243
 244         /// Initializes a FixedAllocator by calculating # of blocks per Chunk.
 245         void Initialize( std::size_t blockSize, std::size_t pageSize );
 246
 247         /** Returns pointer to allocated memory block of fixed size - or NULL
 248          if it failed to allocate.
 249          */
 250         void *Allocate( void );
 251
 252         /** Deallocate a memory block previously allocated with Allocate.  If
 253          the block is not owned by this FixedAllocator, it returns false so
 254          that SmallObjAllocator can call the default deallocator.  If the
 255          block was found, this returns true.
 256          */
 257         bool Deallocate( void *p, Chunk *hint );
 258
 259         /// Returns block size with which the FixedAllocator was initialized.
 260         inline std::size_t BlockSize() const
 261         {
 262                 return blockSize_;
 263         }
 264
 265         /** Releases the memory used by the empty Chunk.  This will take
 266          constant time under any situation.
 267          @return True if empty chunk found and released, false if none empty.
 268          */
 269         bool TrimEmptyChunk( void );
 270
 271         /** Releases unused spots from ChunkList.  This takes constant time
 272          with respect to # of Chunks, but actual time depends on underlying
 273          memory allocator.
 274          @return False if no unused spots, true if some found and released.
 275          */
 276         bool TrimChunkList( void );
 277
 278         /** Returns count of empty Chunks held by this allocator.  Complexity
 279          is O(C) where C is the total number of Chunks - empty or used.
 280          */
 281         std::size_t CountEmptyChunks( void ) const;
 282
 283         /** Determines if FixedAllocator is corrupt.  Checks data members to
 284          see if any have erroneous values, or violate class invariants.  It
 285          also checks if any Chunk is corrupt.  Complexity is O(C) where C is
 286          the number of Chunks.  If any data is corrupt, this will return true
 287          in release mode, or assert in debug mode.
 288          */
 289         bool IsCorrupt( void ) const;
 290
 291         /** Returns true if the block at address p is within a Chunk owned by
 292          this FixedAllocator.  Complexity is O(C) where C is the total number
 293          of Chunks - empty or used.
 294          */
 295         const Chunk *HasBlock( void *p ) const;
 296         inline Chunk *HasBlock( void *p )
 297         {
 298                 return const_cast< Chunk * >(
 299                            const_cast< const FixedAllocator * >( this )->HasBlock( p ) );
 300         }
 301
 302 };
 303
 304 unsigned char FixedAllocator::MinObjectsPerChunk_ = 8;
 305 unsigned char FixedAllocator::MaxObjectsPerChunk_ = UCHAR_MAX;
 306
 307 // Chunk::Init ----------------------------------------------------------------
 308
 309 bool Chunk::Init( std::size_t blockSize, unsigned char blocks )
 310 {
 311         assert(blockSize > 0);
 312         assert(blocks > 0);
 313         // Overflow check
 314         const std::size_t allocSize = blockSize * blocks;
 315         assert( allocSize / blockSize == blocks);
 316
 317 #ifdef USE_NEW_TO_ALLOCATE
 318         // If this new operator fails, it will throw, and the exception will get
 319         // caught one layer up.
 320         pData_ = static_cast< unsigned char * >( ::operator new ( allocSize ) );
 321 #else
 322         // malloc can't throw, so its only way to indicate an error is to return
 323         // a NULL pointer, so we have to check for that.
 324         pData_ = static_cast< unsigned char * >( ::std::malloc( allocSize ) );
 325         if ( NULL == pData_ ) return false;
 326 #endif
 327
 328         Reset( blockSize, blocks );
 329         return true;
 330 }
 331
 332 // Chunk::Reset ---------------------------------------------------------------
 333
 334 void Chunk::Reset(std::size_t blockSize, unsigned char blocks)
 335 {
 336         assert(blockSize > 0);
 337         assert(blocks > 0);
 338         // Overflow check
 339         assert((blockSize * blocks) / blockSize == blocks);
 340
 341         firstAvailableBlock_ = 0;
 342         blocksAvailable_ = blocks;
 343
 344         unsigned char i = 0;
 345         for ( unsigned char *p = pData_; i != blocks; p += blockSize )
 346         {
 347                 *p = ++i;
 348         }
 349 }
 350
 351 // Chunk::Release -------------------------------------------------------------
 352
 353 void Chunk::Release()
 354 {
 355         assert( NULL != pData_ );
 356 #ifdef USE_NEW_TO_ALLOCATE
 357         ::operator delete ( pData_ );
 358 #else
 359         ::std::free( static_cast< void * >( pData_ ) );
 360 #endif
 361 }
 362
 363 // Chunk::Allocate ------------------------------------------------------------
 364
 365 void *Chunk::Allocate(std::size_t blockSize)
 366 {
 367         if ( IsFilled() ) return NULL;
 368
 369         assert((firstAvailableBlock_ * blockSize) / blockSize ==
 370                firstAvailableBlock_);
 371         unsigned char *pResult = pData_ + (firstAvailableBlock_ * blockSize);
 372         firstAvailableBlock_ = *pResult;
 373         --blocksAvailable_;
 374
 375         return pResult;
 376 }
 377
 378 // Chunk::Deallocate ----------------------------------------------------------
 379
 380 void Chunk::Deallocate(void *p, std::size_t blockSize)
 381 {
 382         assert(p >= pData_);
 383
 384         unsigned char *toRelease = static_cast<unsigned char *>(p);
 385         // Alignment check
 386         assert((toRelease - pData_) % blockSize == 0);
 387         unsigned char index = static_cast< unsigned char >(
 388                                   ( toRelease - pData_ ) / blockSize);
 389
 390 #if defined(DEBUG) || defined(_DEBUG)
 391         // Check if block was already deleted.  Attempting to delete the same
 392         // block more than once causes Chunk's linked-list of stealth indexes to
 393         // become corrupt.  And causes count of blocksAvailable_ to be wrong.
 394         if ( 0 < blocksAvailable_ )
 395                 assert( firstAvailableBlock_ != index );
 396 #endif
 397
 398         *toRelease = firstAvailableBlock_;
 399         firstAvailableBlock_ = index;
 400         // Truncation check
 401         assert(firstAvailableBlock_ == (toRelease - pData_) / blockSize);
 402
 403         ++blocksAvailable_;
 404 }
 405
 406 // Chunk::IsCorrupt -----------------------------------------------------------
 407
 408 bool Chunk::IsCorrupt( unsigned char numBlocks, std::size_t blockSize,
 409                        bool checkIndexes ) const
 410 {
 411
 412         if ( numBlocks < blocksAvailable_ )
 413         {
 414                 // Contents at this Chunk corrupted.  This might mean something has
 415                 // overwritten memory owned by the Chunks container.
 416                 assert( false );
 417                 return true;
 418         }
 419         if ( IsFilled() )
 420                 // Useless to do further corruption checks if all blocks allocated.
 421                 return false;
 422         unsigned char index = firstAvailableBlock_;
 423         if ( numBlocks <= index )
 424         {
 425                 // Contents at this Chunk corrupted.  This might mean something has
 426                 // overwritten memory owned by the Chunks container.
 427                 assert( false );
 428                 return true;
 429         }
 430         if ( !checkIndexes )
 431                 // Caller chose to skip more complex corruption tests.
 432                 return false;
 433
 434         /* If the bit at index was set in foundBlocks, then the stealth index was
 435          found on the linked-list.
 436          */
 437         std::bitset< UCHAR_MAX > foundBlocks;
 438         unsigned char *nextBlock = NULL;
 439
 440         /* The loop goes along singly linked-list of stealth indexes and makes sure
 441          that each index is within bounds (0 <= index < numBlocks) and that the
 442          index was not already found while traversing the linked-list.  The linked-
 443          list should have exactly blocksAvailable_ nodes, so the for loop will not
 444          check more than blocksAvailable_.  This loop can't check inside allocated
 445          blocks for corruption since such blocks are not within the linked-list.
 446          Contents of allocated blocks are not changed by Chunk.
 447
 448          Here are the types of corrupted link-lists which can be verified.  The
 449          corrupt index is shown with asterisks in each example.
 450
 451          Type 1: Index is too big.
 452           numBlocks == 64
 453           blocksAvailable_ == 7
 454           firstAvailableBlock_ -> 17 -> 29 -> *101*
 455           There should be no indexes which are equal to or larger than the total
 456           number of blocks.  Such an index would refer to a block beyond the
 457           Chunk's allocated domain.
 458
 459          Type 2: Index is repeated.
 460           numBlocks == 64
 461           blocksAvailable_ == 5
 462           firstAvailableBlock_ -> 17 -> 29 -> 53 -> *17* -> 29 -> 53 ...
 463           No index should be repeated within the linked-list since that would
 464           indicate the presence of a loop in the linked-list.
 465          */
 466         for ( unsigned char cc = 0; ; )
 467         {
 468                 nextBlock = pData_ + ( index * blockSize );
 469                 foundBlocks.set( index, true );
 470                 ++cc;
 471                 if ( cc >= blocksAvailable_ )
 472                         // Successfully counted off number of nodes in linked-list.
 473                         break;
 474                 index = *nextBlock;
 475                 if ( numBlocks <= index )
 476                 {
 477                         /* This catches Type 1 corruptions as shown in above comments.
 478                          This implies that a block was corrupted due to a stray pointer
 479                          or an operation on a nearby block overran the size of the block.
 480                          */
 481                         assert( false );
 482                         return true;
 483                 }
 484                 if ( foundBlocks.test( index ) )
 485                 {
 486                         /* This catches Type 2 corruptions as shown in above comments.
 487                          This implies that a block was corrupted due to a stray pointer
 488                          or an operation on a nearby block overran the size of the block.
 489                          Or perhaps the program tried to delete a block more than once.
 490                          */
 491                         assert( false );
 492                         return true;
 493                 }
 494         }
 495         if ( foundBlocks.count() != blocksAvailable_ )
 496         {
 497                 /* This implies that the singly-linked-list of stealth indexes was
 498                  corrupted.  Ideally, this should have been detected within the loop.
 499                  */
 500                 assert( false );
 501                 return true;
 502         }
 503
 504         return false;
 505 }
 506
 507 // Chunk::IsBlockAvailable ----------------------------------------------------
 508
 509 bool Chunk::IsBlockAvailable( void *p, unsigned char numBlocks,
 510                               std::size_t blockSize ) const
 511 {
 512         (void) numBlocks;
 513
 514         if ( IsFilled() )
 515                 return false;
 516
 517         unsigned char *place = static_cast< unsigned char * >( p );
 518         // Alignment check
 519         assert( ( place - pData_ ) % blockSize == 0 );
 520         unsigned char blockIndex = static_cast< unsigned char >(
 521                                        ( place - pData_ ) / blockSize );
 522
 523         unsigned char index = firstAvailableBlock_;
 524         assert( numBlocks > index );
 525         if ( index == blockIndex )
 526                 return true;
 527
 528         /* If the bit at index was set in foundBlocks, then the stealth index was
 529          found on the linked-list.
 530          */
 531         std::bitset< UCHAR_MAX > foundBlocks;
 532         unsigned char *nextBlock = NULL;
 533         for ( unsigned char cc = 0; ; )
 534         {
 535                 nextBlock = pData_ + ( index * blockSize );
 536                 foundBlocks.set( index, true );
 537                 ++cc;
 538                 if ( cc >= blocksAvailable_ )
 539                         // Successfully counted off number of nodes in linked-list.
 540                         break;
 541                 index = *nextBlock;
 542                 if ( index == blockIndex )
 543                         return true;
 544                 assert( numBlocks > index );
 545                 assert( !foundBlocks.test( index ) );
 546         }
 547
 548         return false;
 549 }
 550
 551 // FixedAllocator::FixedAllocator ---------------------------------------------
 552
 553 FixedAllocator::FixedAllocator()
 554         : blockSize_( 0 )
 555         , numBlocks_( 0 )
 556         , chunks_( 0 )
 557         , allocChunk_( NULL )
 558         , deallocChunk_( NULL )
 559         , emptyChunk_( NULL )
 560 {
 561 }
 562
 563 // FixedAllocator::~FixedAllocator --------------------------------------------
 564
 565 FixedAllocator::~FixedAllocator()
 566 {
 567 #ifdef DO_EXTRA_LOKI_TESTS
 568         TrimEmptyChunk();
 569         assert( chunks_.empty() && "Memory leak detected!" );
 570 #endif
 571         for ( ChunkIter i( chunks_.begin() ); i != chunks_.end(); ++i )
 572                 i->Release();
 573 }
 574
 575 // FixedAllocator::Initialize -------------------------------------------------
 576
 577 void FixedAllocator::Initialize( std::size_t blockSize, std::size_t pageSize )
 578 {
 579         assert( blockSize > 0 );
 580         assert( pageSize >= blockSize );
 581         blockSize_ = blockSize;
 582
 583         std::size_t numBlocks = pageSize / blockSize;
 584         if ( numBlocks > MaxObjectsPerChunk_ ) numBlocks = MaxObjectsPerChunk_;
 585         else if ( numBlocks < MinObjectsPerChunk_ ) numBlocks = MinObjectsPerChunk_;
 586
 587         numBlocks_ = static_cast<unsigned char>(numBlocks);
 588         assert(numBlocks_ == numBlocks);
 589 }
 590
 591 // FixedAllocator::CountEmptyChunks -------------------------------------------
 592
 593 std::size_t FixedAllocator::CountEmptyChunks( void ) const
 594 {
 595 #ifdef DO_EXTRA_LOKI_TESTS
 596         // This code is only used for specialized tests of the allocator.
 597         // It is #ifdef-ed so that its O(C) complexity does not overwhelm the
 598         // functions which call it.
 599         std::size_t count = 0;
 600         for ( ChunkCIter it( chunks_.begin() ); it != chunks_.end(); ++it )
 601         {
 602                 const Chunk &chunk = *it;
 603                 if ( chunk.HasAvailable( numBlocks_ ) )
 604                         ++count;
 605         }
 606         return count;
 607 #else
 608         return ( NULL == emptyChunk_ ) ? 0 : 1;
 609 #endif
 610 }
 611
 612 // FixedAllocator::IsCorrupt --------------------------------------------------
 613
 614 bool FixedAllocator::IsCorrupt( void ) const
 615 {
 616         const bool isEmpty = chunks_.empty();
 617         ChunkCIter start( chunks_.begin() );
 618         ChunkCIter last( chunks_.end() );
 619         const size_t emptyChunkCount = CountEmptyChunks();
 620
 621         if ( isEmpty )
 622         {
 623                 if ( start != last )
 624                 {
 625                         assert( false );
 626                         return true;
 627                 }
 628                 if ( 0 < emptyChunkCount )
 629                 {
 630                         assert( false );
 631                         return true;
 632                 }
 633                 if ( NULL != deallocChunk_ )
 634                 {
 635                         assert( false );
 636                         return true;
 637                 }
 638                 if ( NULL != allocChunk_ )
 639                 {
 640                         assert( false );
 641                         return true;
 642                 }
 643                 if ( NULL != emptyChunk_ )
 644                 {
 645                         assert( false );
 646                         return true;
 647                 }
 648         }
 649
 650         else
 651         {
 652                 const Chunk *front = &chunks_.front();
 653                 const Chunk *back  = &chunks_.back();
 654                 if ( start >= last )
 655                 {
 656                         assert( false );
 657                         return true;
 658                 }
 659                 if ( back < deallocChunk_ )
 660                 {
 661                         assert( false );
 662                         return true;
 663                 }
 664                 if ( back < allocChunk_ )
 665                 {
 666                         assert( false );
 667                         return true;
 668                 }
 669                 if ( front > deallocChunk_ )
 670                 {
 671                         assert( false );
 672                         return true;
 673                 }
 674                 if ( front > allocChunk_ )
 675                 {
 676                         assert( false );
 677                         return true;
 678                 }
 679
 680                 switch ( emptyChunkCount )
 681                 {
 682                 case 0:
 683                         if ( emptyChunk_ != NULL )
 684                         {
 685                                 assert( false );
 686                                 return true;
 687                         }
 688                         break;
 689                 case 1:
 690                         if ( emptyChunk_ == NULL )
 691                         {
 692                                 assert( false );
 693                                 return true;
 694                         }
 695                         if ( back < emptyChunk_ )
 696                         {
 697                                 assert( false );
 698                                 return true;
 699                         }
 700                         if ( front > emptyChunk_ )
 701                         {
 702                                 assert( false );
 703                                 return true;
 704                         }
 705                         if ( !emptyChunk_->HasAvailable( numBlocks_ ) )
 706                         {
 707                                 // This may imply somebody tried to delete a block twice.
 708                                 assert( false );
 709                                 return true;
 710                         }
 711                         break;
 712                 default:
 713                         assert( false );
 714                         return true;
 715                 }
 716                 for ( ChunkCIter it( start ); it != last; ++it )
 717                 {
 718                         const Chunk &chunk = *it;
 719                         if ( chunk.IsCorrupt( numBlocks_, blockSize_, true ) )
 720                                 return true;
 721                 }
 722         }
 723
 724         return false;
 725 }
 726
 727 // FixedAllocator::HasBlock ---------------------------------------------------
 728
 729 const Chunk *FixedAllocator::HasBlock( void *p ) const
 730 {
 731         const std::size_t chunkLength = numBlocks_ * blockSize_;
 732         for ( ChunkCIter it( chunks_.begin() ); it != chunks_.end(); ++it )
 733         {
 734                 const Chunk &chunk = *it;
 735                 if ( chunk.HasBlock( p, chunkLength ) )
 736                         return &chunk;
 737         }
 738         return NULL;
 739 }
 740
 741 // FixedAllocator::TrimEmptyChunk ---------------------------------------------
 742
 743 bool FixedAllocator::TrimEmptyChunk( void )
 744 {
 745         // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
 746         assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
 747         if ( NULL == emptyChunk_ ) return false;
 748
 749         // If emptyChunk_ points to valid Chunk, then chunk list is not empty.
 750         assert( !chunks_.empty() );
 751         // And there should be exactly 1 empty Chunk.
 752         assert( 1 == CountEmptyChunks() );
 753
 754         Chunk *lastChunk = &chunks_.back();
 755         if ( lastChunk != emptyChunk_ )
 756                 std::swap( *emptyChunk_, *lastChunk );
 757         assert( lastChunk->HasAvailable( numBlocks_ ) );
 758         lastChunk->Release();
 759         chunks_.pop_back();
 760
 761         if ( chunks_.empty() )
 762         {
 763                 allocChunk_ = NULL;
 764                 deallocChunk_ = NULL;
 765         }
 766         else
 767         {
 768                 if ( deallocChunk_ == emptyChunk_ )
 769                 {
 770                         deallocChunk_ = &chunks_.front();
 771                         assert( deallocChunk_->blocksAvailable_ < numBlocks_ );
 772                 }
 773                 if ( allocChunk_ == emptyChunk_ )
 774                 {
 775                         allocChunk_ = &chunks_.back();
 776                         assert( allocChunk_->blocksAvailable_ < numBlocks_ );
 777                 }
 778         }
 779
 780         emptyChunk_ = NULL;
 781         assert( 0 == CountEmptyChunks() );
 782
 783         return true;
 784 }
 785
 786 // FixedAllocator::TrimChunkList ----------------------------------------------
 787
 788 bool FixedAllocator::TrimChunkList( void )
 789 {
 790         if ( chunks_.empty() )
 791         {
 792                 assert( NULL == allocChunk_ );
 793                 assert( NULL == deallocChunk_ );
 794         }
 795
 796         if ( chunks_.size() == chunks_.capacity() )
 797                 return false;
 798         // Use the "make-a-temp-and-swap" trick to remove excess capacity.
 799         Chunks( chunks_ ).swap( chunks_ );
 800
 801         return true;
 802 }
 803
 804 // FixedAllocator::MakeNewChunk -----------------------------------------------
 805
 806 bool FixedAllocator::MakeNewChunk( void )
 807 {
 808         bool allocated = false;
 809         try
 810         {
 811                 std::size_t size = chunks_.size();
 812                 // Calling chunks_.reserve *before* creating and initializing the new
 813                 // Chunk means that nothing is leaked by this function in case an
 814                 // exception is thrown from reserve.
 815                 if ( chunks_.capacity() == size )
 816                 {
 817                         if ( 0 == size ) size = 4;
 818                         chunks_.reserve( size * 2 );
 819                 }
 820                 Chunk newChunk;
 821                 allocated = newChunk.Init( blockSize_, numBlocks_ );
 822                 if ( allocated )
 823                         chunks_.push_back( newChunk );
 824         }
 825         catch ( ... )
 826         {
 827                 allocated = false;
 828         }
 829         if ( !allocated ) return false;
 830
 831         allocChunk_ = &chunks_.back();
 832         deallocChunk_ = &chunks_.front();
 833         return true;
 834 }
 835
 836 // FixedAllocator::Allocate ---------------------------------------------------
 837
 838 void *FixedAllocator::Allocate( void )
 839 {
 840         // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
 841         assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
 842         assert( CountEmptyChunks() < 2 );
 843
 844         if ( ( NULL == allocChunk_ ) || allocChunk_->IsFilled() )
 845         {
 846                 if ( NULL != emptyChunk_ )
 847                 {
 848                         allocChunk_ = emptyChunk_;
 849                         emptyChunk_ = NULL;
 850                 }
 851                 else
 852                 {
 853                         for ( ChunkIter i( chunks_.begin() ); ; ++i )
 854                         {
 855                                 if ( chunks_.end() == i )
 856                                 {
 857                                         if ( !MakeNewChunk() )
 858                                                 return NULL;
 859                                         break;
 860                                 }
 861                                 if ( !i->IsFilled() )
 862                                 {
 863                                         allocChunk_ = &*i;
 864                                         break;
 865                                 }
 866                         }
 867                 }
 868         }
 869         else if ( allocChunk_ == emptyChunk_)
 870                 // detach emptyChunk_ from allocChunk_, because after
 871                 // calling allocChunk_->Allocate(blockSize_); the chunk
 872                 // is no longer empty.
 873                 emptyChunk_ = NULL;
 874
 875         assert( allocChunk_ != NULL );
 876         assert( !allocChunk_->IsFilled() );
 877         void *place = allocChunk_->Allocate( blockSize_ );
 878
 879         // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
 880         assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
 881         assert( CountEmptyChunks() < 2 );
 882 #ifdef LOKI_CHECK_FOR_CORRUPTION
 883         if ( allocChunk_->IsCorrupt( numBlocks_, blockSize_, true ) )
 884         {
 885                 assert( false );
 886                 return NULL;
 887         }
 888 #endif
 889
 890         return place;
 891 }
 892
 893 // FixedAllocator::Deallocate -------------------------------------------------
 894
 895 bool FixedAllocator::Deallocate( void *p, Chunk *hint )
 896 {
 897         assert(!chunks_.empty());
 898         assert(&chunks_.front() <= deallocChunk_);
 899         assert(&chunks_.back() >= deallocChunk_);
 900         assert( &chunks_.front() <= allocChunk_ );
 901         assert( &chunks_.back() >= allocChunk_ );
 902         assert( CountEmptyChunks() < 2 );
 903
 904         Chunk *foundChunk = ( NULL == hint ) ? VicinityFind( p ) : hint;
 905         if ( NULL == foundChunk )
 906                 return false;
 907
 908         assert( foundChunk->HasBlock( p, numBlocks_ * blockSize_ ) );
 909 #ifdef LOKI_CHECK_FOR_CORRUPTION
 910         if ( foundChunk->IsCorrupt( numBlocks_, blockSize_, true ) )
 911         {
 912                 assert( false );
 913                 return false;
 914         }
 915         if ( foundChunk->IsBlockAvailable( p, numBlocks_, blockSize_ ) )
 916         {
 917                 assert( false );
 918                 return false;
 919         }
 920 #endif
 921         deallocChunk_ = foundChunk;
 922         DoDeallocate(p);
 923         assert( CountEmptyChunks() < 2 );
 924
 925         return true;
 926 }
 927
 928 // FixedAllocator::VicinityFind -----------------------------------------------
 929
 930 Chunk *FixedAllocator::VicinityFind( void *p ) const
 931 {
 932         if ( chunks_.empty() ) return NULL;
 933         assert(deallocChunk_);
 934
 935         const std::size_t chunkLength = numBlocks_ * blockSize_;
 936         Chunk *lo = deallocChunk_;
 937         Chunk *hi = deallocChunk_ + 1;
 938         const Chunk *loBound = &chunks_.front();
 939         const Chunk *hiBound = &chunks_.back() + 1;
 940
 941         // Special case: deallocChunk_ is the last in the array
 942         if (hi == hiBound) hi = NULL;
 943
 944         for (;;)
 945         {
 946                 if (lo)
 947                 {
 948                         if ( lo->HasBlock( p, chunkLength ) ) return lo;
 949                         if ( lo == loBound )
 950                         {
 951                                 lo = NULL;
 952                                 if ( NULL == hi ) break;
 953                         }
 954                         else --lo;
 955                 }
 956
 957                 if (hi)
 958                 {
 959                         if ( hi->HasBlock( p, chunkLength ) ) return hi;
 960                         if ( ++hi == hiBound )
 961                         {
 962                                 hi = NULL;
 963                                 if ( NULL == lo ) break;
 964                         }
 965                 }
 966         }
 967
 968         return NULL;
 969 }
 970
 971 // FixedAllocator::DoDeallocate -----------------------------------------------
 972
 973 void FixedAllocator::DoDeallocate(void *p)
 974 {
 975         // Show that deallocChunk_ really owns the block at address p.
 976         assert( deallocChunk_->HasBlock( p, numBlocks_ * blockSize_ ) );
 977         // Either of the next two assertions may fail if somebody tries to
 978         // delete the same block twice.
 979         assert( emptyChunk_ != deallocChunk_ );
 980         assert( !deallocChunk_->HasAvailable( numBlocks_ ) );
 981         // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
 982         assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
 983
 984         // call into the chunk, will adjust the inner list but won't release memory
 985         deallocChunk_->Deallocate(p, blockSize_);
 986
 987         if ( deallocChunk_->HasAvailable( numBlocks_ ) )
 988         {
 989                 assert( emptyChunk_ != deallocChunk_ );
 990                 // deallocChunk_ is empty, but a Chunk is only released if there are 2
 991                 // empty chunks.  Since emptyChunk_ may only point to a previously
 992                 // cleared Chunk, if it points to something else besides deallocChunk_,
 993                 // then FixedAllocator currently has 2 empty Chunks.
 994                 if ( NULL != emptyChunk_ )
 995                 {
 996                         // If last Chunk is empty, just change what deallocChunk_
 997                         // points to, and release the last.  Otherwise, swap an empty
 998                         // Chunk with the last, and then release it.
 999                         Chunk *lastChunk = &chunks_.back();
1000                         if ( lastChunk == deallocChunk_ )
1001                                 deallocChunk_ = emptyChunk_;
1002                         else if ( lastChunk != emptyChunk_ )
1003                                 std::swap( *emptyChunk_, *lastChunk );
1004                         assert( lastChunk->HasAvailable( numBlocks_ ) );
1005                         lastChunk->Release();
1006                         chunks_.pop_back();
1007                         if ( ( allocChunk_ == lastChunk ) || allocChunk_->IsFilled() )
1008                                 allocChunk_ = deallocChunk_;
1009                 }
1010                 emptyChunk_ = deallocChunk_;
1011         }
1012
1013         // prove either emptyChunk_ points nowhere, or points to a truly empty Chunk.
1014         assert( ( NULL == emptyChunk_ ) || ( emptyChunk_->HasAvailable( numBlocks_ ) ) );
1015 }
1016
1017 // GetOffset ------------------------------------------------------------------
1018 /// @ingroup SmallObjectGroupInternal
1019 /// Calculates index into array where a FixedAllocator of numBytes is located.
1020 inline std::size_t GetOffset( std::size_t numBytes, std::size_t alignment )
1021 {
1022         const std::size_t alignExtra = alignment-1;
1023         return ( numBytes + alignExtra ) / alignment;
1024 }
1025
1026 // DefaultAllocator -----------------------------------------------------------
1027 /** @ingroup SmallObjectGroupInternal
1028  Calls the default allocator when SmallObjAllocator decides not to handle a
1029  request.  SmallObjAllocator calls this if the number of bytes is bigger than
1030  the size which can be handled by any FixedAllocator.
1031  @param numBytes number of bytes
1032  @param doThrow True if this function should throw an exception, or false if it
1033   should indicate failure by returning a NULL pointer.
1034 */
1035 void *DefaultAllocator( std::size_t numBytes, bool doThrow )
1036 {
1037 #ifdef USE_NEW_TO_ALLOCATE
1038         return doThrow ? ::operator new( numBytes ) :
1039                ::operator new( numBytes, std::nothrow_t() );
1040 #else
1041         void *p = ::std::malloc( numBytes );
1042         if ( doThrow && ( NULL == p ) )
1043                 throw std::bad_alloc();
1044         return p;
1045 #endif
1046 }
1047
1048 // DefaultDeallocator ---------------------------------------------------------
1049 /** @ingroup SmallObjectGroupInternal
1050  Calls default deallocator when SmallObjAllocator decides not to handle a
1051  request.  The default deallocator could be the global delete operator or the
1052  free function.  The free function is the preferred default deallocator since
1053  it matches malloc which is the preferred default allocator.  SmallObjAllocator
1054  will call this if an address was not found among any of its own blocks.
1055  */
1056 void DefaultDeallocator( void *p )
1057 {
1058 #ifdef USE_NEW_TO_ALLOCATE
1059         ::operator delete( p );
1060 #else
1061         ::std::free( p );
1062 #endif
1063 }
1064
1065 // SmallObjAllocator::SmallObjAllocator ---------------------------------------
1066
1067 SmallObjAllocator::SmallObjAllocator( std::size_t pageSize,
1068                                       std::size_t maxObjectSize, std::size_t objectAlignSize ) :
1069         pool_( NULL ),
1070         maxSmallObjectSize_( maxObjectSize ),
1071         objectAlignSize_( objectAlignSize )
1072 {
1073 #ifdef DO_EXTRA_LOKI_TESTS
1074         std::cout << "SmallObjAllocator " << this << std::endl;
1075 #endif
1076         assert( 0 != objectAlignSize );
1077         const std::size_t allocCount = GetOffset( maxObjectSize, objectAlignSize );
1078         pool_ = new FixedAllocator[ allocCount ];
1079         for ( std::size_t i = 0; i < allocCount; ++i )
1080                 pool_[ i ].Initialize( ( i+1 ) * objectAlignSize, pageSize );
1081 }
1082
1083 // SmallObjAllocator::~SmallObjAllocator --------------------------------------
1084
1085 SmallObjAllocator::~SmallObjAllocator( void )
1086 {
1087 #ifdef DO_EXTRA_LOKI_TESTS
1088         std::cout << "~SmallObjAllocator " << this << std::endl;
1089 #endif
1090         delete [] pool_;
1091 }
1092
1093 // SmallObjAllocator::TrimExcessMemory ----------------------------------------
1094
1095 bool SmallObjAllocator::TrimExcessMemory( void )
1096 {
1097         bool found = false;
1098         const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1099         std::size_t i = 0;
1100         for ( ; i < allocCount; ++i )
1101         {
1102                 if ( pool_[ i ].TrimEmptyChunk() )
1103                         found = true;
1104         }
1105         for ( i = 0; i < allocCount; ++i )
1106         {
1107                 if ( pool_[ i ].TrimChunkList() )
1108                         found = true;
1109         }
1110
1111         return found;
1112 }
1113
1114 // SmallObjAllocator::Allocate ------------------------------------------------
1115
1116 void *SmallObjAllocator::Allocate( std::size_t numBytes, bool doThrow )
1117 {
1118         if ( numBytes > GetMaxObjectSize() )
1119                 return DefaultAllocator( numBytes, doThrow );
1120
1121         assert( NULL != pool_ );
1122         if ( 0 == numBytes ) numBytes = 1;
1123         const std::size_t index = GetOffset( numBytes, GetAlignment() ) - 1;
1124         const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1125         (void) allocCount;
1126         assert( index < allocCount );
1127
1128         FixedAllocator &allocator = pool_[ index ];
1129         assert( allocator.BlockSize() >= numBytes );
1130         assert( allocator.BlockSize() < numBytes + GetAlignment() );
1131         void *place = allocator.Allocate();
1132
1133         if ( ( NULL == place ) && TrimExcessMemory() )
1134                 place = allocator.Allocate();
1135
1136         if ( ( NULL == place ) && doThrow )
1137         {
1138 #ifdef _MSC_VER
1139                 throw std::bad_alloc( "could not allocate small object" );
1140 #else
1141                 // GCC did not like a literal string passed to std::bad_alloc.
1142                 // so just throw the default-constructed exception.
1143                 throw std::bad_alloc();
1144 #endif
1145         }
1146         return place;
1147 }
1148
1149 // SmallObjAllocator::Deallocate ----------------------------------------------
1150
1151 void SmallObjAllocator::Deallocate( void *p, std::size_t numBytes )
1152 {
1153         if ( NULL == p ) return;
1154         if ( numBytes > GetMaxObjectSize() )
1155         {
1156                 DefaultDeallocator( p );
1157                 return;
1158         }
1159         assert( NULL != pool_ );
1160         if ( 0 == numBytes ) numBytes = 1;
1161         const std::size_t index = GetOffset( numBytes, GetAlignment() ) - 1;
1162         const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1163         (void) allocCount;
1164         assert( index < allocCount );
1165         FixedAllocator &allocator = pool_[ index ];
1166         assert( allocator.BlockSize() >= numBytes );
1167         assert( allocator.BlockSize() < numBytes + GetAlignment() );
1168         const bool found = allocator.Deallocate( p, NULL );
1169         (void) found;
1170         assert( found );
1171 }
1172
1173 // SmallObjAllocator::Deallocate ----------------------------------------------
1174
1175 void SmallObjAllocator::Deallocate( void *p )
1176 {
1177         if ( NULL == p ) return;
1178         assert( NULL != pool_ );
1179         FixedAllocator *pAllocator = NULL;
1180         const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1181         Chunk *chunk = NULL;
1182
1183         for ( std::size_t ii = 0; ii < allocCount; ++ii )
1184         {
1185                 chunk = pool_[ ii ].HasBlock( p );
1186                 if ( NULL != chunk )
1187                 {
1188                         pAllocator = &pool_[ ii ];
1189                         break;
1190                 }
1191         }
1192         if ( NULL == pAllocator )
1193         {
1194                 DefaultDeallocator( p );
1195                 return;
1196         }
1197
1198         assert( NULL != chunk );
1199         const bool found = pAllocator->Deallocate( p, chunk );
1200         (void) found;
1201         assert( found );
1202 }
1203
1204 // SmallObjAllocator::IsCorrupt -----------------------------------------------
1205
1206 bool SmallObjAllocator::IsCorrupt( void ) const
1207 {
1208         if ( NULL == pool_ )
1209         {
1210                 assert( false );
1211                 return true;
1212         }
1213         if ( 0 == GetAlignment() )
1214         {
1215                 assert( false );
1216                 return true;
1217         }
1218         if ( 0 == GetMaxObjectSize() )
1219         {
1220                 assert( false );
1221                 return true;
1222         }
1223         const std::size_t allocCount = GetOffset( GetMaxObjectSize(), GetAlignment() );
1224         for ( std::size_t ii = 0; ii < allocCount; ++ii )
1225         {
1226                 if ( pool_[ ii ].IsCorrupt() )
1227                         return true;
1228         }
1229         return false;
1230 }
1231
1232 } // end namespace Loki
1233