summaryrefslogtreecommitdiff
path: root/asl/containers
diff options
context:
space:
mode:
Diffstat (limited to 'asl/containers')
-rw-r--r--asl/containers/BUILD.bazel58
-rw-r--r--asl/containers/buffer.hpp459
-rw-r--r--asl/containers/buffer_tests.cpp603
-rw-r--r--asl/containers/hash_map.hpp178
-rw-r--r--asl/containers/hash_map_tests.cpp48
-rw-r--r--asl/containers/hash_set.hpp418
-rw-r--r--asl/containers/hash_set_tests.cpp185
7 files changed, 1949 insertions, 0 deletions
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<is_object T, allocator Allocator = DefaultAllocator>
+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<T*> + size_of<isize_t> + size_of<size_t>;
+
+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<T>;
+ }();
+
+private:
+ static_assert(align_of<T> <= align_of<T*>);
+ static_assert(align_of<T*> == align_of<isize_t>);
+ static_assert(align_of<T*> == align_of<size_t>);
+
+ 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_t>(size) | kOnHeapMask;
+ }
+
+ static constexpr isize_t decode_size(size_t size_encoded)
+ {
+ if constexpr (kInlineCapacity == 0)
+ {
+ return is_on_heap(size_encoded)
+ ? static_cast<isize_t>(size_encoded & (~kOnHeapMask))
+ : 0;
+ }
+ else
+ {
+ return is_on_heap(size_encoded)
+ ? static_cast<isize_t>(size_encoded & (~kOnHeapMask))
+ : static_cast<isize_t>(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<T> && 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<size_t>(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<T>)
+ {
+ 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<const T> 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<typename... Args>
+ void resize_inner(isize_t new_size, Args&&... args)
+ requires constructible_from<T, Args&&...>
+ {
+ 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<T>(it, ASL_FWD(args)...);
+ }
+ }
+
+public:
+ constexpr buffer() requires default_constructible<Allocator> = default;
+
+ explicit constexpr buffer(span<const T> s)
+ requires default_constructible<Allocator>
+ : buffer{}
+ {
+ copy_range(s);
+ }
+
+ explicit constexpr buffer(Allocator allocator)
+ : m_allocator{ASL_MOVE(allocator)}
+ {}
+
+ explicit constexpr buffer(span<const T> s, Allocator allocator)
+ : m_allocator{ASL_MOVE(allocator)}
+ {
+ copy_range(s);
+ }
+
+ constexpr buffer(const buffer& other)
+ requires copy_constructible<Allocator> && copyable<T>
+ : m_allocator{other.m_allocator}
+ {
+ copy_range(other);
+ }
+
+ constexpr buffer(buffer&& other)
+ requires moveable<T>
+ : buffer(ASL_MOVE(other.m_allocator))
+ {
+ move_from_other(ASL_MOVE(other), false);
+ }
+
+ constexpr buffer& operator=(const buffer& other)
+ requires copyable<T>
+ {
+ if (&other == this) { return *this; }
+ copy_range(other);
+ return *this;
+ }
+
+ constexpr buffer& operator=(buffer&& other)
+ requires moveable<T>
+ {
+ 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<T>(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<isize_t>(round_up_pow2(static_cast<uint64_t>(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<T>(old_capacity);
+ auto new_layout = layout::array<T>(new_capacity);
+
+ if (currently_on_heap && trivially_move_constructible<T>)
+ {
+ m_data = reinterpret_cast<T*>(m_allocator.realloc(m_data, old_layout, new_layout));
+ m_capacity = new_capacity;
+ return;
+ }
+
+ T* new_data = reinterpret_cast<T*>(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<T> && trivially_destructible<T>
+ {
+ reserve_capacity(new_size);
+ set_size(new_size);
+ }
+
+ constexpr void resize_zero(isize_t new_size)
+ requires trivially_default_constructible<T> && trivially_destructible<T>
+ {
+ isize_t old_size = size();
+ resize_uninit(new_size);
+
+ if (new_size > old_size)
+ {
+ memzero(data() + old_size, (new_size - old_size) * size_of<T>);
+ }
+ }
+
+ void resize(isize_t new_size)
+ requires default_constructible<T>
+ {
+ 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, decltype(args)&&...>
+ {
+ T* uninit = push_uninit();
+ T* init = construct_at<T>(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<const T*>(this);
+ }
+ }
+
+ T* data()
+ {
+ if constexpr (kInlineCapacity == 0)
+ {
+ return m_data;
+ }
+ else
+ {
+ return is_on_heap() ? m_data : reinterpret_cast<T*>(this);
+ }
+ }
+
+ // @Todo(C++23) Use deducing this
+ constexpr contiguous_iterator<const T> begin() const { return contiguous_iterator{data()}; }
+ constexpr contiguous_iterator<const T> end() const { return contiguous_iterator{data() + size()}; }
+
+ constexpr contiguous_iterator<T> begin() { return contiguous_iterator{data()}; }
+ constexpr contiguous_iterator<T> end() { return contiguous_iterator{data() + size()}; }
+
+ // @Todo(C++23) Deducing this
+ constexpr operator span<const T>() const // NOLINT(*-explicit-conversions)
+ {
+ return as_span();
+ }
+
+ constexpr operator span<T>() // NOLINT(*-explicit-conversions)
+ {
+ return as_span();
+ }
+
+ constexpr span<const T> as_span() const
+ {
+ return span<const T>{data(), size()};
+ }
+
+ constexpr span<T> as_span()
+ {
+ return span<T>{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<typename H>
+ requires hashable<T>
+ 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<int32_t>::kInlineCapacity == 5);
+static_assert(asl::buffer<int64_t>::kInlineCapacity == 2);
+static_assert(asl::buffer<char>::kInlineCapacity == 23);
+static_assert(asl::buffer<Big>::kInlineCapacity == 0);
+
+ASL_TEST(default_size)
+{
+ asl::buffer<int32_t> b1;
+ ASL_TEST_EXPECT(b1.size() == 0);
+ ASL_TEST_EXPECT(b1.capacity() == 5);
+ ASL_TEST_EXPECT(static_cast<const void*>(b1.data()) == &b1);
+
+ asl::buffer<Big> 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<CounterAllocator>);
+
+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<IncompatibleAllocator>);
+
+ASL_TEST(reserve_capacity)
+{
+ isize_t count = 0;
+ asl::buffer<int32_t, CounterAllocator> 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<int32_t> 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<int> 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<MoveableType>);
+static_assert(!asl::trivially_move_constructible<MoveableType>);
+static_assert(!asl::copyable<MoveableType>);
+static_assert(asl::move_constructible<MoveableType>);
+
+ASL_TEST(push_move)
+{
+ asl::buffer<MoveableType> b;
+
+ static_assert(asl::buffer<MoveableType>::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<int32_t> 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<DestructorObserver>::kInlineCapacity == 2);
+
+ASL_TEST(clear_destructor_small)
+{
+ bool d0 = false;
+ bool d1 = false;
+
+ asl::buffer<DestructorObserver> 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<DestructorObserver> 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<DestructorObserver> buf;
+ buf.push(&d[0]);
+ buf.push(&d[1]);
+ buf.push(&d[2]);
+
+ {
+ asl::buffer<DestructorObserver> 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<uint64_t> buf;
+ buf.push(1U);
+ buf.push(2U);
+
+ asl::buffer<uint64_t> 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<DestructorObserver> buf;
+ buf.push(&d[0]);
+ buf.push(&d[1]);
+
+ {
+ asl::buffer<DestructorObserver> 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<DestructorObserver> buf;
+ asl::buffer<DestructorObserver> 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<int64_t, CounterAllocator> buf{CounterAllocator{&alloc_count}};
+ asl::buffer<int64_t, CounterAllocator> 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<int64_t, CounterAllocator> buf{CounterAllocator{&alloc_count}};
+ asl::buffer<int64_t, CounterAllocator> 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<DestructorObserver> buf;
+ asl::buffer<DestructorObserver> 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<DestructorObserver, IncompatibleAllocator> buf;
+ asl::buffer<DestructorObserver, IncompatibleAllocator> 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<int> buf;
+ buf.push(0);
+ buf.push(1);
+ buf.push(2);
+
+ asl::buffer<int> 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<int> buf;
+ buf.push(0);
+ buf.push(1);
+ buf.push(2);
+
+ asl::buffer<int> 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<int> buf;
+ buf.push(0);
+ buf.push(1);
+ buf.push(2);
+
+ asl::buffer<int> 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<int> 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<int> 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<int> 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<typename K, typename V>
+struct Slot
+{
+ K key;
+ V value;
+};
+
+template<hashable K, typename V, key_hasher<K> KeyHasher>
+struct SlotHasher : public KeyHasher
+{
+ using KeyHasher::hash;
+
+ constexpr static uint64_t hash(const Slot<K, V>& slot)
+ {
+ return KeyHasher::hash(slot.key);
+ }
+};
+
+template<equality_comparable K, typename V, key_comparator<K> KeyComparator>
+struct SlotComparator : public KeyComparator
+{
+ using KeyComparator::eq;
+
+ constexpr static bool eq(const Slot<K, V>& a, const Slot<K, V>& b)
+ {
+ r