← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/include/llvm/ADT/PostOrderIterator.h

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/include/llvm/ADT/PostOrderIterator.h
1
 
//===- llvm/ADT/PostOrderIterator.h - PostOrder iterator --------*- C++ -*-===//
2
 
//
3
 
//                     The LLVM Compiler Infrastructure
4
 
//
5
 
// This file is distributed under the University of Illinois Open Source
6
 
// License. See LICENSE.TXT for details.
7
 
//
8
 
//===----------------------------------------------------------------------===//
9
 
//
10
 
// This file builds on the ADT/GraphTraits.h file to build a generic graph
11
 
// post order iterator.  This should work over any graph type that has a
12
 
// GraphTraits specialization.
13
 
//
14
 
//===----------------------------------------------------------------------===//
15
 
 
16
 
#ifndef LLVM_ADT_POSTORDERITERATOR_H
17
 
#define LLVM_ADT_POSTORDERITERATOR_H
18
 
 
19
 
#include "llvm/ADT/GraphTraits.h"
20
 
#include "llvm/ADT/SmallPtrSet.h"
21
 
#include <set>
22
 
#include <vector>
23
 
 
24
 
namespace llvm {
25
 
 
26
 
template<class SetType, bool External>   // Non-external set
27
 
class po_iterator_storage {
28
 
public:
29
 
  SetType Visited;
30
 
};
31
 
 
32
 
template<class SetType>
33
 
class po_iterator_storage<SetType, true> {
34
 
public:
35
 
  po_iterator_storage(SetType &VSet) : Visited(VSet) {}
36
 
  po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {}
37
 
  SetType &Visited;
38
 
};
39
 
 
40
 
template<class GraphT,
41
 
  class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
42
 
  bool ExtStorage = false,
43
 
  class GT = GraphTraits<GraphT> >
44
 
class po_iterator : public std::iterator<std::forward_iterator_tag,
45
 
                                         typename GT::NodeType, ptrdiff_t>,
46
 
                    public po_iterator_storage<SetType, ExtStorage> {
47
 
  typedef std::iterator<std::forward_iterator_tag,
48
 
                        typename GT::NodeType, ptrdiff_t> super;
49
 
  typedef typename GT::NodeType          NodeType;
50
 
  typedef typename GT::ChildIteratorType ChildItTy;
51
 
 
52
 
  // VisitStack - Used to maintain the ordering.  Top = current block
53
 
  // First element is basic block pointer, second is the 'next child' to visit
54
 
  std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
55
 
 
56
 
  void traverseChild() {
57
 
    while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
58
 
      NodeType *BB = *VisitStack.back().second++;
59
 
      if (!this->Visited.count(BB)) {  // If the block is not visited...
60
 
        this->Visited.insert(BB);
61
 
        VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
62
 
      }
63
 
    }
64
 
  }
65
 
 
66
 
  inline po_iterator(NodeType *BB) {
67
 
    this->Visited.insert(BB);
68
 
    VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
69
 
    traverseChild();
70
 
  }
71
 
  inline po_iterator() {} // End is when stack is empty.
72
 
 
73
 
  inline po_iterator(NodeType *BB, SetType &S) :
74
 
    po_iterator_storage<SetType, ExtStorage>(S) {
75
 
    if(!S.count(BB)) {
76
 
      this->Visited.insert(BB);
77
 
      VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
78
 
      traverseChild();
79
 
    }
80
 
  }
81
 
 
82
 
  inline po_iterator(SetType &S) :
83
 
      po_iterator_storage<SetType, ExtStorage>(S) {
84
 
  } // End is when stack is empty.
85
 
public:
86
 
  typedef typename super::pointer pointer;
87
 
  typedef po_iterator<GraphT, SetType, ExtStorage, GT> _Self;
88
 
 
89
 
  // Provide static "constructors"...
90
 
  static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); }
91
 
  static inline _Self end  (GraphT G) { return _Self(); }
92
 
 
93
 
  static inline _Self begin(GraphT G, SetType &S) {
94
 
    return _Self(GT::getEntryNode(G), S);
95
 
  }
96
 
  static inline _Self end  (GraphT G, SetType &S) { return _Self(S); }
97
 
 
98
 
  inline bool operator==(const _Self& x) const {
99
 
    return VisitStack == x.VisitStack;
100
 
  }
101
 
  inline bool operator!=(const _Self& x) const { return !operator==(x); }
102
 
 
103
 
  inline pointer operator*() const {
104
 
    return VisitStack.back().first;
105
 
  }
106
 
 
107
 
  // This is a nonstandard operator-> that dereferences the pointer an extra
108
 
  // time... so that you can actually call methods ON the BasicBlock, because
109
 
  // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
110
 
  //
111
 
  inline NodeType *operator->() const { return operator*(); }
