home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / Heap.h < prev    next >
C/C++ Source or Header  |  2005-11-14  |  35KB  |  1,163 lines

  1.  
  2. #ifndef __HEAP_H__
  3. #define __HEAP_H__
  4.  
  5. /*
  6. ===============================================================================
  7.  
  8.     Memory Management
  9.  
  10.     This is a replacement for the compiler heap code (i.e. "C" malloc() and
  11.     free() calls). On average 2.5-3.0 times faster than MSVC malloc()/free().
  12.     Worst case performance is 1.65 times faster and best case > 70 times.
  13.  
  14. ===============================================================================
  15. */
  16.  
  17. // RAVEN BEGIN
  18. // jsinger: attempt to eliminate cross-DLL allocation issues
  19. #ifdef RV_UNIFIED_ALLOCATOR
  20. class Memory
  21. {
  22. public:
  23.     static void *Allocate(size_t size)
  24.     {
  25.         if(mAllocator)
  26.         {
  27.             return mAllocator(size);
  28.         }
  29.         else
  30.         {
  31. #ifndef _LOAD_DLL
  32.             // allocations from the exe are safe no matter what, but allocations from a DLL through
  33.             // this path will be unsafe, so we warn about them.  Adding a breakpoint here will allow
  34.             // allow locating of the specific offending allocation
  35.             Error("Unprotected allocations are not allowed.  Make sure you've initialized Memory before allocating dynamic memory");
  36. #endif
  37.             return malloc(size);
  38.         }
  39.     }
  40.  
  41.     static void Free(void *ptr)
  42.     {
  43.         if(mDeallocator)
  44.         {
  45.             mDeallocator(ptr);
  46.         }
  47.         else
  48.         {
  49. #ifndef _LOAD_DLL
  50.             // allocations from the exe are safe no matter what, but allocations from a DLL through
  51.             // this path will be unsafe, so we warn about them.  Adding a breakpoint here will allow
  52.             // allow locating of the specific offending allocation
  53.             Error("Unprotected allocations are not allowed.  Make sure you've initialized Memory before allocating dynamic memory");
  54. #endif
  55.             return free(ptr);
  56.         }
  57.     }
  58.  
  59.     static size_t MSize(void *ptr)
  60.     {
  61.         if(mMSize)
  62.         {
  63.             return mMSize(ptr);
  64.         }
  65.         else
  66.         {
  67. #ifndef _LOAD_DLL
  68.             // allocations from the exe are safe no matter what, but allocations from a DLL through
  69.             // this path will be unsafe, so we warn about them.  Adding a breakpoint here will allow
  70.             // allow locating of the specific offending allocation
  71.             Error("Unprotected allocations are not allowed.  Make sure you've initialized Memory before allocating dynamic memory");
  72. #endif
  73.             return _msize(ptr);
  74.         }
  75.     }
  76.  
  77.     static void InitAllocator(void *(*allocator)(size_t size), void (*deallocator)(void *), size_t (*msize)(void *ptr))
  78.     {
  79.         // check for errors prior to initialization
  80.         if(!sOK)
  81.         {
  82.             Error("Unprotected allocation in DLL detected prior to initialization of memory system");
  83.         }
  84.  
  85.         mAllocator = allocator;
  86.         mDeallocator = deallocator;
  87.         mMSize = msize;
  88.     }
  89.  
  90.     static void DeinitAllocator()
  91.     {
  92.         mAllocator = NULL;
  93.         mDeallocator = NULL;
  94.         mMSize = NULL;
  95.     }
  96.  
  97.     static void Error(const char *errStr);
  98.  
  99. private:
  100.     static void *(*mAllocator)(size_t size);
  101.     static void (*mDeallocator)(void *ptr);
  102.     static size_t (*mMSize)(void *ptr);
  103.     static bool sOK;
  104. };
  105. #endif
  106. // RAVEN END
  107.  
  108. typedef struct {
  109.     int        num;
  110.     int        minSize;
  111.     int        maxSize;
  112.     int        totalSize;
  113. } memoryStats_t;
  114.  
  115. // RAVEN BEGIN
  116. // amccarthy:  tags for memory allocation tracking.  When updating this list please update the
  117. // list of discriptions in Heap.cpp as well.
  118. typedef enum {
  119.     MA_NONE = 0,    
  120.     
  121.     MA_OPNEW,
  122.     MA_DEFAULT,
  123.     MA_LEXER,
  124.     MA_PARSER,
  125.     MA_AAS,
  126.     MA_CLASS,
  127.     MA_SCRIPT,
  128.     MA_CM,
  129.     MA_CVAR,
  130.     MA_DECL,
  131.     MA_FILESYS,
  132.     MA_IMAGES,
  133.     MA_MATERIAL,
  134.     MA_MODEL,
  135.     MA_FONT,
  136.     MA_RENDER,
  137.     MA_VERTEX,
  138.     MA_SOUND,
  139.     MA_WINDOW,
  140.     MA_EVENT,
  141.     MA_MATH,
  142.     MA_ANIM,
  143.     MA_DYNAMICBLOCK,
  144.     MA_STRING,
  145.     MA_GUI,
  146.     MA_EFFECT,
  147.     MA_ENTITY,
  148.     MA_PHYSICS,
  149.     MA_AI,
  150.     MA_NETWORK,
  151.  
  152.     MA_DO_NOT_USE,        // neither of the two remaining enumerated values should be used (no use of MA_DO_NOT_USE prevents the second dword in a memory block from getting the value 0xFFFFFFFF)
  153.     MA_MAX                // <- this enumerated value is a count and cannot exceed 32 (5 bits are used to encode tag within memory block with rvHeap.cpp)
  154. } Mem_Alloc_Types_t;
  155.  
  156. #if defined(_DEBUG) || defined(_RV_MEM_SYS_SUPPORT)
  157. const char *GetMemAllocStats(int tag, int &num, int &size, int &peak);
  158. #endif
  159. // RAVEN END
  160.  
  161. void        Mem_Init( void );
  162. void        Mem_Shutdown( void );
  163. void        Mem_EnableLeakTest( const char *name );
  164. void        Mem_ClearFrameStats( void );
  165. void        Mem_GetFrameStats( memoryStats_t &allocs, memoryStats_t &frees );
  166. void        Mem_GetStats( memoryStats_t &stats );
  167. void        Mem_Dump_f( const class idCmdArgs &args );
  168. void        Mem_DumpCompressed_f( const class idCmdArgs &args );
  169. void        Mem_AllocDefragBlock( void );
  170.  
  171. // RAVEN BEGIN
  172. // amccarthy command for printing tagged mem_alloc info
  173. void        Mem_ShowMemAlloc_f( const idCmdArgs &args );
  174.  
  175. // jnewquist: Add Mem_Size to query memory allocation size
  176. int            Mem_Size( void *ptr );
  177.  
  178. // jnewquist: memory tag stack for new/delete
  179. #if (defined(_DEBUG) || defined(_RV_MEM_SYS_SUPPORT)) && !defined(ENABLE_INTEL_SMP)
  180. class MemScopedTag {
  181.     byte mTag;
  182.     MemScopedTag *mPrev;
  183.     static MemScopedTag *mTop;
  184. public:
  185.     MemScopedTag( byte tag ) {
  186.         mTag = tag;
  187.         mPrev = mTop;
  188.         mTop = this;
  189.     }
  190.     ~MemScopedTag() {
  191.         assert( mTop != NULL );
  192.         mTop = mTop->mPrev;
  193.     }
  194.     void SetTag( byte tag ) {
  195.         mTag = tag;
  196.     }
  197.     static byte GetTopTag( void ) {
  198.         if ( mTop ) {
  199.             return mTop->mTag;
  200.         } else {
  201.             return MA_OPNEW;
  202.         }
  203.     }
  204. };
  205. #define MemScopedTag_GetTopTag() MemScopedTag::GetTopTag()
  206. #define MEM_SCOPED_TAG(var, tag) MemScopedTag var(tag)
  207. #define MEM_SCOPED_TAG_SET(var, tag) var.SetTag(tag)
  208. #else
  209. #define MemScopedTag_GetTopTag() MA_OPNEW
  210. #define MEM_SCOPED_TAG(var, tag)
  211. #define MEM_SCOPED_TAG_SET(var, tag)
  212. #endif
  213.  
  214. // RAVEN END
  215.  
  216. #ifndef ID_DEBUG_MEMORY
  217.  
  218. // RAVEN BEGIN
  219. // amccarthy: added tags from memory allocation tracking.
  220. void *        Mem_Alloc( const int size, byte tag = MA_DEFAULT );
  221. void *        Mem_ClearedAlloc( const int size, byte tag = MA_DEFAULT );
  222. void        Mem_Free( void *ptr );
  223. char *        Mem_CopyString( const char *in );
  224. void *        Mem_Alloc16( const int size, byte tag=MA_DEFAULT );
  225. void        Mem_Free16( void *ptr );
  226.  
  227. // jscott: standardised stack allocation
  228. inline void *Mem_StackAlloc( const int size ) { return( _alloca( size ) ); }
  229.  
  230. // RAVEN BEGIN
  231. // dluetscher: moved the inline new/delete operators to sys_local.cpp and Game_local.cpp so that
  232. //               Tools.dll will link.
  233. #if defined(_XBOX) || defined(ID_REDIRECT_NEWDELETE) || defined(_RV_MEM_SYS_SUPPORT)
  234.  
  235. void *operator new( size_t s );
  236. void operator delete( void *p );
  237. void *operator new[]( size_t s );
  238. void operator delete[]( void *p );
  239. // RAVEN END
  240.  
  241. #endif
  242. // RAVEN END
  243.  
  244. #else /* ID_DEBUG_MEMORY */
  245.  
  246. // RAVEN BEGIN
  247. // amccarthy: added tags from memory allocation tracking.
  248. void *        Mem_Alloc( const int size, const char *fileName, const int lineNumber, byte tag = MA_DEFAULT );
  249. void *        Mem_ClearedAlloc( const int size, const char *fileName, const int lineNumber, byte tag = MA_DEFAULT );
  250. void        Mem_Free( void *ptr, const char *fileName, const int lineNumber );
  251. char *        Mem_CopyString( const char *in, const char *fileName, const int lineNumber );
  252. void *        Mem_Alloc16( const int size, const char *fileName, const int lineNumber, byte tag = MA_DEFAULT);
  253. void        Mem_Free16( void *ptr, const char *fileName, const int lineNumber );
  254.  
  255.  
  256. // jscott: standardised stack allocation
  257. inline void *Mem_StackAlloc( const int size ) { return( _alloca( size ) ); }
  258.  
  259. // RAVEN BEGIN
  260. // dluetscher: moved the inline new/delete operators to sys_local.cpp and Game_local.cpp so that
  261. //               the Tools.dll will link.
  262. #if defined(_XBOX) || defined(ID_REDIRECT_NEWDELETE) || defined(_RV_MEM_SYS_SUPPORT)
  263.  
  264. void *operator new( size_t s, int t1, int t2, char *fileName, int lineNumber );
  265. void operator delete( void *p, int t1, int t2, char *fileName, int lineNumber );
  266. void *operator new[]( size_t s, int t1, int t2, char *fileName, int lineNumber );
  267. void operator delete[]( void *p, int t1, int t2, char *fileName, int lineNumber );
  268.  
  269. void *operator new( size_t s );
  270. void operator delete( void *p );
  271. void *operator new[]( size_t s );
  272. void operator delete[]( void *p );
  273. // RAVEN END
  274.  
  275. #define ID_DEBUG_NEW                        new( 0, 0, __FILE__, __LINE__ )
  276. #undef new
  277. #define new                                    ID_DEBUG_NEW
  278.  
  279. #endif
  280.  
  281. #define        Mem_Alloc( size, tag )                Mem_Alloc( size, __FILE__, __LINE__ )
  282. #define        Mem_ClearedAlloc( size, tag )        Mem_ClearedAlloc( size, __FILE__, __LINE__ )
  283. #define        Mem_Free( ptr )                    Mem_Free( ptr, __FILE__, __LINE__ )
  284. #define        Mem_CopyString( s )                Mem_CopyString( s, __FILE__, __LINE__ )
  285. #define        Mem_Alloc16( size, tag )                Mem_Alloc16( size, __FILE__, __LINE__ )
  286. #define        Mem_Free16( ptr )                Mem_Free16( ptr, __FILE__, __LINE__ )
  287. // RAVEN END
  288. #endif /* ID_DEBUG_MEMORY */
  289.  
  290.  
  291. /*
  292. ===============================================================================
  293.  
  294.     Block based allocator for fixed size objects.
  295.  
  296.     All objects of the 'type' are properly constructed.
  297.     However, the constructor is not called for re-used objects.
  298.  
  299. ===============================================================================
  300. */
  301.  
  302. // RAVEN BEGIN
  303. // jnewquist: Mark memory tags for idBlockAlloc
  304. template<class type, int blockSize, byte memoryTag>
  305. class idBlockAlloc {
  306. public:
  307.                             idBlockAlloc( void );
  308.                             ~idBlockAlloc( void );
  309.  
  310.     void                    Shutdown( void );
  311.  
  312.     type *                    Alloc( void );
  313.     void                    Free( type *element );
  314.  
  315.     int                        GetTotalCount( void ) const { return total; }
  316.     int                        GetAllocCount( void ) const { return active; }
  317.     int                        GetFreeCount( void ) const { return total - active; }
  318.  
  319. // RAVEN BEGIN
  320. // jscott: get the amount of memory used
  321.     size_t                    Allocated( void ) const { return( total * sizeof( type ) ); }
  322. // RAVEN END
  323.  
  324. private:
  325.     typedef struct element_s {
  326.         struct element_s *    next;
  327.         type                t;
  328.     } element_t;
  329.     typedef struct block_s {
  330.         element_t            elements[blockSize];
  331.         struct block_s *    next;
  332.     } block_t;
  333.  
  334.     block_t *                blocks;
  335.     element_t *                free;
  336.     int                        total;
  337.     int                        active;
  338. };
  339.  
  340. template<class type, int blockSize, byte memoryTag>
  341. idBlockAlloc<type,blockSize,memoryTag>::idBlockAlloc( void ) {
  342.     blocks = NULL;
  343.     free = NULL;
  344.     total = active = 0;
  345. }
  346.  
  347. template<class type, int blockSize, byte memoryTag>
  348. idBlockAlloc<type,blockSize,memoryTag>::~idBlockAlloc( void ) {
  349.     Shutdown();
  350. }
  351.  
  352. template<class type, int blockSize, byte memoryTag>
  353. type *idBlockAlloc<type,blockSize,memoryTag>::Alloc( void ) {
  354.     if ( !free ) {
  355.         MEM_SCOPED_TAG(tag, memoryTag);
  356.         block_t *block = new block_t;
  357.         block->next = blocks;
  358.         blocks = block;
  359.         for ( int i = 0; i < blockSize; i++ ) {
  360.             block->elements[i].next = free;
  361.             free = &block->elements[i];
  362.         }
  363.         total += blockSize;
  364.     }
  365.     active++;
  366.     element_t *element = free;
  367.     free = free->next;
  368.     element->next = NULL;
  369.     return &element->t;
  370. }
  371.  
  372. template<class type, int blockSize, byte memoryTag>
  373. void idBlockAlloc<type,blockSize,memoryTag>::Free( type *t ) {
  374.     element_t *element = (element_t *)( ( (unsigned char *) t ) - ( (int) &((element_t *)0)->t ) );
  375.     element->next = free;
  376.     free = element;
  377.     active--;
  378. }
  379.  
  380. template<class type, int blockSize, byte memoryTag>
  381. void idBlockAlloc<type,blockSize,memoryTag>::Shutdown( void ) {
  382.     while( blocks ) {
  383.         block_t *block = blocks;
  384.         blocks = blocks->next;
  385.         delete block;
  386.     }
  387.     blocks = NULL;
  388.     free = NULL;
  389.     total = active = 0;
  390. }
  391. // RAVEN END
  392.  
  393. /*
  394. ==============================================================================
  395.  
  396.     Dynamic allocator, simple wrapper for normal allocations which can
  397.     be interchanged with idDynamicBlockAlloc.
  398.  
  399.     No constructor is called for the 'type'.
  400.     Allocated blocks are always 16 byte aligned.
  401.  
  402. ==============================================================================
  403. */
  404.  
  405. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  406. class idDynamicAlloc {
  407. public:
  408.                                     idDynamicAlloc( void );
  409.                                     ~idDynamicAlloc( void );
  410.  
  411.     void                            Init( void );
  412.     void                            Shutdown( void );
  413.     void                            SetFixedBlocks( int numBlocks ) {}
  414.     void                            SetLockMemory( bool lock ) {}
  415.     void                            FreeEmptyBaseBlocks( void ) {}
  416.  
  417.     type *                            Alloc( const int num );
  418.     type *                            Resize( type *ptr, const int num );
  419.     void                            Free( type *ptr );
  420.     const char *                    CheckMemory( const type *ptr ) const;
  421.  
  422.     int                                GetNumBaseBlocks( void ) const { return 0; }
  423.     int                                GetBaseBlockMemory( void ) const { return 0; }
  424.     int                                GetNumUsedBlocks( void ) const { return numUsedBlocks; }
  425.     int                                GetUsedBlockMemory( void ) const { return usedBlockMemory; }
  426.     int                                GetNumFreeBlocks( void ) const { return 0; }
  427.     int                                GetFreeBlockMemory( void ) const { return 0; }
  428.     int                                GetNumEmptyBaseBlocks( void ) const { return 0; }
  429.  
  430. private:
  431.     int                                numUsedBlocks;            // number of used blocks
  432.     int                                usedBlockMemory;        // total memory in used blocks
  433.  
  434.     int                                numAllocs;
  435.     int                                numResizes;
  436.     int                                numFrees;
  437.  
  438.     void                            Clear( void );
  439. };
  440.  
  441. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  442. idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::idDynamicAlloc( void ) {
  443.     Clear();
  444. }
  445.  
  446. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  447. idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::~idDynamicAlloc( void ) {
  448.     Shutdown();
  449. }
  450.  
  451. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  452. void idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Init( void ) {
  453. }
  454.  
  455. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  456. void idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Shutdown( void ) {
  457.     Clear();
  458. }
  459.  
  460. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  461. type *idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Alloc( const int num ) {
  462.     numAllocs++;
  463.     if ( num <= 0 ) {
  464.         return NULL;
  465.     }
  466.     numUsedBlocks++;
  467.     usedBlockMemory += num * sizeof( type );
  468. // RAVEN BEGIN
  469. // jscott: to make it build
  470. // mwhitlock: to make it build on Xenon
  471.     return (type *) ( (byte *) Mem_Alloc16( num * sizeof( type ), memoryTag ) );
  472. // RAVEN BEGIN
  473. }
  474.  
  475. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  476. type *idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Resize( type *ptr, const int num ) {
  477.  
  478.     numResizes++;
  479.  
  480. // RAVEN BEGIN
  481. // jnewquist: provide a real implementation of resize
  482.     if ( num <= 0 ) {
  483.         Free( ptr );
  484.         return NULL;
  485.     }
  486.  
  487.     type *newptr = Alloc( num );
  488.  
  489.     if ( ptr != NULL ) {
  490.         const int oldSize = Mem_Size(ptr);
  491.         const int newSize = num*sizeof(type);
  492.         SIMDProcessor->Memcpy( newptr, ptr, (newSize<oldSize)?newSize:oldSize );
  493.         Free(ptr);
  494.     }
  495.  
  496.     return newptr;
  497. // RAVEN END
  498. }
  499.  
  500. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  501. void idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Free( type *ptr ) {
  502.     numFrees++;
  503.     if ( ptr == NULL ) {
  504.         return;
  505.     }
  506.     Mem_Free16( ptr );
  507. }
  508.  
  509. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  510. const char *idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::CheckMemory( const type *ptr ) const {
  511.     return NULL;
  512. }
  513.  
  514. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  515. void idDynamicAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Clear( void ) {
  516.     numUsedBlocks = 0;
  517.     usedBlockMemory = 0;
  518.     numAllocs = 0;
  519.     numResizes = 0;
  520.     numFrees = 0;
  521. }
  522.  
  523.  
  524. /*
  525. ==============================================================================
  526.  
  527.     Fast dynamic block allocator.
  528.  
  529.     No constructor is called for the 'type'.
  530.     Allocated blocks are always 16 byte aligned.
  531.  
  532. ==============================================================================
  533. */
  534.  
  535. #include "containers/BTree.h"
  536.  
  537. // RAVEN BEGIN
  538. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  539. //#ifdef _DEBUG
  540. //#define DYNAMIC_BLOCK_ALLOC_CHECK
  541. // FIXME: doesn't compile right on OSX when enabled. investigate
  542. #ifndef MACOS_X
  543. #define DYNAMIC_BLOCK_ALLOC_FASTCHECK
  544. #endif
  545. #define DYNAMIC_BLOCK_ALLOC_CHECK_IS_FATAL
  546. //#endif
  547. // RAVEN END
  548.  
  549. template<class type>
  550. class idDynamicBlock {
  551. public:
  552.     type *                            GetMemory( void ) const { return (type *)( ( (byte *) this ) + sizeof( idDynamicBlock<type> ) ); }
  553.     int                                GetSize( void ) const { return abs( size ); }
  554.     void                            SetSize( int s, bool isBaseBlock ) { size = isBaseBlock ? -s : s; }
  555.     bool                            IsBaseBlock( void ) const { return ( size < 0 ); }
  556.  
  557. // RAVEN BEGIN
  558. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  559. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  560. // RAVEN END
  561.     int                                id[3];
  562.     void *                            allocator;
  563. #endif
  564.  
  565.     int                                size;                    // size in bytes of the block
  566.     idDynamicBlock<type> *            prev;                    // previous memory block
  567.     idDynamicBlock<type> *            next;                    // next memory block
  568.     idBTreeNode<idDynamicBlock<type>,int> *node;            // node in the B-Tree with free blocks
  569. };
  570.  
  571. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  572. class idDynamicBlockAlloc {
  573. public:
  574.                                     idDynamicBlockAlloc( void );
  575.                                     ~idDynamicBlockAlloc( void );
  576.  
  577.     void                            Init( void );
  578.     void                            Shutdown( void );
  579.     void                            SetFixedBlocks( int numBlocks );
  580.     void                            SetLockMemory( bool lock );
  581.     void                            FreeEmptyBaseBlocks( void );
  582.  
  583.     type *                            Alloc( const int num );
  584.     type *                            Resize( type *ptr, const int num );
  585.     void                            Free( type *ptr );
  586.     const char *                    CheckMemory( const type *ptr ) const;
  587.  
  588.     int                                GetNumBaseBlocks( void ) const { return numBaseBlocks; }
  589.     int                                GetBaseBlockMemory( void ) const { return baseBlockMemory; }
  590.     int                                GetNumUsedBlocks( void ) const { return numUsedBlocks; }
  591.     int                                GetUsedBlockMemory( void ) const { return usedBlockMemory; }
  592.     int                                GetNumFreeBlocks( void ) const { return numFreeBlocks; }
  593.     int                                GetFreeBlockMemory( void ) const { return freeBlockMemory; }
  594.     int                                GetNumEmptyBaseBlocks( void ) const;
  595.  
  596. private:
  597.     idDynamicBlock<type> *            firstBlock;                // first block in list in order of increasing address
  598.     idDynamicBlock<type> *            lastBlock;                // last block in list in order of increasing address
  599.     idBTree<idDynamicBlock<type>,int,4>freeTree;            // B-Tree with free memory blocks
  600.     bool                            allowAllocs;            // allow base block allocations
  601.     bool                            lockMemory;                // lock memory so it cannot get swapped out
  602.  
  603. // RAVEN BEGIN
  604. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  605. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  606. // RAVEN END
  607.     int                                blockId[3];
  608. #endif
  609.  
  610.     int                                numBaseBlocks;            // number of base blocks
  611.     int                                baseBlockMemory;        // total memory in base blocks
  612.     int                                numUsedBlocks;            // number of used blocks
  613.     int                                usedBlockMemory;        // total memory in used blocks
  614.     int                                numFreeBlocks;            // number of free blocks
  615.     int                                freeBlockMemory;        // total memory in free blocks
  616.  
  617.     int                                numAllocs;
  618.     int                                numResizes;
  619.     int                                numFrees;
  620.  
  621.     void                            Clear( void );
  622.     idDynamicBlock<type> *            AllocInternal( const int num );
  623.     idDynamicBlock<type> *            ResizeInternal( idDynamicBlock<type> *block, const int num );
  624.     void                            FreeInternal( idDynamicBlock<type> *block );
  625.     void                            LinkFreeInternal( idDynamicBlock<type> *block );
  626.     void                            UnlinkFreeInternal( idDynamicBlock<type> *block );
  627.     void                            CheckMemory( void ) const;
  628. // RAVEN BEGIN
  629. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  630.     const char *                    CheckMemory( const idDynamicBlock<type> *block ) const;
  631. // RAVEN END
  632. };
  633.  
  634. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  635. idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::idDynamicBlockAlloc( void ) {
  636.     Clear();
  637. }
  638.  
  639. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  640. idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::~idDynamicBlockAlloc( void ) {
  641.     Shutdown();
  642. }
  643.  
  644. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  645. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Init( void ) {
  646. // RAVEN BEGIN
  647. // jnewquist: Tag scope and callees to track allocations using "new".
  648.     MEM_SCOPED_TAG(tag,memoryTag);
  649. // RAVEN END
  650.     freeTree.Init();
  651. }
  652.  
  653. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  654. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Shutdown( void ) {
  655.     idDynamicBlock<type> *block;
  656.  
  657.     for ( block = firstBlock; block != NULL; block = block->next ) {
  658.         if ( block->node == NULL ) {
  659.             FreeInternal( block );
  660.         }
  661.     }
  662.  
  663.     for ( block = firstBlock; block != NULL; block = firstBlock ) {
  664.         firstBlock = block->next;
  665.         assert( block->IsBaseBlock() );
  666.         if ( lockMemory ) {
  667.             idLib::sys->UnlockMemory( block, block->GetSize() + (int)sizeof( idDynamicBlock<type> ) );
  668.         }
  669.         Mem_Free16( block );
  670.     }
  671.  
  672.     freeTree.Shutdown();
  673.  
  674.     Clear();
  675. }
  676.  
  677. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  678. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::SetFixedBlocks( int numBlocks ) {
  679.     int i;
  680.     idDynamicBlock<type> *block;
  681.  
  682.     for ( i = numBaseBlocks; i < numBlocks; i++ ) {
  683. //RAVEN BEGIN
  684. //amccarthy: Added allocation tag
  685.         block = ( idDynamicBlock<type> * ) Mem_Alloc16( baseBlockSize, memoryTag );
  686. //RAVEN END
  687.         if ( lockMemory ) {
  688.             idLib::sys->LockMemory( block, baseBlockSize );
  689.         }
  690. // RAVEN BEGIN
  691. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  692. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  693. // RAVEN END
  694.         memcpy( block->id, blockId, sizeof( block->id ) );
  695.         block->allocator = (void*)this;
  696. #endif
  697.         block->SetSize( baseBlockSize - (int)sizeof( idDynamicBlock<type> ), true );
  698.         block->next = NULL;
  699.         block->prev = lastBlock;
  700.         if ( lastBlock ) {
  701.             lastBlock->next = block;
  702.         } else {
  703.             firstBlock = block;
  704.         }
  705.         lastBlock = block;
  706.         block->node = NULL;
  707.  
  708.         FreeInternal( block );
  709.  
  710.         numBaseBlocks++;
  711.         baseBlockMemory += baseBlockSize;
  712.     }
  713.  
  714.     allowAllocs = false;
  715. }
  716.  
  717. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  718. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::SetLockMemory( bool lock ) {
  719.     lockMemory = lock;
  720. }
  721.  
  722. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  723. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::FreeEmptyBaseBlocks( void ) {
  724.     idDynamicBlock<type> *block, *next;
  725.  
  726.     for ( block = firstBlock; block != NULL; block = next ) {
  727.         next = block->next;
  728.  
  729.         if ( block->IsBaseBlock() && block->node != NULL && ( next == NULL || next->IsBaseBlock() ) ) {
  730.             UnlinkFreeInternal( block );
  731.             if ( block->prev ) {
  732.                 block->prev->next = block->next;
  733.             } else {
  734.                 firstBlock = block->next;
  735.             }
  736.             if ( block->next ) {
  737.                 block->next->prev = block->prev;
  738.             } else {
  739.                 lastBlock = block->prev;
  740.             }
  741.             if ( lockMemory ) {
  742.                 idLib::sys->UnlockMemory( block, block->GetSize() + (int)sizeof( idDynamicBlock<type> ) );
  743.             }
  744.             numBaseBlocks--;
  745.             baseBlockMemory -= block->GetSize() + (int)sizeof( idDynamicBlock<type> );
  746.             Mem_Free16( block );
  747.         }
  748.     }
  749.  
  750. #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
  751.     CheckMemory();
  752. #endif
  753. }
  754.  
  755. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  756. int idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::GetNumEmptyBaseBlocks( void ) const {
  757.     int numEmptyBaseBlocks;
  758.     idDynamicBlock<type> *block;
  759.  
  760.     numEmptyBaseBlocks = 0;
  761.     for ( block = firstBlock; block != NULL; block = block->next ) {
  762.         if ( block->IsBaseBlock() && block->node != NULL && ( block->next == NULL || block->next->IsBaseBlock() ) ) {
  763.             numEmptyBaseBlocks++;
  764.         }
  765.     }
  766.     return numEmptyBaseBlocks;
  767. }
  768.  
  769. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  770. type *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Alloc( const int num ) {
  771.     idDynamicBlock<type> *block;
  772.  
  773.     numAllocs++;
  774.  
  775.     if ( num <= 0 ) {
  776.         return NULL;
  777.     }
  778.  
  779.     block = AllocInternal( num );
  780.     if ( block == NULL ) {
  781.         return NULL;
  782.     }
  783.     block = ResizeInternal( block, num );
  784.     if ( block == NULL ) {
  785.         return NULL;
  786.     }
  787.  
  788. #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
  789.     CheckMemory();
  790. #endif
  791.  
  792.     numUsedBlocks++;
  793.     usedBlockMemory += block->GetSize();
  794.  
  795.     return block->GetMemory();
  796. }
  797.  
  798. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  799. type *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Resize( type *ptr, const int num ) {
  800.  
  801.     numResizes++;
  802.  
  803.     if ( ptr == NULL ) {
  804.         return Alloc( num );
  805.     }
  806.  
  807.     if ( num <= 0 ) {
  808.         Free( ptr );
  809.         return NULL;
  810.     }
  811.  
  812.     idDynamicBlock<type> *block = ( idDynamicBlock<type> * ) ( ( (byte *) ptr ) - (int)sizeof( idDynamicBlock<type> ) );
  813.  
  814.     usedBlockMemory -= block->GetSize();
  815.  
  816.     block = ResizeInternal( block, num );
  817.     if ( block == NULL ) {
  818.         return NULL;
  819.     }
  820.  
  821. #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
  822.     CheckMemory();
  823. #endif
  824.  
  825.     usedBlockMemory += block->GetSize();
  826.  
  827.     return block->GetMemory();
  828. }
  829.  
  830. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  831. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Free( type *ptr ) {
  832.  
  833.     numFrees++;
  834.  
  835.     if ( ptr == NULL ) {
  836.         return;
  837.     }
  838.  
  839.     idDynamicBlock<type> *block = ( idDynamicBlock<type> * ) ( ( (byte *) ptr ) - (int)sizeof( idDynamicBlock<type> ) );
  840.  
  841.     numUsedBlocks--;
  842.     usedBlockMemory -= block->GetSize();
  843.  
  844.     FreeInternal( block );
  845.  
  846. #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
  847.     CheckMemory();
  848. #endif
  849. }
  850.  
  851. // RAVEN BEGIN
  852. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  853. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  854. const char *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::CheckMemory( const idDynamicBlock<type> *block ) const {
  855.     if ( block->node != NULL ) {
  856.         return "memory has been freed";
  857.     }
  858.  
  859. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  860. // RAVEN END
  861.     if ( block->id[0] != 0x11111111 || block->id[1] != 0x22222222 || block->id[2] != 0x33333333 ) {
  862.         return "memory has invalid id";
  863.     }
  864. // RAVEN BEGIN
  865. // jsinger: attempt to eliminate cross-DLL allocation issues
  866. #ifndef RV_UNIFIED_ALLOCATOR
  867.     if ( block->allocator != (void*)this ) {
  868.         return "memory was allocated with different allocator";
  869.     }
  870. #endif // RV_UNIFIED_ALLOCATOR
  871. // RAVEN END
  872. #endif
  873.  
  874.     /* base blocks can be larger than baseBlockSize which can cause this code to fail
  875.     idDynamicBlock<type> *base;
  876.     for ( base = firstBlock; base != NULL; base = base->next ) {
  877.         if ( base->IsBaseBlock() ) {
  878.             if ( ((int)block) >= ((int)base) && ((int)block) < ((int)base) + baseBlockSize ) {
  879.                 break;
  880.             }
  881.         }
  882.     }
  883.     if ( base == NULL ) {
  884.         return "no base block found for memory";
  885.     }
  886.     */
  887.  
  888.     return NULL;
  889. }
  890.  
  891. // RAVEN BEGIN
  892. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  893. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  894. const char *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::CheckMemory( const type *ptr ) const {
  895.     idDynamicBlock<type> *block;
  896.  
  897.     if ( ptr == NULL ) {
  898.         return NULL;
  899.     }
  900.  
  901.     block = ( idDynamicBlock<type> * ) ( ( (byte *) ptr ) - (int)sizeof( idDynamicBlock<type> ) );
  902.     return CheckMemory( block );
  903. }
  904. // RAVEN END
  905.  
  906. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  907. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::Clear( void ) {
  908.     firstBlock = lastBlock = NULL;
  909.     allowAllocs = true;
  910.     lockMemory = false;
  911.     numBaseBlocks = 0;
  912.     baseBlockMemory = 0;
  913.     numUsedBlocks = 0;
  914.     usedBlockMemory = 0;
  915.     numFreeBlocks = 0;
  916.     freeBlockMemory = 0;
  917.     numAllocs = 0;
  918.     numResizes = 0;
  919.     numFrees = 0;
  920.  
  921. // RAVEN BEGIN
  922. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  923. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  924. // RAVEN END
  925.     blockId[0] = 0x11111111;
  926.     blockId[1] = 0x22222222;
  927.     blockId[2] = 0x33333333;
  928. #endif
  929. }
  930.  
  931. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  932. idDynamicBlock<type> *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::AllocInternal( const int num ) {
  933.     idDynamicBlock<type> *block;
  934.     int alignedBytes = ( num * sizeof( type ) + 15 ) & ~15;
  935.  
  936.     block = freeTree.FindSmallestLargerEqual( alignedBytes );
  937.     if ( block != NULL ) {
  938.         UnlinkFreeInternal( block );
  939.     } else if ( allowAllocs ) {
  940.         int allocSize = Max( baseBlockSize, alignedBytes + (int)sizeof( idDynamicBlock<type> ) );
  941. //RAVEN BEGIN
  942. //amccarthy: Added allocation tag
  943.         block = ( idDynamicBlock<type> * ) Mem_Alloc16( allocSize, memoryTag );
  944. //RAVEN END
  945.         if ( lockMemory ) {
  946.             idLib::sys->LockMemory( block, baseBlockSize );
  947.         }
  948. // RAVEN BEGIN
  949. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  950. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  951. // RAVEN END
  952.         memcpy( block->id, blockId, sizeof( block->id ) );
  953.         block->allocator = (void*)this;
  954. #endif
  955.         block->SetSize( allocSize - (int)sizeof( idDynamicBlock<type> ), true );
  956.         block->next = NULL;
  957.         block->prev = lastBlock;
  958.         if ( lastBlock ) {
  959.             lastBlock->next = block;
  960.         } else {
  961.             firstBlock = block;
  962.         }
  963.         lastBlock = block;
  964.         block->node = NULL;
  965.  
  966.         numBaseBlocks++;
  967.         baseBlockMemory += allocSize;
  968.     }
  969.  
  970.     return block;
  971. }
  972.  
  973. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  974. idDynamicBlock<type> *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::ResizeInternal( idDynamicBlock<type> *block, const int num ) {
  975.     int alignedBytes = ( num * sizeof( type ) + 15 ) & ~15;
  976.  
  977. // RAVEN BEGIN
  978. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  979. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  980. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK_IS_FATAL)
  981.     const char *chkstr = CheckMemory( block );
  982.     if ( chkstr ) {
  983.         throw idException( chkstr );
  984.     }
  985. #endif
  986. // jsinger: attempt to eliminate cross-DLL allocation issues
  987. #ifdef RV_UNIFIED_ALLOCATOR
  988.     assert( block->id[0] == 0x11111111 && block->id[1] == 0x22222222 && block->id[2] == 0x33333333); // && block->allocator == (void*)this );
  989. #else
  990.     assert( block->id[0] == 0x11111111 && block->id[1] == 0x22222222 && block->id[2] == 0x33333333 && block->allocator == (void*)this );
  991. #endif
  992. // RAVEN END
  993. #endif
  994.  
  995.     // if the new size is larger
  996.     if ( alignedBytes > block->GetSize() ) {
  997.  
  998.         idDynamicBlock<type> *nextBlock = block->next;
  999.  
  1000.         // try to annexate the next block if it's free
  1001.         if ( nextBlock && !nextBlock->IsBaseBlock() && nextBlock->node != NULL &&
  1002.                 block->GetSize() + (int)sizeof( idDynamicBlock<type> ) + nextBlock->GetSize() >= alignedBytes ) {
  1003.  
  1004.             UnlinkFreeInternal( nextBlock );
  1005.             block->SetSize( block->GetSize() + (int)sizeof( idDynamicBlock<type> ) + nextBlock->GetSize(), block->IsBaseBlock() );
  1006.             block->next = nextBlock->next;
  1007.             if ( nextBlock->next ) {
  1008.                 nextBlock->next->prev = block;
  1009.             } else {
  1010.                 lastBlock = block;
  1011.             }
  1012.         } else {
  1013.             // allocate a new block and copy
  1014.             idDynamicBlock<type> *oldBlock = block;
  1015.             block = AllocInternal( num );
  1016.             if ( block == NULL ) {
  1017.                 return NULL;
  1018.             }
  1019.             memcpy( block->GetMemory(), oldBlock->GetMemory(), oldBlock->GetSize() );
  1020.             FreeInternal( oldBlock );
  1021.         }
  1022.     }
  1023.  
  1024.     // if the unused space at the end of this block is large enough to hold a block with at least one element
  1025.     if ( block->GetSize() - alignedBytes - (int)sizeof( idDynamicBlock<type> ) < Max( minBlockSize, (int)sizeof( type ) ) ) {
  1026.         return block;
  1027.     }
  1028.  
  1029.     idDynamicBlock<type> *newBlock;
  1030.  
  1031.     newBlock = ( idDynamicBlock<type> * ) ( ( (byte *) block ) + (int)sizeof( idDynamicBlock<type> ) + alignedBytes );
  1032. // RAVEN BEGIN
  1033. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  1034. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  1035. // RAVEN END
  1036.     memcpy( newBlock->id, blockId, sizeof( newBlock->id ) );
  1037.     newBlock->allocator = (void*)this;
  1038. #endif
  1039.     newBlock->SetSize( block->GetSize() - alignedBytes - (int)sizeof( idDynamicBlock<type> ), false );
  1040.     newBlock->next = block->next;
  1041.     newBlock->prev = block;
  1042.     if ( newBlock->next ) {
  1043.         newBlock->next->prev = newBlock;
  1044.     } else {
  1045.         lastBlock = newBlock;
  1046.     }
  1047.     newBlock->node = NULL;
  1048.     block->next = newBlock;
  1049.     block->SetSize( alignedBytes, block->IsBaseBlock() );
  1050.  
  1051.     FreeInternal( newBlock );
  1052.  
  1053.     return block;
  1054. }
  1055.  
  1056. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  1057. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::FreeInternal( idDynamicBlock<type> *block ) {
  1058.  
  1059.     assert( block->node == NULL );
  1060.  
  1061. // RAVEN BEGIN
  1062. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  1063. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  1064. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK_IS_FATAL)
  1065.     const char *chkstr = CheckMemory( block );
  1066.     if ( chkstr ) {
  1067.         throw idException( chkstr );
  1068.     }
  1069. #endif
  1070. // jsinger: attempt to eliminate cross-DLL allocation issues
  1071. #ifdef RV_UNIFIED_ALLOCATOR
  1072.     assert( block->id[0] == 0x11111111 && block->id[1] == 0x22222222 && block->id[2] == 0x33333333 );//&& block->allocator == (void*)this );
  1073. #else
  1074.     assert( block->id[0] == 0x11111111 && block->id[1] == 0x22222222 && block->id[2] == 0x33333333 && block->allocator == (void*)this );
  1075. #endif // RV_UNIFIED_ALLOCATOR
  1076. // RAVEN END
  1077. #endif
  1078.  
  1079.     // try to merge with a next free block
  1080.     idDynamicBlock<type> *nextBlock = block->next;
  1081.     if ( nextBlock && !nextBlock->IsBaseBlock() && nextBlock->node != NULL ) {
  1082.         UnlinkFreeInternal( nextBlock );
  1083.         block->SetSize( block->GetSize() + (int)sizeof( idDynamicBlock<type> ) + nextBlock->GetSize(), block->IsBaseBlock() );
  1084.         block->next = nextBlock->next;
  1085.         if ( nextBlock->next ) {
  1086.             nextBlock->next->prev = block;
  1087.         } else {
  1088.             lastBlock = block;
  1089.         }
  1090.     }
  1091.  
  1092.     // try to merge with a previous free block
  1093.     idDynamicBlock<type> *prevBlock = block->prev;
  1094.     if ( prevBlock && !block->IsBaseBlock() && prevBlock->node != NULL ) {
  1095.         UnlinkFreeInternal( prevBlock );
  1096.         prevBlock->SetSize( prevBlock->GetSize() + (int)sizeof( idDynamicBlock<type> ) + block->GetSize(), prevBlock->IsBaseBlock() );
  1097.         prevBlock->next = block->next;
  1098.         if ( block->next ) {
  1099.             block->next->prev = prevBlock;
  1100.         } else {
  1101.             lastBlock = prevBlock;
  1102.         }
  1103.         LinkFreeInternal( prevBlock );
  1104.     } else {
  1105.         LinkFreeInternal( block );
  1106.     }
  1107. }
  1108.  
  1109. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  1110. ID_INLINE void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::LinkFreeInternal( idDynamicBlock<type> *block ) {
  1111.     block->node = freeTree.Add( block, block->GetSize() );
  1112.     numFreeBlocks++;
  1113.     freeBlockMemory += block->GetSize();
  1114. }
  1115.  
  1116. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  1117. ID_INLINE void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::UnlinkFreeInternal( idDynamicBlock<type> *block ) {
  1118.     freeTree.Remove( block->node );
  1119.     block->node = NULL;
  1120.     numFreeBlocks--;
  1121.     freeBlockMemory -= block->GetSize();
  1122. }
  1123.  
  1124. template<class type, int baseBlockSize, int minBlockSize, byte memoryTag>
  1125. void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize, memoryTag>::CheckMemory( void ) const {
  1126.     idDynamicBlock<type> *block;
  1127.  
  1128.     for ( block = firstBlock; block != NULL; block = block->next ) {
  1129.  
  1130. // RAVEN BEGIN
  1131. // jnewquist: Fast sanity checking of idDynamicBlockAlloc
  1132. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK) || defined(DYNAMIC_BLOCK_ALLOC_FASTCHECK)
  1133. #if defined(DYNAMIC_BLOCK_ALLOC_CHECK_IS_FATAL)
  1134.         const char *chkstr = CheckMemory( block );
  1135.         if ( chkstr ) {
  1136.             throw idException( chkstr );
  1137.         }
  1138. #endif
  1139. // jsinger: attempt to eliminate cross-DLL allocation issues
  1140. #ifdef RV_UNIFIED_ALLOCATOR
  1141.         assert( block->id[0] == 0x11111111 && block->id[1] == 0x22222222 && block->id[2] == 0x33333333); // && block->allocator == (void*)this );
  1142. #else
  1143.         assert( block->id[0] == 0x11111111 && block->id[1] == 0x22222222 && block->id[2] == 0x33333333 && block->allocator == (void*)this );
  1144. #endif
  1145. // RAVEN END
  1146. #endif
  1147.  
  1148.         // make sure the block is properly linked
  1149.         if ( block->prev == NULL ) {
  1150.             assert( firstBlock == block );
  1151.         } else {
  1152.             assert( block->prev->next == block );
  1153.         }
  1154.         if ( block->next == NULL ) {
  1155.             assert( lastBlock == block );
  1156.         } else {
  1157.             assert( block->next->prev == block );
  1158.         }
  1159.     }
  1160. }
  1161.  
  1162. #endif /* !__HEAP_H__ */
  1163.