summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/util/coretmpl.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/util/coretmpl.h')
-rw-r--r--src/lib/util/coretmpl.h449
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