← 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/SmallBitVector.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/SmallBitVector.h
 
1
//===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- 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 implements the SmallBitVector class.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#ifndef LLVM_ADT_SMALLBITVECTOR_H
 
15
#define LLVM_ADT_SMALLBITVECTOR_H
 
16
 
 
17
#include "llvm/ADT/BitVector.h"
 
18
#include "llvm/ADT/PointerIntPair.h"
 
19
#include "llvm/Support/MathExtras.h"
 
20
#include <cassert>
 
21
 
 
22
namespace llvm {
 
23
 
 
24
/// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array),
 
25
/// optimized for the case when the array is small.  It contains one
 
26
/// pointer-sized field, which is directly used as a plain collection of bits
 
27
/// when possible, or as a pointer to a larger heap-allocated array when
 
28
/// necessary.  This allows normal "small" cases to be fast without losing
 
29
/// generality for large inputs.
 
30
///
 
31
class SmallBitVector {
 
32
  // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
 
33
  // unnecessary level of indirection. It would be more efficient to use a
 
34
  // pointer to memory containing size, allocation size, and the array of bits.
 
35
  PointerIntPair<BitVector *, 1, uintptr_t> X;
 
36
 
 
37
  // The number of bits in this class.
 
38
  static const size_t NumBaseBits = sizeof(uintptr_t) * CHAR_BIT;
 
39
 
 
40
  // One bit is used to discriminate between small and large mode. The
 
41
  // remaining bits are used for the small-mode representation.
 
42
  static const size_t SmallNumRawBits = NumBaseBits - 1;
 
43
 
 
44
  // A few more bits are used to store the size of the bit set in small mode.
 
45
  // Theoretically this is a ceil-log2. These bits are encoded in the most
 
46
  // significant bits of the raw bits.
 
47
  static const size_t SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
 
48
                                          NumBaseBits == 64 ? 6 :
 
49
                                          SmallNumRawBits);
 
50
 
 
51
  // The remaining bits are used to store the actual set in small mode.
 
52
  static const size_t SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits;
 
53
 
 
54
  bool isSmall() const {
 
55
    return X.getInt();
 
56
  }
 
57
 
 
58
  void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
 
59
    X.setInt(true);
 
60
    setSmallSize(NewSize);
 
61
    setSmallBits(NewSmallBits);
 
62
  }
 
63
 
 
64
  void switchToLarge(BitVector *BV) {
 
65
    X.setInt(false);
 
66
    X.setPointer(BV);
 
67
  }
 
68
 
 
69
  // Return all the bits used for the "small" representation; this includes
 
70
  // bits for the size as well as the element bits.
 
71
  uintptr_t getSmallRawBits() const {
 
72
    return reinterpret_cast<uintptr_t>(X.getPointer()) >> 1;
 
73
  }
 
74
 
 
75
  void setSmallRawBits(uintptr_t NewRawBits) {
 
76
    return X.setPointer(reinterpret_cast<BitVector *>(NewRawBits << 1));
 
77
  }
 
78
 
 
79
  // Return the size.
 
80
  size_t getSmallSize() const {
 
81
    return getSmallRawBits() >> SmallNumDataBits;
 
82
  }
 
83
 
 
84
  void setSmallSize(size_t Size) {
 
85
    setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
 
86
  }
 
87
 
 
88
  // Return the element bits.
 
89
  uintptr_t getSmallBits() const {
 
90
    return getSmallRawBits() & ~(~uintptr_t(0) << SmallNumDataBits);
 
91
  }
 
92
 
 
93
  void setSmallBits(uintptr_t NewBits) {
 
94
    setSmallRawBits((getSmallRawBits() & (~uintptr_t(0) << SmallNumDataBits)) |
 
95
                    (NewBits & ~(~uintptr_t(0) << getSmallSize())));
 
96
  }
 
97
 
 
98
public:
 
99
  /// SmallBitVector default ctor - Creates an empty bitvector.
 
100
  SmallBitVector() : X(0, 1) {}
 
