bucket_list.h

Go to the documentation of this file.

// Author(s): Maurice Laveaux
// Copyright: see the accompanying file COPYING or copy at
// https://github.com/mCRL2org/mCRL2/blob/master/COPYING
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
 
#ifndef MCRL2_UTILITIES_DETAIL_BUCKETLIST_H_
#define MCRL2_UTILITIES_DETAIL_BUCKETLIST_H_
 
#include <cassert>
#include <atomic>
#include <cstddef>
#include <iterator>
#include <memory>
 
namespace mcrl2
{
namespace utilities
{
namespace detail
{
 
struct Sentinel{};
 
static constexpr Sentinel EndIterator = {};
 
template<typename Allocator, typename ...Args>
inline auto allocate(Allocator& allocator, const Args&... args) -> decltype(allocator.allocate_args(args...))
{
  return allocator.allocate_args(args...);
}
 
template<typename Allocator, typename ...Args>
inline auto allocate(Allocator& allocator, const Args&...) -> decltype(allocator.allocate(1))
{
  return allocator.allocate(1);
}
 
template<typename Key, typename Allocator>
class bucket_list
{
public:
 
  class node_base
  {
  public:
    node_base() = default;
    node_base(node_base&& other) noexcept
    {
      m_next.store(other.m_next.load());
      other.m_next = nullptr;
    }
 
    node_base* next() const noexcept { return m_next.load(std::memory_order_acquire); }
 
    bool has_next() const noexcept { return m_next.load(std::memory_order_relaxed) != nullptr; }
 
    void set_next(node_base* next) noexcept { m_next.store(next, std::memory_order_relaxed); }
 
    bool exchange(node_base*& expected, node_base* value) { return m_next.compare_exchange_weak(expected, value, std::memory_order_acq_rel); }
  protected:
 
    std::atomic<node_base*> m_next = nullptr;
  };
 
  class node final : public node_base
  {
  public:
 
    template<typename ...Args>
    explicit node(Args&&... args)
      : m_key(std::forward<Args>(args)...)
    {}
 
    Key& key() noexcept { return m_key; }
    const Key& key() const noexcept { return m_key; }
 
    operator Key&() { return m_key; }
  private:
    Key m_key;
  };
 
  template<bool Constant = true>
  class key_iterator
  {
    friend class bucket_list;
 
  public:
    using value_type = typename std::conditional<Constant, const Key, Key>::type;
    using reference = typename std::conditional<Constant, const Key&, Key&>::type;
    using pointer = typename std::conditional<Constant, const Key*, Key*>::type;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;
 
    key_iterator() {}
 
    operator key_iterator<true>() const
    {
      return key_iterator<true>(m_current_node);
    }
 
    key_iterator& operator++()
    {
      m_current_node = reinterpret_cast<node*>(m_current_node->next());
      return *this;
    }
 
    reference operator*() const
    {
      return m_current_node->key();
    }
 
    pointer operator->() const
    {
      return &m_current_node->key();
    }
 
    bool operator== (const key_iterator& it) const noexcept
    {
      return !(*this != it);
    }
 
    bool operator!= (const key_iterator& it) const noexcept
    {
      return m_current_node != it.m_current_node;
    }
 
    bool operator== (Sentinel) const noexcept
    {
      return !(*this != Sentinel());
    }
 
    bool operator!= (Sentinel) const noexcept
    {
      return m_current_node != nullptr;
    }
 
  private:
    explicit key_iterator(node_base* current)
      : m_current_node(reinterpret_cast<node*>(current))
    {}
 
    node* get_node() noexcept
    {
      return m_current_node;
    }
 
    const node* get_node() const noexcept
    {
      return m_current_node;
    }
 
    node* m_current_node = nullptr;
  };
 
public:
  using Bucket = bucket_list<Key, Allocator>;
  using iterator = key_iterator<false>;
  using const_iterator = key_iterator<true>;
 
  using NodeAllocator = typename std::allocator_traits<Allocator>::template rebind_alloc<Bucket::node>;
 
  Key& front() { return reinterpret_cast<node&>(*m_head.next()).key(); }
  const Key& front() const { return reinterpret_cast<const node&>(*m_head.next()).key(); }
 
  iterator begin() { return iterator(m_head.next()); }
  iterator end() { return iterator(); }
 
  iterator before_begin() { return iterator(&m_head); }
 
  const_iterator begin() const { return const_iterator(m_head.next()); }
  const_iterator end() const { return const_iterator(); }
 
  const_iterator cbegin() const { return const_iterator(m_head.next()); }
  const_iterator cend() const { return const_iterator(); }
 
  const_iterator before_begin() const { return const_iterator(const_cast<node_base*>(&m_head)); }
 
