← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

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
        continue;
 
89
      }
 
90
      
 
91
      unsigned childNum = nodeVisitNumbers[childN];
 
92
      if (MinVisitNumStack.back() > childNum)
 
93
        MinVisitNumStack.back() = childNum;
 
94
    }
 
95
  }
 
96
 
 
97
  // Compute the next SCC using the DFS traversal.
 
98
  void GetNextSCC() {
 
99
    assert(VisitStack.size() == MinVisitNumStack.size());
 
100
    CurrentSCC.clear();                 // Prepare to compute the next SCC
 
101
    while (!VisitStack.empty()) {
 
102
      DFSVisitChildren();
 
103
      assert(VisitStack.back().second ==GT::child_end(VisitStack.back().first));
 
104
      NodeType *visitingN = VisitStack.back().first;
 
105
      unsigned minVisitNum = MinVisitNumStack.back();
 
106
      VisitStack.pop_back();
 
107
      MinVisitNumStack.pop_back();
 
108
      if (!MinVisitNumStack.empty() && MinVisitNumStack.back() > minVisitNum)
 
109
        MinVisitNumStack.back() = minVisitNum;
 
110
 
 
111
      //dbgs() << "TarjanSCC: Popped node " << visitingN <<
 
112
      //      " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
 
113
      //      nodeVisitNumbers[visitingN] << "\n";
 
114
 
 
115
      if (minVisitNum != nodeVisitNumbers[visitingN])
 
116
        continue;
 
117
      
 
118
      // A full SCC is on the SCCNodeStack!  It includes all nodes below
 
119
      // visitingN on the stack.  Copy those nodes to CurrentSCC,
 
120
      // reset their minVisit values, and return (this suspends
 
121
      // the DFS traversal till the next ++).
 
122
      do {
 
123
        CurrentSCC.push_back(SCCNodeStack.back());
 
124
        SCCNodeStack.pop_back();
 
125
        nodeVisitNumbers[CurrentSCC.back()] = ~0U;
 
126
      } while (CurrentSCC.back() != visitingN);
 
127
      return;
 
128
    }
 
129
  }
 
130
 
 
131
  inline scc_iterator(NodeType *entryN) : visitNum(0) {
 
132
    DFSVisitOne(entryN);
 
133
    GetNextSCC();
 
134
  }
 
135
  inline scc_iterator() { /* End is when DFS stack is empty */ }
 
136
 
 
137
public:
 
138
  typedef scc_iterator<GraphT, GT> _Self;
 
139
 
 
140
  // Provide static "constructors"...
 
141
  static inline _Self begin(const GraphT &G){return _Self(GT::getEntryNode(G));}
 
142
  static inline _Self end  (const GraphT &G) { return _Self(); }
 
143
 
 
144
  // Direct loop termination test: I.isAtEnd() is more efficient than I == end()
 
145
  inline bool isAtEnd() const {
 
146
    assert(!CurrentSCC.empty() || VisitStack.empty());
 
147
    return CurrentSCC.empty();
 
148
  }
 
149
 
 
150
  inline bool operator==(const _Self& x) const {
 
151
    return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
 
152
  }
 
153
  inline bool operator!=(const _Self& x) const { return !operator==(x); }
 
154
 
 
155
  // Iterator traversal: forward iteration only
 
156
  inline _Self& operator++() {          // Preincrement
 
157
    GetNextSCC();
 
158
    return *this;
 
159
  }
 
160
  inline _Self operator++(int) {        // Postincrement
 
161
    _Self tmp = *this; ++*this; return tmp;
 
162
  }
 
163
 
 
164
  // Retrieve a reference to the current SCC
 
165
  inline const SccTy &operator*() const {
 
166
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
 
167
    return CurrentSCC;
 
168
  }
 
169
  inline SccTy &operator*() {
 
170
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
 
171
    return CurrentSCC;
 
172
  }
 
173
 
 
174
  // hasLoop() -- Test if the current SCC has a loop.  If it has more than one
 
175
  // node, this is trivially true.  If not, it may still contain a loop if the
 
176
  // node has an edge back to itself.
 
177
  bool hasLoop() const {
 
178
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
 
179
    if (CurrentSCC.size() > 1) return true;
 
180
    NodeType *N = CurrentSCC.front();
 
181
    for (ChildItTy CI = GT::child_begin(N), CE=GT::child_end(N); CI != CE; ++CI)
 
182
      if (*CI == N)
 
183
        return true;
 
184
    return false;
 
185
  }
 
186
                           
 
187
  /// ReplaceNode - This informs the scc_iterator that the specified Old node
 
188
  /// has been deleted, and New is to be used in its place.
 
189
  void ReplaceNode(NodeType *Old, NodeType *New) {
 
190
    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
 
191
    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
 
192
    nodeVisitNumbers.erase(Old);
 
193
  }
 
194
};
 
195
 
 
196
 
 
197
// Global constructor for the SCC iterator.
 
198
template <class T>
 
199
scc_iterator<T> scc_begin(const T &G) {
 
200
  return scc_iterator<T>::begin(G);
 
201
}
 
202
 
 
203
template <class T>
 
204
scc_iterator<T> scc_end(const T &G) {
 
205
  return scc_iterator<T>::end(G);
 
206
}
 
207
 
 
208
template <class T>
 
209
scc_iterator<Inverse<T> > scc_begin(const Inverse<T> &G) {
 
210
  return scc_iterator<Inverse<T> >::begin(G);
 
211
}
 
212
 
 
213
template <class T>
 
214
scc_iterator<Inverse<T> > scc_end(const Inverse<T> &G) {
 
215
  return scc_iterator<Inverse<T> >::end(G);
 
216
}
 
217
 
 
218
} // End llvm namespace
 
219
 
 
220
#endif