[ADT] Move CachedHashString to its own header in ADT, and rename to CachedHashStringRef.

[jlebar]

Summary

Reclaiming the name 'CachedHashString' will let us add a type with that
name that owns its value.

[jlebar]

Remove check of hash values in equality function, per Rafael's comment.

[jlebar]

This has Rafael's LG on the mailing list.

lld/trunk/ELF/InputSection.cpp

template <class ELFT> void  MergeInputSection<ELFT>::finalizePieces() {
   for (SectionPiece &Piece : this->Pieces) {
     if (!Piece.Live)
       continue;
     if (Piece.OutputOff == size_t(-1)) {
       // Offsets of tail-merged strings are computed lazily.
       auto *OutSec = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
       ArrayRef<uint8_t> D = this->getData(Piece);
       StringRef S((const char *)D.data(), D.size());
-      CachedHashString V(S, Piece.Hash);
+      CachedHashStringRef V(S, Piece.Hash);
       Piece.OutputOff = OutSec->getOffset(V);
     }
     OffsetMap[Piece.InputOff] = Piece.OutputOff;
   }
 }
 
 template <class ELFT>
 MipsReginfoInputSection<ELFT>::MipsReginfoInputSection(elf::ObjectFile<ELFT> *F,

lld/trunk/ELF/OutputSections.h

class MergeOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::uint uintX_t;
   typedef OutputSectionBase<ELFT> Base;
 
 public:
   MergeOutputSection(StringRef Name, uint32_t Type, uintX_t Flags,
                      uintX_t Alignment);
   void addSection(InputSectionBase<ELFT> *S) override;
   void writeTo(uint8_t *Buf) override;
-  unsigned getOffset(llvm::CachedHashString Val);
+  unsigned getOffset(llvm::CachedHashStringRef Val);
   void finalize() override;
   void finalizePieces() override;
   bool shouldTailMerge() const;
   typename Base::Kind getKind() const override { return Base::Merge; }
   static bool classof(const Base *B) { return B->getKind() == Base::Merge; }
 
 private:
   llvm::StringTableBuilder Builder;

lld/trunk/ELF/OutputSections.cpp

void MergeOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   this->updateAlignment(Sec->Alignment);
   this->Header.sh_entsize = Sec->getSectionHdr()->sh_entsize;
   Sections.push_back(Sec);
 
   for (SectionPiece &Piece : Sec->Pieces) {
     if (!Piece.Live)
       continue;
     StringRef Data = toStringRef(Sec->getData(Piece));
-    CachedHashString V(Data, Piece.Hash);
+    CachedHashStringRef V(Data, Piece.Hash);
     uintX_t OutputOffset = Builder.add(V);
     if (!shouldTailMerge())
       Piece.OutputOff = OutputOffset;
   }
 }
 
 template <class ELFT>
-unsigned MergeOutputSection<ELFT>::getOffset(CachedHashString Val) {
+unsigned MergeOutputSection<ELFT>::getOffset(CachedHashStringRef Val) {
   return Builder.getOffset(Val);
 }
 
 template <class ELFT> bool MergeOutputSection<ELFT>::shouldTailMerge() const {
   return Config->Optimize >= 2 && this->Header.sh_flags & SHF_STRINGS;
 }
 
 template <class ELFT> void MergeOutputSection<ELFT>::finalize() {

llvm/trunk/include/llvm/ADT/CachedHashString.h

+//===- llvm/ADT/CachedHashString.h - Prehashed string/StringRef -*- 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 CachedHashString and CachedHashStringRef.  These are like
+// std::string and StringRef, except they store their hash in addition to their
+// string data.
+//
+// Unlike std::string, CachedHashString can be used in DenseSet/DenseMap
+// (because, unlike std::string, CachedHashString lets us have empty and
+// tombstone values).
+//
+// TODO: Add CachedHashString.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_CACHED_HASH_STRING_H
+#define LLVM_ADT_CACHED_HASH_STRING_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace llvm {
+
+/// A container which contains a StringRef plus a precomputed hash.
+class CachedHashStringRef {
+  const char *P;
+  uint32_t Size;
+  uint32_t Hash;
+
+public:
+  // Explicit because hashing a string isn't free.
+  explicit CachedHashStringRef(StringRef S)
+      : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
+
+  CachedHashStringRef(StringRef S, uint32_t Hash)
+      : P(S.data()), Size(S.size()), Hash(Hash) {
+    assert(S.size() <= std::numeric_limits<uint32_t>::max());
+  }
+
+  StringRef val() const { return StringRef(P, Size); }
+  uint32_t size() const { return Size; }
+  uint32_t hash() const { return Hash; }
+};
+
+template <> struct DenseMapInfo<CachedHashStringRef> {
+  static CachedHashStringRef getEmptyKey() {
+    return CachedHashStringRef(DenseMapInfo<StringRef>::getEmptyKey(), 0);
+  }
+  static CachedHashStringRef getTombstoneKey() {
+    return CachedHashStringRef(DenseMapInfo<StringRef>::getTombstoneKey(), 1);
+  }
+  static unsigned getHashValue(const CachedHashStringRef &S) {
+    assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
+    assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
+    return S.hash();
+  }
+  static bool isEqual(const CachedHashStringRef &LHS,
+                      const CachedHashStringRef &RHS) {
+    return DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val());
+  }
+};
+
+} // namespace llvm
+
+#endif

llvm/trunk/include/llvm/MC/StringTableBuilder.h

 //===-- StringTableBuilder.h - String table building utility ------*- C++ -*-=//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MC_STRINGTABLEBUILDER_H
 #define LLVM_MC_STRINGTABLEBUILDER_H
 
