← 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/EquivalenceClasses.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/EquivalenceClasses.h
 
1
//===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- 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
// Generic implementation of equivalence classes through the use Tarjan's
 
11
// efficient union-find algorithm.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#ifndef LLVM_ADT_EQUIVALENCECLASSES_H
 
16
#define LLVM_ADT_EQUIVALENCECLASSES_H
 
17
 
 
18
#include "llvm/System/DataTypes.h"
 
19
#include <cassert>
 
20
#include <set>
 
21
 
 
22
namespace llvm {
 
23
 
 
24
/// EquivalenceClasses - This represents a collection of equivalence classes and
 
25
/// supports three efficient operations: insert an element into a class of its
 
26
/// own, union two classes, and find the class for a given element.  In
 
27
/// addition to these modification methods, it is possible to iterate over all
 
28
/// of the equivalence classes and all of the elements in a class.
 
29
///
 
30
/// This implementation is an efficient implementation that only stores one copy
 
31
/// of the element being indexed per entry in the set, and allows any arbitrary
 
32
/// type to be indexed (as long as it can be ordered with operator<).
 
33
///
 
34
/// Here is a simple example using integers:
 
35
///
 
36
///  EquivalenceClasses<int> EC;
 
37
///  EC.unionSets(1, 2);                // insert 1, 2 into the same set
 
38
///  EC.insert(4); EC.insert(5);        // insert 4, 5 into own sets
 
39
///  EC.unionSets(5, 1);                // merge the set for 1 with 5's set.
 
40
///
 
41
///  for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end();
 
42
///       I != E; ++I) {           // Iterate over all of the equivalence sets.
 
43
///    if (!I->isLeader()) continue;   // Ignore non-leader sets.
 
44
///    for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I);
 
45
///         MI != EC.member_end(); ++MI)   // Loop over members in this set.
 
46
///      cerr << *MI << " ";  // Print member.
 
47
///    cerr << "\n";   // Finish set.
 
48
///  }
 
49
///
 
50
/// This example prints:
 
51
///   4
 
52
///   5 1 2
 
53
///
 
54
template <class ElemTy>
 
55
class EquivalenceClasses {
 
56
  /// ECValue - The EquivalenceClasses data structure is just a set of these.
 
57
  /// Each of these represents a relation for a value.  First it stores the
 
58
  /// value itself, which provides the ordering that the set queries.  Next, it
 
59
  /// provides a "next pointer", which is used to enumerate all of the elements
 
60
  /// in the unioned set.  Finally, it defines either a "end of list pointer" or
 
61
  /// "leader pointer" depending on whether the value itself is a leader.  A
 
62
  /// "leader pointer" points to the node that is the leader for this element,
 
63
  /// if the node is not a leader.  A "end of list pointer" points to the last
 
64
  /// node in the list of members of this list.  Whether or not a node is a
 
65
  /// leader is determined by a bit stolen from one of the pointers.
 
66
  class ECValue {
 
67
    friend class EquivalenceClasses;
 
68
    mutable const ECValue *Leader, *Next;
 
69
    ElemTy Data;
 
70
    // ECValue ctor - Start out with EndOfList pointing to this node, Next is
 
71
    // Null, isLeader = true.
 
72
    ECValue(const ElemTy &Elt)
 
73
      : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {}
 
74
 
 
75
    const ECValue *getLeader() const {
 
76
      if (isLeader()) return this;
 
77
      if (Leader->isLeader()) return Leader;
 
78
      // Path compression.
 
79
      return Leader = Leader->getLeader();
 
80
    }
 
81
    const ECValue *getEndOfList() const {
 
82
      assert(isLeader() && "Cannot get the end of a list for a non-leader!");
 
83
      return Leader;
 
84
    }
 
85
 
 
86
    void setNext(const ECValue *NewNext) const {
 
87
      assert(getNext() == 0 && "Already has a next pointer!");
 
88
      Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader());
 
89
    }
 
90
  public:
 
91
    ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1),
 
92
                                  Data(RHS.Data) {
 
93
      // Only support copying of singleton nodes.
 
94
      assert(RHS.isLeader() && RHS.getNext() == 0 && "Not a singleton!");
 
95
    }
 
96
 
 
97
    bool operator<(const ECValue &UFN) const { return Data < UFN.Data; }
 
98
 
 
99
    bool isLeader() const { return (intptr_t)Next & 1; }
 
100
    const ElemTy &getData() const { return Data; }
 
101
 
 
102
    const ECValue *getNext() const {
 
103
      return (ECValue*)((intptr_t)Next & ~(intptr_t)1);
 
104
    }
 
105
 
 
106
    template<typename T>
 
107
    bool operator<(const T &Val) const { return Data < Val; }
 
108
  };
 
