← 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/DenseMap.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/DenseMap.h
 
1
//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- 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 DenseMap class.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#ifndef LLVM_ADT_DENSEMAP_H
 
15
#define LLVM_ADT_DENSEMAP_H
 
16
 
 
17
#include "llvm/Support/MathExtras.h"
 
18
#include "llvm/Support/PointerLikeTypeTraits.h"
 
19
#include "llvm/Support/type_traits.h"
 
20
#include "llvm/ADT/DenseMapInfo.h"
 
21
#include <iterator>
 
22
#include <new>
 
23
#include <utility>
 
24
#include <cassert>
 
25
#include <cstddef>
 
26
#include <cstring>
 
27
 
 
28
namespace llvm {
 
29
 
 
30
template<typename KeyT, typename ValueT,
 
31
         typename KeyInfoT = DenseMapInfo<KeyT>,
 
32
         typename ValueInfoT = DenseMapInfo<ValueT>, bool IsConst = false>
 
33
class DenseMapIterator;
 
34
 
 
35
template<typename KeyT, typename ValueT,
 
36
         typename KeyInfoT = DenseMapInfo<KeyT>,
 
37
         typename ValueInfoT = DenseMapInfo<ValueT> >
 
38
class DenseMap {
 
39
  typedef std::pair<KeyT, ValueT> BucketT;
 
40
  unsigned NumBuckets;
 
41
  BucketT *Buckets;
 
42
 
 
43
  unsigned NumEntries;
 
44
  unsigned NumTombstones;
 
45
public:
 
46
  typedef KeyT key_type;
 
47
  typedef ValueT mapped_type;
 
48
  typedef BucketT value_type;
 
49
 
 
50
  DenseMap(const DenseMap &other) {
 
51
    NumBuckets = 0;
 
52
    CopyFrom(other);
 
53
  }
 
54
 
 
55
  explicit DenseMap(unsigned NumInitBuckets = 64) {
 
56
    init(NumInitBuckets);
 
57
  }
 
58
 
 
59
  template<typename InputIt>
 
60
  DenseMap(const InputIt &I, const InputIt &E) {
 
61
    init(64);
 
62
    insert(I, E);
 
63
  }
 
64
  
 
65
  ~DenseMap() {
 
66
    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
 
67
    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
 
68
      if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
 
69
          !KeyInfoT::isEqual(P->first, TombstoneKey))
 
70
        P->second.~ValueT();
 
71
      P->first.~KeyT();
 
72
    }
 
73
#ifndef NDEBUG
 
74
    memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
 
75
#endif
 
76
    operator delete(Buckets);
 
77
  }
 
78
 
 
79
  typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
 
80
  typedef DenseMapIterator<KeyT, ValueT,
 
81
                           KeyInfoT, ValueInfoT, true> const_iterator;
 
82
  inline iterator begin() {
 
83
    // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
 
84
    return empty() ? end() : iterator(Buckets, Buckets+NumBuckets);
 
85
  }
 
86
  inline iterator end() {
 
87
    return iterator(Buckets+NumBuckets, Buckets+NumBuckets);
 
88
  }
 
89
  inline const_iterator begin() const {
 
90
    return empty() ? end() : const_iterator(Buckets, Buckets+NumBuckets);
 
91
  }
 
92
  inline const_iterator end() const {
 
93
    return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
 
94
  }
 
95
 
 
96
  bool empty() const { return NumEntries == 0; }
 
97
  unsigned size() const { return NumEntries; }
 
98
 
 
99
  /// Grow the densemap so that it has at least Size buckets. Does not shrink
 
100
  void resize(size_t Size) { grow(Size); }
 
101
 
 
102
  void clear() {
 
103
    if (NumEntries == 0 && NumTombstones == 0) return;
 
104
    
 
105
    // If the capacity of the array is huge, and the # elements used is small,
 
106
    // shrink the array.
 
107
    if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
 
108
      shrink_and_clear();
 
109
      return;
 
110
    }
 
111
 
 
112
    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
 
113
    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
 
114
      if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
 
