array.h

/*
  This file is part of the Fairytale project

  Copyright (C) 2018 Márcio Pais

  This library is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This library 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 Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef ARRAY_H
#define ARRAY_H

// Template Array class from paq8px, slightly modified, see https://github.com/hxim/paq8px

#include "common.h"

template <class T, const int Align = 16> class Array {
private:
  size_t used_size;
  size_t reserved_size;
  char* ptr; // Address of allocated memory (may not be aligned)
  T* data;   // Aligned base address of the elements, (ptr <= T)
  void create(size_t requested_size);
  inline size_t padding() const {
    return Align - 1;
  }
  inline size_t allocated_bytes() const {
    return (reserved_size == 0) ? 0 : reserved_size * sizeof(T) + padding();
  }

public:
  explicit Array(size_t requested_size) {
    create(requested_size);
  }
  ~Array();
  T& operator[](const size_t i) {
    return data[i];
  }
  const T& operator[](const size_t i) const {
    return data[i];
  }
  size_t size() const {
    return used_size;
  }
  void resize(size_t new_size);
  void pop_back() {
    assert(used_size > 0);
    --used_size;
  }                           // decrement size
  void push_back(const T& x); // increment size, append x
  Array(const Array&) {
    assert(false);
  } //prevent copying - this method must be public (gcc must see it but actually won't use it)
private:
  Array& operator=(const Array&){}; //prevent assignment
};

template <class T, const int Align> void Array<T, Align>::create(size_t requested_size) {
  assert((Align & (Align - 1)) == 0);
  used_size = reserved_size = requested_size;
  if (requested_size == 0) {
    data = 0;
    ptr = 0;
    return;
  }
  size_t bytes_to_allocate = allocated_bytes();
  ptr = (char*)calloc(bytes_to_allocate, 1);
  if (ptr == nullptr)
    throw std::bad_alloc();
  uint64_t pad = padding();
  data = (T*)(((uintptr_t)ptr + pad) & ~(uintptr_t)pad);
  assert(ptr <= (char*)data && (char*)data <= ptr + Align);
  assert(((uintptr_t)data & (Align - 1)) == 0); //aligned as expected?
}

template <class T, const int Align> void Array<T, Align>::resize(size_t new_size) {
  if (new_size <= reserved_size) {
    used_size = new_size;
    return;
  }
  char* old_ptr = ptr;
  T* old_data = data;
  size_t old_size = used_size;
  create(new_size);
  if (old_size > 0) {
    assert(old_ptr && old_data);
    memcpy(data, old_data, sizeof(T) * old_size);
  }
  if (old_ptr) {
    free(old_ptr);
    old_ptr = 0;
  }
}

template <class T, const int Align> void Array<T, Align>::push_back(const T& x) {
  if (used_size == reserved_size) {
    size_t old_size = used_size;
    size_t new_size = used_size * 2 + 16;
    resize(new_size);
    used_size = old_size;
  }
  data[used_size++] = x;
}

template <class T, const int Align> Array<T, Align>::~Array() {
  free(ptr);
  used_size = reserved_size = 0;
  data = 0;
  ptr = 0;
}


#endif