← 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/FoldingSet.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/FoldingSet.h
 
1
//===-- llvm/ADT/FoldingSet.h - Uniquing Hash Set ---------------*- 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 defines a hash set that can be used to remove duplication of nodes
 
11
// in a graph.  This code was originally created by Chris Lattner for use with
 
12
// SelectionDAGCSEMap, but was isolated to provide use across the llvm code set.
 
13
//
 
14
//===----------------------------------------------------------------------===//
 
15
 
 
16
#ifndef LLVM_ADT_FOLDINGSET_H
 
17
#define LLVM_ADT_FOLDINGSET_H
 
18
 
 
19
#include "llvm/System/DataTypes.h"
 
20
#include "llvm/ADT/SmallVector.h"
 
21
#include "llvm/ADT/StringRef.h"
 
22
 
 
23
namespace llvm {
 
24
  class APFloat;
 
25
  class APInt;
 
26
 
 
27
/// This folding set used for two purposes:
 
28
///   1. Given information about a node we want to create, look up the unique
 
29
///      instance of the node in the set.  If the node already exists, return
 
30
///      it, otherwise return the bucket it should be inserted into.
 
31
///   2. Given a node that has already been created, remove it from the set.
 
32
///
 
33
/// This class is implemented as a single-link chained hash table, where the
 
34
/// "buckets" are actually the nodes themselves (the next pointer is in the
 
35
/// node).  The last node points back to the bucket to simplify node removal.
 
36
///
 
37
/// Any node that is to be included in the folding set must be a subclass of
 
38
/// FoldingSetNode.  The node class must also define a Profile method used to
 
39
/// establish the unique bits of data for the node.  The Profile method is
 
40
/// passed a FoldingSetNodeID object which is used to gather the bits.  Just
 
41
/// call one of the Add* functions defined in the FoldingSetImpl::NodeID class.
 
42
/// NOTE: That the folding set does not own the nodes and it is the
 
43
/// responsibility of the user to dispose of the nodes.
 
44
///
 
45
/// Eg.
 
46
///    class MyNode : public FoldingSetNode {
 
47
///    private:
 
48
///      std::string Name;
 
49
///      unsigned Value;
 
50
///    public:
 
51
///      MyNode(const char *N, unsigned V) : Name(N), Value(V) {}
 
52
///       ...
 
53
///      void Profile(FoldingSetNodeID &ID) const {
 
54
///        ID.AddString(Name);
 
55
///        ID.AddInteger(Value);
 
56
///       }
 
57
///       ...
 
58
///     };
 
59
///
 
60
/// To define the folding set itself use the FoldingSet template;
 
61
///
 
62
/// Eg.
 
63
///    FoldingSet<MyNode> MyFoldingSet;
 
64
///
 
65
/// Four public methods are available to manipulate the folding set;
 
66
///
 
67
/// 1) If you have an existing node that you want add to the set but unsure
 
68
/// that the node might already exist then call;
 
69
///
 
70
///    MyNode *M = MyFoldingSet.GetOrInsertNode(N);
 
71
///
 
72
/// If The result is equal to the input then the node has been inserted.
 
73
/// Otherwise, the result is the node existing in the folding set, and the
 
74
/// input can be discarded (use the result instead.)
 
75
///
 
76
/// 2) If you are ready to construct a node but want to check if it already
 
77
/// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to
 
78
/// check;
 
79
///
 
80
///   FoldingSetNodeID ID;
 
81
///   ID.AddString(Name);
 
82
///   ID.AddInteger(Value);
 
83
///   void *InsertPoint;
 
84
///
 
85
///    MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint);
 
86
///
 
87
/// If found then M with be non-NULL, else InsertPoint will point to where it
 
88
/// should be inserted using InsertNode.
 
89
///
 
90
/// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new
 
91
/// node with FindNodeOrInsertPos;
 
92
///
 
93
///    InsertNode(N, InsertPoint);
 
94
///
 
95
/// 4) Finally, if you want to remove a node from the folding set call;
 
96
///
 
97
///    bool WasRemoved = RemoveNode(N);
 
98
///
 
99
/// The result indicates whether the node existed in the folding set.
 
100
 
 
101
class FoldingSetNodeID;
 
102
 
 
103
//===----------------------------------------------------------------------===//
 
104
/// FoldingSetImpl - Implements the folding set functionality.  The main
 
105
/// structure is an array of buckets.  Each bucket is indexed by the hash of
 
106
/// the nodes it contains.  The bucket itself points to the nodes contained
 
107
/// in the bucket via a singly linked list.  The last node in the list points
 
108
/// back to the bucket to facilitate node removal.
 
109
///
 
110
class FoldingSetImpl {
 
111
protected:
 
112
  /// Buckets - Array of bucket chains.
 
113
  ///
 
114
  void **Buckets;
 
115
 
 
116
  /// NumBuckets - Length of the Buckets array.  Always a power of 2.
 
117
  ///
 
118
  unsigned NumBuckets;
 
119
 
 
120
  /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes
 
121
  /// is greater than twice the number of buckets.
 
122
  unsigned NumNodes;
 
123
 
 
124
public:
 
125
  explicit FoldingSetImpl(unsigned Log2InitSize = 6);
 
126
  virtual ~FoldingSetImpl();
 
127
 
 
128
  //===--------------------------------------------------------------------===//
 
129
  /// Node - This class is used to maintain the singly linked bucket list in
 
130
  /// a folding set.
 
131
  ///
 
132
  class Node {
 
133
  private:
 
134
    // NextInFoldingSetBucket - next link in the bucket list.
 
135
    void *NextInFoldingSetBucket;
 
136
 
 
137
  public:
 
138
 
 
139
    Node() : NextInFoldingSetBucket(0) {}
 
140
 
 
141
    // Accessors
 
142
    void *getNextInBucket() const { return NextInFoldingSetBucket; }
 
143
    void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; }
 
144
  };
 
145
 
 
146
  /// clear - Remove all nodes from the folding set.
 
147
  void clear();
 
148
 
 
149
  /// RemoveNode - Remove a node from the folding set, returning true if one
 
150
  /// was removed or false if the node was not in the folding set.
 
151
  bool RemoveNode(Node *N);
 
152
 
 
153
  /// GetOrInsertNode - If there is an existing simple Node exactly
 
154
  /// equal to the specified node, return it.  Otherwise, insert 'N' and return
 
155
  /// it instead.
 
156
  Node *GetOrInsertNode(Node *N);
 
157
 
 
158
  /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
 
159
  /// return it.  If not, return the insertion token that will make insertion
 
160
  /// faster.
 
161
  Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
 
162
 
 
163
  /// InsertNode - Insert the specified node into the folding set, knowing that
 
164
  /// it is not already in the folding set.  InsertPos must be obtained from
 
165
  /// FindNodeOrInsertPos.
 
166
  void InsertNode(Node *N, void *InsertPos);
 
167
 
 
168
  /// size - Returns the number of nodes in the folding set.
 
169
  unsigned size() const { return NumNodes; }
 
170
 
 
171
  /// empty - Returns true if there are no nodes in the folding set.
 
172
  bool empty() const { return NumNodes == 0; }
 
173
 
 
174
private:
 
175
 
 
176
  /// GrowHashTable - Double the size of the hash table and rehash everything.
 
177
  ///
 
178
  void GrowHashTable();
 
179
 
 
180
protected:
 
181
 
 
182
  /// GetNodeProfile - Instantiations of the FoldingSet template implement
 
183
  /// this function to gather data bits for the given node.
 
184
  virtual void GetNodeProfile(FoldingSetNodeID &ID, Node *N) const = 0;
 
185
};
 
