LCOV - code coverage report
Current view: top level - utilities/include/mcrl2/utilities/detail - bucket_list.h (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 79 80 98.8 %
Date: 2020-02-13 00:44:47 Functions: 1036 1328 78.0 %
Legend: Lines: hit not hit

          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_BUCKETLIST_H_
      10             : #define MCRL2_UTILITIES_DETAIL_BUCKETLIST_H_
      11             : 
      12             : #include <cassert>
      13             : #include <atomic>
      14             : #include <cstddef>
      15             : #include <iterator>
      16             : #include <memory>
      17             : 
      18             : namespace mcrl2
      19             : {
      20             : namespace utilities
      21             : {
      22             : namespace detail
      23             : {
      24             : 
      25             : struct Sentinel{};
      26             : 
      27             : /// \brief A end of the iterator sentinel.
      28             : static constexpr Sentinel EndIterator = {};
      29             : 
      30             : /// \brief A compile time check for allocate_args in the given allocator, calls allocate(1) otherwise.
      31             : template<typename Allocator, typename ...Args>
      32         182 : inline auto allocate(Allocator& allocator, const Args&... args) -> decltype(allocator.allocate_args(args...))
      33             : {
      34         182 :   return allocator.allocate_args(args...);
      35             : }
      36             : 
      37             : template<typename Allocator, typename ...Args>
      38      853002 : inline auto allocate(Allocator& allocator, const Args&...) -> decltype(allocator.allocate(1))
      39             : {
      40      853002 :   return allocator.allocate(1);
      41             : }
      42             : 
      43             : /// \brief This essentially implements the std::forward_list, with the difference that
      44             : ///        it does not own the nodes in the list. It just keeps track of the list
      45             : ///        next pointers.
      46             : template<typename Key, typename Allocator>
      47    23467008 : class bucket_list
      48             : {
      49             : public:
      50             : 
      51             :   /// \brief The nodes of the bucket list without carrying any additional informations.
      52             :   ///        Used to make no different between the head and the tail of the list.
      53    24320192 :   class node_base
      54             :   {
      55             :   public:
      56             :     /// \returns The next bucket in the linked list.
      57   203938574 :     node_base* next() const noexcept { return m_next; }
      58             : 
      59             :     /// \returns True if and only there is a next bucket in the linked list.
      60      567376 :     bool has_next() const noexcept { return m_next != nullptr; }
      61             : 
      62             :     /// \brief Set the next pointer to the given next pointer.
      63     2609353 :     void set_next(node_base* next) noexcept { m_next = next; }
      64             :   protected:
      65             : 
      66             :     /// \brief Pointer to the next node.
      67             :     node_base* m_next = nullptr;
      68             :   };
      69             : 
      70             :   /// \brief The nodes of the bucket list.
      71        2064 :   class node final : public node_base
      72             :   {
      73             :   public:
      74             : 
      75             :     /// \brief Constructs a key by using the given arguments.
      76             :     template<typename ...Args>
      77      853184 :     explicit node(Args&&... args)
      78      853184 :       : m_key(std::forward<Args>(args)...)
      79      853184 :     {}
      80             : 
      81             :     /// \returns A reference to the key stored in this node.
      82   356016510 :     Key& key() noexcept { return m_key; }
      83             :     const Key& key() const noexcept { return m_key; }
      84             : 
      85             :     /// \returns An implicit conversion to the underlying key.
      86           0 :     operator Key&() { return m_key; }
      87             :   private:
      88             :     /// \brief Store the actual key.
      89             :     Key m_key;
      90             :   };
      91             : 
      92             :   /// \brief Iterator over all keys in a bucket list.
      93             :   template<bool Constant = true>
      94             :   class key_iterator
      95             :   {
      96             :     friend class bucket_list;
      97             : 
      98             :   public:
      99             :     using value_type = typename std::conditional<Constant, const Key, Key>::type;
     100             :     using reference = typename std::conditional<Constant, const Key&, Key&>::type;
     101             :     using pointer = typename std::conditional<Constant, const Key*, Key*>::type;
     102             :     using difference_type = std::ptrdiff_t;
     103             :     using iterator_category = std::forward_iterator_tag;
     104             : 
     105             :     /// Default constructor.
     106   834239203 :     key_iterator() {}
     107             : 
     108             :     /// \brief Implicit conversion to const_iterator.
     109     2079640 :     operator key_iterator<true>() const
     110             :     {
     111     2079640 :       return key_iterator<true>(m_current_node);
     112             :     }
     113             : 
     114    38972233 :     key_iterator& operator++()
     115             :     {
     116    38972233 :       m_current_node = reinterpret_cast<node*>(m_current_node->next());
     117    38972233 :       return *this;
     118             :     }
     119             : 
     120             :     key_iterator operator++(int)
     121             :     {
     122             :       key_iterator copy(*this);
     123             :       ++(*this);
     124             :       return copy;
     125             :     }
     126             : 
     127   355836018 :     reference operator*() const
     128             :     {
     129   355836018 :       return m_current_node->key();
     130             :     }
     131             : 
     132             :     pointer operator->() const
     133             :     {
     134             :       return &m_current_node->key();
     135             :     }
     136             : 
     137             :     bool operator== (const key_iterator& it) const noexcept
     138             :     {
     139             :       return !(*this != it);
     140             :     }
     141             : 
     142   357497138 :     bool operator!= (const key_iterator& it) const noexcept
     143             :     {
     144   357497138 :       return m_current_node != it.m_current_node;
     145             :     }
     146             : 
     147             :     bool operator== (Sentinel) const noexcept
     148             :     {
     149             :       return !(*this != Sentinel());
     150             :     }
     151             : 
     152     4123357 :     bool operator!= (Sentinel) const noexcept
     153             :     {
     154     4123357 :       return m_current_node != nullptr;
     155             :     }
     156             : 
     157             :   private:
     158   328756102 :     explicit key_iterator(node_base* current)
     159   328756102 :       : m_current_node(reinterpret_cast<node*>(current))
     160   328756102 :     {}
     161             : 
     162      722493 :     node* get_node() noexcept
     163             :     {
     164      722493 :       return m_current_node;
     165             :     }
     166             : 
     167             :     const node* get_node() const noexcept
     168             :     {
     169             :       return m_current_node;
     170             :     }
     171             : 
     172             :     node* m_current_node = nullptr;
     173             :   };
     174             : 
     175             : public:
     176             :   using Bucket = bucket_list<Key, Allocator>;
     177             :   using iterator = key_iterator<false>;
     178             :   using const_iterator = key_iterator<true>;
     179             : 
     180             :   /// Rebind the passed to allocator to a bucket list node allocator.
     181             :   using NodeAllocator = typename Allocator::template rebind<typename Bucket::node>::other;
     182             : 
     183             :   /// \returns The first element.
     184      180492 :   Key& front() { return reinterpret_cast<node&>(*m_head.next()).key(); }
     185             :   const Key& front() const { return reinterpret_cast<const node&>(*m_head.next()).key(); }
     186             : 
     187             :   /// \returns An iterator over the keys of this bucket and successor buckets.
     188     1386687 :   iterator begin() { return iterator(m_head.next()); }
     189      298284 :   iterator end() { return iterator(); }
     190             : 
     191             :   /// \return An iterator pointing to the before the head of the list.
     192     1214718 :   iterator before_begin() { return iterator(&m_head); }
     193             : 
     194             :   /// \returns A const iterator over the keys of this bucket and successor buckets.
     195   162031386 :   const_iterator begin() const { return const_iterator(m_head.next()); }
     196   196427495 :   const_iterator end() const { return const_iterator(); }
     197             : 
     198             :   const_iterator cbegin() const { return const_iterator(m_head.next()); }
     199             :   const_iterator cend() const { return const_iterator(); }
     200             : 
     201             :   /// \return A const iterator pointing to the before the head of the list.
     202   162031386 :   const_iterator before_begin() const { return const_iterator(const_cast<node_base*>(&m_head)); }
     203             : 
     204             :   /// \returns True iff this bucket has no elements.
     205      567376 :   bool empty() const { return !m_head.has_next(); }
     206             : 
     207             :   /// \brief Empties the bucket list.
     208             :   void clear(NodeAllocator& allocator)
     209             :   {
     210             :     while(!empty())
     211             :     {
     212             :       erase_after(before_begin(), allocator);
     213             :     }
     214             :   }
     215             : 
     216             :   /// \brief Constructs an element using the allocator with the given arguments and insert it in the front.
     217             :   template<typename ...Args>
     218      853184 :   void emplace_front(NodeAllocator& allocator, Args&& ...args)
     219             :   {
     220             :     // Allocate a new node.
     221      853184 :     node* new_node = allocate(allocator, std::forward<Args>(args)...);
     222      853184 :     std::allocator_traits<NodeAllocator>::construct(allocator, new_node, std::forward<Args>(args)...);
     223             : 
     224             :     // Ensure that the previous front is set behind this node.
     225      853184 :     new_node->set_next(m_head.next());
     226             : 
     227             :     // Change the head to the newly allocated node.
     228      853184 :     m_head.set_next(new_node);
     229      853184 :   }
     230             : 
     231             :   /// \brief Removes the element after the given iterator from the list. The returned iterator
     232       12285 :   iterator erase_after(NodeAllocator& allocator, const_iterator it)
     233             :   {
     234       12285 :     node* current_node = const_cast<node*>(it.get_node());
     235       12285 :     assert(current_node->next() != nullptr); // Cannot erase after the last node.
     236             : 
     237             :     // Keep track of the node that we should remove.
     238       12285 :     node* erased_node = reinterpret_cast<node*>(current_node->next());
     239       12285 :     node_base* next_node = erased_node->next();
     240             : 
     241             :     // Update the next pointer of the current node.
     242       12285 :     current_node->set_next(next_node);
     243             : 
     244             :     // Clean up the old node.
     245       12285 :     std::allocator_traits<NodeAllocator>::destroy(allocator, erased_node);
     246       12285 :     std::allocator_traits<NodeAllocator>::deallocate(allocator, erased_node, 1);
     247             : 
     248       12285 :     return iterator(next_node);
     249             :   }
     250             : 
     251             :   /// \brief Moves the elements from other into this bucket after the given position.
     252      180492 :   void splice_after(const_iterator pos, bucket_list& other)
     253             :   {
     254      180492 :     if (!other.empty())
     255             :     {
     256      116753 :       assert(begin() != other.begin());
     257      116753 :       node* current_node = const_cast<node*>(pos.get_node());
     258             : 
     259             :       // Increment the position now as we are going to change the current_node.
     260      116753 :       ++pos;
     261             : 
     262             :       // Sets the current position to be followed by the other bucket list.
     263      116753 :       current_node->set_next(other.m_head.next());
     264             : 
     265      116753 :       node* after_pos_node = const_cast<node*>(pos.get_node());
     266      116753 :       if (after_pos_node != nullptr)
     267             :       {
     268             :         // Find the last node of the other list.
     269      115718 :         iterator before_end;
     270      294266 :         for (iterator it = other.begin(); it != other.end(); ++it)
     271             :         {
     272      178548 :           before_end = it;
     273             :         }
     274             : 
     275             :         // Set the last element of other to the position after pos.
     276      115718 :         node* last = before_end.get_node();
     277      115718 :         last->set_next(after_pos_node);
     278             :       }
     279             : 
     280             :       // Make the other bucket empty, all elements belong to this bucket now.
     281      116753 :       other.m_head.set_next(nullptr);
     282             :     }
     283      180492 :   }
     284             : 
     285             :   /// \brief Moves the first node from the given bucket into this bucket after the given position.
     286             :   /// \details This is a non-standard addition to ensure efficient splicing (instead of splice_after(pos, other, other.begin(), ++other.begin()).
     287      180492 :   void splice_front(const_iterator pos, bucket_list& other)
     288             :   {
     289      180492 :     if (!other.empty())
     290             :     {
     291             :       // Sets the current position to be followed by the other bucket list.
     292      180492 :       node* current_node = const_cast<node*>(pos.get_node());
     293      180492 :       node_base* next_node = current_node->next();
     294             : 
     295             :       // Make the other head node the start of our bucket after pos.
     296      180492 :       node_base* head_node = other.begin().get_node();
     297      180492 :       current_node->set_next(head_node);
     298             : 
     299             :       // Make the next position the position after the head, but keep track of the current next node.
     300      180492 :       node_base* next_head_node = head_node->next();
     301      180492 :       head_node->set_next(next_node);
     302             : 
     303             :       // Make the other head point to the next element.
     304      180492 :       other.m_head.set_next(next_head_node);
     305             :     }
     306      180492 :   }
     307             : 
     308             : private:
     309             : 
     310             :   /// \returns True iff this bucket already contains the given node.
     311             :   bool contains(node* node)
     312             :   {
     313             :     node_base* element = &m_head;
     314             :     while(element->has_next())
     315             :     {
     316             :       if (node == element->next())
     317             :       {
     318             :         return true;
     319             :       }
     320             : 
     321             :       element = element->next();
     322             :     }
     323             : 
     324             :     return false;
     325             :   }
     326             : 
     327             :   /// \brief The first node in the bucket list.
     328             :   node_base m_head;
     329             : };
     330             : 
     331             : } // namespace detail
     332             : } // namespace utilities
     333             : } // namespace mcrl2
     334             : 
     335             : #endif // MCRL2_UTILITIES_DETAIL_BUCKETLIST_H_

Generated by: LCOV version 1.13