109
 
 
110
  /// TheMapping - This implicitly provides a mapping from ElemTy values to the
 
111
  /// ECValues, it just keeps the key as part of the value.
 
112
  std::set<ECValue> TheMapping;
 
113
 
 
114
public:
 
115
  EquivalenceClasses() {}
 
116
  EquivalenceClasses(const EquivalenceClasses &RHS) {
 
117
    operator=(RHS);
 
118
  }
 
119
 
 
120
  const EquivalenceClasses &operator=(const EquivalenceClasses &RHS) {
 
121
    TheMapping.clear();
 
122
    for (iterator I = RHS.begin(), E = RHS.end(); I != E; ++I)
 
123
      if (I->isLeader()) {
 
124
        member_iterator MI = RHS.member_begin(I);
 
125
        member_iterator LeaderIt = member_begin(insert(*MI));
 
126
        for (++MI; MI != member_end(); ++MI)
 
127
          unionSets(LeaderIt, member_begin(insert(*MI)));
 
128
      }
 
129
    return *this;
 
130
  }
 
131
 
 
132
  //===--------------------------------------------------------------------===//
 
133
  // Inspection methods
 
134
  //
 
135
 
 
136
  /// iterator* - Provides a way to iterate over all values in the set.
 
137
  typedef typename std::set<ECValue>::const_iterator iterator;
 
138
  iterator begin() const { return TheMapping.begin(); }
 
139
  iterator end() const { return TheMapping.end(); }
 
140
 
 
141
  bool empty() const { return TheMapping.empty(); }
 
142
 
 
143
  /// member_* Iterate over the members of an equivalence class.
 
144
  ///
 
145
  class member_iterator;
 
146
  member_iterator member_begin(iterator I) const {
 
147
    // Only leaders provide anything to iterate over.
 
148
    return member_iterator(I->isLeader() ? &*I : 0);
 
149
  }
 
150
  member_iterator member_end() const {
 
151
    return member_iterator(0);
 
152
  }
 
153
 
 
154
  /// findValue - Return an iterator to the specified value.  If it does not
 
155
  /// exist, end() is returned.
 
156
  iterator findValue(const ElemTy &V) const {
 
157
    return TheMapping.find(V);
 
158
  }
 
159
 
 
160
  /// getLeaderValue - Return the leader for the specified value that is in the
 
161
  /// set.  It is an error to call this method for a value that is not yet in
 
162
  /// the set.  For that, call getOrInsertLeaderValue(V).
 
163
  const ElemTy &getLeaderValue(const ElemTy &V) const {
 
164
    member_iterator MI = findLeader(V);
 
165
    assert(MI != member_end() && "Value is not in the set!");
 
166
    return *MI;
 
167
  }
 
168
 
 
169
  /// getOrInsertLeaderValue - Return the leader for the specified value that is
 
170
  /// in the set.  If the member is not in the set, it is inserted, then
 
171
  /// returned.
 
172
  const ElemTy &getOrInsertLeaderValue(const ElemTy &V) {
 
173
    member_iterator MI = findLeader(insert(V));
 
174
    assert(MI != member_end() && "Value is not in the set!");
 
175
    return *MI;
 
176
  }
 
177
 
 
178
  /// getNumClasses - Return the number of equivalence classes in this set.
 
179
  /// Note that this is a linear time operation.
 
180
  unsigned getNumClasses() const {
 
181
    unsigned NC = 0;
 
182
    for (iterator I = begin(), E = end(); I != E; ++I)
 
183
      if (I->isLeader()) ++NC;
 
184
    return NC;
 
185
  }
 
