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