101
 
 
102
  /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All
 
103
  /// bits are initialized to the specified value.
 
104
  explicit SmallBitVector(unsigned s, bool t = false) : X(0, 1) {
 
105
    if (s <= SmallNumRawBits)
 
106
      switchToSmall(t ? ~uintptr_t(0) : 0, s);
 
107
    else
 
108
      switchToLarge(new BitVector(s, t));
 
109
  }
 
110
 
 
111
  /// SmallBitVector copy ctor.
 
112
  SmallBitVector(const SmallBitVector &RHS) {
 
113
    if (RHS.isSmall())
 
114
      X = RHS.X;
 
115
    else
 
116
      switchToLarge(new BitVector(*RHS.X.getPointer()));
 
117
  }
 
118
 
 
119
  ~SmallBitVector() {
 
120
    if (!isSmall())
 
121
      delete X.getPointer();
 
122
  }
 
123
 
 
124
  /// empty - Tests whether there are no bits in this bitvector.
 
125
  bool empty() const {
 
126
    return isSmall() ? getSmallSize() == 0 : X.getPointer()->empty();
 
127
  }
 
128
 
 
129
  /// size - Returns the number of bits in this bitvector.
 
130
  size_t size() const {
 
131
    return isSmall() ? getSmallSize() : X.getPointer()->size();
 
132
  }
 
133
 
 
134
  /// count - Returns the number of bits which are set.
 
135
  unsigned count() const {
 
136
    if (isSmall()) {
 
137
      uintptr_t Bits = getSmallBits();
 
138
      if (sizeof(uintptr_t) * CHAR_BIT == 32)
 
139
        return CountPopulation_32(Bits);
 
140
      if (sizeof(uintptr_t) * CHAR_BIT == 64)
 
141
        return CountPopulation_64(Bits);
 
142
      assert(0 && "Unsupported!");
 
143
    }
 
144
    return X.getPointer()->count();
 
145
  }
 
146
 
 
147
  /// any - Returns true if any bit is set.
 
148
  bool any() const {
 
149
    if (isSmall())
 
150
      return getSmallBits() != 0;
 
151
    return X.getPointer()->any();
 
152
  }
 
153
 
 
154
  /// none - Returns true if none of the bits are set.
 
155
  bool none() const {
 
156
    if (isSmall())
 
157
      return getSmallBits() == 0;
 
158
    return X.getPointer()->none();
 
159
  }
 
160
 
 
161
  /// find_first - Returns the index of the first set bit, -1 if none
 
162
  /// of the bits are set.
 
163
  int find_first() const {
 
164
    if (isSmall()) {
 
165
      uintptr_t Bits = getSmallBits();
 
166
      if (sizeof(uintptr_t) * CHAR_BIT == 32)
 
167
        return CountTrailingZeros_32(Bits);
 
168
      if (sizeof(uintptr_t) * CHAR_BIT == 64)
 
169
        return CountTrailingZeros_64(Bits);
 
170
      assert(0 && "Unsupported!");
 
171
    }
 
172
    return X.getPointer()->find_first();
 
173
  }
 
174
 
 
175
  /// find_next - Returns the index of the next set bit following the
 
176
  /// "Prev" bit. Returns -1 if the next set bit is not found.
 
177
  int find_next(unsigned Prev) const {
 
178
    if (isSmall()) {
 
179
      uintptr_t Bits = getSmallBits();
 
180
      // Mask off previous bits.
 
181
      Bits &= ~uintptr_t(0) << Prev;
 
182
      if (sizeof(uintptr_t) * CHAR_BIT == 32)
 
183
        return CountTrailingZeros_32(Bits);
 
184
      if (sizeof(uintptr_t) * CHAR_BIT == 64)
 
185
        return CountTrailingZeros_64(Bits);
 
186
      assert(0 && "Unsupported!");
 
187
    }
 
188
    return X.getPointer()->find_next(Prev);
 
189
  }
 
190
 
 
191
  /// clear - Clear all bits.
 
