ROSE 0.11.145.147
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
42template <class T>
44{
45public:
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
136protected:
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
147private:
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
154template <class T>
156 : buffer(new BufferType()),
157 framePtr(buffer->begin()),
158 stackPtr(buffer->end()),
159 deleteBufferWhenDone(true)
160{
161}
162
163template <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
172template <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
182template <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
193template <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
204template <class T>
206{
207 ROSE_ASSERT(deleteBufferWhenDone == (buffer != NULL));
208 if (deleteBufferWhenDone)
209 {
210 delete buffer;
211 buffer = NULL;
212 }
213}
214
215template <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
226template <class T>
227typename StackFrameVector<T>::iterator
229{
230 return framePtr;
231}
232
233template <class T>
234typename StackFrameVector<T>::const_iterator
236{
237 return framePtr;
238}
239
240template <class T>
241typename StackFrameVector<T>::iterator
243{
244 return stackPtr;
245}
246
247template <class T>
248typename StackFrameVector<T>::const_iterator
250{
251 return stackPtr;
252}
253
254template <class T>
255typename StackFrameVector<T>::reverse_iterator
257{
258 return reverse_iterator(end());
259}
260
261template <class T>
262typename StackFrameVector<T>::const_reverse_iterator
264{
265 return reverse_iterator(end());
266}
267
268template <class T>
269typename StackFrameVector<T>::reverse_iterator
271{
272 return reverse_iterator(begin());
273}
274
275template <class T>
276typename StackFrameVector<T>::const_reverse_iterator
278{
279 return reverse_iterator(begin());
280}
281
282template <class T>
283typename StackFrameVector<T>::size_type
285{
286 return end() - begin();
287}
288
289template <class T>
290typename StackFrameVector<T>::size_type
292{
293 return size();
294}
295
296template <class T>
297typename StackFrameVector<T>::size_type
299{
300 return size();
301}
302
303template <class T>
304bool
306{
307 return size() == 0;
308}
309
310template <class T>
311typename StackFrameVector<T>::reference
312StackFrameVector<T>::operator[](typename StackFrameVector<T>::size_type n)
313{
314 return framePtr[n];
315}
316
317template <class T>
318typename StackFrameVector<T>::const_reference
319StackFrameVector<T>::operator[](typename StackFrameVector<T>::size_type n) const
320{
321 return framePtr[n];
322}
323
324#include <stdexcept>
325
326template <class T>
327typename StackFrameVector<T>::reference
328StackFrameVector<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
335template <class T>
336typename StackFrameVector<T>::const_reference
337StackFrameVector<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
344template <class T>
345typename StackFrameVector<T>::reference
347{
348 return *framePtr;
349}
350
351template <class T>
352typename StackFrameVector<T>::const_reference
354{
355 return *framePtr;
356}
357
358template <class T>
359typename StackFrameVector<T>::reference
361{
362 return *(stackPtr - 1);
363}
364
365template <class T>
366typename StackFrameVector<T>::const_reference
368{
369 return *(stackPtr - 1);
370}
371
372template <class T>
373StackFrameVector<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
379template <class T>
380void
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
403template <class T>
404void
405StackFrameVector<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
413template <class T>
414typename StackFrameVector<T>::size_type
416{
417 ROSE_ASSERT(buffer != NULL);
418 return stackPtr - buffer->begin();
419}
420
421template <class T>
422void
424{
425 ROSE_ASSERT(buffer != NULL);
426 framePtr = stackPtr = buffer->begin();
427}
428
429template <class T>
430typename 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
441template <class T>
442void
443StackFrameVector<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