summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/netlist/plib/plists.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/netlist/plib/plists.h')
-rw-r--r--src/lib/netlist/plib/plists.h480
1 files changed, 261 insertions, 219 deletions
diff --git a/src/lib/netlist/plib/plists.h b/src/lib/netlist/plib/plists.h
index 525a65a97f2..2e389f34b54 100644
--- a/src/lib/netlist/plib/plists.h
+++ b/src/lib/netlist/plib/plists.h
@@ -1,281 +1,323 @@
-// license:GPL-2.0+
+// license:BSD-3-Clause
// copyright-holders:Couriersud
-/*
- * plists.h
- *
- */
-
-#pragma once
#ifndef PLISTS_H_
#define PLISTS_H_
-#include "pstring.h"
+///
+/// \file plists.h
+///
+
+#include "ptypes.h"
+#include <algorithm>
#include <array>
#include <type_traits>
-#include <vector>
+#include <utility>
namespace plib {
-/* ----------------------------------------------------------------------------------------
- * uninitialised_array_t:
- * fixed size array allowing to override constructor and initialize
- * members by placement new.
- *
- * Use with care. This template is provided to improve locality of storage
- * in high frequency applications. It should not be used for anything else.
- * ---------------------------------------------------------------------------------------- */
-
-template <class C, std::size_t N>
-class uninitialised_array_t
-{
-public:
-
- using iterator = C *;
- using const_iterator = const C *;
-
- //uninitialised_array_t() noexcept = default;
- uninitialised_array_t() noexcept
- : m_initialized(0)
- {
- }
- COPYASSIGNMOVE(uninitialised_array_t, delete)
- ~uninitialised_array_t() noexcept
+ /// \brief Array holding uninitialized elements
+ ///
+ /// Use with care. This template is provided to improve locality of storage
+ /// in high frequency applications. It should not be used for anything else.
+ ///
+ template <class C, std::size_t N>
+ class uninitialised_array
{
- if (m_initialized>=N)
- for (std::size_t i=0; i<N; i++)
- (*this)[i].~C();
- }
+ public:
- size_t size() const { return N; }
+ using value_type = C;
+ using pointer = value_type *;
+ using const_pointer = const value_type *;
+ using reference = value_type &;
+ using const_reference = const value_type &;
+ using iterator = value_type *;
+ using const_iterator = const value_type *;
+ using size_type = std::size_t;
+ using difference_type = std::ptrdiff_t;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
- C& operator[](const std::size_t &index) noexcept
- {
- return *reinterpret_cast<C *>(&m_buf[index]);
- }
+ constexpr uninitialised_array() noexcept = default;
- const C& operator[](const std::size_t &index) const noexcept
- {
- return *reinterpret_cast<const C *>(&m_buf[index]);
- }
+ constexpr uninitialised_array(const uninitialised_array &) = default;
+ constexpr uninitialised_array &operator=(const uninitialised_array &) = default;
+ constexpr uninitialised_array(uninitialised_array &&) noexcept = default;
+ constexpr uninitialised_array &operator=(uninitialised_array &&) noexcept = default;
- template<typename... Args>
- void emplace(const std::size_t index, Args&&... args)
- {
- m_initialized++;
- // allocate on buffer
- new (&m_buf[index]) C(std::forward<Args>(args)...);
- }
+ ~uninitialised_array() noexcept = default;
- iterator begin() const noexcept { return reinterpret_cast<iterator>(&m_buf[0]); }
- iterator end() const noexcept { return reinterpret_cast<iterator>(&m_buf[N]); }
+ constexpr size_t size() const noexcept { return N; }
- iterator begin() noexcept { return reinterpret_cast<iterator>(&m_buf[0]); }
- iterator end() noexcept { return reinterpret_cast<iterator>(&m_buf[N]); }
+ constexpr bool empty() const noexcept { return size() == 0; }
- const_iterator cbegin() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[0]); }
- const_iterator cend() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[N]); }
+ constexpr reference operator[](size_type index) noexcept
+ {
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ return reinterpret_cast<reference>(m_buf[index]);
+ }
-protected:
+ constexpr const_reference operator[](size_type index) const noexcept
+ {
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ return reinterpret_cast<const_reference>(m_buf[index]);
+ }
-private:
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr iterator begin() const noexcept { return reinterpret_cast<iterator>(&m_buf[0]); }
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr iterator end() const noexcept { return reinterpret_cast<iterator>(&m_buf[0] + N); }
- /* ensure proper alignment */
- PALIGNAS_VECTOROPT()
- std::array<typename std::aligned_storage<sizeof(C), alignof(C)>::type, N> m_buf;
- unsigned m_initialized;
-};
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr iterator begin() noexcept { return reinterpret_cast<iterator>(&m_buf[0]); }
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr iterator end() noexcept { return reinterpret_cast<iterator>(&m_buf[0] + N); }
-// ----------------------------------------------------------------------------------------
-// plinkedlist_t: a simple linked list
-// the list allows insertions / deletions if used properly
-// ----------------------------------------------------------------------------------------
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr const_iterator cbegin() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[0]); }
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr const_iterator cend() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[0] + N); }
-#if 0
-template <class LC>
-class linkedlist_t
-{
-public:
+ private:
+ std::array<typename std::aligned_storage<sizeof(C), alignof(C)>::type, N> m_buf;
+ };
- struct element_t
+ /// \brief fixed allocation vector
+ ///
+ /// Currently only emplace_back and clear are supported.
+ ///
+ /// Use with care. This template is provided to improve locality of storage
+ /// in high frequency applications. It should not be used for anything else.
+ ///
+ template <class C, std::size_t N>
+ class static_vector
{
public:
- friend class linkedlist_t<LC>;
-
- constexpr element_t() : m_next(nullptr) {}
- constexpr element_t(const element_t &rhs) = delete;
- constexpr element_t(element_t &&rhs) = delete;
+ using value_type = C;
+ using pointer = value_type *;
+ using const_pointer = const value_type *;
+ using reference = value_type &;
+ using const_reference = const value_type &;
+ using iterator = value_type *;
+ using const_iterator = const value_type *;
+ using size_type = std::size_t;
+ using difference_type = std::ptrdiff_t;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+ constexpr static_vector() noexcept
+ : m_pos(0)
+ {
+ }
- constexpr LC *next() const noexcept { return m_next; }
+ constexpr static_vector(const static_vector &) = default;
+ constexpr static_vector &operator=(const static_vector &) = default;
+ constexpr static_vector(static_vector &&) noexcept = default;
+ constexpr static_vector &operator=(static_vector &&) noexcept = default;
- protected:
- ~element_t() = default;
- private:
- LC * m_next;
- };
+ ~static_vector() noexcept
+ {
+ clear();
+ }
- struct iter_t final : public std::iterator<std::forward_iterator_tag, LC>
- {
- private:
- LC* p;
- public:
- explicit constexpr iter_t(LC* x) noexcept : p(x) { }
- explicit constexpr iter_t(const iter_t &rhs) noexcept : p(rhs.p) { }
- iter_t(iter_t &&rhs) noexcept { std::swap(*this, rhs); }
- iter_t& operator=(const iter_t &rhs) { iter_t t(rhs); std::swap(*this, t); return *this; }
- iter_t& operator=(iter_t &&rhs) { std::swap(*this, rhs); return *this; }
- iter_t& operator++() noexcept {p = p->next();return *this;}
- iter_t operator++(int) noexcept {iter_t tmp(*this); operator++(); return tmp;}
- constexpr bool operator==(const iter_t& rhs) const noexcept {return p == rhs.p;}
- constexpr bool operator!=(const iter_t& rhs) const noexcept {return p != rhs.p;}
- /* constexpr */ LC& operator*() noexcept {return *p;}
- /* constexpr */ LC* operator->() noexcept {return p;}
-
- constexpr LC& operator*() const noexcept {return *p;}
- constexpr LC* operator->() const noexcept {return p;}
- };
+ constexpr size_t size() const noexcept { return m_pos; }
- constexpr linkedlist_t() : m_head(nullptr) {}
+ constexpr bool empty() const noexcept { return size() == 0; }
- constexpr iter_t begin() const noexcept { return iter_t(m_head); }
- constexpr iter_t end() const noexcept { return iter_t(nullptr); }
+ constexpr void clear()
+ {
+ for (size_type i=0; i<m_pos; ++i)
+ (*this)[i].~C();
+ m_pos = 0;
+ }
- void push_front(LC *elem) noexcept
- {
- elem->m_next = m_head;
- m_head = elem;
- }
+ template<typename... Args>
+ constexpr void emplace_back(Args&&... args)
+ {
+ // placement new on buffer
+ new (&m_buf[m_pos]) C(std::forward<Args>(args)...);
+ m_pos++;
+ }
- void push_back(LC *elem) noexcept
- {
- LC **p = &m_head;
- while (*p != nullptr)
+ constexpr reference operator[](size_type index) noexcept
{
- p = &((*p)->m_next);
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ return reinterpret_cast<reference>(m_buf[index]);
}
- *p = elem;
- elem->m_next = nullptr;
- }
- void remove(const LC *elem) noexcept
- {
- auto p = &m_head;
- while(*p != elem)
+ constexpr const_reference operator[](size_type index) const noexcept
{
- //nl_assert(*p != nullptr);
- p = &((*p)->m_next);
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ return reinterpret_cast<const_reference>(m_buf[index]);
}
- (*p) = elem->m_next;
- }
- LC *front() const noexcept { return m_head; }
- void clear() noexcept { m_head = nullptr; }
- constexpr bool empty() const noexcept { return (m_head == nullptr); }
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr iterator begin() const noexcept { return reinterpret_cast<iterator>(&m_buf[0]); }
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr iterator end() const noexcept { return reinterpret_cast<iterator>(&m_buf[0] + m_pos); }
-private:
- LC *m_head;
-};
-#else
-template <class LC>
-class linkedlist_t
-{
-public:
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr iterator begin() noexcept { return reinterpret_cast<iterator>(&m_buf[0]); }
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr iterator end() noexcept { return reinterpret_cast<iterator>(&m_buf[0] + m_pos); }
+
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr const_iterator cbegin() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[0]); }
+ // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
+ constexpr const_iterator cend() const noexcept { return reinterpret_cast<const_iterator>(&m_buf[0] + m_pos); }
+
+ private:
+ std::array<typename std::aligned_storage<sizeof(C), alignof(C)>::type, N> m_buf;
+ size_type m_pos;
+ };
- struct element_t
+ /// \brief a simple linked list.
+ ///
+ /// The list allows insertions and deletions whilst being processed.
+ ///
+ template <class LC, int TAG>
+ class linked_list_t
{
public:
+ using ttag = std::integral_constant<int, TAG>;
- friend class linkedlist_t<LC>;
+ struct element_t
+ {
+ public:
+ using tag = std::integral_constant<int, TAG>;
- constexpr element_t() : m_next(nullptr), m_prev(nullptr) {}
- ~element_t() noexcept = default;
+ friend class linked_list_t<LC, TAG>;
- COPYASSIGNMOVE(element_t, delete)
+ constexpr element_t() noexcept : m_next(nullptr), m_prev(nullptr) {}
+ ~element_t() noexcept = default;
- constexpr LC *next() const noexcept { return m_next; }
- constexpr LC *prev() const noexcept { return m_prev; }
- private:
- LC * m_next;
- LC * m_prev;
- };
+ constexpr element_t(const element_t &) noexcept = default;
+ constexpr element_t &operator=(const element_t &) noexcept = default;
+ constexpr element_t(element_t &&) noexcept = default;
+ constexpr element_t &operator=(element_t &&) noexcept = default;
- struct iter_t final : public std::iterator<std::forward_iterator_tag, LC>
- {
- private:
- LC* p;
- public:
- explicit constexpr iter_t(LC* x) noexcept : p(x) { }
- constexpr iter_t(iter_t &rhs) noexcept : p(rhs.p) { }
- iter_t(iter_t &&rhs) noexcept { std::swap(*this, rhs); }
- iter_t& operator=(const iter_t &rhs) noexcept { iter_t t(rhs); std::swap(*this, t); return *this; }
- iter_t& operator=(iter_t &&rhs) noexcept { std::swap(*this, rhs); return *this; }
- iter_t& operator++() noexcept {p = p->next();return *this;}
- // NOLINTNEXTLINE(cert-dcl21-cpp)
- iter_t operator++(int) & noexcept {const iter_t tmp(*this); operator++(); return tmp;}
-
- ~iter_t() = default;
-
- constexpr bool operator==(const iter_t& rhs) const noexcept {return p == rhs.p;}
- constexpr bool operator!=(const iter_t& rhs) const noexcept {return p != rhs.p;}
- /* constexpr */ LC& operator*() noexcept {return *p;}
- /* constexpr */ LC* operator->() noexcept {return p;}
-
- constexpr LC& operator*() const noexcept {return *p;}
- constexpr LC* operator->() const noexcept {return p;}
- };
+ private:
+ element_t * m_next;
+ element_t * m_prev;
+ };
- constexpr linkedlist_t() : m_head(nullptr) {}
+ struct iter_t final
+ {
+ private:
+ element_t * p;
+ public:
+ using tag = std::integral_constant<int, TAG>;
+ using iterator_category = std::forward_iterator_tag;
+ using value_type = LC;
+ using pointer = value_type *;
+ using reference = value_type &;
+ using difference_type = std::ptrdiff_t;
+
+ explicit constexpr iter_t(element_t * x) noexcept : p(x) { }
+
+ constexpr iter_t(const iter_t &rhs) noexcept = default;
+ constexpr iter_t(iter_t &&rhs) noexcept = default;
+ constexpr iter_t& operator=(const iter_t &rhs) noexcept = default;
+ constexpr iter_t& operator=(iter_t &&rhs) noexcept = default;
+
+ ~iter_t() noexcept = default;
+
+ iter_t& operator++() noexcept { p = p->m_next; return *this; }
+ // NOLINTNEXTLINE(cert-dcl21-cpp)
+ iter_t operator++(int) & noexcept { const iter_t tmp(*this); operator++(); return tmp; }
+
+ constexpr bool operator==(const iter_t& rhs) const noexcept { return p == rhs.p; }
+ constexpr bool operator!=(const iter_t& rhs) const noexcept { return p != rhs.p; }
+#if 0
+ constexpr LC& operator*() noexcept { return *static_cast<LC *>(p); }
+ constexpr LC* operator->() noexcept { return static_cast<LC *>(p); }
- constexpr iter_t begin() const noexcept { return iter_t(m_head); }
- constexpr iter_t end() const noexcept { return iter_t(nullptr); }
+ constexpr LC& operator*() const noexcept { return *static_cast<LC *>(p); }
+ constexpr LC* operator->() const noexcept { return static_cast<LC *>(p); }
+#else
+ constexpr LC* operator*() noexcept { return static_cast<LC *>(p); }
+ constexpr LC* operator->() noexcept { return static_cast<LC *>(p); }
- void push_front(LC *elem) noexcept
- {
- if (m_head)
- m_head->m_prev = elem;
- elem->m_next = m_head;
- elem->m_prev = nullptr;
- m_head = elem;
- }
-
- void push_back(LC *elem) noexcept
- {
- LC ** p(&m_head);
- LC * prev(nullptr);
- while (*p != nullptr)
+ constexpr LC* operator*() const noexcept { return static_cast<LC *>(p); }
+ constexpr LC* operator->() const noexcept { return static_cast<LC *>(p); }
+#endif
+ };
+
+ constexpr linked_list_t() noexcept : m_head(nullptr) {}
+
+ constexpr iter_t begin() const noexcept { return iter_t(m_head); }
+ constexpr iter_t end() const noexcept { return iter_t(nullptr); }
+
+ constexpr void push_front(element_t *elem) noexcept
{
- prev = *p;
- p = &((*p)->m_next);
+ elem->m_next = m_head;
+ elem->m_prev = nullptr;
+ if (m_head)
+ m_head->m_prev = elem;
+ m_head = elem;
}
- *p = elem;
- elem->m_prev = prev;
- elem->m_next = nullptr;
- }
- void remove(const LC *elem) noexcept
- {
- if (elem->m_prev)
- elem->m_prev->m_next = elem->m_next;
- else
- m_head = elem->m_next;
- if (elem->m_next)
- elem->m_next->m_prev = elem->m_prev;
- else
+ constexpr void push_back(element_t *elem) noexcept
{
- /* update tail */
+ element_t ** p(&m_head);
+ element_t * prev(nullptr);
+ while (*p != nullptr)
+ {
+ prev = *p;
+ p = &((*p)->m_next);
+ }
+ *p = elem;
+ elem->m_prev = prev;
+ elem->m_next = nullptr;
}
- }
- LC *front() const noexcept { return m_head; }
- void clear() noexcept { m_head = nullptr; }
- constexpr bool empty() const noexcept { return (m_head == nullptr); }
+ constexpr void remove(const element_t *elem) noexcept
+ {
+ if (elem->m_prev)
+ elem->m_prev->m_next = elem->m_next;
+ else
+ m_head = elem->m_next;
+ if (elem->m_next)
+ elem->m_next->m_prev = elem->m_prev;
+ else
+ {
+ // update tail
+ }
+ }
+
+ constexpr LC *front() const noexcept { return m_head; }
+ constexpr bool empty() const noexcept { return (m_head == nullptr); }
+ constexpr std::size_t size() const noexcept
+ {
+ std::size_t ret = 0;
+ element_t *p = m_head;
+ while (p != nullptr)
+ {
+ ret++;
+ p = p->m_next;
+ }
+ return ret;
+ }
+
+ constexpr void clear() noexcept
+ {
+ element_t *p(m_head);
+ while (p != nullptr)
+ {
+ element_t *n(p->m_next);
+ p->m_next = nullptr;
+ p->m_prev = nullptr;
+ p = n;
+ }
+ m_head = nullptr;
+ }
+
+ private:
+ element_t *m_head;
+ };
-private:
- LC *m_head;
-};
-#endif
} // namespace plib
-#endif /* PLISTS_H_ */
+#endif // PLISTS_H_