LCOV - code coverage report
Current view: top level - include/llvm/ADT - CachedHashString.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 37 38 97.4 %
Date: 2018-07-13 00:08:38 Functions: 6 6 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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      446220 :       : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
      39             : 
      40             :   CachedHashStringRef(StringRef S, uint32_t Hash)
      41     1872505 :       : P(S.data()), Size(S.size()), Hash(Hash) {
      42             :     assert(S.size() <= std::numeric_limits<uint32_t>::max());
      43             :   }
      44             : 
      45    43866515 :   StringRef val() const { return StringRef(P, Size); }
      46             :   const char *data() const { return P; }
      47             :   uint32_t size() const { return Size; }
      48             :   uint32_t hash() const { return Hash; }
      49             : };
      50             : 
      51             : template <> struct DenseMapInfo<CachedHashStringRef> {
      52             :   static CachedHashStringRef getEmptyKey() {
      53             :     return CachedHashStringRef(DenseMapInfo<StringRef>::getEmptyKey(), 0);
      54             :   }
      55             :   static CachedHashStringRef getTombstoneKey() {
      56             :     return CachedHashStringRef(DenseMapInfo<StringRef>::getTombstoneKey(), 1);
      57             :   }
      58             :   static unsigned getHashValue(const CachedHashStringRef &S) {
      59             :     assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
      60             :     assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
      61     2694898 :     return S.hash();
      62             :   }
      63    19324162 :   static bool isEqual(const CachedHashStringRef &LHS,
      64             :                       const CachedHashStringRef &RHS) {
      65    26880841 :     return LHS.hash() == RHS.hash() &&
      66    41994199 :            DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val());
      67             :   }
      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             :   static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
      81             :   static char *getTombstoneKeyPtr() {
      82             :     return DenseMapInfo<char *>::getTombstoneKey();
      83             :   }
      84             : 
      85             :   bool isEmptyOrTombstone() const {
      86     2361416 :     return P == getEmptyKeyPtr() || P == getTombstoneKeyPtr();
      87             :   }
      88             : 
      89             :   struct ConstructEmptyOrTombstoneTy {};
      90             : 
      91             :   CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
      92      488051 :       : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
      93             :     assert(isEmptyOrTombstone());
      94             :   }
      95             : 
      96             :   // TODO: Use small-string optimization to avoid allocating.
      97             : 
      98             : public:
      99       34656 :   explicit CachedHashString(const char *S) : CachedHashString(StringRef(S)) {}
     100             : 
     101             :   // Explicit because copying and hashing a string isn't free.
     102      298034 :   explicit CachedHashString(StringRef S)
     103      596068 :       : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
     104             : 
     105      298034 :   CachedHashString(StringRef S, uint32_t Hash)
     106      298034 :       : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
     107      298034 :     memcpy(P, S.data(), S.size());
     108      298034 :   }
     109             : 
     110             :   // Ideally this class would not be copyable.  But SetVector requires copyable
     111             :   // keys, and we want this to be usable there.
     112      932576 :   CachedHashString(const CachedHashString &Other)
     113      932576 :       : Size(Other.Size), Hash(Other.Hash) {
     114      932576 :     if (Other.isEmptyOrTombstone()) {
     115      914782 :       P = Other.P;
     116             :     } else {
     117       17794 :       P = new char[Size];
     118       17794 :       memcpy(P, Other.P, Size);
     119             :     }
     120      932576 :   }
     121             : 
     122             :   CachedHashString &operator=(CachedHashString Other) {
     123             :     swap(*this, Other);
     124             :     return *this;
     125             :   }
     126             : 
     127             :   CachedHashString(CachedHashString &&Other) noexcept
     128       22519 :       : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
     129       22519 :     Other.P = getEmptyKeyPtr();
     130             :   }
     131             : 
     132      920136 :   ~CachedHashString() {
     133     1388627 :     if (!isEmptyOrTombstone())
     134      315828 :       delete[] P;
     135             :   }
     136             : 
     137     6296472 :   StringRef val() const { return StringRef(P, Size); }
     138             :   uint32_t size() const { return Size; }
     139             :   uint32_t hash() const { return Hash; }
     140             : 
     141     5754494 :   operator StringRef() const { return val(); }
     142             :   operator CachedHashStringRef() const {
     143             :     return CachedHashStringRef(val(), Hash);
     144             :   }
     145             : 
     146             :   friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
     147             :     using std::swap;
     148             :     swap(LHS.P, RHS.P);
     149             :     swap(LHS.Size, RHS.Size);
     150             :     swap(LHS.Hash, RHS.Hash);
     151             :   }
     152             : };
     153             : 
     154             : template <> struct DenseMapInfo<CachedHashString> {
     155             :   static CachedHashString getEmptyKey() {
     156             :     return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
     157             :                             CachedHashString::getEmptyKeyPtr());
     158             :   }
     159             :   static CachedHashString getTombstoneKey() {
     160             :     return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
     161             :                             CachedHashString::getTombstoneKeyPtr());
     162             :   }
     163             :   static unsigned getHashValue(const CachedHashString &S) {
     164             :     assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
     165             :     assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
     166      291431 :     return S.hash();
     167             :   }
     168      747310 :   static bool isEqual(const CachedHashString &LHS,
     169             :                       const CachedHashString &RHS) {
     170      747310 :     if (LHS.hash() != RHS.hash())
     171             :       return false;
     172      390387 :     if (LHS.P == CachedHashString::getEmptyKeyPtr())
     173      119398 :       return RHS.P == CachedHashString::getEmptyKeyPtr();
     174      270989 :     if (LHS.P == CachedHashString::getTombstoneKeyPtr())
     175           0 :       return RHS.P == CachedHashString::getTombstoneKeyPtr();
     176             : 
     177             :     // This is safe because if RHS.P is the empty or tombstone key, it will have
     178             :     // length 0, so we'll never dereference its pointer.
     179      541978 :     return LHS.val() == RHS.val();
     180             :   }
     181             : };
     182             : 
     183             : } // namespace llvm
     184             : 
     185             : #endif

Generated by: LCOV version 1.13