From cc8f2c2156b7e4ae867585f7f958172587aa9121 Mon Sep 17 00:00:00 2001 From: Chaoren Lin Date: Wed, 4 Mar 2015 06:05:37 +0000 Subject: [PATCH] Revert "[ADT] fail-fast iterators for DenseMap" This reverts commit 4b7263d855006988854036b4a4891fcf19aebe65. r231125 http://reviews.llvm.org/D7931 This was causing many LLDB tests to fail on OS X, Linux, and FreeBSD. https://bpaste.net/show/6a23e1f53623 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@231214 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/DenseMap.h | 63 +++++++--------------- include/llvm/ADT/EpochTracker.h | 95 --------------------------------- 2 files changed, 20 insertions(+), 138 deletions(-) delete mode 100644 include/llvm/ADT/EpochTracker.h diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 8c65f70838e..d947ffaa7ed 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -15,7 +15,6 @@ #define LLVM_ADT_DENSEMAP_H #include "llvm/ADT/DenseMapInfo.h" -#include "llvm/ADT/EpochTracker.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" @@ -51,7 +50,7 @@ class DenseMapIterator; template -class DenseMapBase : public DebugEpochBase { +class DenseMapBase { public: typedef unsigned size_type; typedef KeyT key_type; @@ -63,17 +62,16 @@ public: const_iterator; inline iterator begin() { // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). - return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this); + return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); } inline iterator end() { - return iterator(getBucketsEnd(), getBucketsEnd(), *this, true); + return iterator(getBucketsEnd(), getBucketsEnd(), true); } inline const_iterator begin() const { - return empty() ? end() - : const_iterator(getBuckets(), getBucketsEnd(), *this); + return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); } inline const_iterator end() const { - return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true); + return const_iterator(getBucketsEnd(), getBucketsEnd(), true); } bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { @@ -83,13 +81,11 @@ public: /// Grow the densemap so that it has at least Size buckets. Does not shrink void resize(size_type Size) { - incrementEpoch(); if (Size > getNumBuckets()) grow(Size); } void clear() { - incrementEpoch(); if (getNumEntries() == 0 && getNumTombstones() == 0) return; // If the capacity of the array is huge, and the # elements used is small, @@ -122,13 +118,13 @@ public: iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), *this, true); + return iterator(TheBucket, getBucketsEnd(), true); return end(); } const_iterator find(const KeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), *this, true); + return const_iterator(TheBucket, getBucketsEnd(), true); return end(); } @@ -141,14 +137,14 @@ public: iterator find_as(const LookupKeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), *this, true); + return iterator(TheBucket, getBucketsEnd(), true); return end(); } template const_iterator find_as(const LookupKeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), *this, true); + return const_iterator(TheBucket, getBucketsEnd(), true); return end(); } @@ -167,13 +163,12 @@ public: std::pair insert(const std::pair &KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), + return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - true); + return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); } // Inserts key,value pair into the map if the key isn't already in the map. @@ -182,15 +177,14 @@ public: std::pair insert(std::pair &&KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), + return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), false); // Already in map. - + // Otherwise, insert the new element. TheBucket = InsertIntoBucket(std::move(KV.first), std::move(KV.second), TheBucket); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - true); + return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); } /// insert - Range insertion of pairs. @@ -437,8 +431,6 @@ private: } BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { - incrementEpoch(); - // If the load of the hash table is more than 3/4, or if fewer than 1/8 of // the buckets are empty (meaning that many are filled with tombstones), // grow the table. @@ -995,10 +987,9 @@ private: template -class DenseMapIterator : DebugEpochBase::HandleBase { +class DenseMapIterator { typedef DenseMapIterator ConstIterator; friend class DenseMapIterator; - friend class DenseMapIterator; public: typedef ptrdiff_t difference_type; @@ -1012,10 +1003,8 @@ private: public: DenseMapIterator() : Ptr(nullptr), End(nullptr) {} - DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, - bool NoAdvance = false) - : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { - assert(isHandleInSync() && "invalid construction!"); + DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) + : Ptr(Pos), End(E) { if (!NoAdvance) AdvancePastEmptyBuckets(); } @@ -1026,40 +1015,28 @@ public: typename = typename std::enable_if::type> DenseMapIterator( const DenseMapIterator &I) - : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {} + : Ptr(I.Ptr), End(I.End) {} reference operator*() const { - assert(isHandleInSync() && "invalid iterator access!"); return *Ptr; } pointer operator->() const { - assert(isHandleInSync() && "invalid iterator access!"); return Ptr; } bool operator==(const ConstIterator &RHS) const { - assert((!Ptr || isHandleInSync()) && "handle not in sync!"); - assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); - assert(getEpochAddress() == RHS.getEpochAddress() && - "comparing incomparable iterators!"); - return Ptr == RHS.Ptr; + return Ptr == RHS.operator->(); } bool operator!=(const ConstIterator &RHS) const { - assert((!Ptr || isHandleInSync()) && "handle not in sync!"); - assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); - assert(getEpochAddress() == RHS.getEpochAddress() && - "comparing incomparable iterators!"); - return Ptr != RHS.Ptr; + return Ptr != RHS.operator->(); } inline DenseMapIterator& operator++() { // Preincrement - assert(isHandleInSync() && "invalid iterator access!"); ++Ptr; AdvancePastEmptyBuckets(); return *this; } DenseMapIterator operator++(int) { // Postincrement - assert(isHandleInSync() && "invalid iterator access!"); DenseMapIterator tmp = *this; ++*this; return tmp; } diff --git a/include/llvm/ADT/EpochTracker.h b/include/llvm/ADT/EpochTracker.h deleted file mode 100644 index 179822afb32..00000000000 --- a/include/llvm/ADT/EpochTracker.h +++ /dev/null @@ -1,95 +0,0 @@ -//===- llvm/ADT/EpochTracker.h - ADT epoch tracking --------------*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes. -// These can be used to write iterators that are fail-fast when LLVM is built -// with asserts enabled. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ADT_EPOCH_TRACKER_H -#define LLVM_ADT_EPOCH_TRACKER_H - -#include - -namespace llvm { - -#ifdef NDEBUG - -class DebugEpochBase { -public: - void incrementEpoch() {} - - class HandleBase { - public: - HandleBase() {} - explicit HandleBase(const DebugEpochBase *) {} - bool isHandleInSync() { return true; } - }; -}; - -#else - -/// \brief A base class for data structure classes wishing to make iterators -/// ("handles") pointing into themselves fail-fast. When building without -/// asserts, this class is empty and does nothing. -/// -/// DebugEpochBase does not by itself track handles pointing into itself. The -/// expectation is that routines touching the handles will poll on -/// isHandleInSync at appropriate points to assert that the handle they're using -/// is still valid. -/// -class DebugEpochBase { - uint64_t Epoch; - -public: - DebugEpochBase() : Epoch(0) {} - - /// \brief Calling incrementEpoch invalidates all handles pointing into the - /// calling instance. - void incrementEpoch() { ++Epoch; } - - /// \brief The destructor calls incrementEpoch to make use-after-free bugs - /// more likely to crash deterministically. - ~DebugEpochBase() { incrementEpoch(); } - - /// \brief A base class for iterator classes ("handles") that wish to poll for - /// iterator invalidating modifications in the underlying data structure. - /// When LLVM is built without asserts, this class is empty and does nothing. - /// - /// HandleBase does not track the parent data structure by itself. It expects - /// the routines modifying the data structure to call incrementEpoch when they - /// make an iterator-invalidating modification. - /// - class HandleBase { - const uint64_t *EpochAddress; - uint64_t EpochAtCreation; - - public: - HandleBase() : EpochAddress(nullptr), EpochAtCreation(UINT64_MAX) {} - - explicit HandleBase(const DebugEpochBase *Parent) - : EpochAddress(&Parent->Epoch), EpochAtCreation(Parent->Epoch) {} - - /// \brief Returns true if the DebugEpochBase this Handle is linked to has - /// not called incrementEpoch on itself since the creation of this - /// HandleBase instance. - bool isHandleInSync() const { return *EpochAddress == EpochAtCreation; } - - /// \brief Returns a pointer to the epoch word stored in the data structure - /// this handle points into. - const uint64_t *getEpochAddress() const { return EpochAddress; } - }; -}; - -#endif - -} // namespace llvm - -#endif -- 2.34.1