List.h

#ifndef DASH__LIST_H__
#define DASH__LIST_H__

#include <dash/Types.h>
#include <dash/GlobRef.h>
#include <dash/Team.h>
#include <dash/Exception.h>
#include <dash/memory/GlobHeapMem.h>
#include <dash/Allocator.h>
#include <dash/Array.h>
#include <dash/Meta.h>

#include <dash/list/ListRef.h>
#include <dash/list/LocalListRef.h>
#include <dash/list/GlobListIter.h>
#include <dash/list/internal/ListTypes.h>

#include <iterator>
#include <limits>
#include <vector>

namespace dash {

template <
    typename ElementType,
    typename LocalMemorySpace = dash::HostSpace>
class List {
  static_assert(
    dash::is_container_compatible<ElementType>::value,
    "Type not supported for DASH containers");

  template<typename T_, class A_>
  friend class LocalListRef;

private:
  typedef List<ElementType, LocalMemorySpace> self_t;

  typedef internal::ListNode<ElementType> node_type;

  typedef dash::Array<
      dash::default_size_t,
      int,
      dash::CSRPattern<1, dash::ROW_MAJOR, int> >
      local_sizes_map;

  using glob_mem_type = dash::GlobHeapMem<
      node_type,
      LocalMemorySpace,
      dash::global_allocation_policy::epoch_synchronized,
      dash::allocator::DefaultAllocator>;

public:
  typedef ElementType                    value_type;
  typedef typename dash::default_index_t index_type;
  typedef typename dash::default_size_t  size_type;

  typedef ListRef<ElementType, LocalMemorySpace>      view_type;
  typedef LocalListRef<ElementType, LocalMemorySpace> local_type;

  typedef typename glob_mem_type::local_pointer
    local_node_iterator;
  typedef typename glob_mem_type::const_local_pointer
    const_local_node_iterator;

public:
  typedef index_type                                         difference_type;

  typedef GlobListIter<value_type, glob_mem_type>                   iterator;
  typedef GlobListIter<const value_type, glob_mem_type>       const_iterator;

  typedef std::reverse_iterator<      iterator>             reverse_iterator;
  typedef std::reverse_iterator<const_iterator>       const_reverse_iterator;

  typedef GlobRef<value_type>                                      reference;
  typedef GlobRef<const value_type>                          const_reference;

  typedef       value_type &                                 local_reference;
  typedef const value_type &                           const_local_reference;

  //TODO: add pointer traits to handle this
  typedef GlobHeapPtr<value_type, glob_mem_type> pointer;
  typedef GlobHeapPtr<const value_type, glob_mem_type> const_pointer;

  // TODO: define ListLocalIter to dereference node iterators
  typedef               local_node_iterator                   local_iterator;
  typedef         const_local_node_iterator             const_local_iterator;

public:
  local_type local;

private:
  dash::Team         * _team
                         = nullptr;
  team_unit_t          _myid;
  glob_mem_type      * _globmem
                         = nullptr;
  iterator             _begin;
  iterator             _end;
  size_type            _remote_size
                         = 0;
  local_iterator       _lbegin;
  local_iterator       _lend;
  node_type            _nil_node;
  local_sizes_map      _local_sizes;
  size_type            _local_buffer_size
                         = 4096 / sizeof(value_type);

public:
  explicit List(
    Team & team = dash::Team::Null())
  : local(this),
    _team(&team),
    _myid(team.myid())
  {
    DASH_LOG_TRACE("List() >", "default constructor");
  }

  explicit List(
    size_type   nelem = 0,
    Team      & team  = dash::Team::All())
  : local(this),
    _team(&team),
    _myid(team.myid())
  {
    DASH_LOG_TRACE("List(nelem,team)", "nelem:", nelem);
    if (_team->size() > 0) {
      _local_sizes.allocate(team.size(), dash::BLOCKED, team);
      _local_sizes.local[0] = 0;
    }
    allocate(nelem);
    barrier();
    DASH_LOG_TRACE("List(nelem,team) >");
  }

  List(size_type nelem, size_type nlbuf, Team& team = dash::Team::All())
    : local(this)
    , _team(&team)
    , _myid(team.myid())
    , _local_buffer_size(nlbuf)
  {
    DASH_LOG_TRACE("List(nelem,nlbuf,team)",
                   "nelem:", nelem, "nlbuf:", nlbuf);
    if (_team->size() > 0) {
      _local_sizes.allocate(team.size(), dash::BLOCKED, team);
      _local_sizes.local[0] = 0;
    }
    allocate(nelem);
    barrier();
    DASH_LOG_TRACE("List(nelem,nlbuf,team) >");
  }

  ~List()
  {
    DASH_LOG_TRACE_VAR("List.~List()", this);
    deallocate();
    DASH_LOG_TRACE_VAR("List.~List >", this);
  }

  void push_back(const value_type & element)
  {
  }

  void pop_back()
  {
  }

  reference back()
  {
  }

  void push_front(const value_type & value)
  {
  }

  void pop_front()
  {
  }

