linked-elements.hpp

Go to the documentation of this file.

/*
  LINKED-ELEMENTS.hpp  -  configurable intrusive single linked list template

   Copyright (C)
     2012,            Hermann Vosseler <Ichthyostega@web.de>

  **Lumiera** is free software; you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by the
  Free Software Foundation; either version 2 of the License, or (at your
  option) any later version. See the file COPYING for further details.

*/

#ifndef LIB_LINKED_ELEMENTS_H
#define LIB_LINKED_ELEMENTS_H


#include "lib/error.hpp"
#include "lib/nocopy.hpp"
#include "lib/iter-adapter.hpp"
#include "lib/allocator-handle.hpp"
#include "lib/util.hpp"

#include <utility>
#include <memory>


namespace lib {
  
  namespace error = lumiera::error;
  using LERR_(INDEX_BOUNDS);
  using util::unConst;
  
  
  namespace linked_elements { 
    
    template<class ALO>
    struct OwningAllocated
      : lib::allo::StdFactory<ALO>
      , util::MoveOnly
      {
        using lib::allo::StdFactory<ALO>::StdFactory;
        
        using CustomAllocator = ALO;
      };
    
    
    template<class N>
    using OwningHeapAllocated = OwningAllocated<std::allocator<N>>;
    
    
    
    
    struct NoOwnership
      {
        typedef void* CustomAllocator;
        
        void
        dispose (void*)
          {
            /* does nothing */
          }
        
        template<class TY, typename...ARGS>
        TY&
        create (ARGS&&...)
          {
            static_assert ("NoOwnership allocation strategy can not allocate elements");
          } //          ... you'll have to do that yourself (that's the whole point of using this strategy)
      };
    
  }//(END)namespace linked_elements (predefined policies)
  
  
  
  
  
  
  
  
  
  
  /****************************************************************************/
  template
    < class N       
    , class ALO = linked_elements::OwningHeapAllocated<N>
    >
  class LinkedElements
    : ALO
    {
      N* head_;
      
      
    public:
      
     ~LinkedElements()  noexcept
        {
          clear();
        }
      
      LinkedElements()
        : head_{nullptr}
        { }
      
      LinkedElements (LinkedElements const&) = default;
      LinkedElements (LinkedElements&& rr)
        : head_{rr.head_}
        { // possibly transfer ownership
          rr.head_ = nullptr;
        }
      
      explicit
      LinkedElements (typename ALO::CustomAllocator allo)
        : ALO{allo}
        , head_{nullptr}
        { }
      
      template<class IT>
      LinkedElements (IT&& elements)
        : head_{nullptr}
        {
        try {
            pushAll (std::forward<IT> (elements));
          }
        catch(...)
          {
            WARN (progress, "Failure while populating LinkedElements list. "
                            "All elements will be discarded");
            clear();
            throw;
        } }
      
      
      
      void
      clear()  noexcept
        {
          while (head_)
            {
              N* elm = head_;
              head_ = head_->next;
              try {
                  ALO::dispose (elm);
                }
              ERROR_LOG_AND_IGNORE (progress, "Clean-up of element in LinkedElements list")
            }
        }
      
      
      template<class IT>
      void
      pushAll (IT elements)
        {
          for ( ; elements; ++elements )
            push (*elements);
        }
      
      
      
      
      template<typename TY>
      TY&
      push (TY& elm)  noexcept
        {
          elm.next = head_;
          head_ = &elm;
          return elm;
        }
      
      
      
      template<class TY =N, typename...ARGS>
      TY&
      emplace (ARGS&& ...args)
        {
          return push (* ALO::template create<TY> (std::forward<ARGS> (args)...));
        }
      
      
      
      LinkedElements&
      reverse()
        {
          if (not empty())
            {
              N* p = head_->next;
              head_->next = nullptr;
              while (p)
                {
                  N& n = *p;
                  p = p->next;
                  push (n);
            }   }
          return *this;
        }
      
      
      
      
      /* === Element access and iteration === */
      
      N&
      operator[] (size_t index)  const
        {
          N* p = head_;
          while (p and index)
            {
              p = p->next;
              --index;
            }
          
          if (!p or index)
            throw error::Logic ("Attempt to access element beyond the end of LinkedElements list"
                               , LERR_(INDEX_BOUNDS));
          else
            return *p;
        }
      
      
      N&
      top()  const
        {
          REQUIRE (head_, "NIL");
          return *(unConst(this)->head_);
        }
      
      
      size_t
      size()  const
        {
          uint count=0;
          N* p = head_;
          while (p)
            {
              p = p->next;
              ++count;
            }
          return count;
        }
      
      
      bool
      empty() const
        {
          return !head_;
        }
      
    private:
      struct IterationState
        {
          N* node;
          
          IterationState (N* p =nullptr)
            : node{p}
            { }
          
          /* ==== internal callback API for the iterator ==== */
          
          void
          iterNext()
            {
              node = node->next;
            }
          
          bool
          checkPoint()  const
            {
              return bool(node);
            }
          
          N&
          yield()  const
            {
              REQUIRE (node);
              return * unConst(this)->node;
            }
          
          friend bool
          operator== (IterationState const& il, IterationState const& ir)
          {
            return il.node == ir.node;
          }
        };
      
    public:
      using       iterator = IterStateWrapper<IterationState,       N&>;
      using const_iterator = IterStateWrapper<IterationState, const N&>;
      
      
      iterator       begin()       { return iterator       (head_); }
      const_iterator begin() const { return const_iterator (head_); }
      iterator       end ()        { return iterator();       }
      const_iterator end ()  const { return const_iterator(); }
      
    };
  
  
  template<class N>
  auto&
  asLinkedElements (N* const& anchor)
  {
    using Linked = LinkedElements<const N,linked_elements::NoOwnership>;
    return reinterpret_cast<Linked const&>(anchor);
  }
  
  
  
} // namespace lib
#endif /*LIB_LINKED_ELEMENTS_H*/