192
  void clear() {
 
193
    if (!isSmall())
 
194
      delete X.getPointer();
 
195
    switchToSmall(0, 0);
 
196
  }
 
197
 
 
198
  /// resize - Grow or shrink the bitvector.
 
199
  void resize(unsigned N, bool t = false) {
 
200
    if (!isSmall()) {
 
201
      X.getPointer()->resize(N, t);
 
202
    } else if (getSmallSize() >= N) {
 
203
      setSmallSize(N);
 
204
      setSmallBits(getSmallBits());
 
205
    } else {
 
206
      BitVector *BV = new BitVector(N, t);
 
207
      uintptr_t OldBits = getSmallBits();
 
208
      for (size_t i = 0, e = getSmallSize(); i != e; ++i)
 
209
        (*BV)[i] = (OldBits >> i) & 1;
 
210
      switchToLarge(BV);
 
211
    }
 
212
  }
 
213
 
 
214
  void reserve(unsigned N) {
 
215
    if (isSmall()) {
 
216
      if (N > SmallNumDataBits) {
 
217
        uintptr_t OldBits = getSmallRawBits();
 
218
        size_t SmallSize = getSmallSize();
 
219
        BitVector *BV = new BitVector(SmallSize);
 
220
        for (size_t i = 0; i < SmallSize; ++i)
 
221
          if ((OldBits >> i) & 1)
 
222
            BV->set(i);
 
223
        BV->reserve(N);
 
224
        switchToLarge(BV);
 
225
      }
 
226
    } else {
 
227
      X.getPointer()->reserve(N);
 
228
    }
 
229
  }
 
230
 
 
231
  // Set, reset, flip
 
232
  SmallBitVector &set() {
 
233
    if (isSmall())
 
234
      setSmallBits(~uintptr_t(0));
 
235
    else
 
236
      X.getPointer()->set();
 
237
    return *this;
 
238
  }
 
239
 
 
240
  SmallBitVector &set(unsigned Idx) {
 
241
    if (isSmall())
 
242
      setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
 
243
    else
 
244
      X.getPointer()->set(Idx);
 
245
    return *this;
 
246
  }
 
247
 
 
248
  SmallBitVector &reset() {
 
249
    if (isSmall())
 
250
      setSmallBits(0);
 
251
    else
 
252
      X.getPointer()->reset();
 
253
    return *this;
 
254
  }
 
255
 
 
256
  SmallBitVector &reset(unsigned Idx) {
 
257
    if (isSmall())
 
258
      setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
 
259
    else
 
260
      X.getPointer()->reset(Idx);
 
261
    return *this;
 
262
  }
 
263
 
 
264
  SmallBitVector &flip() {
 
265
    if (isSmall())
 
266
      setSmallBits(~getSmallBits());
 
267
    else
 
268
      X.getPointer()->flip();
 
269
    return *this;
 
270
  }
 
271
 
 
272
  SmallBitVector &flip(unsigned Idx) {
 
273
    if (isSmall())
 
274
      setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
 
275
    else
 
276
      X.getPointer()->flip(Idx);
 
277
    return *this;
 
278
  }
 
279
 
 
280
  // No argument flip.
 
281
  SmallBitVector operator~() const {
 
282
    return SmallBitVector(*this).flip();
 
283
  }
 
284
 
 
285
  // Indexing.
 
286
  // TODO: Add an index operator which returns a "reference" (proxy class).
 
287
  bool operator[](unsigned Idx) const {
 
288
    assert(Idx < size() && "Out-of-bounds Bit access.");
 
289
    if (isSmall())
 
290
      return ((getSmallBits() >> Idx) & 1) != 0;
 
291
    return X.getPointer()->operator[](Idx);
 
292
  }
 
293
 
 
294
  bool test(unsigned Idx) const {
 
295
    return (*this)[Idx];
 
296
  }
 
297
 
 
298
  // Comparison operators.
 
