LLVM  6.0.0svn
CachedHashString.h
Go to the documentation of this file.
1 //===- llvm/ADT/CachedHashString.h - Prehashed string/StringRef -*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines CachedHashString and CachedHashStringRef. These are owning
11 // and not-owning string types that store their hash in addition to their string
12 // data.
13 //
14 // Unlike std::string, CachedHashString can be used in DenseSet/DenseMap
15 // (because, unlike std::string, CachedHashString lets us have empty and
16 // tombstone values).
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_ADT_CACHED_HASH_STRING_H
21 #define LLVM_ADT_CACHED_HASH_STRING_H
22 
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/StringRef.h"
26 
27 namespace llvm {
28 
29 /// A container which contains a StringRef plus a precomputed hash.
31  const char *P;
32  uint32_t Size;
33  uint32_t Hash;
34 
35 public:
36  // Explicit because hashing a string isn't free.
38  : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
39 
41  : P(S.data()), Size(S.size()), Hash(Hash) {
43  }
44 
45  StringRef val() const { return StringRef(P, Size); }
46  uint32_t size() const { return Size; }
47  uint32_t hash() const { return Hash; }
48 };
49 
50 template <> struct DenseMapInfo<CachedHashStringRef> {
53  }
56  }
57  static unsigned getHashValue(const CachedHashStringRef &S) {
58  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
59  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
60  return S.hash();
61  }
62  static bool isEqual(const CachedHashStringRef &LHS,
63  const CachedHashStringRef &RHS) {
64  return LHS.hash() == RHS.hash() &&
66  }
67 };
68 
69 /// A container which contains a string, which it owns, plus a precomputed hash.
70 ///
71 /// We do not null-terminate the string.
74 
75  char *P;
76  uint32_t Size;
77  uint32_t Hash;
78 
79  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
80  static char *getTombstoneKeyPtr() {
82  }
83 
84  bool isEmptyOrTombstone() const {
85  return P == getEmptyKeyPtr() || P == getTombstoneKeyPtr();
86  }
87 
88  struct ConstructEmptyOrTombstoneTy {};
89 
90  CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
91  : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
92  assert(isEmptyOrTombstone());
93  }
94 
95  // TODO: Use small-string optimization to avoid allocating.
96 
97 public:
98  explicit CachedHashString(const char *S) : CachedHashString(StringRef(S)) {}
99 
100  // Explicit because copying and hashing a string isn't free.
102  : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
103 
105  : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
106  memcpy(P, S.data(), S.size());
107  }
108 
109  // Ideally this class would not be copyable. But SetVector requires copyable
110  // keys, and we want this to be usable there.
112  : Size(Other.Size), Hash(Other.Hash) {
113  if (Other.isEmptyOrTombstone()) {
114  P = Other.P;
115  } else {
116  P = new char[Size];
117  memcpy(P, Other.P, Size);
118  }
119  }
120 
122  swap(*this, Other);
123  return *this;
124  }
125 
127  : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
128  Other.P = getEmptyKeyPtr();
129  }
130 
132  if (!isEmptyOrTombstone())
133  delete[] P;
134  }
135 
136  StringRef val() const { return StringRef(P, Size); }
137  uint32_t size() const { return Size; }
138  uint32_t hash() const { return Hash; }
139 
140  operator StringRef() const { return val(); }
141  operator CachedHashStringRef() const {
142  return CachedHashStringRef(val(), Hash);
143  }
144 
145  friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
146  using std::swap;
147  swap(LHS.P, RHS.P);
148  swap(LHS.Size, RHS.Size);
149  swap(LHS.Hash, RHS.Hash);
150  }
151 };
152 
153 template <> struct DenseMapInfo<CachedHashString> {
155  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
156  CachedHashString::getEmptyKeyPtr());
157  }
159  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
160  CachedHashString::getTombstoneKeyPtr());
161  }
162  static unsigned getHashValue(const CachedHashString &S) {
163  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
164  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
165  return S.hash();
166  }
167  static bool isEqual(const CachedHashString &LHS,
168  const CachedHashString &RHS) {
169  if (LHS.hash() != RHS.hash())
170  return false;
171  if (LHS.P == CachedHashString::getEmptyKeyPtr())
172  return RHS.P == CachedHashString::getEmptyKeyPtr();
173  if (LHS.P == CachedHashString::getTombstoneKeyPtr())
174  return RHS.P == CachedHashString::getTombstoneKeyPtr();
175 
176  // This is safe because if RHS.P is the empty or tombstone key, it will have
177  // length 0, so we'll never dereference its pointer.
178  return LHS.val() == RHS.val();
179  }
180 };
181 
182 } // namespace llvm
183 
184 #endif
A container which contains a StringRef plus a precomputed hash.
CachedHashString(const CachedHashString &Other)
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const
size - Get the string size.
Definition: StringRef.h:138
static bool isEqual(const CachedHashStringRef &LHS, const CachedHashStringRef &RHS)
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:128
static bool isEqual(const CachedHashString &LHS, const CachedHashString &RHS)
CachedHashStringRef(StringRef S, uint32_t Hash)
CachedHashString(StringRef S, uint32_t Hash)
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:736
CachedHashString & operator=(CachedHashString Other)
static CachedHashString getTombstoneKey()
static bool isEqual(const Function &Caller, const Function &Callee)
static CachedHashStringRef getTombstoneKey()
StringRef val() const
#define P(N)
CachedHashString(CachedHashString &&Other) noexcept
static CachedHashString getEmptyKey()
static unsigned getHashValue(const CachedHashStringRef &S)
static unsigned getHashValue(const CachedHashString &S)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A container which contains a string, which it owns, plus a precomputed hash.
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
static CachedHashStringRef getEmptyKey()
CachedHashString(const char *S)
friend void swap(CachedHashString &LHS, CachedHashString &RHS)