free_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_FREELIST_H_
#define MCRL2_UTILITIES_DETAIL_FREELIST_H_
 
#include <cassert>
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <iterator>
 
namespace mcrl2
{
namespace utilities
{
namespace detail
{
 
template<typename Element>
class free_list
{
public:
 
  static constexpr std::uintptr_t FreeListSentinel = std::numeric_limits<std::uintptr_t>::max();
 
  union slot
  {
  public:
    slot() {}
    ~slot() {}
 
    slot* next() const noexcept { return m_next; }
 
    bool has_next() const noexcept { return m_next != nullptr; }
 
    void next(slot* next) noexcept { m_next = next; }
 
    Element& element() noexcept { return m_element; }
 
    operator Element&() { return m_element; }
 
    void mark() { m_next = reinterpret_cast<slot*>(FreeListSentinel); }
 
    bool is_marked() const noexcept { return m_next == reinterpret_cast<slot*>(FreeListSentinel); }
  protected:
 
    slot* m_next = nullptr;
 
    Element m_element;
  };
 
  template<bool Constant = true>
  class slot_iterator : std::iterator_traits<Element>
  {
    struct Sentinel{};
 
    using tag = std::input_iterator_tag;
 
    friend class free_list<Element>;
    using Freelist = typename std::conditional<Constant, const free_list<Element>, free_list<Element>>::type;
    using reference = typename std::conditional<Constant, const Element&, Element&>::type;
    using slot_pointer = typename std::conditional<Constant, const slot*, slot*>::type;
 
  public:
    static constexpr Sentinel EndIterator{};
 
    slot_iterator(slot_pointer slot)
      : m_slot(slot)
    {}
 
    slot_iterator(Freelist& list)
      : m_slot(list.head()->next())
    {}
 
    slot_iterator()
      : m_slot(nullptr)
    {}
 
    slot_iterator& operator++()
    {
      m_slot = m_slot->next();
      return *this;
    }
 
    template<bool Constant_ = Constant>
    typename std::enable_if<!Constant_, reference>::type operator*()
    {
      return m_slot->element();
    }
 
    template<bool Constant_ = Constant>
    typename std::enable_if<Constant_, reference>::type operator*() const
    {
      return m_slot->element();
    }
 
    bool operator != (const slot_iterator& it) const noexcept
    {
      return m_slot != it.m_slot;
    }
 
    bool operator != (Sentinel) const noexcept
    {
      return m_slot != nullptr;
    }
 
    slot_pointer get_slot()
    {
      return m_slot;
    }
 
  private:
    slot_pointer m_slot;
  };
 
public:
  using Freelist = free_list<Element>;
  using iterator = slot_iterator<false>;
  using const_iterator = slot_iterator<true>;
 
  free_list() {}
 
  iterator begin() { return iterator(head().next()); }
  iterator end() { return iterator(); }
 
  iterator before_begin() { return iterator(&head()); }
 
  const_iterator begin() const { return const_iterator(*this); }
  const_iterator end() const { return const_iterator(); }
 
  const_iterator before_begin() const { return const_iterator(&m_head); }
 
  iterator erase_after(iterator it)
  {
    slot* current_node = it.get_node();
    assert(current_node->next() != nullptr); // Cannot erase after the last node.
 
    // Keep track of the node that we should remove.
    slot* erased_node = current_node->next();
    slot* next_node = erased_node->next();
 
    // Update the next pointer of the current node.
    current_node->next(next_node);
    return iterator(next_node);
  }
 
  void clear() { head().next(nullptr); }
 
  bool contains(Element* pointer)
  {
    union slot* slot = reinterpret_cast<union slot*>(pointer);
    for (auto it = begin(); it != end(); ++it)
    {
      if (slot == *it)
      {
        return true;
      }
    }
 
    return false;
  }
 
  std::size_t count()
  {
    std::size_t length = 0;
    for (auto it = begin(); it != end(); ++it)
    {
      ++length;
    }
    return length;
  }
 
  void destructive_mark()
  {
    for (auto it = begin(); it != end();)
    {
      slot* current_slot = it.get_slot();
      ++it;
      current_slot->mark();
    }
 
    head().next(nullptr);
  }
 
  bool empty() const noexcept
  {
    return !head().has_next();
  }
 
  iterator insert_after(iterator it, slot& element)
  {
    slot& current = *it.get_slot();
    element.next(current.next());
    current.next(&element);
    return iterator(&element);
  }
 
  Element& pop_front()
  {
    slot* element = head().next();
    head().next(element->next());
    return element->element();
  }
 
  void push_front(slot& slot)
  {
    slot.next(head().next());
    head().next(&slot);
  }
 
  void erase_after(iterator position, iterator last)
  {
    position.get_slot()->next(last.get_slot());
  }
 
private:
  slot& head() noexcept { return m_head; }
  const slot& head() const noexcept { return m_head; }
 
  slot m_head;
};
 
} // namespace detail
} // namespace utilities
} // namespace mcrl2
 
#endif // MCRL2_UTILITIES_DETAIL_FREELIST_H_