diff options
Diffstat (limited to 'src/lib/util/coretmpl.h')
-rw-r--r-- | src/lib/util/coretmpl.h | 449 |
1 files changed, 36 insertions, 413 deletions
diff --git a/src/lib/util/coretmpl.h b/src/lib/util/coretmpl.h index a06c4fb8a46..55313a4a0f5 100644 --- a/src/lib/util/coretmpl.h +++ b/src/lib/util/coretmpl.h @@ -13,24 +13,16 @@ #pragma once #include "osdcomm.h" -#include "osdcore.h" -#include "corealloc.h" +#include "vecstream.h" #include <array> -#include <cassert> #include <cstddef> -#include <functional> -#include <initializer_list> #include <iterator> -#include <list> -#include <map> -#include <memory> -#include <set> +#include <numeric> #include <stdexcept> -#include <tuple> +#include <string_view> #include <type_traits> #include <utility> -#include <vector> // ======================> simple_list @@ -404,384 +396,6 @@ private: }; -// LRU cache that behaves like std::map with differences: -// * drops least-recently used items if necessary on insert to prevent size from exceeding max_size -// * operator[], at, insert, emplace and find freshen existing entries -// * iterates from least- to most-recently used rather than in order by key -// * iterators to dropped items are invalidated -// * not all map interfaces implemented -// * copyable and swappable but not movable -// * swap may invalidate past-the-end iterator, other iterators refer to new container -template <typename Key, typename T, typename Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key const, T> > > -class lru_cache_map -{ -private: - class iterator_compare; - typedef std::list<std::pair<Key const, T>, Allocator> value_list; - typedef typename std::allocator_traits<Allocator>::template rebind_alloc<typename value_list::iterator> iterator_allocator_type; - typedef std::set<typename value_list::iterator, iterator_compare, iterator_allocator_type> iterator_set; - - class iterator_compare - { - public: - typedef std::true_type is_transparent; - iterator_compare(Compare const &comp) : m_comp(comp) { } - iterator_compare(iterator_compare const &that) = default; - iterator_compare(iterator_compare &&that) = default; - Compare key_comp() const { return m_comp; } - iterator_compare &operator=(iterator_compare const &that) = default; - iterator_compare &operator=(iterator_compare &&that) = default; - bool operator()(typename value_list::iterator const &lhs, typename value_list::iterator const &rhs) const { return m_comp(lhs->first, rhs->first); } - template <typename K> bool operator()(typename value_list::iterator const &lhs, K const &rhs) const { return m_comp(lhs->first, rhs); } - template <typename K> bool operator()(K const &lhs, typename value_list::iterator const &rhs) const { return m_comp(lhs, rhs->first); } - private: - Compare m_comp; - }; - -public: - typedef Key key_type; - typedef T mapped_type; - typedef std::pair<Key const, T> value_type; - typedef typename value_list::size_type size_type; - typedef typename value_list::difference_type difference_type; - typedef Compare key_compare; - typedef Allocator allocator_type; - typedef value_type &reference; - typedef value_type const &const_reference; - typedef typename std::allocator_traits<Allocator>::pointer pointer; - typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer; - typedef typename value_list::iterator iterator; - typedef typename value_list::const_iterator const_iterator; - typedef typename value_list::reverse_iterator reverse_iterator; - typedef typename value_list::const_reverse_iterator const_reverse_iterator; - - explicit lru_cache_map(size_type max_size) - : lru_cache_map(max_size, key_compare()) - { - } - lru_cache_map(size_type max_size, key_compare const &comp, allocator_type const &alloc = allocator_type()) - : m_max_size(max_size) - , m_size(0U) - , m_elements(alloc) - , m_mapping(iterator_compare(comp), iterator_allocator_type(alloc)) - { - assert(0U < m_max_size); - } - lru_cache_map(lru_cache_map const &that) - : m_max_size(that.m_max_size) - , m_size(that.m_size) - , m_elements(that.m_elements) - , m_mapping(that.m_mapping.key_comp(), that.m_mapping.get_allocator()) - { - for (iterator it = m_elements.begin(); it != m_elements.end(); ++it) - m_mapping.insert(it); - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - } - - allocator_type get_allocator() const { return m_elements.get_allocator(); } - - iterator begin() { return m_elements.begin(); } - const_iterator begin() const { return m_elements.cbegin(); } - const_iterator cbegin() const { return m_elements.cbegin(); } - iterator end() { return m_elements.end(); } - const_iterator end() const { return m_elements.cend(); } - const_iterator cend() const { return m_elements.cend(); } - reverse_iterator rbegin() { return m_elements.rbegin(); } - const_reverse_iterator rbegin() const { return m_elements.crbegin(); } - const_reverse_iterator crbegin() const { return m_elements.crbegin(); } - reverse_iterator rend() { return m_elements.end(); } - const_reverse_iterator rend() const { return m_elements.crend(); } - const_reverse_iterator crend() const { return m_elements.crend(); } - - bool empty() const { return !m_size; } - size_type size() const { return m_size; } - size_type max_size() const { return m_max_size; } - - mapped_type &operator[](key_type const &key) - { - typename iterator_set::iterator existing(m_mapping.lower_bound(key)); - if ((m_mapping.end() != existing) && !m_mapping.key_comp()(key, *existing)) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return (*existing)->second; - } - make_space(existing); - iterator const inserted(m_elements.emplace(m_elements.end(), std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>())); - m_mapping.insert(existing, inserted); - ++m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return inserted->second; - } - mapped_type &operator[](key_type &&key) - { - typename iterator_set::iterator existing(m_mapping.lower_bound(key)); - if ((m_mapping.end() != existing) && !m_mapping.key_comp()(key, *existing)) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return (*existing)->second; - } - make_space(existing); - iterator const inserted(m_elements.emplace(m_elements.end(), std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>())); - m_mapping.insert(existing, inserted); - ++m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return inserted->second; - } - mapped_type &at(key_type const &key) - { - typename iterator_set::iterator existing(m_mapping.find(key)); - if (m_mapping.end() != existing) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return (*existing)->second; - } - else - { - throw std::out_of_range("lru_cache_map::at"); - } - } - mapped_type const &at(key_type const &key) const - { - typename iterator_set::iterator existing(m_mapping.find(key)); - if (m_mapping.end() != existing) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return (*existing)->second; - } - else - { - throw std::out_of_range("lru_cache_map::at"); - } - } - - void clear() - { - m_size = 0U; - m_elements.clear(); - m_mapping.clear(); - } - std::pair<iterator, bool> insert(value_type const &value) - { - typename iterator_set::iterator existing(m_mapping.lower_bound(value.first)); - if ((m_mapping.end() != existing) && !m_mapping.key_comp()(value.first, *existing)) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return std::pair<iterator, bool>(*existing, false); - } - make_space(existing); - iterator const inserted(m_elements.emplace(m_elements.end(), value)); - m_mapping.insert(existing, inserted); - ++m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return std::pair<iterator, bool>(inserted, true); - } - std::pair<iterator, bool> insert(value_type &&value) - { - typename iterator_set::iterator existing(m_mapping.lower_bound(value.first)); - if ((m_mapping.end() != existing) && !m_mapping.key_comp()(value.first, *existing)) - { - m_elements.splice(m_elements.cend(), m_elements, *existing); - return std::pair<iterator, bool>(*existing, false); - } - make_space(existing); - iterator const inserted(m_elements.emplace(m_elements.end(), std::move(value))); - m_mapping.insert(existing, inserted); - ++m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return std::pair<iterator, bool>(inserted, true); - } - template <typename P> - std::enable_if_t<std::is_constructible<value_type, P>::value, std::pair<iterator, bool> > insert(P &&value) - { - return emplace(std::forward<P>(value)); - } - template <typename InputIt> - void insert(InputIt first, InputIt last) - { - while (first != last) - { - insert(*first); - ++first; - } - } - void insert(std::initializer_list<value_type> ilist) - { - for (value_type const &value : ilist) - insert(value); - } - template <typename... Params> - std::pair<iterator, bool> emplace(Params &&... args) - { - // TODO: is there a more efficient way than depending on value_type being efficiently movable? - return insert(value_type(std::forward<Params>(args)...)); - } - iterator erase(const_iterator pos) - { - m_mapping.erase(m_elements.erase(pos, pos)); - iterator const result(m_elements.erase(pos)); - --m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return result; - } - iterator erase(const_iterator first, const_iterator last) - { - iterator pos(m_elements.erase(first, first)); - while (pos != last) - { - m_mapping.erase(pos); - pos = m_elements.erase(pos); - --m_size; - } - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return pos; - } - size_type erase(key_type const &key) - { - typename iterator_set::iterator const found(m_mapping.find(key)); - if (m_mapping.end() == found) - { - return 0U; - } - else - { - m_elements.erase(*found); - m_mapping.erase(found); - --m_size; - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return 1U; - } - } - void swap(lru_cache_map &that) - { - using std::swap; - swap(m_max_size, that.m_max_size); - swap(m_size, that.m_size); - swap(m_elements, that.m_elements); - swap(m_mapping, that.m_mapping); - } - - size_type count(key_type const &key) const - { - // TODO: perhaps this should freshen an element - return m_mapping.count(key); - } - template <typename K> - size_type count(K const &x) const - { - // FIXME: should only enable this overload if Compare::is_transparent - // TODO: perhaps this should freshen an element - return m_mapping.count(x); - } - iterator find(key_type const &key) - { - typename iterator_set::const_iterator const found(m_mapping.find(key)); - if (m_mapping.end() == found) - { - return m_elements.end(); - } - else - { - m_elements.splice(m_elements.cend(), m_elements, *found); - return *found; - } - } - iterator find(key_type const &key) const - { - typename iterator_set::const_iterator const found(m_mapping.find(key)); - if (m_mapping.end() == found) - { - return m_elements.end(); - } - else - { - m_elements.splice(m_elements.cend(), m_elements, *found); - return *found; - } - } - template <typename K> - iterator find(K const &x) - { - // FIXME: should only enable this overload if Compare::is_transparent - typename iterator_set::const_iterator const found(m_mapping.find(x)); - if (m_mapping.end() == found) - { - return m_elements.end(); - } - else - { - m_elements.splice(m_elements.cend(), m_elements, *found); - return *found; - } - } - template <typename K> - iterator find(K const &x) const - { - // FIXME: should only enable this overload if Compare::is_transparent - typename iterator_set::const_iterator const found(m_mapping.find(x)); - if (m_mapping.end() == found) - { - return m_elements.end(); - } - else - { - m_elements.splice(m_elements.cend(), m_elements, *found); - return *found; - } - } - - key_compare key_comp() const - { - return m_mapping.key_comp().key_comp(); - } - - lru_cache_map &operator=(lru_cache_map const &that) - { - m_max_size = that.m_max_size; - m_size = that.m_size; - m_elements = that.m_elements; - m_mapping.clear(); - for (iterator it = m_elements.begin(); it != m_elements.end(); ++it) - m_mapping.insert(it); - assert(m_elements.size() == m_size); - assert(m_mapping.size() == m_size); - return *this; - } - -private: - void make_space(typename iterator_set::iterator &existing) - { - while (m_max_size <= m_size) - { - if ((m_mapping.end() != existing) && (m_elements.begin() == *existing)) - existing = m_mapping.erase(existing); - else - m_mapping.erase(m_elements.begin()); - m_elements.erase(m_elements.begin()); - --m_size; - } - } - - size_type m_max_size; - size_type m_size; - mutable value_list m_elements; - iterator_set m_mapping; -}; - -template <typename Key, typename T, typename Compare, class Allocator> -void swap(lru_cache_map<Key, T, Compare, Allocator> &lhs, lru_cache_map<Key, T, Compare, Allocator> &rhs) -{ - lhs.swap(rhs); -} - - template <typename T, std::size_t N, bool WriteWrap = false, bool ReadWrap = WriteWrap> class fifo : protected std::array<T, N> { @@ -912,6 +526,25 @@ private: }; +// extract a string_view from an ovectorstream buffer +template <typename CharT, typename Traits, typename Allocator> +std::basic_string_view<CharT, Traits> buf_to_string_view(basic_ovectorstream<CharT, Traits, Allocator> &stream) +{ + // this works on the assumption that the value tellp returns is the same both before and after vec is called + return std::basic_string_view<CharT, Traits>(&stream.vec()[0], stream.tellp()); +} + + +// For declaring an array of the same dimensions as another array (including multi-dimensional arrays) +template <typename T, typename U> struct equivalent_array_or_type { typedef T type; }; +template <typename T, typename U, std::size_t N> struct equivalent_array_or_type<T, U[N]> { typedef typename equivalent_array_or_type<T, U>::type type[N]; }; +template <typename T, typename U> using equivalent_array_or_type_t = typename equivalent_array_or_type<T, U>::type; +template <typename T, typename U> struct equivalent_array { }; +template <typename T, typename U, std::size_t N> struct equivalent_array<T, U[N]> { typedef equivalent_array_or_type_t<T, U> type[N]; }; +template <typename T, typename U> using equivalent_array_t = typename equivalent_array<T, U>::type; +#define EQUIVALENT_ARRAY(a, T) util::equivalent_array_t<T, std::remove_reference_t<decltype(a)> > + + template <typename E> using enable_enum_t = typename std::enable_if_t<std::is_enum<E>::value, typename std::underlying_type_t<E> >; @@ -977,20 +610,6 @@ template <typename T, typename U, typename V> constexpr T BIT(T x, U n, V w) } -/// \brief Extract and right-align a single bit field -/// -/// This overload is used to terminate a recursive template -/// implementation. It is functionally equivalent to the BIT -/// function for extracting a single bit. -/// -/// \param [in] val The integer to extract the bit from. -/// \param [in] b The bit to extract, where zero is the least -/// significant bit of the input. -/// \return The specified bit of the input extracted to the least -/// significant position. -template <typename T, typename U> constexpr T bitswap(T val, U b) noexcept { return BIT(val, b) << 0U; } - - /// \brief Extract bits in arbitrary order /// /// Extracts bits from an integer. Specify the bits in the order they @@ -1008,7 +627,10 @@ template <typename T, typename U> constexpr T bitswap(T val, U b) noexcept { ret /// \return The extracted bits packed into a right-aligned field. template <typename T, typename U, typename... V> constexpr T bitswap(T val, U b, V... c) noexcept { - return (BIT(val, b) << sizeof...(c)) | bitswap(val, c...); + if constexpr (sizeof...(c) > 0U) + return (BIT(val, b) << sizeof...(c)) | bitswap(val, c...); + else + return BIT(val, b); } @@ -1042,6 +664,14 @@ template <unsigned B, typename T, typename... U> T bitswap(T val, U... b) noexce /// \} +// utility function for sign-extending values of arbitrary width +template <typename T, typename U> +constexpr std::make_signed_t<T> sext(T value, U width) noexcept +{ + return std::make_signed_t<T>(value << (8 * sizeof(value) - width)) >> (8 * sizeof(value) - width); +} + + // constexpr absolute value of an integer template <typename T> constexpr std::enable_if_t<std::is_signed<T>::value, T> iabs(T v) noexcept @@ -1050,18 +680,11 @@ constexpr std::enable_if_t<std::is_signed<T>::value, T> iabs(T v) noexcept } -// returns greatest common divisor of a and b using the Euclidean algorithm -template <typename M, typename N> -constexpr std::common_type_t<M, N> euclid_gcd(M a, N b) -{ - return b ? euclid_gcd(b, a % b) : a; -} - // reduce a fraction template <typename M, typename N> inline void reduce_fraction(M &num, N &den) { - auto const div(euclid_gcd(num, den)); + auto const div(std::gcd(num, den)); if (div) { num /= div; @@ -1069,6 +692,6 @@ inline void reduce_fraction(M &num, N &den) } } -}; // namespace util +} // namespace util #endif // MAME_UTIL_CORETMPL_H |