← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/clamav/jaunty-backports

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (1.39.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 11.
  • 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/SparseBitVector.h
 
1
//===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector -*- 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 SparseBitVector class.  See the doxygen comment for
 
11
// SparseBitVector for more details on the algorithm used.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#ifndef LLVM_ADT_SPARSEBITVECTOR_H
 
16
#define LLVM_ADT_SPARSEBITVECTOR_H
 
17
 
 
18
#include "llvm/ADT/ilist.h"
 
19
#include "llvm/ADT/ilist_node.h"
 
20
#include "llvm/System/DataTypes.h"
 
21
#include "llvm/Support/MathExtras.h"
 
22
#include "llvm/Support/raw_ostream.h"
 
23
#include <cassert>
 
24
#include <climits>
 
25
#include <cstring>
 
26
 
 
27
namespace llvm {
 
28
 
 
29
/// SparseBitVector is an implementation of a bitvector that is sparse by only
 
30
/// storing the elements that have non-zero bits set.  In order to make this
 
31
/// fast for the most common cases, SparseBitVector is implemented as a linked
 
32
/// list of SparseBitVectorElements.  We maintain a pointer to the last
 
33
/// SparseBitVectorElement accessed (in the form of a list iterator), in order
 
34
/// to make multiple in-order test/set constant time after the first one is
 
35
/// executed.  Note that using vectors to store SparseBitVectorElement's does
 
36
/// not work out very well because it causes insertion in the middle to take
 
37
/// enormous amounts of time with a large amount of bits.  Other structures that
 
38
/// have better worst cases for insertion in the middle (various balanced trees,
 
39
/// etc) do not perform as well in practice as a linked list with this iterator
 
40
/// kept up to date.  They are also significantly more memory intensive.
 
41
 
 
42
 
 
43
template <unsigned ElementSize = 128>
 
44
struct SparseBitVectorElement
 
45
  : public ilist_node<SparseBitVectorElement<ElementSize> > {
 
46
public:
 
47
  typedef unsigned long BitWord;
 
48
  enum {
 
49
    BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
 
50
    BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
 
51
    BITS_PER_ELEMENT = ElementSize
 
52
  };
 
53
 
 
54
private:
 
55
  // Index of Element in terms of where first bit starts.
 
56
  unsigned ElementIndex;
 
57
  BitWord Bits[BITWORDS_PER_ELEMENT];
 
58
  // Needed for sentinels
 
59
  friend struct ilist_sentinel_traits<SparseBitVectorElement>;
 
60
  SparseBitVectorElement() {
 
61
    ElementIndex = ~0U;
 
62
    memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
 
63
  }
 
64
 
 
65
public:
 
66
  explicit SparseBitVectorElement(unsigned Idx) {
 
67
    ElementIndex = Idx;
 
68
    memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
 
69
  }
 
70
 
 
71
  // Comparison.
 
72
  bool operator==(const SparseBitVectorElement &RHS) const {
 
73
    if (ElementIndex != RHS.ElementIndex)
 
74
      return false;
 
75
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 
76
      if (Bits[i] != RHS.Bits[i])
 
77
        return false;
 
78
    return true;
 
79
  }
 
80
 
 
81
  bool operator!=(const SparseBitVectorElement &RHS) const {
 
82
    return !(*this == RHS);
 
83
  }
 
84
 
 
85
  // Return the bits that make up word Idx in our element.
 
86
  BitWord word(unsigned Idx) const {
 
87
    assert (Idx < BITWORDS_PER_ELEMENT);
 
88
    return Bits[Idx];
 
89
  }
 
90
 
 
91
  unsigned index() const {
 
92
    return ElementIndex;
 
93
  }
 
94
 
 
95
  bool empty() const {
 
96
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 
97
      if (Bits[i])
 
98
        return false;
 
99
    return true;
 
100
  }
 
101
 
 
102
  void set(unsigned Idx) {
 
103
    Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
 
104
  }
 
105
 
 
106
  bool test_and_set (unsigned Idx) {
 
107
    bool old = test(Idx);
 
108
    if (!old) {
 
109
      set(Idx);
 
110
      return true;
 
111
    }
 
112
    return false;
 
113
  }
 
114
 
 
115
  void reset(unsigned Idx) {
 
116
    Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
 
117
  }
 
118
 
 
119
  bool test(unsigned Idx) const {
 
120
    return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
 
121
  }
 
122
 
 
123
  unsigned count() const {
 
124
    unsigned NumBits = 0;
 
125
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 
126
      if (sizeof(BitWord) == 4)
 
127
        NumBits += CountPopulation_32(Bits[i]);
 
128
      else if (sizeof(BitWord) == 8)
 
129
        NumBits += CountPopulation_64(Bits[i]);
 
130
      else
 
131
        assert(0 && "Unsupported!");
 
132
    return NumBits;
 
133
  }
 
134
 
 
135
  /// find_first - Returns the index of the first set bit.
 
136
  int find_first() const {
 
137
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 
138
      if (Bits[i] != 0) {
 
139
        if (sizeof(BitWord) == 4)
 
140
          return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 
141
        else if (sizeof(BitWord) == 8)
 
142
          return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 
143
        else
 
144
          assert(0 && "Unsupported!");
 
145
      }
 
146
    assert(0 && "Illegal empty element");
 
147
    return 0; // Not reached
 
148
  }
 
149
 
 
150
  /// find_next - Returns the index of the next set bit starting from the
 
151
  /// "Curr" bit. Returns -1 if the next set bit is not found.
 
152
  int find_next(unsigned Curr) const {
 
153
    if (Curr >= BITS_PER_ELEMENT)
 
154
      return -1;
 
155
 
 
156
    unsigned WordPos = Curr / BITWORD_SIZE;
 
157
    unsigned BitPos = Curr % BITWORD_SIZE;
 
158
    BitWord Copy = Bits[WordPos];
 
159
    assert (WordPos <= BITWORDS_PER_ELEMENT
 
160
            && "Word Position outside of element");
 
161
 
 
162
    // Mask off previous bits.
 
163
    Copy &= ~0L << BitPos;
 
164
 
 
165
    if (Copy != 0) {
 
166
      if (sizeof(BitWord) == 4)
 
167
        return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
 
168
      else if (sizeof(BitWord) == 8)
 
169
        return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
 
170
      else
 
171
        assert(0 && "Unsupported!");
 
172
    }
 
173
 
 
174
    // Check subsequent words.
 
175
    for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
 
176
      if (Bits[i] != 0) {
 
177
        if (sizeof(BitWord) == 4)
 
178
          return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 
179
        else if (sizeof(BitWord) == 8)
 
180
          return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 
181
        else
 
182
          assert(0 && "Unsupported!");
 
183
      }
 
184
    return -1;
 
185
  }
 
186
 
 
187
  // Union this element with RHS and return true if this one changed.
 
188
  bool unionWith(const SparseBitVectorElement &RHS) {
 
189
    bool changed = false;
 
190
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 
191
      BitWord old = changed ? 0 : Bits[i];
 
192
 
 
193
      Bits[i] |= RHS.Bits[i];
 
194
      if (!changed && old != Bits[i])
 
195
        changed = true;
 
196
    }
 
197
    return changed;
 
198
  }
 
199
 
 
200
  // Return true if we have any bits in common with RHS
 
201
  bool intersects(const SparseBitVectorElement &RHS) const {
 
202
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 
203
      if (RHS.Bits[i] & Bits[i])
 
204
        return true;
 
205
    }
 
206
    return false;
 
207
  }
 
208
 
 
209
  // Intersect this Element with RHS and return true if this one changed.
 
210
  // BecameZero is set to true if this element became all-zero bits.
 
211
  bool intersectWith(const SparseBitVectorElement &RHS,
 
212
                     bool &BecameZero) {
 
213
    bool changed = false;
 
214
    bool allzero = true;
 
215
 
 
216
    BecameZero = false;
 
217
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 
218
      BitWord old = changed ? 0 : Bits[i];
 
219
 
 
220
      Bits[i] &= RHS.Bits[i];
 
221
      if (Bits[i] != 0)
 
222
        allzero = false;
 
223
 
 
224
      if (!changed && old != Bits[i])
 
225
        changed = true;
 
226
    }
 
227
    BecameZero = allzero;
 
228
    return changed;
 
229
  }
 
