[llvm-commits] CVS: llvm/include/llvm/ADT/DenseMap.h
Changes in directory llvm/include/llvm/ADT:
DenseMap.h updated: 1.17 - 1.18
---
Log message:
Allow DenseMAp to take an explicit DenseMapKeyInfo
---
Diffs of the changes: (+20 -19)
DenseMap.h | 39 ---
1 files changed, 20 insertions(+), 19 deletions(-)
Index: llvm/include/llvm/ADT/DenseMap.h
diff -u llvm/include/llvm/ADT/DenseMap.h:1.17
llvm/include/llvm/ADT/DenseMap.h:1.18
--- llvm/include/llvm/ADT/DenseMap.h:1.17 Tue Feb 6 18:55:59 2007
+++ llvm/include/llvm/ADT/DenseMap.hSat Feb 10 00:34:58 2007
@@ -40,12 +40,15 @@
static bool isPod() { return true; }
};
-templatetypename KeyT, typename ValueT
+templatetypename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapKeyInfoKeyT
class DenseMapIterator;
-templatetypename KeyT, typename ValueT
+templatetypename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapKeyInfoKeyT
class DenseMapConstIterator;
-templatetypename KeyT, typename ValueT
+templatetypename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapKeyInfoKeyT
class DenseMap {
typedef std::pairKeyT, ValueT BucketT;
unsigned NumBuckets;
@@ -68,21 +71,19 @@
delete[] (char*)Buckets;
}
- typedef DenseMapIteratorKeyT, ValueT iterator;
- typedef DenseMapConstIteratorKeyT, ValueT const_iterator;
+ typedef DenseMapIteratorKeyT, ValueT, KeyInfoT iterator;
+ typedef DenseMapConstIteratorKeyT, ValueT, KeyInfoT const_iterator;
inline iterator begin() {
- return DenseMapIteratorKeyT, ValueT(Buckets, Buckets+NumBuckets);
+ return iterator(Buckets, Buckets+NumBuckets);
}
inline iterator end() {
-return DenseMapIteratorKeyT, ValueT(Buckets+NumBuckets,
- Buckets+NumBuckets);
+return iterator(Buckets+NumBuckets, Buckets+NumBuckets);
}
inline const_iterator begin() const {
-return DenseMapConstIteratorKeyT, ValueT(Buckets, Buckets+NumBuckets);
+return const_iterator(Buckets, Buckets+NumBuckets);
}
inline const_iterator end() const {
-return DenseMapConstIteratorKeyT, ValueT(Buckets+NumBuckets,
- Buckets+NumBuckets);
+return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
}
bool empty() const { return NumEntries == 0; }
@@ -181,13 +182,13 @@
}
static unsigned getHashValue(const KeyT Val) {
-return DenseMapKeyInfoKeyT::getHashValue(Val);
+return KeyInfoT::getHashValue(Val);
}
static const KeyT getEmptyKey() {
-return DenseMapKeyInfoKeyT::getEmptyKey();
+return KeyInfoT::getEmptyKey();
}
static const KeyT getTombstoneKey() {
-return DenseMapKeyInfoKeyT::getTombstoneKey();
+return KeyInfoT::getTombstoneKey();
}
/// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
@@ -285,7 +286,7 @@
}
};
-templatetypename KeyT, typename ValueT
+templatetypename KeyT, typename ValueT, typename KeyInfoT
class DenseMapIterator {
typedef std::pairKeyT, ValueT BucketT;
protected:
@@ -320,16 +321,16 @@
private:
void AdvancePastEmptyBuckets() {
-const KeyT Empty = DenseMapKeyInfoKeyT::getEmptyKey();
-const KeyT Tombstone = DenseMapKeyInfoKeyT::getTombstoneKey();
+const KeyT Empty = KeyInfoT::getEmptyKey();
+const KeyT Tombstone = KeyInfoT::getTombstoneKey();
while (Ptr != End (Ptr-first == Empty || Ptr-first == Tombstone))
++Ptr;
}
};
-templatetypename KeyT, typename ValueT
-class DenseMapConstIterator : public DenseMapIteratorKeyT, ValueT {
+templatetypename KeyT, typename ValueT, typename KeyInfoT
+class DenseMapConstIterator : public DenseMapIteratorKeyT, ValueT, KeyInfoT {
public:
DenseMapConstIterator(const std::pairKeyT, ValueT *Pos,
const std::pairKeyT, ValueT *E)
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/DenseMap.h
Changes in directory llvm/include/llvm/ADT:
DenseMap.h updated: 1.18 - 1.19
---
Log message:
Make find return the appropriate iterator/const_iterator
---
Diffs of the changes: (+8 -2)
DenseMap.h | 10 --
1 files changed, 8 insertions(+), 2 deletions(-)
Index: llvm/include/llvm/ADT/DenseMap.h
diff -u llvm/include/llvm/ADT/DenseMap.h:1.18
llvm/include/llvm/ADT/DenseMap.h:1.19
--- llvm/include/llvm/ADT/DenseMap.h:1.18 Sat Feb 10 00:34:58 2007
+++ llvm/include/llvm/ADT/DenseMap.hSat Feb 10 00:58:17 2007
@@ -108,12 +108,18 @@
return LookupBucketFor(Val, TheBucket);
}
- iterator find(const KeyT Val) const {
+ iterator find(const KeyT Val) {
BucketT *TheBucket;
if (LookupBucketFor(Val, TheBucket))
return iterator(TheBucket, Buckets+NumBuckets);
return end();
}
+ const_iterator find(const KeyT Val) const {
+BucketT *TheBucket;
+if (LookupBucketFor(Val, TheBucket))
+ return const_iterator(TheBucket, Buckets+NumBuckets);
+return end();
+ }
bool insert(const std::pairKeyT, ValueT KV) {
BucketT *TheBucket;
@@ -334,7 +340,7 @@
public:
DenseMapConstIterator(const std::pairKeyT, ValueT *Pos,
const std::pairKeyT, ValueT *E)
-: DenseMapIteratorKeyT, ValueT(Pos, E) {
+: DenseMapIteratorKeyT, ValueT, KeyInfoT(Pos, E) {
}
const std::pairKeyT, ValueT operator*() const {
return *this-Ptr;
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/DenseMap.h
Changes in directory llvm/include/llvm/ADT:
DenseMap.h updated: 1.14 - 1.15
---
Log message:
8 buckets is way too small to start out with. This was only for testing.
---
Diffs of the changes: (+1 -1)
DenseMap.h |2 +-
1 files changed, 1 insertion(+), 1 deletion(-)
Index: llvm/include/llvm/ADT/DenseMap.h
diff -u llvm/include/llvm/ADT/DenseMap.h:1.14
llvm/include/llvm/ADT/DenseMap.h:1.15
--- llvm/include/llvm/ADT/DenseMap.h:1.14 Fri Feb 2 15:19:18 2007
+++ llvm/include/llvm/ADT/DenseMap.hSat Feb 3 13:30:48 2007
@@ -53,7 +53,7 @@
unsigned NumEntries;
DenseMap(const DenseMap ); // not implemented.
public:
- explicit DenseMap(unsigned NumInitBuckets = 8) {
+ explicit DenseMap(unsigned NumInitBuckets = 64) {
init(NumInitBuckets);
}
~DenseMap() {
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/DenseMap.h
Changes in directory llvm/include/llvm/ADT:
DenseMap.h updated: 1.15 - 1.16
---
Log message:
add a version of insert that takes the key and value.
---
Diffs of the changes: (+23 -8)
DenseMap.h | 31 +++
1 files changed, 23 insertions(+), 8 deletions(-)
Index: llvm/include/llvm/ADT/DenseMap.h
diff -u llvm/include/llvm/ADT/DenseMap.h:1.15
llvm/include/llvm/ADT/DenseMap.h:1.16
--- llvm/include/llvm/ADT/DenseMap.h:1.15 Sat Feb 3 13:30:48 2007
+++ llvm/include/llvm/ADT/DenseMap.hSat Feb 3 18:42:41 2007
@@ -111,6 +111,16 @@
return end();
}
+ bool insert(const std::pairKeyT, ValueT KV) {
+BucketT *TheBucket;
+if (LookupBucketFor(KV.first, TheBucket))
+ return false; // Already in map.
+
+// Otherwise, insert the new element.
+InsertIntoBucket(KV.first, KV.second, TheBucket);
+return true;
+ }
+
bool erase(const KeyT Val) {
BucketT *TheBucket;
if (!LookupBucketFor(Val, TheBucket))
@@ -129,23 +139,28 @@
return true;
}
- ValueT operator[](const KeyT Val) {
+ ValueT operator[](const KeyT Key) {
BucketT *TheBucket;
-if (LookupBucketFor(Val, TheBucket))
+if (LookupBucketFor(Key, TheBucket))
return TheBucket-second;
+return InsertIntoBucket(Key, ValueT(), TheBucket)-second;
+ }
+
+private:
+ BucketT *InsertIntoBucket(const KeyT Key, const ValueT Value,
+BucketT *TheBucket) {
// If the load of the hash table is more than 3/4, grow it.
if (NumEntries*4 = NumBuckets*3) {
this-grow();
- LookupBucketFor(Val, TheBucket);
+ LookupBucketFor(Key, TheBucket);
}
++NumEntries;
-TheBucket-first = Val;
-new (TheBucket-second) ValueT();
-return TheBucket-second;
+TheBucket-first = Key;
+new (TheBucket-second) ValueT(Value);
+return TheBucket;
}
-
-private:
+
static unsigned getHashValue(const KeyT Val) {
return DenseMapKeyInfoKeyT::getHashValue(Val);
}
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/DenseMap.h
Changes in directory llvm/include/llvm/ADT:
DenseMap.h updated: 1.11 - 1.12
---
Log message:
add iterators
---
Diffs of the changes: (+82 -22)
DenseMap.h | 104 -
1 files changed, 82 insertions(+), 22 deletions(-)
Index: llvm/include/llvm/ADT/DenseMap.h
diff -u llvm/include/llvm/ADT/DenseMap.h:1.11
llvm/include/llvm/ADT/DenseMap.h:1.12
--- llvm/include/llvm/ADT/DenseMap.h:1.11 Thu Feb 1 01:49:59 2007
+++ llvm/include/llvm/ADT/DenseMap.hFri Feb 2 13:27:13 2007
@@ -16,6 +16,7 @@
#include llvm/Support/DataTypes.h
#include cassert
+#include utility
namespace llvm {
@@ -38,10 +39,12 @@
static bool isPod() { return true; }
};
+templatetypename KeyT, typename ValueT
+class DenseMapIterator;
templatetypename KeyT, typename ValueT
class DenseMap {
- struct BucketT { KeyT Key; ValueT Value; };
+ typedef std::pairKeyT, ValueT BucketT;
unsigned NumBuckets;
BucketT *Buckets;
@@ -54,21 +57,26 @@
~DenseMap() {
const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
- if (P-Key != EmptyKey P-Key != TombstoneKey)
-P-Value.~ValueT();
- P-Key.~KeyT();
+ if (P-first != EmptyKey P-first != TombstoneKey)
+P-second.~ValueT();
+ P-first.~KeyT();
}
delete[] (char*)Buckets;
}
+ typedef DenseMapIteratorKeyT, ValueT iterator;
+ typedef DenseMapIteratorKeyT, ValueT const_iterator;
+ inline iterator begin() const;
+ inline iterator end() const;
+
unsigned size() const { return NumEntries; }
void clear() {
const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
- if (P-Key != EmptyKey P-Key != TombstoneKey) {
-P-Key = EmptyKey;
-P-Value.~ValueT();
+ if (P-first != EmptyKey P-first != TombstoneKey) {
+P-first = EmptyKey;
+P-second.~ValueT();
--NumEntries;
}
}
@@ -84,7 +92,7 @@
ValueT operator[](const KeyT Val) {
BucketT *TheBucket;
if (LookupBucketFor(Val, TheBucket))
- return TheBucket-Value;
+ return TheBucket-second;
// If the load of the hash table is more than 3/4, grow it.
if (NumEntries*4 = NumBuckets*3) {
@@ -92,9 +100,9 @@
LookupBucketFor(Val, TheBucket);
}
++NumEntries;
-TheBucket-Key = Val;
-new (TheBucket-Value) ValueT();
-return TheBucket-Value;
+TheBucket-first = Val;
+new (TheBucket-second) ValueT();
+return TheBucket-second;
}
private:
@@ -125,14 +133,14 @@
while (1) {
BucketT *ThisBucket = BucketsPtr + (BucketNo (NumBuckets-1));
// Found Val's bucket? If so, return it.
- if (ThisBucket-Key == Val) {
+ if (ThisBucket-first == Val) {
FoundBucket = ThisBucket;
return true;
}
// If we found an empty bucket, the key doesn't exist in the set.
// Insert it and return the default value.
- if (ThisBucket-Key == EmptyKey) {
+ if (ThisBucket-first == EmptyKey) {
// If we've already seen a tombstone while probing, fill it in instead
// of the empty bucket we eventually probed to.
if (FoundTombstone) ThisBucket = FoundTombstone;
@@ -142,7 +150,7 @@
// If this is a tombstone, remember it. If Val ends up not in the map,
we
// prefer to return it than something that would require more probing.
- if (ThisBucket-Key == TombstoneKey !FoundTombstone)
+ if (ThisBucket-first == TombstoneKey !FoundTombstone)
FoundTombstone = ThisBucket; // Remember the first tombstone found.
// Otherwise, it's a hash collision or a tombstone, continue quadratic
@@ -160,7 +168,7 @@
// Initialize all the keys to EmptyKey.
const KeyT EmptyKey = getEmptyKey();
for (unsigned i = 0; i != InitBuckets; ++i)
- new (Buckets[i].Key) KeyT(EmptyKey);
+ new (Buckets[i].first) KeyT(EmptyKey);
}
void grow() {
@@ -174,23 +182,23 @@
// Initialize all the keys to EmptyKey.
const KeyT EmptyKey = getEmptyKey();
for (unsigned i = 0, e = NumBuckets; i != e; ++i)
- new (Buckets[i].Key) KeyT(EmptyKey);
+ new (Buckets[i].first) KeyT(EmptyKey);
// Insert all the old elements.
const KeyT TombstoneKey = getTombstoneKey();
for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
- if (B-Key != EmptyKey B-Key != TombstoneKey) {
+ if (B-first != EmptyKey B-first != TombstoneKey) {
// Insert the key/value into the new table.
BucketT *DestBucket;
-bool FoundVal = LookupBucketFor(B-Key, DestBucket);
+bool FoundVal = LookupBucketFor(B-first, DestBucket);
assert(!FoundVal Key already in new map?);
-DestBucket-Key = B-Key;
-new
[llvm-commits] CVS: llvm/include/llvm/ADT/DenseMap.h
Changes in directory llvm/include/llvm/ADT:
DenseMap.h updated: 1.12 - 1.13
---
Log message:
add find/erase, add const iterators, fix bugs in iterators.
---
Diffs of the changes: (+67 -19)
DenseMap.h | 86 +++--
1 files changed, 67 insertions(+), 19 deletions(-)
Index: llvm/include/llvm/ADT/DenseMap.h
diff -u llvm/include/llvm/ADT/DenseMap.h:1.12
llvm/include/llvm/ADT/DenseMap.h:1.13
--- llvm/include/llvm/ADT/DenseMap.h:1.12 Fri Feb 2 13:27:13 2007
+++ llvm/include/llvm/ADT/DenseMap.hFri Feb 2 14:34:32 2007
@@ -41,6 +41,8 @@
templatetypename KeyT, typename ValueT
class DenseMapIterator;
+templatetypename KeyT, typename ValueT
+class DenseMapConstIterator;
templatetypename KeyT, typename ValueT
class DenseMap {
@@ -65,10 +67,23 @@
}
typedef DenseMapIteratorKeyT, ValueT iterator;
- typedef DenseMapIteratorKeyT, ValueT const_iterator;
- inline iterator begin() const;
- inline iterator end() const;
+ typedef DenseMapConstIteratorKeyT, ValueT const_iterator;
+ inline iterator begin() {
+ return DenseMapIteratorKeyT, ValueT(Buckets, Buckets+NumBuckets);
+ }
+ inline iterator end() {
+return DenseMapIteratorKeyT, ValueT(Buckets+NumBuckets,
+ Buckets+NumBuckets);
+ }
+ inline const_iterator begin() const {
+return DenseMapConstIteratorKeyT, ValueT(Buckets, Buckets+NumBuckets);
+ }
+ inline const_iterator end() const {
+return DenseMapConstIteratorKeyT, ValueT(Buckets+NumBuckets,
+ Buckets+NumBuckets);
+ }
+ bool empty() const { return NumEntries == 0; }
unsigned size() const { return NumEntries; }
void clear() {
@@ -89,6 +104,31 @@
return LookupBucketFor(Val, TheBucket);
}
+ iterator find(const KeyT Val) const {
+BucketT *TheBucket;
+if (LookupBucketFor(Val, TheBucket))
+ return iterator(TheBucket, Buckets+NumBuckets);
+return end();
+ }
+
+ bool erase(const KeyT Val) {
+BucketT *TheBucket;
+if (!LookupBucketFor(Val, TheBucket))
+ return false; // not in map.
+
+TheBucket-second.~ValueT();
+TheBucket-first = getTombstoneKey();
+--NumEntries;
+return true;
+ }
+ bool erase(iterator I) {
+BucketT *TheBucket = *I;
+TheBucket-second.~ValueT();
+TheBucket-first = getTombstoneKey();
+--NumEntries;
+return true;
+ }
+
ValueT operator[](const KeyT Val) {
BucketT *TheBucket;
if (LookupBucketFor(Val, TheBucket))
@@ -106,11 +146,13 @@
}
private:
- unsigned getHashValue(const KeyT Val) const {
+ static unsigned getHashValue(const KeyT Val) {
return DenseMapKeyInfoKeyT::getHashValue(Val);
}
- const KeyT getEmptyKey() const { return
DenseMapKeyInfoKeyT::getEmptyKey();}
- const KeyT getTombstoneKey() const {
+ static const KeyT getEmptyKey() {
+return DenseMapKeyInfoKeyT::getEmptyKey();
+ }
+ static const KeyT getTombstoneKey() {
return DenseMapKeyInfoKeyT::getTombstoneKey();
}
@@ -209,17 +251,18 @@
templatetypename KeyT, typename ValueT
class DenseMapIterator {
typedef std::pairKeyT, ValueT BucketT;
+protected:
const BucketT *Ptr, *End;
public:
DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
AdvancePastEmptyBuckets();
}
- const std::pairKeyT, ValueT operator*() const {
-return *Ptr;
+ std::pairKeyT, ValueT operator*() const {
+return *const_castBucketT*(Ptr);
}
- const std::pairKeyT, ValueT *operator-() const {
-return Ptr;
+ std::pairKeyT, ValueT *operator-() const {
+return const_castBucketT*(Ptr);
}
bool operator==(const DenseMapIterator RHS) const {
@@ -243,20 +286,25 @@
const KeyT Empty = DenseMapKeyInfoKeyT::getEmptyKey();
const KeyT Tombstone = DenseMapKeyInfoKeyT::getTombstoneKey();
-while (Ptr != End Ptr-first != Empty Ptr-first != Tombstone)
+while (Ptr != End (Ptr-first == Empty || Ptr-first == Tombstone))
++Ptr;
}
};
-
-templatetypename KeyT, typename ValueT
-inline DenseMapIteratorKeyT, ValueT DenseMapKeyT, ValueT::begin() const {
- return DenseMapIteratorKeyT, ValueT(Buckets, Buckets+NumBuckets);
-}
templatetypename KeyT, typename ValueT
-inline DenseMapIteratorKeyT, ValueT DenseMapKeyT, ValueT::end() const {
- return DenseMapIteratorKeyT, ValueT(Buckets+NumBuckets,
Buckets+NumBuckets);
-}
+class DenseMapConstIterator : public DenseMapIteratorKeyT, ValueT {
+public:
+ DenseMapConstIterator(const std::pairKeyT, ValueT *Pos,
+const std::pairKeyT, ValueT *E)
+: DenseMapIteratorKeyT, ValueT(Pos, E) {
+ }
+ const std::pairKeyT, ValueT operator*() const {
+return *this-Ptr;
+ }
+ const std::pairKeyT, ValueT *operator-() const {
+return this-Ptr;
+ }
+};
} // end namespace llvm
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
[llvm-commits] CVS: llvm/include/llvm/ADT/DenseMap.h
Changes in directory llvm/include/llvm/ADT: DenseMap.h updated: 1.13 - 1.14 --- Log message: silence annoying warning in release-asserts build --- Diffs of the changes: (+1 -0) DenseMap.h |1 + 1 files changed, 1 insertion(+) Index: llvm/include/llvm/ADT/DenseMap.h diff -u llvm/include/llvm/ADT/DenseMap.h:1.13 llvm/include/llvm/ADT/DenseMap.h:1.14 --- llvm/include/llvm/ADT/DenseMap.h:1.13 Fri Feb 2 14:34:32 2007 +++ llvm/include/llvm/ADT/DenseMap.hFri Feb 2 15:19:18 2007 @@ -233,6 +233,7 @@ // Insert the key/value into the new table. BucketT *DestBucket; bool FoundVal = LookupBucketFor(B-first, DestBucket); +FoundVal = FoundVal; // silence warning. assert(!FoundVal Key already in new map?); DestBucket-first = B-first; new (DestBucket-second) ValueT(B-second); ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/DenseMap.h
Changes in directory llvm/include/llvm/ADT:
DenseMap.h updated: 1.10 - 1.11
---
Log message:
Add a new dense hash table implementation
---
Diffs of the changes: (+203 -0)
DenseMap.h | 203 +
1 files changed, 203 insertions(+)
Index: llvm/include/llvm/ADT/DenseMap.h
diff -u /dev/null llvm/include/llvm/ADT/DenseMap.h:1.11
--- /dev/null Thu Feb 1 01:50:09 2007
+++ llvm/include/llvm/ADT/DenseMap.hThu Feb 1 01:49:59 2007
@@ -0,0 +1,203 @@
+//===- llvm/ADT/DenseMap.h - Dense probed hash table *- C++
-*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Chris Lattner and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===--===//
+//
+// This file defines the DenseMap class.
+//
+//===--===//
+
+#ifndef LLVM_ADT_DENSEMAP_H
+#define LLVM_ADT_DENSEMAP_H
+
+#include llvm/Support/DataTypes.h
+#include cassert
+
+namespace llvm {
+
+templatetypename T
+struct DenseMapKeyInfo {
+ //static inline T getEmptyKey();
+ //static inline T getTombstoneKey();
+ //static unsigned getHashValue(const T Val);
+ //static bool isPod()
+};
+
+templatetypename T
+struct DenseMapKeyInfoT* {
+ static inline T* getEmptyKey() { return (T*)-1; }
+ static inline T* getTombstoneKey() { return (T*)-2; }
+ static unsigned getHashValue(const T *PtrVal) {
+return (unsigned)((uintptr_t)PtrVal 4) ^
+ (unsigned)((uintptr_t)PtrVal 9);
+ }
+ static bool isPod() { return true; }
+};
+
+
+templatetypename KeyT, typename ValueT
+class DenseMap {
+ struct BucketT { KeyT Key; ValueT Value; };
+ unsigned NumBuckets;
+ BucketT *Buckets;
+
+ unsigned NumEntries;
+ DenseMap(const DenseMap ); // not implemented.
+public:
+ explicit DenseMap(unsigned NumInitBuckets = 8) {
+init(NumInitBuckets);
+ }
+ ~DenseMap() {
+const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
+ if (P-Key != EmptyKey P-Key != TombstoneKey)
+P-Value.~ValueT();
+ P-Key.~KeyT();
+}
+delete[] (char*)Buckets;
+ }
+
+ unsigned size() const { return NumEntries; }
+
+ void clear() {
+const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
+ if (P-Key != EmptyKey P-Key != TombstoneKey) {
+P-Key = EmptyKey;
+P-Value.~ValueT();
+--NumEntries;
+ }
+}
+assert(NumEntries == 0 Node count imbalance!);
+ }
+
+ /// count - Return true if the specified key is in the map.
+ bool count(const KeyT Val) const {
+BucketT *TheBucket;
+return LookupBucketFor(Val, TheBucket);
+ }
+
+ ValueT operator[](const KeyT Val) {
+BucketT *TheBucket;
+if (LookupBucketFor(Val, TheBucket))
+ return TheBucket-Value;
+
+// If the load of the hash table is more than 3/4, grow it.
+if (NumEntries*4 = NumBuckets*3) {
+ this-grow();
+ LookupBucketFor(Val, TheBucket);
+}
+++NumEntries;
+TheBucket-Key = Val;
+new (TheBucket-Value) ValueT();
+return TheBucket-Value;
+ }
+
+private:
+ unsigned getHashValue(const KeyT Val) const {
+return DenseMapKeyInfoKeyT::getHashValue(Val);
+ }
+ const KeyT getEmptyKey() const { return
DenseMapKeyInfoKeyT::getEmptyKey();}
+ const KeyT getTombstoneKey() const {
+return DenseMapKeyInfoKeyT::getTombstoneKey();
+ }
+
+ /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
+ /// FoundBucket. If the bucket contains the key and a value, this returns
+ /// true, otherwise it returns a bucket with an empty marker or tombstone and
+ /// returns false.
+ bool LookupBucketFor(const KeyT Val, BucketT *FoundBucket) const {
+unsigned BucketNo = getHashValue(Val);
+unsigned ProbeAmt = 1;
+BucketT *BucketsPtr = Buckets;
+
+// FoundTombstone - Keep track of whether we find a tombstone while
probing.
+BucketT *FoundTombstone = 0;
+const KeyT EmptyKey = getEmptyKey();
+const KeyT TombstoneKey = getTombstoneKey();
+assert(Val != EmptyKey Val != TombstoneKey
+ Empty/Tombstone value shouldn't be inserted into map!);
+
+while (1) {
+ BucketT *ThisBucket = BucketsPtr + (BucketNo (NumBuckets-1));
+ // Found Val's bucket? If so, return it.
+ if (ThisBucket-Key == Val) {
+FoundBucket = ThisBucket;
+return true;
+ }
+
+ // If we found an empty bucket, the key doesn't exist in the set.
+ // Insert it and return the default value.
+ if (ThisBucket-Key == EmptyKey) {
+// If we've already seen a tombstone while probing, fill it in instead
+// of the empty
