← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

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