Line data    Source code

       1             : // Author(s): Maurice Laveaux
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : 
       9             : #ifndef MCRL2_UTILITIES_DETAIL_FREELIST_H_
      10             : #define MCRL2_UTILITIES_DETAIL_FREELIST_H_
      11             : 
      12             : #include <cassert>
      13             : #include <atomic>
      14             : #include <cstddef>
      15             : #include <cstdint>
      16             : #include <limits>
      17             : #include <iterator>
      18             : 
      19             : namespace mcrl2
      20             : {
      21             : namespace utilities
      22             : {
      23             : namespace detail
      24             : {
      25             : 
      26             : /// \brief This essentially implements the std::forward_list, with the difference that
      27             : ///        it does not own the nodes in the list. It just keeps track of the list
      28             : ///        next pointers. Furthermore this assumes that the objects in the list will not
      29             : ///        be accessed, so it stores the next pointer within the Element.
      30             : template<typename Element>
      31             : class free_list
      32             : {
      33             : public:
      34             : 
      35             :   /// \brief A sentinel value for the next of a slot to indicate that it belonged to the freelist.
      36             :   static constexpr std::uintptr_t FreeListSentinel = std::numeric_limits<std::uintptr_t>::max();
      37             : 
      38             :   /// \brief The nodes of the free list without.
      39             :   union slot
      40             :   {
      41             :   public:
      42     2255463 :     slot() {}
      43      344273 :     ~slot() {}
      44             : 
      45             :     /// \returns The next bucket in the linked list.
      46     1083422 :     slot* next() const noexcept { return m_next; }
      47             : 
      48             :     /// \returns True if and only there is a next bucket in the linked list.
      49     1172539 :     bool has_next() const noexcept { return m_next != nullptr; }
      50             : 
      51             :     /// \brief Set the next pointer to the given next pointer.
      52     1257512 :     void next(slot* next) noexcept { m_next = next; }
      53             : 
      54             :     /// \returns A reference to the key stored in this node.
      55     1172346 :     Element& element() noexcept { return m_element; }
      56             : 
      57             :     /// \returns An implicit conversion to the underlying key.
      58             :     operator Element&() { return m_element; }
      59             : 
      60             :     /// \brief Mark this slot with a special value, destroys the slot.
      61      353479 :     void mark() { m_next = reinterpret_cast<slot*>(FreeListSentinel); }
      62             : 
      63             :     /// \returns True if and only if this slot is marked.
      64     2412106 :     bool is_marked() const noexcept { return m_next == reinterpret_cast<slot*>(FreeListSentinel); }
      65             :   protected:
      66             : 
      67             :     /// \brief Pointer to the next node.
      68             :     slot* m_next = nullptr;
      69             : 
      70             :     /// \brief Store the actual element.
      71             :     Element m_element;
      72             :   };
      73             : 
      74             :   /// \brief Iterator over all keys in a bucket list.
      75             :   template<bool Constant = true>
      76             :   class slot_iterator : std::iterator_traits<Element>
      77             :   {
      78             :     struct Sentinel{};
      79             : 
      80             :     using tag = std::input_iterator_tag;
      81             : 
      82             :     friend class free_list<Element>;
      83             :     using Freelist = typename std::conditional<Constant, const free_list<Element>, free_list<Element>>::type;
      84             :     using reference = typename std::conditional<Constant, const Element&, Element&>::type;
      85             :     using slot_pointer = typename std::conditional<Constant, const slot*, slot*>::type;
      86             : 
      87             :   public:
      88             :     /// \brief A end of the iterator sentinel.
      89             :     static constexpr Sentinel EndIterator{};
      90             : 
      91       12085 :     slot_iterator(slot_pointer slot)
      92       12085 :       : m_slot(slot)
      93       12085 :     {}
      94             : 
      95             :     slot_iterator(Freelist& list)
      96             :       : m_slot(list.head()->next())
      97             :     {}
      98             : 
      99      362811 :     slot_iterator()
     100      362811 :       : m_slot(nullptr)
     101      362811 :     {}
     102             : 
     103      353479 :     slot_iterator& operator++()
     104             :     {
     105      353479 :       m_slot = m_slot->next();
     106      353479 :       return *this;
     107             :     }
     108             : 
     109             :     template<bool Constant_ = Constant>
     110             :     typename std::enable_if<!Constant_, reference>::type operator*()
     111             :     {
     112             :       return m_slot->element();
     113             :     }
     114             : 
     115             :     template<bool Constant_ = Constant>
     116             :     typename std::enable_if<Constant_, reference>::type operator*() const
     117             :     {
     118             :       return m_slot->element();
     119             :     }
     120             : 
     121      362811 :     bool operator != (const slot_iterator& it) const noexcept
     122             :     {
     123      362811 :       return m_slot != it.m_slot;
     124             :     }
     125             : 
     126             :     bool operator != (Sentinel) const noexcept
     127             :     {
     128             :       return m_slot != nullptr;
     129             :     }
     130             : 
     131      353895 :     slot_pointer get_slot()
     132             :     {
     133      353895 :       return m_slot;
     134             :     }
     135             : 
     136             :   private:
     137             :     slot_pointer m_slot;
     138             :   };
     139             : 
     140             : public:
     141             :   using Freelist = free_list<Element>;
     142             :   using iterator = slot_iterator<false>;
     143             :   using const_iterator = slot_iterator<true>;
     144             : 
     145        1623 :   free_list() {}
     146             : 
     147             :   /// \returns An iterator over the keys of this bucket and successor buckets.
     148       11877 :   iterator begin() { return iterator(head().next()); }
     149      362811 :   iterator end() { return iterator(); }
     150             : 
     151             :   /// \return An iterator pointing to the before the head of the list.
     152         208 :   iterator before_begin() { return iterator(&head()); }
     153             : 
     154             :   /// \returns A const iterator over the keys of this bucket and successor buckets.
     155             :   const_iterator begin() const { return const_iterator(*this); }
     156             :   const_iterator end() const { return const_iterator(); }
     157             : 
     158             :   /// \return A const iterator pointing to the before the head of the list.
     159             :   const_iterator before_begin() const { return const_iterator(&m_head); }
     160             : 
     161             :   /// \brief Removes the element after the given iterator from the list. The returned iterator
     162             :   iterator erase_after(iterator it)
     163             :   {
     164             :     slot* current_node = it.get_node();
     165             :     assert(current_node->next() != nullptr); // Cannot erase after the last node.
     166             : 
     167             :     // Keep track of the node that we should remove.
     168             :     slot* erased_node = current_node->next();
     169             :     slot* next_node = erased_node->next();
     170             : 
     171             :     // Update the next pointer of the current node.
     172             :     current_node->next(next_node);
     173             :     return iterator(next_node);
     174             :   }
     175             : 
     176             :   /// \brief Empties the bucket list.
     177             :   void clear() { head().next(nullptr); }
     178             : 
     179             :   /// \returns True if the given pointer is already in the freelist.
     180             :   bool contains(Element* pointer)
     181             :   {
     182             :     union slot* slot = reinterpret_cast<union slot*>(pointer);
     183             :     for (auto it = begin(); it != end(); ++it)
     184             :     {
     185             :       if (slot == *it)
     186             :       {
     187             :         return true;
     188             :       }
     189             :     }
     190             : 
     191             :     return false;
     192             :   }
     193             : 
     194             :   /// \returns The length of the freelist.
     195             :   std::size_t count()
     196             :   {
     197             :     std::size_t length = 0;
     198             :     for (auto it = begin(); it != end(); ++it)
     199             :     {
     200             :       ++length;
     201             :     }
     202             :     return length;
     203             :   }
     204             : 
     205             :   /// \brief Mark all elements in this list with a special value, destroys the list.
     206        9332 :   void destructive_mark()
     207             :   {
     208      362811 :     for (auto it = begin(); it != end();)
     209             :     {
     210      353479 :       slot* current_slot = it.get_slot();
     211      353479 :       ++it;
     212      353479 :       current_slot->mark();
     213             :     }
     214             : 
     215        9332 :     head().next(nullptr);
     216        9332 :   }
     217             : 
     218             :   /// \returns True if and only if this list is empty.
     219     1172539 :   bool empty() const noexcept
     220             :   {
     221     1172539 :     return !head().has_next();
     222             :   }
     223             : 
     224             :   /// \brief Inserts an element at the position after the iterator.
     225             :   iterator insert_after(iterator it, slot& element)
     226             :   {
     227             :     slot& current = *it.get_slot();
     228             :     element.next(current.next());
     229             :     current.next(&element);
     230             :     return iterator(&element);
     231             :   }
     232             : 
     233             :   /// \brief Removes the head of the list and returns a reference to this head slot.
     234       62720 :   Element& pop_front()
     235             :   {
     236       62720 :     slot* element = head().next();
     237       62720 :     head().next(element->next());
     238       62720 :     return element->element();
     239             :   }
     240             : 
     241             :   /// \brief Puts the given node before the head of the list.
     242      592626 :   void push_front(slot& slot)
     243             :   {
     244      592626 :     slot.next(head().next());
     245      592626 :     head().next(&slot);
     246      592626 :   }
     247             : 
     248             :   /// \brief Erases elements in the range (position, last], constant complexity since no destructors
     249             :   ///        will be called.
     250         208 :   void erase_after(iterator position, iterator last)
     251             :   {
     252         208 :     position.get_slot()->next(last.get_slot());
     253         208 :   }
     254             : 
     255             : private:
     256             :   /// \brief Provides access to the head as if it was an actual slot.
     257     1332109 :   slot& head() noexcept { return m_head; }
     258     1172539 :   const slot& head() const noexcept { return m_head; }
     259             : 
     260             :   /// \brief The first node in the bucket list.
     261             :   /// \details This wastes sizeof(Element) space, because slot can store both an Element or a next pointer.
     262             :   slot m_head;
     263             : };
     264             : 
     265             : } // namespace detail
     266             : } // namespace utilities
     267             : } // namespace mcrl2
     268             : 
     269             : #endif // MCRL2_UTILITIES_DETAIL_FREELIST_H_