HEAP.CPP (37858B)
1 // 2 // Copyright 2020 Electronic Arts Inc. 3 // 4 // TiberianDawn.DLL and RedAlert.dll and corresponding source code is free 5 // software: you can redistribute it and/or modify it under the terms of 6 // the GNU General Public License as published by the Free Software Foundation, 7 // either version 3 of the License, or (at your option) any later version. 8 9 // TiberianDawn.DLL and RedAlert.dll and corresponding source code is distributed 10 // in the hope that it will be useful, but with permitted additional restrictions 11 // under Section 7 of the GPL. See the GNU General Public License in LICENSE.TXT 12 // distributed with this program. You should have received a copy of the 13 // GNU General Public License along with permitted additional restrictions 14 // with this program. If not, see https://github.com/electronicarts/CnC_Remastered_Collection 15 16 /* $Header: /CounterStrike/HEAP.CPP 1 3/03/97 10:24a Joe_bostic $ */ 17 /*********************************************************************************************** 18 *** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S *** 19 *********************************************************************************************** 20 * * 21 * Project Name : Command & Conquer * 22 * * 23 * File Name : HEAP.CPP * 24 * * 25 * Programmer : Joe L. Bostic * 26 * * 27 * Start Date : 02/18/95 * 28 * * 29 * Last Update : May 6, 1996 [JLB] * 30 * * 31 *---------------------------------------------------------------------------------------------* 32 * Functions: * 33 * FixedHeapClass::Allocate -- Allocate a sub-block from the heap. * 34 * FixedHeapClass::Clear -- Clears (and frees) the heap manager memory. * 35 * FixedHeapClass::FixedHeapClass -- Normal constructor for heap management class. * 36 * FixedHeapClass::Free -- Frees a sub-block in the heap. * 37 * FixedHeapClass::Free_All -- Frees all objects in the fixed heap. * 38 * FixedHeapClass::ID -- Converts a pointer to a sub-block index number. * 39 * FixedHeapClass::Set_Heap -- Assigns a memory block for this heap manager. * 40 * FixedHeapClass::~FixedHeapClass -- Destructor for the heap manager class. * 41 * FixedIHeapClass::Allocate -- Allocate an object from the heap. * 42 * FixedIHeapClass::Clear -- Clears the fixed heap of all entries. * 43 * FixedIHeapClass::Free -- Frees an object in the heap. * 44 * FixedIHeapClass::Free_All -- Frees all objects out of the indexed heap. * 45 * FixedIHeapClass::Logical_ID -- Fetches the logical ID number. * 46 * FixedIHeapClass::Set_Heap -- Set the heap to the buffer provided. * 47 * TFixedIHeapClass::Code_Pointers -- codes pointers for every object, to prepare for save * 48 * TFixedIHeapClass::Decode_Pointers -- Decodes all object pointers, for after loading * 49 * TFixedIHeapClass::Load -- Loads all active objects * 50 * TFixedIHeapClass::Save -- Saves all active objects * 51 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ 52 53 54 #include "function.h" 55 #include "heap.h" 56 //#include <mem.h> 57 #include <stdio.h> 58 #include <stddef.h> 59 #include <conio.h> 60 #include <string.h> 61 62 63 template class TFixedIHeapClass<AircraftClass>; 64 template class TFixedIHeapClass<AircraftTypeClass>; 65 template class TFixedIHeapClass<AnimClass>; 66 template class TFixedIHeapClass<AnimTypeClass>; 67 template class TFixedIHeapClass<BuildingClass>; 68 template class TFixedIHeapClass<BuildingTypeClass>; 69 template class TFixedIHeapClass<BulletClass>; 70 template class TFixedIHeapClass<BulletTypeClass>; 71 template class TFixedIHeapClass<FactoryClass>; 72 template class TFixedIHeapClass<HouseClass>; 73 template class TFixedIHeapClass<HouseTypeClass>; 74 template class TFixedIHeapClass<InfantryClass>; 75 template class TFixedIHeapClass<InfantryTypeClass>; 76 template class TFixedIHeapClass<OverlayClass>; 77 template class TFixedIHeapClass<OverlayTypeClass>; 78 template class TFixedIHeapClass<SmudgeClass>; 79 template class TFixedIHeapClass<SmudgeTypeClass>; 80 template class TFixedIHeapClass<TeamClass>; 81 template class TFixedIHeapClass<TeamClass>; 82 template class TFixedIHeapClass<TeamTypeClass>; 83 template class TFixedIHeapClass<TemplateClass>; 84 template class TFixedIHeapClass<TemplateTypeClass>; 85 template class TFixedIHeapClass<TerrainClass>; 86 template class TFixedIHeapClass<TerrainTypeClass>; 87 template class TFixedIHeapClass<TriggerClass>; 88 template class TFixedIHeapClass<TriggerTypeClass>; 89 template class TFixedIHeapClass<UnitClass>; 90 template class TFixedIHeapClass<UnitTypeClass>; 91 template class TFixedIHeapClass<VesselClass>; 92 template class TFixedIHeapClass<VesselTypeClass>; 93 template class TFixedIHeapClass<WarheadTypeClass>; 94 template class TFixedIHeapClass<WeaponTypeClass>; 95 96 97 /*********************************************************************************************** 98 * FixedHeapClass::FixedHeapClass -- Normal constructor for heap management class. * 99 * * 100 * This is the normal constructor used for the heap manager class. This initializes * 101 * the class but doesn't yet assign actual heap memory to this manager. That is handled * 102 * by the Set_Heap() function. * 103 * * 104 * INPUT: size -- The size of the individual sub-blocks in this heap. This value is * 105 * typically the size of some class or structure. * 106 * * 107 * OUTPUT: none * 108 * * 109 * WARNINGS: The heap must first be assigned a block of memory to manage before it can * 110 * be used. * 111 * * 112 * HISTORY: * 113 * 02/21/1995 JLB : Created. * 114 *=============================================================================================*/ 115 FixedHeapClass::FixedHeapClass(int size) : 116 IsAllocated(false), 117 Size(size), 118 TotalCount(0), 119 ActiveCount(0), 120 Buffer(0) 121 { 122 } 123 124 125 /*********************************************************************************************** 126 * FixedHeapClass::~FixedHeapClass -- Destructor for the heap manager class. * 127 * * 128 * This is the default constructor for the heap manager class. It handles freeing the * 129 * memory assigned to this heap. * 130 * * 131 * INPUT: none * 132 * * 133 * OUTPUT: none * 134 * * 135 * WARNINGS: none * 136 * * 137 * HISTORY: * 138 * 02/21/1995 JLB : Created. * 139 *=============================================================================================*/ 140 FixedHeapClass::~FixedHeapClass(void) 141 { 142 FixedHeapClass::Clear(); 143 } 144 145 146 /*********************************************************************************************** 147 * FixedHeapClass::Set_Heap -- Assigns a memory block for this heap manager. * 148 * * 149 * This routine is used to assign a memory heap to this object. A memory heap so assigned * 150 * will start with all sub-blocks unallocated. After this routine is called, normal * 151 * allocation and freeing may occur. This routine will allocate necessary memory if the * 152 * buffer parameter is NULL. * 153 * * 154 * INPUT: count -- The number of objects that this heap should manage. * 155 * * 156 * buffer -- Pointer to pre-allocated buffer that this manager will use. If this * 157 * parameter is NULL, then memory will be automatically allocated. * 158 * * 159 * OUTPUT: bool; Was the heap successfully initialized? * 160 * * 161 * WARNINGS: none * 162 * * 163 * HISTORY: * 164 * 02/21/1995 JLB : Created. * 165 *=============================================================================================*/ 166 int FixedHeapClass::Set_Heap(int count, void * buffer) 167 { 168 /* 169 ** Clear out the old heap data. 170 */ 171 Clear(); 172 173 /* 174 ** If there is no size to the objects in the heap, then this block memory 175 ** handler can NEVER function. Return with a failure condition. 176 */ 177 if (!Size) return(false); 178 179 /* 180 ** If there is no count specified, then this indicates that the heap should 181 ** be disabled. 182 */ 183 if (!count) return(true); 184 185 /* 186 ** Initialize the free boolean vector and the buffer for the actual 187 ** allocation objects. 188 */ 189 if (FreeFlag.Resize(count)) { 190 if (!buffer) { 191 buffer = new char[count * Size]; 192 if (!buffer) { 193 FreeFlag.Clear(); 194 return(false); 195 } 196 IsAllocated = true; 197 } 198 Buffer = buffer; 199 TotalCount = count; 200 return(true); 201 } 202 return(false); 203 } 204 205 206 /*********************************************************************************************** 207 * FixedHeapClass::Allocate -- Allocate a sub-block from the heap. * 208 * * 209 * Finds the first available sub-block in the heap and returns a pointer to it. The sub- * 210 * block is marked as allocated by this routine. If there are no more sub-blocks * 211 * available, then this routine will return NULL. * 212 * * 213 * INPUT: none * 214 * * 215 * OUTPUT: Returns with a pointer to the newly allocated sub-block. * 216 * * 217 * WARNINGS: none * 218 * * 219 * HISTORY: * 220 * 02/21/1995 JLB : Created. * 221 *=============================================================================================*/ 222 void * FixedHeapClass::Allocate(void) 223 { 224 if (ActiveCount < TotalCount) { 225 int index = FreeFlag.First_False(); 226 227 if (index != -1) { 228 ActiveCount++; 229 FreeFlag[index] = true; 230 return((*this)[index]); 231 } 232 } 233 return(0); 234 } 235 236 237 /*********************************************************************************************** 238 * FixedHeapClass::Free -- Frees a sub-block in the heap. * 239 * * 240 * Use this routine to free a previously allocated sub-block in the heap. * 241 * * 242 * INPUT: pointer -- A pointer to the sub-block to free. This is the same pointer that * 243 * was returned from the Allocate() function. * 244 * * 245 * OUTPUT: bool; Was the deallocation successful? Failure could indicate a pointer that * 246 * doesn't refer to this heap or a null pointer. * 247 * * 248 * WARNINGS: none * 249 * * 250 * HISTORY: * 251 * 02/21/1995 JLB : Created. * 252 *=============================================================================================*/ 253 int FixedHeapClass::Free(void * pointer) 254 { 255 if (pointer && ActiveCount) { 256 int index = ID(pointer); 257 258 if (index < TotalCount) { 259 if (FreeFlag[index]) { 260 ActiveCount--; 261 FreeFlag[index] = false; 262 return(true); 263 } 264 } 265 } 266 return(false); 267 } 268 269 270 /*********************************************************************************************** 271 * FixedHeapClass::ID -- Converts a pointer to a sub-block index number. * 272 * * 273 * Use this routine to convert a pointer (returned by Allocate) into the sub-block * 274 * index number. This index number can be used as a form of identifier for the block. * 275 * * 276 * INPUT: pointer -- A pointer to the sub-block to convert into an ID number. * 277 * * 278 * OUTPUT: Returns with the index (ID) number for the sub-block specified. This number will * 279 * range between 0 and the sub-block max -1. If -1 is returned, then the pointer * 280 * was invalid. * 281 * * 282 * WARNINGS: none * 283 * * 284 * HISTORY: * 285 * 02/21/1995 JLB : Created. * 286 *=============================================================================================*/ 287 int FixedHeapClass::ID(void const * pointer) const 288 { 289 if (pointer && Size) { 290 return((int)(((char *)pointer - (char *)Buffer) / Size)); 291 } 292 return(-1); 293 } 294 295 296 /*********************************************************************************************** 297 * FixedHeapClass::Clear -- Clears (and frees) the heap manager memory. * 298 * * 299 * This routine is used to bring the heap manager back into a non-functioning state. All * 300 * memory allocated by this manager is freed. Any previous pointers to allocated blocks * 301 * from this heap are now invalid. * 302 * * 303 * INPUT: none * 304 * * 305 * OUTPUT: none * 306 * * 307 * WARNINGS: none * 308 * * 309 * HISTORY: * 310 * 02/21/1995 JLB : Created. * 311 *=============================================================================================*/ 312 void FixedHeapClass::Clear(void) 313 { 314 /* 315 ** Free the old buffer (if present). 316 */ 317 if (Buffer && IsAllocated) { 318 delete[] Buffer; 319 } 320 Buffer = 0; 321 IsAllocated = false; 322 ActiveCount = 0; 323 TotalCount = 0; 324 FreeFlag.Clear(); 325 } 326 327 328 /*********************************************************************************************** 329 * FixedHeapClass::Free_All -- Frees all objects in the fixed heap. * 330 * * 331 * This routine will free all previously allocated objects out of the heap. Use this * 332 * routine to ensure that the heap is empty. * 333 * * 334 * INPUT: none * 335 * * 336 * OUTPUT: Was the heap successfully cleared of all objects? * 337 * * 338 * WARNINGS: none * 339 * * 340 * HISTORY: * 341 * 05/22/1995 JLB : Created. * 342 *=============================================================================================*/ 343 int FixedHeapClass::Free_All(void) 344 { 345 ActiveCount = 0; 346 FreeFlag.Reset(); 347 return(true); 348 } 349 350 351 ///////////////////////////////////////////////////////////////////// 352 353 354 /*********************************************************************************************** 355 * FixedIHeapClass::Free_All -- Frees all objects out of the indexed heap. * 356 * * 357 * Use this routine to free all previously allocated objects in the heap. This routine will * 358 * also clear out the allocated object vector as well. * 359 * * 360 * INPUT: none * 361 * * 362 * OUTPUT: Was the heap successfully cleared of objects? * 363 * * 364 * WARNINGS: none * 365 * * 366 * HISTORY: * 367 * 05/22/1995 JLB : Created. * 368 *=============================================================================================*/ 369 int FixedIHeapClass::Free_All(void) 370 { 371 ActivePointers.Delete_All(); 372 return(FixedHeapClass::Free_All()); 373 } 374 375 376 /*********************************************************************************************** 377 * FixedIHeapClass::Clear -- Clears the fixed heap of all entries. * 378 * * 379 * This routine will clear the entire heap. All memory that was allocation, will be freed * 380 * by this routine. After calling this routine, the heap must either be resized or * 381 * a new heap memory block specifically attached, before it can be used again. * 382 * * 383 * INPUT: none * 384 * * 385 * OUTPUT: none * 386 * * 387 * WARNINGS: none * 388 * * 389 * HISTORY: * 390 * 09/21/1995 JLB : Created. * 391 *=============================================================================================*/ 392 void FixedIHeapClass::Clear(void) 393 { 394 FixedHeapClass::Clear(); 395 ActivePointers.Clear(); 396 } 397 398 399 /*********************************************************************************************** 400 * FixedIHeapClass::Set_Heap -- Set the heap to the buffer provided. * 401 * * 402 * This routine will set the heap to use the buffer specified. Use this routine when a * 403 * pre-allocated buffer is to be used for the heap. A heap that is assigned in this * 404 * manner cannot be resized. * 405 * * 406 * INPUT: count -- The number of objects that the buffer pointer can be used to track. * 407 * * 408 * buffer -- Pointer to the buffer to use when keeping track of the objects. * 409 * * 410 * OUTPUT: Was the heap assigned successfully? * 411 * * 412 * WARNINGS: none * 413 * * 414 * HISTORY: * 415 * 09/21/1995 JLB : Created. * 416 *=============================================================================================*/ 417 int FixedIHeapClass::Set_Heap(int count, void * buffer) 418 { 419 Clear(); 420 if (FixedHeapClass::Set_Heap(count, buffer)) { 421 ActivePointers.Resize(count); 422 return(true); 423 } 424 return(false); 425 } 426 427 428 /*********************************************************************************************** 429 * FixedIHeapClass::Allocate -- Allocate an object from the heap. * 430 * * 431 * This routine will allocate an object located in the heap. If no free object space * 432 * could be found, then NULL is returned. * 433 * * 434 * INPUT: none * 435 * * 436 * OUTPUT: Returns with a pointer to the allocated object memory block. * 437 * * 438 * WARNINGS: none * 439 * * 440 * HISTORY: * 441 * 09/21/1995 JLB : Created. * 442 *=============================================================================================*/ 443 void * FixedIHeapClass::Allocate(void) 444 { 445 void * ptr = FixedHeapClass::Allocate(); 446 if (ptr) { 447 ActivePointers.Add(ptr); 448 memset (ptr, 0, Size); 449 } 450 return(ptr); 451 } 452 453 454 /*********************************************************************************************** 455 * FixedIHeapClass::Free -- Frees an object in the heap. * 456 * * 457 * This routine is used to free an object in the heap. Freeing is accomplished by marking * 458 * the object's memory as free to be reallocated. The object is also removed from the * 459 * allocated object pointer vector. * 460 * * 461 * INPUT: pointer -- Pointer to the object that is to be removed from the heap. * 462 * * 463 * OUTPUT: none * 464 * * 465 * WARNINGS: none * 466 * * 467 * HISTORY: * 468 * 02/21/1995 JLB : Created. * 469 *=============================================================================================*/ 470 int FixedIHeapClass::Free(void * pointer) 471 { 472 if (FixedHeapClass::Free(pointer)) { 473 ActivePointers.Delete(pointer); 474 } 475 return(false); 476 } 477 478 479 /*********************************************************************************************** 480 * FixedIHeapClass::Logical_ID -- Fetches the logical ID number. * 481 * * 482 * Ths logical ID number of a memory block is the index number of the block as if the * 483 * heap consisted only of valid allocated blocks. This knowledge comes in handy when * 484 * the real index number must be anticipated before a memory block packing process. * 485 * * 486 * INPUT: pointer -- Pointer to an allocated block in the heap. * 487 * * 488 * OUTPUT: Returns with the logical index number of this block. The number returned must not * 489 * be used as a regular index into the heap until such time as the heap has been * 490 * compacted (by some means or another) without modifying the block order. * 491 * * 492 * WARNINGS: Runs in linear time. * 493 * * 494 * HISTORY: * 495 * 05/06/1996 JLB : Created. * 496 *=============================================================================================*/ 497 int FixedIHeapClass::Logical_ID(void const * pointer) const 498 { 499 if (pointer != NULL) { 500 for (int index = 0; index < Count(); index++) { 501 if (Active_Ptr(index) == pointer) { 502 return(index); 503 } 504 } 505 } 506 return(-1); 507 } 508 509 510 /*********************************************************************************************** 511 * TFixedIHeapClass::Save -- Saves all active objects * 512 * * 513 * INPUT: file file to write to * 514 * * 515 * OUTPUT: true = OK, false = error * 516 * * 517 * WARNINGS: none * 518 * * 519 * HISTORY: * 520 * 03/15/1995 BRR : Created. * 521 * 03/12/1996 JLB : Uses in-place new operator for virtual table control. * 522 *=============================================================================================*/ 523 template<class T> 524 int TFixedIHeapClass<T>::Save(Pipe & file) const 525 { 526 /* 527 ** Save the number of instances of this class 528 */ 529 file.Put(&ActiveCount, sizeof(ActiveCount)); 530 531 /* 532 ** Save each instance of this class 533 */ 534 for (int i = 0; i < ActiveCount; i++) { 535 536 /* 537 ** Save the array index of the object, so it can be loaded back into the 538 ** same array location (so TARGET translations will work) 539 */ 540 int idx = ID(Ptr(i)); 541 file.Put(&idx, sizeof(idx)); 542 543 /* 544 ** Save the object itself 545 */ 546 file.Put(Ptr(i), sizeof(T)); 547 } 548 549 return(true); 550 } 551 552 553 /*********************************************************************************************** 554 * TFixedIHeapClass::Load -- Loads all active objects * 555 * * 556 * INPUT: file file to read from * 557 * * 558 * OUTPUT: true = OK, false = error * 559 * * 560 * WARNINGS: none * 561 * * 562 * HISTORY: * 563 * 03/15/1995 BRR : Created. * 564 *=============================================================================================*/ 565 template<class T> 566 int TFixedIHeapClass<T>::Load(Straw & file) 567 { 568 int i; // loop counter 569 int idx; // object index 570 T * ptr; // object pointer 571 int a_count; 572 573 /* 574 ** Read the number of instances of this class 575 */ 576 if (file.Get(&a_count, sizeof(a_count)) != sizeof(a_count)) { 577 return(false); 578 } 579 580 /* 581 ** Error if more objects than we can hold 582 */ 583 if (a_count > TotalCount) { 584 return(false); 585 } 586 587 /* 588 ** Read each class instance 589 */ 590 for (i = 0; i < a_count; i++) { 591 /* 592 ** Read the object's array index 593 */ 594 if (file.Get(&idx, sizeof(idx)) != sizeof(idx)) { 595 return(false); 596 } 597 598 /* 599 ** Get a pointer to the object, activate that object 600 */ 601 ptr = (T *)(*this)[idx]; 602 FreeFlag[idx] = true; 603 ActiveCount++; 604 ActivePointers.Add(ptr); 605 606 /* 607 ** Load the object 608 */ 609 file.Get(ptr, sizeof(T)); 610 new(ptr) T(NoInitClass()); 611 // if (!ptr->Load(file)) { 612 // return(false); 613 // } 614 } 615 616 return(true); 617 } 618 619 620 /*********************************************************************************************** 621 * TFixedIHeapClass::Code_Pointers -- codes pointers for every object, to prepare for save * 622 * * 623 * INPUT: file file to read from * 624 * * 625 * OUTPUT: true = OK, false = error * 626 * * 627 * WARNINGS: none * 628 * * 629 * HISTORY: * 630 * 03/15/1995 BRR : Created. * 631 *=============================================================================================*/ 632 template<class T> 633 void TFixedIHeapClass<T>::Code_Pointers(void) 634 { 635 int i; 636 637 for (i = 0; i < ActiveCount; i++) { 638 Ptr(i)->Code_Pointers(); 639 } 640 } 641 642 643 /*********************************************************************************************** 644 * TFixedIHeapClass::Decode_Pointers -- Decodes all object pointers, for after loading * 645 * * 646 * INPUT: file file to read from * 647 * * 648 * OUTPUT: true = OK, false = error * 649 * * 650 * WARNINGS: none * 651 * * 652 * HISTORY: * 653 * 03/15/1995 BRR : Created. * 654 *=============================================================================================*/ 655 template<class T> 656 void TFixedIHeapClass<T>::Decode_Pointers(void) 657 { 658 int i; 659 660 for (i = 0; i < ActiveCount; i++) { 661 Ptr(i)->Decode_Pointers(); 662 } 663 }