115
        if (!KeyInfoT::isEqual(P->first, TombstoneKey)) {
 
116
          P->second.~ValueT();
 
117
          --NumEntries;
 
118
        }
 
119
        P->first = EmptyKey;
 
120
      }
 
121
    }
 
122
    assert(NumEntries == 0 && "Node count imbalance!");
 
123
    NumTombstones = 0;
 
124
  }
 
125
 
 
126
  /// count - Return true if the specified key is in the map.
 
127
  bool count(const KeyT &Val) const {
 
128
    BucketT *TheBucket;
 
129
    return LookupBucketFor(Val, TheBucket);
 
130
  }
 
131
 
 
132
  iterator find(const KeyT &Val) {
 
133
    BucketT *TheBucket;
 
134
    if (LookupBucketFor(Val, TheBucket))
 
135
      return iterator(TheBucket, Buckets+NumBuckets);
 
136
    return end();
 
137
  }
 
138
  const_iterator find(const KeyT &Val) const {
 
139
    BucketT *TheBucket;
 
140
    if (LookupBucketFor(Val, TheBucket))
 
141
      return const_iterator(TheBucket, Buckets+NumBuckets);
 
142
    return end();
 
143
  }
 
144
 
 
145
  /// lookup - Return the entry for the specified key, or a default
 
146
  /// constructed value if no such entry exists.
 
147
  ValueT lookup(const KeyT &Val) const {
 
148
    BucketT *TheBucket;
 
149
    if (LookupBucketFor(Val, TheBucket))
 
150
      return TheBucket->second;
 
151
    return ValueT();
 
152
  }
 
153
 
 
154
  // Inserts key,value pair into the map if the key isn't already in the map.
 
155
  // If the key is already in the map, it returns false and doesn't update the
 
156
  // value.
 
157
  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
 
158
    BucketT *TheBucket;
 
159
    if (LookupBucketFor(KV.first, TheBucket))
 
160
      return std::make_pair(iterator(TheBucket, Buckets+NumBuckets),
 
161
                            false); // Already in map.
 
162
 
 
163
    // Otherwise, insert the new element.
 
164
    TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
 
165
    return std::make_pair(iterator(TheBucket, Buckets+NumBuckets),
 
166
                          true);
 
167
  }
 
168
 
 
169
  /// insert - Range insertion of pairs.
 
170
  template<typename InputIt>
 
171
  void insert(InputIt I, InputIt E) {
 
172
    for (; I != E; ++I)
 
173
      insert(*I);
 
174
  }
 
175
 
 
176
 
 
177
  bool erase(const KeyT &Val) {
 
178
    BucketT *TheBucket;
 
179
    if (!LookupBucketFor(Val, TheBucket))
 
180
      return false; // not in map.
 
181
 
 
182
    TheBucket->second.~ValueT();
 
183
    TheBucket->first = getTombstoneKey();
 
184
    --NumEntries;
 
185
    ++NumTombstones;
 
186
    return true;
 
187
  }
 
188
  void erase(iterator I) {
 
189
    BucketT *TheBucket = &*I;
 
190
    TheBucket->second.~ValueT();
 
191
    TheBucket->first = getTombstoneKey();
 
192
    --NumEntries;
 
193
    ++NumTombstones;
 
194
  }
 
195
 
 
196
  void swap(DenseMap& RHS) {
 
197
    std::swap(NumBuckets, RHS.NumBuckets);
 
198
    std::swap(Buckets, RHS.Buckets);
 
199
    std::swap(NumEntries, RHS.NumEntries);
 
200
    std::swap(NumTombstones, RHS.NumTombstones);
 
201
  }
 
202
 
 
203
  value_type& FindAndConstruct(const KeyT &Key) {
 
204
    BucketT *TheBucket;
 
205
    if (LookupBucketFor(Key, TheBucket))
 
206
      return *TheBucket;
 
207
 
 
208
    return *InsertIntoBucket(Key, ValueT(), TheBucket);
 
209
  }
 
210
 
 
211
  ValueT &operator[](const KeyT &Key) {
 
212
    return FindAndConstruct(Key).second;
 
213
  }
 
