include/llvm/ADT/CachedHashString.h

   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       : 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
  50 template <> 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.
  72 class 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
  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       : 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
 153 template <> 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