PageParser.h

Go to the documentation of this file.

// Copyright 2019-2020 CERN and copyright holders of ALICE O2.
// See https://alice-o2.web.cern.ch/copyright for details of the copyright holders.
// All rights not expressly granted are reserved.
//
// This software is distributed under the terms of the GNU General Public
// License v3 (GPL Version 3), copied verbatim in the file "COPYING".
//
// In applying this license CERN does not waive the privileges and immunities
// granted to it by virtue of its status as an Intergovernmental Organization
// or submit itself to any jurisdiction.
 
#ifndef ALGORITHM_PAGEPARSER_H
#define ALGORITHM_PAGEPARSER_H
 
 
#include <functional>
#include <vector>
#include <cassert>
#include <type_traits>
#include <stdexcept>
 
namespace o2
{
 
namespace algorithm
{
 
namespace pageparser
{
// a function to extract the number of elements from the group type
// this is the version for all but integral types
template <typename T>
typename std::enable_if<std::is_void<T>::value, size_t>::type
  extractNElements(T* v)
{
  return 0;
}
 
// the specialization for integral types
template <typename T>
typename std::enable_if<std::is_integral<T>::value, T>::type
  extractNElements(T* v)
{
  return *v;
}
 
template <typename GroupT>
using DefaultGetNElementsFctT = size_t (*)(const GroupT*);
 
// the default function to extract the number of elements in a group
// where the group header is a single integral type holding number of
// elements
auto defaultGetNElementsFct = [](const auto* groupdata) {
  using ReturnType = size_t;
  using T = typename std::remove_pointer<decltype(groupdata)>::type;
  // this default function is only for integral types
  static_assert(std::is_integral<T>::value || std::is_void<T>::value,
                "A function for extracting the number of elements from the "
                "group header must be specified for non-trivial types");
  // the default function for trivial integral types means there
  // is exactly one number holding the size
  return static_cast<ReturnType>(extractNElements(groupdata));
};
 
template <typename T>
T* alloc()
{
  return new T;
}
 
template <>
void* alloc<void>()
{
  return nullptr;
}
 
template <typename T>
void free(T* ptr)
{
  if (ptr) {
    delete ptr;
  }
}
 
template <>
void free<void>(void*)
{
}
 
template <typename T>
size_t sizeofGroupHeader()
{
  return sizeof(T);
}
 
template <>
size_t sizeofGroupHeader<void>()
{
  return 0;
}
 
template <typename T>
void set(T* h, size_t v)
{
  *h = v;
}
 
template <>
void set<void>(void*, size_t)
{
}
} // namespace pageparser
 
template <typename PageHeaderT,
          size_t PageSize,
          typename ElementT,
          typename GroupT = void,
          typename GetNElementsFctT = pageparser::DefaultGetNElementsFctT<GroupT>>
class PageParser
{
 public:
  using PageHeaderType = PageHeaderT;
  using BufferType = unsigned char;
  using value_type = ElementT;
  using GroupType = GroupT;
  using GetNElements = GetNElementsFctT;
  static const size_t page_size = PageSize;
 
  // at the moment an object can only be split among two pages
  static_assert(PageSize >= sizeof(PageHeaderType) + sizeof(value_type),
                "Page Header and at least one element have to fit into page");
 
  // switches for the copy method, used to skip ill-formed expressions
  using TargetInPageBuffer = std::true_type;
  using SourceInPageBuffer = std::false_type;
 
  PageParser() = delete;
  template <typename T>
  PageParser(T* buffer, size_t size,
             GetNElements getNElementsFct = pageparser::defaultGetNElementsFct)
    : mBuffer(nullptr), mBufferIsConst(std::is_const<T>::value), mSize(size), mGetNElementsFct(getNElementsFct), mNPages(size > 0 ? ((size - 1) / page_size) + 1 : 0), mGroupHeader(pageparser::alloc<GroupType>())
  {
    static_assert(sizeof(T) == sizeof(BufferType),
                  "buffer required to be byte-type");
 
    // the buffer pointer is stored non-const, a runtime check ensures
    // that iterator write works only for non-const buffers
    mBuffer = const_cast<BufferType*>(buffer);
  }
  ~PageParser()
  {
    pageparser::free(mGroupHeader);
  }
 