214
 
 
215
  DenseMap& operator=(const DenseMap& other) {
 
216
    CopyFrom(other);
 
217
    return *this;
 
218
  }
 
219
 
 
220
  /// isPointerIntoBucketsArray - Return true if the specified pointer points
 
221
  /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
 
222
  /// value in the DenseMap).
 
223
  bool isPointerIntoBucketsArray(const void *Ptr) const {
 
224
    return Ptr >= Buckets && Ptr < Buckets+NumBuckets;
 
225
  }
 
226
 
 
227
  /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
 
228
  /// array.  In conjunction with the previous method, this can be used to
 
229
  /// determine whether an insertion caused the DenseMap to reallocate.
 
230
  const void *getPointerIntoBucketsArray() const { return Buckets; }
 
231
 
 
232
private:
 
233
  void CopyFrom(const DenseMap& other) {
 
234
    if (NumBuckets != 0 &&
 
235
        (!isPodLike<KeyInfoT>::value || !isPodLike<ValueInfoT>::value)) {
 
236
      const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
 
237
      for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
 
238
        if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
 
239
            !KeyInfoT::isEqual(P->first, TombstoneKey))
 
240
          P->second.~ValueT();
 
241
        P->first.~KeyT();
 
242
      }
 
243
    }
 
244
 
 
245
    NumEntries = other.NumEntries;
 
246
    NumTombstones = other.NumTombstones;
 
247
 
 
248
    if (NumBuckets) {
 
249
#ifndef NDEBUG
 
250
      memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
 
251
#endif
 
252
      operator delete(Buckets);
 
253
    }
 
254
    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) *
 
255
                                                 other.NumBuckets));
 
256
 
 
257
    if (isPodLike<KeyInfoT>::value && isPodLike<ValueInfoT>::value)
 
258
      memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT));
 
259
    else
 
260
      for (size_t i = 0; i < other.NumBuckets; ++i) {
 
261
        new (&Buckets[i].first) KeyT(other.Buckets[i].first);
 
262
        if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) &&
 
263
            !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey()))
 
264
          new (&Buckets[i].second) ValueT(other.Buckets[i].second);
 
265
      }
 
266
    NumBuckets = other.NumBuckets;
 
267
  }
 
268
 
 
269
  BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
 
270
                            BucketT *TheBucket) {
 
271
    // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
 
272
    // the buckets are empty (meaning that many are filled with tombstones),
 
273
    // grow the table.
 
274
    //
 
275
    // The later case is tricky.  For example, if we had one empty bucket with
 
276
    // tons of tombstones, failing lookups (e.g. for insertion) would have to
 
277
    // probe almost the entire table until it found the empty bucket.  If the
 
278
    // table completely filled with tombstones, no lookup would ever succeed,
 
279
    // causing infinite loops in lookup.
 
280
    ++NumEntries;
 
281
    if (NumEntries*4 >= NumBuckets*3 ||
 
282
        NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
 
283
      this->grow(NumBuckets * 2);
 
284
      LookupBucketFor(Key, TheBucket);
 
285
    }
 
286
 
 
287
    // If we are writing over a tombstone, remember this.
 
288
    if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
 
289
      --NumTombstones;
 
290
 
 
291
    TheBucket->first = Key;
 
292
    new (&TheBucket->second) ValueT(Value);
 
293
    return TheBucket;
 
294
  }
 
295
 
 
296
  static unsigned getHashValue(const KeyT &Val) {
 
297
    return KeyInfoT::getHashValue(Val);
 
298
  }
 
299
  static const KeyT getEmptyKey() {
 
300
    return KeyInfoT::getEmptyKey();
 
301
  }
 
302
  static const KeyT getTombstoneKey() {
 
303
    return KeyInfoT::getTombstoneKey();
 
304
  }
 
305
 
 
306
  /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
 
307
  /// FoundBucket.  If the bucket contains the key and a value, this returns
 
308
  /// true, otherwise it returns a bucket with an empty marker or tombstone and
 
309
  /// returns false.
 