230
  // Intersect this Element with the complement of RHS and return true if this
 
231
  // one changed.  BecameZero is set to true if this element became all-zero
 
232
  // bits.
 
233
  bool intersectWithComplement(const SparseBitVectorElement &RHS,
 
234
                               bool &BecameZero) {
 
235
    bool changed = false;
 
236
    bool allzero = true;
 
237
 
 
238
    BecameZero = false;
 
239
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 
240
      BitWord old = changed ? 0 : Bits[i];
 
241
 
 
242
      Bits[i] &= ~RHS.Bits[i];
 
243
      if (Bits[i] != 0)
 
244
        allzero = false;
 
245
 
 
246
      if (!changed && old != Bits[i])
 
247
        changed = true;
 
248
    }
 
249
    BecameZero = allzero;
 
250
    return changed;
 
251
  }
 
252
  // Three argument version of intersectWithComplement that intersects
 
253
  // RHS1 & ~RHS2 into this element
 
254
  void intersectWithComplement(const SparseBitVectorElement &RHS1,
 
255
                               const SparseBitVectorElement &RHS2,
 
256
                               bool &BecameZero) {
 
257
    bool allzero = true;
 
258
 
 
259
    BecameZero = false;
 
260
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 
261
      Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
 
262
      if (Bits[i] != 0)
 
263
        allzero = false;
 
264
    }
 
