1198090Srdivacky//===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===// 2198090Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6198090Srdivacky// 7198090Srdivacky//===----------------------------------------------------------------------===// 8198090Srdivacky// 9198090Srdivacky// This file defines DenseMapInfo traits for DenseMap. 10198090Srdivacky// 11198090Srdivacky//===----------------------------------------------------------------------===// 12198090Srdivacky 13198090Srdivacky#ifndef LLVM_ADT_DENSEMAPINFO_H 14198090Srdivacky#define LLVM_ADT_DENSEMAPINFO_H 15198090Srdivacky 16296417Sdim#include "llvm/ADT/ArrayRef.h" 17288943Sdim#include "llvm/ADT/Hashing.h" 18288943Sdim#include "llvm/ADT/StringRef.h" 19198090Srdivacky#include "llvm/Support/PointerLikeTypeTraits.h" 20360784Sdim#include "llvm/Support/TypeSize.h" 21321369Sdim#include <cassert> 22321369Sdim#include <cstddef> 23321369Sdim#include <cstdint> 24321369Sdim#include <utility> 25198090Srdivacky 26198090Srdivackynamespace llvm { 27198090Srdivacky 28198090Srdivackytemplate<typename T> 29198090Srdivackystruct DenseMapInfo { 30198090Srdivacky //static inline T getEmptyKey(); 31198090Srdivacky //static inline T getTombstoneKey(); 32198090Srdivacky //static unsigned getHashValue(const T &Val); 33198090Srdivacky //static bool isEqual(const T &LHS, const T &RHS); 34198090Srdivacky}; 35198090Srdivacky 36198090Srdivacky// Provide DenseMapInfo for all pointers. 37198090Srdivackytemplate<typename T> 38198090Srdivackystruct DenseMapInfo<T*> { 39198090Srdivacky static inline T* getEmptyKey() { 40243830Sdim uintptr_t Val = static_cast<uintptr_t>(-1); 41198090Srdivacky Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 42198090Srdivacky return reinterpret_cast<T*>(Val); 43198090Srdivacky } 44321369Sdim 45198090Srdivacky static inline T* getTombstoneKey() { 46243830Sdim uintptr_t Val = static_cast<uintptr_t>(-2); 47198090Srdivacky Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 48198090Srdivacky return reinterpret_cast<T*>(Val); 49198090Srdivacky } 50321369Sdim 51198090Srdivacky static unsigned getHashValue(const T *PtrVal) { 52198090Srdivacky return (unsigned((uintptr_t)PtrVal) >> 4) ^ 53198090Srdivacky (unsigned((uintptr_t)PtrVal) >> 9); 54198090Srdivacky } 55321369Sdim 56198090Srdivacky static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 57198090Srdivacky}; 58198090Srdivacky 59198090Srdivacky// Provide DenseMapInfo for chars. 60198090Srdivackytemplate<> struct DenseMapInfo<char> { 61198090Srdivacky static inline char getEmptyKey() { return ~0; } 62198090Srdivacky static inline char getTombstoneKey() { return ~0 - 1; } 63226633Sdim static unsigned getHashValue(const char& Val) { return Val * 37U; } 64321369Sdim 65198090Srdivacky static bool isEqual(const char &LHS, const char &RHS) { 66198090Srdivacky return LHS == RHS; 67198090Srdivacky } 68198090Srdivacky}; 69296417Sdim 70360784Sdim// Provide DenseMapInfo for unsigned chars. 71360784Sdimtemplate <> struct DenseMapInfo<unsigned char> { 72360784Sdim static inline unsigned char getEmptyKey() { return ~0; } 73360784Sdim static inline unsigned char getTombstoneKey() { return ~0 - 1; } 74360784Sdim static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; } 75360784Sdim 76360784Sdim static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) { 77360784Sdim return LHS == RHS; 78360784Sdim } 79360784Sdim}; 80360784Sdim 81321369Sdim// Provide DenseMapInfo for unsigned shorts. 82321369Sdimtemplate <> struct DenseMapInfo<unsigned short> { 83321369Sdim static inline unsigned short getEmptyKey() { return 0xFFFF; } 84321369Sdim static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; } 85321369Sdim static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; } 86321369Sdim 87321369Sdim static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) { 88321369Sdim return LHS == RHS; 89321369Sdim } 90321369Sdim}; 91321369Sdim 92198090Srdivacky// Provide DenseMapInfo for unsigned ints. 93198090Srdivackytemplate<> struct DenseMapInfo<unsigned> { 94234353Sdim static inline unsigned getEmptyKey() { return ~0U; } 95198090Srdivacky static inline unsigned getTombstoneKey() { return ~0U - 1; } 96226633Sdim static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 97321369Sdim 98198090Srdivacky static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 99198090Srdivacky return LHS == RHS; 100198090Srdivacky } 101198090Srdivacky}; 102198090Srdivacky 103198090Srdivacky// Provide DenseMapInfo for unsigned longs. 104198090Srdivackytemplate<> struct DenseMapInfo<unsigned long> { 105198090Srdivacky static inline unsigned long getEmptyKey() { return ~0UL; } 106198090Srdivacky static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } 107321369Sdim 108198090Srdivacky static unsigned getHashValue(const unsigned long& Val) { 109198396Srdivacky return (unsigned)(Val * 37UL); 110198090Srdivacky } 111321369Sdim 112198090Srdivacky static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { 113198090Srdivacky return LHS == RHS; 114198090Srdivacky } 115198090Srdivacky}; 116198090Srdivacky 117198090Srdivacky// Provide DenseMapInfo for unsigned long longs. 118198090Srdivackytemplate<> struct DenseMapInfo<unsigned long long> { 119198090Srdivacky static inline unsigned long long getEmptyKey() { return ~0ULL; } 120198090Srdivacky static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } 121321369Sdim 122198090Srdivacky static unsigned getHashValue(const unsigned long long& Val) { 123198396Srdivacky return (unsigned)(Val * 37ULL); 124198090Srdivacky } 125321369Sdim 126198090Srdivacky static bool isEqual(const unsigned long long& LHS, 127198090Srdivacky const unsigned long long& RHS) { 128198090Srdivacky return LHS == RHS; 129198090Srdivacky } 130198090Srdivacky}; 131198090Srdivacky 132321369Sdim// Provide DenseMapInfo for shorts. 133321369Sdimtemplate <> struct DenseMapInfo<short> { 134321369Sdim static inline short getEmptyKey() { return 0x7FFF; } 135321369Sdim static inline short getTombstoneKey() { return -0x7FFF - 1; } 136321369Sdim static unsigned getHashValue(const short &Val) { return Val * 37U; } 137321369Sdim static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; } 138321369Sdim}; 139321369Sdim 140207618Srdivacky// Provide DenseMapInfo for ints. 141207618Srdivackytemplate<> struct DenseMapInfo<int> { 142207618Srdivacky static inline int getEmptyKey() { return 0x7fffffff; } 143207618Srdivacky static inline int getTombstoneKey() { return -0x7fffffff - 1; } 144226633Sdim static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); } 145321369Sdim 146207618Srdivacky static bool isEqual(const int& LHS, const int& RHS) { 147207618Srdivacky return LHS == RHS; 148207618Srdivacky } 149207618Srdivacky}; 150207618Srdivacky 151218893Sdim// Provide DenseMapInfo for longs. 152218893Sdimtemplate<> struct DenseMapInfo<long> { 153218893Sdim static inline long getEmptyKey() { 154243830Sdim return (1UL << (sizeof(long) * 8 - 1)) - 1UL; 155218893Sdim } 156321369Sdim 157218893Sdim static inline long getTombstoneKey() { return getEmptyKey() - 1L; } 158321369Sdim 159218893Sdim static unsigned getHashValue(const long& Val) { 160226633Sdim return (unsigned)(Val * 37UL); 161218893Sdim } 162321369Sdim 163218893Sdim static bool isEqual(const long& LHS, const long& RHS) { 164218893Sdim return LHS == RHS; 165218893Sdim } 166218893Sdim}; 167218893Sdim 168202878Srdivacky// Provide DenseMapInfo for long longs. 169202878Srdivackytemplate<> struct DenseMapInfo<long long> { 170202878Srdivacky static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; } 171202878Srdivacky static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; } 172321369Sdim 173202878Srdivacky static unsigned getHashValue(const long long& Val) { 174226633Sdim return (unsigned)(Val * 37ULL); 175202878Srdivacky } 176321369Sdim 177202878Srdivacky static bool isEqual(const long long& LHS, 178202878Srdivacky const long long& RHS) { 179202878Srdivacky return LHS == RHS; 180202878Srdivacky } 181202878Srdivacky}; 182202878Srdivacky 183198090Srdivacky// Provide DenseMapInfo for all pairs whose members have info. 184198090Srdivackytemplate<typename T, typename U> 185321369Sdimstruct DenseMapInfo<std::pair<T, U>> { 186321369Sdim using Pair = std::pair<T, U>; 187321369Sdim using FirstInfo = DenseMapInfo<T>; 188321369Sdim using SecondInfo = DenseMapInfo<U>; 189198090Srdivacky 190198090Srdivacky static inline Pair getEmptyKey() { 191198090Srdivacky return std::make_pair(FirstInfo::getEmptyKey(), 192198090Srdivacky SecondInfo::getEmptyKey()); 193198090Srdivacky } 194321369Sdim 195198090Srdivacky static inline Pair getTombstoneKey() { 196198090Srdivacky return std::make_pair(FirstInfo::getTombstoneKey(), 197226633Sdim SecondInfo::getTombstoneKey()); 198198090Srdivacky } 199321369Sdim 200198090Srdivacky static unsigned getHashValue(const Pair& PairVal) { 201198090Srdivacky uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 202198090Srdivacky | (uint64_t)SecondInfo::getHashValue(PairVal.second); 203198090Srdivacky key += ~(key << 32); 204198090Srdivacky key ^= (key >> 22); 205198090Srdivacky key += ~(key << 13); 206198090Srdivacky key ^= (key >> 8); 207198090Srdivacky key += (key << 3); 208198090Srdivacky key ^= (key >> 15); 209198090Srdivacky key += ~(key << 27); 210198090Srdivacky key ^= (key >> 31); 211198090Srdivacky return (unsigned)key; 212198090Srdivacky } 213321369Sdim 214221345Sdim static bool isEqual(const Pair &LHS, const Pair &RHS) { 215226633Sdim return FirstInfo::isEqual(LHS.first, RHS.first) && 216221345Sdim SecondInfo::isEqual(LHS.second, RHS.second); 217221345Sdim } 218198090Srdivacky}; 219198090Srdivacky 220288943Sdim// Provide DenseMapInfo for StringRefs. 221288943Sdimtemplate <> struct DenseMapInfo<StringRef> { 222288943Sdim static inline StringRef getEmptyKey() { 223288943Sdim return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)), 224288943Sdim 0); 225288943Sdim } 226321369Sdim 227288943Sdim static inline StringRef getTombstoneKey() { 228288943Sdim return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)), 229288943Sdim 0); 230288943Sdim } 231321369Sdim 232288943Sdim static unsigned getHashValue(StringRef Val) { 233288943Sdim assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!"); 234288943Sdim assert(Val.data() != getTombstoneKey().data() && 235288943Sdim "Cannot hash the tombstone key!"); 236288943Sdim return (unsigned)(hash_value(Val)); 237288943Sdim } 238321369Sdim 239288943Sdim static bool isEqual(StringRef LHS, StringRef RHS) { 240288943Sdim if (RHS.data() == getEmptyKey().data()) 241288943Sdim return LHS.data() == getEmptyKey().data(); 242288943Sdim if (RHS.data() == getTombstoneKey().data()) 243288943Sdim return LHS.data() == getTombstoneKey().data(); 244288943Sdim return LHS == RHS; 245288943Sdim } 246288943Sdim}; 247288943Sdim 248296417Sdim// Provide DenseMapInfo for ArrayRefs. 249296417Sdimtemplate <typename T> struct DenseMapInfo<ArrayRef<T>> { 250296417Sdim static inline ArrayRef<T> getEmptyKey() { 251296417Sdim return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)), 252296417Sdim size_t(0)); 253296417Sdim } 254321369Sdim 255296417Sdim static inline ArrayRef<T> getTombstoneKey() { 256296417Sdim return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)), 257296417Sdim size_t(0)); 258296417Sdim } 259321369Sdim 260296417Sdim static unsigned getHashValue(ArrayRef<T> Val) { 261296417Sdim assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!"); 262296417Sdim assert(Val.data() != getTombstoneKey().data() && 263296417Sdim "Cannot hash the tombstone key!"); 264296417Sdim return (unsigned)(hash_value(Val)); 265296417Sdim } 266321369Sdim 267296417Sdim static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) { 268296417Sdim if (RHS.data() == getEmptyKey().data()) 269296417Sdim return LHS.data() == getEmptyKey().data(); 270296417Sdim if (RHS.data() == getTombstoneKey().data()) 271296417Sdim return LHS.data() == getTombstoneKey().data(); 272296417Sdim return LHS == RHS; 273296417Sdim } 274296417Sdim}; 275296417Sdim 276341825Sdimtemplate <> struct DenseMapInfo<hash_code> { 277341825Sdim static inline hash_code getEmptyKey() { return hash_code(-1); } 278341825Sdim static inline hash_code getTombstoneKey() { return hash_code(-2); } 279341825Sdim static unsigned getHashValue(hash_code val) { return val; } 280341825Sdim static bool isEqual(hash_code LHS, hash_code RHS) { return LHS == RHS; } 281341825Sdim}; 282341825Sdim 283353358Sdimtemplate <> struct DenseMapInfo<ElementCount> { 284353358Sdim static inline ElementCount getEmptyKey() { return {~0U, true}; } 285353358Sdim static inline ElementCount getTombstoneKey() { return {~0U - 1, false}; } 286353358Sdim static unsigned getHashValue(const ElementCount& EltCnt) { 287353358Sdim if (EltCnt.Scalable) 288353358Sdim return (EltCnt.Min * 37U) - 1U; 289353358Sdim 290353358Sdim return EltCnt.Min * 37U; 291353358Sdim } 292353358Sdim 293353358Sdim static bool isEqual(const ElementCount& LHS, const ElementCount& RHS) { 294353358Sdim return LHS == RHS; 295353358Sdim } 296353358Sdim}; 297353358Sdim 298198090Srdivacky} // end namespace llvm 299198090Srdivacky 300321369Sdim#endif // LLVM_ADT_DENSEMAPINFO_H 301