From 32d57d7713250c58a85b2ac094f0bfee429f2fc4 Mon Sep 17 00:00:00 2001 From: Alex Ainscow Date: Tue, 11 Feb 2025 10:51:40 +0000 Subject: [PATCH] common: bitset_set and mini_flat_map The bitset_set is compile-time-fixed size bitmap, which can be accessed using a std::set-like iterator. The mini_flat_map is similar to a boost::flat_map, except with more restrictions on the size and key, allowing it to make better use of vectors. Both have the restriction that the key must be unambiguously castable to/from a small integer. The mini_flat_map has the additional restriction, that the size must be known at construction time. Signed-off-by: Alex Ainscow --- src/common/bitset_set.h | 449 +++++++++++++++++++++++ src/common/mini_flat_map.h | 493 ++++++++++++++++++++++++++ src/test/common/CMakeLists.txt | 14 + src/test/common/test_bitset_set.cc | 184 ++++++++++ src/test/common/test_mini_flat_map.cc | 151 ++++++++ 5 files changed, 1291 insertions(+) create mode 100644 src/common/bitset_set.h create mode 100644 src/common/mini_flat_map.h create mode 100644 src/test/common/test_bitset_set.cc create mode 100644 src/test/common/test_mini_flat_map.cc diff --git a/src/common/bitset_set.h b/src/common/bitset_set.h new file mode 100644 index 0000000000000..0b19b0041e01d --- /dev/null +++ b/src/common/bitset_set.h @@ -0,0 +1,449 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +/* The standard bitset library does not behave like a "std::set", making it + * hard to use as a drop-in replacement. This templated class is intended to + * behave like a std::set() with the restriction that it can only store values + * less than N. The contents is stored as a bitset for efficiency and there are + * some extensions (such as insert_range) that exploit the implementation, + * however the main intent is that this is a drop-in replacement for std::set. + * + * The Key must cast to/from int8_t unambiguously and support the pre-increment + * operator. + */ + +#pragma once +#include + +#include "include/buffer.h" + +template +concept ExplicitlyCastableToOrFrom = requires(KeyT key, IntT v) { IntT(key); KeyT(v); }; + +template +requires(ExplicitlyCastableToOrFrom && NumBitsV % (sizeof(uint64_t) * CHAR_BIT) == 0 && NumBitsV > 0) +class bitset_set { + static constexpr const inline size_t bits_per_uint64_t = sizeof(uint64_t) * CHAR_BIT; + static constexpr const inline size_t word_count = NumBitsV / bits_per_uint64_t; + static constexpr const inline size_t max_bits = NumBitsV; + + // end_pos is permitted to wrap (e.g for int8_t: NumBitsV=128 -> end_pos=-128 ) + static constexpr const inline KeyT end_pos = static_cast(max_bits); + + // Not possible to create a non-const iterator! + public: + class const_iterator { + const bitset_set *set; + KeyT pos; + + public: + using difference_type = std::int64_t; + + const_iterator() : set(nullptr), pos(0) { + } + + const_iterator(const bitset_set *_set, size_t _pos) : set(_set), pos(_pos) { + } + + const_iterator(const bitset_set *_set, KeyT _pos) : set(_set), pos(_pos) { + } + + const_iterator(const bitset_set *_set) : set(_set), pos(end_pos) { + for (size_t i = 0; i < word_count; ++i) { + size_t p = std::countr_zero(set->words[i]); + if (p != bits_per_uint64_t) { + pos = (i * bits_per_uint64_t) + p; + break; + } + } + } + + const_iterator &operator++() { + uint64_t v; + size_t i = (int(pos) + 1) / bits_per_uint64_t; + int bit = (int(pos) + 1) % bits_per_uint64_t; + while (i < word_count) { + if (bit == bits_per_uint64_t) { + v = set->words[i]; + } else { + v = set->words[i] & -1ULL << bit; + } + bit = std::countr_zero(v); + if (bit != bits_per_uint64_t) { + pos = (i * bits_per_uint64_t) + bit; + return *this; + } + ++i; + } + pos = end_pos; + return *this; + } + + const_iterator operator++(int) { + const_iterator tmp(*this); + ++(*this); + return tmp; + } + + bool operator==(const const_iterator &rhs) const { + return int(pos) == int(rhs.pos); + } + + bool operator!=(const const_iterator &rhs) const { + return !operator==(rhs); + } + + const KeyT &operator*() const { + return pos; + } + }; + + static_assert(std::input_or_output_iterator); + + private: + std::array words; + const_iterator _end; + + public: + + static unsigned int unsigned_cast(KeyT const k) { + int8_t i = static_cast(k); + return static_cast(i); + } + + /** default constructor */ + bitset_set() : _end(this, end_pos) { + clear(); + } + + /** Copy constructor */ + bitset_set(const bitset_set &other) : _end(this, end_pos) { + copy(other); + } + + /** Move constructor (copies) */ + bitset_set(bitset_set &&other) noexcept : bitset_set(other) { + } + + /** Construct from compatible iterators */ + template + bitset_set(const InputIt first, const InputIt last) : bitset_set() { + for (InputIt it = first; it != last; ++it) { + emplace(*it); + } + } + + /** Constructor for initializer lists (mini_flat_map{1,2}) */ + bitset_set(const std::initializer_list init) + : bitset_set(init.begin(), init.end()) { + } + + /** Convenience utility for converting from a std::set */ + bitset_set(const std::set &std_set) + : bitset_set(std_set.begin(), std_set.end()) { + } + + /** Convenience utility for converting from a std::set */ + bitset_set(const std::set &std_set) + : bitset_set(std_set.begin(), std_set.end()) { + } + + /** insert k into set. */ + void insert(const KeyT k) { + ceph_assert( unsigned_cast(k) < max_bits); + ceph_assert(int(k) >= 0); + words[int(k) / bits_per_uint64_t] |= 1ULL << (int(k) % bits_per_uint64_t); + } + + /** insert k into set. */ + void insert(const bitset_set &other) { + for (unsigned i = 0; i < word_count; ++i) { + words[i] |= other.words[i]; + } + } + + /* Emplace key. Unusually this is LESS efficient than insert, since the key + * must be constructed, so the int value can be inserted. The key is + * immediately discarded. + * + * It is provided for compatibility with std::set, + * + * Where possible, insert should be used rather than emplace. + */ + template + std::pair emplace(Args &&... args) { + const KeyT k(args...); + bool add = !contains(k); + if (add) { + insert(k); + } + return std::make_pair(const_iterator(this, k), add); + } + + /** erase key from set. Unlike std::set does not return anything */ + void erase(const KeyT k) { + ceph_assert(unsigned_cast(k) < max_bits); + ceph_assert(int(k) >= 0); + words[int(k) / bits_per_uint64_t] &= ~(1ULL << (int(k) % bits_per_uint64_t)); + } + + /** Efficiently insert a range of values. When N is small, this is + * essentially an O(1) algorithm, although technically it is O(N) + */ + void insert_range(const KeyT start, int length) { + unsigned start_word = int(start) / bits_per_uint64_t; + // This is not an off-by-one error. Conventionally this would have length + // - 1, but the logic below is simpler with it as follows. + unsigned end_word = (int(start) + length) / bits_per_uint64_t; + ceph_assert(end_word < word_count + 1); + + if (start_word == end_word) { + words[start_word] |= + ((1ULL << length) - 1) << (int(start) % bits_per_uint64_t); + } else { + words[start_word] |= -1ULL << (int(start) % bits_per_uint64_t); + while (++start_word < end_word) { + words[start_word] = -1ULL; + } + if (end_word < word_count) { + words[end_word] |= + (1ULL << ((int(start) + length) % bits_per_uint64_t)) - 1; + } + } + } + + /** Efficiently erase a range of values. When N is small, this is + * essentially an O(1) algorithm, although technically it is O(N) + */ + void erase_range(const KeyT start, int length) { + unsigned start_word = int(start) / bits_per_uint64_t; + // This is not an off-by-one error. Conventionally this would have length + // - 1, but the logic below is simpler with it as follows. + unsigned end_word = (int(start) + length) / bits_per_uint64_t; + ceph_assert(0 <= end_word && end_word < word_count + 1); + + if (start_word == end_word) { + words[start_word] &= + ~(((1ULL << length) - 1) << (int(start) % bits_per_uint64_t)); + } else { + words[start_word] &= ~(-1ULL << (int(start) % bits_per_uint64_t)); + while (++start_word < end_word) { + words[start_word] = 0; + } + if (end_word < word_count) { + words[end_word] &= + ~((1ULL << ((int(start) + length) % bits_per_uint64_t)) - 1); + } + } + } + + /** Clear all entries from list */ + void clear() { + for (size_t i = 0; i < word_count; ++i) { + words[i] = 0; + } + } + + /** @return true if there are no keys in the container */ + bool empty() const { + bool empty = true; + for (size_t i = 0; i < word_count; ++i) { + if (words[i] != 0) { + empty = false; + break; + } + } + return empty; + } + + /** @return true if the container contains Key k. */ + bool contains(KeyT k) const { + ceph_assert(unsigned_cast(k) < max_bits); + ceph_assert(int(k) >= 0); + return (words[int(k) / bits_per_uint64_t] + & 1ULL << (int(k) % bits_per_uint64_t)); + } + + /** @return the count of matching keys in the container. Either returns 0 or 1 + */ + int count(KeyT k) const { + return contains(k) ? 1 : 0; + } + + /** @return a const_iterator to the specified key, or end if it does not + * exist. O(1) complexity. + */ + const_iterator find(const KeyT &k) const { + if (contains(k)) { + return const_iterator(this, k); + } + return end(); + } + + /** @return number of keys in the container. O(1) complexity on most + * modern CPUs. + */ + size_t size() const { + size_t count = 0; + for (size_t i = 0; i < word_count; ++i) { + count += std::popcount(words[i]); + } + return count; + } + + /** @return maximum size of set */ + constexpr size_t max_size() const { + return max_bits; + } + + /** Utility for encode/decode to allow serialisations */ + void bound_encode(size_t &p) const { + for (size_t i = 0; i < word_count; ++i) { + denc_varint(words[i], p); + } + } + + /** Utility for encode/decode to allow serialisations */ + void encode(ceph::buffer::list::contiguous_appender &bl) const { + for (size_t i = 0; i < word_count; ++i) { + denc_varint(words[i], bl); + } + } + + /** Utility for encode/decode to allow serialisations */ + void decode(ceph::buffer::ptr::const_iterator &bp) { + for (size_t i = 0; i < word_count; ++i) { + denc_varint(words[i], bp); + } + } + + /** @return begin const_iterator. There is no non-const iterator */ + const_iterator begin() const { + return const_iterator(this); + } + + /** @return begin const_iterator. There is no non-const iterator */ + const_iterator cbegin() const { + return begin(); + } + + /** @return begin const_iterator. There is no non-const iterator */ + const_iterator end() const { + return _end; + } + + /** @return begin const_iterator. There is no non-const iterator */ + const_iterator cend() const { + return _end; + } + + /** Utility for implemting copy operators. Not intented to be used + * externally, although it is safe to do so + */ + void copy(const bitset_set &other) { + for (size_t i = 0; i < word_count; ++i) { + words[i] = other.words[i]; + } + } + + /** Assign-with-copy operator */ + bitset_set &operator=(const bitset_set &other) { + if (&other != this) { + copy(other); + } + return *this; + } + + /** Assign with move operator */ + bitset_set &operator=(bitset_set &&other) noexcept { + if (&other != this) { + copy(other); + } + return *this; + } + + /** Swap contents with other. */ + void swap(bitset_set &other) noexcept { + for (size_t i = 0; i < word_count; ++i) { + uint64_t tmp = other.words[i]; + other.words[i] = words[i]; + words[i] = tmp; + } + } + + /** Returns true if other contains a subset of the keys in this container. + * + * Useful to replace std::includes if comparing complete sets + */ + bool includes(const bitset_set &other) const { + for (size_t i = 0; i < word_count; ++i) { + if ((words[i] & other.words[i]) != other.words[i]) { + return false; + } + } + return true; + } + + /** Standard copy operator */ + friend bool operator==(const bitset_set &lhs, const bitset_set &rhs) { + for (size_t i = 0; i < word_count; ++i) { + if (lhs.words[i] != rhs.words[i]) { + return false; + } + } + return true; + } + + /** Standard ostream operator */ + friend std::ostream &operator<<(std::ostream &lhs, const bitset_set &rhs) { + unsigned int c = 0; + lhs << "{"; + for (auto &&k : rhs) { + lhs << k; + c++; + if (c < rhs.size()) { + lhs << ","; + } + } + lhs << "}"; + return lhs; + } + + /** returns a bitset_set with the elements from lhs which are not found in rhs + * + * Useful to replace calls to std::difference which looked at the complete + * sets. + */ + static bitset_set difference(const bitset_set &lhs, const bitset_set &rhs) { + bitset_set res; + for (size_t i = 0; i < word_count; ++i) { + res.words[i] = lhs.words[i] & ~rhs.words[i]; + } + return res; + } + + /** returns a bitset_set with the elements from lhs which are found in rhs + * + * Useful to replace calls to std::intersection which looked at the complete + * sets. + */ + static bitset_set intersection(const bitset_set &lhs, const bitset_set &rhs) { + bitset_set res; + for (size_t i = 0; i < word_count; ++i) { + res.words[i] = lhs.words[i] & rhs.words[i]; + } + return res; + } + + /** Spaceship operator! Woosh... */ + friend std::strong_ordering operator<=>(const bitset_set &lhs, + const bitset_set &rhs) { + for (size_t i = 0; i < word_count; ++i) { + if (lhs.words[i] != rhs.words[i]) { + return lhs.words[i] <=> rhs.words[i]; + } + } + + return std::strong_ordering::equal; + } +}; diff --git a/src/common/mini_flat_map.h b/src/common/mini_flat_map.h new file mode 100644 index 0000000000000..931326f014821 --- /dev/null +++ b/src/common/mini_flat_map.h @@ -0,0 +1,493 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#pragma once + +#include +#include +#include +#include +#include + + +/* This class struct provides an API similar to std::map, but with the + * restriction that "Key" must cast to/from IntT without ambiguity. For + * example, the key could be a simple wrapper for an int8_t, used to provide + * some type safety. Additionally, the constructor must be passed the max + * value of the key, referred to as max_size. + * + * Signing: This library allows for IntT to be signed OR unsigned. If a signed + * type is used, then only POSITIVE values of KeyT are permitted in the map. + * + * The structure is a vector of optionals, indexed by the key. This therefore + * provides O(1) lookup, with an extremely low constant overhead. The size + * reflects the number of populated optionals, which is tracked independently. + * + * This was written generically, but with a single purpose in mind (in Erasure + * Coding), so the interface is not as complete as it could be. + */ +template +requires(ExplicitlyCastableToOrFrom) +class mini_flat_map { + using vector_type = std::optional; + using value_type = std::pair; + + static unsigned int unsigned_cast(KeyT const k) { + IntT i = static_cast(k); + return static_cast(i); + } + + void range_check(KeyT const k) const { + IntT i_s = static_cast(k); + unsigned int i_u = static_cast(i_s); + ceph_assert(0 <= i_s && i_u < max_size()); + } + + public: + template + class _iterator { + friend class mini_flat_map; + using mini_flat_map_p = std::conditional_t; + using value_type = std::conditional_t, + std::pair>; + + mini_flat_map_p map; + std::optional value; + KeyT key; + + void progress() { + while (unsigned_cast(key) < map->data.size() && !map->_at(key)) { + key = KeyT(static_cast(key) + 1); + } + + if (unsigned_cast(key) < map->data.size()) { + value.emplace(key, *(map->_at(key))); + } + } + + public: + using difference_type = std::ptrdiff_t; + + _iterator(mini_flat_map_p map) : map(map), key(0) { + progress(); + } + + _iterator(mini_flat_map_p map, KeyT key) : map(map), key(key) { + if (unsigned_cast(key) < map->data.size()) { + value.emplace(key, *map->_at(key)); + } else { + ceph_assert(unsigned_cast(key) == map->data.size()); // end + } + } + + // Only for end constructor. + _iterator(mini_flat_map_p map, size_t map_size) : map(map), key(map_size) { + ceph_assert(map_size == map->data.size()); + } + + _iterator &operator++() { + key = KeyT(static_cast(key) + 1); + progress(); + return *this; + } + + _iterator operator++(int) { + _iterator tmp(*this); + this->operator++(); + return tmp; + } + + bool operator==(const _iterator &other) const { + return key == other.key && map == other.map; + } + + value_type &operator*() { + return *value; + } + + value_type *operator->() { + return value.operator->(); + } + + _iterator &operator=(const _iterator &other) { + if (this != &other) { + key = other.key; + progress(); // populate value + } + return *this; + } + }; + + using iterator = _iterator; + using const_iterator = _iterator; + + static_assert(std::input_or_output_iterator); + static_assert(std::input_or_output_iterator); + + private: + std::vector data; + const iterator _end; + const const_iterator _const_end; + size_t _size; + + std::optional &_at(const KeyT &k) { + range_check(k); + return data[static_cast(k)]; + } + + const std::optional &_at(const KeyT &k) const { + range_check(k); + return data[static_cast(k)]; + } + + public: + /** Basic constructor. The mini_flat_map cannot be re-sized, so there is no + * default constructor. + */ + mini_flat_map(size_t max_size) + : data(max_size), + _end(this, max_size), + _const_end(this, max_size), + _size(0) { + } + + /** Move constructor, forwards the move to the vector + * This has O(N) complexity. + */ + mini_flat_map(mini_flat_map &&other) noexcept + : data(std::move(other.data)), + _end(this, data.size()), + _const_end(this, data.size()), + _size(other.size()) {} + + /** Generic initializer iterator constructor, similar to std::map constructor + * of the same name. + */ + template + mini_flat_map(size_t max_size, const InputIt first, const InputIt last) + : mini_flat_map(max_size) { + for (InputIt it = first; it != last; ++it) { + const KeyT k(it->first); + auto &args = it->second; + emplace(k, args); + } + } + + /** Copy constructor. Forwards the copy onto the vector */ + mini_flat_map(const mini_flat_map &other) noexcept + : mini_flat_map(other.data.size(), other.begin(), other.end()) { + ceph_assert(_size == other._size); + } + + /** Map compatibility. Some legacy code required conversion from std::map. + * This is similar to the move constructor + */ + mini_flat_map(size_t max_size, const std::map &&other) : data( + max_size), _end(this, max_size), _const_end(this, max_size), _size(0) { + for (auto &&[k, t] : other) { + emplace(k, std::move(t)); + } + ceph_assert(_size == other.size()); + } + + /** Map compatibility. Some legacy code required conversion from std::map. + * This is similar to the copy constructor + */ + mini_flat_map(size_t max_size, const std::map &other) + : mini_flat_map(max_size, other.begin(), other.end()) { + ceph_assert(_size == other.size()); + } + + /** Checks if there is an element with key equivalent to key in the container. + * @param key that may be contained + */ + bool contains(const KeyT &key) const { + return unsigned_cast(key) < data.size() && data.at(unsigned_cast(key)); + } + + /** Checks if the container has no elements. */ + [[nodiscard]] bool empty() const noexcept { + return _size == 0; + } + + /** Exchanges the contents of the container with those of other. Does not + * invoke any move, copy, or swap operations on individual elements. + * + * @param other - map to be modified + */ + void swap(mini_flat_map &other) noexcept { + data.swap(other.data); + std::swap(_size, other._size); + } + + /** Erases all elements from the container. */ + void clear() { + if (!_size) { + return; + } + for (auto &&d : data) { + d.reset(); + } + _size = 0; + } + + /** Assignment with move operator */ + mini_flat_map &operator=(mini_flat_map &&other) noexcept { + data = std::move(other.data); + _size = other._size; + return *this; + } + + /** Assignment with copy operator */ + mini_flat_map &operator=(const mini_flat_map &other) { + ceph_assert(data.size() == other.data.size()); + clear(); + + for (auto &&[k, v] : other) { + emplace(k, ValueT(v)); + } + + ceph_assert(_size == other._size); + + return *this; + } + + /** Removes specified element from the container. + * @param i - iterator to remove + * @return iterator - pointing at next element (or end) + */ + iterator erase(iterator &i) { + erase(i->first); + i.progress(); + return i; + } + + /** Removes specified element from the container. + * NOTE: returns iterator, rather than const_iterator as per std::map::erase + * @param i - const_iterator to remove + * @return iterator - pointing at next element (or end) + */ + iterator erase(const_iterator &i) { + erase(i->first); + i.progress(); + return iterator(this, i.key); + } + + /** Removes specified element from the container. + * @param k - key to remove + * @return size_t - 1 if element removed, 0 otherwise. + */ + size_t erase(const KeyT &k) { + if (!contains(k)) { + return 0; + } + _size--; + data.at(IntT(k)).reset(); + return 1; + } + + /** @return begin const_iterator */ + const_iterator begin() const { + return cbegin(); + } + + /** @return end const_iterator */ + const_iterator end() const { + return cend(); + } + + /** @return begin const_iterator */ + const_iterator cbegin() const { + return const_iterator(this); + } + + /** @return end const_iterator */ + const_iterator cend() const { + return _const_end; + } + + /** @return begin iterator */ + iterator begin() { + return iterator(this); + } + + /** @return end iterator */ + iterator end() { + return _end; + } + + /** return number of elements in map, This is the number of optionals + * which are not null in the map. + * @return size_t size + */ + size_t size() const { + return _size; + } + + /** return maximum number of elements that container can hold. + * @return size_t + */ + auto max_size() const { + return data.size(); + } + + /** Returns a reference to the mapped value of the element with specified key. + * If no such element exists, an exception of type std::out_of_range is + * thrown. + * + * @param k - key + * @return reference to value. + */ + ValueT &at(const KeyT &k) { + if (!contains(k)) { + throw std::out_of_range("Key not found"); + } + return *data.at(IntT(k)); + } + + /** Returns a reference to the mapped value of the element with specified key. + * If no such element exists, an exception of type std::out_of_range is + * thrown. + * + * @param k - const key + * @return const reference to value. + */ + const ValueT &at(const KeyT &k) const { + if (!contains(k)) { + throw std::out_of_range("Key not found"); + } + return *data.at(IntT(k)); + } + + /** Equality operator */ + bool operator==(mini_flat_map const &other) const { + if (_size != other._size) { + return false; + } + + for (auto &&[k, v] : *this) { + if (!other.contains(k)) { + return false; + } + if (other.at(k) != v) { + return false; + } + } + + return true; + } + + /** Inserts a new element into the container constructed in-place with the + * given args, if there is no element with the key in the container. + * + * The constructor of the new element is called with exactly the same + * arguments as supplied to emplace, forwarded via + * std::forward(args).... The element may be constructed even if there + * already is an element with the key in the container, in which case the + * newly constructed element will be destroyed immediately (see try_emplace() + * if this behavior is undesirable). + * + * This is different to the std::map interface, in that key must be + * provided explicitly, rather than constructed. THis does provide some + * performance gains and should have the same behaviour. + * + * Careful use of emplace allows the new element to be constructed while + * avoiding unnecessary copy or move operations. + * + * This also differs to std::map in that no iterators are returned + * + * @param k - key to add + * @param args to construct value. + * + * @return true if inserted. + */ + template + bool emplace(const KeyT &k, Args &&... args) { + if (!contains(k)) { + _size++; + _at(k).emplace(std::forward(args)...); + return true; + } + return false; + } + + /** Inserts an element into the container using the copy operator */ + bool insert(const KeyT &k, const ValueT &value) { + return emplace(k, value); + } + + /** Returns a reference to the value that is mapped to a key equivalent to + * key, performing an insertion if such key does not already exist. + * + * Since the key is not stored explicitly, there is no "move" variant as + * there is in std::map. + */ + ValueT &operator[](const KeyT &s) { + if (!contains(s)) { + ceph_assert(emplace(s)); + } + return at(s); + } + + /** Returns the number of elements with key that compares equivalent to the + * specified argument. Each key can only exist once, so cannot return more + * than 1. + */ + size_t count(const KeyT &key) const { + return contains(key) ? 1 : 0; + } + + /** Returns an iterator to the specified key or end if it does not exist. + * O(1) search with low overahead. + * @param key + * * @return iterator. + */ + iterator find(const KeyT &key) { + if (!contains(key)) { + return _end; + } + return iterator(this, key); + } + + /** Returns a const_iterator to the specified key or end if it does not exist. + * O(1) search with low overahead. + * @param key + * @return const_iterator. + */ + const_iterator find(const KeyT &key) const { + if (!contains(key)) { + return _const_end; + } + return const_iterator(this, key); + } + + template + void populate_bitset_set(bitset_set &set) const { + for (IntT ki = 0; static_cast(ki) < data.size(); ++ki) { + KeyT k(ki); + if (_at(k)) { + set.insert(k); + } + } + } + + /** Standard ostream operator */ + friend std::ostream &operator<<(std::ostream &lhs, + const mini_flat_map &rhs) { + unsigned int c = 0; + lhs << "{"; + for (auto &&[k, v] : rhs) { + lhs << k << ":" << v; + c++; + if (c < rhs._size) { + lhs << ","; + } + } + lhs << "}"; + return lhs; + } +}; diff --git a/src/test/common/CMakeLists.txt b/src/test/common/CMakeLists.txt index 1e2653e739bc7..27de0d8ccd919 100644 --- a/src/test/common/CMakeLists.txt +++ b/src/test/common/CMakeLists.txt @@ -256,6 +256,20 @@ add_executable(unittest_interval_set add_ceph_unittest(unittest_interval_set) target_link_libraries(unittest_interval_set ceph-common GTest::Main) +# unittest_mini_flat_map +add_executable(unittest_mini_flat_map + test_mini_flat_map.cc +) +add_ceph_unittest(unittest_mini_flat_map) +target_link_libraries(unittest_mini_flat_map ceph-common GTest::Main) + +# unittest_bitset_set +add_executable(unittest_bitset_set + test_bitset_set.cc +) +add_ceph_unittest(unittest_bitset_set) +target_link_libraries(unittest_bitset_set ceph-common GTest::Main) + # unittest_weighted_priority_queue add_executable(unittest_weighted_priority_queue test_weighted_priority_queue.cc diff --git a/src/test/common/test_bitset_set.cc b/src/test/common/test_bitset_set.cc new file mode 100644 index 0000000000000..f8de103bd46fd --- /dev/null +++ b/src/test/common/test_bitset_set.cc @@ -0,0 +1,184 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#include +#include + +struct Key { + int8_t k; + + constexpr Key(int8_t k) : k(k) { + } + + explicit constexpr operator int8_t() const { + return k; + } + explicit constexpr operator int() const { + return k; + } + + friend std::ostream &operator<<(std::ostream &lhs, const Key &rhs) { + return lhs << (uint32_t) rhs.k; + } + friend bool operator==(const Key &lhs, const Key &rhs) = default; +}; + +TEST(bitset_set, constructors) { + bitset_set<128, Key> bs; + ASSERT_TRUE(bs.empty()); + bs.insert(2); + bs.insert(4); + bitset_set<128, Key> bs2(bs); + ASSERT_EQ(bs, bs2); + int array[] = {2, 4}; + bitset_set<128, Key> bs3(array, array + 2); + ASSERT_EQ(bs, bs3); + bitset_set<128, Key> bs4{2, 4}; + ASSERT_EQ(bs, bs4); +} + +TEST(bitset_set, insert_emplace) { + bitset_set<128, Key> bitset; + bitset.insert(1); + bitset.emplace(3); + + Key keys[] = {1, 3}; + int i = 0; + for (const Key &k : bitset) { + ASSERT_EQ(k, keys[i++]); + } + ASSERT_EQ(2, i); + + bitset_set<128, Key> bitset2; + bitset2.insert(5); + bitset2.insert(bitset); + ASSERT_EQ(3, bitset2.size()); +} + +TEST(bitset_set, erase) { + bitset_set<128, Key> bitset; + bitset.insert(1); + bitset.insert(3); + bitset.insert(5); + bitset.erase(1); + + Key keys[] = {3, 5}; + + // i is used here to count the number of iterations and check it against the + // reference array. + int i = 0; + for (const Key &k : bitset) { + ASSERT_EQ(keys[i++], k); + } + ASSERT_EQ(2, i); +} + +void test_insert_range(int start, int length) +{ + bitset_set<128, Key> bitset; + bitset_set<128, Key> bitset_ref; + + bitset.insert_range(start, length); + for (int i = start; i < length + start; ++i) { + bitset_ref.insert(i); + } + ASSERT_EQ(bitset_ref, bitset) << "start=" << start << " length=" << length; +} + +TEST(bitset_set, insert_range) { + for (int i=0; i < 128; i++) { + for (int j=0; j <= 128 - i; j++) { + test_insert_range(i, j); + } + } +} + +void test_erase_range(int start, int length) +{ + bitset_set<128, Key> bitset; + bitset_set<128, Key> bitset_ref; + + bitset.insert_range(0, 128); + bitset_ref.insert_range(0, 128); + bitset.erase_range(start, length); + for (int i = start; i < length + start; ++i) { + bitset_ref.erase(i); + } + ASSERT_EQ(bitset_ref, bitset); +} + +TEST(bitset_set, erase_range) { + for (int i=0; i < 128; i++) { + for (int j=0; j <= 128 - i; j++) { + test_erase_range(i, j); + } + } +} + +TEST(bitset_set, clear_empty) { + bitset_set<128, Key> bitset; + bitset.insert_range(1, 4); + bitset.clear(); + ASSERT_TRUE(bitset.empty()); +} + +TEST(bitset_set, count_contains_find) { + bitset_set<128, Key> bitset; + ASSERT_FALSE(bitset.contains(1)); + ASSERT_EQ(0, bitset.count(1)); + ASSERT_EQ(bitset.end(), bitset.find(1)); + + bitset.insert(1); + ASSERT_TRUE(bitset.contains(1)); + ASSERT_EQ(1, bitset.count(1)); + ASSERT_EQ(bitset.begin(), bitset.find(1)); +} + +TEST(bitset_set, swap) { + bitset_set<128, Key> bitset; + bitset_set<128, Key> bitset2; + + ASSERT_FALSE(bitset.contains(1)); + ASSERT_EQ(0, bitset.count(1)); + ASSERT_EQ(bitset.end(), bitset.find(1)); + + bitset.insert(1); + ASSERT_FALSE(bitset.empty()); + ASSERT_TRUE(bitset2.empty()); + + bitset2.swap(bitset); + ASSERT_TRUE(bitset.empty()); + ASSERT_FALSE(bitset2.empty()); +} + +TEST(bitset_set, assign) { + bitset_set<128, Key> bitset; + bitset_set<128, Key> bitset2; + + bitset.insert(1); + ASSERT_FALSE(bitset.empty()); + ASSERT_TRUE(bitset2.empty()); + + bitset2 = bitset; + ASSERT_FALSE(bitset.empty()); + ASSERT_FALSE(bitset2.empty()); + + bitset_set<128, Key> bitset3; + bitset3 = std::move(bitset); + ASSERT_FALSE(bitset3.empty()); +} + +TEST(bitset_set, equality) { + bitset_set<128, Key> bitset; + bitset_set<128, Key> bitset2; + + ASSERT_EQ(bitset, bitset2); + bitset.insert(1); + ASSERT_NE(bitset, bitset2); + bitset2.insert(1); + ASSERT_EQ(bitset, bitset2); + bitset.insert(64); + ASSERT_NE(bitset, bitset2); + bitset2.insert(64); + ASSERT_EQ(bitset, bitset2); +} diff --git a/src/test/common/test_mini_flat_map.cc b/src/test/common/test_mini_flat_map.cc new file mode 100644 index 0000000000000..d415d5b95f357 --- /dev/null +++ b/src/test/common/test_mini_flat_map.cc @@ -0,0 +1,151 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab + +#include +#include + +struct Value { + int value; + + explicit Value() : value(0) { + } + explicit Value(int value) : value(value) { + } + + friend std::ostream &operator<<(std::ostream &out, const Value &rhs) { + return out << rhs.value; + } + + bool operator==(const Value &other) const { + return value == other.value; + } +}; + +struct Key { + int8_t k; + + Key(int8_t k) : k(k) { + } + + explicit constexpr operator int8_t() const { + return k; + } + Key &operator++() { + k++; + return *this; + } + + friend std::ostream &operator<<(std::ostream &out, const Key &rhs) { + return out << static_cast(rhs.k); + } + friend bool operator==(const Key &lhs, const Key &rhs) { + return lhs.k == rhs.k; + } +}; + +TEST(mini_flat_map, copy_operator_and_element_access) { + mini_flat_map m(4); + m[0] = Value(1); + ASSERT_EQ(1, m[0].value); + Key non_const_key(0); + ASSERT_EQ(1, m[non_const_key].value); + ASSERT_TRUE(m.contains(0)); + mini_flat_map m2 = m; + ASSERT_EQ(m, m2); + mini_flat_map m3(m); + ASSERT_TRUE(m3.contains(0)); + ASSERT_TRUE(m.contains(0)); +} + +TEST(mini_flat_map, iterators) { + mini_flat_map m(4); + m[0] = Value(1); + m[2] = Value(2); + Value values[] = {Value(1), Value(2)}; + Key keys[] = {Key(0), Key(2)}; + + int i = 0; + for (auto &&[k, v] : m) { + ASSERT_EQ(keys[i], k); + ASSERT_EQ(values[i], v); + i++; + } + ASSERT_EQ(2, i); + + const mini_flat_map m2 = m; + i = 0; + // This loop tests const iterator. + for (auto &&[k, v] : m2) { + ASSERT_EQ(keys[i], k); + ASSERT_EQ(values[i], v); + i++; + } + ASSERT_EQ(2, i); +} + +TEST(mini_flat_map, capacity) { + mini_flat_map m(4); + ASSERT_FALSE(m.contains(Key(0))); + Key k(1); + ASSERT_FALSE(m.contains(k)); + ASSERT_TRUE(m.empty()); + ASSERT_EQ(0, m.size()); + ASSERT_EQ(4, m.max_size()); + + m[k] = Value(2); + ASSERT_TRUE(m.contains(k)); + ASSERT_FALSE(m.empty()); + ASSERT_EQ(1, m.size()); + ASSERT_EQ(4, m.max_size()); +} + +TEST(mini_flat_map, clear) { + mini_flat_map m(4); + m[1] = Value(2); + ASSERT_TRUE(m.contains(1)); + m.clear(); + ASSERT_FALSE(m.contains(1)); + ASSERT_TRUE(m.empty()); +} +// No insert, insert_range, insert_or_assign, emplace_hint, try_emplace, + +TEST(mini_flat_map, emplace_erase) { + mini_flat_map m(4); + m.emplace(1, 2); + ASSERT_TRUE(m.contains(1)); + m.erase(Key(1)); + ASSERT_FALSE(m.contains(1)); + m.emplace(1, 2); + ASSERT_TRUE(m.contains(1)); + auto it = m.begin(); + m.erase(it); + ASSERT_EQ(m.end(), it); + ASSERT_FALSE(m.contains(1)); + m.emplace(1, 2); + ASSERT_TRUE(m.contains(1)); + auto cit = m.cbegin(); + m.erase(cit); + ASSERT_EQ(m.cend(), cit); + ASSERT_FALSE(m.contains(1)); +} +// no erase(range) + +TEST(mini_flat_map, swap) { + mini_flat_map m(4); + m[1] = Value(2); + mini_flat_map m2(4); + m2.swap(m); + ASSERT_TRUE(m.empty()); + ASSERT_FALSE(m2.empty()); +} +// No extract, merge + +TEST(mini_flat_map, lookup) { + mini_flat_map m(4); + ASSERT_EQ(0, m.count(Key(0))); + ASSERT_EQ(0, m.count(Key(1))); + m[1] = Value(2); + ASSERT_EQ(0, m.count(Key(0))); + ASSERT_EQ(1, m.count(Key(1))); +} +// NO equal_range, lower_bound, upper_bound -- 2.39.5