Home | History | Annotate | Download | only in ADT 
      1 //===- llvm/ADT/PointerEmbeddedInt.h ----------------------------*- 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 #ifndef LLVM_ADT_POINTEREMBEDDEDINT_H
     11 #define LLVM_ADT_POINTEREMBEDDEDINT_H
     12 
     13 #include "llvm/ADT/DenseMapInfo.h"
     14 #include "llvm/Support/MathExtras.h"
     15 #include "llvm/Support/PointerLikeTypeTraits.h"
     16 #include <cassert>
     17 #include <climits>
     18 #include <cstdint>
     19 #include <type_traits>
     20 
     21 namespace llvm {
     22 
     23 /// Utility to embed an integer into a pointer-like type. This is specifically
     24 /// intended to allow embedding integers where fewer bits are required than
     25 /// exist in a pointer, and the integer can participate in abstractions along
     26 /// side other pointer-like types. For example it can be placed into a \c
     27 /// PointerSumType or \c PointerUnion.
     28 ///
     29 /// Note that much like pointers, an integer value of zero has special utility
     30 /// due to boolean conversions. For example, a non-null value can be tested for
     31 /// in the above abstractions without testing the particular active member.
     32 /// Also, the default constructed value zero initializes the integer.
     33 template <typename IntT, int Bits = sizeof(IntT) * CHAR_BIT>
     34 class PointerEmbeddedInt {
     35   uintptr_t Value = 0;
     36 
     37   // Note: This '<' is correct; using '<=' would result in some shifts
     38   // overflowing their storage types.
     39   static_assert(Bits < sizeof(uintptr_t) * CHAR_BIT,
     40                 "Cannot embed more bits than we have in a pointer!");
     41 
     42   enum : uintptr_t {
     43     // We shift as many zeros into the value as we can while preserving the
     44     // number of bits desired for the integer.
     45     Shift = sizeof(uintptr_t) * CHAR_BIT - Bits,
     46 
     47     // We also want to be able to mask out the preserved bits for asserts.
     48     Mask = static_cast<uintptr_t>(-1) << Bits
     49   };
     50 
     51   struct RawValueTag {
     52     explicit RawValueTag() = default;
     53   };
     54 
     55   friend class PointerLikeTypeTraits<PointerEmbeddedInt>;
     56 
     57   explicit PointerEmbeddedInt(uintptr_t Value, RawValueTag) : Value(Value) {}
     58 
     59 public:
     60   PointerEmbeddedInt() = default;
     61 
     62   PointerEmbeddedInt(IntT I) { *this = I; }
     63 
     64   PointerEmbeddedInt &operator=(IntT I) {
     65     assert((std::is_signed<IntT>::value ? isInt<Bits>(I) : isUInt<Bits>(I)) &&
     66            "Integer has bits outside those preserved!");
     67     Value = static_cast<uintptr_t>(I) << Shift;
     68     return *this;
     69   }
     70 
     71   // Note that this implicit conversion additionally allows all of the basic
     72   // comparison operators to work transparently, etc.
     73   operator IntT() const {
     74     if (std::is_signed<IntT>::value)
     75       return static_cast<IntT>(static_cast<intptr_t>(Value) >> Shift);
     76     return static_cast<IntT>(Value >> Shift);
     77   }
     78 };
     79 
     80 // Provide pointer like traits to support use with pointer unions and sum
     81 // types.
     82 template <typename IntT, int Bits>
     83 class PointerLikeTypeTraits<PointerEmbeddedInt<IntT, Bits>> {
     84   using T = PointerEmbeddedInt<IntT, Bits>;
     85 
     86 public:
     87   static inline void *getAsVoidPointer(const T &P) {
     88     return reinterpret_cast<void *>(P.Value);
     89   }
     90 
     91   static inline T getFromVoidPointer(void *P) {
     92     return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag());
     93   }
     94 
     95   static inline T getFromVoidPointer(const void *P) {
     96     return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag());
     97   }
     98 
     99   enum { NumLowBitsAvailable = T::Shift };
    100 };
    101 
    102 // Teach DenseMap how to use PointerEmbeddedInt objects as keys if the Int type
    103 // itself can be a key.
    104 template <typename IntT, int Bits>
    105 struct DenseMapInfo<PointerEmbeddedInt<IntT, Bits>> {
    106   using T = PointerEmbeddedInt<IntT, Bits>;
    107   using IntInfo = DenseMapInfo<IntT>;
    108 
    109   static inline T getEmptyKey() { return IntInfo::getEmptyKey(); }
    110   static inline T getTombstoneKey() { return IntInfo::getTombstoneKey(); }
    111 
    112   static unsigned getHashValue(const T &Arg) {
    113     return IntInfo::getHashValue(Arg);
    114   }
    115 
    116   static bool isEqual(const T &LHS, const T &RHS) { return LHS == RHS; }
    117 };
    118 
    119 } // end namespace llvm
    120 
    121 #endif // LLVM_ADT_POINTEREMBEDDEDINT_H
    122