ranges.cpp

#include <cstdint>
#include <vector>
#include <atomic>
#include <optional>


// The vectors here are explicitly oragnized as pages. The kernel does
// not provide a way for userland to remap pages, so we remap them by
// hand instead of copying data when concatenating. Specifically we
// create a vector of references to pages that will be read only
// except when we concatenate the pages.
//
// To make the datatypes more concise we use similar but different
// ones for each phase.
template<typename T,size_t pagesize=PAGESiZE>
class vectors {
  alignas(pagesize) class page {
    page() {}
    ~page() {}
    const T& operator[](unsigned i) const { return m_store[i]; }
    T& operator[](unsigned i) { return m_store[i]; }
  private:
    static constexpr capacity = pagesize / sizeof(T);
    T m_store[capacity];
  };

  // It's cheaper to copy these vectors
  using page_ref=std::unique_ptr<page>;
  using pages_vec=std::vector<page_ref>;

  class static_v {
  public:
    static_v(size_t size, pages_vec&& pages) : m_pages(pages), size(size) {}
    ~static_v() {}

    using elem_type=T;
    const T& operator[](unsigned i) const {
      // The compiler will be able to do the right thing here since
      // these are constexprs.
      return m_store[i / page::capacity][i % page::capacity];
    }

    T& operator[](unsigned i) {
      return m_store[i / page::capacity][i % page::capacity];
    }

  private:
    size_t m_size;
    pages_vec m_pages;
  };

  struct full_range {
    size_t size() const {
      // calculate the largest size given the offset.
      //
      // 
    }
    size_t offset;
    static_v& v;
  };

  class comb_v {
  public:
    comb_v(size_t partial_page_size, page_ptr&& partial_page, pages_vec&& pages) :
      m_partial_page_size(partial_page_size),
      m_partial_page(std::move(partial_page))
      m_pages(std::move(pages)) {}
    ~comb_v() {}

    void to_static() && {
      size_t size = partial_page_size.size() * page::capacity + m_partial_page_size;
      m_pages.emplace_back(m_partial_page);
      return {size,m_pages};
    }

    void combine(comb_v&& v) {
      std::move(v.m_pages.begin(), v.m_pages.end(), std::back_inserter(m_pages));
      size_t checkpoint =
        std::min(page::capacity,m_partial_page_size + v.m_partial_page_size);
      for (;;) {
        if (m_partial_page_size == checkpoint) {
          if (v.m_partial_page_size == 0) break;
          m_pages.push_back(m_partial_page);
          m_partial_page = std::move(v.m_partial_page);
          m_partial_page_size = v.m_partial_page_size;
          break;
        }
        m_partial_page[m_partial_page_size++] = m_partial_page[--m_partial_page_size];
      }
    }
  private:
    size_t m_partial_page_size;
    page_ref m_partial_page;
    pages_vec m_pages;
  };

  class push_v {
    push_v() {}
    ~push_v() {}
    void push_back(const std::vector<T>& v) {
      size_t i = 0;
      size_t checkpoint =
        std::min(v.size(), i + page::capacity + m_partial_page_size);

      for (;;) {
        if (i == checkpoint) [[unlikely]] {
          if (i == v.size()) break;
          if (m_partial_page_size == page::capacity) {fresh_page();}
          end = std::min(v.size(), i + page::capacity);
        }
        (*m_partial_page)[m_partial_page_size++] = v[i++];
      }
    }

    void fresh_page() {
      m_partial_page_size = 0;
      m_pages.emplace_back(m_partial_page.release());
      m_partial_page.reset(new page());
    }

    comb_v to_comb() && {
      return {m_partial_page_size,std::move(m_partial_page),std::move(m_pages)};
    }
  private:
    size_t m_partial_page_size;
    page_ref m_partial_page;
    pages_vec m_pages;
  };
};


struct cell_state {
  struct finished {};

  // A reference to another cell. If the cell referenced is empty then we are refering the the tree 
  struct ref { size_t addr; };
  struct cursor { size_t addr; };
  
  struct iterating { size_t remaining_steps; };
  struct virgin {};
  using state_type=std::variant<finished,iterating,virgin,invalid>;
};

struct cell {
  unsigned invalidate() { store.exchange(cell_state::invalid::value); }
  void restore(unsigned v) { store.store(v); }
  void decrement_unsafe() { store--; }
  std::atomic<unsigned> store;
};

// Each subtree has a head and N children
template<size_t N>
struct implicit_finger_tree {
  // steal the largest full block after the cursor by
  // * Making the cursor into an reference to the point of the cursor
  // * The point of reference is now a new cursor.
  cell_state::state_type steal_block(cell cell, size_t block_size) {
    switch (cell.subtract_safe(block_size));
    cell.exchange(cell_state::invalid::value);
  }

  // Find a free subtree and run the algorithm in there. The search in
  // the tree is random.
  template<typename V,typename Fn>
  bool locate_subtree(size_t head, V& v, Fn callback) {
    size_t subtree = rand() % n;
    steal_block((head - v.size()) / N);
  }
  size_t subtree_size(size_t off, size_t total_size) {
    if (off == 0) return total_size
    if (total_size - 1 < N) return 1;
    size_t sutree_size = (total_size - 1) / N;
    // Hopefully the compiler can turn this into a loop.
    return subtree_size((off - 1)  % subtree_size, subtree_size);
  }
}


// MEMORY VECTOR
// 
// The memory vector is organized into an implicit hierarchical
// structure where the structure of each element is distinct from all
// the rest and inferrable only from the address of the head element
// and the size of the entire structure. A simple example and the one
// we use in the N-ary tree prefixed by the root.
//
// For efficiency each substructure is largely (or entirely)
// contiguous.
//
// Elements of the vector that have already been consumed are marked
// and reused to indicate the state of consumption for the
// vector. As a hint for designing the algorithm, a hint may be:
//
//  * self contained -- eg negative values -> references
//  
//  * used in conjunction with other references -- eg. -1 means the
//    next slot is a reference.
//
//  * dependent on the address -- eg. only entire cache lines are considered
//
// For example consider the following semantics
//
//  * cursor pointing at this cell [also marked for demotion]
//  * cursor pointing at the next cell [also marked for demotion]
//  * A cursor the value of which is the next cell
//  * next cell is a reference
//  * other => cell is a node id
//
// We do not use a pointer to an external object to avoid a) memory
// management and b) the extra pointer dereferencing.
//
// Non-demoting Cursor
//
// A non-demoting cursor is a cursor that shows how many elements
// remain till completion. The problem with this cursor is that there
// is no way to tell which sub-structures have been stolen, ie where
// is the true position of the cursor.
//
// However a cursor that is equivalent to an absolute position does
// not contain atomically updatable information about the end
// condition.
//
// The cursor needs both pieces of information:
//
// - How far it is from the end
// - where is the end
//
// We encode both those pieces of information in one cell via
// demotion.
// 
// Moving CURSOR
//
// While a subtree is being consumed it's head acts as a cursor that
// stores the reference of the currently processed item. When another
// thread wants to steal from the tail of the datastructure it
// atomically marks the cursor for relocation. The processing thread
// upon detecting the marked cursor will create a new cursor location
// at the beginning of the field being traced.
//
// What if it is demoted more than once?
// 
// JUMPING JIM
// 
// When a substructure is entirely consumed it's head becomes a
// _reference_ to another address, We _define an algorithm_ for
// traversing these references until a thread reaches a reference for
// a subtree to be consumed. 
//
// All jumps are cache aligned.


int main  () {
  std::vector<atomwrapper<int>> cells{1,2,3};
}