small_shared_n_way_ptr.h

Go to the documentation of this file.

/*******************************************************************\
 
Module: Small shared n-way pointer
 
Author: Daniel Poetzl
 
\*******************************************************************/
 
#ifndef CPROVER_UTIL_SMALL_SHARED_N_WAY_PTR_H
#define CPROVER_UTIL_SMALL_SHARED_N_WAY_PTR_H
 
#include <limits>
#include <tuple>
#include <type_traits>
#include <utility>
 
#include "invariant.h"
 
template <std::size_t I, typename... Ts>
struct get_typet
{
  // NOLINTNEXTLINE(readability/identifiers)
  typedef typename std::tuple_element<I, std::tuple<Ts...>>::type type;
};
 
template <std::size_t N, typename Num>
class small_shared_n_way_pointee_baset;
 
// Struct to hold the static method destruct() to destruct the pointee of a
// small shared n-way pointer.
//
// Note: This functionality should ideally be in a private static method of
// small_shared_n_way_ptrt, but partial template specializations are not allowed
// within other templates, hence it is defined at global scope.
template <std::size_t I, typename pointee_baset, typename... Ts>
struct destructt
{
  static void destruct(pointee_baset *p)
  {
    if(p->template is_derived<I>())
    {
      typedef typename get_typet<I, Ts...>::type pointeet;
      static_assert(
        std::is_base_of<pointee_baset, pointeet>::value,
        "indexed pointee type must be a subclass of the pointee base");
 
      delete static_cast<pointeet *>(p);
    }
    else
    {
      destructt<I - 1, pointee_baset, Ts...>::destruct(p);
    }
  }
};
 
template <typename pointee_baset, typename... Ts>
struct destructt<0, pointee_baset, Ts...>
{
  static void destruct(pointee_baset *p)
  {
    PRECONDITION(p->template is_derived<0>());
 
    typedef typename get_typet<0, Ts...>::type pointeet;
    static_assert(
      std::is_base_of<pointee_baset, pointeet>::value,
      "indexed pointee type must be a subclass of the pointee base");
 
    delete static_cast<pointeet *>(p);
  }
};
 
template <typename... Ts>
class small_shared_n_way_ptrt final
{
public:
  static const std::size_t num_types =
    std::tuple_size<std::tuple<Ts...>>::value;
 
  static_assert(
    num_types >= 2,
    "parameter pack should contain at least two types");
 
  typedef decltype(std::declval<typename get_typet<0, Ts...>::type>()
                     .get_use_count()) use_countt;
 
  typedef small_shared_n_way_pointee_baset<num_types, use_countt> pointee_baset;
 
  small_shared_n_way_ptrt() = default;
 
  template <std::size_t I>
  static small_shared_n_way_ptrt<Ts...>
  create_small_shared_n_way_ptr(typename get_typet<I, Ts...>::type *p)
  {
    PRECONDITION(p != nullptr);
    PRECONDITION(p->get_use_count() == 0);
 
    p->template set_derived<I>();
    p->increment_use_count();
 
    return small_shared_n_way_ptrt<Ts...>(p);
  }
 
  small_shared_n_way_ptrt(const small_shared_n_way_ptrt &rhs) : p(rhs.p)
  {
    PRECONDITION(is_same_type(rhs));
 
    if(p)
    {
      p->increment_use_count();
    }
  }
 
  small_shared_n_way_ptrt(small_shared_n_way_ptrt &&rhs)
  {
    PRECONDITION(is_same_type(rhs));
 
    swap(rhs);
  }
 
  small_shared_n_way_ptrt &operator=(const small_shared_n_way_ptrt &rhs)
  {
    PRECONDITION(is_same_type(rhs));
 
    small_shared_n_way_ptrt copy(rhs);
    swap(copy);
    return *this;
  }
 
  small_shared_n_way_ptrt &operator=(small_shared_n_way_ptrt &&rhs)
  {
    PRECONDITION(is_same_type(rhs));
 
    swap(rhs);
    return *this;
  }
 
  ~small_shared_n_way_ptrt()
  {
    destruct();
  }
 
  void reset()
  {
    destruct();
    p = nullptr;
  }
 
  void swap(small_shared_n_way_ptrt &rhs)
  {
    PRECONDITION(is_same_type(rhs));
 
    std::swap(p, rhs.p);
  }
 
  use_countt use_count() const
  {
    return p ? p->get_use_count() : 0;
  }
 
