[176] | 1 | // -*- C++ -*- |
---|
| 2 | |
---|
| 3 | #ifndef _OBSTACKREAP_H_ |
---|
| 4 | #define _OBSTACKREAP_H_ |
---|
| 5 | |
---|
| 6 | #include <assert.h> |
---|
| 7 | |
---|
| 8 | /* |
---|
| 9 | |
---|
| 10 | ObstackReap layers obstack functionality on top of reaps. |
---|
| 11 | |
---|
| 12 | */ |
---|
| 13 | |
---|
| 14 | #if WIN32 |
---|
| 15 | #include <windows.h> |
---|
| 16 | #endif |
---|
| 17 | |
---|
| 18 | #include "dynarray.h" |
---|
| 19 | |
---|
| 20 | namespace ObstackReapNS { |
---|
| 21 | |
---|
| 22 | #if 0 |
---|
| 23 | template <class ObjType> |
---|
| 24 | class DynamicArray { |
---|
| 25 | public: |
---|
| 26 | DynamicArray (void) |
---|
| 27 | : internalArray (0), |
---|
| 28 | internalArrayLength (0) |
---|
| 29 | {} |
---|
| 30 | |
---|
| 31 | ~DynamicArray (void) |
---|
| 32 | { |
---|
| 33 | clear(); |
---|
| 34 | } |
---|
| 35 | |
---|
| 36 | // clear deletes everything in the array. |
---|
| 37 | |
---|
| 38 | inline void clear (void) { |
---|
| 39 | if (internalArray) { |
---|
| 40 | delete [] internalArray; |
---|
| 41 | internalArray = 0; |
---|
| 42 | internalArrayLength = 0; |
---|
| 43 | //printf ("\ninternalArrayLength %x = %d\n", this, internalArrayLength); |
---|
| 44 | } |
---|
| 45 | } |
---|
| 46 | |
---|
| 47 | // Read-only access to an array element; |
---|
| 48 | // asserts that this index is in range. |
---|
| 49 | |
---|
| 50 | inline const ObjType& operator[] (int index) const { |
---|
| 51 | assert (index < internalArrayLength); |
---|
| 52 | assert (index >= 0); |
---|
| 53 | return internalArray[index]; |
---|
| 54 | } |
---|
| 55 | |
---|
| 56 | // Access a particular array index by reference, |
---|
| 57 | // growing the array if necessary. |
---|
| 58 | |
---|
| 59 | inline ObjType& operator[] (int index) { |
---|
| 60 | assert (index >= 0); |
---|
| 61 | if (index >= internalArrayLength) { |
---|
| 62 | |
---|
| 63 | // This index is beyond the current size of the array. |
---|
| 64 | // Grow the array by doubling and copying the old array into the new. |
---|
| 65 | |
---|
| 66 | const int newSize = index * 2 + 1; |
---|
| 67 | ObjType * arr = new ObjType[newSize]; |
---|
| 68 | // printf ("grow! %d to %d\n", internalArrayLength, newSize); |
---|
| 69 | #if MALLOC_TRACE |
---|
| 70 | printf ("m %x %d\n", arr, newSize * sizeof(ObjType)); |
---|
| 71 | #endif |
---|
| 72 | if (internalArray) { |
---|
| 73 | memcpy (arr, internalArray, internalArrayLength * sizeof(ObjType)); |
---|
| 74 | delete [] internalArray; |
---|
| 75 | #if MALLOC_TRACE |
---|
| 76 | printf ("f %x\n", internalArray); |
---|
| 77 | #endif |
---|
| 78 | } |
---|
| 79 | internalArray = arr; |
---|
| 80 | internalArrayLength = newSize; |
---|
| 81 | // printf ("\ninternalArrayLength %x = %d\n", this, internalArrayLength); |
---|
| 82 | } |
---|
| 83 | return internalArray[index]; |
---|
| 84 | } |
---|
| 85 | |
---|
| 86 | // trim informs the array that it is now only nelts long |
---|
| 87 | // as far as the client is concerned. This may trigger |
---|
| 88 | // shrinking of the array. |
---|
| 89 | |
---|
| 90 | inline void trim (int nelts) { |
---|
| 91 | |
---|
| 92 | // Halve the array if the number of elements |
---|
| 93 | // drops below one-fourth of the array size. |
---|
| 94 | |
---|
| 95 | if (internalArray) { |
---|
| 96 | if (nelts * 4 < internalArrayLength) { |
---|
| 97 | const int newSize = nelts * 2; |
---|
| 98 | ObjType * arr = new ObjType[newSize]; |
---|
| 99 | // printf ("trim! %d to %d\n", internalArrayLength, newSize); |
---|
| 100 | #if MALLOC_TRACE |
---|
| 101 | printf ("m %x %d\n", arr, newSize * sizeof(ObjType)); |
---|
| 102 | #endif |
---|
| 103 | memcpy (arr, internalArray, sizeof(ObjType) * nelts); |
---|
| 104 | delete [] internalArray; |
---|
| 105 | #if MALLOC_TRACE |
---|
| 106 | printf ("f %x\n", internalArray); |
---|
| 107 | #endif |
---|
| 108 | internalArray = arr; |
---|
| 109 | internalArrayLength = newSize; |
---|
| 110 | } |
---|
| 111 | assert (nelts <= internalArrayLength); |
---|
| 112 | } |
---|
| 113 | } |
---|
| 114 | |
---|
| 115 | |
---|
| 116 | private: |
---|
| 117 | |
---|
| 118 | // The pointer to the current array. |
---|
| 119 | |
---|
| 120 | ObjType * internalArray; |
---|
| 121 | |
---|
| 122 | // The length of the internal array, in elements. |
---|
| 123 | |
---|
| 124 | int internalArrayLength; |
---|
| 125 | }; |
---|
| 126 | #endif |
---|
| 127 | |
---|
| 128 | template <class OBJTYPE> |
---|
| 129 | class DynStack { |
---|
| 130 | public: |
---|
| 131 | DynStack (void) |
---|
| 132 | : numItems (0) |
---|
| 133 | { |
---|
| 134 | items[0] = 0; |
---|
| 135 | } |
---|
| 136 | |
---|
| 137 | int length (void) const { return numItems; } |
---|
| 138 | |
---|
| 139 | inline void push (OBJTYPE * ptr) { |
---|
| 140 | numItems++; |
---|
| 141 | items[numItems] = ptr; |
---|
| 142 | } |
---|
| 143 | |
---|
| 144 | inline OBJTYPE * pop (void) { |
---|
| 145 | OBJTYPE * ptr = 0; |
---|
| 146 | if (numItems > 0) { |
---|
| 147 | ptr = items[numItems]; |
---|
| 148 | numItems--; |
---|
| 149 | // The array has shrunk, so potentially trim it. |
---|
| 150 | items.trim (numItems + 1); |
---|
| 151 | } |
---|
| 152 | return ptr; |
---|
| 153 | } |
---|
| 154 | |
---|
| 155 | inline OBJTYPE * top (void) { |
---|
| 156 | OBJTYPE * ptr = NULL; |
---|
| 157 | if (numItems > 0) { |
---|
| 158 | ptr = items[numItems]; |
---|
| 159 | } |
---|
| 160 | return ptr; |
---|
| 161 | } |
---|
| 162 | |
---|
| 163 | inline void clear (void) { |
---|
| 164 | items.clear(); |
---|
| 165 | } |
---|
| 166 | |
---|
| 167 | private: |
---|
| 168 | |
---|
| 169 | // The number of items recorded above. |
---|
| 170 | // 0 == no items. |
---|
| 171 | // 1 == items[1] has the single item, etc. |
---|
| 172 | // i.e., we waste entry zero. |
---|
| 173 | |
---|
| 174 | int numItems; |
---|
| 175 | |
---|
| 176 | // The array of remembered objects. |
---|
| 177 | |
---|
| 178 | DynamicArray<OBJTYPE *> items; |
---|
| 179 | }; |
---|
| 180 | |
---|
| 181 | }; |
---|
| 182 | |
---|
| 183 | |
---|
| 184 | // Layers on top of a reap. |
---|
| 185 | |
---|
| 186 | template <class ReapType> |
---|
| 187 | class ObstackReap { |
---|
| 188 | public: |
---|
| 189 | |
---|
| 190 | ObstackReap (void) |
---|
| 191 | { |
---|
| 192 | currentReap = new ReapType; |
---|
| 193 | initCurrentObject(); |
---|
| 194 | } |
---|
| 195 | |
---|
| 196 | ~ObstackReap (void) { |
---|
| 197 | ReapType * r; |
---|
| 198 | while ((r = reapStack.pop())) { |
---|
| 199 | delete r; |
---|
| 200 | } |
---|
| 201 | delete currentReap; |
---|
| 202 | delete currentObject; |
---|
| 203 | } |
---|
| 204 | |
---|
| 205 | inline void * malloc (size_t sz); |
---|
| 206 | inline void freeAfter (void * ptr); |
---|
| 207 | inline void freeAll (void); |
---|
| 208 | inline void * getObjectBase (void); |
---|
| 209 | inline void finalize (void); |
---|
| 210 | inline void * grow (size_t sz); |
---|
| 211 | |
---|
| 212 | private: |
---|
| 213 | |
---|
| 214 | inline void initCurrentObject (void); |
---|
| 215 | |
---|
| 216 | // Hide free. |
---|
| 217 | void free (void *); |
---|
| 218 | |
---|
| 219 | enum { INITIAL_OBJECT_SIZE = 8 * sizeof(double) }; |
---|
| 220 | |
---|
| 221 | void * currentObject; |
---|
| 222 | char * currentObjectPosition; |
---|
| 223 | size_t currentObjectSize; |
---|
| 224 | size_t actualObjectSize; |
---|
| 225 | bool isCurrentObjectExposed; |
---|
| 226 | ReapType * currentReap; |
---|
| 227 | ObstackReapNS::DynStack<ReapType> reapStack; |
---|
| 228 | }; |
---|
| 229 | |
---|
| 230 | |
---|
| 231 | template <class ReapType> |
---|
| 232 | void ObstackReap<ReapType>::initCurrentObject (void) { |
---|
| 233 | currentObject = currentReap->malloc (INITIAL_OBJECT_SIZE); |
---|
| 234 | currentObjectPosition = (char *) currentObject; |
---|
| 235 | currentObjectSize = 0; |
---|
| 236 | actualObjectSize = INITIAL_OBJECT_SIZE; |
---|
| 237 | isCurrentObjectExposed = false; |
---|
| 238 | } |
---|
| 239 | |
---|
| 240 | template <class ReapType> |
---|
| 241 | void * ObstackReap<ReapType>::malloc (size_t sz) { |
---|
| 242 | if (!isCurrentObjectExposed) { |
---|
| 243 | return currentReap->malloc (sz); |
---|
| 244 | } else { |
---|
| 245 | void * ptr = currentReap->realloc (currentObject, sz); |
---|
| 246 | reapStack.push (currentReap); |
---|
| 247 | currentReap = new ReapType; |
---|
| 248 | initCurrentObject(); |
---|
| 249 | return ptr; |
---|
| 250 | } |
---|
| 251 | } |
---|
| 252 | |
---|
| 253 | template <class ReapType> |
---|
| 254 | void ObstackReap<ReapType>::freeAfter (void * ptr) { |
---|
| 255 | while (currentReap && (!currentReap->find(ptr))) { |
---|
| 256 | delete currentReap; |
---|
| 257 | currentReap = reapStack.pop(); |
---|
| 258 | } |
---|
| 259 | } |
---|
| 260 | |
---|
| 261 | template <class ReapType> |
---|
| 262 | void ObstackReap<ReapType>::freeAll (void) { |
---|
| 263 | while (currentReap) { |
---|
| 264 | delete currentReap; |
---|
| 265 | currentReap = reapStack.pop(); |
---|
| 266 | } |
---|
| 267 | currentHeap = new ReapType; |
---|
| 268 | } |
---|
| 269 | |
---|
| 270 | |
---|
| 271 | template <class ReapType> |
---|
| 272 | inline void * ObstackReap<ReapType>::getObjectBase (void) { |
---|
| 273 | isCurrentObjectExposed = true; |
---|
| 274 | return currentObject; |
---|
| 275 | } |
---|
| 276 | |
---|
| 277 | template <class ReapType> |
---|
| 278 | inline void ObstackReap<ReapType>::finalize (void) { |
---|
| 279 | if (isCurrentObjectExposed) { |
---|
| 280 | reapStack.push (currentReap); |
---|
| 281 | currentReap = new ReapType; |
---|
| 282 | } |
---|
| 283 | initCurrentObject(); |
---|
| 284 | } |
---|
| 285 | |
---|
| 286 | template <class ReapType> |
---|
| 287 | inline void * ObstackReap<ReapType>::grow (size_t sz) { |
---|
| 288 | |
---|
| 289 | const int requestedObjectSize = currentObjectSize + sz; |
---|
| 290 | |
---|
| 291 | if (requestedObjectSize > actualObjectSize) { |
---|
| 292 | cout << "resize!\n"; |
---|
| 293 | void * ptr = currentReap->realloc (currentObject, sz); |
---|
| 294 | currentObjectPosition = (char *) ptr + (currentObjectPosition - (char *) currentObject); |
---|
| 295 | if (isCurrentObjectExposed) { |
---|
| 296 | reapStack.push (currentReap); |
---|
| 297 | currentReap = new ReapType; |
---|
| 298 | } |
---|
| 299 | currentObject = ptr; |
---|
| 300 | } |
---|
| 301 | |
---|
| 302 | // Because calling grow can result in a new object, |
---|
| 303 | // the current object can be considered no longer exposed (if it was before). |
---|
| 304 | |
---|
| 305 | isCurrentObjectExposed = false; |
---|
| 306 | currentObjectSize += sz; |
---|
| 307 | char * oldPosition = currentObjectPosition; |
---|
| 308 | currentObjectPosition += sz; |
---|
| 309 | return oldPosition; |
---|
| 310 | } |
---|
| 311 | |
---|
| 312 | #endif |
---|