  template <typename T>
  class Iterator
  {
   public:
    using ParentType = PageParser;
    using SelfType = Iterator;
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using reference = T&;
    using pointer = T*;
    using difference_type = std::ptrdiff_t;
    using ElementType = typename std::remove_const<value_type>::type;
 
    Iterator() = delete;
 
    Iterator(ParentType const* parent, size_t position = 0)
      : mParent(parent)
    {
      mPosition = position;
      size_t argument = mPosition;
      if (!mParent->getElement(argument, mElement)) {
        // eof, both mPosition and mNextPosition point to buffer end
        mPosition = argument;
      }
      mNextPosition = argument;
      backup();
    }
    ~Iterator()
    {
      sync();
    }
 
    // prefix increment
    SelfType& operator++()
    {
      sync();
      mPosition = mNextPosition;
      size_t argument = mPosition;
      if (!mParent->getElement(argument, mElement)) {
        // eof, both mPosition and mNextPosition point to buffer end
        mPosition = argument;
      }
      mNextPosition = argument;
      backup();
      return *this;
    }
    // postfix increment
    SelfType operator++(int /*unused*/)
    {
      SelfType copy(*this);
      operator++();
      return copy;
    }
    // return reference
    reference operator*()
    {
      return mElement;
    }
    // comparison
    bool operator==(const SelfType& rh) const
    {
      return mPosition == rh.mPosition;
    }
    // comparison
    bool operator!=(const SelfType& rh) const
    {
      return mPosition != rh.mPosition;
    }
 
    const GroupType* getGroupHeader() const
    {
      return mParent->getGroupHeader();
    }
 
   private:
    // sync method for non-const iterator
    template <typename U = void>
    typename std::enable_if<!std::is_const<value_type>::value, U>::type sync()
    {
      if (std::memcmp(&mElement, &mBackup, sizeof(value_type)) != 0) {
        // mElement is changed, sync to buffer
        mParent->setElement(mPosition, mElement);
      }
    }
 
    // overload for const_iterator, empty function body
    template <typename U = void>
    typename std::enable_if<std::is_const<value_type>::value, U>::type sync()
    {
    }
 
    // backup for non-const iterator
    template <typename U = void>
    typename std::enable_if<!std::is_const<value_type>::value, U>::type backup()
    {
      mBackup = mElement;
    }
 
    // overload for const_iterator, empty function body
    template <typename U = void>
    typename std::enable_if<std::is_const<value_type>::value, U>::type backup()
    {
    }
 
    int mPosition;
    int mNextPosition;
    ParentType const* mParent;
    ElementType mElement;
    ElementType mBackup;
  };
 
  size_t setElement(size_t position, const value_type& element) const
  {
    // write functionality not yet implemented for grouped elements
    assert(std::is_void<GroupType>::value);
    // check if we are at the end
    if (position >= mSize) {
      assert(position == mSize);
      return mSize;
    }
 
    // check if there is space for one element
    if (position + sizeof(value_type) > mSize) {
      // format error, probably throw exception
      return mSize;
    }
 
    auto source = reinterpret_cast<const BufferType*>(&element);
    auto target = mBuffer + position;
    return position + copy<TargetInPageBuffer>(source, target, page_size - (position % page_size));
  }
 
  template <typename T>
  size_t readGroupHeader(size_t position, T* groupHeader) const
  {
    assert((position % page_size) == sizeof(PageHeaderType));
    if (std::is_void<T>::value) {
      return 0;
    }
 
    memcpy(groupHeader, mBuffer + position, pageparser::sizeofGroupHeader<T>());
    return mGetNElementsFct(groupHeader);
  }
 