310
  bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const {
 
311
    unsigned BucketNo = getHashValue(Val);
 
312
    unsigned ProbeAmt = 1;
 
313
    BucketT *BucketsPtr = Buckets;
 
314
 
 
315
    // FoundTombstone - Keep track of whether we find a tombstone while probing.
 
316
    BucketT *FoundTombstone = 0;
 
317
    const KeyT EmptyKey = getEmptyKey();
 
318
    const KeyT TombstoneKey = getTombstoneKey();
 
319
    assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
 
320
           !KeyInfoT::isEqual(Val, TombstoneKey) &&
 
321
           "Empty/Tombstone value shouldn't be inserted into map!");
 
322
 
 
323
    while (1) {
 
324
      BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
 
325
      // Found Val's bucket?  If so, return it.
 
326
      if (KeyInfoT::isEqual(ThisBucket->first, Val)) {
 
327
        FoundBucket = ThisBucket;
 
328
        return true;
 
329
      }
 
330
 
 
331
      // If we found an empty bucket, the key doesn't exist in the set.
 
332
      // Insert it and return the default value.
 
333
      if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
 
334
        // If we've already seen a tombstone while probing, fill it in instead
 
335
        // of the empty bucket we eventually probed to.
 
336
        if (FoundTombstone) ThisBucket = FoundTombstone;
 
337
        FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
 
338
        return false;
 
339
      }
 
340
 
 
341
      // If this is a tombstone, remember it.  If Val ends up not in the map, we
 
342
      // prefer to return it than something that would require more probing.
 
343
      if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
 
344
        FoundTombstone = ThisBucket;  // Remember the first tombstone found.
 
345
 
 
346
      // Otherwise, it's a hash collision or a tombstone, continue quadratic
 
347
      // probing.
 
348
      BucketNo += ProbeAmt++;
 
349
    }
 
350
  }
 
351
 
 
352
  void init(unsigned InitBuckets) {
 
353
    NumEntries = 0;
 
354
    NumTombstones = 0;
 
355
    NumBuckets = InitBuckets;
 
356
    assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 &&
 
357
           "# initial buckets must be a power of two!");
 
358
    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets));
 
359
    // Initialize all the keys to EmptyKey.
 
360
    const KeyT EmptyKey = getEmptyKey();
 
361
    for (unsigned i = 0; i != InitBuckets; ++i)
 
362
      new (&Buckets[i].first) KeyT(EmptyKey);
 
363
  }
 
364
 
 
365
  void grow(unsigned AtLeast) {
 
366
    unsigned OldNumBuckets = NumBuckets;
 
367
    BucketT *OldBuckets = Buckets;
 
368
 
 
369
    // Double the number of buckets.
 
370
    while (NumBuckets < AtLeast)
 
371
      NumBuckets <<= 1;
 
372
    NumTombstones = 0;
 
373
    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
 
374
 
 
375
    // Initialize all the keys to EmptyKey.
 
376
    const KeyT EmptyKey = getEmptyKey();
 
377
    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
 
378
      new (&Buckets[i].first) KeyT(EmptyKey);
 
379
 
 
380
    // Insert all the old elements.
 
381
    const KeyT TombstoneKey = getTombstoneKey();
 
382
    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
 
383
      if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
 
384
          !KeyInfoT::isEqual(B->first, TombstoneKey)) {
 
385
        // Insert the key/value into the new table.
 
386
        BucketT *DestBucket;
 
387
        bool FoundVal = LookupBucketFor(B->first, DestBucket);
 
388
        FoundVal = FoundVal; // silence warning.
 
389
        assert(!FoundVal && "Key already in new map?");
 
390
        DestBucket->first = B->first;
 
391
        new (&DestBucket->second) ValueT(B->second);
 
392
 
 
393
        // Free the value.
 
394
        B->second.~ValueT();
 
395
      }
 
396
      B->first.~KeyT();
 
397
    }
 
398
 
 
399
#ifndef NDEBUG
 
400
    memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
 
401
#endif
 
402
    // Free the old table.
 
403
    operator delete(OldBuckets);
 
404
  }
 