186
 
 
187
//===----------------------------------------------------------------------===//
 
188
/// FoldingSetTrait - This trait class is used to define behavior of how
 
189
///  to "profile" (in the FoldingSet parlance) an object of a given type.
 
190
///  The default behavior is to invoke a 'Profile' method on an object, but
 
191
///  through template specialization the behavior can be tailored for specific
 
192
///  types.  Combined with the FoldingSetNodeWrapper classs, one can add objects
 
193
///  to FoldingSets that were not originally designed to have that behavior.
 
194
///
 
195
template<typename T> struct FoldingSetTrait {
 
196
  static inline void Profile(const T& X, FoldingSetNodeID& ID) { X.Profile(ID);}
 
197
  static inline void Profile(T& X, FoldingSetNodeID& ID) { X.Profile(ID); }
 
198
};
 
199
 
 
200
//===--------------------------------------------------------------------===//
 
201
/// FoldingSetNodeID - This class is used to gather all the unique data bits of
 
202
/// a node.  When all the bits are gathered this class is used to produce a
 
203
/// hash value for the node.
 
204
///
 
205
class FoldingSetNodeID {
 
206
  /// Bits - Vector of all the data bits that make the node unique.
 
207
  /// Use a SmallVector to avoid a heap allocation in the common case.
 
208
  SmallVector<unsigned, 32> Bits;
 
209
 
 
210
public:
 
211
  FoldingSetNodeID() {}
 
212
 
 
213
  /// getRawData - Return the ith entry in the Bits data.
 
214
  ///
 
215
  unsigned getRawData(unsigned i) const {
 
216
    return Bits[i];
 
217
  }
 
218
 
 
219
  /// Add* - Add various data types to Bit data.
 
220
  ///
 
221
  void AddPointer(const void *Ptr);
 
222
  void AddInteger(signed I);
 
223
  void AddInteger(unsigned I);
 
224
  void AddInteger(long I);
 
225
  void AddInteger(unsigned long I);
 
226
  void AddInteger(long long I);
 
227
  void AddInteger(unsigned long long I);
 
228
  void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); }
 