265
    BecameZero = allzero;
 
266
  }
 
267
 
 
268
  // Get a hash value for this element;
 
269
  uint64_t getHashValue() const {
 
270
    uint64_t HashVal = 0;
 
271
    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 
272
      HashVal ^= Bits[i];
 
273
    }
 
274
    return HashVal;
 
275
  }
 
276
};
 
277
 
 
278
template <unsigned ElementSize = 128>
 
279
class SparseBitVector {
 
280
  typedef ilist<SparseBitVectorElement<ElementSize> > ElementList;
 
281
  typedef typename ElementList::iterator ElementListIter;
 
282
  typedef typename ElementList::const_iterator ElementListConstIter;
 
283
  enum {
 
284
    BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
 
285
  };
 
286
 
 
287
  // Pointer to our current Element.
 
288
  ElementListIter CurrElementIter;
 
289
  ElementList Elements;
 
290
 
 
291
  // This is like std::lower_bound, except we do linear searching from the
 
292
  // current position.
 
293
  ElementListIter FindLowerBound(unsigned ElementIndex) {
 
294
 
 
295
    if (Elements.empty()) {
 
296
      CurrElementIter = Elements.begin();
 
297
      return Elements.begin();
 
298
    }
 
299
 
 
300
    // Make sure our current iterator is valid.
 
301
    if (CurrElementIter == Elements.end())
 
302
      --CurrElementIter;
 
303
 
 
304
    // Search from our current iterator, either backwards or forwards,
 
305
    // depending on what element we are looking for.
 
306
    ElementListIter ElementIter = CurrElementIter;
 
307
    if (CurrElementIter->index() == ElementIndex) {
 
308
      return ElementIter;
 
309
    } else if (CurrElementIter->index() > ElementIndex) {
 
310
      while (ElementIter != Elements.begin()
 
311
             && ElementIter->index() > ElementIndex)
 
312
        --ElementIter;
 
313
    } else {
 
314
      while (ElementIter != Elements.end() &&
 
315
             ElementIter->index() < ElementIndex)
 
316
        ++ElementIter;
 
317
    }
 
318
    CurrElementIter = ElementIter;
 
319
    return ElementIter;
 
320
  }
 
321
 
 
322
  // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
 
323
  // than it would be, in order to be efficient.
 
324
  class SparseBitVectorIterator {
 
325
  private:
 
326
    bool AtEnd;
 
327
 
 
328
    const SparseBitVector<ElementSize> *BitVector;
 
329
 
 
330
    // Current element inside of bitmap.
 
331
    ElementListConstIter Iter;
 
332
 
 
333
    // Current bit number inside of our bitmap.
 
334
    unsigned BitNumber;
 
335
 
 
336
    // Current word number inside of our element.
 
337
    unsigned WordNumber;
 
338
 
 
339
    // Current bits from the element.
 
340
    typename SparseBitVectorElement<ElementSize>::BitWord Bits;
 
341
 
 
342
    // Move our iterator to the first non-zero bit in the bitmap.
 
343
    void AdvanceToFirstNonZero() {
 
344
      if (AtEnd)
 
345
        return;
 
346
      if (BitVector->Elements.empty()) {
 
347
        AtEnd = true;
 
348
        return;
 
349
      }
 
350
      Iter = BitVector->Elements.begin();
 
351
      BitNumber = Iter->index() * ElementSize;
 
352
      unsigned BitPos = Iter->find_first();
 
353
      BitNumber += BitPos;
 
354
      WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 
355
      Bits = Iter->word(WordNumber);
 
356
      Bits >>= BitPos % BITWORD_SIZE;
 
357
    }
 
358
 
 
359
    // Move our iterator to the next non-zero bit.
 
360
    void AdvanceToNextNonZero() {
 
361
      if (AtEnd)
 
362
        return;
 
363
 
 
364
      while (Bits && !(Bits & 1)) {
 
365
        Bits >>= 1;
 
366
        BitNumber += 1;
 
367
      }
 
368
 
 
369
      // See if we ran out of Bits in this word.
 
370
      if (!Bits) {
 
371
        int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
 
372
        // If we ran out of set bits in this element, move to next element.
 
373
        if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
 
374
          ++Iter;
 
375
          WordNumber = 0;
 
376
 
 
377
          // We may run out of elements in the bitmap.
 
378
          if (Iter == BitVector->Elements.end()) {
 
379
            AtEnd = true;
 
380
            return;
 
381
          }
 
382
          // Set up for next non zero word in bitmap.
 
383
          BitNumber = Iter->index() * ElementSize;
 
384
          NextSetBitNumber = Iter->find_first();
 
385
          BitNumber += NextSetBitNumber;
 
386
          WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 
387
          Bits = Iter->word(WordNumber);
 
388
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
 
389
        } else {
 
390
          WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
 
391
          Bits = Iter->word(WordNumber);
 
392
          Bits >>= NextSetBitNumber % BITWORD_SIZE;
 
393
          BitNumber = Iter->index() * ElementSize;
 
394
          BitNumber += NextSetBitNumber;
 
395
        }
 
396
      }
 
397
    }
 
398
  public:
 
399
    // Preincrement.
 
400
    inline SparseBitVectorIterator& operator++() {
 
401
      ++BitNumber;
 
402
      Bits >>= 1;
 
403
      AdvanceToNextNonZero();
 
404
      return *this;
 
405
    }
 
406
 
 
407
    // Postincrement.
 
408
    inline SparseBitVectorIterator operator++(int) {
 
409
      SparseBitVectorIterator tmp = *this;
 
410
      ++*this;
 
411
      return tmp;
 
412
    }
 
413
 
 
414
    // Return the current set bit number.
 
415
    unsigned operator*() const {
 
416
      return BitNumber;
 
417
    }
 
418
 
 
419
    bool operator==(const SparseBitVectorIterator &RHS) const {
 
420
      // If they are both at the end, ignore the rest of the fields.
 
421
      if (AtEnd && RHS.AtEnd)
 
422
        return true;
 
423
      // Otherwise they are the same if they have the same bit number and
 
424
      // bitmap.
 
425
      return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
 
426
    }
 
427
    bool operator!=(const SparseBitVectorIterator &RHS) const {
 
428
      return !(*this == RHS);
 
429
    }
 
430
    SparseBitVectorIterator(): BitVector(NULL) {
 
431
    }
 
432
 
 
433
 
 
434
    SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
 
435
                            bool end = false):BitVector(RHS) {
 
436
      Iter = BitVector->Elements.begin();
 
437
      BitNumber = 0;
 
438
      Bits = 0;
 
439
      WordNumber = ~0;
 
440
      AtEnd = end;
 
441
      AdvanceToFirstNonZero();
 
442
    }
 
