1 /*
2 ===========================================================================
3
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code").
8
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29 #ifndef __HEAP_H__
30 #define __HEAP_H__
31
32 #include "idlib/Lib.h"
33 #include "sys/sys_public.h"
34
35 /*
36 ===============================================================================
37
38 Memory Management
39
40 This is a replacement for the compiler heap code (i.e. "C" malloc() and
41 free() calls). On average 2.5-3.0 times faster than MSVC malloc()/free().
42 Worst case performance is 1.65 times faster and best case > 70 times.
43
44 ===============================================================================
45 */
46
47
48 typedef struct {
49 int num;
50 int minSize;
51 int maxSize;
52 int totalSize;
53 } memoryStats_t;
54
55
56 void Mem_Init( void );
57 void Mem_Shutdown( void );
58 void Mem_EnableLeakTest( const char *name );
59 void Mem_ClearFrameStats( void );
60 void Mem_GetFrameStats( memoryStats_t &allocs, memoryStats_t &frees );
61 void Mem_GetStats( memoryStats_t &stats );
62 void Mem_Dump_f( const class idCmdArgs &args );
63 void Mem_DumpCompressed_f( const class idCmdArgs &args );
64 void Mem_AllocDefragBlock( void );
65
66
67 #ifndef ID_DEBUG_MEMORY
68
69 void * Mem_Alloc( const int size );
70 void * Mem_ClearedAlloc( const int size );
71 void Mem_Free( void *ptr );
72 char * Mem_CopyString( const char *in );
73 void * Mem_Alloc16( const int size );
74 void Mem_Free16( void *ptr );
75
76 #ifdef ID_REDIRECT_NEWDELETE
77
new(size_t s)78 __inline void *operator new( size_t s ) {
79 return Mem_Alloc( s );
80 }
delete(void * p)81 __inline void operator delete( void *p ) {
82 Mem_Free( p );
83 }
84 __inline void *operator new[]( size_t s ) {
85 return Mem_Alloc( s );
86 }
87 __inline void operator delete[]( void *p ) {
88 Mem_Free( p );
89 }
90
91 #endif
92
93 #else /* ID_DEBUG_MEMORY */
94
95 void * Mem_Alloc( const int size, const char *fileName, const int lineNumber );
96 void * Mem_ClearedAlloc( const int size, const char *fileName, const int lineNumber );
97 void Mem_Free( void *ptr, const char *fileName, const int lineNumber );
98 char * Mem_CopyString( const char *in, const char *fileName, const int lineNumber );
99 void * Mem_Alloc16( const int size, const char *fileName, const int lineNumber );
100 void Mem_Free16( void *ptr, const char *fileName, const int lineNumber );
101
102 #ifdef ID_REDIRECT_NEWDELETE
103
new(size_t s,int t1,int t2,char * fileName,int lineNumber)104 __inline void *operator new( size_t s, int t1, int t2, char *fileName, int lineNumber ) {
105 return Mem_Alloc( s, fileName, lineNumber );
106 }
delete(void * p,int t1,int t2,char * fileName,int lineNumber)107 __inline void operator delete( void *p, int t1, int t2, char *fileName, int lineNumber ) {
108 Mem_Free( p, fileName, lineNumber );
109 }
110 __inline void *operator new[]( size_t s, int t1, int t2, char *fileName, int lineNumber ) {
111 return Mem_Alloc( s, fileName, lineNumber );
112 }
113 __inline void operator delete[]( void *p, int t1, int t2, char *fileName, int lineNumber ) {
114 Mem_Free( p, fileName, lineNumber );
115 }
new(size_t s)116 __inline void *operator new( size_t s ) {
117 return Mem_Alloc( s, "", 0 );
118 }
delete(void * p)119 __inline void operator delete( void *p ) {
120 Mem_Free( p, "", 0 );
121 }
122 __inline void *operator new[]( size_t s ) {
123 return Mem_Alloc( s, "", 0 );
124 }
125 __inline void operator delete[]( void *p ) {
126 Mem_Free( p, "", 0 );
127 }
128
129 #define ID_DEBUG_NEW new( 0, 0, __FILE__, __LINE__ )
130 #undef new
131 #define new ID_DEBUG_NEW
132
133 #endif
134
135 #define Mem_Alloc( size ) Mem_Alloc( size, __FILE__, __LINE__ )
136 #define Mem_ClearedAlloc( size ) Mem_ClearedAlloc( size, __FILE__, __LINE__ )
137 #define Mem_Free( ptr ) Mem_Free( ptr, __FILE__, __LINE__ )
138 #define Mem_CopyString( s ) Mem_CopyString( s, __FILE__, __LINE__ )
139 #define Mem_Alloc16( size ) Mem_Alloc16( size, __FILE__, __LINE__ )
140 #define Mem_Free16( ptr ) Mem_Free16( ptr, __FILE__, __LINE__ )
141
142 #endif /* ID_DEBUG_MEMORY */
143
144
145 /*
146 ===============================================================================
147
148 Block based allocator for fixed size objects.
149
150 All objects of the 'type' are properly constructed.
151 However, the constructor is not called for re-used objects.
152
153 ===============================================================================
154 */
155
156 template<class type, int blockSize>
157 class idBlockAlloc {
158 public:
159 idBlockAlloc( void );
160 ~idBlockAlloc( void );
161
162 void Shutdown( void );
163
164 type * Alloc( void );
165 void Free( type *element );
166
GetTotalCount(void)167 int GetTotalCount( void ) const { return total; }
GetAllocCount(void)168 int GetAllocCount( void ) const { return active; }
GetFreeCount(void)169 int GetFreeCount( void ) const { return total - active; }
170
171 private:
172 typedef struct element_s {
173 type t;
174 struct element_s * next;
175 } element_t;
176 typedef struct block_s {
177 element_t elements[blockSize];
178 struct block_s * next;
179 } block_t;
180
181 block_t * blocks;
182 element_t * free;
183 int total;
184 int active;
185 };
186
187 template<class type, int blockSize>
idBlockAlloc(void)188 idBlockAlloc<type,blockSize>::idBlockAlloc( void ) {
189 blocks = NULL;
190 free = NULL;
191 total = active = 0;
192 }
193
194 template<class type, int blockSize>
~idBlockAlloc(void)195 idBlockAlloc<type,blockSize>::~idBlockAlloc( void ) {
196 Shutdown();
197 }
198
199 template<class type, int blockSize>
Alloc(void)200 type *idBlockAlloc<type,blockSize>::Alloc( void ) {
201 if ( !free ) {
202 block_t *block = new block_t;
203 block->next = blocks;
204 blocks = block;
205 for ( int i = 0; i < blockSize; i++ ) {
206 block->elements[i].next = free;
207 free = &block->elements[i];
208 }
209 total += blockSize;
210 }
211 active++;
212 element_t *element = free;
213 free = free->next;
214 element->next = NULL;
215 return &element->t;
216 }
217
218 template<class type, int blockSize>
Free(type * t)219 void idBlockAlloc<type,blockSize>::Free( type *t ) {
220 element_t *element = (element_t *)t;
221 element->next = free;
222 free = element;
223 active--;
224 }
225
226 template<class type, int blockSize>
Shutdown(void)227 void idBlockAlloc<type,blockSize>::Shutdown( void ) {
228 while( blocks ) {
229 block_t *block = blocks;
230 blocks = blocks->next;
231 delete block;
232 }
233 blocks = NULL;
234 free = NULL;
235 total = active = 0;
236 }
237
238 /*
239 ==============================================================================
240
241 Dynamic allocator, simple wrapper for normal allocations which can
242 be interchanged with idDynamicBlockAlloc.
243
244 No constructor is called for the 'type'.
245 Allocated blocks are always 16 byte aligned.
246
247 ==============================================================================
248 */
249
250 template<class type, int baseBlockSize, int minBlockSize>
251 class idDynamicAlloc {
252 public:
253 idDynamicAlloc( void );
254 ~idDynamicAlloc( void );
255
256 void Init( void );
257 void Shutdown( void );
SetFixedBlocks(int numBlocks)258 void SetFixedBlocks( int numBlocks ) {}
SetLockMemory(bool lock)259 void SetLockMemory( bool lock ) {}
FreeEmptyBaseBlocks(void)260 void FreeEmptyBaseBlocks( void ) {}
261
262 type * Alloc( const int num );
263 type * Resize( type *ptr, const int num );
264 void Free( type *ptr );
265 const char * CheckMemory( const type *ptr ) const;
266
GetNumBaseBlocks(void)267 int GetNumBaseBlocks( void ) const { return 0; }
GetBaseBlockMemory(void)268 int GetBaseBlockMemory( void ) const { return 0; }
GetNumUsedBlocks(void)269 int GetNumUsedBlocks( void ) const { return numUsedBlocks; }
GetUsedBlockMemory(void)270 int GetUsedBlockMemory( void ) const { return usedBlockMemory; }
GetNumFreeBlocks(void)271 int GetNumFreeBlocks( void ) const { return 0; }
GetFreeBlockMemory(void)272 int GetFreeBlockMemory( void ) const { return 0; }
GetNumEmptyBaseBlocks(void)273 int GetNumEmptyBaseBlocks( void ) const { return 0; }
274
275 private:
276 int numUsedBlocks; // number of used blocks
277 int usedBlockMemory; // total memory in used blocks
278
279 int numAllocs;
280 int numResizes;
281 int numFrees;
282
283 void Clear( void );
284 };
285
286 template<class type, int baseBlockSize, int minBlockSize>
idDynamicAlloc(void)287 idDynamicAlloc<type, baseBlockSize, minBlockSize>::idDynamicAlloc( void ) {
288 Clear();
289 }
290
291 template<class type, int baseBlockSize, int minBlockSize>
~idDynamicAlloc(void)292 idDynamicAlloc<type, baseBlockSize, minBlockSize>::~idDynamicAlloc( void ) {
293 Shutdown();
294 }
295
296 template<class type, int baseBlockSize, int minBlockSize>
Init(void)297 void idDynamicAlloc<type, baseBlockSize, minBlockSize>::Init( void ) {
298 }
299
300 template<class type, int baseBlockSize, int minBlockSize>
Shutdown(void)301 void idDynamicAlloc<type, baseBlockSize, minBlockSize>::Shutdown( void ) {
302 Clear();
303 }
304
305 template<class type, int baseBlockSize, int minBlockSize>
Alloc(const int num)306 type *idDynamicAlloc<type, baseBlockSize, minBlockSize>::Alloc( const int num ) {
307 numAllocs++;
308 if ( num <= 0 ) {
309 return NULL;
310 }
311 numUsedBlocks++;
312 usedBlockMemory += num * sizeof( type );
313 return Mem_Alloc16( num * sizeof( type ) );
314 }
315
316 template<class type, int baseBlockSize, int minBlockSize>
Resize(type * ptr,const int num)317 type *idDynamicAlloc<type, baseBlockSize, minBlockSize>::Resize( type *ptr, const int num ) {
318
319 numResizes++;
320
321 if ( ptr == NULL ) {
322 return Alloc( num );
323 }
324
325 if ( num <= 0 ) {
326 Free( ptr );
327 return NULL;
328 }
329
330 assert( 0 );
331 return ptr;
332 }
333
334 template<class type, int baseBlockSize, int minBlockSize>
Free(type * ptr)335 void idDynamicAlloc<type, baseBlockSize, minBlockSize>::Free( type *ptr ) {
336 numFrees++;
337 if ( ptr == NULL ) {
338 return;
339 }
340 Mem_Free16( ptr );
341 }
342
343 template<class type, int baseBlockSize, int minBlockSize>
CheckMemory(const type * ptr)344 const char *idDynamicAlloc<type, baseBlockSize, minBlockSize>::CheckMemory( const type *ptr ) const {
345 return NULL;
346 }
347
348 template<class type, int baseBlockSize, int minBlockSize>
Clear(void)349 void idDynamicAlloc<type, baseBlockSize, minBlockSize>::Clear( void ) {
350 numUsedBlocks = 0;
351 usedBlockMemory = 0;
352 numAllocs = 0;
353 numResizes = 0;
354 numFrees = 0;
355 }
356
357
358 /*
359 ==============================================================================
360
361 Fast dynamic block allocator.
362
363 No constructor is called for the 'type'.
364 Allocated blocks are always 16 byte aligned.
365
366 ==============================================================================
367 */
368
369 #include "containers/BTree.h"
370
371 //#define DYNAMIC_BLOCK_ALLOC_CHECK
372
373 template<class type>
374 class idDynamicBlock {
375 public:
GetMemory(void)376 type * GetMemory( void ) const { return (type *)( ( (byte *) this ) + sizeof( idDynamicBlock<type> ) ); }
GetSize(void)377 int GetSize( void ) const { return abs( size ); }
SetSize(int s,bool isBaseBlock)378 void SetSize( int s, bool isBaseBlock ) { size = isBaseBlock ? -s : s; }
IsBaseBlock(void)379 bool IsBaseBlock( void ) const { return ( size < 0 ); }
380
381 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
382 int id[3];
383 void * allocator;
384 #endif
385
386 int size; // size in bytes of the block
387 idDynamicBlock<type> * prev; // previous memory block
388 idDynamicBlock<type> * next; // next memory block
389 idBTreeNode<idDynamicBlock<type>,int> *node; // node in the B-Tree with free blocks
390 };
391
392 template<class type, int baseBlockSize, int minBlockSize>
393 class idDynamicBlockAlloc {
394 public:
395 idDynamicBlockAlloc( void );
396 ~idDynamicBlockAlloc( void );
397
398 void Init( void );
399 void Shutdown( void );
400 void SetFixedBlocks( int numBlocks );
401 void SetLockMemory( bool lock );
402 void FreeEmptyBaseBlocks( void );
403
404 type * Alloc( const int num );
405 type * Resize( type *ptr, const int num );
406 void Free( type *ptr );
407 const char * CheckMemory( const type *ptr ) const;
408
GetNumBaseBlocks(void)409 int GetNumBaseBlocks( void ) const { return numBaseBlocks; }
GetBaseBlockMemory(void)410 int GetBaseBlockMemory( void ) const { return baseBlockMemory; }
GetNumUsedBlocks(void)411 int GetNumUsedBlocks( void ) const { return numUsedBlocks; }
GetUsedBlockMemory(void)412 int GetUsedBlockMemory( void ) const { return usedBlockMemory; }
GetNumFreeBlocks(void)413 int GetNumFreeBlocks( void ) const { return numFreeBlocks; }
GetFreeBlockMemory(void)414 int GetFreeBlockMemory( void ) const { return freeBlockMemory; }
415 int GetNumEmptyBaseBlocks( void ) const;
416
417 private:
418 idDynamicBlock<type> * firstBlock; // first block in list in order of increasing address
419 idDynamicBlock<type> * lastBlock; // last block in list in order of increasing address
420 idBTree<idDynamicBlock<type>,int,4>freeTree; // B-Tree with free memory blocks
421 bool allowAllocs; // allow base block allocations
422 bool lockMemory; // lock memory so it cannot get swapped out
423
424 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
425 int blockId[3];
426 #endif
427
428 int numBaseBlocks; // number of base blocks
429 int baseBlockMemory; // total memory in base blocks
430 int numUsedBlocks; // number of used blocks
431 int usedBlockMemory; // total memory in used blocks
432 int numFreeBlocks; // number of free blocks
433 int freeBlockMemory; // total memory in free blocks
434
435 int numAllocs;
436 int numResizes;
437 int numFrees;
438
439 void Clear( void );
440 idDynamicBlock<type> * AllocInternal( const int num );
441 idDynamicBlock<type> * ResizeInternal( idDynamicBlock<type> *block, const int num );
442 void FreeInternal( idDynamicBlock<type> *block );
443 void LinkFreeInternal( idDynamicBlock<type> *block );
444 void UnlinkFreeInternal( idDynamicBlock<type> *block );
445 void CheckMemory( void ) const;
446 };
447
448 template<class type, int baseBlockSize, int minBlockSize>
idDynamicBlockAlloc(void)449 idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::idDynamicBlockAlloc( void ) {
450 Clear();
451 }
452
453 template<class type, int baseBlockSize, int minBlockSize>
~idDynamicBlockAlloc(void)454 idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::~idDynamicBlockAlloc( void ) {
455 Shutdown();
456 }
457
458 template<class type, int baseBlockSize, int minBlockSize>
Init(void)459 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::Init( void ) {
460 freeTree.Init();
461 }
462
463 template<class type, int baseBlockSize, int minBlockSize>
Shutdown(void)464 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::Shutdown( void ) {
465 idDynamicBlock<type> *block;
466
467 for ( block = firstBlock; block != NULL; block = block->next ) {
468 if ( block->node == NULL ) {
469 FreeInternal( block );
470 }
471 }
472
473 for ( block = firstBlock; block != NULL; block = firstBlock ) {
474 firstBlock = block->next;
475 assert( block->IsBaseBlock() );
476 if ( lockMemory ) {
477 idLib::sys->UnlockMemory( block, block->GetSize() + (int)sizeof( idDynamicBlock<type> ) );
478 }
479 Mem_Free16( block );
480 }
481
482 freeTree.Shutdown();
483
484 Clear();
485 }
486
487 template<class type, int baseBlockSize, int minBlockSize>
SetFixedBlocks(int numBlocks)488 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::SetFixedBlocks( int numBlocks ) {
489 idDynamicBlock<type> *block;
490
491 for ( int i = numBaseBlocks; i < numBlocks; i++ ) {
492 block = ( idDynamicBlock<type> * ) Mem_Alloc16( baseBlockSize );
493 if ( lockMemory ) {
494 idLib::sys->LockMemory( block, baseBlockSize );
495 }
496 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
497 memcpy( block->id, blockId, sizeof( block->id ) );
498 block->allocator = (void*)this;
499 #endif
500 block->SetSize( baseBlockSize - (int)sizeof( idDynamicBlock<type> ), true );
501 block->next = NULL;
502 block->prev = lastBlock;
503 if ( lastBlock ) {
504 lastBlock->next = block;
505 } else {
506 firstBlock = block;
507 }
508 lastBlock = block;
509 block->node = NULL;
510
511 FreeInternal( block );
512
513 numBaseBlocks++;
514 baseBlockMemory += baseBlockSize;
515 }
516
517 allowAllocs = false;
518 }
519
520 template<class type, int baseBlockSize, int minBlockSize>
SetLockMemory(bool lock)521 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::SetLockMemory( bool lock ) {
522 lockMemory = lock;
523 }
524
525 template<class type, int baseBlockSize, int minBlockSize>
FreeEmptyBaseBlocks(void)526 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::FreeEmptyBaseBlocks( void ) {
527 idDynamicBlock<type> *block, *next;
528
529 for ( block = firstBlock; block != NULL; block = next ) {
530 next = block->next;
531
532 if ( block->IsBaseBlock() && block->node != NULL && ( next == NULL || next->IsBaseBlock() ) ) {
533 UnlinkFreeInternal( block );
534 if ( block->prev ) {
535 block->prev->next = block->next;
536 } else {
537 firstBlock = block->next;
538 }
539 if ( block->next ) {
540 block->next->prev = block->prev;
541 } else {
542 lastBlock = block->prev;
543 }
544 if ( lockMemory ) {
545 idLib::sys->UnlockMemory( block, block->GetSize() + (int)sizeof( idDynamicBlock<type> ) );
546 }
547 numBaseBlocks--;
548 baseBlockMemory -= block->GetSize() + (int)sizeof( idDynamicBlock<type> );
549 Mem_Free16( block );
550 }
551 }
552
553 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
554 CheckMemory();
555 #endif
556 }
557
558 template<class type, int baseBlockSize, int minBlockSize>
GetNumEmptyBaseBlocks(void)559 int idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::GetNumEmptyBaseBlocks( void ) const {
560 int numEmptyBaseBlocks;
561 idDynamicBlock<type> *block;
562
563 numEmptyBaseBlocks = 0;
564 for ( block = firstBlock; block != NULL; block = block->next ) {
565 if ( block->IsBaseBlock() && block->node != NULL && ( block->next == NULL || block->next->IsBaseBlock() ) ) {
566 numEmptyBaseBlocks++;
567 }
568 }
569 return numEmptyBaseBlocks;
570 }
571
572 template<class type, int baseBlockSize, int minBlockSize>
Alloc(const int num)573 type *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::Alloc( const int num ) {
574 idDynamicBlock<type> *block;
575
576 numAllocs++;
577
578 if ( num <= 0 ) {
579 return NULL;
580 }
581
582 block = AllocInternal( num );
583 if ( block == NULL ) {
584 return NULL;
585 }
586 block = ResizeInternal( block, num );
587 if ( block == NULL ) {
588 return NULL;
589 }
590
591 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
592 CheckMemory();
593 #endif
594
595 numUsedBlocks++;
596 usedBlockMemory += block->GetSize();
597
598 return block->GetMemory();
599 }
600
601 template<class type, int baseBlockSize, int minBlockSize>
Resize(type * ptr,const int num)602 type *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::Resize( type *ptr, const int num ) {
603
604 numResizes++;
605
606 if ( ptr == NULL ) {
607 return Alloc( num );
608 }
609
610 if ( num <= 0 ) {
611 Free( ptr );
612 return NULL;
613 }
614
615 idDynamicBlock<type> *block = ( idDynamicBlock<type> * ) ( ( (byte *) ptr ) - (int)sizeof( idDynamicBlock<type> ) );
616
617 usedBlockMemory -= block->GetSize();
618
619 block = ResizeInternal( block, num );
620 if ( block == NULL ) {
621 return NULL;
622 }
623
624 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
625 CheckMemory();
626 #endif
627
628 usedBlockMemory += block->GetSize();
629
630 return block->GetMemory();
631 }
632
633 template<class type, int baseBlockSize, int minBlockSize>
Free(type * ptr)634 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::Free( type *ptr ) {
635
636 numFrees++;
637
638 if ( ptr == NULL ) {
639 return;
640 }
641
642 idDynamicBlock<type> *block = ( idDynamicBlock<type> * ) ( ( (byte *) ptr ) - (int)sizeof( idDynamicBlock<type> ) );
643
644 numUsedBlocks--;
645 usedBlockMemory -= block->GetSize();
646
647 FreeInternal( block );
648
649 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
650 CheckMemory();
651 #endif
652 }
653
654 template<class type, int baseBlockSize, int minBlockSize>
CheckMemory(const type * ptr)655 const char *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::CheckMemory( const type *ptr ) const {
656 idDynamicBlock<type> *block;
657
658 if ( ptr == NULL ) {
659 return NULL;
660 }
661
662 block = ( idDynamicBlock<type> * ) ( ( (byte *) ptr ) - (int)sizeof( idDynamicBlock<type> ) );
663
664 if ( block->node != NULL ) {
665 return "memory has been freed";
666 }
667
668 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
669 if ( block->id[0] != 0x11111111 || block->id[1] != 0x22222222 || block->id[2] != 0x33333333 ) {
670 return "memory has invalid id";
671 }
672 if ( block->allocator != (void*)this ) {
673 return "memory was allocated with different allocator";
674 }
675 #endif
676
677 /* base blocks can be larger than baseBlockSize which can cause this code to fail
678 idDynamicBlock<type> *base;
679 for ( base = firstBlock; base != NULL; base = base->next ) {
680 if ( base->IsBaseBlock() ) {
681 if ( ((int)block) >= ((int)base) && ((int)block) < ((int)base) + baseBlockSize ) {
682 break;
683 }
684 }
685 }
686 if ( base == NULL ) {
687 return "no base block found for memory";
688 }
689 */
690
691 return NULL;
692 }
693
694 template<class type, int baseBlockSize, int minBlockSize>
Clear(void)695 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::Clear( void ) {
696 firstBlock = lastBlock = NULL;
697 allowAllocs = true;
698 lockMemory = false;
699 numBaseBlocks = 0;
700 baseBlockMemory = 0;
701 numUsedBlocks = 0;
702 usedBlockMemory = 0;
703 numFreeBlocks = 0;
704 freeBlockMemory = 0;
705 numAllocs = 0;
706 numResizes = 0;
707 numFrees = 0;
708
709 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
710 blockId[0] = 0x11111111;
711 blockId[1] = 0x22222222;
712 blockId[2] = 0x33333333;
713 #endif
714 }
715
716 template<class type, int baseBlockSize, int minBlockSize>
AllocInternal(const int num)717 idDynamicBlock<type> *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::AllocInternal( const int num ) {
718 idDynamicBlock<type> *block;
719 int alignedBytes = ( num * sizeof( type ) + 15 ) & ~15;
720
721 block = freeTree.FindSmallestLargerEqual( alignedBytes );
722 if ( block != NULL ) {
723 UnlinkFreeInternal( block );
724 } else if ( allowAllocs ) {
725 int allocSize = Max( baseBlockSize, alignedBytes + (int)sizeof( idDynamicBlock<type> ) );
726 block = ( idDynamicBlock<type> * ) Mem_Alloc16( allocSize );
727 if ( lockMemory ) {
728 idLib::sys->LockMemory( block, baseBlockSize );
729 }
730 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
731 memcpy( block->id, blockId, sizeof( block->id ) );
732 block->allocator = (void*)this;
733 #endif
734 block->SetSize( allocSize - (int)sizeof( idDynamicBlock<type> ), true );
735 block->next = NULL;
736 block->prev = lastBlock;
737 if ( lastBlock ) {
738 lastBlock->next = block;
739 } else {
740 firstBlock = block;
741 }
742 lastBlock = block;
743 block->node = NULL;
744
745 numBaseBlocks++;
746 baseBlockMemory += allocSize;
747 }
748
749 return block;
750 }
751
752 template<class type, int baseBlockSize, int minBlockSize>
ResizeInternal(idDynamicBlock<type> * block,const int num)753 idDynamicBlock<type> *idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::ResizeInternal( idDynamicBlock<type> *block, const int num ) {
754 int alignedBytes = ( num * sizeof( type ) + 15 ) & ~15;
755
756 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
757 assert( block->id[0] == 0x11111111 && block->id[1] == 0x22222222 && block->id[2] == 0x33333333 && block->allocator == (void*)this );
758 #endif
759
760 // if the new size is larger
761 if ( alignedBytes > block->GetSize() ) {
762
763 idDynamicBlock<type> *nextBlock = block->next;
764
765 // try to annexate the next block if it's free
766 if ( nextBlock && !nextBlock->IsBaseBlock() && nextBlock->node != NULL &&
767 block->GetSize() + (int)sizeof( idDynamicBlock<type> ) + nextBlock->GetSize() >= alignedBytes ) {
768
769 UnlinkFreeInternal( nextBlock );
770 block->SetSize( block->GetSize() + (int)sizeof( idDynamicBlock<type> ) + nextBlock->GetSize(), block->IsBaseBlock() );
771 block->next = nextBlock->next;
772 if ( nextBlock->next ) {
773 nextBlock->next->prev = block;
774 } else {
775 lastBlock = block;
776 }
777 } else {
778 // allocate a new block and copy
779 idDynamicBlock<type> *oldBlock = block;
780 block = AllocInternal( num );
781 if ( block == NULL ) {
782 return NULL;
783 }
784 memcpy( block->GetMemory(), oldBlock->GetMemory(), oldBlock->GetSize() );
785 FreeInternal( oldBlock );
786 }
787 }
788
789 // if the unused space at the end of this block is large enough to hold a block with at least one element
790 if ( block->GetSize() - alignedBytes - (int)sizeof( idDynamicBlock<type> ) < Max( minBlockSize, (int)sizeof( type ) ) ) {
791 return block;
792 }
793
794 idDynamicBlock<type> *newBlock;
795
796 newBlock = ( idDynamicBlock<type> * ) ( ( (byte *) block ) + (int)sizeof( idDynamicBlock<type> ) + alignedBytes );
797 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
798 memcpy( newBlock->id, blockId, sizeof( newBlock->id ) );
799 newBlock->allocator = (void*)this;
800 #endif
801 newBlock->SetSize( block->GetSize() - alignedBytes - (int)sizeof( idDynamicBlock<type> ), false );
802 newBlock->next = block->next;
803 newBlock->prev = block;
804 if ( newBlock->next ) {
805 newBlock->next->prev = newBlock;
806 } else {
807 lastBlock = newBlock;
808 }
809 newBlock->node = NULL;
810 block->next = newBlock;
811 block->SetSize( alignedBytes, block->IsBaseBlock() );
812
813 FreeInternal( newBlock );
814
815 return block;
816 }
817
818 template<class type, int baseBlockSize, int minBlockSize>
FreeInternal(idDynamicBlock<type> * block)819 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::FreeInternal( idDynamicBlock<type> *block ) {
820
821 assert( block->node == NULL );
822
823 #ifdef DYNAMIC_BLOCK_ALLOC_CHECK
824 assert( block->id[0] == 0x11111111 && block->id[1] == 0x22222222 && block->id[2] == 0x33333333 && block->allocator == (void*)this );
825 #endif
826
827 // try to merge with a next free block
828 idDynamicBlock<type> *nextBlock = block->next;
829 if ( nextBlock && !nextBlock->IsBaseBlock() && nextBlock->node != NULL ) {
830 UnlinkFreeInternal( nextBlock );
831 block->SetSize( block->GetSize() + (int)sizeof( idDynamicBlock<type> ) + nextBlock->GetSize(), block->IsBaseBlock() );
832 block->next = nextBlock->next;
833 if ( nextBlock->next ) {
834 nextBlock->next->prev = block;
835 } else {
836 lastBlock = block;
837 }
838 }
839
840 // try to merge with a previous free block
841 idDynamicBlock<type> *prevBlock = block->prev;
842 if ( prevBlock && !block->IsBaseBlock() && prevBlock->node != NULL ) {
843 UnlinkFreeInternal( prevBlock );
844 prevBlock->SetSize( prevBlock->GetSize() + (int)sizeof( idDynamicBlock<type> ) + block->GetSize(), prevBlock->IsBaseBlock() );
845 prevBlock->next = block->next;
846 if ( block->next ) {
847 block->next->prev = prevBlock;
848 } else {
849 lastBlock = prevBlock;
850 }
851 LinkFreeInternal( prevBlock );
852 } else {
853 LinkFreeInternal( block );
854 }
855 }
856
857 template<class type, int baseBlockSize, int minBlockSize>
LinkFreeInternal(idDynamicBlock<type> * block)858 ID_INLINE void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::LinkFreeInternal( idDynamicBlock<type> *block ) {
859 block->node = freeTree.Add( block, block->GetSize() );
860 numFreeBlocks++;
861 freeBlockMemory += block->GetSize();
862 }
863
864 template<class type, int baseBlockSize, int minBlockSize>
UnlinkFreeInternal(idDynamicBlock<type> * block)865 ID_INLINE void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::UnlinkFreeInternal( idDynamicBlock<type> *block ) {
866 freeTree.Remove( block->node );
867 block->node = NULL;
868 numFreeBlocks--;
869 freeBlockMemory -= block->GetSize();
870 }
871
872 template<class type, int baseBlockSize, int minBlockSize>
CheckMemory(void)873 void idDynamicBlockAlloc<type, baseBlockSize, minBlockSize>::CheckMemory( void ) const {
874 idDynamicBlock<type> *block;
875
876 for ( block = firstBlock; block != NULL; block = block->next ) {
877 // make sure the block is properly linked
878 if ( block->prev == NULL ) {
879 assert( firstBlock == block );
880 } else {
881 assert( block->prev->next == block );
882 }
883 if ( block->next == NULL ) {
884 assert( lastBlock == block );
885 } else {
886 assert( block->next->prev == block );
887 }
888 }
889 }
890
891 #endif /* !__HEAP_H__ */
892