10218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor//===-------------- TypeOrdering.h - Total ordering for types -------------===// 20218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor// 30218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor// The LLVM Compiler Infrastructure 40218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor// 50218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor// This file is distributed under the University of Illinois Open Source 60218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor// License. See LICENSE.TXT for details. 70218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor// 80218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor//===----------------------------------------------------------------------===// 91f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// 101f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// \file 111f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// \brief Allows QualTypes to be sorted and hence used in maps and sets. 121f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// 131f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// Defines clang::QualTypeOrdering, a total ordering on clang::QualType, 141f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// and hence enables QualType values to be sorted and to be used in 151f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// std::maps, std::sets, llvm::DenseMaps, and llvm::DenseSets. 161f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// 170218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor//===----------------------------------------------------------------------===// 180218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor 190218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor#ifndef LLVM_CLANG_TYPE_ORDERING_H 200218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor#define LLVM_CLANG_TYPE_ORDERING_H 210218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor 22f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor#include "clang/AST/CanonicalType.h" 2330a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "clang/AST/Type.h" 240218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor#include <functional> 250218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor 260218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregornamespace clang { 270218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor 281f26342b5f51387aaa18ee703d7dfdf004871466James Dennett/// \brief Function object that provides a total ordering on QualType values. 290218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregorstruct QualTypeOrdering : std::binary_function<QualType, QualType, bool> { 302b9d973eb749aee6becbcf5e51ab5d49b828c978Douglas Gregor bool operator()(QualType T1, QualType T2) const { 310218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor return std::less<void*>()(T1.getAsOpaquePtr(), T2.getAsOpaquePtr()); 320218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor } 330218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor}; 340218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor 350218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor} 360218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor 37eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregornamespace llvm { 38bf3af056289893f58d37b05a2c80970708781d61Douglas Gregor template<class> struct DenseMapInfo; 39bf3af056289893f58d37b05a2c80970708781d61Douglas Gregor 40eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor template<> struct DenseMapInfo<clang::QualType> { 41eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor static inline clang::QualType getEmptyKey() { return clang::QualType(); } 42eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor 431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump static inline clang::QualType getTombstoneKey() { 44eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor using clang::QualType; 45eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor return QualType::getFromOpaquePtr(reinterpret_cast<clang::Type *>(-1)); 46eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor } 47eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor 48eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor static unsigned getHashValue(clang::QualType Val) { 49b7c3ca8af0a1a3b66fb220562c72dd3102153d5bDouglas Gregor return (unsigned)((uintptr_t)Val.getAsOpaquePtr()) ^ 50b7c3ca8af0a1a3b66fb220562c72dd3102153d5bDouglas Gregor ((unsigned)((uintptr_t)Val.getAsOpaquePtr() >> 9)); 51eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor } 52eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor 53eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor static bool isEqual(clang::QualType LHS, clang::QualType RHS) { 54eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor return LHS == RHS; 55eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor } 56eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor }; 57f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor 58f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor template<> struct DenseMapInfo<clang::CanQualType> { 59f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor static inline clang::CanQualType getEmptyKey() { 60f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor return clang::CanQualType(); 61f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor } 62f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor 63f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor static inline clang::CanQualType getTombstoneKey() { 64f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor using clang::CanQualType; 65f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor return CanQualType::getFromOpaquePtr(reinterpret_cast<clang::Type *>(-1)); 66f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor } 67f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor 68f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor static unsigned getHashValue(clang::CanQualType Val) { 69f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor return (unsigned)((uintptr_t)Val.getAsOpaquePtr()) ^ 70f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor ((unsigned)((uintptr_t)Val.getAsOpaquePtr() >> 9)); 71f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor } 72f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor 73f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor static bool isEqual(clang::CanQualType LHS, clang::CanQualType RHS) { 74f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor return LHS == RHS; 75f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor } 76f5586f6b311c98e1022a8fe0609053849b70d323Douglas Gregor }; 77eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor} 78eb8f3063257a392f15aea48d42fb73ec51afc548Douglas Gregor 790218936235b137bbdcd29a6c36d61d9215bb4eddDouglas Gregor#endif 80