229
  void AddString(StringRef String);
 
230
 
 
231
  template <typename T>
 
232
  inline void Add(const T& x) { FoldingSetTrait<T>::Profile(x, *this); }
 
233
 
 
234
  /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
 
235
  ///  object to be used to compute a new profile.
 
236
  inline void clear() { Bits.clear(); }
 
237
 
 
238
  /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
 
239
  ///  to lookup the node in the FoldingSetImpl.
 
240
  unsigned ComputeHash() const;
 
241
 
 
242
  /// operator== - Used to compare two nodes to each other.
 
243
  ///
 
244
  bool operator==(const FoldingSetNodeID &RHS) const;
 
245
};
 
246
 
 
247
// Convenience type to hide the implementation of the folding set.
 
248
typedef FoldingSetImpl::Node FoldingSetNode;
 
249
template<class T> class FoldingSetIterator;
 
250
template<class T> class FoldingSetBucketIterator;
 
251
 
 
252
//===----------------------------------------------------------------------===//
 
253
/// FoldingSet - This template class is used to instantiate a specialized
 
254
/// implementation of the folding set to the node class T.  T must be a
 
255
/// subclass of FoldingSetNode and implement a Profile function.
 
256
///
 
257
template<class T> class FoldingSet : public FoldingSetImpl {
 
258
private:
 
259
  /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
 
260
  /// way to convert nodes into a unique specifier.
 
261
  virtual void GetNodeProfile(FoldingSetNodeID &ID, Node *N) const {
 
262
    T *TN = static_cast<T *>(N);
 
263
    FoldingSetTrait<T>::Profile(*TN,ID);
 
264
  }
 
265
 
 
266
public:
 
267
  explicit FoldingSet(unsigned Log2InitSize = 6)
 
268
  : FoldingSetImpl(Log2InitSize)
 
269
  {}
 
270
 
 
271
  typedef FoldingSetIterator<T> iterator;
 
272
  iterator begin() { return iterator(Buckets); }
 
273
  iterator end() { return iterator(Buckets+NumBuckets); }
 
274
 
 
275
  typedef FoldingSetIterator<const T> const_iterator;
 
276
  const_iterator begin() const { return const_iterator(Buckets); }
 
277
  const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
 
278
 
 
279
  typedef FoldingSetBucketIterator<T> bucket_iterator;
 
280
 
 
281
  bucket_iterator bucket_begin(unsigned hash) {
 
282
    return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
 
283
  }
 
284
 
 
285
  bucket_iterator bucket_end(unsigned hash) {
 
286
    return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
 
287
  }
 
288
 
 
289
  /// GetOrInsertNode - If there is an existing simple Node exactly
 
290
  /// equal to the specified node, return it.  Otherwise, insert 'N' and
 
291
  /// return it instead.
 
292
  T *GetOrInsertNode(Node *N) {
 
293
    return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N));
 