443
  };
 
444
public:
 
445
  typedef SparseBitVectorIterator iterator;
 
446
 
 
447
  SparseBitVector () {
 
448
    CurrElementIter = Elements.begin ();
 
449
  }
 
450
 
 
451
  ~SparseBitVector() {
 
452
  }
 
453
 
 
454
  // SparseBitVector copy ctor.
 
455
  SparseBitVector(const SparseBitVector &RHS) {
 
456
    ElementListConstIter ElementIter = RHS.Elements.begin();
 
457
    while (ElementIter != RHS.Elements.end()) {
 
458
      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
 
459
      ++ElementIter;
 
460
    }
 
461
 
 
462
    CurrElementIter = Elements.begin ();
 
463
  }
 
464
 
 
465
  // Clear.
 
466
  void clear() {
 
467
    Elements.clear();
 
468
  }
 
469
 
 
470
  // Assignment
 
471
  SparseBitVector& operator=(const SparseBitVector& RHS) {
 
472
    Elements.clear();
 
473
 
 
474
    ElementListConstIter ElementIter = RHS.Elements.begin();
 
475
    while (ElementIter != RHS.Elements.end()) {
 
476
      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
 
477
      ++ElementIter;
 
478
    }
 
479
 
 
480
    CurrElementIter = Elements.begin ();
 
481
 
 
482
    return *this;
 
483
  }
 
