GrowableBuffer.h

Go to the documentation of this file.

// BSD 3-Clause License; see https://github.com/scikit-hep/awkward/blob/main/LICENSE
 
#ifndef AWKWARD_GROWABLEBUFFER_H_
#define AWKWARD_GROWABLEBUFFER_H_
 
#include "awkward/BuilderOptions.h"
 
#include <cstring>
#include <vector>
#include <memory>
#include <numeric>
#include <cmath>
#include <complex>
#include <iostream>
#include <utility>
#include <type_traits>
#include <stdexcept>
#include <stdint.h>
 
namespace awkward {
 
  template <template <class...> class TT, class... Args>
  std::true_type is_tt_impl(TT<Args...>);
  template <template <class...> class TT>
  std::false_type is_tt_impl(...);
 
  template <template <class...> class TT, class T>
  using is_tt = decltype(is_tt_impl<TT>(std::declval<typename std::decay<T>::type>()));
 
  template <typename PRIMITIVE>
  class Panel {
  public:

    Panel(size_t reserved)
        : ptr_(std::unique_ptr<PRIMITIVE[]>(new PRIMITIVE[reserved])),
          length_(0),
          reserved_(reserved),
          next_(nullptr) {}

    Panel(std::unique_ptr<PRIMITIVE[]> ptr, size_t length, size_t reserved)
        : ptr_(std::move(ptr)),
          length_(length),
          reserved_(reserved),
          next_(nullptr) {}

    ~Panel() {
      for (std::unique_ptr<Panel> current = std::move(next_);
           current;
           current = std::move(current->next_));
    }

    PRIMITIVE& operator[](size_t i) { return ptr_.get()[i]; }

    Panel*
    append_panel(size_t reserved) {
      next_ = std::make_unique<Panel>(reserved);
      return next_.get();
    }

    void
    fill_panel(PRIMITIVE datum) {
      ptr_.get()[length_++] = datum;
    }

    void
    fill_panel_from(const PRIMITIVE* from_ptr, size_t size) {
      if (std::is_trivially_copyable<PRIMITIVE>::value) {
        memcpy(ptr_.get() + length_, from_ptr, size * sizeof(PRIMITIVE));
        length_ += size;
      } else {
        for (size_t i = 0; i < size; i++) {
          ptr_.get()[length_++] = from_ptr[i];
        }
      }
    }

    std::unique_ptr<Panel>&
    next() {
      return next_;
    }

    size_t
    current_length() {
      return length_;
    }

    size_t
    reserved() {
      return reserved_;
    }

    std::unique_ptr<PRIMITIVE[]>&
    data() {
      return ptr_;
    }

    void
    append(PRIMITIVE* to_ptr, size_t offset, size_t from, int64_t length) const noexcept {
      memcpy(to_ptr + offset,
             reinterpret_cast<void*>(ptr_.get() + from),
             length * sizeof(PRIMITIVE) - from);
    }

    void
    concatenate_to_from(PRIMITIVE* to_ptr, size_t offset, size_t from) const noexcept {
      memcpy(to_ptr + offset,
             reinterpret_cast<void*>(ptr_.get() + from),
             length_ * sizeof(PRIMITIVE) - from);
      if (next_) {
        next_->concatenate_to(to_ptr, offset + length_);
      }
    }

    void
    concatenate_to(PRIMITIVE* to_ptr, size_t offset) const noexcept {
      memcpy(to_ptr + offset,
             reinterpret_cast<void*>(ptr_.get()),
             length_ * sizeof(PRIMITIVE));
      if (next_) {
        next_->concatenate_to(to_ptr, offset + length_);
      }
    }

    template <typename TO_PRIMITIVE>
    typename std::enable_if<(!awkward::is_tt<std::complex, TO_PRIMITIVE>::value &&
                             !awkward::is_tt<std::complex, PRIMITIVE>::value) ||
                            (awkward::is_tt<std::complex, TO_PRIMITIVE>::value &&
                             awkward::is_tt<std::complex, PRIMITIVE>::value)>::type
    copy_as(TO_PRIMITIVE* to_ptr, size_t offset) {
      for (size_t i = 0; i < length_; i++) {
        to_ptr[offset++] = static_cast<TO_PRIMITIVE>(ptr_.get()[i]);
      }
      if (next_) {
        next_->copy_as(to_ptr, offset);
      }
    }
 