  template <std::size_t I>
  bool is_derived() const
  {
    return p == nullptr || p->template is_derived<I>();
  }
 
  pointee_baset *get() const
  {
    return p;
  }
 
  template <std::size_t I>
  typename get_typet<I, Ts...>::type *get_derived() const
  {
    PRECONDITION(is_derived<I>());
 
    return static_cast<typename get_typet<I, Ts...>::type *>(p);
  }
 
  bool is_same_type(const small_shared_n_way_ptrt &other) const
  {
    if(p == nullptr || other.p == nullptr)
      return true;
 
    return p->is_same_type(*other.p);
  }
 
  explicit operator bool() const
  {
    return p != nullptr;
  }
 
private:
  template <typename T>
  explicit small_shared_n_way_ptrt(T *p) : p(p)
  {
  }
 
  void destruct()
  {
    if(!p)
    {
      return;
    }
 
    if(p->get_use_count() > 1)
    {
      p->decrement_use_count();
      return;
    }
 
    destructt<num_types - 1, pointee_baset, Ts...>::destruct(p);
  }
 
  pointee_baset *p = nullptr;
};
 
template <std::size_t I, typename U, typename V, typename... Ts>
small_shared_n_way_ptrt<U, V> make_shared_2(Ts &&... ts)
{
  return small_shared_n_way_ptrt<U, V>::template create_small_shared_n_way_ptr<
    I>(new typename get_typet<I, U, V>::type(std::forward<Ts>(ts)...));
}
 
template <std::size_t I, typename U, typename V, typename W, typename... Ts>
small_shared_n_way_ptrt<U, V, W> make_shared_3(Ts &&... ts)
{
  return small_shared_n_way_ptrt<U, V, W>::
    template create_small_shared_n_way_ptr<I>(
      new typename get_typet<I, U, V, W>::type(std::forward<Ts>(ts)...));
}
 
template <typename... Ts>
bool operator==(
  const small_shared_n_way_ptrt<Ts...> &lhs,
  const small_shared_n_way_ptrt<Ts...> &rhs)
{
  return lhs.get() == rhs.get();
}
 
template <typename... Ts>
bool operator!=(
  const small_shared_n_way_ptrt<Ts...> &lhs,
  const small_shared_n_way_ptrt<Ts...> &rhs)
{
  return lhs.get() != rhs.get();
}
 
template <std::size_t N, typename Num>
class small_shared_n_way_pointee_baset
{
public:
  static_assert(std::is_unsigned<Num>::value, "Num must be an unsigned type");
 
  small_shared_n_way_pointee_baset() = default;
 
  // The use count shall be unaffected
  small_shared_n_way_pointee_baset(const small_shared_n_way_pointee_baset &)
  {
  }
 
  // The use count shall be unaffected
  small_shared_n_way_pointee_baset &
  operator=(const small_shared_n_way_pointee_baset &)
  {
    return *this;
  }
 
  Num get_use_count() const
  {
    return use_count & use_count_mask;
  }
 
  void increment_use_count()
  {
    PRECONDITION(get_use_count() < use_count_mask);
 
    ++use_count;
  }
 
  void decrement_use_count()
  {
    PRECONDITION(get_use_count() > 0);
 
    --use_count;
  }
 
  template <std::size_t I>
  void set_derived()
  {
    static_assert(I < N, "type index shall be within bounds");
 
    use_count &= use_count_mask;
    use_count |= I << use_count_bit_width;
  }
 
  template <std::size_t I>
  bool is_derived() const
  {
    static_assert(I < N, "type index shall be within bounds");
 
    return ((use_count & ~use_count_mask) >> use_count_bit_width) == I;
  }
 
  bool is_same_type(const small_shared_n_way_pointee_baset &other) const
  {
    return !((use_count ^ other.use_count) & ~use_count_mask);
  }
 
private:
  Num use_count = 0;
 
  static const int bit_width = std::numeric_limits<Num>::digits;
 
  static constexpr std::size_t num_bits(const std::size_t n)
  {
    return n < 2 ? 1 : 1 + num_bits(n >> 1);
  }
 
  static const std::size_t type_bit_width = num_bits(N);
 
  static const std::size_t use_count_bit_width =
    (std::size_t)bit_width - type_bit_width;
 
  static const Num use_count_mask = ((Num)1 << use_count_bit_width) - 1;
};
 
#endif // CPROVER_UTIL_SMALL_SHARED_N_WAY_PTR_H