484
 
 
485
  // Test, Reset, and Set a bit in the bitmap.
 
486
  bool test(unsigned Idx) {
 
487
    if (Elements.empty())
 
488
      return false;
 
489
 
 
490
    unsigned ElementIndex = Idx / ElementSize;
 
491
    ElementListIter ElementIter = FindLowerBound(ElementIndex);
 
492
 
 
493
    // If we can't find an element that is supposed to contain this bit, there
 
494
    // is nothing more to do.
 
495
    if (ElementIter == Elements.end() ||
 
496
        ElementIter->index() != ElementIndex)
 
497
      return false;
 
498
    return ElementIter->test(Idx % ElementSize);
 
499
  }
 
500
 
 
501
  void reset(unsigned Idx) {
 
502
    if (Elements.empty())
 
503
      return;
 
504
 
 
505
    unsigned ElementIndex = Idx / ElementSize;
 
506
    ElementListIter ElementIter = FindLowerBound(ElementIndex);
 
507
 
 
508
    // If we can't find an element that is supposed to contain this bit, there
 
509
    // is nothing more to do.
 
510
    if (ElementIter == Elements.end() ||
 
511
        ElementIter->index() != ElementIndex)
 
512
      return;
 
513
    ElementIter->reset(Idx % ElementSize);
 
514
 
 
515
    // When the element is zeroed out, delete it.
 
516
    if (ElementIter->empty()) {
 
517
      ++CurrElementIter;
 
518
      Elements.erase(ElementIter);
 
519
    }
 
520
  }
 
521
 
 
522
  void set(unsigned Idx) {
 
523
    unsigned ElementIndex = Idx / ElementSize;
 
524
    SparseBitVectorElement<ElementSize> *Element;
 
525
    ElementListIter ElementIter;
 
526
    if (Elements.empty()) {
 
527
      Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 
528
      ElementIter = Elements.insert(Elements.end(), Element);
 
529
 
 
530
    } else {
 
531
      ElementIter = FindLowerBound(ElementIndex);
 
532
 
 
533
      if (ElementIter == Elements.end() ||
 
534
          ElementIter->index() != ElementIndex) {
 
535
        Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 
536
        // We may have hit the beginning of our SparseBitVector, in which case,
 
537
        // we may need to insert right after this element, which requires moving
 
538
        // the current iterator forward one, because insert does insert before.
 
539
        if (ElementIter != Elements.end() &&
 
540
            ElementIter->index() < ElementIndex)
 
541
          ElementIter = Elements.insert(++ElementIter, Element);
 
542
        else
 
543
          ElementIter = Elements.insert(ElementIter, Element);
 
544
      }
 
545
    }
 
546
    CurrElementIter = ElementIter;
 
547
 
 
548
    ElementIter->set(Idx % ElementSize);
 
549
  }
 
550
 
 
551
  bool test_and_set (unsigned Idx) {
 
552
    bool old = test(Idx);
 
553
    if (!old) {
 
554
      set(Idx);
 
555
      return true;
 
556
    }
 
557
    return false;
 
558
  }
 
559
 
 
560
  bool operator!=(const SparseBitVector &RHS) const {
 
561
    return !(*this == RHS);
 
562
  }
 
563
 
 
564
  bool operator==(const SparseBitVector &RHS) const {
 
565
    ElementListConstIter Iter1 = Elements.begin();
 
566
    ElementListConstIter Iter2 = RHS.Elements.begin();
 
567
 
 
568
    for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
 
569
         ++Iter1, ++Iter2) {
 
570
      if (*Iter1 != *Iter2)
 
571
        return false;
 
572
    }
 
573
    return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
 
574
  }
 