    template <typename TO_PRIMITIVE>
    typename std::enable_if<!awkward::is_tt<std::complex, TO_PRIMITIVE>::value &&
                             awkward::is_tt<std::complex, PRIMITIVE>::value>::type
    copy_as(TO_PRIMITIVE* to_ptr, size_t offset) {
      for (size_t i = 0; i < length_; i++) {
        to_ptr[offset++] = static_cast<TO_PRIMITIVE>(ptr_.get()[i].real());
        to_ptr[offset++] = static_cast<TO_PRIMITIVE>(ptr_.get()[i].imag());
      }
      if (next_) {
        next_->copy_as(to_ptr, offset);
      }
    }

    template <typename TO_PRIMITIVE>
    typename std::enable_if<awkward::is_tt<std::complex, TO_PRIMITIVE>::value &&
                            !awkward::is_tt<std::complex, PRIMITIVE>::value>::type
    copy_as(TO_PRIMITIVE* to_ptr, size_t offset) {
      for (size_t i = 0; i < length_; i++) {
        double val = static_cast<double>(ptr_.get()[i]);
        to_ptr[offset++] = TO_PRIMITIVE(val);
      }
      if (next_) {
        next_->copy_as(to_ptr, offset);
      }
    }
 
  private:
    std::unique_ptr<PRIMITIVE[]> ptr_;

    size_t length_;

    size_t reserved_;

    std::unique_ptr<Panel> next_;
  };

  template <typename PRIMITIVE>
  class GrowableBuffer {
  public:
    static GrowableBuffer<PRIMITIVE>
    empty(const BuilderOptions& options) {
      return empty(options, 0);
    }

    static GrowableBuffer<PRIMITIVE>
    empty(const BuilderOptions& options, int64_t minreserve) {
      int64_t actual = options.initial();
      if (actual < minreserve) {
        actual = minreserve;
      }
      return GrowableBuffer(
          options,
          std::unique_ptr<PRIMITIVE[]>(new PRIMITIVE[(size_t)actual]),
          0,
          actual);
    }

    static GrowableBuffer<PRIMITIVE>
    zeros(const BuilderOptions& options, int64_t length) {
      int64_t actual = options.initial();
      if (actual < length) {
        actual = length;
      }
      auto ptr = std::unique_ptr<PRIMITIVE[]>(new PRIMITIVE[(size_t)actual]);
      PRIMITIVE* rawptr = ptr.get();
      for (int64_t i = 0; i < length; i++) {
        rawptr[i] = 0;
      }
      return GrowableBuffer(options, std::move(ptr), length, actual);
    }

    static GrowableBuffer<PRIMITIVE>
    full(const BuilderOptions& options, PRIMITIVE value, int64_t length) {
      int64_t actual = options.initial();
      if (actual < length) {
        actual = length;
      }
      auto ptr = std::unique_ptr<PRIMITIVE[]>(new PRIMITIVE[(size_t)actual]);
      PRIMITIVE* rawptr = ptr.get();
      for (int64_t i = 0; i < length; i++) {
        rawptr[i] = value;
      }
      return GrowableBuffer<PRIMITIVE>(options, std::move(ptr), length, actual);
    }

    static GrowableBuffer<PRIMITIVE>
    arange(const BuilderOptions& options, int64_t length) {
      int64_t actual = options.initial();
      if (actual < length) {
        actual = length;
      }
      auto ptr = std::unique_ptr<PRIMITIVE[]>(new PRIMITIVE[(size_t)actual]);
      PRIMITIVE* rawptr = ptr.get();
      for (int64_t i = 0; i < length; i++) {
        rawptr[i] = (PRIMITIVE)i;
      }
      return GrowableBuffer(options, std::move(ptr), length, actual);
    }

    template <typename TO_PRIMITIVE>
    static GrowableBuffer<TO_PRIMITIVE>
    copy_as(const GrowableBuffer<PRIMITIVE>& other) {
      int64_t len = (int64_t)other.length();
      int64_t actual =
          (len < other.options_.initial()) ? other.options_.initial() : len;
 
      if (!awkward::is_tt<std::complex, TO_PRIMITIVE>::value &&
        awkward::is_tt<std::complex, PRIMITIVE>::value) {
          len *= 2;
          actual *= 2;
        }
 
      auto ptr =
          std::unique_ptr<TO_PRIMITIVE[]>(new TO_PRIMITIVE[(size_t)actual]);
      TO_PRIMITIVE* rawptr = ptr.get();
 
      other.panel_->copy_as(rawptr, 0);
 
      return GrowableBuffer<TO_PRIMITIVE>(
          BuilderOptions(actual, other.options().resize()),
          std::move(ptr),
          len,
          actual);
    }