  reference front()
  {
  }

  iterator begin() noexcept
  {
    return _begin;
  }

  constexpr const_iterator begin() const noexcept
  {
    return _begin;
  }

  iterator end() noexcept
  {
    return _end;
  }

  constexpr const_iterator end() const noexcept
  {
    return _end;
  }

  local_iterator lbegin() noexcept
  {
    return _lbegin;
  }

  constexpr const_local_iterator lbegin() const noexcept
  {
    return _lbegin;
  }

  local_iterator lend() noexcept
  {
    return _lend;
  }

  constexpr const_local_iterator lend() const noexcept
  {
    return _lend;
  }

  constexpr size_type max_size() const noexcept
  {
    return std::numeric_limits<index_type>::max();
  }

  constexpr size_type size() const noexcept
  {
    return _remote_size + _local_sizes.local[0];
  }

  void resize(size_t num_elements)
  {
  }

  constexpr size_type capacity() const noexcept
  {
    return _globmem->size();
  }

  inline iterator erase(const_iterator position)
  {
    return _begin;
  }

  inline iterator erase(const_iterator first, const_iterator last)
  {
    return _end;
  }

  constexpr Team & team() const noexcept
  {
    return *_team;
  }

  constexpr size_type lsize() const noexcept
  {
    return _local_sizes.local[0];
  }

  constexpr size_type lcapacity() const noexcept
  {
    return _globmem != nullptr
           ? _globmem->local_size()
           : 0;
  }

  constexpr bool empty() const noexcept
  {
    return size() == 0;
  }

  void barrier()
  {
    DASH_LOG_TRACE_VAR("List.barrier()", _team);
    // Apply changes in local memory spaces to global memory space:
    if (_globmem != nullptr) {
      _globmem->commit();
    }
    // Accumulate local sizes of remote units:
    _remote_size = 0;
    for (int u = 0; u < _team->size(); ++u) {
      if (u != _myid) {
        size_type local_size_u  = _local_sizes[u];
        _remote_size           += local_size_u;
      }
    }
    DASH_LOG_TRACE("List.barrier()", "passed barrier");
  }

  bool allocate(
    size_type    nelem = 0,
    dash::Team & team  = dash::Team::All())
  {
    DASH_LOG_TRACE("List.allocate()");
    DASH_LOG_TRACE_VAR("List.allocate", nelem);
    DASH_LOG_TRACE_VAR("List.allocate", _local_buffer_size);
    if (_team == nullptr || *_team == dash::Team::Null()) {
      DASH_LOG_TRACE("List.allocate",
                     "initializing with Team::All()");
      _team = &team;
      DASH_LOG_TRACE_VAR("List.allocate", team.dart_id());
    } else {
      DASH_LOG_TRACE("List.allocate",
                     "initializing with initial team");
    }
    DASH_ASSERT_GT(_local_buffer_size, 0, "local buffer size must not be 0");
    if (nelem < _team->size() * _local_buffer_size) {
      nelem = _team->size() * _local_buffer_size;
    }
    _remote_size = 0;
    auto lcap    = dash::math::div_ceil(nelem, _team->size());
    // Initialize members:
    _myid        = _team->myid();
    // Allocate local memory of identical size on every unit:
    DASH_LOG_TRACE_VAR("List.allocate", lcap);

    _globmem     = new glob_mem_type(lcap, *_team);
    // Global iterators:
    _begin       = iterator(_globmem, _nil_node);
    _end         = _begin;
    // Local iterators:
    _lbegin      = _globmem->lbegin();
    // More efficient than using _globmem->lend as this a second mapping
    // of the local memory segment:
    _lend        = _lbegin;
    DASH_LOG_TRACE_VAR("List.allocate", _myid);
    // Register deallocator of this list instance at the team
    // instance that has been used to initialized it:
    _team->register_deallocator(
             this, std::bind(&List::deallocate, this));
    // Assure all units are synchronized after allocation, otherwise
    // other units might start working on the list before allocation
    // completed at all units:
    if (dash::is_initialized()) {
      DASH_LOG_TRACE("List.allocate",
                     "waiting for allocation of all units");
      _team->barrier();
    }
    DASH_LOG_TRACE("List.allocate >", "finished");
    return true;
  }

  void deallocate()
  {
    DASH_LOG_TRACE_VAR("List.deallocate()", this);
    // Assure all units are synchronized before deallocation, otherwise
    // other units might still be working on the list:
    if (dash::is_initialized()) {
      barrier();
    }
    // Remove this function from team deallocator list to avoid
    // double-free:
    _team->unregister_deallocator(
      this, std::bind(&List::deallocate, this));
    // Deallocate list elements:
    DASH_LOG_TRACE_VAR("List.deallocate()", _globmem);
    if (_globmem != nullptr) {
      delete _globmem;
      _globmem = nullptr;
    }
    _local_sizes.local[0] = 0;
    _remote_size          = 0;
    DASH_LOG_TRACE_VAR("List.deallocate >", this);
  }

};

} // namespace dash

#endif // DASH__LIST_H__