575
 
 
576
  // Union our bitmap with the RHS and return true if we changed.
 
577
  bool operator|=(const SparseBitVector &RHS) {
 
578
    bool changed = false;
 
579
    ElementListIter Iter1 = Elements.begin();
 
580
    ElementListConstIter Iter2 = RHS.Elements.begin();
 
581
 
 
582
    // If RHS is empty, we are done
 
583
    if (RHS.Elements.empty())
 
584
      return false;
 
585
 
 
586
    while (Iter2 != RHS.Elements.end()) {
 
587
      if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
 
588
        Elements.insert(Iter1,
 
589
                        new SparseBitVectorElement<ElementSize>(*Iter2));
 
590
        ++Iter2;
 
591
        changed = true;
 
592
      } else if (Iter1->index() == Iter2->index()) {
 
593
        changed |= Iter1->unionWith(*Iter2);
 
594
        ++Iter1;
 
595
        ++Iter2;
 
596
      } else {
 
597
        ++Iter1;
 
598
      }
 
599
    }
 
600
    CurrElementIter = Elements.begin();
 
601
    return changed;
 
602
  }
 
603
 
 
604
  // Intersect our bitmap with the RHS and return true if ours changed.
 
605
  bool operator&=(const SparseBitVector &RHS) {
 
606
    bool changed = false;
 
607
    ElementListIter Iter1 = Elements.begin();
 
608
    ElementListConstIter Iter2 = RHS.Elements.begin();
 
609
 
 
610
    // Check if both bitmaps are empty.
 
611
    if (Elements.empty() && RHS.Elements.empty())
 
612
      return false;
 
613
 
 
614
    // Loop through, intersecting as we go, erasing elements when necessary.
 
615
    while (Iter2 != RHS.Elements.end()) {
 
616
      if (Iter1 == Elements.end()) {
 
617
        CurrElementIter = Elements.begin();
 
618
        return changed;
 
619
      }
 
620
 
 
621
      if (Iter1->index() > Iter2->index()) {
 
622
        ++Iter2;
 
623
      } else if (Iter1->index() == Iter2->index()) {
 
624
        bool BecameZero;
 
625
        changed |= Iter1->intersectWith(*Iter2, BecameZero);
 
626
        if (BecameZero) {
 
627
          ElementListIter IterTmp = Iter1;
 
628
          ++Iter1;
 
629
          Elements.erase(IterTmp);
 
630
        } else {
 
631
          ++Iter1;
 
632
        }
 
633
        ++Iter2;
 
634
      } else {
 
635
        ElementListIter IterTmp = Iter1;
 
636
        ++Iter1;
 
637
        Elements.erase(IterTmp);
 
638
      }
 
639
    }
 
640
    Elements.erase(Iter1, Elements.end());
 
641
    CurrElementIter = Elements.begin();
 
642
    return changed;
 
643
  }
 
644
 
 
645
  // Intersect our bitmap with the complement of the RHS and return true
 
646
  // if ours changed.
 
647
  bool intersectWithComplement(const SparseBitVector &RHS) {
 
648
    bool changed = false;
 
649
    ElementListIter Iter1 = Elements.begin();
 
650
    ElementListConstIter Iter2 = RHS.Elements.begin();
 
651
 
 
652
    // If either our bitmap or RHS is empty, we are done
 
653
    if (Elements.empty() || RHS.Elements.empty())
 
654
      return false;
 
655
 
 
656
    // Loop through, intersecting as we go, erasing elements when necessary.
 
657
    while (Iter2 != RHS.Elements.end()) {
 
658
      if (Iter1 == Elements.end()) {
 
659
        CurrElementIter = Elements.begin();
 
660
        return changed;
 
661
      }
 
662
 
 
663
      if (Iter1->index() > Iter2->index()) {
 
664
        ++Iter2;
 
665
      } else if (Iter1->index() == Iter2->index()) {
 
666
        bool BecameZero;
 
667
        changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
 
668
        if (BecameZero) {
 
669
          ElementListIter IterTmp = Iter1;
 
670
          ++Iter1;
 
671
          Elements.erase(IterTmp);
 
672
        } else {
 
673
          ++Iter1;
 
674
        }
 
675
        ++Iter2;
 
676
      } else {
 
677
        ++Iter1;
 
678
      }
 
679
    }
 
680
    CurrElementIter = Elements.begin();
 
681
    return changed;
 
682
  }
 
