QUEUE.H (16508B)
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/QUEUE.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 : QUEUE.H * 24 * * 25 * Programmer : Joe L. Bostic * 26 * * 27 * Start Date : 12/08/94 * 28 * * 29 * Last Update : December 9, 1994 [JLB] * 30 * * 31 *---------------------------------------------------------------------------------------------* 32 * Functions: * 33 * QueueClass<T,size>::Add -- Add object to queue. * 34 * QueueClass<T,size>::First -- Fetches reference to first object in list. * 35 * QueueClass<T,size>::Init -- Initializes queue to empty state. * 36 * QueueClass<T,size>::Next -- Throws out the head of the line. * 37 * QueueClass<T,size>::operator[] -- Fetches reference to sub object in queue. * 38 * QueueClass<T,size>::QueueClass -- Default constructor for QueueClass objects. * 39 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ 40 41 #ifndef QUEUE_H 42 #define QUEUE_H 43 44 #include "mission.h" 45 #include "target.h" 46 #include "defines.h" 47 48 //#pragma warn -inl 49 50 /* 51 ** This class implements a classic FIFO queue (also known as - standing in line). Objects 52 ** are added to the end (tail) of the line. Objects are removed from the start (first) of 53 ** the line. A keyboard buffer is a good example of a common computer use of a queue. There 54 ** is no provision for "taking cuts" or leaving the line once an object has been added. 55 ** 56 ** The implementation uses a circular list of objects. This allows adding and deleting of 57 ** elements without any maintenance moves of remaining objects that would otherwise be 58 ** necessary in a simple array storage method. A side effect of this means that accessing the 59 ** internal array directly is not allowed. Supporting functions are provided for this purpose. 60 ** 61 ** WARNING WARNING WARNING WARNING!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 62 ** The size parameter MUST be an exact power of two (2, 4, 8, 16, etc.) otherwise the internal 63 ** indexing algorithm will fail. 64 */ 65 template<class T, int size> 66 class QueueClass 67 { 68 public: 69 /* 70 ** This is the count of the number of objects in the queue. If this count is zero, 71 ** then the operator[], First(), and Next() functions are undefined. Check this 72 ** value BEFORE calling these functions. 73 */ 74 const int Count; 75 76 //-------------- Functions -------------------- 77 QueueClass(void); // Default constructor. 78 79 /* 80 ** The bracket subscript operator functions similarly to the way a normal subscript 81 ** operator works except that entry [0] matches the first-in-line and entry 82 ** [Count-1] matches the last-in-line. This is ensured regardless of the actual position 83 ** of the object in the circular internal list. 84 */ 85 T & operator[](int); 86 87 /* 88 ** This function will return a reference to the "head of the line" object. 89 */ 90 T & First(void); 91 92 /* 93 ** This function clears the list of objects. 94 */ 95 void Init(void); 96 97 /* 98 ** This function discards the head-of-the-line object and advances all the remaining 99 ** objects up by one. Mnemonic: Imagine a broadway audition and the director yells 100 ** "NEXT!" 101 */ 102 int Next(void); 103 104 /* 105 ** This will add an object to the tail of the line. If there is no more room to add 106 ** the object, then false will be returned. 107 */ 108 int Add(T const &); 109 110 int Get_Head(void); 111 int Get_Tail(void); 112 T * Get_Array(void); 113 114 private: 115 int Head; // Index of element in list the longest. 116 int Tail; // Index where next new addition will go. 117 118 T Array[size]; // Raw array of objects. 119 }; 120 121 122 /*********************************************************************************************** 123 * QueueClass<T,size>::QueueClass -- Default constructor for QueueClass objects. * 124 * * 125 * This default constructor for QueueClass objects initializes the queue to an empty * 126 * state. * 127 * * 128 * INPUT: none * 129 * * 130 * OUTPUT: none * 131 * * 132 * WARNINGS: none * 133 * * 134 * HISTORY: * 135 * 12/09/1994 JLB : Created. * 136 *=============================================================================================*/ 137 template<class T, int size> 138 inline QueueClass<T,size>::QueueClass(void) : Count(0) 139 { 140 Init(); 141 } 142 143 144 /*********************************************************************************************** 145 * QueueClass<T,size>::Init -- Initializes queue to empty state. * 146 * * 147 * This function resets the queue to an empty state. * 148 * * 149 * INPUT: none * 150 * * 151 * OUTPUT: none * 152 * * 153 * WARNINGS: none * 154 * * 155 * HISTORY: * 156 * 12/09/1994 JLB : Created. * 157 *=============================================================================================*/ 158 template<class T, int size> 159 inline void QueueClass<T,size>::Init(void) 160 { 161 ((int &)Count) = 0; 162 Head = 0; 163 Tail = 0; 164 } 165 166 167 /*********************************************************************************************** 168 * QueueClass<T,size>::Add -- Add object to queue. * 169 * * 170 * This function is used to add an object to the tail of the line. If the queue cannot * 171 * accept any more entries, then the object won't be added and false will be returned. * 172 * * 173 * INPUT: object -- The object that is to be added to the queue. * 174 * * 175 * OUTPUT: bool; Was the object added successfully? * 176 * * 177 * WARNINGS: If the queue is full, then the object won't be added. Be sure to check for this.* 178 * * 179 * HISTORY: * 180 * 12/09/1994 JLB : Created. * 181 *=============================================================================================*/ 182 template<class T, int size> 183 inline int QueueClass<T,size>::Add(T const &q) 184 { 185 if (Count < size) { 186 Array[Tail] = q; 187 Tail = (Tail + 1) & (size-1); 188 ((int &)Count) = Count + 1; 189 return(true); 190 } 191 return (false); 192 } 193 194 195 /*********************************************************************************************** 196 * QueueClass<T,size>::Next -- Throws out the head of the line. * 197 * * 198 * This routine is used to discard the object at the head of the line. All remaining * 199 * objects "move up" one. No actual movement occurs, merely the index is adjusted, but * 200 * the affect is that the next oldest object in the queue will now be returned with the * 201 * next call to the First() function. * 202 * * 203 * INPUT: none * 204 * * 205 * OUTPUT: Returns the number of object remaining in the queue. * 206 * * 207 * WARNINGS: none * 208 * * 209 * HISTORY: * 210 * 12/09/1994 JLB : Created. * 211 *=============================================================================================*/ 212 template<class T, int size> 213 inline int QueueClass<T,size>::Next(void) 214 { 215 if (Count) { 216 Head = (Head + 1) & (size-1); 217 ((int &)Count) = Count - 1; 218 } 219 return (Count); 220 } 221 222 223 /*********************************************************************************************** 224 * QueueClass<T,size>::operator[] -- Fetches reference to sub object in queue. * 225 * * 226 * Use this routine to examine individual objects within the queue. The oldest object in * 227 * the queue is referenced by an index value of zero. The newest object in the queue is * 228 * referenced by a value of Count-1. If there are no objects in the queue, then this * 229 * operator is undefined. Although this operator allows examination of the queue, there is * 230 * no corresponding ability to insert or delete objects from the middle of the queue. * 231 * * 232 * INPUT: index -- The index into the queue of objects. Valid values range from zero to * 233 * Count-1. All other values return an undefined reference! * 234 * * 235 * OUTPUT: Returns with a reference to the object indicated by the index. * 236 * * 237 * WARNINGS: Check to make sure that Count is not zero before using this operator. Failure * 238 * to do so will return a reference to an undefined object. * 239 * * 240 * HISTORY: * 241 * 12/09/1994 JLB : Created. * 242 *=============================================================================================*/ 243 template<class T, int size> 244 inline T & QueueClass<T,size>::operator[](int index) 245 { 246 return Array[(Head + index) & (size-1)]; 247 } 248 249 250 /*********************************************************************************************** 251 * QueueClass<T,size>::First -- Fetches reference to first object in list. * 252 * * 253 * This routine is used to fetch the first object in the list (head of the line). This * 254 * object is the oldest in the list. Typical use of this function is to get and process * 255 * the first object so that it may be discarded with the Next() function in order to bring * 256 * subsequent objects to the first position. * 257 * * 258 * INPUT: none * 259 * * 260 * OUTPUT: Returns with a reference to the oldest object in the queue. * 261 * * 262 * WARNINGS: If there are no objects in the queue, then this function returns an undefined * 263 * reference. Be sure to check Count against zero before calling this function. * 264 * * 265 * HISTORY: * 266 * 12/09/1994 JLB : Created. * 267 *=============================================================================================*/ 268 template<class T, int size> 269 inline T & QueueClass<T,size>::First(void) 270 { 271 return Array[Head]; 272 } 273 274 template<class T, int size> 275 inline int QueueClass<T,size>::Get_Head(void) 276 { 277 return Head; 278 } 279 280 template<class T, int size> 281 inline int QueueClass<T,size>::Get_Tail(void) 282 { 283 return Tail; 284 } 285 286 template<class T, int size> 287 inline T * QueueClass<T,size>::Get_Array(void) 288 { 289 return Array; 290 } 291 292 #endif