A dummy Decision Diagram with reference counting using shared_ptr and weak_ptr

dd.cc

#include <cassert>
#include <map>
#include <memory>          // shared_ptr, weak_ptr
#include <unordered_map>
#include <utility>         // pair

/*----------------------------------------------------------------------------*/

class Node
{
public:

  using Successors = std::map<int, std::shared_ptr<const Node>>;
  using const_iterator = Successors::const_iterator;

public:

  Node(const Node&) = default;
  Node& operator=(const Node&) = default;
  Node(Node&&) = default;
  Node& operator=(Node&&) = default;

  Node(int variable)
    : Node{variable, {}}
  {}

  Node(int variable, Successors successors)
    : m_variable{variable}
    , m_successors{std::move(successors)}
  {}

  int
  variable()
  const noexcept
  {
    return m_variable;
  }

  const_iterator
  begin()
  const noexcept
  {
    return m_successors.cbegin();
  }

  const_iterator
  end()
  const noexcept
  {
    return m_successors.cend();
  }

  std::shared_ptr<const Node>
  operator[](int valuation)
  const noexcept
  {
    return m_successors.at(valuation);
  }

  friend
  bool
  operator==(const Node& lhs, const Node& rhs)
  noexcept
  {
    return lhs.m_variable == rhs.m_variable
       and lhs.m_successors == rhs.m_successors;
  }

private:

  int m_variable;
  Successors m_successors;
};

/*----------------------------------------------------------------------------*/

namespace std {

template <>
struct hash<Node>
{
  /// @todo A real hash function
  std::size_t
  operator()(const Node& node)
  const noexcept
  {
    auto h = std::hash<int>{}(node.variable());
    for (const auto& arc : node)
    {
        h ^= 31 * std::hash<int>{}(arc.first);
        h ^= 27 * std::hash<Node>{}(*arc.second);
    }
    return h;
  }
};

} // namespace std

/*----------------------------------------------------------------------------*/

using set_type = std::unordered_map<Node, std::weak_ptr<const Node>>;

/*----------------------------------------------------------------------------*/

std::shared_ptr<const Node>
insert(set_type& set, Node&& node)
{
  const auto search = set.find(node);
  if (search == set.end())
  {
    static const auto deleter = [&](const auto* ptr)
                                {
                                  assert(set.find(*ptr) != set.end());
                                  set.erase(*ptr);
                                };
    // First insert the node to have its final address in memory
    auto insertion = set.emplace(std::move(node), std::weak_ptr<const Node>{});
    // Then create a shared pointer from this memory location, in assocation
    // with a "finalizer"
    const auto sp = std::shared_ptr<const Node>( &insertion.first->first
                                               , deleter);
    // Finally, update the weak pointer to keep the reference counter
    insertion.first->second = sp;
    return sp;
  }
  else
  {
    return search->second.lock();
  }
}

/*----------------------------------------------------------------------------*/

int
main()
{
  auto set = set_type{};

  assert(set.size() == 0);
  {
    auto t0  = insert(set, Node{0});
    auto t0_ = insert(set, Node{0});
    assert(set.size() == 1);
    assert(*t0 == *t0_);

    auto t1  = insert(set, Node{1});
    auto t1_ = insert(set, Node{1});
    assert(set.size() == 2);
    assert(*t1 == *t1_);

    {
      auto n2  = insert(set, Node{2, {{0, t0}, {1, t1}}});
      auto n2_ = insert(set, Node{2, {{0, t0}, {1, t1}}});
      assert(set.size() == 3);
      assert(*n2 == *n2_);
      assert(*(*n2)[0] == *t0);
      assert(*(*n2)[1] == *t1);
    }
    assert(set.size() == 2);
  }
  assert(set.size() == 0);
}

/*----------------------------------------------------------------------------*/