    GrowableBuffer(const BuilderOptions& options,
                   std::unique_ptr<PRIMITIVE[]> ptr,
                   int64_t length,
                   int64_t reserved)
        : options_(options),
          length_(0),
          panel_(std::unique_ptr<Panel<PRIMITIVE>>(new Panel<PRIMITIVE>(
              std::move(ptr), (size_t)length, (size_t)reserved))),
          ptr_(panel_.get()) {}

    GrowableBuffer(const BuilderOptions& options)
        : GrowableBuffer(options,
                         std::unique_ptr<PRIMITIVE[]>(
                             new PRIMITIVE[(size_t)options.initial()]),
                         0,
                         options.initial()) {}

    GrowableBuffer(GrowableBuffer&& other) noexcept
        : options_(other.options_),
          length_(other.length_),
          panel_(std::move(other.panel_)),
          ptr_(other.ptr_) {}

    GrowableBuffer& operator=(GrowableBuffer&& other) noexcept = default;

    size_t
    length() const {
      return length_ + ptr_->current_length();
    }

    const BuilderOptions&
    options() const {
      return options_;
    }

    void
    clear() {
      panel_ = std::make_unique<Panel<PRIMITIVE>>((size_t)options_.initial());
      ptr_ = panel_.get();
      length_ = 0;
    }

    PRIMITIVE
    last() const {
      if (ptr_->current_length() == 0) {
        throw std::runtime_error("Buffer is empty");
      } else {
        return (*ptr_)[ptr_->current_length() - 1];
      }
    }

    size_t
    nbytes() const {
      return length() * sizeof(PRIMITIVE);
    }

    void
    append(PRIMITIVE datum) {
      if (ptr_->current_length() == ptr_->reserved()) {
        add_panel((size_t)ceil((double)ptr_->reserved() * options_.resize()));
      }
      fill_panel(datum);
    }

    void
    extend(const PRIMITIVE* ptr, size_t size) {
      size_t unfilled_items = ptr_->reserved() - ptr_->current_length();
      if (size > unfilled_items) {
        fill_panel_from(ptr, unfilled_items);
        add_panel(size - unfilled_items > ptr_->reserved() ? size - unfilled_items
                                                        : ptr_->reserved());
        fill_panel_from(ptr + unfilled_items, size - unfilled_items);
      } else {
        fill_panel_from(ptr, size);
      }
    }

    PRIMITIVE&
    append_and_get_ref(PRIMITIVE datum) {
      append(datum);
      return (*ptr_)[ptr_->current_length() - 1];
    }

    void
    concatenate(PRIMITIVE* external_pointer) const noexcept {
      if (external_pointer) {
        panel_->concatenate_to(external_pointer, 0);
      }
    }

    void
    move_to(PRIMITIVE* to_ptr) noexcept {
      size_t next_offset = 0;
      while(panel_) {
        memcpy(to_ptr + next_offset,
               reinterpret_cast<void*>(panel_.get()->data().get()),
               panel_.get()->current_length() * sizeof(PRIMITIVE));
        next_offset += panel_.get()->current_length();
        panel_ = std::move(panel_.get()->next());
      }
      clear();
    }

    void
    concatenate_from(PRIMITIVE* external_pointer, size_t to, size_t from) const noexcept {
      if (external_pointer) {
        panel_->concatenate_to_from(external_pointer, to, from);
      }
    }

    void
    append(PRIMITIVE* external_pointer, size_t offset, size_t from, int64_t length) const noexcept {
      if (external_pointer) {
        panel_->append(external_pointer, offset, from, length);
      }
    }
 
  private:
    void
    fill_panel(PRIMITIVE datum) {
      ptr_->fill_panel(datum);
    }

    void
    fill_panel_from(const PRIMITIVE* from_ptr, size_t size) {
      ptr_->fill_panel_from(from_ptr, size);
    }

    void
    add_panel(size_t reserved) {
      length_ += ptr_->current_length();
      ptr_ = ptr_->append_panel(reserved);
    }

    BuilderOptions options_;

    size_t length_;

    std::unique_ptr<Panel<PRIMITIVE>> panel_;

    Panel<PRIMITIVE>* ptr_;
  };
}  // namespace awkward
 
#endif  // AWKWARD_GROWABLEBUFFER_H_