683
 
 
684
  bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
 
685
    return intersectWithComplement(*RHS);
 
686
  }
 
687
 
 
688
 
 
689
  //  Three argument version of intersectWithComplement.
 
690
  //  Result of RHS1 & ~RHS2 is stored into this bitmap.
 
691
  void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
 
692
                               const SparseBitVector<ElementSize> &RHS2)
 
693
  {
 
694
    Elements.clear();
 
695
    CurrElementIter = Elements.begin();
 
696
    ElementListConstIter Iter1 = RHS1.Elements.begin();
 
697
    ElementListConstIter Iter2 = RHS2.Elements.begin();
 
698
 
 
699
    // If RHS1 is empty, we are done
 
700
    // If RHS2 is empty, we still have to copy RHS1
 
701
    if (RHS1.Elements.empty())
 
702
      return;
 
703
 
 
704
    // Loop through, intersecting as we go, erasing elements when necessary.
 
705
    while (Iter2 != RHS2.Elements.end()) {
 
706
      if (Iter1 == RHS1.Elements.end())
 
707
        return;
 
708
 
 
709
      if (Iter1->index() > Iter2->index()) {
 
710
        ++Iter2;
 
711
      } else if (Iter1->index() == Iter2->index()) {
 
712
        bool BecameZero = false;
 
713
        SparseBitVectorElement<ElementSize> *NewElement =
 
714
          new SparseBitVectorElement<ElementSize>(Iter1->index());
 
715
        NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
 
716
        if (!BecameZero) {
 
717
          Elements.push_back(NewElement);
 
718
        }
 
719
        else
 
720
          delete NewElement;
 
721
        ++Iter1;
 
722
        ++Iter2;
 
723
      } else {
 
724
        SparseBitVectorElement<ElementSize> *NewElement =
 
725
          new SparseBitVectorElement<ElementSize>(*Iter1);
 
726
        Elements.push_back(NewElement);
 
727
        ++Iter1;
 
728
      }
 
729
    }
 
730
 
 
731
    // copy the remaining elements
 
732
    while (Iter1 != RHS1.Elements.end()) {
 
733
        SparseBitVectorElement<ElementSize> *NewElement =
 
734
          new SparseBitVectorElement<ElementSize>(*Iter1);
 
735
        Elements.push_back(NewElement);
 
736
        ++Iter1;
 
737
      }
 
738
 
 
739
    return;
 
740
  }
 
741
 
 
742
  void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
 
743
                               const SparseBitVector<ElementSize> *RHS2) {
 
744
    intersectWithComplement(*RHS1, *RHS2);
 
745
  }
 
746
 
 
747
  bool intersects(const SparseBitVector<ElementSize> *RHS) const {
 
748
    return intersects(*RHS);
 
749
  }
 
750
 
 
751
  // Return true if we share any bits in common with RHS
 
752
  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
 
753
    ElementListConstIter Iter1 = Elements.begin();
 
754
    ElementListConstIter Iter2 = RHS.Elements.begin();
 
755
 
 
756
    // Check if both bitmaps are empty.
 
757
    if (Elements.empty() && RHS.Elements.empty())
 
758
      return false;
 
759
 
 
760
    // Loop through, intersecting stopping when we hit bits in common.
 
761
    while (Iter2 != RHS.Elements.end()) {
 
762
      if (Iter1 == Elements.end())
 
763
        return false;
 
764
 
 
765
      if (Iter1->index() > Iter2->index()) {
 
766
        ++Iter2;
 
767
      } else if (Iter1->index() == Iter2->index()) {
 
768
        if (Iter1->intersects(*Iter2))
 
769
          return true;
 
770
        ++Iter1;
 
771
        ++Iter2;
 
772
      } else {
 
773
        ++Iter1;
 
774
      }
 
775
    }
 
776
    return false;
 
777
  }
 
778
 
 
779
  // Return true iff all bits set in this SparseBitVector are
 
780
  // also set in RHS.
 
781
  bool contains(const SparseBitVector<ElementSize> &RHS) const {
 
782
    SparseBitVector<ElementSize> Result(*this);
 
783
    Result &= RHS;
 
784
    return (Result == RHS);
 
785
  }
 
786
 
 
787
  // Return the first set bit in the bitmap.  Return -1 if no bits are set.
 
