From a141c401f78467bc15f62882fca5d55a007cacbb Mon Sep 17 00:00:00 2001 From: Steven Le Rouzic Date: Mon, 17 Feb 2025 00:21:48 +0100 Subject: Reorganize everything --- asl/containers/BUILD.bazel | 58 ++++ asl/containers/buffer.hpp | 459 +++++++++++++++++++++++++++++ asl/containers/buffer_tests.cpp | 603 ++++++++++++++++++++++++++++++++++++++ asl/containers/hash_map.hpp | 178 +++++++++++ asl/containers/hash_map_tests.cpp | 48 +++ asl/containers/hash_set.hpp | 418 ++++++++++++++++++++++++++ asl/containers/hash_set_tests.cpp | 185 ++++++++++++ 7 files changed, 1949 insertions(+) create mode 100644 asl/containers/BUILD.bazel create mode 100644 asl/containers/buffer.hpp create mode 100644 asl/containers/buffer_tests.cpp create mode 100644 asl/containers/hash_map.hpp create mode 100644 asl/containers/hash_map_tests.cpp create mode 100644 asl/containers/hash_set.hpp create mode 100644 asl/containers/hash_set_tests.cpp (limited to 'asl/containers') diff --git a/asl/containers/BUILD.bazel b/asl/containers/BUILD.bazel new file mode 100644 index 0000000..2d2e057 --- /dev/null +++ b/asl/containers/BUILD.bazel @@ -0,0 +1,58 @@ +cc_library( + name = "buffer", + hdrs = [ + "buffer.hpp", + ], + deps = [ + "//asl/memory", + "//asl/base", + "//asl/types:span", + "//asl/hashing", + ], + visibility = ["//visibility:public"], +) + +cc_library( + name = "hash_set", + hdrs = [ + "hash_set.hpp", + ], + deps = [ + "//asl/base", + "//asl/memory", + "//asl/types:maybe_uninit", + "//asl/hashing", + ], + visibility = ["//visibility:public"], +) + +cc_library( + name = "hash_map", + hdrs = [ + "hash_map.hpp", + ], + deps = [ + "//asl/base", + "//asl/memory", + "//asl/hashing", + ":hash_set", + ], + visibility = ["//visibility:public"], +) + +[cc_test( + name = "%s_tests" % name, + srcs = [ + "%s_tests.cpp" % name, + ], + deps = [ + ":%s" % name, + "//asl/tests:utils", + "//asl/testing", + "//asl/strings:string", + ], +) for name in [ + "buffer", + "hash_map", + "hash_set", +]] diff --git a/asl/containers/buffer.hpp b/asl/containers/buffer.hpp new file mode 100644 index 0000000..76562d3 --- /dev/null +++ b/asl/containers/buffer.hpp @@ -0,0 +1,459 @@ +#pragma once + +#include "asl/base/meta.hpp" +#include "asl/memory/allocator.hpp" +#include "asl/memory/memory.hpp" +#include "asl/base/annotations.hpp" +#include "asl/base/assert.hpp" +#include "asl/types/span.hpp" +#include "asl/hashing/hash.hpp" + +namespace asl +{ + +template +class buffer +{ + T* m_data{}; + isize_t m_capacity{}; + + static constexpr size_t kOnHeapMask = 0x8000'0000'0000'0000ULL; + + // bit 63 : 1 = on heap, 0 = inline + // bits [62:56] : size when inline + // bits [62:0] : size when on heap + size_t m_size_encoded_{}; + + ASL_NO_UNIQUE_ADDRESS Allocator m_allocator; + + static constexpr isize_t kInlineRegionSize = size_of + size_of + size_of; + +public: + static constexpr isize_t kInlineCapacity = []() { + // 1 byte is used for size inline in m_size_encoded. + // This is enough because we have at most 24 bytes available, + // so 23 chars of capacity. + const isize_t available_size = kInlineRegionSize - 1; + return available_size / size_of; + }(); + +private: + static_assert(align_of <= align_of); + static_assert(align_of == align_of); + static_assert(align_of == align_of); + + constexpr size_t load_size_encoded() const + { + size_t s{}; + asl::memcpy(&s, &m_size_encoded_, sizeof(size_t)); + return s; + } + + constexpr void store_size_encoded(size_t encoded) + { + asl::memcpy(&m_size_encoded_, &encoded, sizeof(size_t)); + } + + static constexpr bool is_on_heap(size_t size_encoded) + { + return (size_encoded & kOnHeapMask) != 0; + } + + static constexpr size_t encode_size_heap(isize_t size) + { + return static_cast(size) | kOnHeapMask; + } + + static constexpr isize_t decode_size(size_t size_encoded) + { + if constexpr (kInlineCapacity == 0) + { + return is_on_heap(size_encoded) + ? static_cast(size_encoded & (~kOnHeapMask)) + : 0; + } + else + { + return is_on_heap(size_encoded) + ? static_cast(size_encoded & (~kOnHeapMask)) + : static_cast(size_encoded >> 56); + } + } + + constexpr bool is_on_heap() const + { + return is_on_heap(load_size_encoded()); + } + + constexpr T* push_uninit() + { + isize_t sz = size(); + resize_uninit_inner(sz + 1); + return data() + sz; + } + + constexpr void resize_uninit_inner(isize_t new_size) + { + isize_t old_size = size(); + if (!trivially_destructible && new_size < old_size) + { + destroy_n(data() + new_size, old_size - new_size); + } + reserve_capacity(new_size); + set_size(new_size); + } + + constexpr void set_size_inline(isize_t new_size) + { + ASL_ASSERT(new_size >= 0 && new_size <= kInlineCapacity); + size_t size_encoded = (load_size_encoded() & size_t{0x00ff'ffff'ffff'ffff}) | (bit_cast(new_size) << 56); + store_size_encoded(size_encoded); + } + + constexpr void set_size(isize_t new_size) + { + ASL_ASSERT(new_size >= 0 && new_size <= capacity()); + if (is_on_heap()) + { + store_size_encoded(encode_size_heap(new_size)); + } + else + { + set_size_inline(new_size); + } + } + + // NOLINTNEXTLINE(*-rvalue-reference-param-not-moved) + void move_from_other(buffer&& other, bool assign) + { + if (other.is_on_heap()) + { + destroy(); + m_data = other.m_data; + m_capacity = other.m_capacity; + store_size_encoded(other.load_size_encoded()); + } + else if (trivially_move_constructible) + { + destroy(); + asl::memcpy(this, &other, kInlineRegionSize); + } + else if (!assign || m_allocator == other.m_allocator) + { + isize_t other_n = other.size(); + isize_t this_n = size(); + resize_uninit_inner(other_n); + if (other_n <= this_n) + { + relocate_assign_n(data(), other.data(), other_n); + } + else + { + relocate_assign_n(data(), other.data(), this_n); + relocate_uninit_n(data() + this_n, other.data() + this_n, other_n - this_n); + } + } + else + { + destroy(); + isize_t n = other.size(); + ASL_ASSERT(n <= kInlineCapacity); + relocate_uninit_n(data(), other.data(), n); + set_size_inline(n); + } + + other.set_size_inline(0); + + if (assign) + { + m_allocator = ASL_MOVE(other.m_allocator); + } + } + + void copy_range(span to_copy) + { + isize_t this_size = size(); + isize_t new_size = to_copy.size(); + + resize_uninit_inner(to_copy.size()); + ASL_ASSERT(capacity() >= new_size); + ASL_ASSERT(size() == to_copy.size()); + + if (new_size <= this_size) + { + copy_assign_n(data(), to_copy.data(), new_size); + } + else + { + copy_assign_n(data(), to_copy.data(), this_size); + copy_uninit_n(data() + this_size, to_copy.data() + this_size, new_size - this_size); + } + } + + template + void resize_inner(isize_t new_size, Args&&... args) + requires constructible_from + { + ASL_ASSERT(new_size >= 0); + + isize_t old_size = size(); + resize_uninit_inner(new_size); + + T* data_ptr = data(); + T* end = data_ptr + new_size; + + // NOLINTNEXTLINE(*-pointer-arithmetic) + for (T* it = data_ptr + old_size; it < end; ++it) + { + construct_at(it, ASL_FWD(args)...); + } + } + +public: + constexpr buffer() requires default_constructible = default; + + explicit constexpr buffer(span s) + requires default_constructible + : buffer{} + { + copy_range(s); + } + + explicit constexpr buffer(Allocator allocator) + : m_allocator{ASL_MOVE(allocator)} + {} + + explicit constexpr buffer(span s, Allocator allocator) + : m_allocator{ASL_MOVE(allocator)} + { + copy_range(s); + } + + constexpr buffer(const buffer& other) + requires copy_constructible && copyable + : m_allocator{other.m_allocator} + { + copy_range(other); + } + + constexpr buffer(buffer&& other) + requires moveable + : buffer(ASL_MOVE(other.m_allocator)) + { + move_from_other(ASL_MOVE(other), false); + } + + constexpr buffer& operator=(const buffer& other) + requires copyable + { + if (&other == this) { return *this; } + copy_range(other); + return *this; + } + + constexpr buffer& operator=(buffer&& other) + requires moveable + { + if (&other == this) { return *this; } + move_from_other(ASL_MOVE(other), true); + return *this; + } + + ~buffer() + { + destroy(); + } + + constexpr isize_t size() const + { + return decode_size(load_size_encoded()); + } + + constexpr isize_t capacity() const + { + if constexpr (kInlineCapacity == 0) + { + return m_capacity; + } + else + { + return is_on_heap() ? m_capacity : kInlineCapacity; + } + } + + void clear() + { + isize_t current_size = size(); + if (current_size == 0) { return; } + + destroy_n(data(), current_size); + set_size(0); + } + + void destroy() + { + clear(); + if (is_on_heap()) + { + if (m_data != nullptr) + { + auto current_layout = layout::array(m_capacity); + m_allocator.dealloc(m_data, current_layout); + } + set_size_inline(0); + } + } + + void reserve_capacity(isize_t new_capacity) + { + ASL_ASSERT(new_capacity >= 0); + ASL_ASSERT_RELEASE(new_capacity <= 0x4000'0000'0000'0000); + + if (new_capacity <= capacity()) { return; } + ASL_ASSERT(new_capacity > kInlineCapacity); + + new_capacity = static_cast(round_up_pow2(static_cast(new_capacity))); + + T* old_data = data(); + const isize_t old_capacity = capacity(); + const isize_t current_size = size(); + const bool currently_on_heap = is_on_heap(); + + auto old_layout = layout::array(old_capacity); + auto new_layout = layout::array(new_capacity); + + if (currently_on_heap && trivially_move_constructible) + { + m_data = reinterpret_cast(m_allocator.realloc(m_data, old_layout, new_layout)); + m_capacity = new_capacity; + return; + } + + T* new_data = reinterpret_cast(m_allocator.alloc(new_layout)); + + relocate_uninit_n(new_data, old_data, current_size); + + if (currently_on_heap) + { + m_allocator.dealloc(old_data, old_layout); + } + + m_data = new_data; + m_capacity = new_capacity; + store_size_encoded(encode_size_heap(current_size)); + } + + constexpr void resize_uninit(isize_t new_size) + requires trivially_default_constructible && trivially_destructible + { + reserve_capacity(new_size); + set_size(new_size); + } + + constexpr void resize_zero(isize_t new_size) + requires trivially_default_constructible && trivially_destructible + { + isize_t old_size = size(); + resize_uninit(new_size); + + if (new_size > old_size) + { + memzero(data() + old_size, (new_size - old_size) * size_of); + } + } + + void resize(isize_t new_size) + requires default_constructible + { + resize_inner(new_size); + } + + void resize(isize_t new_size, const T& value) + { + resize_inner(new_size, value); + } + + constexpr T& push(auto&&... args) + requires constructible_from + { + T* uninit = push_uninit(); + T* init = construct_at(uninit, ASL_FWD(args)...); + return *init; + } + + // @Todo(C++23) Use deducing this + const T* data() const + { + if constexpr (kInlineCapacity == 0) + { + return m_data; + } + else + { + return is_on_heap() ? m_data : reinterpret_cast(this); + } + } + + T* data() + { + if constexpr (kInlineCapacity == 0) + { + return m_data; + } + else + { + return is_on_heap() ? m_data : reinterpret_cast(this); + } + } + + // @Todo(C++23) Use deducing this + constexpr contiguous_iterator begin() const { return contiguous_iterator{data()}; } + constexpr contiguous_iterator end() const { return contiguous_iterator{data() + size()}; } + + constexpr contiguous_iterator begin() { return contiguous_iterator{data()}; } + constexpr contiguous_iterator end() { return contiguous_iterator{data() + size()}; } + + // @Todo(C++23) Deducing this + constexpr operator span() const // NOLINT(*-explicit-conversions) + { + return as_span(); + } + + constexpr operator span() // NOLINT(*-explicit-conversions) + { + return as_span(); + } + + constexpr span as_span() const + { + return span{data(), size()}; + } + + constexpr span as_span() + { + return span{data(), size()}; + } + + // @Todo(C++23) Use deducing this + constexpr T& operator[](isize_t i) + { + ASL_ASSERT(i >= 0 && i <= size()); + return data()[i]; + } + + constexpr const T& operator[](isize_t i) const + { + ASL_ASSERT(i >= 0 && i <= size()); + return data()[i]; + } + + template + requires hashable + friend H AslHashValue(H h, const buffer& b) + { + return H::combine_contiguous(ASL_MOVE(h), b.as_span()); + } +}; + +} // namespace asl + diff --git a/asl/containers/buffer_tests.cpp b/asl/containers/buffer_tests.cpp new file mode 100644 index 0000000..fd8ad45 --- /dev/null +++ b/asl/containers/buffer_tests.cpp @@ -0,0 +1,603 @@ +#include "asl/containers/buffer.hpp" + +#include "asl/testing/testing.hpp" +#include "asl/tests/types.hpp" + +struct Big +{ + uint64_t data[8]; +}; + +static_assert(asl::buffer::kInlineCapacity == 5); +static_assert(asl::buffer::kInlineCapacity == 2); +static_assert(asl::buffer::kInlineCapacity == 23); +static_assert(asl::buffer::kInlineCapacity == 0); + +ASL_TEST(default_size) +{ + asl::buffer b1; + ASL_TEST_EXPECT(b1.size() == 0); + ASL_TEST_EXPECT(b1.capacity() == 5); + ASL_TEST_EXPECT(static_cast(b1.data()) == &b1); + + asl::buffer b2; + ASL_TEST_EXPECT(b2.size() == 0); + ASL_TEST_EXPECT(b2.capacity() == 0); + ASL_TEST_EXPECT(b2.data() == nullptr); +} + +struct CounterAllocator +{ + isize_t* count; + + void* alloc(const asl::layout& layout) const + { + *count += 1; + return asl::GlobalHeap::alloc(layout); + } + + void* realloc(void* ptr, const asl::layout& old, const asl::layout& new_layout) const + { + *count += 1; + return asl::GlobalHeap::realloc(ptr, old, new_layout); + } + + static void dealloc(void* ptr, const asl::layout& layout) + { + asl::GlobalHeap::dealloc(ptr, layout); + } + + constexpr bool operator==(const CounterAllocator&) const { return true; } +}; +static_assert(asl::allocator); + +struct IncompatibleAllocator +{ + static void* alloc(const asl::layout& layout) + { + return asl::GlobalHeap::alloc(layout); + } + + static void* realloc(void* ptr, const asl::layout& old, const asl::layout& new_layout) + { + return asl::GlobalHeap::realloc(ptr, old, new_layout); + } + + static void dealloc(void* ptr, const asl::layout& layout) + { + asl::GlobalHeap::dealloc(ptr, layout); + } + + constexpr bool operator==(const IncompatibleAllocator&) const { return false; } +}; +static_assert(asl::allocator); + +ASL_TEST(reserve_capacity) +{ + isize_t count = 0; + asl::buffer b(CounterAllocator{&count}); + ASL_TEST_EXPECT(b.size() == 0); + ASL_TEST_EXPECT(b.capacity() == 5); + ASL_TEST_EXPECT(count == 0); + + b.reserve_capacity(4); + ASL_TEST_EXPECT(b.size() == 0); + ASL_TEST_EXPECT(b.capacity() == 5); + ASL_TEST_EXPECT(count == 0); + + b.reserve_capacity(12); + ASL_TEST_EXPECT(b.size() == 0); + ASL_TEST_EXPECT(b.capacity() >= 12); + ASL_TEST_EXPECT(count == 1); + + b.reserve_capacity(13); + ASL_TEST_EXPECT(b.size() == 0); + ASL_TEST_EXPECT(b.capacity() >= 13); + ASL_TEST_EXPECT(count == 1); + + b.reserve_capacity(130); + ASL_TEST_EXPECT(b.size() == 0); + ASL_TEST_EXPECT(b.capacity() >= 130); + ASL_TEST_EXPECT(count == 2); +} + +ASL_TEST(push) +{ + asl::buffer b; + ASL_TEST_EXPECT(b.size() == 0); + + b.push(1); + ASL_TEST_EXPECT(b.size() == 1); + ASL_TEST_EXPECT(b[0] == 1); + + b.push(2); + b.push(3); + ASL_TEST_EXPECT(b.size() == 3); + ASL_TEST_EXPECT(b[0] == 1); + ASL_TEST_EXPECT(b[1] == 2); + ASL_TEST_EXPECT(b[2] == 3); + + b.push(4); + b.push(5); + b.push(6); + b.push(7); + ASL_TEST_EXPECT(b.size() == 7); + ASL_TEST_EXPECT(b[0] == 1); + ASL_TEST_EXPECT(b[1] == 2); + ASL_TEST_EXPECT(b[2] == 3); + ASL_TEST_EXPECT(b[3] == 4); + ASL_TEST_EXPECT(b[4] == 5); + ASL_TEST_EXPECT(b[5] == 6); + ASL_TEST_EXPECT(b[6] == 7); +} + +ASL_TEST(from_span) +{ + int data[] = {1, 2, 4, 8}; + asl::buffer b{data}; + + ASL_TEST_EXPECT(b.size() == 4); + ASL_TEST_EXPECT(b[0] == 1); + ASL_TEST_EXPECT(b[1] == 2); + ASL_TEST_EXPECT(b[2] == 4); + ASL_TEST_EXPECT(b[3] == 8); +} + +struct MoveableType +{ + int moved{}; + int value; + + explicit MoveableType(int x) : value{x} {} + MoveableType(const MoveableType&) = delete; + MoveableType(MoveableType&& other) : moved{other.moved + 1}, value{other.value} {} + MoveableType& operator=(const MoveableType&) = delete; + MoveableType& operator=(MoveableType&&) = delete; +}; +static_assert(!asl::trivially_copy_constructible); +static_assert(!asl::trivially_move_constructible); +static_assert(!asl::copyable); +static_assert(asl::move_constructible); + +ASL_TEST(push_move) +{ + asl::buffer b; + + static_assert(asl::buffer::kInlineCapacity > 0); + + b.push(0); + ASL_TEST_EXPECT(b[0].value == 0); + ASL_TEST_EXPECT(b[0].moved == 0); + + b.push(1); + ASL_TEST_EXPECT(b[0].value == 0); + ASL_TEST_EXPECT(b[0].moved == 0); + ASL_TEST_EXPECT(b[1].value == 1); + ASL_TEST_EXPECT(b[1].moved == 0); + + b.push(2); + ASL_TEST_EXPECT(b[0].value == 0); + ASL_TEST_EXPECT(b[0].moved == 1); + ASL_TEST_EXPECT(b[1].value == 1); + ASL_TEST_EXPECT(b[1].moved == 1); + ASL_TEST_EXPECT(b[2].value == 2); + ASL_TEST_EXPECT(b[2].moved == 0); + + b.push(3); + ASL_TEST_EXPECT(b[0].value == 0); + ASL_TEST_EXPECT(b[0].moved == 1); + ASL_TEST_EXPECT(b[1].value == 1); + ASL_TEST_EXPECT(b[1].moved == 1); + ASL_TEST_EXPECT(b[2].value == 2); + ASL_TEST_EXPECT(b[2].moved == 0); + ASL_TEST_EXPECT(b[3].value == 3); + ASL_TEST_EXPECT(b[3].moved == 0); + + b.push(4); + ASL_TEST_EXPECT(b[0].value == 0); + ASL_TEST_EXPECT(b[0].moved == 2); + ASL_TEST_EXPECT(b[1].value == 1); + ASL_TEST_EXPECT(b[1].moved == 2); + ASL_TEST_EXPECT(b[2].value == 2); + ASL_TEST_EXPECT(b[2].moved == 1); + ASL_TEST_EXPECT(b[3].value == 3); + ASL_TEST_EXPECT(b[3].moved == 1); + ASL_TEST_EXPECT(b[4].value == 4); + ASL_TEST_EXPECT(b[4].moved == 0); +} + +ASL_TEST(clear) +{ + asl::buffer b; + ASL_TEST_EXPECT(b.size() == 0); + + b.push(1); + b.push(2); + b.push(3); + b.push(4); + b.push(5); + b.push(6); + b.push(7); + ASL_TEST_EXPECT(b.size() == 7); + + b.clear(); + ASL_TEST_EXPECT(b.size() == 0); +} + +static_assert(asl::buffer::kInlineCapacity == 2); + +ASL_TEST(clear_destructor_small) +{ + bool d0 = false; + bool d1 = false; + + asl::buffer buf; + + buf.push(&d0); + buf.push(&d1); + + buf.clear(); + ASL_TEST_EXPECT(d0 == true); + ASL_TEST_EXPECT(d1 == true); +} + +ASL_TEST(clear_destructor_heap) +{ + bool d0 = false; + bool d1 = false; + bool d2 = false; + + asl::buffer buf; + + buf.push(&d0); + buf.push(&d1); + buf.push(&d2); + ASL_TEST_EXPECT(d0 == false); + ASL_TEST_EXPECT(d1 == false); + ASL_TEST_EXPECT(d2 == false); + + buf.clear(); + ASL_TEST_EXPECT(d0 == true); + ASL_TEST_EXPECT(d1 == true); + ASL_TEST_EXPECT(d2 == true); +} + +ASL_TEST(move_construct_from_heap) +{ + bool d[3]{}; + asl::buffer buf; + buf.push(&d[0]); + buf.push(&d[1]); + buf.push(&d[2]); + + { + asl::buffer buf2(ASL_MOVE(buf)); + ASL_TEST_EXPECT(buf2.size() == 3); + ASL_TEST_EXPECT(d[0] == false); + ASL_TEST_EXPECT(d[1] == false); + ASL_TEST_EXPECT(d[2] == false); + } + + ASL_TEST_EXPECT(buf.size() == 0); + ASL_TEST_EXPECT(d[0] == true); + ASL_TEST_EXPECT(d[1] == true); + ASL_TEST_EXPECT(d[2] == true); +} + +ASL_TEST(move_construct_inline_trivial) +{ + asl::buffer buf; + buf.push(1U); + buf.push(2U); + + asl::buffer buf2(ASL_MOVE(buf)); + ASL_TEST_EXPECT(buf2[0] == 1U); + ASL_TEST_EXPECT(buf2[1] == 2U); + + ASL_TEST_EXPECT(buf2.size() == 2); + ASL_TEST_EXPECT(buf.size() == 0); +} + +ASL_TEST(move_construct_from_inline_non_trivial) +{ + bool d[2]{}; + asl::buffer buf; + buf.push(&d[0]); + buf.push(&d[1]); + + { + asl::buffer buf2(ASL_MOVE(buf)); + ASL_TEST_EXPECT(buf2.size() == 2); + ASL_TEST_EXPECT(d[0] == false); + ASL_TEST_EXPECT(d[1] == false); + } + + ASL_TEST_EXPECT(buf.size() == 0); + ASL_TEST_EXPECT(d[0] == true); + ASL_TEST_EXPECT(d[1] == true); +} + +ASL_TEST(move_assign_from_heap) +{ + bool d[6]{}; + + { + asl::buffer buf; + asl::buffer buf2; + + buf.push(&d[0]); + buf.push(&d[1]); + buf.push(&d[2]); + + buf2.push(&d[3]); + buf2.push(&d[4]); + buf2.push(&d[5]); + + ASL_TEST_EXPECT(d[0] == false); + ASL_TEST_EXPECT(d[1] == false); + ASL_TEST_EXPECT(d[2] == false); + ASL_TEST_EXPECT(d[3] == false); + ASL_TEST_EXPECT(d[4] == false); + ASL_TEST_EXPECT(d[5] == false); + + buf2 = ASL_MOVE(buf); + + ASL_TEST_EXPECT(buf.size() == 0); + ASL_TEST_EXPECT(buf2.size() == 3); + + ASL_TEST_EXPECT(d[0] == false); + ASL_TEST_EXPECT(d[1] == false); + ASL_TEST_EXPECT(d[2] == false); + ASL_TEST_EXPECT(d[3] == true); + ASL_TEST_EXPECT(d[4] == true); + ASL_TEST_EXPECT(d[5] == true); + } + + ASL_TEST_EXPECT(d[0] == true); + ASL_TEST_EXPECT(d[1] == true); + ASL_TEST_EXPECT(d[2] == true); + ASL_TEST_EXPECT(d[3] == true); + ASL_TEST_EXPECT(d[4] == true); + ASL_TEST_EXPECT(d[5] == true); +} + +ASL_TEST(move_assign_trivial_heap_to_inline) +{ + isize_t alloc_count = 0; + asl::buffer buf{CounterAllocator{&alloc_count}}; + asl::buffer buf2{CounterAllocator{&alloc_count}}; + + buf.push(1); + buf.push(2); + ASL_TEST_EXPECT(alloc_count == 0); + + buf2.push(3); + buf2.push(4); + buf2.push(5); + ASL_TEST_EXPECT(alloc_count == 1); + + buf = ASL_MOVE(buf2); + ASL_TEST_EXPECT(alloc_count == 1); + + ASL_TEST_EXPECT(buf.size() == 3); + ASL_TEST_EXPECT(buf2.size() == 0); + ASL_TEST_EXPECT(buf[0] == 3); + ASL_TEST_EXPECT(buf[1] == 4); + ASL_TEST_EXPECT(buf[2] == 5); +} + +ASL_TEST(move_assign_trivial_inline_to_heap) +{ + isize_t alloc_count = 0; + asl::buffer buf{CounterAllocator{&alloc_count}}; + asl::buffer buf2{CounterAllocator{&alloc_count}}; + + buf.push(1); + buf.push(2); + ASL_TEST_EXPECT(alloc_count == 0); + + buf2.push(3); + buf2.push(4); + buf2.push(5); + ASL_TEST_EXPECT(alloc_count == 1); + + buf2 = ASL_MOVE(buf); + ASL_TEST_EXPECT(alloc_count == 1); + + ASL_TEST_EXPECT(buf.size() == 0); + ASL_TEST_EXPECT(buf2.size() == 2); + ASL_TEST_EXPECT(buf2[0] == 1); + ASL_TEST_EXPECT(buf2[1] == 2); +} + +ASL_TEST(move_assign_inline_to_heap) +{ + bool d[6]{}; + + { + asl::buffer buf; + asl::buffer buf2; + + buf.push(&d[0]); + buf.push(&d[1]); + + buf2.push(&d[2]); + buf2.push(&d[3]); + buf2.push(&d[4]); + buf2.push(&d[5]); + + buf2 = ASL_MOVE(buf); + + ASL_TEST_EXPECT(buf.size() == 0); + ASL_TEST_EXPECT(buf2.size() == 2); + ASL_TEST_EXPECT(d[0] == false); + ASL_TEST_EXPECT(d[1] == false); + ASL_TEST_EXPECT(d[2] == false); // moved but not destroyed + ASL_TEST_EXPECT(d[3] == false); // moved but not destroyed + ASL_TEST_EXPECT(d[4] == true); + ASL_TEST_EXPECT(d[5] == true); + } + + ASL_TEST_EXPECT(d[0] == true); + ASL_TEST_EXPECT(d[1] == true); + ASL_TEST_EXPECT(d[2] == false); // moved but not destroyed + ASL_TEST_EXPECT(d[3] == false); // moved but not destroyed + ASL_TEST_EXPECT(d[4] == true); + ASL_TEST_EXPECT(d[5] == true); +} + +ASL_TEST(move_assign_from_inline_incompatible_allocator) +{ + bool d[6]{}; + + { + asl::buffer buf; + asl::buffer buf2; + + buf.push(&d[0]); + buf.push(&d[1]); + + buf2.push(&d[2]); + buf2.push(&d[3]); + buf2.push(&d[4]); + buf2.push(&d[5]); + + buf2 = ASL_MOVE(buf); + + ASL_TEST_EXPECT(buf.size() == 0); + ASL_TEST_EXPECT(buf2.size() == 2); + ASL_TEST_EXPECT(d[0] == false); + ASL_TEST_EXPECT(d[1] == false); + ASL_TEST_EXPECT(d[2] == true); + ASL_TEST_EXPECT(d[3] == true); + ASL_TEST_EXPECT(d[4] == true); + ASL_TEST_EXPECT(d[5] == true); + } + + ASL_TEST_EXPECT(d[0] == true); + ASL_TEST_EXPECT(d[1] == true); + ASL_TEST_EXPECT(d[2] == true); + ASL_TEST_EXPECT(d[3] == true); + ASL_TEST_EXPECT(d[4] == true); + ASL_TEST_EXPECT(d[5] == true); +} + +ASL_TEST(copy_construct_inline) +{ + asl::buffer buf; + buf.push(0); + buf.push(1); + buf.push(2); + + asl::buffer buf2{buf}; + + ASL_TEST_EXPECT(buf.size() == buf2.size()); + ASL_TEST_EXPECT(buf.size() == 3); + ASL_TEST_EXPECT(buf[0] == 0); + ASL_TEST_EXPECT(buf[1] == 1); + ASL_TEST_EXPECT(buf[2] == 2); + ASL_TEST_EXPECT(buf2[0] == 0); + ASL_TEST_EXPECT(buf2[1] == 1); + ASL_TEST_EXPECT(buf2[2] == 2); +} + +ASL_TEST(copy_assign_into_smaller) +{ + asl::buffer buf; + buf.push(0); + buf.push(1); + buf.push(2); + + asl::buffer buf2; + buf2.push(4); + + buf2 = buf; + + ASL_TEST_EXPECT(buf.size() == 3); + ASL_TEST_EXPECT(buf2.size() == 3); + + ASL_TEST_EXPECT(buf[0] == 0); + ASL_TEST_EXPECT(buf[1] == 1); + ASL_TEST_EXPECT(buf[2] == 2); + ASL_TEST_EXPECT(buf2[0] == 0); + ASL_TEST_EXPECT(buf2[1] == 1); + ASL_TEST_EXPECT(buf2[2] == 2); +} + +ASL_TEST(copy_assign_into_larger) +{ + asl::buffer buf; + buf.push(0); + buf.push(1); + buf.push(2); + + asl::buffer buf2; + buf2.push(4); + + buf = buf2; + + ASL_TEST_EXPECT(buf.size() == 1); + ASL_TEST_EXPECT(buf2.size() == 1); + + ASL_TEST_EXPECT(buf[0] == 4); + ASL_TEST_EXPECT(buf2[0] == 4); +} + +ASL_TEST(resize_default) +{ + asl::buffer buf; + + buf.push(5); + buf.resize(4); + + ASL_TEST_ASSERT(buf.size() == 4); + ASL_TEST_EXPECT(buf[0] == 5); + ASL_TEST_EXPECT(buf[1] == 0); + ASL_TEST_EXPECT(buf[2] == 0); + ASL_TEST_EXPECT(buf[3] == 0); + + buf.resize(2); + + ASL_TEST_ASSERT(buf.size() == 2); + ASL_TEST_EXPECT(buf[0] == 5); + ASL_TEST_EXPECT(buf[1] == 0); +} + +ASL_TEST(resize) +{ + asl::buffer buf; + + buf.push(5); + buf.resize(4, 6); + + ASL_TEST_ASSERT(buf.size() == 4); + ASL_TEST_EXPECT(buf[0] == 5); + ASL_TEST_EXPECT(buf[1] == 6); + ASL_TEST_EXPECT(buf[2] == 6); + ASL_TEST_EXPECT(buf[3] == 6); + + buf.resize(2, 7); + + ASL_TEST_ASSERT(buf.size() == 2); + ASL_TEST_EXPECT(buf[0] == 5); + ASL_TEST_EXPECT(buf[1] == 6); +} + +ASL_TEST(resize_zero) +{ + asl::buffer buf; + for (int i = 0; i < 100; ++i) + { + buf.push(i); + } + + buf.resize_zero(200); + ASL_TEST_ASSERT(buf.size() == 200); + + for (int i = 0; i < 100; ++i) + { + ASL_TEST_EXPECT(buf[i] == i); + ASL_TEST_EXPECT(buf[100 + i] == 0); + } +} + diff --git a/asl/containers/hash_map.hpp b/asl/containers/hash_map.hpp new file mode 100644 index 0000000..104bd6a --- /dev/null +++ b/asl/containers/hash_map.hpp @@ -0,0 +1,178 @@ +#pragma once + +#include "asl/base/utility.hpp" +#include "asl/base/meta.hpp" +#include "asl/hashing/hash.hpp" +#include "asl/memory/allocator.hpp" +#include "asl/containers/hash_set.hpp" + +namespace asl +{ + +namespace hash_map_internal +{ + +template +struct Slot +{ + K key; + V value; +}; + +template KeyHasher> +struct SlotHasher : public KeyHasher +{ + using KeyHasher::hash; + + constexpr static uint64_t hash(const Slot& slot) + { + return KeyHasher::hash(slot.key); + } +}; + +template KeyComparator> +struct SlotComparator : public KeyComparator +{ + using KeyComparator::eq; + + constexpr static bool eq(const Slot& a, const Slot& b) + { + return KeyComparator::eq(a.key, b.key); + } + + constexpr static bool eq(const Slot& a, const K& b) + { + return KeyComparator::eq(a.key, b); + } +}; + +} // namespace hash_map_internal + +template< + is_object K, + is_object V, + allocator Allocator = DefaultAllocator, + key_hasher KeyHasher = default_key_hasher, + key_comparator KeyComparator = default_key_comparator +> +requires moveable && moveable +class hash_map : protected hash_set< + hash_map_internal::Slot, + Allocator, + hash_map_internal::SlotHasher, + hash_map_internal::SlotComparator> +{ + using Base = + hash_set< + hash_map_internal::Slot, + Allocator, + hash_map_internal::SlotHasher, + hash_map_internal::SlotComparator>; + +public: + constexpr hash_map() requires default_constructible = default; + + explicit constexpr hash_map(Allocator allocator) + : Base{ASL_MOVE(allocator)} + {} + + hash_map(const hash_map&) requires copyable && copyable = default; + + hash_map& operator=(const hash_map&) requires copyable && copyable = default; + + hash_map(hash_map&&) = default; + + hash_map& operator=(hash_map&&) = default; + + ~hash_map() = default; + + using Base::destroy; + + using Base::clear; + + using Base::size; + + using Base::remove; + + using Base::contains; + + template + requires + key_hasher && + key_comparator && + constructible_from && + constructible_from + void insert(U&& key, Arg0&& arg0, Args1&&... args1) + { + Base::maybe_grow_to_fit_one_more(); + + auto result = Base::find_slot_insert(key); + + // NOLINTBEGIN(*-pointer-arithmetic) + + ASL_ASSERT(result.first_available_index >= 0); + + if (result.already_present_index >= 0) + { + if (result.already_present_index != result.first_available_index) + { + ASL_ASSERT((Base::m_tags[result.first_available_index] & Base::kHasValue) == 0); + + Base::m_values[result.first_available_index].construct_unsafe(ASL_MOVE(Base::m_values[result.already_present_index].as_init_unsafe())); + Base::m_values[result.already_present_index].destroy_unsafe(); + + Base::m_tags[result.first_available_index] = result.tag; + Base::m_tags[result.already_present_index] = Base::kTombstone; + } + + ASL_ASSERT(Base::m_tags[result.first_available_index] == result.tag); + + if constexpr (sizeof...(Args1) == 0 && assignable_from) + { + Base::m_values[result.first_available_index].as_init_unsafe().value = ASL_FWD(arg0); + } + else + { + Base::m_values[result.first_available_index].as_init_unsafe().value = ASL_MOVE(V{ASL_FWD(arg0), ASL_FWD(args1)...}); + } + } + else + { + ASL_ASSERT((Base::m_tags[result.first_available_index] & Base::kHasValue) == 0); + Base::m_values[result.first_available_index].construct_unsafe(ASL_FWD(key), V{ASL_FWD(arg0), ASL_FWD(args1)...}); + Base::m_tags[result.first_available_index] = result.tag; + Base::m_size += 1; + } + + // NOLINTEND(*-pointer-arithmetic) + } + + // @Todo(C++23) Deducing this + template + requires key_hasher && key_comparator + const V* get(const U& value) const + { + isize_t index = Base::find_slot_lookup(value); + if (index >= 0) + { + // NOLINTNEXTLINE(*-pointer-arithmetic) + return &Base::m_values[index].as_init_unsafe().value; + } + return nullptr; + } + + template + requires key_hasher && key_comparator + V* get(const U& value) + { + isize_t index = Base::find_slot_lookup(value); + if (index >= 0) + { + // NOLINTNEXTLINE(*-pointer-arithmetic) + return &Base::m_values[index].as_init_unsafe().value; + } + return nullptr; + } +}; + +} // namespace asl diff --git a/asl/containers/hash_map_tests.cpp b/asl/containers/hash_map_tests.cpp new file mode 100644 index 0000000..6cb7fe1 --- /dev/null +++ b/asl/containers/hash_map_tests.cpp @@ -0,0 +1,48 @@ +#include "asl/testing/testing.hpp" +#include "asl/containers/hash_map.hpp" + +ASL_TEST(default) +{ + asl::hash_map map; + + ASL_TEST_EXPECT(!map.contains(45)); + ASL_TEST_EXPECT(!map.contains(46)); + + map.insert(45, 5); + map.insert(46, 6); + + ASL_TEST_EXPECT(map.size() == 2); + + ASL_TEST_EXPECT(map.contains(45)); + ASL_TEST_EXPECT(map.contains(46)); + ASL_TEST_EXPECT(!map.contains(47)); + + ASL_TEST_EXPECT(*map.get(45) == 5); + ASL_TEST_EXPECT(*map.get(46) == 6); + ASL_TEST_EXPECT(map.get(47) == nullptr); + + ASL_TEST_EXPECT(map.remove(45)); + ASL_TEST_EXPECT(!map.remove(45)); + + ASL_TEST_EXPECT(map.size() == 1); + + ASL_TEST_EXPECT(!map.contains(45)); + ASL_TEST_EXPECT(map.contains(46)); + ASL_TEST_EXPECT(!map.contains(47)); + + ASL_TEST_EXPECT(map.get(45) == nullptr); + ASL_TEST_EXPECT(*map.get(46) == 6); + ASL_TEST_EXPECT(map.get(47) == nullptr); + + map.insert(46, 460); + + ASL_TEST_EXPECT(map.size() == 1); + + ASL_TEST_EXPECT(!map.contains(45)); + ASL_TEST_EXPECT(map.contains(46)); + ASL_TEST_EXPECT(!map.contains(47)); + + ASL_TEST_EXPECT(map.get(45) == nullptr); + ASL_TEST_EXPECT(*map.get(46) == 460); + ASL_TEST_EXPECT(map.get(47) == nullptr); +} diff --git a/asl/containers/hash_set.hpp b/asl/containers/hash_set.hpp new file mode 100644 index 0000000..97a37f2 --- /dev/null +++ b/asl/containers/hash_set.hpp @@ -0,0 +1,418 @@ +#pragma once + +#include "asl/base/annotations.hpp" +#include "asl/base/utility.hpp" +#include "asl/base/meta.hpp" +#include "asl/memory/allocator.hpp" +#include "asl/memory/memory.hpp" +#include "asl/types/maybe_uninit.hpp" +#include "asl/hashing/hash.hpp" + +namespace asl +{ + +template +concept key_hasher = requires (const T& value) +{ + { H::hash(value) } -> same_as; +}; + +template +struct default_key_hasher +{ + constexpr static uint64_t hash(const T& value) + { + return hash_value(value); + } +}; + +template +concept key_comparator = requires(const U& a, const V& b) +{ + { C::eq(a, b) } -> same_as; +}; + +template +struct default_key_comparator +{ + constexpr static bool eq(const T& a, const T& b) + { + return a == b; + } +}; + +template< + is_object T, + allocator Allocator = DefaultAllocator, + key_hasher KeyHasher = default_key_hasher, + key_comparator KeyComparator = default_key_comparator +> +requires moveable +class hash_set +{ +protected: + static constexpr uint8_t kHasValue = 0x80; + static constexpr uint8_t kHashMask = 0x7f; + static constexpr uint8_t kEmpty = 0x00; + static constexpr uint8_t kTombstone = 0x01; + + static constexpr isize_t kMinCapacity = 8; + + // Important so we can memzero the tags + static_assert(kEmpty == 0); + + uint8_t* m_tags{}; + maybe_uninit* m_values{}; + isize_t m_capacity{}; + isize_t m_size{}; + + ASL_NO_UNIQUE_ADDRESS Allocator m_allocator; + + constexpr isize_t max_size() const + { + // Max load factor is 75% + return (m_capacity >> 1) + (m_capacity >> 2); + } + + static isize_t size_to_capacity(isize_t size) + { + ASL_ASSERT(size > 0); + return max( + kMinCapacity, + static_cast(round_up_pow2((static_cast(size) * 4 + 2) / 3))); + } + + static void insert_inner( + T&& value, + uint8_t* tags, + maybe_uninit* values, + isize_t capacity, + isize_t* size) + { + ASL_ASSERT(*size < capacity); + + const auto result = find_slot_insert(value, tags, values, capacity); + + // NOLINTBEGIN(*-pointer-arithmetic) + + ASL_ASSERT(result.first_available_index >= 0); + + if (result.already_present_index != result.first_available_index) + { + ASL_ASSERT((tags[result.first_available_index] & kHasValue) == 0); + if (result.already_present_index >= 0) + { + ASL_ASSERT((tags[result.already_present_index] & kHasValue) != 0); + values[result.already_present_index].destroy_unsafe(); + tags[result.already_present_index] = kTombstone; + } + else + { + *size += 1; + } + + values[result.first_available_index].construct_unsafe(ASL_MOVE(value)); + tags[result.first_available_index] = result.tag; + } + + // NOLINTEND(*-pointer-arithmetic) + } + + void grow_and_rehash() + { + grow_and_rehash(max(kMinCapacity, m_capacity * 2)); + } + + void grow_and_rehash(isize_t new_capacity) + { + ASL_ASSERT(new_capacity >= kMinCapacity && is_pow2(new_capacity) && new_capacity > m_capacity); + + auto* new_tags = reinterpret_cast(m_allocator.alloc(layout::array(new_capacity))); + auto* new_values = reinterpret_cast*>(m_allocator.alloc(layout::array>(new_capacity))); + asl::memzero(new_tags, new_capacity); + + isize_t new_size = 0; + + if (m_size > 0) + { + // NOLINTBEGIN(*-pointer-arithmetic) + for (isize_t i = 0; i < m_capacity; ++i) + { + if ((m_tags[i] & kHasValue) == 0) { continue; } + + insert_inner(ASL_MOVE(m_values[i].as_init_unsafe()), new_tags, new_values, new_capacity, &new_size); + + // Destroy now so that destroy() has less things to do + m_values[i].destroy_unsafe(); + m_tags[i] = kTombstone; + } + // NOLINTEND(*-pointer-arithmetic) + } + + ASL_ASSERT(new_size == m_size); + + m_size = 0; + destroy(); + + m_tags = new_tags; + m_values = new_values; + m_capacity = new_capacity; + m_size = new_size; + } + + void clear_values() + { + if constexpr (!trivially_destructible) + { + if (m_size > 0) + { + for (isize_t i = 0; i < m_capacity; ++i) + { + if ((m_tags[i] & kHasValue) != 0) // NOLINT(*-pointer-arithmetic) + { + m_values[i].destroy_unsafe(); // NOLINT(*-pointer-arithmetic) + } + } + } + } + } + + void copy_from(const hash_set& other) + { + if (other.size() > 0) + { + isize_t min_capacity = size_to_capacity(other.size()); + if (m_capacity < min_capacity) + { + grow_and_rehash(min_capacity); + } + ASL_ASSERT(m_capacity >= min_capacity); + + for (isize_t i = 0; i < other.m_capacity; ++i) + { + if ((other.m_tags[i] & kHasValue) != 0) // NOLINT(*-pointer-arithmetic) + { + insert(other.m_values[i].as_init_unsafe()); // NOLINT(*-pointer-arithmetic) + } + } + } + } + + struct FindSlotResult + { + uint8_t tag{}; + isize_t first_available_index = -1; + isize_t already_present_index = -1; + }; + + template + requires key_hasher && key_comparator + static FindSlotResult find_slot_insert( + const U& value, + const uint8_t* tags, + const maybe_uninit* values, + isize_t capacity) + { + ASL_ASSERT(is_pow2(capacity)); + + FindSlotResult result{}; + + const isize_t capacity_mask = capacity - 1; + const uint64_t hash = KeyHasher::hash(value); + const auto starting_index = static_cast(hash >> 7) & capacity_mask; + + result.tag = static_cast(hash & kHashMask) | kHasValue; + + // NOLINTBEGIN(*-pointer-arithmetic) + + for ( + isize_t i = starting_index; + i != starting_index || result.first_available_index < 0; + i = (i + 1) & capacity_mask) + { + uint8_t t = tags[i]; + + if ((t & kHasValue) == 0 && result.first_available_index < 0) + { + result.first_available_index = i; + } + + if (t == result.tag && KeyComparator::eq(values[i].as_init_unsafe(), value)) + { + ASL_ASSERT(result.already_present_index < 0); + result.already_present_index = i; + if (result.first_available_index < 0) + { + result.first_available_index = i; + } + break; + } + + if (t == kEmpty) { break; } + } + + // NOLINTEND(*-pointer-arithmetic) + + return result; + } + + template + requires key_hasher && key_comparator + isize_t find_slot_lookup(const U& value) const + { + if (m_size <= 0) { return -1; }; + + ASL_ASSERT(is_pow2(m_capacity)); + + const isize_t capacity_mask = m_capacity - 1; + const uint64_t hash = KeyHasher::hash(value); + const uint8_t tag = static_cast(hash & kHashMask) | kHasValue; + const auto starting_index = static_cast(hash >> 7) & capacity_mask; + + // NOLINTBEGIN(*-pointer-arithmetic) + + isize_t i = starting_index; + do + { + const uint8_t t = m_tags[i]; + + if (t == tag && KeyComparator::eq(m_values[i].as_init_unsafe(), value)) { return i; } + if (t == kEmpty) { break; } + + i = (i + 1) & capacity_mask; + } while (i != starting_index); + + // NOLINTEND(*-pointer-arithmetic) + + return -1; + } + + template + requires key_hasher && key_comparator + FindSlotResult find_slot_insert(const U& value) + { + return find_slot_insert(value, m_tags, m_values, m_capacity); + } + + void maybe_grow_to_fit_one_more() + { + if (m_size >= max_size()) + { + grow_and_rehash(); + } + } + +public: + constexpr hash_set() requires default_constructible + : m_allocator{} + {} + + explicit constexpr hash_set(Allocator allocator) + : m_allocator{ASL_MOVE(allocator)} + {} + + hash_set(const hash_set& other) + requires copy_constructible && copyable + : hash_set{other.m_allocator} + { + copy_from(other); + } + + hash_set& operator=(const hash_set& other) + requires copyable + { + if (&other != this) + { + clear(); + copy_from(other); + } + return *this; + } + + hash_set(hash_set&& other) + requires move_constructible + : m_tags{exchange(other.m_tags, nullptr)} + , m_values{exchange(other.m_values, nullptr)} + , m_capacity{exchange(other.m_capacity, 0)} + , m_size{exchange(other.m_size, 0)} + , m_allocator{ASL_MOVE(other.m_allocator)} + {} + + hash_set& operator=(hash_set&& other) + { + if (&other != this) + { + destroy(); + m_tags = exchange(other.m_tags, nullptr); + m_values = exchange(other.m_values, nullptr); + m_capacity = exchange(other.m_capacity, 0); + m_size = exchange(other.m_size, 0); + m_allocator = ASL_MOVE(other.m_allocator); + } + return *this; + } + + ~hash_set() + { + destroy(); + } + + void destroy() + { + clear_values(); + m_size = 0; + + if (m_capacity > 0) + { + m_allocator.dealloc(m_tags, layout::array(m_capacity)); + m_allocator.dealloc(m_values, layout::array>(m_capacity)); + m_capacity = 0; + } + } + + void clear() + { + clear_values(); + m_size = 0; + + if (m_capacity > 0) + { + asl::memzero(m_tags, m_capacity); + } + } + + constexpr isize_t size() const { return m_size; } + + template + void insert(Args&&... args) + requires constructible_from + { + maybe_grow_to_fit_one_more(); + ASL_ASSERT(m_size < max_size()); + insert_inner(ASL_MOVE(T{ASL_FWD(args)...}), m_tags, m_values, m_capacity, &m_size); + } + + template + requires key_hasher && key_comparator + bool contains(const U& value) const + { + return find_slot_lookup(value) >= 0; + } + + template + requires key_hasher && key_comparator + bool remove(const U& value) + { + isize_t slot = find_slot_lookup(value); + if (slot < 0) { return false; } + + m_values[slot].destroy_unsafe(); // NOLINT(*-pointer-arithmetic) + m_tags[slot] = kTombstone; // NOLINT(*-pointer-arithmetic) + m_size -= 1; + + return true; + } +}; + +} // namespace asl + diff --git a/asl/containers/hash_set_tests.cpp b/asl/containers/hash_set_tests.cpp new file mode 100644 index 0000000..2baab94 --- /dev/null +++ b/asl/containers/hash_set_tests.cpp @@ -0,0 +1,185 @@ +#include "asl/containers/hash_set.hpp" +#include "asl/testing/testing.hpp" +#include "asl/tests/types.hpp" +#include "asl/strings/string.hpp" +#include "asl/strings/string_view.hpp" + +ASL_TEST(empty) +{ + asl::hash_set set; + + ASL_TEST_EXPECT(set.size() == 0); + + for (int i = 0; i < 100; ++i) + { + ASL_TEST_EXPECT(!set.contains(i)); + } +} + +ASL_TEST(a_bunch_of_strings) +{ + asl::hash_set> set; + + set.insert("Hello, world!"); + ASL_TEST_EXPECT(set.size() == 1); + + set.insert("Hello, puppy!"); + ASL_TEST_EXPECT(set.size() == 2); + + set.insert("Hello, puppy!"); + ASL_TEST_EXPECT(set.size() == 2); + + ASL_TEST_EXPECT(set.contains("Hello, world!"_sv)); + ASL_TEST_EXPECT(set.contains("Hello, puppy!"_sv)); + ASL_TEST_EXPECT(!set.contains("Hello, Steven!"_sv)); +} + +ASL_TEST(a_bunch_of_ints) +{ + asl::hash_set set; + + int count = 3000; + + for (int i = 0; i < count; ++i) + { + set.insert(i); + } + + ASL_TEST_EXPECT(set.size() == count); + + for (int i = 0; i < count * 2; ++i) + { + ASL_TEST_EXPECT(set.contains(i) == (i < count)); + } +} + +struct HashWithDestructor: public DestructorObserver +{ + int x; + + HashWithDestructor(int x_, bool* ptr) + : DestructorObserver{ptr} + , x{x_} + {} + + constexpr bool operator==(const HashWithDestructor& other) const + { + return x == other.x; + } +}; + +struct CustomComparator +{ + static bool eq(const HashWithDestructor& a, const HashWithDestructor& b) + { + return a.x == b.x; + } + + static bool eq(const HashWithDestructor& a, int b) + { + return a.x == b; + } +}; + +struct CustomHasher +{ + static uint64_t hash(const HashWithDestructor& b) + { + return asl::hash_value(b.x); + } + + static uint64_t hash(int x) + { + return asl::hash_value(x); + } +}; + +ASL_TEST(destructor_and_remove) +{ + static constexpr int kCount = 200; + bool destroyed[kCount]{}; + + { + asl::hash_set set; + + for (int i = 0; i < kCount; ++i) + { + set.insert(i, &destroyed[i]); // NOLINT + } + + ASL_TEST_EXPECT(set.size() == kCount); + + for (int i = 0; i < kCount; ++i) + { + ASL_TEST_EXPECT(!destroyed[i]); // NOLINT + } + + for (int i = 0; i < kCount; i += 2) + { + ASL_TEST_EXPECT(set.remove(i)); + } + + for (int i = 0; i < kCount; i += 2) + { + ASL_TEST_EXPECT(!set.contains(i)); + ASL_TEST_EXPECT(set.contains(i+1)); + ASL_TEST_EXPECT(destroyed[i]); // NOLINT + ASL_TEST_EXPECT(!destroyed[i + 1]); // NOLINT + } + } + + for (int i = 0; i < kCount; ++i) + { + ASL_TEST_EXPECT(destroyed[i]); // NOLINT + } +} + +ASL_TEST(copy) +{ + asl::hash_set set1; + + for (int i = 0; i < 100; ++i) + { + set1.insert(i); + } + + asl::hash_set set2 = set1; + asl::hash_set set3; + set3 = set1; + + ASL_TEST_EXPECT(set2.size() == 100); + ASL_TEST_EXPECT(set3.size() == 100); + + for (int i = 0; i < 100; ++i) + { + ASL_TEST_EXPECT(set2.contains(i)); + ASL_TEST_EXPECT(set3.contains(i)); + } +} + +ASL_TEST(move) +{ + asl::hash_set set1; + + for (int i = 0; i < 100; ++i) + { + set1.insert(i); + } + + asl::hash_set set2 = ASL_MOVE(set1); + + ASL_TEST_EXPECT(set2.size() == 100); + for (int i = 0; i < 100; ++i) + { + ASL_TEST_EXPECT(set2.contains(i)); + } + + set1 = ASL_MOVE(set2); + + ASL_TEST_EXPECT(set1.size() == 100); + for (int i = 0; i < 100; ++i) + { + ASL_TEST_EXPECT(set1.contains(i)); + } +} + -- cgit