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/DenseMap.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/Support/raw_ostream.h"
25
26namespace llvm {
27
28/// A container which contains a StringRef plus a precomputed hash.
29class CachedHashStringRef {
30  const char *P;
31  uint32_t Size;
32  uint32_t Hash;
33
34public:
35  // Explicit because hashing a string isn't free.
36  explicit CachedHashStringRef(StringRef S)
37      : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
38
39  CachedHashStringRef(StringRef S, uint32_t Hash)
40      : P(S.data()), Size(S.size()), Hash(Hash) {
41    assert(S.size() <= std::numeric_limits<uint32_t>::max());
42  }
43
44  StringRef val() const { return StringRef(P, Size); }
45  const char *data() const { return P; }
46  uint32_t size() const { return Size; }
47  uint32_t hash() const { return Hash; }
48};
49
50template <> struct DenseMapInfo<CachedHashStringRef> {
51  static CachedHashStringRef getEmptyKey() {
52    return CachedHashStringRef(DenseMapInfo<StringRef>::getEmptyKey(), 0);
53  }
54  static CachedHashStringRef getTombstoneKey() {
55    return CachedHashStringRef(DenseMapInfo<StringRef>::getTombstoneKey(), 1);
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() &&
65           DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val());
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.
72class CachedHashString {
73  friend struct DenseMapInfo<CachedHashString>;
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() {
81    return DenseMapInfo<char *>::getTombstoneKey();
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
97public:
98  explicit CachedHashString(const char *S) : CachedHashString(StringRef(S)) {}
99
100  // Explicit because copying and hashing a string isn't free.
101  explicit CachedHashString(StringRef S)
102      : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
103
104  CachedHashString(StringRef S, uint32_t Hash)
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.
111  CachedHashString(const CachedHashString &Other)
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
121  CachedHashString &operator=(CachedHashString Other) {
122    swap(*this, Other);
123    return *this;
124  }
125
126  CachedHashString(CachedHashString &&Other) noexcept
127      : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
128    Other.P = getEmptyKeyPtr();
129  }
130
131  ~CachedHashString() {
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
153template <> struct DenseMapInfo<CachedHashString> {
154  static CachedHashString getEmptyKey() {
155    return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
156                            CachedHashString::getEmptyKeyPtr());
157  }
158  static CachedHashString getTombstoneKey() {
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
185