From c36c540c5bfce941f3d892919394d092491211f2 Mon Sep 17 00:00:00 2001 From: Douglas Gregor Date: Thu, 9 Apr 2009 17:29:08 +0000 Subject: [PATCH] Simple DeclContext's internal representation by always storing a StoredDeclsMap, instead of using the it's-an-array-or-its-a-map trick. I'll verify that performance isn't impacted later; for now, I need the common representation. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@68715 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/DeclBase.h | 27 ++------ lib/AST/DeclBase.cpp | 117 +++++------------------------------ 2 files changed, 20 insertions(+), 124 deletions(-) diff --git a/include/clang/AST/DeclBase.h b/include/clang/AST/DeclBase.h index 4194ba0459..4675136d49 100644 --- a/include/clang/AST/DeclBase.h +++ b/include/clang/AST/DeclBase.h @@ -349,21 +349,10 @@ class DeclContext { /// DeclKind - This indicates which class this is. Decl::Kind DeclKind : 8; - /// LookupPtrKind - Describes what kind of pointer LookupPtr - /// actually is. - enum LookupPtrKind { - /// LookupIsMap - Indicates that LookupPtr is actually a map. - LookupIsMap = 7 - }; - - /// LookupPtr - Pointer to a data structure used to lookup - /// declarations within this context. If the context contains fewer - /// than seven declarations, the number of declarations is provided - /// in the 3 lowest-order bits and the upper bits are treated as a - /// pointer to an array of NamedDecl pointers. If the context - /// contains seven or more declarations, the upper bits are treated - /// as a pointer to a DenseMap. - llvm::PointerIntPair LookupPtr; + /// \brief Pointer to the data structure used to lookup declarations + /// within this context, which is a DenseMap. + void* LookupPtr; /// FirstDecl - The first declaration stored within this declaration /// context. @@ -377,7 +366,7 @@ class DeclContext { protected: DeclContext(Decl::Kind K) - : DeclKind(K), LookupPtr(), FirstDecl(0), LastDecl(0) { } + : DeclKind(K), LookupPtr(0), FirstDecl(0), LastDecl(0) { } void DestroyDecls(ASTContext &C); @@ -759,12 +748,8 @@ public: // Low-level accessors - /// \brief Determine if the lookup structure is a - /// DenseMap. Othewise, it is an array. - bool isLookupMap() const { return LookupPtr.getInt() == LookupIsMap; } - /// \brief Retrieve the internal representation of the lookup structure. - llvm::PointerIntPair getLookupPtr() const { return LookupPtr; } + void* getLookupPtr() const { return LookupPtr; } static bool classof(const Decl *D); static bool classof(const DeclContext *D) { return true; } diff --git a/lib/AST/DeclBase.cpp b/lib/AST/DeclBase.cpp index 45c5494d4c..f3cf7814e5 100644 --- a/lib/AST/DeclBase.cpp +++ b/lib/AST/DeclBase.cpp @@ -365,10 +365,7 @@ bool DeclContext::classof(const Decl *D) { } DeclContext::~DeclContext() { - if (isLookupMap()) - delete static_cast(LookupPtr.getPointer()); - else - delete [] static_cast(LookupPtr.getPointer()); + delete static_cast(LookupPtr); } void DeclContext::DestroyDecls(ASTContext &C) { @@ -488,29 +485,18 @@ DeclContext::lookup(DeclarationName Name) { /// If there is no lookup data structure, build one now by walking /// all of the linked DeclContexts (in declaration order!) and /// inserting their values. - if (LookupPtr.getPointer() == 0) + if (!LookupPtr) { buildLookup(this); - if (isLookupMap()) { - StoredDeclsMap *Map = static_cast(LookupPtr.getPointer()); - StoredDeclsMap::iterator Pos = Map->find(Name); - if (Pos == Map->end()) + if (!LookupPtr) return lookup_result(0, 0); - return Pos->second.getLookupResult(); - } - - // We have a small array. Look into it. - unsigned Size = LookupPtr.getInt(); - NamedDecl **Array = static_cast(LookupPtr.getPointer()); - for (unsigned Idx = 0; Idx != Size; ++Idx) - if (Array[Idx]->getDeclName() == Name) { - unsigned Last = Idx + 1; - while (Last != Size && Array[Last]->getDeclName() == Name) - ++Last; - return lookup_result(&Array[Idx], &Array[Last]); - } + } - return lookup_result(0, 0); + StoredDeclsMap *Map = static_cast(LookupPtr); + StoredDeclsMap::iterator Pos = Map->find(Name); + if (Pos == Map->end()) + return lookup_result(0, 0); + return Pos->second.getLookupResult(); } DeclContext::lookup_const_result @@ -550,7 +536,7 @@ void DeclContext::makeDeclVisibleInContext(NamedDecl *D) { // If we already have a lookup data structure, perform the insertion // into it. Otherwise, be lazy and don't build that structure until // someone asks for it. - if (LookupPtr.getPointer()) + if (LookupPtr) makeDeclVisibleInContextImpl(D); // If we are a transparent context, insert into our parent context, @@ -570,86 +556,11 @@ void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D) { if (isa(D)) return; - bool MayBeRedeclaration = true; - - if (!isLookupMap()) { - unsigned Size = LookupPtr.getInt(); - - // The lookup data is stored as an array. Search through the array - // to find the insertion location. - NamedDecl **Array; - if (Size == 0) { - Array = new NamedDecl*[LookupIsMap - 1]; - LookupPtr.setPointer(Array); - } else { - Array = static_cast(LookupPtr.getPointer()); - } - - // We always keep declarations of the same name next to each other - // in the array, so that it is easy to return multiple results - // from lookup(). - unsigned FirstMatch; - for (FirstMatch = 0; FirstMatch != Size; ++FirstMatch) - if (Array[FirstMatch]->getDeclName() == D->getDeclName()) - break; - - unsigned InsertPos = FirstMatch; - if (FirstMatch != Size) { - // We found another declaration with the same name. First - // determine whether this is a redeclaration of an existing - // declaration in this scope, in which case we will replace the - // existing declaration. - unsigned LastMatch = FirstMatch; - for (; LastMatch != Size; ++LastMatch) { - if (Array[LastMatch]->getDeclName() != D->getDeclName()) - break; - - if (D->declarationReplaces(Array[LastMatch])) { - // D is a redeclaration of an existing element in the - // array. Replace that element with D. - Array[LastMatch] = D; - return; - } - } - - // [FirstMatch, LastMatch) contains the set of declarations that - // have the same name as this declaration. Determine where the - // declaration D will be inserted into this range. - if (D->getKind() == Decl::UsingDirective || - D->getIdentifierNamespace() == Decl::IDNS_Tag) - InsertPos = LastMatch; - else if (Array[LastMatch-1]->getIdentifierNamespace() == Decl::IDNS_Tag) - InsertPos = LastMatch - 1; - else - InsertPos = LastMatch; - } - - if (Size < LookupIsMap - 1) { - // The new declaration will fit in the array. Insert the new - // declaration at the position Match in the array. - for (unsigned Idx = Size; Idx > InsertPos; --Idx) - Array[Idx] = Array[Idx-1]; - - Array[InsertPos] = D; - LookupPtr.setInt(Size + 1); - return; - } - - // We've reached capacity in this array. Create a map and copy in - // all of the declarations that were stored in the array. - StoredDeclsMap *Map = new StoredDeclsMap(16); - LookupPtr.setPointer(Map); - LookupPtr.setInt(LookupIsMap); - for (unsigned Idx = 0; Idx != LookupIsMap - 1; ++Idx) - makeDeclVisibleInContextImpl(Array[Idx]); - delete [] Array; - - // Fall through to perform insertion into the map. - MayBeRedeclaration = false; - } + if (!LookupPtr) + LookupPtr = new StoredDeclsMap; // Insert this declaration into the map. - StoredDeclsMap &Map = *static_cast(LookupPtr.getPointer()); + StoredDeclsMap &Map = *static_cast(LookupPtr); StoredDeclsList &DeclNameEntries = Map[D->getDeclName()]; if (DeclNameEntries.isNull()) { DeclNameEntries.setOnlyValue(D); @@ -659,7 +570,7 @@ void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D) { // If it is possible that this is a redeclaration, check to see if there is // already a decl for which declarationReplaces returns true. If there is // one, just replace it and return. - if (MayBeRedeclaration && DeclNameEntries.HandleRedeclaration(D)) + if (DeclNameEntries.HandleRedeclaration(D)) return; // Put this declaration into the appropriate slot. -- 2.40.0