00001 // ************************************************************************ 00002 // 00003 // $Id: maciRegistrar.h,v 1.79 2003/09/19 08:35:02 almamgr Exp $ 00004 // 00005 // Copyright (c) 2000 by Klemen Zagar 00006 // 00007 // GROUP = Data Structures 00008 // AUTHOR --- Klemen Zagar 00009 // 00010 // ************************************************************************ 00011 00012 #ifndef maciRegistrar_h 00013 #define maciRegistrar_h 00014 00015 // ==========================[ class Registrar ]=========================== 00016 00017 // 00018 // NAME: Registrar 00019 // 00020 // DESCRIPTION: Data structure for maintaining a collection of elements 00021 // that can be referred to using handles. 00022 // 00023 // Stores data elements in an array-like structure. Individual elements are 00024 // addressed using handles, which can be though of as indices in the 00025 // array. The registrar fulfills these requirements: 00026 // 00027 // 1. Allocation: A new element can be added to the registrar and is 00028 // assigned a unique handle. Allocation is an O(1) operation. 00029 // 00030 // 2. Deallocation: An element can be removed from the registrar. The 00031 // handle is freed, and can be assigned to another element during 00032 // allocation at a later time. Deallocation is an O(1) operation. 00033 // 00034 // 3. Retrieval: A reference to the element can be retrieved from the 00035 // registrar for reading and writing. Retrieval is an O(1) operation. 00036 // 00037 // 4. Enumeration: Elements stored in the registrar can be traversed from 00038 // first to last. Costs of acquiring first, last, next and previous 00039 // element of the array are O(1). 00040 // 00041 // 5. Unlimited storage: There is no limit other than amount of available 00042 // memory to store elements. 00043 // 00044 // The registrar data structure is suitable for enumerating resources that 00045 // are frequently allocated, retrieved and deallocated without losing large 00046 // amounts of memory and/or time. 00047 // 00048 // PARAMETERS: 00049 // 00050 // Handle - Type that represents the handle. Usually an integral type. 00051 // Must be castable to 0. 00052 // 00053 // T - Type of data that the registrar should store. 00054 // 00055 // EXAMPLE: 00056 // 00057 // // A registrar that maintains strings. 00058 // Registrar<int, string> reg; 00059 // // Allocate a new string and remember its handle. 00060 // int h = reg.Allocate(); 00061 // // Set string's value. 00062 // reg[h] = "a string"; 00063 // // Get string's value. 00064 // cout << reg[h] << endl; 00065 // // Deallocate the string. 00066 // reg.Deallocate(h); 00067 // 00068 // INTERNAL: The registrar is essentially a doubly-linked list of elements, 00069 // which are placed in an array. Each element has assigned a handle (the 00070 // index in the array), and handles of the elements that come previous and 00071 // next to it. There are actually two chains of elements: the free element 00072 // chain, which contains all elements that have not yet been allocated, and 00073 // the allocated element chain. Free element chain is cyclic (passing the 00074 // end resumes at the beginning), and contains the element with the handle 00075 // 0. The allocated element chain is not cyclic: it starts with the element 00076 // that was first allocated, and ends with the one that was last allocated. 00077 // 00078 template<class Handle, class T> 00079 class Registrar 00080 { 00081 struct Element 00082 { 00083 int hPrev, hNext; // Previous and next elements with the same bFree. 00084 T tData; // The actual data. 00085 bool bFree; // *true* if the element is still unallocated. 00086 }; 00087 00088 int m_nCapacity; // Capacity of the registrar. 00089 int m_nSize; // Number of elements currently in the registrar. 00090 Element *m_pData; // Pointer to the first element in the registrar. 00091 Handle m_hFirst; // Handle of the first non-free element. 00092 Handle m_hLast; // Handle of the last non-free element. 00093 Handle m_hOffset; // Amount by which to offset all handles. 00094 00095 public: 00096 // 00097 // DESCRIPTION: Construct the registrar. 00098 // 00099 // Creates a registrar and allocates enough space to hold nCapacity 00100 // elements. 00101 // 00102 // PARAMETERS: 00103 // hOffset - Amount by which to offset all handles. 00104 // nCapacity - Initial capacity of the registrar. 00105 // 00106 Registrar(Handle hOffset = 0, int nCapacity = 128); 00107 00108 // 00109 // DESCRIPTION: Destruct the registar, freeing all its elements. 00110 // 00111 #ifndef MAKE_VXWORKS 00112 ~Registrar(); 00113 #else 00114 ~Registrar() { delete[] m_pData; } 00115 #endif 00116 00117 // 00118 // DESCRIPTION: Gives a reference to the h-th element in the array. 00119 // 00120 // NOTE: No checking is performed whether an element corresponding to 00121 // handle h actually exists or not, n either whether h-th element is 00122 // actually within capacity limits of the registrar. 00123 // 00124 // PARAMETERS: 00125 // h - Handle of the element to return the reference to. 00126 // 00127 // RETURN VALUE: Reference (or const-reference) to the requested element. 00128 // 00129 T& operator[](Handle h) { return m_pData[h-m_hOffset].tData; } 00130 const T& operator[](Handle h) const { return m_pData[h-m_hOffset].tData; } 00131 00132 // ---------------------------------------------------------------------- 00133 // GROUP = Registrar capacity 00134 // ---------------------------------------------------------------------- 00135 00136 // 00137 // DESCRIPTION: Sets the maximum amount of elements the registrar can 00138 // hold before resizing itself. 00139 // 00140 // The registar is made to hold elements with handles of up to nCapacity. 00141 // 00142 // NOTE: If nCapacity is smaller than the current capacity, the operation 00143 // fails. 00144 // 00145 // PARAMETERS: 00146 // nCapacity - The requested capacity of the registrar. 00147 // 00148 // RETURN VALUE: If the capacity has been successfully set, a return 00149 // value of *true* is returned. In case of an error, such as lack of 00150 // memory or too small capacity, *false* is returned. 00151 // 00152 bool SetCapacity(int nCapacity); 00153 00154 // 00155 // DESCRIPTION: Get the capacity of the registrary. 00156 // 00157 // RETURN VALUE: Returns the capacity of the registrar, i.e. the maximum 00158 // number of elements that the registrar can hold before resizing itself. 00159 // 00160 int GetCapacity() { return m_nCapacity - 1; } 00161 00162 // 00163 // DESCRIPTION: Get the number of elements currently in the registrar. 00164 // 00165 // RETURN VALUE: The number of elements currently in the registar. 00166 // 00167 int GetSize() { return m_nSize; } 00168 00169 // ---------------------------------------------------------------------- 00170 // GROUP = Allocation/Deallocation 00171 // ---------------------------------------------------------------------- 00172 00173 // 00174 // DESCRIPTION: Allocate an element in the registrar. 00175 // 00176 // Assures that the registrar is capable of holding yet another element 00177 // and returns a handle to it. If h is specified, then the function tries 00178 // to make the returned handle 00179 // 00180 // NOTE: Do not use too high a value for h, because Allocate assures that 00181 // capacity of the registar becomes at least h, resulting in a huge 00182 // consumption of memory. 00183 // 00184 // PARAMETERS: 00185 // h - Requests the registrar to use h as the handle of the allocated 00186 // element. If 0 is passed (the default), then the handle is 00187 // assigned automatically by the registrar. 00188 // 00189 // RETURN VALUE: If 0 is returned, then the allocation was not 00190 // successful, either because the handle is already allocated, or because 00191 // the system ran out of memory. 00192 // 00193 // SEE ALSO: Deallocate 00194 // 00195 Handle Allocate(Handle h = 0); 00196 00197 Handle Preallocate(Handle h = 0); 00198 Handle AckAllocate(Handle h); 00199 00200 // 00201 // DESCRIPTION: Deallocate an element with the given handle. 00202 // 00203 // The element and its corresponding handle can be reused at a later call 00204 // to Allocate. 00205 // 00206 // PARAMETERS: 00207 // h - The handle of the element to deallocate. 00208 // 00209 // RETURN VALUE: Returns 0 if the element is not yet allocated. In case 00210 // of success, the handle of the next element in the registrar is 00211 // returned, which can also be 0 if h represents the last element in the 00212 // array. 00213 // 00214 // EXAMPLE: This example shows how to deallocate all elements in the 00215 // array. 00216 // 00217 // Registrar<Handle, T> reg; 00218 // . . . 00219 // Handle h = reg.First(); 00220 // while(h) h = reg.Deallocate(h); 00221 // 00222 Handle Deallocate(Handle h); 00223 00224 Handle Depreallocate(Handle h); 00225 00226 // 00227 // DESCRIPTION: Determines whether a given handle has already been 00228 // allocated. 00229 // 00230 // PARAMETERS: 00231 // h - The handle in question. 00232 // 00233 // RETURN VALUE: Returns *true* if an element with handle h already 00234 // exists in the registrar and false otherwise. 00235 // 00236 bool IsAllocated(Handle h); 00237 00238 // ---------------------------------------------------------------------- 00239 // GROUP = Enumeration 00240 // ---------------------------------------------------------------------- 00241 00242 // 00243 // DESCRIPTION: Return the handle of the first element in the array. 00244 // 00245 // RETURN VALUE: Returns the handle of the element that was the first one 00246 // to get allocated and has not yet been deallocated. Useful for 00247 // determining the starting point when enumerating the entire registry. 00248 // 00249 // SEE ALSO: Next, Previous 00250 // 00251 Handle First() { return m_hFirst + m_hOffset; } 00252 00253 // 00254 // DESCRIPTION: Return the handle of the last element in the array. 00255 // 00256 // RETURN VALUE: Returns the handle of the element that was the last one 00257 // to get allocated and has not yet been deallocated. Useful for 00258 // determining the starting point when enumerating the entire registry. 00259 // 00260 // SEE ALSO: Next, Previous 00261 // 00262 Handle Last() { return m_hLast + m_hOffset; } 00263 00264 // 00265 // DESCRIPTION: Return the handle of the next element in the array. 00266 // 00267 // PARAMETERS: 00268 // h - Handle of the element whose sucessor's handle we wish to 00269 // acquire. 00270 // 00271 // RETURN VALUE: Returns the handle of the element that follows the one 00272 // whose handle is h. If h is the last element, 0 is returned. 00273 // 00274 Handle Next(Handle h) { return m_pData[h-m_hOffset].hNext + m_hOffset; } 00275 00276 // 00277 // DESCRIPTION: Return the handle of the previous element in the array. 00278 // 00279 // PARAMETERS: 00280 // h - Handle of the element whose predecessor's handle we 00281 // wish to acquire. 00282 // 00283 // RETURN VALUE: Returns the handle of the element that precedes the one 00284 // whose handle is h. If h is the first element, 0 is returned. 00285 // 00286 Handle Previous(Handle h) { return m_pData[h-m_hOffset].hPrev + m_hOffset; } 00287 00288 // ---------------------------------------------------------------------- 00289 // GROUP = Miscellaneous 00290 // ---------------------------------------------------------------------- 00291 00292 // 00293 // DESCRIPTION: Check whether the registrar is in a consistent state. 00294 // 00295 // Performs several consistency checks on the registar. 00296 // 00297 // RETURN VALUE: 00298 // 0 - The registrar is in a consistent state. 00299 // 1 - Doubly-linked list exceeds the capacity of the registrar; some 00300 // of its elements are not within the array managed by the 00301 // registrar. 00302 // 2 - Doubly-linked list is inconsistent (element's next's previous is 00303 // not the element). 00304 // 3 - An element is in the free element chain, but it is marked as 00305 // allocated. 00306 // 4 - An element in the allocated element chain, but it is marked as 00307 // free. 00308 // 5 - The two doubly-linked lists don't span the entire capacity of 00309 // the registrar. 00310 // 00311 int CheckIntegrity(); 00312 }; 00313 00314 #include <maciRegistrar.i> 00315 00316 #endif // maciRegistrar_h 00317
1.6.2