Coverage Report

Created: 2019-03-22 08:08

/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
4.70M
      : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
38
39
  CachedHashStringRef(StringRef S, uint32_t Hash)
40
23.7M
      : P(S.data()), Size(S.size()), Hash(Hash) {
41
23.7M
    assert(S.size() <= std::numeric_limits<uint32_t>::max());
42
23.7M
  }
43
44
61.5M
  StringRef val() const { return StringRef(P, Size); }
45
9
  const char *data() const { return P; }
46
1.35M
  uint32_t size() const { return Size; }
47
76.6M
  uint32_t hash() const { return Hash; }
48
};
49
50
template <> struct DenseMapInfo<CachedHashStringRef> {
51
10.2M
  static CachedHashStringRef getEmptyKey() {
52
10.2M
    return CachedHashStringRef(DenseMapInfo<StringRef>::getEmptyKey(), 0);
53
10.2M
  }
54
8.83M
  static CachedHashStringRef getTombstoneKey() {
55
8.83M
    return CachedHashStringRef(DenseMapInfo<StringRef>::getTombstoneKey(), 1);
56
8.83M
  }
57
6.05M
  static unsigned getHashValue(const CachedHashStringRef &S) {
58
6.05M
    assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
59
6.05M
    assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
60
6.05M
    return S.hash();
61
6.05M
  }
62
  static bool isEqual(const CachedHashStringRef &LHS,
63
35.3M
                      const CachedHashStringRef &RHS) {
64
35.3M
    return LHS.hash() == RHS.hash() &&
65
35.3M
           
DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val())14.9M
;
66
35.3M
  }
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
6.58M
  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
80
1.32M
  static char *getTombstoneKeyPtr() {
81
1.32M
    return DenseMapInfo<char *>::getTombstoneKey();
82
1.32M
  }
83
84
3.48M
  bool isEmptyOrTombstone() const {
85
3.48M
    return P == getEmptyKeyPtr() || 
P == getTombstoneKeyPtr()695k
;
86
3.48M
  }
87
88
  struct ConstructEmptyOrTombstoneTy {};
89
90
  CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
91
908k
      : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
92
908k
    assert(isEmptyOrTombstone());
93
908k
  }
94
95
  // TODO: Use small-string optimization to avoid allocating.
96
97
public:
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
301k
      : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
103
104
  CachedHashString(StringRef S, uint32_t Hash)
105
301k
      : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
106
301k
    memcpy(P, S.data(), S.size());
107
301k
  }
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.24M
      : Size(Other.Size), Hash(Other.Hash) {
113
1.24M
    if (Other.isEmptyOrTombstone()) {
114
1.22M
      P = Other.P;
115
1.22M
    } else {
116
18.2k
      P = new char[Size];
117
18.2k
      memcpy(P, Other.P, Size);
118
18.2k
    }
119
1.24M
  }
120
121
21.1k
  CachedHashString &operator=(CachedHashString Other) {
122
21.1k
    swap(*this, Other);
123
21.1k
    return *this;
124
21.1k
  }
125
126
  CachedHashString(CachedHashString &&Other) noexcept
127
24.5k
      : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
128
24.5k
    Other.P = getEmptyKeyPtr();
129
24.5k
  }
130
131
2.24M
  ~CachedHashString() {
132
2.24M
    if (!isEmptyOrTombstone())
133
320k
      delete[] P;
134
2.24M
  }
135
136
6.58M
  StringRef val() const { return StringRef(P, Size); }
137
  uint32_t size() const { return Size; }
138
3.86M
  uint32_t hash() const { return Hash; }
139
140
6.03M
  operator StringRef() const { return val(); }
141
0
  operator CachedHashStringRef() const {
142
0
    return CachedHashStringRef(val(), Hash);
143
0
  }
144
145
21.1k
  friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
146
21.1k
    using std::swap;
147
21.1k
    swap(LHS.P, RHS.P);
148
21.1k
    swap(LHS.Size, RHS.Size);
149
21.1k
    swap(LHS.Hash, RHS.Hash);
150
21.1k
  }
151
};
152
153
template <> struct DenseMapInfo<CachedHashString> {
154
551k
  static CachedHashString getEmptyKey() {
155
551k
    return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
156
551k
                            CachedHashString::getEmptyKeyPtr());
157
551k
  }
158
356k
  static CachedHashString getTombstoneKey() {
159
356k
    return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
160
356k
                            CachedHashString::getTombstoneKeyPtr());
161
356k
  }
162
296k
  static unsigned getHashValue(const CachedHashString &S) {
163
296k
    assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
164
296k
    assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
165
296k
    return S.hash();
166
296k
  }
167
  static bool isEqual(const CachedHashString &LHS,
168
1.78M
                      const CachedHashString &RHS) {
169
1.78M
    if (LHS.hash() != RHS.hash())
170
384k
      return false;
171
1.39M
    if (LHS.P == CachedHashString::getEmptyKeyPtr())
172
1.12M
      return RHS.P == CachedHashString::getEmptyKeyPtr();
173
274k
    if (LHS.P == CachedHashString::getTombstoneKeyPtr())
174
0
      return RHS.P == CachedHashString::getTombstoneKeyPtr();
175
274k
176
274k
    // This is safe because if RHS.P is the empty or tombstone key, it will have
177
274k
    // length 0, so we'll never dereference its pointer.
178
274k
    return LHS.val() == RHS.val();
179
274k
  }
180
};
181
182
} // namespace llvm
183
184
#endif