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