container.hpp

Go to the documentation of this file.

/* SPDX-License-Identifier: Apache-2.0 */
/* Copyright 2015-2019 Peter A. Bigot */
 
#ifndef PABIGOT_CONTAINER_HPP
#define PABIGOT_CONTAINER_HPP
#pragma once
 
#include <array>
#include <cinttypes>
#include <functional>
#include <limits>
 
#include <pabigot/common.hpp>
 
namespace pabigot {
 
namespace container {
 
template <typename T = uint8_t>
class rr_adaptor
{
public:
  using value_type = T;
 
  using size_type = uint16_t;
 
  using ssize_type = std::make_signed<size_type>::type;
 
  static constexpr size_type EMPTY_HEAD = -1;
 
  constexpr rr_adaptor (value_type* data,
                        size_type count) :
    data_{data},
    count_{count}
  { }
 
  rr_adaptor () = delete;
  rr_adaptor (const rr_adaptor&) = delete;
  rr_adaptor& operator= (const rr_adaptor&) = delete;
  rr_adaptor (rr_adaptor&&) = delete;
  rr_adaptor& operator= (rr_adaptor&&) = delete;
 
  bool empty () const noexcept
  {
    return EMPTY_HEAD == head_;
  }
 
  bool full () const noexcept
  {
    return size() == max_size();
  }
 
  size_type max_size () const noexcept
  {
    return count_;
  }
 
  size_type size () const noexcept
  {
    size_type rv = 0;
    if (!empty()) {
      /* Get the signed difference between the head and tail.  Negative means the
       * range wraps. */
      ssize_type n = head_ - tail_;
      if (0 >= n) {
        n += count_;
      }
      rv = n;
    }
    return rv;
  }
 
  bool push (value_type v) noexcept
  {
    bool rv = false;
 
    if (empty()) {
      head_ = tail_ = 0;
    } else if (tail_ == head_) {
      rv = true;
      (void)pop();
    }
    auto nh = next_index_(head_);
    data_[head_] = v;
    head_ = nh;
    return rv;
  }
 
  value_type pop () noexcept
  {
    if (empty()) {
      return value_type{};
    }
    size_type tail = tail_;
    tail_ = next_index_(tail_);
    if (head_ == tail_) {
      head_ = EMPTY_HEAD;
    }
    return data_[tail];
  }
 
  void clear () noexcept
  {
    head_ = EMPTY_HEAD;
  }
 
private:
  size_type next_index_ (size_type v) const
  {
    if (++v >= count_) {
      v = 0;
    }
    return v;
  }
 
  value_type* data_;
  size_type const count_;
  size_type head_ = EMPTY_HEAD;
  size_type tail_ = 0;
};
 
template <typename T,
          typename REF_NEXT>
class forward_chain
{
public:
  using chain_type = forward_chain<T, REF_NEXT>;
 
  using value_type = T;
 
  using pointer_type = value_type *;
 
  using predicate_type = std::function<bool(const value_type&)>;
 
  static constexpr uintptr_t UNLINKED_PTR = -1;
 
  static pointer_type unlinked_ptr () noexcept
  {
    return reinterpret_cast<pointer_type>(UNLINKED_PTR);
  }
 
  bool is_unlinked (pointer_type ptr) const noexcept
  {
    return unlinked_ptr() == ptr;
  }
 
  bool is_unlinked (value_type& value) const noexcept
  {
    return is_unlinked(ref_next(value));
  }
 
  /* You can default-construct these. */
  forward_chain () noexcept = default;
 
  /* You can't copy them. */
  forward_chain (const forward_chain&) = delete;
  forward_chain& operator= (const forward_chain&) = delete;
 
  /* You can move them. */
  forward_chain (forward_chain&& from) noexcept :
    front_{from.front_},
    back_{from.back_}
  {
    from.front_ = from.back_ = nullptr;
  }
 
  forward_chain& operator= (forward_chain&& from) noexcept
  {
    front_ = from.front_;
    back_ = from.back_;
    from.front_ = from.back_ = nullptr;
    return *this;
  }
 
  class end_iterator_type { };
 
  class chain_iterator_type
  {
    friend chain_type;
 
