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.h673
1 files changed, 172 insertions, 501 deletions
diff --git a/src/lib/util/coretmpl.h b/src/lib/util/coretmpl.h
index 6c8ac39b45c..87f8cfbf09e 100644
--- a/src/lib/util/coretmpl.h
+++ b/src/lib/util/coretmpl.h
@@ -13,39 +13,22 @@
#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>
-
-// Generate a N-bit mask at compile time. N better be constant.
-// Works even for signed types
-
-template<typename T> constexpr T make_bitmask(unsigned int N)
-{
- return T((N < (8 * sizeof(T)) ? (std::make_unsigned_t<T>(1) << N) : std::make_unsigned_t<T>(0)) - 1);
-}
-
// ======================> simple_list
// a simple_list is a singly-linked list whose 'next' pointer is owned
// by the object
-template<class _ElementType>
+template<class ElementType>
class simple_list final
{
public:
@@ -53,36 +36,31 @@ public:
{
public:
typedef int difference_type;
- typedef _ElementType value_type;
- typedef _ElementType *pointer;
- typedef _ElementType &reference;
+ typedef ElementType value_type;
+ typedef ElementType *pointer;
+ typedef ElementType &reference;
typedef std::forward_iterator_tag iterator_category;
// construction/destruction
auto_iterator() noexcept : m_current(nullptr) { }
- auto_iterator(_ElementType *ptr) noexcept : m_current(ptr) { }
+ auto_iterator(ElementType *ptr) noexcept : m_current(ptr) { }
// required operator overloads
bool operator==(const auto_iterator &iter) const noexcept { return m_current == iter.m_current; }
bool operator!=(const auto_iterator &iter) const noexcept { return m_current != iter.m_current; }
- _ElementType &operator*() const noexcept { return *m_current; }
- _ElementType *operator->() const noexcept { return m_current; }
- // note that _ElementType::next() must not return a const ptr
+ ElementType &operator*() const noexcept { return *m_current; }
+ ElementType *operator->() const noexcept { return m_current; }
+ // note that ElementType::next() must not return a const ptr
auto_iterator &operator++() noexcept { m_current = m_current->next(); return *this; }
auto_iterator operator++(int) noexcept { auto_iterator result(*this); m_current = m_current->next(); return result; }
private:
// private state
- _ElementType *m_current;
+ ElementType *m_current;
};
// construction/destruction
- simple_list() noexcept
- : m_head(nullptr)
- , m_tail(nullptr)
- , m_count(0)
- {
- }
+ simple_list() noexcept { }
~simple_list() noexcept { reset(); }
// we don't support deep copying
@@ -90,18 +68,19 @@ public:
simple_list &operator=(const simple_list &) = delete;
// but we do support cheap swap/move
- simple_list(simple_list &&list) : simple_list() { operator=(std::move(list)); }
+ simple_list(simple_list &&list) noexcept { operator=(std::move(list)); }
simple_list &operator=(simple_list &&list)
{
using std::swap;
swap(m_head, list.m_head);
swap(m_tail, list.m_tail);
swap(m_count, list.m_count);
+ return *this;
}
// simple getters
- _ElementType *first() const noexcept { return m_head; }
- _ElementType *last() const noexcept { return m_tail; }
+ ElementType *first() const noexcept { return m_head; }
+ ElementType *last() const noexcept { return m_tail; }
int count() const noexcept { return m_count; }
bool empty() const noexcept { return m_count == 0; }
@@ -117,7 +96,7 @@ public:
}
// add the given object to the head of the list
- _ElementType &prepend(_ElementType &object) noexcept
+ ElementType &prepend(ElementType &object) noexcept
{
object.m_next = m_head;
m_head = &object;
@@ -128,13 +107,13 @@ public:
}
// add the given list to the head of the list
- void prepend_list(simple_list<_ElementType> &list) noexcept
+ void prepend_list(simple_list<ElementType> &list) noexcept
{
int count = list.count();
if (count == 0)
return;
- _ElementType *tail = list.last();
- _ElementType *head = list.detach_all();
+ ElementType *tail = list.last();
+ ElementType *head = list.detach_all();
tail->m_next = m_head;
m_head = head;
if (m_tail == nullptr)
@@ -143,7 +122,7 @@ public:
}
// add the given object to the tail of the list
- _ElementType &append(_ElementType &object) noexcept
+ ElementType &append(ElementType &object) noexcept
{
object.m_next = nullptr;
if (m_tail != nullptr)
@@ -155,13 +134,13 @@ public:
}
// add the given list to the tail of the list
- void append_list(simple_list<_ElementType> &list) noexcept
+ void append_list(simple_list<ElementType> &list) noexcept
{
int count = list.count();
if (count == 0)
return;
- _ElementType *tail = list.last();
- _ElementType *head = list.detach_all();
+ ElementType *tail = list.last();
+ ElementType *head = list.detach_all();
if (m_tail != nullptr)
m_tail->m_next = head;
else
@@ -171,7 +150,7 @@ public:
}
// insert the given object after a particular object (nullptr means prepend)
- _ElementType &insert_after(_ElementType &object, _ElementType *insert_after) noexcept
+ ElementType &insert_after(ElementType &object, ElementType *insert_after) noexcept
{
if (insert_after == nullptr)
return prepend(object);
@@ -184,11 +163,11 @@ public:
}
// insert the given object before a particular object (nullptr means append)
- _ElementType &insert_before(_ElementType &object, _ElementType *insert_before) noexcept
+ ElementType &insert_before(ElementType &object, ElementType *insert_before) noexcept
{
if (insert_before == nullptr)
return append(object);
- for (_ElementType **curptr = &m_head; *curptr != nullptr; curptr = &(*curptr)->m_next)
+ for (ElementType **curptr = &m_head; *curptr != nullptr; curptr = &(*curptr)->m_next)
if (*curptr == insert_before)
{
object.m_next = insert_before;
@@ -202,10 +181,10 @@ public:
}
// replace an item in the list at the same location, and remove it
- _ElementType &replace_and_remove(_ElementType &object, _ElementType &toreplace) noexcept
+ ElementType &replace_and_remove(ElementType &object, ElementType &toreplace) noexcept
{
- _ElementType *prev = nullptr;
- for (_ElementType *cur = m_head; cur != nullptr; prev = cur, cur = cur->m_next)
+ ElementType *prev = nullptr;
+ for (ElementType *cur = m_head; cur != nullptr; prev = cur, cur = cur->m_next)
if (cur == &toreplace)
{
if (prev != nullptr)
@@ -215,16 +194,16 @@ public:
if (m_tail == &toreplace)
m_tail = &object;
object.m_next = toreplace.m_next;
- global_free(&toreplace);
+ delete &toreplace;
return object;
}
return append(object);
}
// detach the head item from the list, but don't free its memory
- _ElementType *detach_head() noexcept
+ ElementType *detach_head() noexcept
{
- _ElementType *result = m_head;
+ ElementType *result = m_head;
if (result != nullptr)
{
m_head = result->m_next;
@@ -236,10 +215,10 @@ public:
}
// detach the given item from the list, but don't free its memory
- _ElementType &detach(_ElementType &object) noexcept
+ ElementType &detach(ElementType &object) noexcept
{
- _ElementType *prev = nullptr;
- for (_ElementType *cur = m_head; cur != nullptr; prev = cur, cur = cur->m_next)
+ ElementType *prev = nullptr;
+ for (ElementType *cur = m_head; cur != nullptr; prev = cur, cur = cur->m_next)
if (cur == &object)
{
if (prev != nullptr)
@@ -255,34 +234,34 @@ public:
}
// detach the entire list, returning the head, but don't free memory
- _ElementType *detach_all() noexcept
+ ElementType *detach_all() noexcept
{
- _ElementType *result = m_head;
+ ElementType *result = m_head;
m_head = m_tail = nullptr;
m_count = 0;
return result;
}
// remove the given object and free its memory
- void remove(_ElementType &object) noexcept
+ void remove(ElementType &object) noexcept
{
- global_free(&detach(object));
+ delete &detach(object);
}
// find an object by index in the list
- _ElementType *find(int index) const noexcept
+ ElementType *find(int index) const noexcept
{
- for (_ElementType *cur = m_head; cur != nullptr; cur = cur->m_next)
+ for (ElementType *cur = m_head; cur != nullptr; cur = cur->m_next)
if (index-- == 0)
return cur;
return nullptr;
}
// return the index of the given object in the list
- int indexof(const _ElementType &object) const noexcept
+ int indexof(const ElementType &object) const noexcept
{
int index = 0;
- for (_ElementType *cur = m_head; cur != nullptr; cur = cur->m_next)
+ for (ElementType *cur = m_head; cur != nullptr; cur = cur->m_next)
{
if (cur == &object)
return index;
@@ -293,49 +272,16 @@ public:
private:
// internal state
- _ElementType * m_head; // head of the singly-linked list
- _ElementType * m_tail; // tail of the singly-linked list
- int m_count; // number of objects in the list
-};
-
-
-// ======================> simple_list_wrapper
-
-// a simple_list_wrapper wraps an existing object with a next pointer so it
-// can live in a simple_list without requiring the object to have a next
-// pointer
-template<class _ObjectType>
-class simple_list_wrapper
-{
-public:
- template<class U> friend class simple_list;
-
- // construction/destruction
- simple_list_wrapper(_ObjectType *object)
- : m_next(nullptr),
- m_object(object) { }
-
- // operators
- operator _ObjectType *() { return m_object; }
- operator _ObjectType *() const { return m_object; }
- _ObjectType *operator *() { return m_object; }
- _ObjectType *operator *() const { return m_object; }
-
- // getters
- simple_list_wrapper *next() const { return m_next; }
- _ObjectType *object() const { return m_object; }
-
-private:
- // internal state
- simple_list_wrapper * m_next;
- _ObjectType * m_object;
+ ElementType * m_head = nullptr; // head of the singly-linked list
+ ElementType * m_tail = nullptr; // tail of the singly-linked list
+ int m_count = 0; // number of objects in the list
};
// ======================> fixed_allocator
// a fixed_allocator is a simple class that maintains a free pool of objects
-template<class _ItemType>
+template<class ItemType>
class fixed_allocator
{
// we don't support deep copying
@@ -347,24 +293,24 @@ public:
fixed_allocator() { }
// allocate a new item, either by recycling an old one, or by allocating a new one
- _ItemType *alloc()
+ ItemType *alloc()
{
- _ItemType *result = m_freelist.detach_head();
+ ItemType *result = m_freelist.detach_head();
if (result == nullptr)
- result = global_alloc(_ItemType);
+ result = new ItemType;
return result;
}
// reclaim an item by adding it to the free list
- void reclaim(_ItemType *item) { if (item != nullptr) m_freelist.append(*item); }
- void reclaim(_ItemType &item) { m_freelist.append(item); }
+ void reclaim(ItemType *item) { if (item != nullptr) m_freelist.append(*item); }
+ void reclaim(ItemType &item) { m_freelist.append(item); }
// reclaim all items from a list
- void reclaim_all(simple_list<_ItemType> &_list) { m_freelist.append_list(_list); }
+ void reclaim_all(simple_list<ItemType> &_list) { m_freelist.append_list(_list); }
private:
// internal state
- simple_list<_ItemType> m_freelist; // list of free objects
+ simple_list<ItemType> m_freelist; // list of free objects
};
@@ -450,383 +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);
- }
-
-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>
{
@@ -957,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> >;
@@ -975,24 +563,114 @@ constexpr typename std::enable_if_t<std::is_enum<E>::value && std::is_integral<T
}
-// useful functions to deal with bit shuffling
+/// \defgroup bitutils Useful functions for bit shuffling
+/// \{
+
+/// \brief Generate a right-aligned bit mask
+///
+/// Generates a right aligned mask of the specified width. Works with
+/// signed and unsigned integer types.
+/// \tparam T Desired output type.
+/// \tparam U Type of the input (generally resolved by the compiler).
+/// \param [in] n Width of the mask to generate in bits.
+/// \return Right-aligned mask of the specified width.
+
+template <typename T, typename U> constexpr T make_bitmask(U n)
+{
+ return T((n < (8 * sizeof(T)) ? (std::make_unsigned_t<T>(1) << n) : std::make_unsigned_t<T>(0)) - 1);
+}
+
+
+/// \brief Extract a single bit from an integer
+///
+/// Extracts a single bit from an integer into the least significant bit
+/// position.
+///
+/// \param [in] x The integer to extract the bit from.
+/// \param [in] n The bit to extract, where zero is the least
+/// significant bit of the input.
+/// \return Zero if the specified bit is unset, or one if it is set.
+/// \sa bitswap
template <typename T, typename U> constexpr T BIT(T x, U n) noexcept { return (x >> n) & T(1); }
-template <typename T, typename U> constexpr T bitswap(T val, U b) noexcept { return BIT(val, b) << 0U; }
+/// \brief Extract a bit field from an integer
+///
+/// Extracts and right-aligns a bit field from an integer.
+///
+/// \param [in] x The integer to extract the bit field from.
+/// \param [in] n The least significant bit position of the field to
+/// extract, where zero is the least significant bit of the input.
+/// \param [in] w The width of the field to extract in bits.
+/// \return The field [n..(n+w-1)] from the input.
+/// \sa bitswap
+template <typename T, typename U, typename V> constexpr T BIT(T x, U n, V w)
+{
+ return (x >> n) & make_bitmask<T>(w);
+}
+
+
+/// \brief Extract bits in arbitrary order
+///
+/// Extracts bits from an integer. Specify the bits in the order they
+/// should be arranged in the output, from most significant to least
+/// significant. The extracted bits will be packed into a right-aligned
+/// field in the output.
+///
+/// \param [in] val The integer to extract bits from.
+/// \param [in] b The first bit to extract from the input
+/// extract, where zero is the least significant bit of the input.
+/// This bit will appear in the most significant position of the
+/// right-aligned output field.
+/// \param [in] c The remaining bits to extract, where zero is the
+/// least significant bit of the input.
+/// \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);
}
-// explicit version that checks number of bit position arguments
-template <unsigned B, typename T, typename... U> T bitswap(T val, U... b) noexcept
+
+/// \brief Extract bits in arbitrary order with explicit count
+///
+/// Extracts bits from an integer. Specify the bits in the order they
+/// should be arranged in the output, from most significant to least
+/// significant. The extracted bits will be packed into a right-aligned
+/// field in the output. The number of bits to extract must be supplied
+/// as a template argument.
+///
+/// A compile error will be generated if the number of bit positions
+/// supplied does not match the specified number of bits to extract, or
+/// if the output type is too small to hold the extracted bits. This
+/// guards against some simple errors.
+///
+/// \tparam B The number of bits to extract. Must match the number of
+/// bit positions supplied.
+/// \param [in] val The integer to extract bits from.
+/// \param [in] b Bits to extract, where zero is the least significant
+/// bit of the input. Specify bits in the order they should appear in
+/// the output field, from most significant to least significant.
+/// \return The extracted bits packed into a right-aligned field.
+template <unsigned B, typename T, typename... U> constexpr T bitswap(T val, U... b) noexcept
{
static_assert(sizeof...(b) == B, "wrong number of bits");
static_assert((sizeof(std::remove_reference_t<T>) * 8) >= B, "return type too small for result");
return bitswap(val, b...);
}
+/// \}
+
+
+// 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>
@@ -1002,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;
@@ -1021,6 +692,6 @@ inline void reduce_fraction(M &num, N &den)
}
}
-}; // namespace util
+} // namespace util
#endif // MAME_UTIL_CORETMPL_H