299
  bool operator==(const SmallBitVector &RHS) const {
 
300
    if (size() != RHS.size())
 
301
      return false;
 
302
    if (isSmall())
 
303
      return getSmallBits() == RHS.getSmallBits();
 
304
    else
 
305
      return *X.getPointer() == *RHS.X.getPointer();
 
306
  }
 
307
 
 
308
  bool operator!=(const SmallBitVector &RHS) const {
 
309
    return !(*this == RHS);
 
310
  }
 
311
 
 
312
  // Intersection, union, disjoint union.
 
313
  SmallBitVector &operator&=(const SmallBitVector &RHS) {
 
314
    resize(std::max(size(), RHS.size()));
 
315
    if (isSmall())
 
316
      setSmallBits(getSmallBits() & RHS.getSmallBits());
 
317
    else if (!RHS.isSmall())
 
318
      X.getPointer()->operator&=(*RHS.X.getPointer());
 
319
    else {
 
320
      SmallBitVector Copy = RHS;
 
321
      Copy.resize(size());
 
322
      X.getPointer()->operator&=(*Copy.X.getPointer());
 
323
    }
 
324
    return *this;
 
325
  }
 
326
 
 
327
  SmallBitVector &operator|=(const SmallBitVector &RHS) {
 
328
    resize(std::max(size(), RHS.size()));
 
329
    if (isSmall())
 
330
      setSmallBits(getSmallBits() | RHS.getSmallBits());
 
331
    else if (!RHS.isSmall())
 
332
      X.getPointer()->operator|=(*RHS.X.getPointer());
 
333
    else {
 
334
      SmallBitVector Copy = RHS;
 
335
      Copy.resize(size());
 
336
      X.getPointer()->operator|=(*Copy.X.getPointer());
 
337
    }
 
338
    return *this;
 
339
  }
 
340
 
 
341
  SmallBitVector &operator^=(const SmallBitVector &RHS) {
 
342
    resize(std::max(size(), RHS.size()));
 
343
    if (isSmall())
 
344
      setSmallBits(getSmallBits() ^ RHS.getSmallBits());
 
345
    else if (!RHS.isSmall())
 
346
      X.getPointer()->operator^=(*RHS.X.getPointer());
 
347
    else {
 
348
      SmallBitVector Copy = RHS;
 
349
      Copy.resize(size());
 
350
      X.getPointer()->operator^=(*Copy.X.getPointer());
 
351
    }
 
352
    return *this;
 
353
  }
 
354
 
 
355
  // Assignment operator.
 
356
  const SmallBitVector &operator=(const SmallBitVector &RHS) {
 
357
    if (isSmall()) {
 
358
      if (RHS.isSmall())
 
359
        X = RHS.X;
 
360
      else
 
361
        switchToLarge(new BitVector(*RHS.X.getPointer()));
 
362
    } else {
 
363
      if (!RHS.isSmall())
 
364
        *X.getPointer() = *RHS.X.getPointer();
 
365
      else {
 
366
        delete X.getPointer();
 
367
        X = RHS.X;
 
368
      }
 
369
    }
 
370
    return *this;
 
371
  }
 
372
 
 
373
  void swap(SmallBitVector &RHS) {
 
374
    std::swap(X, RHS.X);
 
375
  }
 
376
};
 
377
 
 
378
inline SmallBitVector
 
379
operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 
380
  SmallBitVector Result(LHS);
 
381
  Result &= RHS;
 
382
  return Result;
 
383
}
 
384
 
 
385
inline SmallBitVector
 
386
operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 
387
  SmallBitVector Result(LHS);
 
388
  Result |= RHS;
 
389
  return Result;
 
390
}
 
391
 
 
392
inline SmallBitVector
 
393
operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 
394
  SmallBitVector Result(LHS);
 
395
  Result ^= RHS;
 
396
  return Result;
 
397
}
 
398
 
 
399
} // End llvm namespace
 
400
 
 
401
namespace std {
 
402
  /// Implement std::swap in terms of BitVector swap.
 
403
  inline void
 
404
  swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
 
405
    LHS.swap(RHS);
 
406
  }
 
407
}
 
408
 
 
409
#endif