Index: clang/lib/Frontend/ASTUnit.cpp =================================================================== --- clang/lib/Frontend/ASTUnit.cpp +++ clang/lib/Frontend/ASTUnit.cpp @@ -35,9 +35,9 @@ #include "clang/Serialization/ASTReader.h" #include "clang/Serialization/ASTWriter.h" #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringSet.h" #include "llvm/Support/CrashRecoveryContext.h" +#include "llvm/Support/DJB.h" #include "llvm/Support/Host.h" #include "llvm/Support/MemoryBuffer.h" #include "llvm/Support/Mutex.h" @@ -185,7 +185,7 @@ ASTUnit::ASTUnit(bool _MainFileIsAST) : Reader(nullptr), HadModuleLoaderFatalFailure(false), OnlyLocalDecls(false), CaptureDiagnostics(false), - MainFileIsAST(_MainFileIsAST), + MainFileIsAST(_MainFileIsAST), TUKind(TU_Complete), WantTiming(getenv("LIBCLANG_TIMING")), OwnsRemappedFileBuffers(true), NumStoredDiagnosticsFromDriver(0), @@ -196,7 +196,7 @@ CompletionCacheTopLevelHashValue(0), PreambleTopLevelHashValue(0), CurrentTopLevelHashValue(0), - UnsafeToFree(false) { + UnsafeToFree(false) { if (getenv("LIBCLANG_OBJTRACKING")) fprintf(stderr, "+++ %u translation units\n", ++ActiveASTUnitObjects); } @@ -219,8 +219,8 @@ delete RB.second; } - ClearCachedCompletionResults(); - + ClearCachedCompletionResults(); + if (getenv("LIBCLANG_OBJTRACKING")) fprintf(stderr, "--- %u translation units\n", --ActiveASTUnitObjects); } @@ -229,20 +229,20 @@ this->PP = std::move(PP); } -/// \brief Determine the set of code-completion contexts in which this +/// \brief Determine the set of code-completion contexts in which this /// declaration should be shown. static unsigned getDeclShowContexts(const NamedDecl *ND, const LangOptions &LangOpts, bool &IsNestedNameSpecifier) { IsNestedNameSpecifier = false; - + if (isa(ND)) ND = dyn_cast(ND->getUnderlyingDecl()); if (!ND) return 0; - + uint64_t Contexts = 0; - if (isa(ND) || isa(ND) || + if (isa(ND) || isa(ND) || isa(ND) || isa(ND) || isa(ND)) { // Types can appear in these contexts. @@ -257,12 +257,12 @@ // In C++, types can appear in expressions contexts (for functional casts). if (LangOpts.CPlusPlus) Contexts |= (1LL << CodeCompletionContext::CCC_Expression); - + // In Objective-C, message sends can send interfaces. In Objective-C++, // all types are available due to functional casts. if (LangOpts.CPlusPlus || isa(ND)) Contexts |= (1LL << CodeCompletionContext::CCC_ObjCMessageReceiver); - + // In Objective-C, you can only be a subclass of another Objective-C class if (const auto *ID = dyn_cast(ND)) { // Objective-C interfaces can be used in a class property expression. @@ -274,7 +274,7 @@ // Deal with tag names. if (isa(ND)) { Contexts |= (1LL << CodeCompletionContext::CCC_EnumTag); - + // Part of the nested-name-specifier in C++0x. if (LangOpts.CPlusPlus11) IsNestedNameSpecifier = true; @@ -283,7 +283,7 @@ Contexts |= (1LL << CodeCompletionContext::CCC_UnionTag); else Contexts |= (1LL << CodeCompletionContext::CCC_ClassOrStructTag); - + if (LangOpts.CPlusPlus) IsNestedNameSpecifier = true; } else if (isa(ND)) @@ -300,24 +300,24 @@ Contexts = (1LL << CodeCompletionContext::CCC_ObjCCategoryName); } else if (isa(ND) || isa(ND)) { Contexts = (1LL << CodeCompletionContext::CCC_Namespace); - + // Part of the nested-name-specifier. IsNestedNameSpecifier = true; } - + return Contexts; } void ASTUnit::CacheCodeCompletionResults() { if (!TheSema) return; - + SimpleTimer Timer(WantTiming); Timer.setOutput("Cache global code completions for " + getMainFileName()); // Clear out the previous results. ClearCachedCompletionResults(); - + // Gather the set of global code completions. typedef CodeCompletionResult Result; SmallVector Results; @@ -325,7 +325,7 @@ CodeCompletionTUInfo CCTUInfo(CachedCompletionAllocator); TheSema->GatherGlobalCodeCompletions(*CachedCompletionAllocator, CCTUInfo, Results); - + // Translate global code completions into cached completions. llvm::DenseMap CompletionTypes; CodeCompletionContext CCContext(CodeCompletionContext::CCC_TopLevel); @@ -344,7 +344,7 @@ CachedResult.Kind = R.CursorKind; CachedResult.Availability = R.Availability; - // Keep track of the type of this completion in an ASTContext-agnostic + // Keep track of the type of this completion in an ASTContext-agnostic // way. QualType UsageType = getDeclUsageType(*Ctx, R.Declaration); if (UsageType.isNull()) { @@ -356,7 +356,7 @@ CachedResult.TypeClass = getSimplifiedTypeClass(CanUsageType); // Determine whether we have already seen this type. If so, we save - // ourselves the work of formatting the type string by using the + // ourselves the work of formatting the type string by using the // temporary, CanQualType-based hash table to find the associated value. unsigned &TypeValue = CompletionTypes[CanUsageType]; if (TypeValue == 0) { @@ -364,12 +364,12 @@ CachedCompletionTypes[QualType(CanUsageType).getAsString()] = TypeValue; } - + CachedResult.Type = TypeValue; } - + CachedCompletionResults.push_back(CachedResult); - + /// Handle nested-name-specifiers in C++. if (TheSema->Context.getLangOpts().CPlusPlus && IsNestedNameSpecifier && !R.StartsNestedNameSpecifier) { @@ -392,10 +392,10 @@ isa(R.Declaration)) NNSContexts |= (1LL << CodeCompletionContext::CCC_Namespace); - if (unsigned RemainingContexts + if (unsigned RemainingContexts = NNSContexts & ~CachedResult.ShowInContexts) { - // If there any contexts where this completion can be a - // nested-name-specifier but isn't already an option, create a + // If there any contexts where this completion can be a + // nested-name-specifier but isn't already an option, create a // nested-name-specifier completion. R.StartsNestedNameSpecifier = true; CachedResult.Completion = R.CreateCodeCompletionString( @@ -410,13 +410,13 @@ } break; } - + case Result::RK_Keyword: case Result::RK_Pattern: // Ignore keywords and patterns; we don't care, since they are so // easily regenerated. break; - + case Result::RK_Macro: { CachedCodeCompletionResult CachedResult; CachedResult.Completion = R.CreateCodeCompletionString( @@ -446,7 +446,7 @@ } } } - + // Save the current top-level hash value. CompletionCacheTopLevelHashValue = CurrentTopLevelHashValue; } @@ -486,10 +486,10 @@ bool AllowCompatibleDifferences) override { if (InitializedLanguage) return false; - + LangOpt = LangOpts; InitializedLanguage = true; - + updated(); return false; } @@ -798,14 +798,14 @@ /// \brief Add the given macro to the hash of all top-level entities. void AddDefinedMacroToHash(const Token &MacroNameTok, unsigned &Hash) { - Hash = llvm::HashString(MacroNameTok.getIdentifierInfo()->getName(), Hash); + Hash = llvm::djbHash(MacroNameTok.getIdentifierInfo()->getName(), Hash); } -/// \brief Preprocessor callback class that updates a hash value with the names +/// \brief Preprocessor callback class that updates a hash value with the names /// of all macros that have been defined by the translation unit. class MacroDefinitionTrackerPPCallbacks : public PPCallbacks { unsigned &Hash; - + public: explicit MacroDefinitionTrackerPPCallbacks(unsigned &Hash) : Hash(Hash) { } @@ -819,11 +819,11 @@ void AddTopLevelDeclarationToHash(Decl *D, unsigned &Hash) { if (!D) return; - + DeclContext *DC = D->getDeclContext(); if (!DC) return; - + if (!(DC->isTranslationUnit() || DC->getLookupParent()->isTranslationUnit())) return; @@ -834,16 +834,16 @@ if (!EnumD->isScoped()) { for (const auto *EI : EnumD->enumerators()) { if (EI->getIdentifier()) - Hash = llvm::HashString(EI->getIdentifier()->getName(), Hash); + Hash = llvm::djbHash(EI->getIdentifier()->getName(), Hash); } } } if (ND->getIdentifier()) - Hash = llvm::HashString(ND->getIdentifier()->getName(), Hash); + Hash = llvm::djbHash(ND->getIdentifier()->getName(), Hash); else if (DeclarationName Name = ND->getDeclName()) { std::string NameStr = Name.getAsString(); - Hash = llvm::HashString(NameStr, Hash); + Hash = llvm::djbHash(NameStr, Hash); } return; } @@ -851,7 +851,7 @@ if (ImportDecl *ImportD = dyn_cast(D)) { if (Module *Mod = ImportD->getImportedModule()) { std::string ModName = Mod->getFullModuleName(); - Hash = llvm::HashString(ModName, Hash); + Hash = llvm::djbHash(ModName, Hash); } return; } @@ -860,7 +860,7 @@ class TopLevelDeclTrackerConsumer : public ASTConsumer { ASTUnit &Unit; unsigned &Hash; - + public: TopLevelDeclTrackerConsumer(ASTUnit &_Unit, unsigned &Hash) : Unit(_Unit), Hash(Hash) { @@ -933,7 +933,7 @@ bool hasCodeCompletionSupport() const override { return false; } TranslationUnitKind getTranslationUnitKind() override { - return Unit.getTranslationUnitKind(); + return Unit.getTranslationUnitKind(); } }; @@ -1052,11 +1052,11 @@ Clang->setInvocation(CCInvocation); OriginalSourceFile = Clang->getFrontendOpts().Inputs[0].getFile(); - + // Set up diagnostics, capturing any diagnostics that would // otherwise be dropped. Clang->setDiagnostics(&getDiagnostics()); - + // Create the target instance. Clang->setTarget(TargetInfo::CreateTargetInfo( Clang->getDiagnostics(), Clang->getInvocation().TargetOpts)); @@ -1068,7 +1068,7 @@ // FIXME: We shouldn't need to do this, the target should be immutable once // created. This complexity should be lifted elsewhere. Clang->getTarget().adjust(Clang->getLangOpts()); - + assert(Clang->getFrontendOpts().Inputs.size() == 1 && "Invocation must have exactly one source file!"); assert(Clang->getFrontendOpts().Inputs[0].getKind().getFormat() == @@ -1097,10 +1097,10 @@ // Create a file manager object to provide access to and cache the filesystem. Clang->setFileManager(&getFileManager()); - + // Create the source manager. Clang->setSourceManager(&getSourceManager()); - + // If the main file has been overridden due to the use of a preamble, // make that override happen and introduce the preamble. if (OverrideMainBuffer) { @@ -1135,7 +1135,7 @@ goto error; transferASTDataFromCompilerInstance(*Clang); - + Act->EndSourceFile(); FailedParseDiagnostics.clear(); @@ -1204,10 +1204,10 @@ /// the source file. /// /// This routine will compute the preamble of the main source file. If a -/// non-trivial preamble is found, it will precompile that preamble into a +/// non-trivial preamble is found, it will precompile that preamble into a /// precompiled header so that the precompiled preamble can be used to reduce /// reparsing time. If a precompiled preamble has already been constructed, -/// this routine will determine if it is still valid and, if so, avoid +/// this routine will determine if it is still valid and, if so, avoid /// rebuilding the precompiled preamble. /// /// \param AllowRebuild When true (the default), this routine is @@ -1442,7 +1442,7 @@ if (!AST) return nullptr; } - + if (!ResourceFilesPath.empty()) { // Override the resources path. CI->getHeaderSearchOpts().ResourceDir = ResourceFilesPath; @@ -1478,11 +1478,11 @@ Clang->setInvocation(std::move(CI)); AST->OriginalSourceFile = Clang->getFrontendOpts().Inputs[0].getFile(); - + // Set up diagnostics, capturing any diagnostics that would // otherwise be dropped. Clang->setDiagnostics(&AST->getDiagnostics()); - + // Create the target instance. Clang->setTarget(TargetInfo::CreateTargetInfo( Clang->getDiagnostics(), Clang->getInvocation().TargetOpts)); @@ -1494,7 +1494,7 @@ // FIXME: We shouldn't need to do this, the target should be immutable once // created. This complexity should be lifted elsewhere. Clang->getTarget().adjust(Clang->getLangOpts()); - + assert(Clang->getFrontendOpts().Inputs.size() == 1 && "Invocation must have exactly one source file!"); assert(Clang->getFrontendOpts().Inputs[0].getKind().getFormat() == @@ -1512,7 +1512,7 @@ // Create a file manager object to provide access to and cache the filesystem. Clang->setFileManager(&AST->getFileManager()); - + // Create the source manager. Clang->setSourceManager(&AST->getSourceManager()); @@ -1558,7 +1558,7 @@ // Steal the created target, context, and preprocessor. AST->transferASTDataFromCompilerInstance(*Clang); - + Act->EndSourceFile(); if (OwnAST) @@ -1623,7 +1623,7 @@ AST->FileSystemOpts = FileMgr->getFileSystemOpts(); AST->FileMgr = FileMgr; AST->UserFilesAreVolatile = UserFilesAreVolatile; - + // Recover resources if we crash before exiting this method. llvm::CrashRecoveryContextCleanupRegistrar ASTUnitCleanup(AST.get()); @@ -1676,7 +1676,7 @@ PPOpts.RemappedFilesKeepOriginalName = RemappedFilesKeepOriginalName; PPOpts.AllowPCHWithCompilerErrors = AllowPCHWithCompilerErrors; PPOpts.SingleFileParseMode = SingleFileParse; - + // Override the resources path. CI->getHeaderSearchOpts().ResourceDir = ResourceFilesPath; @@ -1745,7 +1745,7 @@ } clearFileLevelDecls(); - + SimpleTimer ParsingTimer(WantTiming); ParsingTimer.setOutput("Reparsing " + getMainFileName()); @@ -1779,7 +1779,7 @@ bool Result = Parse(std::move(PCHContainerOps), std::move(OverrideMainBuffer), VFS); - // If we're caching global code-completion results, and the top-level + // If we're caching global code-completion results, and the top-level // declarations have changed, clear out the code-completion cache. if (!Result && ShouldCacheCodeCompletionResults && CurrentTopLevelHashValue != CompletionCacheTopLevelHashValue) @@ -1788,7 +1788,7 @@ // We now need to clear out the completion info related to this translation // unit; it'll be recreated if necessary. CCTUInfo.reset(); - + return Result; } @@ -1812,21 +1812,21 @@ namespace { /// \brief Code completion consumer that combines the cached code-completion /// results from an ASTUnit with the code-completion results provided to it, - /// then passes the result on to + /// then passes the result on to class AugmentedCodeCompleteConsumer : public CodeCompleteConsumer { uint64_t NormalContexts; ASTUnit &AST; CodeCompleteConsumer &Next; - + public: AugmentedCodeCompleteConsumer(ASTUnit &AST, CodeCompleteConsumer &Next, const CodeCompleteOptions &CodeCompleteOpts) : CodeCompleteConsumer(CodeCompleteOpts, Next.isOutputBinary()), AST(AST), Next(Next) - { + { // Compute the set of contexts in which we will look when we don't have // any information about the specific context. - NormalContexts + NormalContexts = (1LL << CodeCompletionContext::CCC_TopLevel) | (1LL << CodeCompletionContext::CCC_ObjCInterface) | (1LL << CodeCompletionContext::CCC_ObjCImplementation) @@ -1895,13 +1895,13 @@ case CodeCompletionContext::CCC_ParenthesizedExpression: case CodeCompletionContext::CCC_ObjCInterfaceName: break; - + case CodeCompletionContext::CCC_EnumTag: case CodeCompletionContext::CCC_UnionTag: case CodeCompletionContext::CCC_ClassOrStructTag: OnlyTagNames = true; break; - + case CodeCompletionContext::CCC_ObjCProtocolName: case CodeCompletionContext::CCC_MacroName: case CodeCompletionContext::CCC_MacroNameUse: @@ -1919,12 +1919,12 @@ // be hidden. return; } - + typedef CodeCompletionResult Result; for (unsigned I = 0; I != NumResults; ++I) { if (Results[I].Kind != Result::RK_Declaration) continue; - + unsigned IDNS = Results[I].Declaration->getUnderlyingDecl()->getIdentifierNamespace(); @@ -1932,17 +1932,17 @@ if (OnlyTagNames) Hiding = (IDNS & Decl::IDNS_Tag); else { - unsigned HiddenIDNS = (Decl::IDNS_Type | Decl::IDNS_Member | + unsigned HiddenIDNS = (Decl::IDNS_Type | Decl::IDNS_Member | Decl::IDNS_Namespace | Decl::IDNS_Ordinary | Decl::IDNS_NonMemberOperator); if (Ctx.getLangOpts().CPlusPlus) HiddenIDNS |= Decl::IDNS_Tag; Hiding = (IDNS & HiddenIDNS); } - + if (!Hiding) continue; - + DeclarationName Name = Results[I].Declaration->getDeclName(); if (IdentifierInfo *Identifier = Name.getAsIdentifierInfo()) HiddenNames.insert(Identifier->getName()); @@ -1954,7 +1954,7 @@ void AugmentedCodeCompleteConsumer::ProcessCodeCompleteResults(Sema &S, CodeCompletionContext Context, CodeCompletionResult *Results, - unsigned NumResults) { + unsigned NumResults) { // Merge the results we were given with the results we cached. bool AddedResult = false; uint64_t InContexts = @@ -1964,29 +1964,29 @@ llvm::StringSet HiddenNames; typedef CodeCompletionResult Result; SmallVector AllResults; - for (ASTUnit::cached_completion_iterator + for (ASTUnit::cached_completion_iterator C = AST.cached_completion_begin(), CEnd = AST.cached_completion_end(); C != CEnd; ++C) { - // If the context we are in matches any of the contexts we are + // If the context we are in matches any of the contexts we are // interested in, we'll add this result. if ((C->ShowInContexts & InContexts) == 0) continue; - + // If we haven't added any results previously, do so now. if (!AddedResult) { - CalculateHiddenNames(Context, Results, NumResults, S.Context, + CalculateHiddenNames(Context, Results, NumResults, S.Context, HiddenNames); AllResults.insert(AllResults.end(), Results, Results + NumResults); AddedResult = true; } - + // Determine whether this global completion result is hidden by a local // completion result. If so, skip it. if (C->Kind != CXCursor_MacroDefinition && HiddenNames.count(C->Completion->getTypedText())) continue; - + // Adjust priority based on similar type classes. unsigned Priority = C->Priority; CodeCompletionString *Completion = C->Completion; @@ -1994,7 +1994,7 @@ if (C->Kind == CXCursor_MacroDefinition) { Priority = getMacroUsagePriority(C->Completion->getTypedText(), S.getLangOpts(), - Context.getPreferredType()->isAnyPointerType()); + Context.getPreferredType()->isAnyPointerType()); } else if (C->Type) { CanQualType Expected = S.Context.getCanonicalType( @@ -2013,7 +2013,7 @@ } } } - + // Adjust the completion string, if required. if (C->Kind == CXCursor_MacroDefinition && Context.getKind() == CodeCompletionContext::CCC_MacroNameUse) { @@ -2025,18 +2025,18 @@ Priority = CCP_CodePattern; Completion = Builder.TakeString(); } - + AllResults.push_back(Result(Completion, Priority, C->Kind, C->Availability)); } - + // If we did not add any cached completion results, just forward the // results we were given to the next consumer. if (!AddedResult) { Next.ProcessCodeCompleteResults(S, Context, Results, NumResults); return; } - + Next.ProcessCodeCompleteResults(S, Context, AllResults.data(), AllResults.size()); } @@ -2093,11 +2093,11 @@ auto &Inv = *CCInvocation; Clang->setInvocation(std::move(CCInvocation)); OriginalSourceFile = Clang->getFrontendOpts().Inputs[0].getFile(); - + // Set up diagnostics, capturing any diagnostics produced. Clang->setDiagnostics(&Diag); - CaptureDroppedDiagnostics Capture(true, - Clang->getDiagnostics(), + CaptureDroppedDiagnostics Capture(true, + Clang->getDiagnostics(), &StoredDiagnostics, nullptr); ProcessWarningOptions(Diag, Inv.getDiagnosticOpts()); @@ -2108,13 +2108,13 @@ Clang->setInvocation(nullptr); return; } - + // Inform the target of the language options. // // FIXME: We shouldn't need to do this, the target should be immutable once // created. This complexity should be lifted elsewhere. Clang->getTarget().adjust(Clang->getLangOpts()); - + assert(Clang->getFrontendOpts().Inputs.size() == 1 && "Invocation must have exactly one source file!"); assert(Clang->getFrontendOpts().Inputs[0].getKind().getFormat() == @@ -2123,7 +2123,7 @@ assert(Clang->getFrontendOpts().Inputs[0].getKind().getLanguage() != InputKind::LLVM_IR && "IR inputs not support here!"); - + // Use the source and file managers that we were given. Clang->setFileManager(&FileMgr); Clang->setSourceManager(&SourceMgr); @@ -2210,7 +2210,7 @@ if (llvm::sys::fs::createUniqueFile(TempPath, fd, TempPath)) return true; - // FIXME: Can we somehow regenerate the stat cache here, or do we need to + // FIXME: Can we somehow regenerate the stat cache here, or do we need to // unconditionally create a stat cache when we parse the file? llvm::raw_fd_ostream Out(fd, /*shouldClose=*/true); @@ -2313,7 +2313,7 @@ FH.RemoveRange = CharSourceRange::getCharRange(BL, EL); } - Result.push_back(StoredDiagnostic(SD.Level, SD.ID, + Result.push_back(StoredDiagnostic(SD.Level, SD.ID, SD.Message, Loc, Ranges, FixIts)); } Result.swap(Out); @@ -2321,7 +2321,7 @@ void ASTUnit::addFileLevelDecl(Decl *D) { assert(D); - + // We only care about local declarations. if (D->isFromASTFile()) return; @@ -2398,7 +2398,7 @@ std::make_pair(Offset + Length, (Decl *)nullptr), llvm::less_first()); if (EndIt != LocDecls.end()) ++EndIt; - + for (LocDeclsTy::iterator DIt = BeginIt; DIt != EndIt; ++DIt) Decls.push_back(DIt->second); } @@ -2463,10 +2463,10 @@ FileID FID; if (SourceMgr) FID = SourceMgr->getPreambleFileID(); - + if (Loc.isInvalid() || FID.isInvalid()) return false; - + return SourceMgr->isInFileID(Loc, FID); } @@ -2474,10 +2474,10 @@ FileID FID; if (SourceMgr) FID = SourceMgr->getMainFileID(); - + if (Loc.isInvalid() || FID.isInvalid()) return false; - + return SourceMgr->isInFileID(Loc, FID); } @@ -2485,7 +2485,7 @@ FileID FID; if (SourceMgr) FID = SourceMgr->getPreambleFileID(); - + if (FID.isInvalid()) return SourceLocation(); @@ -2496,10 +2496,10 @@ FileID FID; if (SourceMgr) FID = SourceMgr->getMainFileID(); - + if (FID.isInvalid()) return SourceLocation(); - + return SourceMgr->getLocForStartOfFile(FID); } Index: clang/lib/Frontend/CacheTokens.cpp =================================================================== --- clang/lib/Frontend/CacheTokens.cpp +++ clang/lib/Frontend/CacheTokens.cpp @@ -21,8 +21,8 @@ #include "clang/Lex/Lexer.h" #include "clang/Lex/PTHManager.h" #include "clang/Lex/Preprocessor.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringMap.h" +#include "llvm/Support/DJB.h" #include "llvm/Support/EndianStream.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/MemoryBuffer.h" @@ -128,7 +128,7 @@ typedef unsigned offset_type; static hash_value_type ComputeHash(PTHEntryKeyVariant V) { - return llvm::HashString(V.getString()); + return llvm::djbHash(V.getString()); } static std::pair @@ -625,7 +625,7 @@ typedef unsigned offset_type; static hash_value_type ComputeHash(PTHIdKey* key) { - return llvm::HashString(key->II->getName()); + return llvm::djbHash(key->II->getName()); } static std::pair Index: clang/lib/Lex/PTHLexer.cpp =================================================================== --- clang/lib/Lex/PTHLexer.cpp +++ clang/lib/Lex/PTHLexer.cpp @@ -23,8 +23,8 @@ #include "clang/Lex/Preprocessor.h" #include "clang/Lex/Token.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Support/DJB.h" #include "llvm/Support/Endian.h" #include "llvm/Support/ErrorOr.h" #include "llvm/Support/FileSystem.h" @@ -145,7 +145,7 @@ ParsingPreprocessorDirective = false; // Done parsing the "line". return true; // Have a token. } - + assert(!LexingRawMode); // If we are in a #if directive, emit an error. @@ -336,7 +336,7 @@ using offset_type = unsigned; static hash_value_type ComputeHash(internal_key_type x) { - return llvm::HashString(x.second); + return llvm::djbHash(x.second); } static std::pair @@ -396,7 +396,7 @@ } static hash_value_type ComputeHash(const internal_key_type& a) { - return llvm::HashString(StringRef(a.first, a.second)); + return llvm::djbHash(StringRef(a.first, a.second)); } // This hopefully will just get inlined and removed by the optimizer. Index: clang/lib/Serialization/ASTCommon.cpp =================================================================== --- clang/lib/Serialization/ASTCommon.cpp +++ clang/lib/Serialization/ASTCommon.cpp @@ -16,7 +16,7 @@ #include "clang/AST/DeclObjC.h" #include "clang/Basic/IdentifierTable.h" #include "clang/Serialization/ASTDeserializationListener.h" -#include "llvm/ADT/StringExtras.h" +#include "llvm/Support/DJB.h" using namespace clang; @@ -171,7 +171,7 @@ unsigned R = 5381; for (unsigned I = 0; I != N; ++I) if (IdentifierInfo *II = Sel.getIdentifierInfoForSlot(I)) - R = llvm::HashString(II->getName(), R); + R = llvm::djbHash(II->getName(), R); return R; } @@ -231,7 +231,7 @@ default: llvm_unreachable("Unhandled DeclContext in AST reader"); } - + llvm_unreachable("Unhandled decl kind"); } Index: clang/lib/Serialization/ASTReader.cpp =================================================================== --- clang/lib/Serialization/ASTReader.cpp +++ clang/lib/Serialization/ASTReader.cpp @@ -106,6 +106,7 @@ #include "llvm/Support/Casting.h" #include "llvm/Support/Compression.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/DJB.h" #include "llvm/Support/Endian.h" #include "llvm/Support/Error.h" #include "llvm/Support/ErrorHandling.h" @@ -870,7 +871,7 @@ } unsigned ASTIdentifierLookupTraitBase::ComputeHash(const internal_key_type& a) { - return llvm::HashString(a); + return llvm::djbHash(a); } std::pair @@ -3226,7 +3227,7 @@ PP.getPreprocessingRecord()->SetExternalSource(*this); F.BasePreprocessedSkippedRangeID = PP.getPreprocessingRecord() ->allocateSkippedRanges(F.NumPreprocessedSkippedRanges); - + if (F.NumPreprocessedSkippedRanges > 0) GlobalSkippedRangeMap.insert( std::make_pair(F.BasePreprocessedSkippedRangeID, &F)); Index: clang/lib/Serialization/ASTWriter.cpp =================================================================== --- clang/lib/Serialization/ASTWriter.cpp +++ clang/lib/Serialization/ASTWriter.cpp @@ -82,13 +82,13 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringRef.h" #include "llvm/Bitcode/BitCodes.h" #include "llvm/Bitcode/BitstreamWriter.h" #include "llvm/Support/Casting.h" #include "llvm/Support/Compression.h" +#include "llvm/Support/DJB.h" #include "llvm/Support/Endian.h" #include "llvm/Support/EndianStream.h" #include "llvm/Support/Error.h" @@ -453,7 +453,7 @@ Code = TYPE_DEPENDENT_SIZED_EXT_VECTOR; } -void +void ASTTypeWriter::VisitDependentAddressSpaceType( const DependentAddressSpaceType *T) { Record.AddTypeRef(T->getPointeeType()); @@ -661,7 +661,7 @@ SourceRange range = TL.getAttrOperandParensRange(); Record.AddSourceLocation(range.getBegin()); Record.AddSourceLocation(range.getEnd()); - Record.AddStmt(TL.getAttrExprOperand()); + Record.AddStmt(TL.getAttrExprOperand()); } void TypeLocWriter::VisitDependentSizedExtVectorTypeLoc( @@ -1294,7 +1294,7 @@ RECORD(DECL_PRAGMA_COMMENT); RECORD(DECL_PRAGMA_DETECT_MISMATCH); RECORD(DECL_OMP_DECLARE_REDUCTION); - + // Statements and Exprs can occur in the Decls and Types block. AddStmtsExprs(Stream, Record); @@ -1445,7 +1445,7 @@ Stream.EnterSubblock(CONTROL_BLOCK_ID, 5); RecordData Record; - + // Metadata auto MetadataAbbrev = std::make_shared(); MetadataAbbrev->Add(BitCodeAbbrevOp(METADATA)); @@ -1912,11 +1912,11 @@ // Trait used for the on-disk hash table of header search information. class HeaderFileInfoTrait { ASTWriter &Writer; - + // Keep track of the framework names we've used during serialization. SmallVector FrameworkStringData; llvm::StringMap FrameworkNameOffset; - + public: HeaderFileInfoTrait(ASTWriter &Writer) : Writer(Writer) {} @@ -1929,7 +1929,7 @@ using UnresolvedModule = llvm::PointerIntPair; - + struct data_type { const HeaderFileInfo &HFI; ArrayRef KnownHeaders; @@ -1939,14 +1939,14 @@ using hash_value_type = unsigned; using offset_type = unsigned; - + hash_value_type ComputeHash(key_type_ref key) { // The hash is based only on size/time of the file, so that the reader can // match even when symlinking or excess path elements ("foo/../", "../") // change the form of the name. However, complete path is still the key. return llvm::hash_combine(key.Size, key.ModTime); } - + std::pair EmitKeyDataLength(raw_ostream& Out, key_type_ref key, data_type_ref Data) { using namespace llvm::support; @@ -1981,14 +1981,14 @@ endian::Writer LE(Out); uint64_t Start = Out.tell(); (void)Start; - + unsigned char Flags = (Data.HFI.isImport << 5) | (Data.HFI.isPragmaOnce << 4) | (Data.HFI.DirInfo << 1) | Data.HFI.IndexHeaderMapHeader; LE.write(Flags); LE.write(Data.HFI.NumIncludes); - + if (!Data.HFI.ControllingMacro) LE.write(Data.HFI.ControllingMacroID); else @@ -2001,10 +2001,10 @@ = FrameworkNameOffset.find(Data.HFI.Framework); if (Pos == FrameworkNameOffset.end()) { Offset = FrameworkStringData.size() + 1; - FrameworkStringData.append(Data.HFI.Framework.begin(), + FrameworkStringData.append(Data.HFI.Framework.begin(), Data.HFI.Framework.end()); FrameworkStringData.push_back(0); - + FrameworkNameOffset[Data.HFI.Framework] = Offset; } else Offset = Pos->second; @@ -2028,14 +2028,14 @@ assert(Out.tell() - Start == DataLen && "Wrong data length"); } - + const char *strings_begin() const { return FrameworkStringData.begin(); } const char *strings_end() const { return FrameworkStringData.end(); } }; } // namespace -/// \brief Write the header search block for the list of files that +/// \brief Write the header search block for the list of files that /// /// \param HS The header search structure to save. void ASTWriter::WriteHeaderSearch(const HeaderSearch &HS) { @@ -2101,7 +2101,7 @@ SmallVector FilesByUID; HS.getFileMgr().GetUniqueIDMapping(FilesByUID); - + if (FilesByUID.size() > HS.header_file_size()) FilesByUID.resize(HS.header_file_size()); @@ -2163,13 +2163,13 @@ Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32)); Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob)); unsigned TableAbbrev = Stream.EmitAbbrev(std::move(Abbrev)); - + // Write the header search table RecordData::value_type Record[] = {HEADER_SEARCH_TABLE, BucketOffset, NumHeaderSearchEntries, TableData.size()}; TableData.append(GeneratorTrait.strings_begin(),GeneratorTrait.strings_end()); Stream.EmitRecordWithBlob(TableAbbrev, Record, TableData); - + // Free all of the strings we had to duplicate. for (unsigned I = 0, N = SavedStrings.size(); I != N; ++I) free(const_cast(SavedStrings[I])); @@ -2269,7 +2269,7 @@ Record.push_back(InputFileIDs[Content->OrigEntry]); Record.push_back(File.NumCreatedFIDs); - + FileDeclIDsTy::iterator FDI = FileDeclIDs.find(FID); if (FDI != FileDeclIDs.end()) { Record.push_back(FDI->second->FirstDeclIndex); @@ -2278,9 +2278,9 @@ Record.push_back(0); Record.push_back(0); } - + Stream.EmitRecordWithAbbrev(SLocFileAbbrv, Record); - + if (Content->BufferOverridden || Content->IsTransient) EmitBlob = true; } else { @@ -2641,8 +2641,8 @@ // If the preprocessor has a preprocessing record, emit it. unsigned NumPreprocessingRecords = 0; using namespace llvm; - - // Set up the abbreviation for + + // Set up the abbreviation for unsigned InclusionAbbrev = 0; { auto Abbrev = std::make_shared(); @@ -2654,15 +2654,15 @@ Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob)); InclusionAbbrev = Stream.EmitAbbrev(std::move(Abbrev)); } - - unsigned FirstPreprocessorEntityID - = (Chain ? PPRec.getNumLoadedPreprocessedEntities() : 0) + + unsigned FirstPreprocessorEntityID + = (Chain ? PPRec.getNumLoadedPreprocessedEntities() : 0) + NUM_PREDEF_PP_ENTITY_IDS; unsigned NextPreprocessorEntityID = FirstPreprocessorEntityID; RecordData Record; for (PreprocessingRecord::iterator E = PPRec.local_begin(), EEnd = PPRec.local_end(); - E != EEnd; + E != EEnd; (void)++E, ++NumPreprocessingRecords, ++NextPreprocessorEntityID) { Record.clear(); @@ -2703,7 +2703,7 @@ Stream.EmitRecordWithBlob(InclusionAbbrev, Record, Buffer); continue; } - + llvm_unreachable("Unhandled PreprocessedEntity in ASTWriter"); } Stream.ExitBlock(); @@ -2783,14 +2783,14 @@ for (auto Sub = Mod->submodule_begin(), SubEnd = Mod->submodule_end(); Sub != SubEnd; ++Sub) ChildModules += getNumberOfModules(*Sub); - + return ChildModules + 1; } void ASTWriter::WriteSubmodules(Module *WritingModule) { // Enter the submodule description block. Stream.EnterSubblock(SUBMODULE_BLOCK_ID, /*bits for abbreviations*/5); - + // Write the abbreviations needed for the submodules block. using namespace llvm; @@ -2883,7 +2883,7 @@ getNumberOfModules(WritingModule), FirstSubmoduleID - NUM_PREDEF_SUBMODULE_IDS}; Stream.EmitRecord(SUBMODULE_METADATA, Record); - + // Write all of the submodules. std::queue Q; Q.push(WritingModule); @@ -2959,7 +2959,7 @@ Stream.EmitRecordWithBlob(TopHeaderAbbrev, Record, H->getName()); } - // Emit the imports. + // Emit the imports. if (!Mod->Imports.empty()) { RecordData Record; for (auto *I : Mod->Imports) @@ -2967,7 +2967,7 @@ Stream.EmitRecord(SUBMODULE_IMPORTS, Record); } - // Emit the exports. + // Emit the exports. if (!Mod->Exports.empty()) { RecordData Record; for (const auto &E : Mod->Exports) { @@ -3017,12 +3017,12 @@ RecordData::value_type Record[] = {SUBMODULE_EXPORT_AS}; Stream.EmitRecordWithBlob(ExportAsAbbrev, Record, Mod->ExportAsModule); } - + // Queue up the submodules of this module. for (auto *M : Mod->submodules()) Q.push(M); } - + Stream.ExitBlock(); assert((NextSubmoduleID - FirstSubmoduleID == @@ -3061,7 +3061,7 @@ unsigned &DiagStateID = DiagStateIDMap[State]; Record.push_back(DiagStateID); - + if (DiagStateID == 0) { DiagStateID = ++CurrID; @@ -3546,7 +3546,7 @@ bool IsModule; bool NeedDecls; ASTWriter::RecordData *InterestingIdentifierOffsets; - + /// \brief Determines whether this is an "interesting" identifier that needs a /// full IdentifierInfo structure written into the hash table. Notably, this /// doesn't check whether the name has macros defined; use PublicMacroIterator @@ -3582,7 +3582,7 @@ bool needDecls() const { return NeedDecls; } static hash_value_type ComputeHash(const IdentifierInfo* II) { - return llvm::HashString(II->getName()); + return llvm::djbHash(II->getName()); } bool isInterestingIdentifier(const IdentifierInfo *II) { @@ -3694,7 +3694,7 @@ /// The identifier table consists of a blob containing string data /// (the actual identifiers themselves) and a separate "offsets" index /// that maps identifier IDs to locations within the blob. -void ASTWriter::WriteIdentifierTable(Preprocessor &PP, +void ASTWriter::WriteIdentifierTable(Preprocessor &PP, IdentifierResolver &IdResolver, bool IsModule) { using namespace llvm; @@ -4298,16 +4298,16 @@ void ASTWriter::WriteObjCCategories() { SmallVector CategoriesMap; RecordData Categories; - + for (unsigned I = 0, N = ObjCClassesWithCategories.size(); I != N; ++I) { unsigned Size = 0; unsigned StartIndex = Categories.size(); - + ObjCInterfaceDecl *Class = ObjCClassesWithCategories[I]; - + // Allocate space for the size. Categories.push_back(0); - + // Add the categories. for (ObjCInterfaceDecl::known_categories_iterator Cat = Class->known_categories_begin(), @@ -4316,10 +4316,10 @@ assert(getDeclID(*Cat) != 0 && "Bogus category"); AddDeclRef(*Cat, Categories); } - + // Update the size. Categories[StartIndex] = Size; - + // Record this interface -> category map. ObjCCategoriesInfo CatInfo = { getDeclID(Class), StartIndex }; CategoriesMap.push_back(CatInfo); @@ -4579,7 +4579,7 @@ WritingAST = true; ASTHasCompilerErrors = hasErrors; - + // Emit the file header. Stream.Emit((unsigned)'C', 8); Stream.Emit((unsigned)'P', 8); @@ -4627,7 +4627,7 @@ // Make sure that the AST reader knows to finalize itself. if (Chain) Chain->finalizeForWriting(); - + ASTContext &Context = SemaRef.Context; Preprocessor &PP = SemaRef.PP; @@ -4668,7 +4668,7 @@ // headers. RecordData TentativeDefinitions; AddLazyVectorDecls(*this, SemaRef.TentativeDefinitions, TentativeDefinitions); - + // Build a record containing all of the file scoped decls in this file. RecordData UnusedFileScopedDecls; if (!isModule) @@ -4789,7 +4789,7 @@ NewGlobalKindDeclPairs.push_back(GetDeclRef(D)); } } - + auto Abv = std::make_shared(); Abv->Add(llvm::BitCodeAbbrevOp(TU_UPDATE_LEXICAL)); Abv->Add(llvm::BitCodeAbbrevOp(llvm::BitCodeAbbrevOp::Blob)); @@ -4811,7 +4811,7 @@ // If we have any extern "C" names, write out a visible update for them. if (Context.ExternCContext) WriteDeclContextVisibleUpdate(Context.ExternCContext); - + // If the translation unit has an anonymous namespace, and we don't already // have an update block for it, write it as an update block. // FIXME: Why do we not do this if there's already an update block? @@ -4900,7 +4900,7 @@ // declaration-id:i32 // c++-base-specifiers-id:i32 // type-id:i32) - // + // // module-kind is the ModuleKind enum value. If it is MK_PrebuiltModule or // MK_ExplicitModule, then the module-name is the module name. Otherwise, // it is the module file name. @@ -4994,7 +4994,7 @@ WriteOpenCLExtensionDecls(SemaRef); WriteCUDAPragmas(SemaRef); - // If we're emitting a module, write out the submodule information. + // If we're emitting a module, write out the submodule information. if (WritingModule) WriteSubmodules(WritingModule); @@ -5044,7 +5044,7 @@ // Write the record containing CUDA-specific declaration references. if (!CUDASpecialDeclRefs.empty()) Stream.EmitRecord(CUDA_SPECIAL_DECL_REFS, CUDASpecialDeclRefs); - + // Write the delegating constructors. if (!DelegatingCtorDecls.empty()) Stream.EmitRecord(DELEGATING_CTORS, DelegatingCtorDecls); @@ -5347,7 +5347,7 @@ MacroID ASTWriter::getMacroID(MacroInfo *MI) { if (!MI || MI->isBuiltinMacro()) return 0; - + assert(MacroIDs.find(MI) != MacroIDs.end() && "Macro not emitted!"); return MacroIDs[MI]; } @@ -5491,12 +5491,12 @@ if (!D) { return 0; } - + // If D comes from an AST file, its declaration ID is already known and // fixed. if (D->isFromASTFile()) return D->getGlobalID(); - + assert(!(reinterpret_cast(D) & 0x01) && "Invalid decl pointer"); DeclID &ID = DeclIDs[D]; if (ID == 0) { @@ -5818,7 +5818,7 @@ AddTemplateName(subst->getReplacement()); break; } - + case TemplateName::SubstTemplateTemplateParmPack: { SubstTemplateTemplateParmPackStorage *SubstPack = Name.getAsSubstTemplateTemplateParmPack(); @@ -5918,7 +5918,7 @@ Record->push_back(Base.getInheritConstructors()); AddTypeSourceInfo(Base.getTypeSourceInfo()); AddSourceRange(Base.getSourceRange()); - AddSourceLocation(Base.isPackExpansion()? Base.getEllipsisLoc() + AddSourceLocation(Base.isPackExpansion()? Base.getEllipsisLoc() : SourceLocation()); } @@ -6052,9 +6052,9 @@ AddUnresolvedSet(Data.Conversions.get(*Writer->Context)); AddUnresolvedSet(Data.VisibleConversions.get(*Writer->Context)); - // Data.Definition is the owning decl, no need to write it. + // Data.Definition is the owning decl, no need to write it. AddDeclRef(D->getFirstFriend()); - + // Add lambda-specific data. if (Data.IsLambda) { auto &Lambda = D->getLambdaData(); @@ -6347,7 +6347,7 @@ assert(!WritingAST && "Already writing the AST!"); if (!IFD->isFromASTFile()) return; // Declaration not imported from PCH. - + assert(IFD->getDefinition() && "Category on a class without a definition?"); ObjCClassesWithCategories.insert( const_cast(IFD->getDefinition())); Index: clang/lib/Serialization/GlobalModuleIndex.cpp =================================================================== --- clang/lib/Serialization/GlobalModuleIndex.cpp +++ clang/lib/Serialization/GlobalModuleIndex.cpp @@ -21,9 +21,9 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallString.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/Bitcode/BitstreamReader.h" #include "llvm/Bitcode/BitstreamWriter.h" +#include "llvm/Support/DJB.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/LockFileManager.h" #include "llvm/Support/MemoryBuffer.h" @@ -81,7 +81,7 @@ } static hash_value_type ComputeHash(const internal_key_type& a) { - return llvm::HashString(a); + return llvm::djbHash(a); } static std::pair @@ -289,7 +289,7 @@ bool GlobalModuleIndex::lookupIdentifier(StringRef Name, HitSet &Hits) { Hits.clear(); - + // If there's no identifier index, there is nothing we can do. if (!IdentifierIndex) return false; @@ -413,7 +413,7 @@ /// \brief A mapping from all interesting identifiers to the set of module /// files in which those identifiers are considered interesting. InterestingIdentifierMap InterestingIdentifiers; - + /// \brief Write the block-info block for the global module index file. void emitBlockInfoBlock(llvm::BitstreamWriter &Stream); @@ -608,7 +608,7 @@ // Skip the import location ++Idx; - // Load stored size/modification time. + // Load stored size/modification time. off_t StoredSize = (off_t)Record[Idx++]; time_t StoredModTime = (time_t)Record[Idx++]; @@ -697,7 +697,7 @@ typedef unsigned offset_type; static hash_value_type ComputeHash(key_type_ref Key) { - return llvm::HashString(Key); + return llvm::djbHash(Key); } std::pair @@ -710,7 +710,7 @@ LE.write(DataLen); return std::make_pair(KeyLen, DataLen); } - + void EmitKey(raw_ostream& Out, key_type_ref Key, unsigned KeyLen) { Out.write(Key.data(), KeyLen); } @@ -740,7 +740,7 @@ } using namespace llvm; - + // Emit the file header. Stream.Emit((unsigned)'B', 8); Stream.Emit((unsigned)'C', 8); @@ -789,7 +789,7 @@ I != IEnd; ++I) { Generator.insert(I->first(), I->second, Trait); } - + // Create the on-disk hash table in a buffer. SmallString<4096> IdentifierTable; uint32_t BucketOffset; @@ -902,7 +902,7 @@ // Rename the newly-written index file to the proper name. if (llvm::sys::fs::rename(IndexTmpPath, IndexPath)) { - // Rename failed; just remove the + // Rename failed; just remove the llvm::sys::fs::remove(IndexTmpPath); return EC_IOError; } Index: lld/include/lld/Core/SymbolTable.h =================================================================== --- lld/include/lld/Core/SymbolTable.h +++ lld/include/lld/Core/SymbolTable.h @@ -12,7 +12,7 @@ #include "lld/Common/LLVM.h" #include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/StringExtras.h" +#include "llvm/Support/DJB.h" #include #include #include @@ -65,7 +65,7 @@ static StringRef getEmptyKey() { return StringRef(); } static StringRef getTombstoneKey() { return StringRef(" ", 1); } static unsigned getHashValue(StringRef const val) { - return llvm::HashString(val); + return llvm::djbHash(val); } static bool isEqual(StringRef const lhs, StringRef const rhs) { return lhs.equals(rhs); Index: lldb/source/Utility/ConstString.cpp =================================================================== --- lldb/source/Utility/ConstString.cpp +++ lldb/source/Utility/ConstString.cpp @@ -11,10 +11,10 @@ #include "lldb/Utility/Stream.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/iterator.h" // for iterator_facade_base #include "llvm/Support/Allocator.h" // for BumpPtrAllocator +#include "llvm/Support/DJB.h" // for djbHash #include "llvm/Support/FormatProviders.h" // for format_provider #include "llvm/Support/RWMutex.h" #include "llvm/Support/Threading.h" @@ -171,7 +171,7 @@ protected: uint8_t hash(const llvm::StringRef &s) const { - uint32_t h = llvm::HashString(s); + uint32_t h = llvm::djbHash(s); return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff; } Index: llvm/include/llvm/ADT/StringExtras.h =================================================================== --- llvm/include/llvm/ADT/StringExtras.h +++ llvm/include/llvm/ADT/StringExtras.h @@ -232,19 +232,6 @@ SmallVectorImpl &OutFragments, StringRef Delimiters = " \t\n\v\f\r"); -/// HashString - Hash function for strings. -/// -/// This is the Bernstein hash function. -// -// FIXME: Investigate whether a modified bernstein hash function performs -// better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx -// X*33+c -> X*33^c -inline unsigned HashString(StringRef Str, unsigned Result = 0) { - for (StringRef::size_type i = 0, e = Str.size(); i != e; ++i) - Result = Result * 33 + (unsigned char)Str[i]; - return Result; -} - /// Returns the English suffix for an ordinal integer (-st, -nd, -rd, -th). inline StringRef getOrdinalSuffix(unsigned Val) { // It is critically important that we do this perfectly for Index: llvm/lib/Support/StringMap.cpp =================================================================== --- llvm/lib/Support/StringMap.cpp +++ llvm/lib/Support/StringMap.cpp @@ -14,6 +14,7 @@ #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/DJB.h" #include "llvm/Support/MathExtras.h" #include @@ -32,7 +33,7 @@ StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { ItemSize = itemSize; - + // If a size is specified, initialize the table with that many buckets. if (InitSize) { // The table will grow when the number of entries reach 3/4 of the number of @@ -41,7 +42,7 @@ init(getMinBucketToReserveForEntries(InitSize)); return; } - + // Otherwise, initialize it with zero buckets to avoid the allocation. TheTable = nullptr; NumBuckets = 0; @@ -56,7 +57,7 @@ unsigned NewNumBuckets = InitSize ? InitSize : 16; NumItems = 0; NumTombstones = 0; - + TheTable = static_cast( std::calloc(NewNumBuckets+1, sizeof(StringMapEntryBase **) + sizeof(unsigned))); @@ -82,7 +83,7 @@ init(16); HTSize = NumBuckets; } - unsigned FullHashValue = HashString(Name); + unsigned FullHashValue = djbHash(Name); unsigned BucketNo = FullHashValue & (HTSize-1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); @@ -98,11 +99,11 @@ HashTable[FirstTombstone] = FullHashValue; return FirstTombstone; } - + HashTable[BucketNo] = FullHashValue; return BucketNo; } - + if (BucketItem == getTombstoneVal()) { // Skip over tombstones. However, remember the first one we see. if (FirstTombstone == -1) FirstTombstone = BucketNo; @@ -111,7 +112,7 @@ // case here is that we are only looking at the buckets (for item info // being non-null and for the full hash value) not at the items. This // is important for cache locality. - + // Do the comparison like this because Name isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; @@ -120,10 +121,10 @@ return BucketNo; } } - + // Okay, we didn't find the item. Probe to the next bucket. BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); - + // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. ++ProbeAmt; @@ -136,7 +137,7 @@ int StringMapImpl::FindKey(StringRef Key) const { unsigned HTSize = NumBuckets; if (HTSize == 0) return -1; // Really empty table? - unsigned FullHashValue = HashString(Key); + unsigned FullHashValue = djbHash(Key); unsigned BucketNo = FullHashValue & (HTSize-1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); @@ -146,7 +147,7 @@ // If we found an empty bucket, this key isn't in the table yet, return. if (LLVM_LIKELY(!BucketItem)) return -1; - + if (BucketItem == getTombstoneVal()) { // Ignore tombstones. } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { @@ -154,7 +155,7 @@ // case here is that we are only looking at the buckets (for item info // being non-null and for the full hash value) not at the items. This // is important for cache locality. - + // Do the comparison like this because NameStart isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; @@ -163,10 +164,10 @@ return BucketNo; } } - + // Okay, we didn't find the item. Probe to the next bucket. BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); - + // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. ++ProbeAmt; @@ -187,7 +188,7 @@ StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { int Bucket = FindKey(Key); if (Bucket == -1) return nullptr; - + StringMapEntryBase *Result = TheTable[Bucket]; TheTable[Bucket] = getTombstoneVal(); --NumItems; @@ -241,13 +242,13 @@ NewBucketNo = NewBucket; continue; } - + // Otherwise probe for a spot. unsigned ProbeSize = 1; do { NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); } while (NewTableArray[NewBucket]); - + // Finally found a slot. Fill it in. NewTableArray[NewBucket] = Bucket; NewHashArray[NewBucket] = FullHash; @@ -255,9 +256,9 @@ NewBucketNo = NewBucket; } } - + free(TheTable); - + TheTable = NewTableArray; NumBuckets = NewSize; NumTombstones = 0;