← Back to branch summary

~ubuntu-branches/ubuntu/maverick/clamav/maverick-backports

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Stephen Gran, Stephen Gran, Michael Tautschnig
  • Date: 2010-04-26 21:41:18 UTC
  • mfrom: (2.1.6 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100426214118-i6lo606wnh7ywfj6
Tags: 0.96+dfsg-4
http://bugs.debian.org/579271
http://bugs.debian.org/579068
[ Stephen Gran ]
* Fixed typo in clamav-milter's postinst

[ Michael Tautschnig ]
* Fixed typo in clamav-freshclam's postinst (closes: #579271)
* Debconf translation updates
  - Portuguese (closes: #579068)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/include/llvm/ADT/SmallPtrSet.h
 
1
//===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer 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 the SmallPtrSet class.  See the doxygen comment for
 
11
// SmallPtrSetImpl for more details on the algorithm used.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#ifndef LLVM_ADT_SMALLPTRSET_H
 
16
#define LLVM_ADT_SMALLPTRSET_H
 
17
 
 
18
#include <cassert>
 
19
#include <cstring>
 
20
#include <iterator>
 
21
#include "llvm/System/DataTypes.h"
 
22
#include "llvm/Support/PointerLikeTypeTraits.h"
 
23
 
 
24
namespace llvm {
 
25
 
 
26
class SmallPtrSetIteratorImpl;
 
27
 
 
28
/// SmallPtrSetImpl - This is the common code shared among all the
 
29
/// SmallPtrSet<>'s, which is almost everything.  SmallPtrSet has two modes, one
 
30
/// for small and one for large sets.
 
31
///
 
32
/// Small sets use an array of pointers allocated in the SmallPtrSet object,
 
33
/// which is treated as a simple array of pointers.  When a pointer is added to
 
34
/// the set, the array is scanned to see if the element already exists, if not
 
35
/// the element is 'pushed back' onto the array.  If we run out of space in the
 
36
/// array, we grow into the 'large set' case.  SmallSet should be used when the
 
37
/// sets are often small.  In this case, no memory allocation is used, and only
 
38
/// light-weight and cache-efficient scanning is used.
 
39
///
 
40
/// Large sets use a classic exponentially-probed hash table.  Empty buckets are
 
41
/// represented with an illegal pointer value (-1) to allow null pointers to be
 
42
/// inserted.  Tombstones are represented with another illegal pointer value
 
43
/// (-2), to allow deletion.  The hash table is resized when the table is 3/4 or
 
44
/// more.  When this happens, the table is doubled in size.
 
45
///
 
46
class SmallPtrSetImpl {
 
47
  friend class SmallPtrSetIteratorImpl;
 
48
protected:
 
49
  /// CurArray - This is the current set of buckets.  If it points to
 
50
  /// SmallArray, then the set is in 'small mode'.
 
51
  const void **CurArray;
 
52
  /// CurArraySize - The allocated size of CurArray, always a power of two.
 
53
  /// Note that CurArray points to an array that has CurArraySize+1 elements in
 
54
  /// it, so that the end iterator actually points to valid memory.
 
55
  unsigned CurArraySize;
 
56
 
 
57
  // If small, this is # elts allocated consequtively
 
58
  unsigned NumElements;
 
59
  unsigned NumTombstones;
 
60
  const void *SmallArray[1];  // Must be last ivar.
 
61
 
 
62
  // Helper to copy construct a SmallPtrSet.
 
63
  SmallPtrSetImpl(const SmallPtrSetImpl& that);
 
64
  explicit SmallPtrSetImpl(unsigned SmallSize) {
 
65
    assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
 
66
           "Initial size must be a power of two!");
 
67
    CurArray = &SmallArray[0];
 
68
    CurArraySize = SmallSize;
 
69
    // The end pointer, always valid, is set to a valid element to help the
 
70
    // iterator.
 
71
    CurArray[SmallSize] = 0;
 
72
    clear();
 
73
  }
 
74
  ~SmallPtrSetImpl();
 
75
 
 
76
public:
 
77
  bool empty() const { return size() == 0; }
 
78
  unsigned size() const { return NumElements; }
 
79
 
 
80
  void clear() {
 
81
    // If the capacity of the array is huge, and the # elements used is small,
 
82
    // shrink the array.
 
83
    if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32)
 
84
      return shrink_and_clear();
 
85
 
 
86
    // Fill the array with empty markers.
 
87
    memset(CurArray, -1, CurArraySize*sizeof(void*));
 
88
    NumElements = 0;
 
89
    NumTombstones = 0;
 
90
  }
 
91
 
 
92
protected:
 
93
  static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
 
94
  static void *getEmptyMarker() {
 
95
    // Note that -1 is chosen to make clear() efficiently implementable with
 
96
    // memset and because it's not a valid pointer value.
 
97
    return reinterpret_cast<void*>(-1);
 
98
  }
 
99
 
 
100
  /// insert_imp - This returns true if the pointer was new to the set, false if
 
101
  /// it was already in the set.  This is hidden from the client so that the
 
102
  /// derived class can check that the right type of pointer is passed in.
 
103
  bool insert_imp(const void * Ptr);
 
104
 
 
105
  /// erase_imp - If the set contains the specified pointer, remove it and
 
106
  /// return true, otherwise return false.  This is hidden from the client so
 
107
  /// that the derived class can check that the right type of pointer is passed
 
108
  /// in.
 
109
  bool erase_imp(const void * Ptr);
 
110
 
 
111
  bool count_imp(const void * Ptr) const {
 
112
    if (isSmall()) {
 
113
      // Linear search for the item.
 
114
      for (const void *const *APtr = SmallArray,
 
115
                      *const *E = SmallArray+NumElements; APtr != E; ++APtr)
 
116
        if (*APtr == Ptr)
 
117
          return true;
 
118
      return false;
 
119
    }
 
120
 
 
121
    // Big set case.
 
122
    return *FindBucketFor(Ptr) == Ptr;
 
123
  }
 
124
 
 
125
private:
 
126
  bool isSmall() const { return CurArray == &SmallArray[0]; }
 
127
 
 
128
  unsigned Hash(const void *Ptr) const {
 
129
    return static_cast<unsigned>(((uintptr_t)Ptr >> 4) & (CurArraySize-1));
 
130
  }
 
131
  const void * const *FindBucketFor(const void *Ptr) const;
 
132
  void shrink_and_clear();
 
133
 
 
134
  /// Grow - Allocate a larger backing store for the buckets and move it over.
 
135
  void Grow();
 
136
 
 
137
  void operator=(const SmallPtrSetImpl &RHS);  // DO NOT IMPLEMENT.
 
138
protected:
 
139
  void CopyFrom(const SmallPtrSetImpl &RHS);
 
140
};
 
141
 
 
142
/// SmallPtrSetIteratorImpl - This is the common base class shared between all
 
143
/// instances of SmallPtrSetIterator.
 
144
class SmallPtrSetIteratorImpl {
 
145
protected:
 
146
  const void *const *Bucket;
 
147
public:
 
148
  explicit SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) {
 
149
    AdvanceIfNotValid();
 
150
  }
 
151
 
 
152
  bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
 
153
    return Bucket == RHS.Bucket;
 
154
  }
 
