← 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/SCCIterator.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/SCCIterator.h
 
1
//===-- Support/SCCIterator.h - Strongly Connected Comp. Iter. --*- 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 builds on the llvm/ADT/GraphTraits.h file to find the strongly connected
 
11
// components (SCCs) of a graph in O(N+E) time using Tarjan's DFS algorithm.
 
12
//
 
13
// The SCC iterator has the important property that if a node in SCC S1 has an
 
14
// edge to a node in SCC S2, then it visits S1 *after* S2.
 
15
//
 
16
// To visit S1 *before* S2, use the scc_iterator on the Inverse graph.
 
17
// (NOTE: This requires some simple wrappers and is not supported yet.)
 
18
//
 
19
//===----------------------------------------------------------------------===//
 
20
 
 
21
#ifndef LLVM_ADT_SCCITERATOR_H
 
22
#define LLVM_ADT_SCCITERATOR_H
 
23
 
 
24
#include "llvm/ADT/GraphTraits.h"
 
25
#include "llvm/ADT/DenseMap.h"
 
26
#include <vector>
 
27
 
 
28
namespace llvm {
 
29
 
 
30
//===----------------------------------------------------------------------===//
 
31
///
 
32
/// scc_iterator - Enumerate the SCCs of a directed graph, in
 
33
/// reverse topological order of the SCC DAG.
 
34
///
 
35
template<class GraphT, class GT = GraphTraits<GraphT> >
 
36
class scc_iterator
 
37
  : public std::iterator<std::forward_iterator_tag,
 
38
                         std::vector<typename GT::NodeType>, ptrdiff_t> {
 
39
  typedef typename GT::NodeType          NodeType;
 
40
  typedef typename GT::ChildIteratorType ChildItTy;
 
41
  typedef std::vector<NodeType*> SccTy;
 
42
  typedef std::iterator<std::forward_iterator_tag,
 
43
                        std::vector<typename GT::NodeType>, ptrdiff_t> super;
 
44
  typedef typename super::reference reference;
 
45
  typedef typename super::pointer pointer;
 
46
 
 
47
  // The visit counters used to detect when a complete SCC is on the stack.
 
48
  // visitNum is the global counter.
 
49
  // nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
 
50
  unsigned visitNum;
 
51
  DenseMap<NodeType *, unsigned> nodeVisitNumbers;
 
52
 
 
53
  // SCCNodeStack - Stack holding nodes of the SCC.
 
54
  std::vector<NodeType *> SCCNodeStack;
 
55
 
 
56
  // CurrentSCC - The current SCC, retrieved using operator*().
 
57
  SccTy CurrentSCC;
 
58
 
 
59
  // VisitStack - Used to maintain the ordering.  Top = current block
 
60
  // First element is basic block pointer, second is the 'next child' to visit
 
61
  std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
 
62
 
 
63
  // MinVistNumStack - Stack holding the "min" values for each node in the DFS.
 
64
  // This is used to track the minimum uplink values for all children of
 
65
  // the corresponding node on the VisitStack.
 
66
  std::vector<unsigned> MinVisitNumStack;
 
67
 
 
68
  // A single "visit" within the non-recursive DFS traversal.
 
69
  void DFSVisitOne(NodeType* N) {
 
70
    ++visitNum;                         // Global counter for the visit order
 
71
    nodeVisitNumbers[N] = visitNum;
 
72
    SCCNodeStack.push_back(N);
 
73
    MinVisitNumStack.push_back(visitNum);
 
74
    VisitStack.push_back(std::make_pair(N, GT::child_begin(N)));
 
75
    //dbgs() << "TarjanSCC: Node " << N <<
 
76
    //      " : visitNum = " << visitNum << "\n";
 
77
  }
 
78
 
 
79
  // The stack-based DFS traversal; defined below.
 
80
  void DFSVisitChildren() {
 
81
    assert(!VisitStack.empty());
 
82
    while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
 
83
      // TOS has at least one more child so continue DFS
 
84
      NodeType *childN = *VisitStack.back().second++;
 
85
      if (!nodeVisitNumbers.count(childN)) {
 
86
        // this node has never been seen
 
87
        DFSVisitOne(childN);
 
88
      } else {
 
89
        unsigned childNum = nodeVisitNumbers[childN];
 
90
        if (MinVisitNumStack.back() > childNum)
 
91
          MinVisitNumStack.back() = childNum;
 
92
      }
 
93
    }
 
94
  }
 
95
 
 
96
  // Compute the next SCC using the DFS traversal.
 
97
  void GetNextSCC() {
 
98
    assert(VisitStack.size() == MinVisitNumStack.size());
 
99
    CurrentSCC.clear();                 // Prepare to compute the next SCC
 
100
    while (!VisitStack.empty()) {
 
101
      DFSVisitChildren();
 
102
      assert(VisitStack.back().second ==GT::child_end(VisitStack.back().first));
 
103
      NodeType* visitingN = VisitStack.back().first;
 
104
      unsigned minVisitNum = MinVisitNumStack.back();
 
105
      VisitStack.pop_back();
 
106
      MinVisitNumStack.pop_back();
 
107
      if (!MinVisitNumStack.empty() && MinVisitNumStack.back() > minVisitNum)
 
108
        MinVisitNumStack.back() = minVisitNum;
 
109
 
 
110
      //dbgs() << "TarjanSCC: Popped node " << visitingN <<
 
111
      //      " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
 
112
      //      nodeVisitNumbers[visitingN] << "\n";
 
113
 
 
114
      if (minVisitNum == nodeVisitNumbers[visitingN]) {
 
115
        // A full SCC is on the SCCNodeStack!  It includes all nodes below
 
116
          // visitingN on the stack.  Copy those nodes to CurrentSCC,
 
117
          // reset their minVisit values, and return (this suspends
 
118
          // the DFS traversal till the next ++).
 
119
          do {
 
120
            CurrentSCC.push_back(SCCNodeStack.back());
 
121
            SCCNodeStack.pop_back();
 
122
            nodeVisitNumbers[CurrentSCC.back()] = ~0U;
 
123
          } while (CurrentSCC.back() != visitingN);
 
124
          return;
 
125
        }
 
126
    }
 
127
  }
 
128
 
 
129
  inline scc_iterator(NodeType *entryN) : visitNum(0) {
 
130
    DFSVisitOne(entryN);
 
131
    GetNextSCC();
 
132
  }
 
133
  inline scc_iterator() { /* End is when DFS stack is empty */ }
 
134
 
 
135
public:
 
136
  typedef scc_iterator<GraphT, GT> _Self;
 
137
 
 
138
  // Provide static "constructors"...
 
139
  static inline _Self begin(const GraphT& G) { return _Self(GT::getEntryNode(G)); }
 
140
  static inline _Self end  (const GraphT& G) { return _Self(); }
 
141
 
 
142
  // Direct loop termination test (I.fini() is more efficient than I == end())
 
143
  inline bool fini() const {
 
144
    assert(!CurrentSCC.empty() || VisitStack.empty());
 
145
    return CurrentSCC.empty();
 
146
  }
 
147
 
 
148
  inline bool operator==(const _Self& x) const {
 
149
    return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
 
150
  }
 
151
  inline bool operator!=(const _Self& x) const { return !operator==(x); }
 
152
 
 
153
  // Iterator traversal: forward iteration only
 
154
  inline _Self& operator++() {          // Preincrement
 
155
    GetNextSCC();
 
156
    return *this;
 
157
  }
 
158
  inline _Self operator++(int) {        // Postincrement
 
159
    _Self tmp = *this; ++*this; return tmp;
 
160
  }
 
161
 
 
162
  // Retrieve a reference to the current SCC
 
163
  inline const SccTy &operator*() const {
 
164
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
 
165
    return CurrentSCC;
 
166
  }
 
167
  inline SccTy &operator*() {
 
168
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
 
169
    return CurrentSCC;
 
170
  }
 
171
 
 
172
  // hasLoop() -- Test if the current SCC has a loop.  If it has more than one
 
173
  // node, this is trivially true.  If not, it may still contain a loop if the
 
174
  // node has an edge back to itself.
 
175
  bool hasLoop() const {
 
176
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
 
177
    if (CurrentSCC.size() > 1) return true;
 
178
    NodeType *N = CurrentSCC.front();
 
179
    for (ChildItTy CI = GT::child_begin(N), CE=GT::child_end(N); CI != CE; ++CI)
 
180
      if (*CI == N)
 
181
        return true;
 
182
    return false;
 
183
  }
 
184
};
 
185
 
 
186
 
 
187
// Global constructor for the SCC iterator.
 
188
template <class T>
 
189
scc_iterator<T> scc_begin(const T& G) {
 
190
  return scc_iterator<T>::begin(G);
 
191
}
 
192
 
 
193
template <class T>
 
194
scc_iterator<T> scc_end(const T& G) {
 
195
  return scc_iterator<T>::end(G);
 
196
}
 
197
 
 
198
template <class T>
 
199
scc_iterator<Inverse<T> > scc_begin(const Inverse<T>& G) {
 
200
       return scc_iterator<Inverse<T> >::begin(G);
 
201
}
 
202
 
 
203
template <class T>
 
204
scc_iterator<Inverse<T> > scc_end(const Inverse<T>& G) {
 
205
       return scc_iterator<Inverse<T> >::end(G);
 
206
}
 
207
 
 
208
} // End llvm namespace
 
209
 
 
210
#endif