186
 
 
187
 
 
188
  //===--------------------------------------------------------------------===//
 
189
  // Mutation methods
 
190
 
 
191
  /// insert - Insert a new value into the union/find set, ignoring the request
 
192
  /// if the value already exists.
 
193
  iterator insert(const ElemTy &Data) {
 
194
    return TheMapping.insert(ECValue(Data)).first;
 
195
  }
 
196
 
 
197
  /// findLeader - Given a value in the set, return a member iterator for the
 
198
  /// equivalence class it is in.  This does the path-compression part that
 
199
  /// makes union-find "union findy".  This returns an end iterator if the value
 
200
  /// is not in the equivalence class.
 
201
  ///
 
202
  member_iterator findLeader(iterator I) const {
 
203
    if (I == TheMapping.end()) return member_end();
 
204
    return member_iterator(I->getLeader());
 
205
  }
 
206
  member_iterator findLeader(const ElemTy &V) const {
 
207
    return findLeader(TheMapping.find(V));
 
208
  }
 
209
 
 
210
 
 
211
  /// union - Merge the two equivalence sets for the specified values, inserting
 
212
  /// them if they do not already exist in the equivalence set.
 
213
  member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) {
 
214
    iterator V1I = insert(V1), V2I = insert(V2);
 
215
    return unionSets(findLeader(V1I), findLeader(V2I));
 
216
  }
 
217
  member_iterator unionSets(member_iterator L1, member_iterator L2) {
 
218
    assert(L1 != member_end() && L2 != member_end() && "Illegal inputs!");
 
219
    if (L1 == L2) return L1;   // Unifying the same two sets, noop.
 
220
 
 
221
    // Otherwise, this is a real union operation.  Set the end of the L1 list to
 
222
    // point to the L2 leader node.
 
223
    const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node;
 
224
    L1LV.getEndOfList()->setNext(&L2LV);
 
225
 
 
226
    // Update L1LV's end of list pointer.
 
227
    L1LV.Leader = L2LV.getEndOfList();
 
228
 
 
229
    // Clear L2's leader flag:
 
230
    L2LV.Next = L2LV.getNext();
 
231
 
 
232
    // L2's leader is now L1.
 
233
    L2LV.Leader = &L1LV;
 
234
    return L1;
 
235
  }
 
236
 
 
237
  class member_iterator : public std::iterator<std::forward_iterator_tag,
 
238
                                               const ElemTy, ptrdiff_t> {
 
239
    typedef std::iterator<std::forward_iterator_tag,
 
240
                          const ElemTy, ptrdiff_t> super;
 
241
    const ECValue *Node;
 
242
    friend class EquivalenceClasses;
 
243
  public:
 
244
    typedef size_t size_type;
 
245
    typedef typename super::pointer pointer;
 
246
    typedef typename super::reference reference;
 
247
 
 
248
    explicit member_iterator() {}
 
249
    explicit member_iterator(const ECValue *N) : Node(N) {}
 
250
    member_iterator(const member_iterator &I) : Node(I.Node) {}
 
251
 
 
252
    reference operator*() const {
 
253
      assert(Node != 0 && "Dereferencing end()!");
 
254
      return Node->getData();
 
255
    }
 
256
    reference operator->() const { return operator*(); }
 
257
 
 
258
    member_iterator &operator++() {
 
259
      assert(Node != 0 && "++'d off the end of the list!");
 
260
      Node = Node->getNext();
 
261
      return *this;
 
262
    }
 
263
 
 
264
    member_iterator operator++(int) {    // postincrement operators.
 
265
      member_iterator tmp = *this;
 
266
      ++*this;
 
267
      return tmp;
 
268
    }
 
269
 
 
270
    bool operator==(const member_iterator &RHS) const {
 
271
      return Node == RHS.Node;
 
272
    }
 
273
    bool operator!=(const member_iterator &RHS) const {
 
274
      return Node != RHS.Node;
 
275
    }
 
276
  };
 
277
};
 
278
 
 
279
} // End llvm namespace
 
280
 
 
281
#endif