112
 
 
113
 
  inline _Self& operator++() {   // Preincrement
114
 
    VisitStack.pop_back();
115
 
    if (!VisitStack.empty())
116
 
      traverseChild();
117
 
    return *this;
118
 
  }
119
 
 
120
 
  inline _Self operator++(int) { // Postincrement
121
 
    _Self tmp = *this; ++*this; return tmp;
122
 
  }
123
 
};
124
 
 
125
 
// Provide global constructors that automatically figure out correct types...
126
 
//
127
 
template <class T>
128
 
po_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); }
129
 
template <class T>
130
 
po_iterator<T> po_end  (T G) { return po_iterator<T>::end(G); }
131
 
 
132
 
// Provide global definitions of external postorder iterators...
133
 
template<class T, class SetType=std::set<typename GraphTraits<T>::NodeType*> >
134
 
struct po_ext_iterator : public po_iterator<T, SetType, true> {
135
 
  po_ext_iterator(const po_iterator<T, SetType, true> &V) :
136
 
  po_iterator<T, SetType, true>(V) {}
137
 
};
138
 
 
139
 
template<class T, class SetType>
140
 
po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
141
 
  return po_ext_iterator<T, SetType>::begin(G, S);
142
 
}
143
 
 
144
 
template<class T, class SetType>
145
 
po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) {
146
 
  return po_ext_iterator<T, SetType>::end(G, S);
147
 
}
148
 
 
149
 
// Provide global definitions of inverse post order iterators...
150
 
template <class T,
151
 
          class SetType = std::set<typename GraphTraits<T>::NodeType*>,
152
 
          bool External = false>
153
 
struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External > {
154
 
  ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
155
 
     po_iterator<Inverse<T>, SetType, External> (V) {}
156
 
};
157
 
 
158
 
template <class T>
159
 
ipo_iterator<T> ipo_begin(T G, bool Reverse = false) {
160
 
  return ipo_iterator<T>::begin(G, Reverse);
161
 
}
162
 
 
163
 
template <class T>
164
 
ipo_iterator<T> ipo_end(T G){
165
 
  return ipo_iterator<T>::end(G);
166
 
}
167
 
 
168
 
//Provide global definitions of external inverse postorder iterators...
169
 
template <class T,
170
 
          class SetType = std::set<typename GraphTraits<T>::NodeType*> >
171
 
struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> {
172
 
  ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) :
173
 
    ipo_iterator<T, SetType, true>(&V) {}
174
 
  ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
175
 
    ipo_iterator<T, SetType, true>(&V) {}
176
 
};
177
 
 
178
 
template <class T, class SetType>
179
 
ipo_ext_iterator<T, SetType> ipo_ext_begin(T G, SetType &S) {
180
 
  return ipo_ext_iterator<T, SetType>::begin(G, S);
181
 
}
182
 
 
183
 
template <class T, class SetType>
184
 
ipo_ext_iterator<T, SetType> ipo_ext_end(T G, SetType &S) {
185
 
  return ipo_ext_iterator<T, SetType>::end(G, S);
186
 
}
187
 
 
188
 
//===--------------------------------------------------------------------===//
189
 
// Reverse Post Order CFG iterator code
190
 
//===--------------------------------------------------------------------===//
191
 
//
192
 
// This is used to visit basic blocks in a method in reverse post order.  This
193
 
// class is awkward to use because I don't know a good incremental algorithm to
194
 
// computer RPO from a graph.  Because of this, the construction of the
195
 
// ReversePostOrderTraversal object is expensive (it must walk the entire graph
196
 
// with a postorder iterator to build the data structures).  The moral of this
197
 
// story is: Don't create more ReversePostOrderTraversal classes than necessary.
198
 
//
199
 
// This class should be used like this:
200
 
// {
201
 
//   ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
202
 
//   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
203
 
//      ...
204
 
//   }
205
 
//   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
206
 
//      ...
207
 
//   }
208
 
// }
209
 
//
210
 
 
211
 
template<class GraphT, class GT = GraphTraits<GraphT> >
212
 
class ReversePostOrderTraversal {
213
 
  typedef typename GT::NodeType NodeType;
214
 
  std::vector<NodeType*> Blocks;       // Block list in normal PO order
215
 
  inline void Initialize(NodeType *BB) {
216
 
    copy(po_begin(BB), po_end(BB), back_inserter(Blocks));
217
 
  }
218
 
public:
219
 
  typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator;
220
 
 
221
 
  inline ReversePostOrderTraversal(GraphT G) {
222
 
    Initialize(GT::getEntryNode(G));
223
 
  }
224
 
 
225
 
  // Because we want a reverse post order, use reverse iterators from the vector
226
 
  inline rpo_iterator begin() { return Blocks.rbegin(); }
227
 
  inline rpo_iterator end()   { return Blocks.rend(); }
228
 
};
229
 
 
230
 
} // End llvm namespace
231
 
 
232
 
#endif