    chain_iterator_type (const chain_type& chain) :
      chain{chain},
      current{chain.front_},
      next{current ? chain.ref_next(*current) : nullptr}
    { }
 
    const chain_type& chain;
 
    pointer_type current = nullptr;
 
    pointer_type next = nullptr;
 
  public:
    bool operator== (const end_iterator_type& )
    {
      return !current;
    }
 
    bool operator!= (const end_iterator_type& rhs)
    {
      return !operator==(rhs);
    }
 
    chain_iterator_type& operator++ ()
    {
      current = next;
      if (current) {
        next = chain.ref_next(*current);
        /* Avoid segfault if somebody removed a value that we iterated into.
         * See RangeFor whitebox testing. */
        if (chain.is_unlinked(next)) {
          next = nullptr;
        }
      }
      return *this;
    }
 
    value_type& operator* () noexcept
    {
      return *current;
    }
  };
 
  chain_iterator_type begin () const noexcept
  {
    return {*this};
  }
 
  end_iterator_type end () const noexcept
  {
    return {};
  }
 
  bool empty () const noexcept
  {
    return !front_;
  }
 
  pointer_type front () const noexcept
  {
    return front_;
  }
 
  pointer_type next (value_type& elt) const noexcept
  {
    return ref_next(elt);
  }
 
  pointer_type back () const noexcept
  {
    return back_;
  }
 
  void link_front (value_type &value) noexcept
  {
    if (empty()) {
      back_ = &value;
    }
    ref_next(value) = front_;
    front_ = &value;
  }
 
  pointer_type unlink_front () noexcept
  {
    auto rv = front_;
    if (rv) {
      auto& next = ref_next(*rv);
      front_ = next;
      next = unlinked_ptr();
      if (back_ == rv) {
        back_ = nullptr;
      }
    }
    return rv;
  }
 
  void link_after (value_type &pos,
                   value_type &value) noexcept
  {
    ref_next(value) = ref_next(pos);
    ref_next(pos) = &value;
    if (back_ == &pos) {
      back_ = &value;
    }
  }
 
  void link_before (value_type &value,
                    predicate_type pred) noexcept
  {
    auto npp = &front_;
    while (*npp) {
      auto np = *npp;
      if (pred(*np)) {
        ref_next(value) = np;
        *npp = &value;
        return;
      }
      npp = &ref_next(*np);
    }
    return link_back(value);
  }
 
  chain_type split_through (predicate_type pred) noexcept
  {
    if (empty()
        || (!pred(*front_))) {
      return {};
    }
    auto prev = front_;
    auto npp = &ref_next(*prev);
    while ((*npp) && pred(**npp)) {
      prev = *npp;
      npp = &ref_next(*prev);
    };
    auto front = front_;
    front_ = *npp;
    if (!front_) {
      back_ = nullptr;
    }
    *npp = nullptr;
    return {front, prev};
  }
 
  void link_back (value_type &value) noexcept
  {
    if (empty()) {
      return link_front(value);
    }
    ref_next(value) = nullptr;
    ref_next(*back_) = &value;
    back_ = &value;
  }
 
  pointer_type unlink (value_type& value) noexcept
  {
    auto lpp = &front_;
    pointer_type prev = nullptr;
 
    while (*lpp) {
      auto lp = *lpp;
      if (&value == lp) {
        auto& next = ref_next(value);
        *lpp = next;
        next = unlinked_ptr();
        if (&value == back_) {
          back_ = prev;
        }
        return &value;
      }
      prev = lp;
      lpp = &ref_next(*lp);
    }
    return nullptr;
  }
 
  void clear () noexcept
  {
    auto p = front_;
    while (p) {
      auto& next = ref_next(*p);
      p = next;
      next = unlinked_ptr();
    }
    front_ = back_ = nullptr;
  }
 
private:
  forward_chain (pointer_type front,
                 pointer_type back) noexcept :
    front_{front},
    back_{back}
  { }
 
  pointer_type& ref_next (value_type & elt) const noexcept
  {
    return REF_NEXT{}(elt);
  }
 
  pointer_type front_{};
 
  pointer_type back_{};
};
 
} // ns container
 
} // ns pabigot
 
#endif /* PABIGOT_CONTAINER_HPP */