SEARCH.H (34505B)
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/SEARCH.H 1 3/03/97 10:25a 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 : SEARCH.H * 24 * * 25 * Programmer : Joe L. Bostic * 26 * * 27 * Start Date : 11/02/96 * 28 * * 29 * Last Update : November 2, 1996 [JLB] * 30 * * 31 *---------------------------------------------------------------------------------------------* 32 * Functions: * 33 * IndexClass<T>::Add_Index -- Add element to index tracking system. * 34 * IndexClass<T>::Clear -- Clear index handler to empty state. * 35 * IndexClass<T>::Count -- Fetch the number of index entries recorded. * 36 * IndexClass<T>::Fetch_Index -- Fetch data from specified index. * 37 * IndexClass<T>::Increase_Table_Size -- Increase the internal index table capacity. * 38 * IndexClass<T>::IndexClass -- Constructor for index handler. * 39 * IndexClass<T>::Invalidate_Archive -- Invalidate the archive pointer. * 40 * IndexClass<T>::Is_Archive_Same -- Checks to see if archive pointer is same as index. * 41 * IndexClass<T>::Is_Present -- Checks for presense of index entry. * 42 * IndexClass<T>::Remove_Index -- Find matching index and remove it from system. * 43 * IndexClass<T>::Search_For_Node -- Perform a search for the specified node ID * 44 * IndexClass<T>::Set_Archive -- Records the node pointer into the archive. * 45 * IndexClass<T>::Sort_Nodes -- Sorts nodes in preparation for a binary search. * 46 * IndexClass<T>::~IndexClass -- Destructor for index handler object. * 47 * compfunc -- Support function for bsearch and bsort. * 48 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ 49 50 51 #ifndef SEARCH_H 52 #define SEARCH_H 53 54 /* 55 ** The "bool" integral type was defined by the C++ committee in 56 ** November of '94. Until the compiler supports this, use the following 57 ** definition. 58 */ 59 #ifndef __BORLANDC__ 60 #ifndef TRUE_FALSE_DEFINED 61 #define TRUE_FALSE_DEFINED 62 enum {false=0,true=1}; 63 typedef int bool; 64 #endif 65 #endif 66 67 #ifndef __BORLANDC__ 68 #define _USERENTRY 69 #endif 70 71 /* 72 ** This class is used to create and maintain an index. It does this by assigning a unique 73 ** identifier number to the type objects that it is indexing. The regular binary sort and search 74 ** function are used for speedy index retreival. Typical use of this would be to index pointers to 75 ** normal data objects, but it can be used to hold the data objects themselves. Keep in mind that 76 ** the data object "T" is copied around by this routine in the internal tables so not only must 77 ** it have a valid copy constructor, it must also be efficient. The internal algorithm will 78 ** create an arbitrary number of default constructed objects of type "T". Make sure it has a 79 ** default constructor that is effecient. The constructor need not perform any actual 80 ** initialization since this class has prior knowledge about the legality of these temporary 81 ** objects and doesn't use them until after the copy constructor is used to initialize them. 82 */ 83 84 template<class T> 85 class IndexClass 86 { 87 public: 88 IndexClass(void); 89 ~IndexClass(void); 90 91 /* 92 ** Add element to index table. 93 */ 94 bool Add_Index(int id, T data); 95 96 /* 97 ** Removes an index entry from the index table. 98 */ 99 bool Remove_Index(int id); 100 101 /* 102 ** Check to see if index is present. 103 */ 104 bool Is_Present(int id) const; 105 106 /* 107 ** Fetch number of indexes in the table. 108 */ 109 int Count(void) const; 110 111 /* 112 ** Actually a fetch an index data element from the table. 113 */ 114 T Fetch_Index(int id) const; 115 116 /* 117 ** Clear out the index table to null (empty) state. 118 */ 119 void Clear(void); 120 121 private: 122 /* 123 ** This node object is used to keep track of the connection between the data 124 ** object and the index identifier number. 125 */ 126 struct NodeElement { 127 int ID; // ID number (must be first element in this structure). 128 T Data; // Data element assigned to this ID number. 129 }; 130 131 /* 132 ** This is the pointer to the allocated index table. It contains all valid nodes in 133 ** a sorted order. 134 */ 135 NodeElement * IndexTable; 136 137 /* 138 ** This records the number of valid nodes within the index table. 139 */ 140 int IndexCount; 141 142 /* 143 ** The total size (in nodes) of the index table is recorded here. If adding a node 144 ** would cause the index count to exceed this value, the index table must be resized 145 ** to make room. 146 */ 147 int IndexSize; 148 149 /* 150 ** If the index table is sorted and ready for searching, this flag will be true. Sorting 151 ** of the table only occurs when absolutely necessary. 152 */ 153 bool IsSorted; 154 155 /* 156 ** This records a pointer to the last element found by the Is_Present() function. Using 157 ** this last recorded value can allow quick fetches of data whenever possible. 158 */ 159 NodeElement const * Archive; 160 161 //------------------------------------------------------------------------------------- 162 IndexClass(IndexClass const & rvalue); 163 IndexClass * operator = (IndexClass const & rvalue); 164 165 /* 166 ** Increase size of internal index table by amount specified. 167 */ 168 bool Increase_Table_Size(int amount); 169 170 /* 171 ** Check if archive pointer is the same as that requested. 172 */ 173 bool Is_Archive_Same(int id) const; 174 175 /* 176 ** Invalidate the archive pointer. 177 */ 178 void Invalidate_Archive(void); 179 180 /* 181 ** Set archive to specified value. 182 */ 183 void Set_Archive(NodeElement const * node); 184 185 /* 186 ** Search for the node in the index table. 187 */ 188 NodeElement const * Search_For_Node(int id) const; 189 190 static int _USERENTRY search_compfunc(void const * ptr, void const * ptr2); 191 }; 192 193 194 /*********************************************************************************************** 195 * IndexClass<T>::IndexClass -- Constructor for index handler. * 196 * * 197 * This constructs an empty index handler. * 198 * * 199 * INPUT: none * 200 * * 201 * OUTPUT: none * 202 * * 203 * WARNINGS: none * 204 * * 205 * HISTORY: * 206 * 11/02/1996 JLB : Created. * 207 *=============================================================================================*/ 208 template<class T> 209 IndexClass<T>::IndexClass(void) : 210 IndexTable(0), 211 IndexCount(0), 212 IndexSize(0), 213 IsSorted(false), 214 Archive(0) 215 { 216 Invalidate_Archive(); 217 } 218 219 220 /*********************************************************************************************** 221 * IndexClass<T>::~IndexClass -- Destructor for index handler object. * 222 * * 223 * This will destruct and free any resources managed by this index handler. * 224 * * 225 * INPUT: none * 226 * * 227 * OUTPUT: none * 228 * * 229 * WARNINGS: none * 230 * * 231 * HISTORY: * 232 * 11/02/1996 JLB : Created. * 233 *=============================================================================================*/ 234 template<class T> 235 IndexClass<T>::~IndexClass(void) 236 { 237 Clear(); 238 } 239 240 241 /*********************************************************************************************** 242 * IndexClass<T>::Clear -- Clear index handler to empty state. * 243 * * 244 * This routine will free all internal resources and bring the index handler into a * 245 * known empty state. After this routine, the index handler is free to be reused. * 246 * * 247 * INPUT: none * 248 * * 249 * OUTPUT: none * 250 * * 251 * WARNINGS: none * 252 * * 253 * HISTORY: * 254 * 11/02/1996 JLB : Created. * 255 *=============================================================================================*/ 256 template<class T> 257 void IndexClass<T>::Clear(void) 258 { 259 delete [] IndexTable; 260 IndexTable = 0; 261 IndexCount = 0; 262 IndexSize = 0; 263 IsSorted = false; 264 Invalidate_Archive(); 265 } 266 267 268 /*********************************************************************************************** 269 * IndexClass<T>::Increase_Table_Size -- Increase the internal index table capacity. * 270 * * 271 * This helper function will increase the capacity of the internal index table without * 272 * performing any alterations to the index data. Use this routine prior to adding a new * 273 * element if the existing capacity is insufficient. * 274 * * 275 * INPUT: amount -- The number of index element spaces to add to its capacity. * 276 * * 277 * OUTPUT: bool; Was the internal capacity increased without error? * 278 * * 279 * WARNINGS: If there is insufficient RAM, then this routine will fail. * 280 * * 281 * HISTORY: * 282 * 11/02/1996 JLB : Created. * 283 *=============================================================================================*/ 284 template<class T> 285 bool IndexClass<T>::Increase_Table_Size(int amount) 286 { 287 /* 288 ** Check size increase parameter for legality. 289 */ 290 if (amount < 0) return(false); 291 292 NodeElement * table = new NodeElement[IndexSize + amount]; 293 if (table != NULL) { 294 295 /* 296 ** Copy all valid nodes into the new table. 297 */ 298 for (int index = 0; index < IndexCount; index++) { 299 table[index] = IndexTable[index]; 300 } 301 302 /* 303 ** Make the new table the current one (and delete the old one). 304 */ 305 delete [] IndexTable; 306 IndexTable = table; 307 IndexSize += amount; 308 Invalidate_Archive(); 309 310 /* 311 ** Return with success flag. 312 */ 313 return(true); 314 } 315 316 /* 317 ** Failure to allocate the memory results in a failure to increase 318 ** the size of the index table. 319 */ 320 return(false); 321 } 322 323 324 /*********************************************************************************************** 325 * IndexClass<T>::Count -- Fetch the number of index entries recorded. * 326 * * 327 * This will return the quantity of index entries that have been recored by this index * 328 * handler. * 329 * * 330 * INPUT: none * 331 * * 332 * OUTPUT: Returns with number of recored indecies present. * 333 * * 334 * WARNINGS: none * 335 * * 336 * HISTORY: * 337 * 11/02/1996 JLB : Created. * 338 *=============================================================================================*/ 339 template<class T> 340 int IndexClass<T>::Count(void) const 341 { 342 return(IndexCount); 343 } 344 345 346 /*********************************************************************************************** 347 * IndexClass<T>::Is_Present -- Checks for presense of index entry. * 348 * * 349 * This routine will scan for the specified index entry. If it was found, then 'true' is * 350 * returned. * 351 * * 352 * INPUT: id -- The index ID to search for. * 353 * * 354 * OUTPUT: bool; Was the index entry found in this index handler object? * 355 * * 356 * WARNINGS: none * 357 * * 358 * HISTORY: * 359 * 11/02/1996 JLB : Created. * 360 *=============================================================================================*/ 361 template<class T> 362 bool IndexClass<T>::Is_Present(int id) const 363 { 364 /* 365 ** If there are no data elements in the index table, then it can 366 ** never find the specified index. Check for and return failure 367 ** in this case. 368 */ 369 if (IndexCount == 0) { 370 return(false); 371 } 372 373 /* 374 ** Check to see if this same index element was previously searched for. If 375 ** so and it was previously found, then there is no need to search for it 376 ** again -- just return true. 377 */ 378 if (Is_Archive_Same(id)) { 379 return(true); 380 } 381 382 /* 383 ** Perform a binary search on the index nodes in order to look for a 384 ** matching index value. 385 */ 386 NodeElement const * nodeptr = Search_For_Node(id); 387 388 /* 389 ** If a matching index was found, then record it for future reference and return success. 390 */ 391 if (nodeptr != 0) { 392 ((IndexClass<T> *)this)->Set_Archive(nodeptr); 393 return(true); 394 } 395 396 /* 397 ** Could not find element so return failure condition. 398 */ 399 return(false); 400 } 401 402 403 /*********************************************************************************************** 404 * IndexClass<T>::Fetch_Index -- Fetch data from specified index. * 405 * * 406 * This routine will find the specified index and return the data value associated with it. * 407 * * 408 * INPUT: id -- The index ID to search for. * 409 * * 410 * OUTPUT: Returns with the data value associated with the index value. * 411 * * 412 * WARNINGS: This routine presumes that the index exists. If it doesn't exist, then the * 413 * default constructed object "T" is returned instead. To avoid this problem, * 414 * always verfiy the existance of the index by calling Is_Present() first. * 415 * * 416 * HISTORY: * 417 * 11/02/1996 JLB : Created. * 418 *=============================================================================================*/ 419 template<class T> 420 T IndexClass<T>::Fetch_Index(int id) const 421 { 422 if (Is_Present(id)) { 423 424 /* 425 ** Count on the fact that the archive pointer is always valid after a call to Is_Present 426 ** that returns "true". 427 */ 428 return(Archive->Data); 429 } 430 return(T()); 431 } 432 433 434 /*********************************************************************************************** 435 * IndexClass<T>::Is_Archive_Same -- Checks to see if archive pointer is same as index. * 436 * * 437 * This routine compares the specified index ID with the previously recorded index archive * 438 * pointer in order to determine if they match. * 439 * * 440 * INPUT: id -- The index ID to compare to the archive index object pointer. * 441 * * 442 * OUTPUT: bool; Does the specified index match the archive pointer? * 443 * * 444 * WARNINGS: none * 445 * * 446 * HISTORY: * 447 * 11/02/1996 JLB : Created. * 448 *=============================================================================================*/ 449 template<class T> 450 bool IndexClass<T>::Is_Archive_Same(int id) const 451 { 452 if (Archive != 0 && Archive->ID == id) { 453 return(true); 454 } 455 return(false); 456 } 457 458 459 /*********************************************************************************************** 460 * IndexClass<T>::Invalidate_Archive -- Invalidate the archive pointer. * 461 * * 462 * This routine will set the archive pointer to an invalid state. This must be performed * 463 * if ever the archive pointer would become illegal (such as when the element it refers to * 464 * is deleted). * 465 * * 466 * INPUT: none * 467 * * 468 * OUTPUT: none * 469 * * 470 * WARNINGS: none * 471 * * 472 * HISTORY: * 473 * 11/02/1996 JLB : Created. * 474 *=============================================================================================*/ 475 template<class T> 476 void IndexClass<T>::Invalidate_Archive(void) 477 { 478 Archive = 0; 479 } 480 481 482 /*********************************************************************************************** 483 * IndexClass<T>::Set_Archive -- Records the node pointer into the archive. * 484 * * 485 * This routine records the specified node pointer. Use this routine when there is a * 486 * good chance that the specified node will be requested in the immediate future. * 487 * * 488 * INPUT: node -- Pointer to the node to assign to the archive. * 489 * * 490 * OUTPUT: none * 491 * * 492 * WARNINGS: none * 493 * * 494 * HISTORY: * 495 * 11/02/1996 JLB : Created. * 496 *=============================================================================================*/ 497 template<class T> 498 void IndexClass<T>::Set_Archive(NodeElement const * node) 499 { 500 Archive = node; 501 } 502 503 504 /*********************************************************************************************** 505 * IndexClass<T>::Add_Index -- Add element to index tracking system. * 506 * * 507 * This routine will record the index information into this index manager object. It * 508 * associates the index number with the data specified. The data is copied to an internal * 509 * storage location. * 510 * * 511 * INPUT: id -- The ID number to associate with the data. * 512 * * 513 * data -- The data to store. * 514 * * 515 * OUTPUT: bool; Was the element added without error? Failure indicates that RAM has been * 516 * exhausted. * 517 * * 518 * WARNINGS: The data is COPIED to internal storage. This means that the data object must * 519 * have a functional and efficient copy constructor and assignment operator. * 520 * * 521 * HISTORY: * 522 * 11/02/1996 JLB : Created. * 523 *=============================================================================================*/ 524 template<class T> 525 bool IndexClass<T>::Add_Index(int id, T data) 526 { 527 /* 528 ** Ensure that there is enough room to add this index. If not, then increase the 529 ** capacity of the internal index table. 530 */ 531 if (IndexCount + 1 > IndexSize) { 532 if (!Increase_Table_Size(IndexSize == 0 ? 10 : IndexSize)) { 533 534 /* 535 ** Failure to increase the size of the index table means failure to add 536 ** the index element. 537 */ 538 return(false); 539 } 540 } 541 542 /* 543 ** Add the data to the end of the index data and then sort the index table. 544 */ 545 IndexTable[IndexCount].ID = id; 546 IndexTable[IndexCount].Data = data; 547 IndexCount++; 548 IsSorted = false; 549 550 return(true); 551 } 552 553 554 /*********************************************************************************************** 555 * IndexClass<T>::Remove_Index -- Find matching index and remove it from system. * 556 * * 557 * This will scan through the previously added index elements and if a match was found, it * 558 * will be removed. * 559 * * 560 * INPUT: id -- The index ID to search for and remove. * 561 * * 562 * OUTPUT: bool; Was the index element found and removed? * 563 * * 564 * WARNINGS: none * 565 * * 566 * HISTORY: * 567 * 11/02/1996 JLB : Created. * 568 *=============================================================================================*/ 569 template<class T> 570 bool IndexClass<T>::Remove_Index(int id) 571 { 572 /* 573 ** Find the array index into the table that matches the specified id value. 574 */ 575 int found_index = -1; 576 for (int index = 0; index < IndexCount; index++) { 577 if (IndexTable[index].ID == id) { 578 found_index = index; 579 break; 580 } 581 } 582 583 /* 584 ** If the array index was found, then copy all higher index entries 585 ** downward to fill the vacated location. We cannot use memcpy here because the type 586 ** object may not support raw copies. C++ defines the assignment operator to deal 587 ** with this, so that is what we use. 588 */ 589 if (found_index != -1) { 590 591 for (int index = found_index+1; index < IndexCount; index++) { 592 IndexTable[index-1] = IndexTable[index]; 593 } 594 IndexCount--; 595 596 NodeElement fake; 597 fake.ID = 0; 598 fake.Data = T(); 599 IndexTable[IndexCount] = fake; // zap last (now unused) element 600 601 Invalidate_Archive(); 602 return(true); 603 } 604 605 return(false); 606 } 607 608 609 /*********************************************************************************************** 610 * compfunc -- Support function for bsearch and bsort. * 611 * * 612 * This compare function presumes that its parameters are pointing to NodeElements and that * 613 * the first "int" in the node is the index ID number to be used for comparison. * 614 * * 615 * INPUT: ptr1 -- Pointer to first node. * 616 * * 617 * ptr2 -- Pointer to second node. * 618 * * 619 * OUTPUT: Returns with the comparision value between the two nodes. * 620 * * 621 * WARNINGS: This is highly dependant upon the layout of the NodeElement structure. * 622 * * 623 * HISTORY: * 624 * 11/02/1996 JLB : Created. * 625 *=============================================================================================*/ 626 template<class T> 627 int _USERENTRY IndexClass<T>::search_compfunc(void const * ptr1, void const * ptr2) 628 { 629 if (*(int const *)ptr1 == *(int const *)ptr2) { 630 return(0); 631 } 632 if (*(int const *)ptr1 < *(int const *)ptr2) { 633 return(-1); 634 } 635 return(1); 636 } 637 638 639 /*********************************************************************************************** 640 * IndexClass<T>::Search_For_Node -- Perform a search for the specified node ID * 641 * * 642 * This routine will perform a binary search on the previously recorded index values and * 643 * if a match was found, it will return a pointer to the NodeElement. * 644 * * 645 * INPUT: id -- The index ID to search for. * 646 * * 647 * OUTPUT: Returns with a pointer to the NodeElement that matches the index ID specified. If * 648 * no matching index could be found, then NULL is returned. * 649 * * 650 * WARNINGS: none * 651 * * 652 * HISTORY: * 653 * 11/02/1996 JLB : Created. * 654 *=============================================================================================*/ 655 template<class T> 656 typename IndexClass<T>::NodeElement const * IndexClass<T>::Search_For_Node(int id) const 657 { 658 /* 659 ** If there are no elements in the list, then it certainly can't find any matches. 660 */ 661 if (IndexCount == 0) { 662 return(0); 663 } 664 665 /* 666 ** If the list has not yet been sorted, then do so now. Binary searching requires 667 ** the list to be sorted. 668 */ 669 if (!IsSorted) { 670 qsort(&IndexTable[0], IndexCount, sizeof(IndexTable[0]), search_compfunc); 671 ((IndexClass<T> *)this)->Invalidate_Archive(); 672 ((IndexClass<T> *)this)->IsSorted = true; 673 } 674 675 /* 676 ** This list is sorted and ready to perform a binary search upon it. 677 */ 678 NodeElement node; 679 node.ID = id; 680 return((NodeElement const *)bsearch(&node, &IndexTable[0], IndexCount, sizeof(IndexTable[0]), search_compfunc)); 681 } 682 683 684 #endif 685 686