788
  int find_first() const {
 
789
    if (Elements.empty())
 
790
      return -1;
 
791
    const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
 
792
    return (First.index() * ElementSize) + First.find_first();
 
793
  }
 
794
 
 
795
  // Return true if the SparseBitVector is empty
 
796
  bool empty() const {
 
797
    return Elements.empty();
 
798
  }
 
799
 
 
800
  unsigned count() const {
 
801
    unsigned BitCount = 0;
 
802
    for (ElementListConstIter Iter = Elements.begin();
 
803
         Iter != Elements.end();
 
804
         ++Iter)
 
805
      BitCount += Iter->count();
 
806
 
 
807
    return BitCount;
 
808
  }
 
809
  iterator begin() const {
 
810
    return iterator(this);
 
811
  }
 
812
 
 
813
  iterator end() const {
 
814
    return iterator(this, true);
 
815
  }
 
816
 
 
817
  // Get a hash value for this bitmap.
 
818
  uint64_t getHashValue() const {
 
819
    uint64_t HashVal = 0;
 
820
    for (ElementListConstIter Iter = Elements.begin();
 
821
         Iter != Elements.end();
 
822
         ++Iter) {
 
823
      HashVal ^= Iter->index();
 
824
      HashVal ^= Iter->getHashValue();
 
825
    }
 
826
    return HashVal;
 
827
  }
 
828
};
 
829
 
 
830
// Convenience functions to allow Or and And without dereferencing in the user
 
831
// code.
 
832
 
 
833
template <unsigned ElementSize>
 
834
inline bool operator |=(SparseBitVector<ElementSize> &LHS,
 
835
                        const SparseBitVector<ElementSize> *RHS) {
 
836
  return LHS |= *RHS;
 
837
}
 
838
 
 
839
template <unsigned ElementSize>
 
840
inline bool operator |=(SparseBitVector<ElementSize> *LHS,
 
841
                        const SparseBitVector<ElementSize> &RHS) {
 
842
  return LHS->operator|=(RHS);
 
843
}
 
844
 
 
845
template <unsigned ElementSize>
 
846
inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 
847
                        const SparseBitVector<ElementSize> &RHS) {
 
848
  return LHS->operator&=(RHS);
 
849
}
 
850
 
 
851
template <unsigned ElementSize>
 
852
inline bool operator &=(SparseBitVector<ElementSize> &LHS,
 
853
                        const SparseBitVector<ElementSize> *RHS) {
 
854
  return LHS &= *RHS;
 
855
}
 
856
 
 
857
// Convenience functions for infix union, intersection, difference operators.
 
858
 
 
859
template <unsigned ElementSize>
 
860
inline SparseBitVector<ElementSize>
 
861
operator|(const SparseBitVector<ElementSize> &LHS,
 
862
          const SparseBitVector<ElementSize> &RHS) {
 
863
  SparseBitVector<ElementSize> Result(LHS);
 
864
  Result |= RHS;
 
865
  return Result;
 
866
}
 
867
 
 
868
template <unsigned ElementSize>
 
869
inline SparseBitVector<ElementSize>
 
870
operator&(const SparseBitVector<ElementSize> &LHS,
 
871
          const SparseBitVector<ElementSize> &RHS) {
 
872
  SparseBitVector<ElementSize> Result(LHS);
 
873
  Result &= RHS;
 
874
  return Result;
 
875
}
 
876
 
 
877
template <unsigned ElementSize>
 
878
inline SparseBitVector<ElementSize>
 
879
operator-(const SparseBitVector<ElementSize> &LHS,
 
880
          const SparseBitVector<ElementSize> &RHS) {
 
881
  SparseBitVector<ElementSize> Result;
 
882
  Result.intersectWithComplement(LHS, RHS);
 
883
  return Result;
 
884
}
 
885
 
 
886
 
 
887
 
 
888
 
 
889
// Dump a SparseBitVector to a stream
 
890
template <unsigned ElementSize>
 
891
void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
 
892
  out << "[ ";
 
893
 
 
894
  typename SparseBitVector<ElementSize>::iterator bi;
 
895
  for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
 
896
    out << *bi << " ";
 
897
  }
 
898
  out << " ]\n";
 
899
}
 
900
} // end namespace llvm
 
901
 
 
902
#endif