155
  bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
 
156
    return Bucket != RHS.Bucket;
 
157
  }
 
158
 
 
159
protected:
 
160
  /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
 
161
  /// that is.   This is guaranteed to stop because the end() bucket is marked
 
162
  /// valid.
 
163
  void AdvanceIfNotValid() {
 
164
    while (*Bucket == SmallPtrSetImpl::getEmptyMarker() ||
 
165
           *Bucket == SmallPtrSetImpl::getTombstoneMarker())
 
166
      ++Bucket;
 
167
  }
 
168
};
 
169
 
 
170
/// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
 
171
template<typename PtrTy>
 
172
class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
 
173
  typedef PointerLikeTypeTraits<PtrTy> PtrTraits;
 
174
  
 
175
public:
 
176
  typedef PtrTy                     value_type;
 
177
  typedef PtrTy                     reference;
 
178
  typedef PtrTy                     pointer;
 
179
  typedef std::ptrdiff_t            difference_type;
 
180
  typedef std::forward_iterator_tag iterator_category;
 
181
  
 
182
  explicit SmallPtrSetIterator(const void *const *BP)
 
183
    : SmallPtrSetIteratorImpl(BP) {}
 
184
 
 
185
  // Most methods provided by baseclass.
 
186
 
 
187
  const PtrTy operator*() const {
 
188
    return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
 
189
  }
 