405
 
 
406
  void shrink_and_clear() {
 
407
    unsigned OldNumBuckets = NumBuckets;
 
408
    BucketT *OldBuckets = Buckets;
 
409
 
 
410
    // Reduce the number of buckets.
 
411
    NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1)
 
412
                                 : 64;
 
413
    NumTombstones = 0;
 
414
    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
 
415
 
 
416
    // Initialize all the keys to EmptyKey.
 
417
    const KeyT EmptyKey = getEmptyKey();
 
418
    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
 
419
      new (&Buckets[i].first) KeyT(EmptyKey);
 
420
 
 
421
    // Free the old buckets.
 
422
    const KeyT TombstoneKey = getTombstoneKey();
 
423
    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
 
424
      if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
 
425
          !KeyInfoT::isEqual(B->first, TombstoneKey)) {
 
426
        // Free the value.
 
427
        B->second.~ValueT();
 
428
      }
 
429
      B->first.~KeyT();
 
430
    }
 
431
 
 
432
#ifndef NDEBUG
 
433
    memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
 
434
#endif
 
435
    // Free the old table.
 
436
    operator delete(OldBuckets);
 
437
 
 
438
    NumEntries = 0;
 
439
  }
 
440
};
 
441
 
 
442
template<typename KeyT, typename ValueT,
 
443
         typename KeyInfoT, typename ValueInfoT, bool IsConst>
 
444
class DenseMapIterator {
 
445
  typedef std::pair<KeyT, ValueT> Bucket;
 
446
  typedef DenseMapIterator<KeyT, ValueT,
 
447
                           KeyInfoT, ValueInfoT, true> ConstIterator;
 
448
  friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, ValueInfoT, true>;
 
449
public:
 
450
  typedef ptrdiff_t difference_type;
 
451
  typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type;
 
452
  typedef value_type *pointer;
 
453
  typedef value_type &reference;
 
454
  typedef std::forward_iterator_tag iterator_category;
 
455
private:
 
456
  pointer Ptr, End;
 
457
public:
 
458
  DenseMapIterator() : Ptr(0), End(0) {}
 
459
 
 
460
  DenseMapIterator(pointer Pos, pointer E) : Ptr(Pos), End(E) {
 
461
    AdvancePastEmptyBuckets();
 
462
  }
 
463
 
 
464
  // If IsConst is true this is a converting constructor from iterator to
 
465
  // const_iterator and the default copy constructor is used.
 
466
  // Otherwise this is a copy constructor for iterator.
 
467
  DenseMapIterator(const DenseMapIterator<KeyT, ValueT,
 
468
                                          KeyInfoT, ValueInfoT, false>& I)
 
469
    : Ptr(I.Ptr), End(I.End) {}
 
470
 
 
471
  reference operator*() const {
 
472
    return *Ptr;
 
473
  }
 
474
  pointer operator->() const {
 
475
    return Ptr;
 
476
  }
 
477
 
 
478
  bool operator==(const ConstIterator &RHS) const {
 
479
    return Ptr == RHS.operator->();
 
480
  }
 
481
  bool operator!=(const ConstIterator &RHS) const {
 
482
    return Ptr != RHS.operator->();
 
483
  }
 
484
 
 
485
  inline DenseMapIterator& operator++() {  // Preincrement
 
486
    ++Ptr;
 
487
    AdvancePastEmptyBuckets();
 
488
    return *this;
 
489
  }
 
490
  DenseMapIterator operator++(int) {  // Postincrement
 
491
    DenseMapIterator tmp = *this; ++*this; return tmp;
 
492
  }
 
493
 
 
494
private:
 
495
  void AdvancePastEmptyBuckets() {
 
496
    const KeyT Empty = KeyInfoT::getEmptyKey();
 
497
    const KeyT Tombstone = KeyInfoT::getTombstoneKey();
 
498
 
 
499
    while (Ptr != End &&
 
500
           (KeyInfoT::isEqual(Ptr->first, Empty) ||
 
501
            KeyInfoT::isEqual(Ptr->first, Tombstone)))
 
502
      ++Ptr;
 
503
  }
 
504
};
 
505
 
 
506
} // end namespace llvm
 
507
 
 
508
#endif