  bool getElement(size_t& position, value_type& element) const
  {
    // check if we are at the end
    if (position >= mSize) {
      assert(position == mSize);
      position = mSize;
      return false;
    }
 
    // handle group if defined
    if (!std::is_void<GroupType>::value) {
      if (mNGroupElements == 0) {
        // new group has to be read from the buffer
        do {
          if ((position % page_size) == 0) {
            position += sizeof(PageHeaderType);
          }
          if ((position % page_size) != sizeof(PageHeaderType)) {
            // forward to the next page
            position += page_size - (position % page_size) + sizeof(PageHeaderType);
            if (position > mSize) {
              //this is probably a valid condition as the group header can just
              //indicate zero clusters
              //throw std::runtime_error("");
              position = mSize;
              return false;
            }
          }
          const_cast<PageParser*>(this)->mNGroupElements = readGroupHeader(position, mGroupHeader);
          position += pageparser::sizeofGroupHeader<GroupType>();
        } while (mNGroupElements == 0);
 
        size_t nPages = 0;
        size_t required = pageparser::sizeofGroupHeader<GroupType>() + mNGroupElements * sizeof(value_type);
        do {
          // the block of elements can go beyond the current page, find out
          // how many additional pages are required
          required += sizeof(PageHeaderType);
          ++nPages;
        } while (required > nPages * page_size);
        required -= sizeof(PageHeaderType) + pageparser::sizeofGroupHeader<GroupType>();
        if (position + required > mSize) {
          throw std::runtime_error(
            "format error: the number of group elements "
            "does not fit into the remaining buffer");
        }
      }
      // now we will read one element
      const_cast<PageParser*>(this)->mNGroupElements -= 1;
      ;
    }
 
    // check if there is space for one element
    if (position + sizeof(value_type) > mSize) {
      // FIXME: not sure if this is considered an error condition if
      // no groups are used, i.e. the buffer should have the correct size
      // and no extra space after the last element
      position = mSize;
      return false;
    }
 
    auto source = mBuffer + position;
    auto target = reinterpret_cast<BufferType*>(&element);
    position += copy<SourceInPageBuffer>(source, target, page_size - (position % page_size));
    return true;
  }
 
  // copy data, depending on compile time switch, either source or target
  // pointer are treated as pointer in the raw page, i.e. can be additionally
  // incremented by the page header
  template <typename SwitchT>
  size_t copy(const BufferType* source, BufferType* target, size_t pageCapacity) const
  {
    size_t position = 0;
    auto copySize = sizeof(value_type);
    // choose which of the pointers needs additional PageHeader offsets
    auto pageOffsetTarget = SwitchT::value ? &target : const_cast<BufferType**>(&source);
    if (pageCapacity == page_size) {
      // skip the page header at beginning of page
      position += sizeof(PageHeaderType);
      pageCapacity -= sizeof(PageHeaderType);
      *pageOffsetTarget += sizeof(PageHeaderType);
    }
    if (copySize > pageCapacity) {
      // object is split at the page boundary, copy the part
      // in the current page first
      copySize = pageCapacity;
    }
    if (copySize > 0) {
      memcpy(target, source, copySize);
      position += copySize;
      source += copySize;
      target += copySize;
    }
    copySize = sizeof(value_type) - copySize;
    if (copySize > 0) {
      // skip page header at beginning of new page and copy
      // remaining part of the element
      position += sizeof(PageHeaderType);
      *pageOffsetTarget += sizeof(PageHeaderType);
      memcpy(target, source, copySize);
      position += copySize;
    }
    return position;
  }
 
  const GroupType getGroupHeader() const
  {
    return mGroupHeader;
  }
 
  using iterator = Iterator<value_type>;
  using const_iterator = Iterator<const value_type>;
 
  const_iterator begin() const
  {
    return const_iterator(this, 0);
  }
 
  const_iterator end() const
  {
    return const_iterator(this, mSize);
  }
 
  iterator begin()
  {
    if (mBufferIsConst) {
      // did not find a way to do this at compile time in the constructor,
      // probably one needs to make the buffer type a template parameter
      // to the class
      throw std::runtime_error("the underlying buffer is not writeable");
    }
    return iterator(this, 0);
  }
 
  iterator end()
  {
    return iterator(this, mSize);
  }
 
 private:
  BufferType* mBuffer = nullptr;
  bool mBufferIsConst = false;
  size_t mSize = 0;
  GetNElements mGetNElementsFct = nullptr;
  size_t mNPages = 0;
  GroupType* mGroupHeader = nullptr;
  size_t mNGroupElements = 0;
};
 
} // namespace algorithm
} // namespace o2
 
#endif