294
  }
 
295
 
 
296
  /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
 
297
  /// return it.  If not, return the insertion token that will make insertion
 
298
  /// faster.
 
299
  T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
 
300
    return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos));
 
301
  }
 
302
};
 
303
 
 
304
//===----------------------------------------------------------------------===//
 
305
/// FoldingSetIteratorImpl - This is the common iterator support shared by all
 
306
/// folding sets, which knows how to walk the folding set hash table.
 
307
class FoldingSetIteratorImpl {
 
308
protected:
 
309
  FoldingSetNode *NodePtr;
 
310
  FoldingSetIteratorImpl(void **Bucket);
 
311
  void advance();
 
312
 
 
313
public:
 
314
  bool operator==(const FoldingSetIteratorImpl &RHS) const {
 
315
    return NodePtr == RHS.NodePtr;
 
316
  }
 
317
  bool operator!=(const FoldingSetIteratorImpl &RHS) const {
 
318
    return NodePtr != RHS.NodePtr;
 
319
  }
 
320
};
 
321
 
 
322
 
 
323
template<class T>
 
324
class FoldingSetIterator : public FoldingSetIteratorImpl {
 
325
public:
 
326
  explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
 
327
 
 
328
  T &operator*() const {
 
329
    return *static_cast<T*>(NodePtr);
 
330
  }
 
331
 
 
332
  T *operator->() const {
 
333
    return static_cast<T*>(NodePtr);
 
334
  }
 
335
 
 
336
  inline FoldingSetIterator& operator++() {          // Preincrement
 
337
    advance();
 
338
    return *this;
 
339
  }
 
340
  FoldingSetIterator operator++(int) {        // Postincrement
 
341
    FoldingSetIterator tmp = *this; ++*this; return tmp;
 
342
  }
 
343
};
 
344
 
 
345
//===----------------------------------------------------------------------===//
 
346
/// FoldingSetBucketIteratorImpl - This is the common bucket iterator support
 
347
///  shared by all folding sets, which knows how to walk a particular bucket
 
348
///  of a folding set hash table.
 
349
 
 
350
class FoldingSetBucketIteratorImpl {
 
351
protected:
 
352
  void *Ptr;
 
353
 
 
354
  explicit FoldingSetBucketIteratorImpl(void **Bucket);
 
355
 
 
356
  FoldingSetBucketIteratorImpl(void **Bucket, bool)
 
357
    : Ptr(Bucket) {}
 
358
 
 
359
  void advance() {
 
360
    void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket();
 
361
    uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
 
362
    Ptr = reinterpret_cast<void*>(x);
 
363
  }
 
364
 
 
365
public:
 
366
  bool operator==(const FoldingSetBucketIteratorImpl &RHS) const {
 
367
    return Ptr == RHS.Ptr;
 
368
  }
 
369
  bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const {
 
370
    return Ptr != RHS.Ptr;
 
371
  }
 
372
};
 
373
 
 
374
 
 
375
template<class T>
 
376
class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
 
377
public:
 
378
  explicit FoldingSetBucketIterator(void **Bucket) :
 
379
    FoldingSetBucketIteratorImpl(Bucket) {}
 
