vector.hh

// This file is a part of Aurelia.
// Copyright (C) 2010  Valentin David
// Copyright (C) 2010  University of Bergen
//
// 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 3 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, see <http://www.gnu.org/licenses/>.

#ifndef __VECTOR_HH
# define __VECTOR_HH

# include <atomic>
# include <cassert>
# include "simple_stack.hh"

namespace lockfree {

  template <typename T, size_t SEG_SIZE = 1024u,
            typename Alloc = std::allocator<T> >
  struct vector {
  private:
    struct seg_table {
      size_t n_segments;
      T** segments;
    };

    typedef typename Alloc::template rebind<seg_table>::other st_alloc_t;
    typedef typename Alloc::template rebind<T*>::other pt_alloc_t;

    Alloc alloc;
    st_alloc_t st_alloc;
    pt_alloc_t pt_alloc;
    std::atomic<seg_table*> table;
    simple_stack<seg_table*> free;
    T default_value;

    /* This is not completely thread safe. However, for our use, the vector
     * can be fixed if it was modified.
     */
    void set_size(size_t size) {
      size_t isize = (size+SEG_SIZE-1)/SEG_SIZE;
      seg_table* t = table.load();
      if (t->n_segments >= isize) {
        return ;
      }
      seg_table* newt = st_alloc.allocate(1);
      newt->n_segments = isize;
      newt->segments = pt_alloc.allocate(isize);
      size_t delete_from = isize;
      do {
        t = table.load();
        if (t->n_segments >= isize) {
          for (size_t i = delete_from; i < isize; ++i) {
            for (size_t j = 0; j < SEG_SIZE; ++j)
              alloc.destroy(newt->segments[i] + j);
            alloc.deallocate(newt->segments[i], SEG_SIZE);
          }
          pt_alloc.deallocate(newt->segments, isize);
          st_alloc.deallocate(newt, 1);
          return ;
        }
        size_t i = 0;
        for (; (i < t->n_segments); ++i) {
          if (i >= delete_from) {
            for (size_t j = 0; j < SEG_SIZE; ++j)
              alloc.destroy(newt->segments[i] + j);
            alloc.deallocate(newt->segments[i], SEG_SIZE);
          }
          newt->segments[i] = t->segments[i];
        }
        size_t delete_from_next = i;
        for (; (i < delete_from); ++i) {
          newt->segments[i] = alloc.allocate(SEG_SIZE);
          for (size_t j = 0; j < SEG_SIZE; ++j)
            alloc.construct(newt->segments[i] + j, default_value);
        }
        delete_from = delete_from_next;
      } while (!table.compare_exchange_strong(t, newt));
      free.push((seg_table*)(t));
    }

  public:
    vector(T default_value = T(), Alloc alloc = Alloc())
      : alloc(alloc), st_alloc(alloc), pt_alloc(alloc),
        table(st_alloc.allocate(1)), default_value(default_value) {
      table.load()->n_segments = 0;
    }

    T& operator[](size_t n) {
      seg_table* t = table.load();
      assert(n < (SEG_SIZE*t->n_segments));
      return t->segments[n/SEG_SIZE][n%SEG_SIZE];
    }

    const T& operator[](size_t n) const {
      seg_table* t = table.load();
      assert(n < (SEG_SIZE*t->n_segments));
      return t->segments[n/SEG_SIZE][n%SEG_SIZE];
    }

    void resize(size_t size) {
      set_size(size);
    }

    void collect() {
      while (true) {
        typename simple_stack<seg_table*>::wrapped w = free.pop();
        if (w.end())
          break ;
        seg_table *t = *w;
        if (t->n_segments > 0)
          pt_alloc.deallocate(t->segments, t->n_segments);
        st_alloc.deallocate(t, 1);
      }
    }

    size_t size() const {
      return table.load()->n_segments * SEG_SIZE;
    }

    ~vector() {
      collect();
      seg_table* t = table.load();
      for (size_t i = 0; i < t->n_segments; ++i) {
        for (size_t j = 0; j < SEG_SIZE; ++j) {
          alloc.destroy(t->segments[i] + j);
        }
        alloc.deallocate(t->segments[i], SEG_SIZE);
      }
      if (t->n_segments > 0)
        pt_alloc.deallocate(t->segments, t->n_segments);
      st_alloc.deallocate(t, 1);
    }
  };
}

#endif