llvm/ADT/CachedHashString.h

0001 //===- llvm/ADT/CachedHashString.h - Prehashed string/StringRef -*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines CachedHashString and CachedHashStringRef.  These are
0011 /// owning and not-owning string types that store their hash in addition to
0012 /// their string data.
0013 ///
0014 /// Unlike std::string, CachedHashString can be used in DenseSet/DenseMap
0015 /// (because, unlike std::string, CachedHashString lets us have empty and
0016 /// tombstone values).
0017 ///
0018 //===----------------------------------------------------------------------===//
0019
0020 #ifndef LLVM_ADT_CACHEDHASHSTRING_H
0021 #define LLVM_ADT_CACHEDHASHSTRING_H
0022
0023 #include "llvm/ADT/DenseMapInfo.h"
0024 #include "llvm/ADT/StringRef.h"
0025
0026 namespace llvm {
0027
0028 /// A container which contains a StringRef plus a precomputed hash.
0029 class CachedHashStringRef {
0030   const char *P;
0031   uint32_t Size;
0032   uint32_t Hash;
0033
0034 public:
0035   // Explicit because hashing a string isn't free.
0036   explicit CachedHashStringRef(StringRef S)
0037       : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
0038
0039   CachedHashStringRef(StringRef S, uint32_t Hash)
0040       : P(S.data()), Size(S.size()), Hash(Hash) {
0041     assert(S.size() <= std::numeric_limits<uint32_t>::max());
0042   }
0043
0044   StringRef val() const { return StringRef(P, Size); }
0045   const char *data() const { return P; }
0046   uint32_t size() const { return Size; }
0047   uint32_t hash() const { return Hash; }
0048 };
0049
0050 template <> struct DenseMapInfo<CachedHashStringRef> {
0051   static CachedHashStringRef getEmptyKey() {
0052     return CachedHashStringRef(DenseMapInfo<StringRef>::getEmptyKey(), 0);
0053   }
0054   static CachedHashStringRef getTombstoneKey() {
0055     return CachedHashStringRef(DenseMapInfo<StringRef>::getTombstoneKey(), 1);
0056   }
0057   static unsigned getHashValue(const CachedHashStringRef &S) {
0058     assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
0059     assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
0060     return S.hash();
0061   }
0062   static bool isEqual(const CachedHashStringRef &LHS,
0063                       const CachedHashStringRef &RHS) {
0064     return LHS.hash() == RHS.hash() &&
0065            DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val());
0066   }
0067 };
0068
0069 /// A container which contains a string, which it owns, plus a precomputed hash.
0070 ///
0071 /// We do not null-terminate the string.
0072 class CachedHashString {
0073   friend struct DenseMapInfo<CachedHashString>;
0074
0075   char *P;
0076   uint32_t Size;
0077   uint32_t Hash;
0078
0079   static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
0080   static char *getTombstoneKeyPtr() {
0081     return DenseMapInfo<char *>::getTombstoneKey();
0082   }
0083
0084   bool isEmptyOrTombstone() const {
0085     return P == getEmptyKeyPtr() || P == getTombstoneKeyPtr();
0086   }
0087
0088   struct ConstructEmptyOrTombstoneTy {};
0089
0090   CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
0091       : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
0092     assert(isEmptyOrTombstone());
0093   }
0094
0095   // TODO: Use small-string optimization to avoid allocating.
0096
0097 public:
0098   explicit CachedHashString(const char *S) : CachedHashString(StringRef(S)) {}
0099
0100   // Explicit because copying and hashing a string isn't free.
0101   explicit CachedHashString(StringRef S)
0102       : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
0103
0104   CachedHashString(StringRef S, uint32_t Hash)
0105       : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
0106     memcpy(P, S.data(), S.size());
0107   }
0108
0109   // Ideally this class would not be copyable.  But SetVector requires copyable
0110   // keys, and we want this to be usable there.
0111   CachedHashString(const CachedHashString &Other)
0112       : Size(Other.Size), Hash(Other.Hash) {
0113     if (Other.isEmptyOrTombstone()) {
0114       P = Other.P;
0115     } else {
0116       P = new char[Size];
0117       memcpy(P, Other.P, Size);
0118     }
0119   }
0120
0121   CachedHashString &operator=(CachedHashString Other) {
0122     swap(*this, Other);
0123     return *this;
0124   }
0125
0126   CachedHashString(CachedHashString &&Other) noexcept
0127       : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
0128     Other.P = getEmptyKeyPtr();
0129   }
0130
0131   ~CachedHashString() {
0132     if (!isEmptyOrTombstone())
0133       delete[] P;
0134   }
0135
0136   StringRef val() const { return StringRef(P, Size); }
0137   uint32_t size() const { return Size; }
0138   uint32_t hash() const { return Hash; }
0139
0140   operator StringRef() const { return val(); }
0141   operator CachedHashStringRef() const {
0142     return CachedHashStringRef(val(), Hash);
0143   }
0144
0145   friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
0146     using std::swap;
0147     swap(LHS.P, RHS.P);
0148     swap(LHS.Size, RHS.Size);
0149     swap(LHS.Hash, RHS.Hash);
0150   }
0151 };
0152
0153 template <> struct DenseMapInfo<CachedHashString> {
0154   static CachedHashString getEmptyKey() {
0155     return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
0156                             CachedHashString::getEmptyKeyPtr());
0157   }
0158   static CachedHashString getTombstoneKey() {
0159     return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
0160                             CachedHashString::getTombstoneKeyPtr());
0161   }
0162   static unsigned getHashValue(const CachedHashString &S) {
0163     assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
0164     assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
0165     return S.hash();
0166   }
0167   static bool isEqual(const CachedHashString &LHS,
0168                       const CachedHashString &RHS) {
0169     if (LHS.hash() != RHS.hash())
0170       return false;
0171     if (LHS.P == CachedHashString::getEmptyKeyPtr())
0172       return RHS.P == CachedHashString::getEmptyKeyPtr();
0173     if (LHS.P == CachedHashString::getTombstoneKeyPtr())
0174       return RHS.P == CachedHashString::getTombstoneKeyPtr();
0175
0176     // This is safe because if RHS.P is the empty or tombstone key, it will have
0177     // length 0, so we'll never dereference its pointer.
0178     return LHS.val() == RHS.val();
0179   }
0180 };
0181
0182 } // namespace llvm
0183
0184 #endif