-#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseMap.h"
 #include <cassert>
 
 namespace llvm {
 class raw_ostream;
 
-class CachedHashString {
-  const char *P;
-  uint32_t Size;
-  uint32_t Hash;
-
-public:
-  CachedHashString(StringRef S)
-      : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
-  CachedHashString(StringRef S, uint32_t Hash)
-      : P(S.data()), Size(S.size()), Hash(Hash) {
-    assert(S.size() <= std::numeric_limits<uint32_t>::max());
-  }
-
-  StringRef val() const { return StringRef(P, Size); }
-  uint32_t size() const { return Size; }
-  uint32_t hash() const { return Hash; }
-};
-
 /// \brief Utility for building string tables with deduplicated suffixes.
 class StringTableBuilder {
 public:
   enum Kind { ELF, WinCOFF, MachO, RAW };
 
 private:
-  DenseMap<CachedHashString, size_t> StringIndexMap;
+  DenseMap<CachedHashStringRef, size_t> StringIndexMap;
   size_t Size = 0;
   Kind K;
   unsigned Alignment;
   bool Finalized = false;
 
   void finalizeStringTable(bool Optimize);
   void initSize();
 
 public:
   StringTableBuilder(Kind K, unsigned Alignment = 1);
   ~StringTableBuilder();
 
   /// \brief Add a string to the builder. Returns the position of S in the
   /// table. The position will be changed if finalize is used.
   /// Can only be used before the table is finalized.
-  size_t add(CachedHashString S);
-  size_t add(StringRef S) { return add(CachedHashString(S)); }
+  size_t add(CachedHashStringRef S);
+  size_t add(StringRef S) { return add(CachedHashStringRef(S)); }
 
   /// \brief Analyze the strings and build the final table. No more strings can
   /// be added after this point.
   void finalize();
 
   /// Finalize the string table without reording it. In this mode, offsets
   /// returned by add will still be valid.
   void finalizeInOrder();
 
   /// \brief Get the offest of a string in the string table. Can only be used
   /// after the table is finalized.
-  size_t getOffset(CachedHashString S) const;
-  size_t getOffset(StringRef S) const { return getOffset(CachedHashString(S)); }
+  size_t getOffset(CachedHashStringRef S) const;
+  size_t getOffset(StringRef S) const {
+    return getOffset(CachedHashStringRef(S));
+  }
 
   size_t getSize() const { return Size; }
   void clear();
 
   void write(raw_ostream &OS) const;
   void write(uint8_t *Buf) const;
 
 private:
   bool isFinalized() const { return Finalized; }
 };
 
 } // end llvm namespace
 
 #endif

llvm/trunk/lib/MC/StringTableBuilder.cpp

 //===-- StringTableBuilder.cpp - String table building utility ------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
 #include "llvm/Support/COFF.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <vector>
 
 using namespace llvm;
 
-namespace llvm {
-template <> struct DenseMapInfo<CachedHashString> {
-  static CachedHashString getEmptyKey() {
-    StringRef S = DenseMapInfo<StringRef>::getEmptyKey();
-    return {S, 0};
-  }
-  static CachedHashString getTombstoneKey() {
-    StringRef S = DenseMapInfo<StringRef>::getTombstoneKey();
-    return {S, 0};
-  }
-  static unsigned getHashValue(CachedHashString Val) {
-    assert(!isEqual(Val, getEmptyKey()) && "Cannot hash the empty key!");
-    assert(!isEqual(Val, getTombstoneKey()) &&
-           "Cannot hash the tombstone key!");
-    return Val.hash();
-  }
-  static bool isEqual(CachedHashString A, CachedHashString B) {
-    return DenseMapInfo<StringRef>::isEqual(A.val(), B.val());
-  }
-};
-}
-
 StringTableBuilder::~StringTableBuilder() {}
 
 void StringTableBuilder::initSize() {
   // Account for leading bytes in table so that offsets returned from add are
   // correct.
   switch (K) {
   case RAW:
     Size = 0;

 void StringTableBuilder::write(raw_ostream &OS) const {
   assert(isFinalized());
   SmallString<0> Data;
   Data.resize(getSize());
   write((uint8_t *)&Data[0]);
   OS << Data;
 }
 
-typedef std::pair<CachedHashString, size_t> StringPair;
+typedef std::pair<CachedHashStringRef, size_t> StringPair;
 
 void StringTableBuilder::write(uint8_t *Buf) const {
   assert(isFinalized());
   for (const StringPair &P : StringIndexMap) {
     StringRef Data = P.first.val();
     if (!Data.empty())
       memcpy(Buf + P.second, Data.data(), Data.size());
   }
if (K == MachO)
     Size = alignTo(Size, 4); // Pad to multiple of 4.
 }
 
 void StringTableBuilder::clear() {
   Finalized = false;
   StringIndexMap.clear();
 }
 
-size_t StringTableBuilder::getOffset(CachedHashString S) const {
+size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {
   assert(isFinalized());
   auto I = StringIndexMap.find(S);
   assert(I != StringIndexMap.end() && "String is not in table!");
   return I->second;
 }
 
-size_t StringTableBuilder::add(CachedHashString S) {
+size_t StringTableBuilder::add(CachedHashStringRef S) {
   if (K == WinCOFF)
     assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
 
   assert(!isFinalized());
   auto P = StringIndexMap.insert(std::make_pair(S, 0));
   if (P.second) {
     size_t Start = alignTo(Size, Alignment);
     P.first->second = Start;
     Size = Start + S.size() + (K != RAW);
   }
   return P.first->second;
 }

llvm/trunk/unittests/MC/StringTableBuilderTest.cpp

 //===----------- StringTableBuilderTest.cpp -------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/SmallString.h"
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Support/Endian.h"
 #include "gtest/gtest.h"
 #include <string>
 
 using namespace llvm;
 
 namespace {