LLVM  12.0.0git
CachedHashString.h
Go to the documentation of this file.
1 //===- llvm/ADT/CachedHashString.h - Prehashed string/StringRef -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines CachedHashString and CachedHashStringRef. These are owning
10 // and not-owning string types that store their hash in addition to their string
11 // data.
12 //
13 // Unlike std::string, CachedHashString can be used in DenseSet/DenseMap
14 // (because, unlike std::string, CachedHashString lets us have empty and
15 // tombstone values).
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #ifndef LLVM_ADT_CACHED_HASH_STRING_H
20 #define LLVM_ADT_CACHED_HASH_STRING_H
21 
22 #include "llvm/ADT/DenseMapInfo.h"
23 #include "llvm/ADT/StringRef.h"
24 
25 namespace llvm {
26 
27 /// A container which contains a StringRef plus a precomputed hash.
29  const char *P;
30  uint32_t Size;
31  uint32_t Hash;
32 
33 public:
34  // Explicit because hashing a string isn't free.
36  : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
37 
39  : P(S.data()), Size(S.size()), Hash(Hash) {
41  }
42 
43  StringRef val() const { return StringRef(P, Size); }
44  const char *data() const { return P; }
45  uint32_t size() const { return Size; }
46  uint32_t hash() const { return Hash; }
47 };
48 
49 template <> struct DenseMapInfo<CachedHashStringRef> {
52  }
55  }
56  static unsigned getHashValue(const CachedHashStringRef &S) {
57  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
58  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
59  return S.hash();
60  }
61  static bool isEqual(const CachedHashStringRef &LHS,
62  const CachedHashStringRef &RHS) {
63  return LHS.hash() == RHS.hash() &&
65  }
66 };
67 
68 /// A container which contains a string, which it owns, plus a precomputed hash.
69 ///
70 /// We do not null-terminate the string.
73 
74  char *P;
75  uint32_t Size;
76  uint32_t Hash;
77 
78  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
79  static char *getTombstoneKeyPtr() {
81  }
82 
83  bool isEmptyOrTombstone() const {
84  return P == getEmptyKeyPtr() || P == getTombstoneKeyPtr();
85  }
86 
87  struct ConstructEmptyOrTombstoneTy {};
88 
89  CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
90  : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
91  assert(isEmptyOrTombstone());
92  }
93 
94  // TODO: Use small-string optimization to avoid allocating.
95 
96 public:
97  explicit CachedHashString(const char *S) : CachedHashString(StringRef(S)) {}
98 
99  // Explicit because copying and hashing a string isn't free.
101  : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
102 
104  : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
105  memcpy(P, S.data(), S.size());
106  }
107 
108  // Ideally this class would not be copyable. But SetVector requires copyable
109  // keys, and we want this to be usable there.
111  : Size(Other.Size), Hash(Other.Hash) {
112  if (Other.isEmptyOrTombstone()) {
113  P = Other.P;
114  } else {
115  P = new char[Size];
116  memcpy(P, Other.P, Size);
117  }
118  }
119 
121  swap(*this, Other);
122  return *this;
123  }
124 
126  : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
127  Other.P = getEmptyKeyPtr();
128  }
129 
131  if (!isEmptyOrTombstone())
132  delete[] P;
133  }
134 
135  StringRef val() const { return StringRef(P, Size); }
136  uint32_t size() const { return Size; }
137  uint32_t hash() const { return Hash; }
138 
139  operator StringRef() const { return val(); }
140  operator CachedHashStringRef() const {
141  return CachedHashStringRef(val(), Hash);
142  }
143 
144  friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
145  using std::swap;
146  swap(LHS.P, RHS.P);
147  swap(LHS.Size, RHS.Size);
148  swap(LHS.Hash, RHS.Hash);
149  }
150 };
151 
152 template <> struct DenseMapInfo<CachedHashString> {
154  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
155  CachedHashString::getEmptyKeyPtr());
156  }
158  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
159  CachedHashString::getTombstoneKeyPtr());
160  }
161  static unsigned getHashValue(const CachedHashString &S) {
162  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
163  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
164  return S.hash();
165  }
166  static bool isEqual(const CachedHashString &LHS,
167  const CachedHashString &RHS) {
168  if (LHS.hash() != RHS.hash())
169  return false;
170  if (LHS.P == CachedHashString::getEmptyKeyPtr())
171  return RHS.P == CachedHashString::getEmptyKeyPtr();
172  if (LHS.P == CachedHashString::getTombstoneKeyPtr())
173  return RHS.P == CachedHashString::getTombstoneKeyPtr();
174 
175  // This is safe because if RHS.P is the empty or tombstone key, it will have
176  // length 0, so we'll never dereference its pointer.
177  return LHS.val() == RHS.val();
178  }
179 };
180 
181 } // namespace llvm
182 
183 #endif
A container which contains a StringRef plus a precomputed hash.
CachedHashString(const CachedHashString &Other)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool isEqual(const CachedHashStringRef &LHS, const CachedHashStringRef &RHS)
static bool isEqual(const CachedHashString &LHS, const CachedHashString &RHS)
CachedHashStringRef(StringRef S, uint32_t Hash)
CachedHashString(StringRef S, uint32_t Hash)
CachedHashString & operator=(CachedHashString Other)
static CachedHashString getTombstoneKey()
static bool isEqual(const Function &Caller, const Function &Callee)
LLVM_NODISCARD size_t size() const
size - Get the string size.
Definition: StringRef.h:160
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)
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
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:962
uint32_t Size
Definition: Profile.cpp:46
LLVM_NODISCARD const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:152
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A container which contains a string, which it owns, plus a precomputed hash.
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
static CachedHashStringRef getEmptyKey()
CachedHashString(const char *S)
friend void swap(CachedHashString &LHS, CachedHashString &RHS)