diff options
Diffstat (limited to 'src/lib/netlist/plib/plists.h')
-rw-r--r-- | src/lib/netlist/plib/plists.h | 480 |
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_ |