First draft at a lock-free vector

atomic_vector.hpp

namespace fbw {
template<typename T>
class atomic_vector {
public:
 atomic_vector(N) {
  buffer* b = aligned_alloc(
   alignof(buffer),
   sizeof(buffer) +
   N * sizeof(atomic<T>)
  );
  b->buffer();
  for(int i=0;i<N;i++){
   b->array[i].store(T(),
       mo_relaxed);
  }
  apbuff.store(b,
   mo_relaxed);
  size.store(0,mo_relaxed);
 }
 
 ~atomic_vector_base() {
  buffer* b = apbuff.load(
              mo_relaxed);
  int N = b->capacity;
  for(int i=0; i<N; i++) {
   b->array[i].~T();
  };
  aligned_free(b);
 }

 emplace_back(T val) {
   int idx = 
     size.fetch_add(1);
   T temp;
   while(!CASimpl(temp,val));
 }
 pop_back() {
  size.fetch_sub(1);
 }
 
 shrink_to_fit() {
  shrink_impl();
 }
 clear() {
   size.store(0);
   shrink_impl();
 }
 

 reference
  operator[](size_t idx) {
   return reference(idx,this);
 }


 class reference {
  size_t idx
  atomic_vector* v;
  operator T() {
    return load();
  }
  T load() {
    T temp = T();
    T other = T();
    v->CASimpl(idx,temp,other)
    return temp;
  }
  T exchange(T val) {
    T temp;
    while(!
    v->CASimpl(idx,temp,val));
  }
  void store(T val) {
   return (void)exchange(val);
  }
  bool compare_exchange(
             T& expected,
             T& desired){
    return v->CASimpl(
             idx,expected,
             desired);
  }
 }; // class reference

 friend class reference;

private:
 atomic<buffer*> apbuff;
 atomic<long> size;


 void reserveimpl(size_t idx){
  buffer* b = 
   aligned_alloc(
    alignof(buffer),
    sizeof(buffer)+
    idx*sizeof(T);
  b->capacity = idx;
  dptr d;
  do {
   d = {getptr(),nullptr};
  } while(ptr.cas(d,{b,d.new};
  hptr<0>().store(nullptr);
 }
 
 buffer* getsizebuffer(
               size_t idx) {
  buffer* b = getptr();
  if(idx > b->capacity) {
   reserve(
     max(idx,b->size*2));
   continue;
  }
  size_t sizel;
  while(!size.casw(sizel,
     max(sizel,idx);
  return b;
 }
 
 bool CASimpl(size_t idx,
              T& expected,
              T desired) {
  T temp = expected;
  do {
   buffer* b = getbuffer(idx);
  } while(
    b->array[idx].cas(old,new)
    && b==getptr()
    && temp == expected
  );
  hp_thread<0>()
    .store(nullptr);
  delete_pending_hazards();
 }

 shrink_impl() {
  buffer* b = getptr();
  buffer* temp;
  do {
   temp=b;
   size_t s = b->size.load();
   reserveimpl(s);
   temp=b;
   b = getptr();
  while(b==temp);
 }

 struct buffer {
  size_t capacity;
  atomic<T> array[0];
 };

 struct dptr {
  buffer* new;
  buffer* old;
 };
 
 copy(buffer* oldbuff,
      buffer* newbuff) {
  size_t temp newbuff->
               size.load();
  oldbuff.store(temp);
  for(int i=0; i<ms; i++) {
   T temp =
    oldbuff->array[i].load()
   newbuff->array[i].store(
    temp);
  }
 }

 buffer* getptr() {
  dptr d =
    set_hazard(ptr);
  while(d.old) {
   copy(d.old, d.new);
   if(ptr.cas(d,
             {d.new,nullptr}){
    delete_hazards(d.old);
   }
   d = set_hazard(ptr);
  }
  return d.new;
 }
 
 set_hazard(
   atomic<dptr>& atom) {
  dptr v = atom.load();
  do {
   dptr temp = v;
   hptr<0>().store(temp.new);
   hptr<1>().store(temp.old);
  } while (v!=temp);
  return v;
 }
 
}; // class atomic_vector
} // namespace fbw