Coverage Report

Created: 2018-12-11 17:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ADT/CachedHashString.h
Line
Count
Source (jump to first uncovered line)
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"
25
#include "llvm/Support/raw_ostream.h"
26
27
namespace llvm {
28
29
/// A container which contains a StringRef plus a precomputed hash.
30
class CachedHashStringRef {
31
  const char *P;
32
  uint32_t Size;
33
  uint32_t Hash;
34
35
public:
36
  // Explicit because hashing a string isn't free.
37
  explicit CachedHashStringRef(StringRef S)
38
4.93M
      : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
39
40
  CachedHashStringRef(StringRef S, uint32_t Hash)
41
25.2M
      : P(S.data()), Size(S.size()), Hash(Hash) {
42
25.2M
    assert(S.size() <= std::numeric_limits<uint32_t>::max());
43
25.2M
  }
44
45
66.0M
  StringRef val() const { return StringRef(P, Size); }
46
9
  const char *data() const { return P; }
47
1.47M
  uint32_t size() const { return Size; }
48
82.8M
  uint32_t hash() const { return Hash; }
49
};
50
51
template <> struct DenseMapInfo<CachedHashStringRef> {
52
10.9M
  static CachedHashStringRef getEmptyKey() {
53
10.9M
    return CachedHashStringRef(DenseMapInfo<StringRef>::getEmptyKey(), 0);
54
10.9M
  }
55
9.40M
  static CachedHashStringRef getTombstoneKey() {
56
9.40M
    return CachedHashStringRef(DenseMapInfo<StringRef>::getTombstoneKey(), 1);
57
9.40M
  }
58
6.37M
  static unsigned getHashValue(const CachedHashStringRef &S) {
59
6.37M
    assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
60
6.37M
    assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
61
6.37M
    return S.hash();
62
6.37M
  }
63
  static bool isEqual(const CachedHashStringRef &LHS,
64
38.2M
                      const CachedHashStringRef &RHS) {
65
38.2M
    return LHS.hash() == RHS.hash() &&
66
38.2M
           
DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val())16.3M
;
67
38.2M
  }
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.
73
class CachedHashString {
74
  friend struct DenseMapInfo<CachedHashString>;
75
76
  char *P;
77
  uint32_t Size;
78
  uint32_t Hash;
79
80
6.15M
  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
81
1.32M
  static char *getTombstoneKeyPtr() {
82
1.32M
    return DenseMapInfo<char *>::getTombstoneKey();
83
1.32M
  }
84
85
3.33M
  bool isEmptyOrTombstone() const {
86
3.33M
    return P == getEmptyKeyPtr() || 
P == getTombstoneKeyPtr()692k
;
87
3.33M
  }
88
89
  struct ConstructEmptyOrTombstoneTy {};
90
91
  CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
92
878k
      : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
93
878k
    assert(isEmptyOrTombstone());
94
878k
  }
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.
102
  explicit CachedHashString(StringRef S)
103
303k
      : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
104
105
  CachedHashString(StringRef S, uint32_t Hash)
106
303k
      : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
107
303k
    memcpy(P, S.data(), S.size());
108
303k
  }
109
110
  // Ideally this class would not be copyable.  But SetVector requires copyable
111
  // keys, and we want this to be usable there.
112
  CachedHashString(const CachedHashString &Other)
113
1.22M
      : Size(Other.Size), Hash(Other.Hash) {
114
1.22M
    if (Other.isEmptyOrTombstone()) {
115
1.20M
      P = Other.P;
116
1.20M
    } else {
117
18.2k
      P = new char[Size];
118
18.2k
      memcpy(P, Other.P, Size);
119
18.2k
    }
120
1.22M
  }
121
122
21.2k
  CachedHashString &operator=(CachedHashString Other) {
123
21.2k
    swap(*this, Other);
124
21.2k
    return *this;
125
21.2k
  }
126
127
  CachedHashString(CachedHashString &&Other) noexcept
128
24.5k
      : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
129
24.5k
    Other.P = getEmptyKeyPtr();
130
24.5k
  }
131
132
2.11M
  ~CachedHashString() {
133
2.11M
    if (!isEmptyOrTombstone())
134
322k
      delete[] P;
135
2.11M
  }
136
137
6.65M
  StringRef val() const { return StringRef(P, Size); }
138
  uint32_t size() const { return Size; }
139
3.61M
  uint32_t hash() const { return Hash; }
140
141
6.10M
  operator StringRef() const { return val(); }
142
0
  operator CachedHashStringRef() const {
143
0
    return CachedHashStringRef(val(), Hash);
144
0
  }
145
146
21.2k
  friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
147
21.2k
    using std::swap;
148
21.2k
    swap(LHS.P, RHS.P);
149
21.2k
    swap(LHS.Size, RHS.Size);
150
21.2k
    swap(LHS.Hash, RHS.Hash);
151
21.2k
  }
152
};
153
154
template <> struct DenseMapInfo<CachedHashString> {
155
526k
  static CachedHashString getEmptyKey() {
156
526k
    return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
157
526k
                            CachedHashString::getEmptyKeyPtr());
158
526k
  }
159
351k
  static CachedHashString getTombstoneKey() {
160
351k
    return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
161
351k
                            CachedHashString::getTombstoneKeyPtr());
162
351k
  }
163
298k
  static unsigned getHashValue(const CachedHashString &S) {
164
298k
    assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
165
298k
    assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
166
298k
    return S.hash();
167
298k
  }
168
  static bool isEqual(const CachedHashString &LHS,
169
1.65M
                      const CachedHashString &RHS) {
170
1.65M
    if (LHS.hash() != RHS.hash())
171
386k
      return false;
172
1.27M
    if (LHS.P == CachedHashString::getEmptyKeyPtr())
173
996k
      return RHS.P == CachedHashString::getEmptyKeyPtr();
174
276k
    if (LHS.P == CachedHashString::getTombstoneKeyPtr())
175
0
      return RHS.P == CachedHashString::getTombstoneKeyPtr();
176
276k
177
276k
    // This is safe because if RHS.P is the empty or tombstone key, it will have
178
276k
    // length 0, so we'll never dereference its pointer.
179
276k
    return LHS.val() == RHS.val();
180
276k
  }
181
};
182
183
} // namespace llvm
184
185
#endif