Coverage Report

Created: 2019-07-24 05:18

/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
// 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
26
namespace llvm {
27
28
/// A container which contains a StringRef plus a precomputed hash.
29
class CachedHashStringRef {
30
  const char *P;
31
  uint32_t Size;
32
  uint32_t Hash;
33
34
public:
35
  // Explicit because hashing a string isn't free.
36
  explicit CachedHashStringRef(StringRef S)
37
5.06M
      : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
Unexecuted instantiation: llvm::CachedHashStringRef::CachedHashStringRef(llvm::StringRef)
llvm::CachedHashStringRef::CachedHashStringRef(llvm::StringRef)
Line
Count
Source
37
5.06M
      : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
38
39
  CachedHashStringRef(StringRef S, uint32_t Hash)
40
26.0M
      : P(S.data()), Size(S.size()), Hash(Hash) {
41
26.0M
    assert(S.size() <= std::numeric_limits<uint32_t>::max());
42
26.0M
  }
43
44
67.7M
  StringRef val() const { return StringRef(P, Size); }
45
  const char *data() const { return P; }
46
1.51M
  uint32_t size() const { return Size; }
47
85.9M
  uint32_t hash() const { return Hash; }
48
};
49
50
template <> struct DenseMapInfo<CachedHashStringRef> {
51
11.2M
  static CachedHashStringRef getEmptyKey() {
52
11.2M
    return CachedHashStringRef(DenseMapInfo<StringRef>::getEmptyKey(), 0);
53
11.2M
  }
54
9.70M
  static CachedHashStringRef getTombstoneKey() {
55
9.70M
    return CachedHashStringRef(DenseMapInfo<StringRef>::getTombstoneKey(), 1);
56
9.70M
  }
57
6.60M
  static unsigned getHashValue(const CachedHashStringRef &S) {
58
6.60M
    assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
59
6.60M
    assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
60
6.60M
    return S.hash();
61
6.60M
  }
62
  static bool isEqual(const CachedHashStringRef &LHS,
63
39.6M
                      const CachedHashStringRef &RHS) {
64
39.6M
    return LHS.hash() == RHS.hash() &&
65
39.6M
           
DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val())16.5M
;
66
39.6M
  }
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.
72
class CachedHashString {
73
  friend struct DenseMapInfo<CachedHashString>;
74
75
  char *P;
76
  uint32_t Size;
77
  uint32_t Hash;
78
79
7.08M
  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
80
1.50M
  static char *getTombstoneKeyPtr() {
81
1.50M
    return DenseMapInfo<char *>::getTombstoneKey();
82
1.50M
  }
83
84
3.75M
  bool isEmptyOrTombstone() const {
85
3.75M
    return P == getEmptyKeyPtr() || 
P == getTombstoneKeyPtr()786k
;
86
3.75M
  }
87
88
  struct ConstructEmptyOrTombstoneTy {};
89
90
  CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
91
1.01M
      : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
92
1.01M
    assert(isEmptyOrTombstone());
93
1.01M
  }
94
95
  // TODO: Use small-string optimization to avoid allocating.
96
97
public:
98
0
  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
343k
      : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
Unexecuted instantiation: llvm::CachedHashString::CachedHashString(llvm::StringRef)
llvm::CachedHashString::CachedHashString(llvm::StringRef)
Line
Count
Source
102
343k
      : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
103
104
  CachedHashString(StringRef S, uint32_t Hash)
105
343k
      : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
106
343k
    memcpy(P, S.data(), S.size());
107
343k
  }
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
1.30M
      : Size(Other.Size), Hash(Other.Hash) {
113
1.30M
    if (Other.isEmptyOrTombstone()) {
114
1.28M
      P = Other.P;
115
1.28M
    } else {
116
20.4k
      P = new char[Size];
117
20.4k
      memcpy(P, Other.P, Size);
118
20.4k
    }
119
1.30M
  }
120
121
24.0k
  CachedHashString &operator=(CachedHashString Other) {
122
24.0k
    swap(*this, Other);
123
24.0k
    return *this;
124
24.0k
  }
125
126
  CachedHashString(CachedHashString &&Other) noexcept
127
27.5k
      : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
128
27.5k
    Other.P = getEmptyKeyPtr();
129
27.5k
  }
130
131
2.45M
  ~CachedHashString() {
132
2.45M
    if (!isEmptyOrTombstone())
133
364k
      delete[] P;
134
2.45M
  }
135
136
9.11M
  StringRef val() const { return StringRef(P, Size); }
137
0
  uint32_t size() const { return Size; }
138
4.26M
  uint32_t hash() const { return Hash; }
139
140
8.49M
  operator StringRef() const { return val(); }
141
0
  operator CachedHashStringRef() const {
142
0
    return CachedHashStringRef(val(), Hash);
143
0
  }
144
145
24.0k
  friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
146
24.0k
    using std::swap;
147
24.0k
    swap(LHS.P, RHS.P);
148
24.0k
    swap(LHS.Size, RHS.Size);
149
24.0k
    swap(LHS.Hash, RHS.Hash);
150
24.0k
  }
151
};
152
153
template <> struct DenseMapInfo<CachedHashString> {
154
609k
  static CachedHashString getEmptyKey() {
155
609k
    return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
156
609k
                            CachedHashString::getEmptyKeyPtr());
157
609k
  }
158
401k
  static CachedHashString getTombstoneKey() {
159
401k
    return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
160
401k
                            CachedHashString::getTombstoneKeyPtr());
161
401k
  }
162
338k
  static unsigned getHashValue(const CachedHashString &S) {
163
338k
    assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
164
338k
    assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
165
338k
    return S.hash();
166
338k
  }
167
  static bool isEqual(const CachedHashString &LHS,
168
1.96M
                      const CachedHashString &RHS) {
169
1.96M
    if (LHS.hash() != RHS.hash())
170
459k
      return false;
171
1.50M
    if (LHS.P == CachedHashString::getEmptyKeyPtr())
172
1.18M
      return RHS.P == CachedHashString::getEmptyKeyPtr();
173
313k
    if (LHS.P == CachedHashString::getTombstoneKeyPtr())
174
0
      return RHS.P == CachedHashString::getTombstoneKeyPtr();
175
313k
176
313k
    // This is safe because if RHS.P is the empty or tombstone key, it will have
177
313k
    // length 0, so we'll never dereference its pointer.
178
313k
    return LHS.val() == RHS.val();
179
313k
  }
180
};
181
182
} // namespace llvm
183
184
#endif