LLVM  7.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  const char *data() const { return P; }
47  uint32_t size() const { return Size; }
48  uint32_t hash() const { return Hash; }
49 };
50 
51 template <> struct DenseMapInfo<CachedHashStringRef> {
54  }
57  }
58  static unsigned getHashValue(const CachedHashStringRef &S) {
59  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
60  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
61  return S.hash();
62  }
63  static bool isEqual(const CachedHashStringRef &LHS,
64  const CachedHashStringRef &RHS) {
65  return LHS.hash() == RHS.hash() &&
67  }
68 };
69 
70 /// A container which contains a string, which it owns, plus a precomputed hash.
71 ///
72 /// We do not null-terminate the string.
75 
76  char *P;
77  uint32_t Size;
78  uint32_t Hash;
79 
80  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
81  static char *getTombstoneKeyPtr() {
83  }
84 
85  bool isEmptyOrTombstone() const {
86  return P == getEmptyKeyPtr() || P == getTombstoneKeyPtr();
87  }
88 
89  struct ConstructEmptyOrTombstoneTy {};
90 
91  CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
92  : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
93  assert(isEmptyOrTombstone());
94  }
95 
96  // TODO: Use small-string optimization to avoid allocating.
97 
98 public:
99  explicit CachedHashString(const char *S) : CachedHashString(StringRef(S)) {}
100 
101  // Explicit because copying and hashing a string isn't free.
103  : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
104 
106  : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
107  memcpy(P, S.data(), S.size());
108  }
109 
110  // Ideally this class would not be copyable. But SetVector requires copyable
111  // keys, and we want this to be usable there.
113  : Size(Other.Size), Hash(Other.Hash) {
114  if (Other.isEmptyOrTombstone()) {
115  P = Other.P;
116  } else {
117  P = new char[Size];
118  memcpy(P, Other.P, Size);
119  }
120  }
121 
123  swap(*this, Other);
124  return *this;
125  }
126 
128  : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
129  Other.P = getEmptyKeyPtr();
130  }
131 
133  if (!isEmptyOrTombstone())
134  delete[] P;
135  }
136 
137  StringRef val() const { return StringRef(P, Size); }
138  uint32_t size() const { return Size; }
139  uint32_t hash() const { return Hash; }
140 
141  operator StringRef() const { return val(); }
142  operator CachedHashStringRef() const {
143  return CachedHashStringRef(val(), Hash);
144  }
145 
146  friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
147  using std::swap;
148  swap(LHS.P, RHS.P);
149  swap(LHS.Size, RHS.Size);
150  swap(LHS.Hash, RHS.Hash);
151  }
152 };
153 
154 template <> struct DenseMapInfo<CachedHashString> {
156  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
157  CachedHashString::getEmptyKeyPtr());
158  }
160  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
161  CachedHashString::getTombstoneKeyPtr());
162  }
163  static unsigned getHashValue(const CachedHashString &S) {
164  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
165  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
166  return S.hash();
167  }
168  static bool isEqual(const CachedHashString &LHS,
169  const CachedHashString &RHS) {
170  if (LHS.hash() != RHS.hash())
171  return false;
172  if (LHS.P == CachedHashString::getEmptyKeyPtr())
173  return RHS.P == CachedHashString::getEmptyKeyPtr();
174  if (LHS.P == CachedHashString::getTombstoneKeyPtr())
175  return RHS.P == CachedHashString::getTombstoneKeyPtr();
176 
177  // This is safe because if RHS.P is the empty or tombstone key, it will have
178  // length 0, so we'll never dereference its pointer.
179  return LHS.val() == RHS.val();
180  }
181 };
182 
183 } // namespace llvm
184 
185 #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:773
CachedHashString & operator=(CachedHashString Other)
static CachedHashString getTombstoneKey()
static bool isEqual(const Function &Caller, const Function &Callee)
static CachedHashStringRef getTombstoneKey()
const char * data() const
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:924
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)