ROSE  0.9.9.139
StackFrameVector.h
1 // Author: Gergo Barany
2 // $Id: StackFrameVector.h,v 1.1 2008/01/08 02:56:39 dquinlan Exp $
3 
4 /*
5  StackFrameVector is a template container class meant to be used for the
6  stack of SythesizedAttributes in the SgTreeTraversal class; to the concrete
7  traversal classes (Ast*Processing) it is hidden behind the
8  SynthesizedAttributesList typedef, which used to be a std::vector.
9  Therefore StackFrameVector implements much of the interface of std::vector
10  in the hope that this will cause minimal breakage of existing user code.
11 
12  As it was never a useful operation to alter the size of the
13  SynthesizedAttributesList, or to change its contents, and this would be
14  impossible to support efficiently with StackFrameVector, member functions
15  such as push_back(), erase(), resize() etc. are not implemented. Code using
16  these, for whatever strange reason, should make a copy of the container (a
17  conversion to std::vector is provided) to continue working.
18 
19  At the moment we don't provide comparison operators either.
20 
21  StackFrameVector is basically implemented as a pointer to a vector, which
22  contains the stack elements, and a pair of iterators into this vector
23  denoting the start and end of a stack frame. Some special stack operations
24  are provided: push(const T &) to push an element to the top of the stack,
25  and setFrameSize(BufferType::size_type) to define how many elements will
26  comprise the stack's top frame (i.e., how many elements there will be
27  between begin() and end()). A push() always pops off the current frame
28  before the new element is added.
29 
30  The function debugSize() tells you the total size of the stack, and pop()
31  pops and returns the topmost element, which is mainly useful if the stack
32  contains exactly that one element. All these special functions should only
33  be used by code that knows what it's doing.
34 */
35 
36 #ifndef STACKFRAMEVECTOR_H
37 #define STACKFRAMEVECTOR_H
38 
39 #include <vector>
40 #include <ostream>
41 
42 template <class T>
44 {
45 public:
46  // typedef to the underlying container type; this is provided for
47  // generality, but it will probably not make much sense to change it
48  typedef std::vector<T> BufferType;
49 
50  // typedefs required for std::vector, just use those defined for the
51  // buffer type
52  typedef typename BufferType::reference reference;
53  typedef typename BufferType::const_reference const_reference;
54  typedef typename BufferType::iterator iterator;
55  typedef typename BufferType::const_iterator const_iterator;
56  typedef typename BufferType::size_type size_type;
57  typedef typename BufferType::difference_type difference_type;
58  typedef typename BufferType::value_type value_type;
59  typedef typename BufferType::allocator_type allocator_type;
60  typedef typename BufferType::pointer pointer;
61  typedef typename BufferType::const_pointer const_pointer;
62  typedef typename BufferType::reverse_iterator reverse_iterator;
63  typedef typename BufferType::const_reverse_iterator const_reverse_iterator;
64 
65  // constructors required for std::vector are not all implemented
66  // because user code is not supposed to construct a StackFrameVector
69  StackFrameVector(size_type n);
70  StackFrameVector(size_type n, value_type initValue);
71 
73 
74  // deep copy operation, returns a new instance with a copy of this one's
75  // stack up to the stackPtr (the iterators are set correctly in the copy)
76  StackFrameVector *deepCopy() const;
77 
78  // iterator functions required for std::vector
79  iterator begin();
80  const_iterator begin() const;
81  iterator end();
82  const_iterator end() const;
83  reverse_iterator rbegin();
84  const_reverse_iterator rbegin() const;
85  reverse_iterator rend();
86  const_reverse_iterator rend() const;
87 
88  // various size-related operations required for std::vector; these do
89  // not return the size of the underlying buffer (stack), but only the
90  // size of the current stack frame
91  // size(), max_size(), capacity() return the same value, no resizing
92  // functions are provided.
93  size_type size() const;
94  size_type max_size() const;
95  size_type capacity() const;
96  bool empty() const;
97 
98  // element access functions required for std::vector
99  reference operator[](size_type);
100  const_reference operator[](size_type) const;
101  reference at(size_type);
102  const_reference at(size_type) const;
103  reference front();
104  const_reference front() const;
105  reference back();
106  const_reference back() const;
107 
108  // type conversion to underlying type (this results in a copy, so it
109  // will cost you)
110  operator std::vector<T>();
111 
112  // modifiers; these are deliberately different from what std::vector
113  // provides! use at your own risk, and only if you know what you're doing
114  void push(const T &);
115  void setFrameSize(difference_type);
116 
117  // function used for debugging, returns the overall number of objects
118  // on the stack, i.e. not just in the current frame
119  size_type debugSize() const;
120 
121  // Clear the stack; deliberately not named clear. This should only be
122  // called by the traversal code at the beginning of a traversal, and in
123  // fact it is only needed to support tutorial/traversalShortCircuit.C
124  // which calls a traversal, exits from it by throwing an exception,
125  // leaving junk on the stack, then uses that traversal object again.
126  void resetStack();
127 
128  // Pops the top element off the stack, returns it, and adjusts the
129  // stack pointer accordingly. Note that this makes sense primarily if
130  // the stack (not just the current frame!) contains exactly one element.
131  value_type pop();
132 
133  // do some debug output; this should not be called
134  void debugDump(std::ostream &s);
135 
136 protected:
137  // the buffer to hold all stack elements
138  BufferType *buffer;
139  // the top stack frame is denoted by these iterators, framePtr plays the
140  // role of begin, stackPtr the role of end
141  iterator framePtr, stackPtr;
142  // flag to indicate whether the destructor should delete the buffer; this
143  // must be false for shallow copies (shallow copying is the default
144  // behavior)
145  bool deleteBufferWhenDone;
146 
147 private:
148  explicit StackFrameVector(const BufferType &otherBuffer, difference_type framePtrOffset);
149 };
150 
151 // Author: Gergo Barany
152 // $Id: StackFrameVector.C,v 1.1 2008/01/08 02:56:39 dquinlan Exp $
153 
154 template <class T>
156  : buffer(new BufferType()),
157  framePtr(buffer->begin()),
158  stackPtr(buffer->end()),
159  deleteBufferWhenDone(true)
160 {
161 }
162 
163 template <class T>
165  : buffer(NULL),
166  framePtr(v.framePtr),
167  stackPtr(v.stackPtr),
168  deleteBufferWhenDone(false) // don't delete the pointer, it's not ours
169 {
170 }
171 
172 template <class T>
174  typename StackFrameVector<T>::size_type n)
175  : buffer(new BufferType(n)),
176  framePtr(buffer->begin()),
177  stackPtr(buffer->end()),
178  deleteBufferWhenDone(true)
179 {
180 }
181 
182 template <class T>
184  typename StackFrameVector<T>::size_type n,
185  typename StackFrameVector<T>::value_type initValue)
186  : buffer(new BufferType(n, initValue)),
187  framePtr(buffer->begin()),
188  stackPtr(buffer->end()),
189  deleteBufferWhenDone(true)
190 {
191 }
192 
193 template <class T>
195  const typename StackFrameVector<T>::BufferType &otherBuffer,
196  typename StackFrameVector<T>::difference_type framePtrOffset)
197  : buffer(new BufferType(otherBuffer)),
198  framePtr(buffer->begin() + framePtrOffset),
199  stackPtr(buffer->end()),
200  deleteBufferWhenDone(true)
201 {
202 }
203 
204 template <class T>
206 {
207  ROSE_ASSERT(deleteBufferWhenDone == (buffer != NULL));
208  if (deleteBufferWhenDone)
209  {
210  delete buffer;
211  buffer = NULL;
212  }
213 }
214 
215 template <class T>
218 {
219  // return a pointer to a new instance having a deep copy of all the live
220  // elements on the stack (those up to stackPtr). The second argument is
221  // the offset of the framePtr that needs to be set correctly in the copy
222  // (the stackPtr can just be set to the end of the newly copied buffer).
223  return new StackFrameVector(BufferType(buffer->begin(), stackPtr), framePtr - buffer->begin());
224 }
225 
226 template <class T>
227 typename StackFrameVector<T>::iterator
229 {
230  return framePtr;
231 }
232 
233 template <class T>
234 typename StackFrameVector<T>::const_iterator
236 {
237  return framePtr;
238 }
239 
240 template <class T>
241 typename StackFrameVector<T>::iterator
243 {
244  return stackPtr;
245 }
246 
247 template <class T>
248 typename StackFrameVector<T>::const_iterator
250 {
251  return stackPtr;
252 }
253 
254 template <class T>
255 typename StackFrameVector<T>::reverse_iterator
257 {
258  return reverse_iterator(end());
259 }
260 
261 template <class T>
262 typename StackFrameVector<T>::const_reverse_iterator
264 {
265  return reverse_iterator(end());
266 }
267 
268 template <class T>
269 typename StackFrameVector<T>::reverse_iterator
271 {
272  return reverse_iterator(begin());
273 }
274 
275 template <class T>
276 typename StackFrameVector<T>::const_reverse_iterator
278 {
279  return reverse_iterator(begin());
280 }
281 
282 template <class T>
283 typename StackFrameVector<T>::size_type
285 {
286  return end() - begin();
287 }
288 
289 template <class T>
290 typename StackFrameVector<T>::size_type
292 {
293  return size();
294 }
295 
296 template <class T>
297 typename StackFrameVector<T>::size_type
299 {
300  return size();
301 }
302 
303 template <class T>
304 bool
306 {
307  return size() == 0;
308 }
309 
310 template <class T>
311 typename StackFrameVector<T>::reference
312 StackFrameVector<T>::operator[](typename StackFrameVector<T>::size_type n)
313 {
314  return framePtr[n];
315 }
316 
317 template <class T>
318 typename StackFrameVector<T>::const_reference
319 StackFrameVector<T>::operator[](typename StackFrameVector<T>::size_type n) const
320 {
321  return framePtr[n];
322 }
323 
324 #include <stdexcept>
325 
326 template <class T>
327 typename StackFrameVector<T>::reference
328 StackFrameVector<T>::at(typename StackFrameVector<T>::size_type n)
329 {
330  if (n >= size())
331  throw std::out_of_range("StackFrameVector: index out of range");
332  return (*this)[n];
333 }
334 
335 template <class T>
336 typename StackFrameVector<T>::const_reference
337 StackFrameVector<T>::at(typename StackFrameVector<T>::size_type n) const
338 {
339  if (n >= size())
340  throw std::out_of_range("StackFrameVector: index out of range");
341  return (*this)[n];
342 }
343 
344 template <class T>
345 typename StackFrameVector<T>::reference
347 {
348  return *framePtr;
349 }
350 
351 template <class T>
352 typename StackFrameVector<T>::const_reference
354 {
355  return *framePtr;
356 }
357 
358 template <class T>
359 typename StackFrameVector<T>::reference
361 {
362  return *(stackPtr - 1);
363 }
364 
365 template <class T>
366 typename StackFrameVector<T>::const_reference
368 {
369  return *(stackPtr - 1);
370 }
371 
372 template <class T>
373 StackFrameVector<T>::operator std::vector<T>()
374 {
375  // return a copy of the objects in the current stack frame
376  return BufferType(begin(), end());
377 }
378 
379 template <class T>
380 void
381 StackFrameVector<T>::push(const T &x)
382 {
383  ROSE_ASSERT(buffer != NULL);
384 
385  if (framePtr == buffer->end())
386  {
387  buffer->push_back(x);
388  // push_back may have caused a resize, invalidating iterators;
389  // compute the new iterator values
390  framePtr = stackPtr = buffer->end();
391  // note that no user should have iterators into our buffer lying
392  // around (push is only called by the traversal code, no user function
393  // is alive at that point), so hopefully we haven't invalidated
394  // anything else
395  }
396  else
397  {
398  *framePtr++ = x;
399  stackPtr = framePtr;
400  }
401 }
402 
403 template <class T>
404 void
405 StackFrameVector<T>::setFrameSize(difference_type frameSize)
406 {
407  // set the frame size to the desired value by adjusting the frame
408  // pointer; the next push() (which writes through the frame pointer)
409  // will in effect pop off this whole frame
410  framePtr = stackPtr - frameSize;
411 }
412 
413 template <class T>
414 typename StackFrameVector<T>::size_type
416 {
417  ROSE_ASSERT(buffer != NULL);
418  return stackPtr - buffer->begin();
419 }
420 
421 template <class T>
422 void
424 {
425  ROSE_ASSERT(buffer != NULL);
426  framePtr = stackPtr = buffer->begin();
427 }
428 
429 template <class T>
430 typename StackFrameVector<T>::value_type
432 {
433  // pop off a single element, this is intended to be used if the whole
434  // stack contains just this element (the final result of the computation);
435  // if your stack contains more than one element at this point, your
436  // pointers will be messed up
437  --framePtr;
438  return *--stackPtr;
439 }
440 
441 template <class T>
442 void
443 StackFrameVector<T>::debugDump(std::ostream &s)
444 {
445  // this function should only be called for debugging
446  s << "\n"
447  << "framePtr offset: " << framePtr - buffer->begin()
448  << " stackPtr offset: " << stackPtr - buffer->begin()
449  << " size: " << size()
450  << " buffer size: " << buffer->size()
451  << "\n";
452  s << "buffer:" << "\n";
453  const_iterator i;
454  for (i = buffer->begin(); i != buffer->end(); ++i)
455  s << (void *) *i << ' ';
456  s << "\n" << "\n";
457 }
458 
459 #endif