QUEUE.H (16408B)
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: F:\projects\c&c\vcs\code\queue.h_v 2.16 16 Oct 1995 16:45:50 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 private: 111 int Head; // Index of element in list the longest. 112 int Tail; // Index where next new addition will go. 113 114 T Array[size]; // Raw array of objects. 115 }; 116 117 118 /*********************************************************************************************** 119 * QueueClass<T,size>::QueueClass -- Default constructor for QueueClass objects. * 120 * * 121 * This default constructor for QueueClass objects initializes the queue to an empty * 122 * state. * 123 * * 124 * INPUT: none * 125 * * 126 * OUTPUT: none * 127 * * 128 * WARNINGS: none * 129 * * 130 * HISTORY: * 131 * 12/09/1994 JLB : Created. * 132 *=============================================================================================*/ 133 template<class T, int size> 134 inline QueueClass<T,size>::QueueClass(void) : Count(0) 135 { 136 Init(); 137 } 138 139 140 /*********************************************************************************************** 141 * QueueClass<T,size>::Init -- Initializes queue to empty state. * 142 * * 143 * This function resets the queue to an empty state. * 144 * * 145 * INPUT: none * 146 * * 147 * OUTPUT: none * 148 * * 149 * WARNINGS: none * 150 * * 151 * HISTORY: * 152 * 12/09/1994 JLB : Created. * 153 *=============================================================================================*/ 154 template<class T, int size> 155 inline void QueueClass<T,size>::Init(void) 156 { 157 ((int &)Count) = 0; 158 Head = 0; 159 Tail = 0; 160 } 161 162 163 /*********************************************************************************************** 164 * QueueClass<T,size>::Add -- Add object to queue. * 165 * * 166 * This function is used to add an object to the tail of the line. If the queue cannot * 167 * accept any more entries, then the object won't be added and false will be returned. * 168 * * 169 * INPUT: object -- The object that is to be added to the queue. * 170 * * 171 * OUTPUT: bool; Was the object added successfully? * 172 * * 173 * WARNINGS: If the queue is full, then the object won't be added. Be sure to check for this.* 174 * * 175 * HISTORY: * 176 * 12/09/1994 JLB : Created. * 177 *=============================================================================================*/ 178 template<class T, int size> 179 inline int QueueClass<T,size>::Add(T const &q) 180 { 181 if (Count < size) { 182 Array[Tail] = q; 183 Tail = (Tail + 1) & (size-1); 184 ((int &)Count) = Count + 1; 185 return(true); 186 } 187 Mono_Printf( "Queue Add failed Count %d size %d tail %d head %d \n", 188 Count, size, Tail, Head ); 189 return (false); 190 } 191 192 193 /*********************************************************************************************** 194 * QueueClass<T,size>::Next -- Throws out the head of the line. * 195 * * 196 * This routine is used to discard the object at the head of the line. All remaining * 197 * objects "move up" one. No actual movement occurs, merely the index is adjusted, but * 198 * the affect is that the next oldest object in the queue will now be returned with the * 199 * next call to the First() function. * 200 * * 201 * INPUT: none * 202 * * 203 * OUTPUT: Returns the number of object remaining in the queue. * 204 * * 205 * WARNINGS: none * 206 * * 207 * HISTORY: * 208 * 12/09/1994 JLB : Created. * 209 *=============================================================================================*/ 210 template<class T, int size> 211 inline int QueueClass<T,size>::Next(void) 212 { 213 if (Count) { 214 Head = (Head + 1) & (size-1); 215 ((int &)Count) = Count - 1; 216 } 217 return (Count); 218 } 219 220 221 /*********************************************************************************************** 222 * QueueClass<T,size>::operator[] -- Fetches reference to sub object in queue. * 223 * * 224 * Use this routine to examine individual objects within the queue. The oldest object in * 225 * the queue is referenced by an index value of zero. The newest object in the queue is * 226 * referenced by a value of Count-1. If there are no objects in the queue, then this * 227 * operator is undefined. Although this operator allows examination of the queue, there is * 228 * no corresponding ability to insert or delete objects from the middle of the queue. * 229 * * 230 * INPUT: index -- The index into the queue of objects. Valid values range from zero to * 231 * Count-1. All other values return an undefined reference! * 232 * * 233 * OUTPUT: Returns with a reference to the object indicated by the index. * 234 * * 235 * WARNINGS: Check to make sure that Count is not zero before using this operator. Failure * 236 * to do so will return a reference to an undefined object. * 237 * * 238 * HISTORY: * 239 * 12/09/1994 JLB : Created. * 240 *=============================================================================================*/ 241 template<class T, int size> 242 inline T & QueueClass<T,size>::operator[](int index) 243 { 244 return Array[(Head + index) & (size-1)]; 245 } 246 247 248 /*********************************************************************************************** 249 * QueueClass<T,size>::First -- Fetches reference to first object in list. * 250 * * 251 * This routine is used to fetch the first object in the list (head of the line). This * 252 * object is the oldest in the list. Typical use of this function is to get and process * 253 * the first object so that it may be discarded with the Next() function in order to bring * 254 * subsequent objects to the first position. * 255 * * 256 * INPUT: none * 257 * * 258 * OUTPUT: Returns with a reference to the oldest object in the queue. * 259 * * 260 * WARNINGS: If there are no objects in the queue, then this function returns an undefined * 261 * reference. Be sure to check Count against zero before calling this function. * 262 * * 263 * HISTORY: * 264 * 12/09/1994 JLB : Created. * 265 *=============================================================================================*/ 266 template<class T, int size> 267 inline T & QueueClass<T,size>::First(void) 268 { 269 return Array[Head]; 270 } 271 272 #endif