190
 
 
191
  inline SmallPtrSetIterator& operator++() {          // Preincrement
 
192
    ++Bucket;
 
193
    AdvanceIfNotValid();
 
194
    return *this;
 
195
  }
 
196
 
 
197
  SmallPtrSetIterator operator++(int) {        // Postincrement
 
198
    SmallPtrSetIterator tmp = *this; ++*this; return tmp;
 
199
  }
 
200
};
 
201
 
 
202
/// NextPowerOfTwo - This is a helper template that rounds N up to the next
 
203
/// power of two.
 
204
template<unsigned N>
 
205
struct NextPowerOfTwo;
 
206
 
 
207
/// NextPowerOfTwoH - If N is not a power of two, increase it.  This is a helper
 
208
/// template used to implement NextPowerOfTwo.
 
209
template<unsigned N, bool isPowerTwo>
 
210
struct NextPowerOfTwoH {
 
211
  enum { Val = N };
 
212
};
 
213
template<unsigned N>
 
214
struct NextPowerOfTwoH<N, false> {
 
215
  enum {
 
216
    // We could just use NextVal = N+1, but this converges faster.  N|(N-1) sets
 
217
    // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
 
218
    Val = NextPowerOfTwo<(N|(N-1)) + 1>::Val
 
219
  };
 
220
};
 
221
 
 
222
template<unsigned N>
 
223
struct NextPowerOfTwo {
 
224
  enum { Val = NextPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
 
225
};
 
226
  
 
227
 
 
228
/// SmallPtrSet - This class implements a set which is optimized for holding
 
229
/// SmallSize or less elements.  This internally rounds up SmallSize to the next
 
230
/// power of two if it is not already a power of two.  See the comments above
 
231
/// SmallPtrSetImpl for details of the algorithm.
 
232
template<class PtrType, unsigned SmallSize>
 
233
class SmallPtrSet : public SmallPtrSetImpl {
 
234
  // Make sure that SmallSize is a power of two, round up if not.
 
235
  enum { SmallSizePowTwo = NextPowerOfTwo<SmallSize>::Val };
 
236
  void *SmallArray[SmallSizePowTwo];
 
237
  typedef PointerLikeTypeTraits<PtrType> PtrTraits;
 
238
public:
 
239
  SmallPtrSet() : SmallPtrSetImpl(NextPowerOfTwo<SmallSizePowTwo>::Val) {}
 
240
  SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(that) {}
 
241
 
 
242
  template<typename It>
 
243
  SmallPtrSet(It I, It E)
 
244
    : SmallPtrSetImpl(NextPowerOfTwo<SmallSizePowTwo>::Val) {
 
245
    insert(I, E);
 
246
  }
 
247
 
 
248
  /// insert - This returns true if the pointer was new to the set, false if it
 
249
  /// was already in the set.
 
250
  bool insert(PtrType Ptr) {
 
251
    return insert_imp(PtrTraits::getAsVoidPointer(Ptr));
 
252
  }
 
253
 
 
254
  /// erase - If the set contains the specified pointer, remove it and return
 
255
  /// true, otherwise return false.
 
256
  bool erase(PtrType Ptr) {
 
257
    return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
 
258
  }
 
259
 
 
260
  /// count - Return true if the specified pointer is in the set.
 
261
  bool count(PtrType Ptr) const {
 
262
    return count_imp(PtrTraits::getAsVoidPointer(Ptr));
 
263
  }
 
264
 
 
265
  template <typename IterT>
 
266
  void insert(IterT I, IterT E) {
 
267
    for (; I != E; ++I)
 
268
      insert(*I);
 
269
  }
 
270
 
 
271
  typedef SmallPtrSetIterator<PtrType> iterator;
 
272
  typedef SmallPtrSetIterator<PtrType> const_iterator;
 
273
  inline iterator begin() const {
 
274
    return iterator(CurArray);
 
275
  }
 
276
  inline iterator end() const {
 
277
    return iterator(CurArray+CurArraySize);
 
278
  }
 
279
 
 
280
  // Allow assignment from any smallptrset with the same element type even if it
 
281
  // doesn't have the same smallsize.
 
282
  const SmallPtrSet<PtrType, SmallSize>&
 
283
  operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
 
284
    CopyFrom(RHS);
 
285
    return *this;
 
286
  }
 
287
 
 
288
};
 
289
 
 
290
}
 
291
 
 
292
#endif