380
 
 
381
  FoldingSetBucketIterator(void **Bucket, bool) :
 
382
    FoldingSetBucketIteratorImpl(Bucket, true) {}
 
383
 
 
384
  T& operator*() const { return *static_cast<T*>(Ptr); }
 
385
  T* operator->() const { return static_cast<T*>(Ptr); }
 
386
 
 
387
  inline FoldingSetBucketIterator& operator++() { // Preincrement
 
388
    advance();
 
389
    return *this;
 
390
  }
 
391
  FoldingSetBucketIterator operator++(int) {      // Postincrement
 
392
    FoldingSetBucketIterator tmp = *this; ++*this; return tmp;
 
393
  }
 
394
};
 
395
 
 
396
//===----------------------------------------------------------------------===//
 
397
/// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary
 
398
/// types in an enclosing object so that they can be inserted into FoldingSets.
 
399
template <typename T>
 
400
class FoldingSetNodeWrapper : public FoldingSetNode {
 
401
  T data;
 
402
public:
 
403
  explicit FoldingSetNodeWrapper(const T& x) : data(x) {}
 
404
  virtual ~FoldingSetNodeWrapper() {}
 
405
 
 
406
  template<typename A1>
 
407
  explicit FoldingSetNodeWrapper(const A1& a1)
 
408
    : data(a1) {}
 
409
 
 
410
  template <typename A1, typename A2>
 
411
  explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2)
 
412
    : data(a1,a2) {}
 
413
 
 
414
  template <typename A1, typename A2, typename A3>
 
415
  explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3)
 
416
    : data(a1,a2,a3) {}
 
417
 
 
418
  template <typename A1, typename A2, typename A3, typename A4>
 
419
  explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3,
 
420
                                 const A4& a4)
 
421
    : data(a1,a2,a3,a4) {}
 
422
 
 
423
  template <typename A1, typename A2, typename A3, typename A4, typename A5>
 
424
  explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3,
 
425
                                 const A4& a4, const A5& a5)
 
426
  : data(a1,a2,a3,a4,a5) {}
 
427
 
 
428
 
 
429
  void Profile(FoldingSetNodeID& ID) { FoldingSetTrait<T>::Profile(data, ID); }
 
430
 
 
431
  T& getValue() { return data; }
 
432
  const T& getValue() const { return data; }
 
433
 
 
434
  operator T&() { return data; }
 
435
  operator const T&() const { return data; }
 
436
};
 
437
 
 
438
//===----------------------------------------------------------------------===//
 
439
/// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores
 
440
/// a FoldingSetNodeID value rather than requiring the node to recompute it
 
441
/// each time it is needed. This trades space for speed (which can be
 
442
/// significant if the ID is long), and it also permits nodes to drop
 
443
/// information that would otherwise only be required for recomputing an ID.
 
444
class FastFoldingSetNode : public FoldingSetNode {
 
445
  FoldingSetNodeID FastID;
 
446
protected:
 
447
  explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
 
448
public:
 
449
  void Profile(FoldingSetNodeID& ID) { ID = FastID; }
 
450
};
 
451
 
 
452
//===----------------------------------------------------------------------===//
 
453
// Partial specializations of FoldingSetTrait.
 
454
 
 
455
template<typename T> struct FoldingSetTrait<T*> {
 
456
  static inline void Profile(const T* X, FoldingSetNodeID& ID) {
 
457
    ID.AddPointer(X);
 
458
  }
 
459
  static inline void Profile(T* X, FoldingSetNodeID& ID) {
 
460
    ID.AddPointer(X);
 
461
  }
 
462
};
 
463
 
 
464
template<typename T> struct FoldingSetTrait<const T*> {
 
465
  static inline void Profile(const T* X, FoldingSetNodeID& ID) {
 
466
    ID.AddPointer(X);
 
467
  }
 
468
};
 
469
 
 
470
} // End of namespace llvm.
 
471
 
 
472
#endif