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