  bool empty() const { return !m_head.has_next(); }
 
  void clear(NodeAllocator& allocator)
  {
    while(!empty())
    {
      erase_after(before_begin(), allocator);
    }
  }
 
  template<typename ...Args>
  void emplace_front(NodeAllocator& allocator, Args&& ...args)
  {
    // Allocate a new node.
    node* new_node = allocate(allocator, std::forward<Args>(args)...);
    std::allocator_traits<NodeAllocator>::construct(allocator, new_node, std::forward<Args>(args)...);
 
    // Ensure that the previous front is set behind this node.
    new_node->set_next(m_head.next());
 
    // Change the head to the newly allocated node.
    m_head.set_next(new_node);
  }
 
  template<typename ...Args,
           typename Equals>
  std::pair<iterator, bool> emplace_front_unique(NodeAllocator& allocator, const Equals& equals, Args&& ...args)
  {
    // Allocate a new node.
    node* new_node = allocate(allocator, std::forward<Args>(args)...);
    std::allocator_traits<NodeAllocator>::construct(allocator, new_node, std::forward<Args>(args)...);
 
    // This was the first and last when we started the operation.
    node_base* old_head = m_head.next();
    iterator old_end;
 
    // Change the head to the newly allocated node.
    do
    {
      // Ensure that the previous front is set behind this node.
      new_node->set_next(old_head);
 
      // Check whether the new node is not already contained in the bucket list.
      for (auto it = iterator(old_head); it != old_end; ++it)
      {
        if (equals(*it, std::forward<Args>(args)...))
        {
          // Clean up new node and leave bucket as is.          
          std::allocator_traits<NodeAllocator>::destroy(allocator, new_node);
          std::allocator_traits<NodeAllocator>::deallocate(allocator, new_node, 1);
          return std::make_pair(it, false);
        }
      }
 
      // Next iteration we only have to look at newly inserted nodes.
      old_end = iterator(old_head);
    }
    while(!m_head.exchange(old_head, new_node));
 
    return std::make_pair(iterator(new_node), true);
  }
 
  iterator erase_after(NodeAllocator& allocator, const_iterator it)
  {
    node* current_node = const_cast<node*>(it.get_node());
    assert(current_node->next() != nullptr); // Cannot erase after the last node.
 
    // Keep track of the node that we should remove.
    node* erased_node = reinterpret_cast<node*>(current_node->next());
    node_base* next_node = erased_node->next();
 
    // Update the next pointer of the current node.
    current_node->set_next(next_node);
 
    // Clean up the old node.
    std::allocator_traits<NodeAllocator>::destroy(allocator, erased_node);
    std::allocator_traits<NodeAllocator>::deallocate(allocator, erased_node, 1);
 
    return iterator(next_node);
  }
 
  void splice_after(const_iterator pos, bucket_list& other)
  {
    if (!other.empty())
    {
      assert(begin() != other.begin());
      node* current_node = const_cast<node*>(pos.get_node());
 
      // Increment the position now as we are going to change the current_node.
      ++pos;
 
      // Sets the current position to be followed by the other bucket list.
      current_node->set_next(other.m_head.next());
 
      node* after_pos_node = const_cast<node*>(pos.get_node());
      if (after_pos_node != nullptr)
      {
        // Find the last node of the other list.
        iterator before_end;
        for (iterator it = other.begin(); it != other.end(); ++it)
        {
          before_end = it;
        }
 
        // Set the last element of other to the position after pos.
        node* last = before_end.get_node();
        last->set_next(after_pos_node);
      }
 
      // Make the other bucket empty, all elements belong to this bucket now.
      other.m_head.set_next(nullptr);
    }
  }
 
  void splice_front(const_iterator pos, bucket_list& other)
  {
    if (!other.empty())
    {
      // Sets the current position to be followed by the other bucket list.
      node* current_node = const_cast<node*>(pos.get_node());
      node_base* next_node = current_node->next();
 
      // Make the other head node the start of our bucket after pos.
      node_base* head_node = other.begin().get_node();
      current_node->set_next(head_node);
 
      // Make the next position the position after the head, but keep track of the current next node.
      node_base* next_head_node = head_node->next();
      head_node->set_next(next_node);
 
      // Make the other head point to the next element.
      other.m_head.set_next(next_head_node);
    }
  }
 
private:
 
  bool contains(node* node)
  {
    node_base* element = &m_head;
    while(element->has_next())
    {
      if (node == element->next())
      {
        return true;
      }
 
      element = element->next();
    }
 
    return false;
  }
 
  node_base m_head;
};
 
} // namespace detail
} // namespace utilities
} // namespace mcrl2
 
#endif // MCRL2_UTILITIES_DETAIL_BUCKETLIST_H_