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