linked-elements.hpp

Go to the documentation of this file.

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

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

  This program 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.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

*/

#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/util.hpp"

#include <utility>


namespace lib {
  
  namespace error = lumiera::error;
  using LERR_(INDEX_BOUNDS);
  using util::unConst;
  
  
  namespace linked_elements { 
    
    struct OwningHeapAllocated
      : util::MoveOnly
      {
        typedef void* CustomAllocator;
        
        template<class X>
        void 
        destroy (X* elm)
          {
            delete elm;
          }
        
        
        template<class TY, typename...ARGS>
        TY&
        create (ARGS&& ...args)
          {
            return *new TY (std::forward<ARGS> (args)...);
          }
      };
    
    
    
    
    
    
    struct NoOwnership
      {
        typedef void* CustomAllocator;
        
        void 
        destroy (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)
      };
    
    
    
    
    
#ifdef LIB_ALLOCATION_CLUSTER_H
    
    struct UseAllocationCluster
      {
        typedef AllocationCluster& CustomAllocator;
        
        CustomAllocator cluster_;
        
        
        explicit
        UseAllocationCluster (CustomAllocator clu)
          : cluster_(clu)
          { }
        
        
        void 
        destroy (void*)
          {
            /* does nothing */
          }
        
        
        template<class TY, typename...ARGS>
        TY&
        create (ARGS&& ...args)
          {
            return cluster_.create<TY> (std::forward<ARGS> (args)...);
          }
      };
    
#endif //(End)if lib/allocation-cluster.hpp was included
    
  }//(END)namespace linked_elements
  
  
  
  
  
  
  
  
  
  
  template
    < class N                 
    , class ALO = linked_elements::OwningHeapAllocated
    >
  class LinkedElements
    : ALO
    {
      N* head_;
      
      
    public:
      
     ~LinkedElements()
        { 
          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()
        {
          while (head_)
            {
              N* elm = head_;
              head_ = head_->next;
              try {
                  ALO::destroy(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)
        {
          elm.next = head_;
          head_ = &elm;
          return elm;
        }
      
      
//      template< class TY =N>
//      TY&                                                  //_________________________________________
//      emplace ()                                          ///< add object of type TY, using 0-arg ctor
//        {
//          return push (ALO::template create<TY>());
//        }
      
      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<      N, IterationState>;
      using const_iterator = IterStateWrapper<const N, IterationState>;
      
      
      iterator       begin()       { return iterator       (head_); }
      const_iterator begin() const { return const_iterator (head_); }
      iterator       end ()        { return iterator();       }
      const_iterator end ()  const { return const_iterator(); }
      
    };
  
  
  
  
} // namespace lib
#endif /*LIB_LINKED_ELEMENTS_H*/