commit 0e4b6d5999e3707863870f624c2bc4ea3ce41abb
Author: Mikołaj Lenczewski <mblenczewski@gmail.com>
Date: Sun, 11 May 2025 12:16:34 +0000
Initial commit
Diffstat:
16 files changed, 642 insertions(+), 0 deletions(-)
diff --git a/.editorconfig b/.editorconfig
@@ -0,0 +1,21 @@
+root = true
+
+[*]
+end_of_line = lf
+insert_final_newline = true
+trim_trailing_whitespace = true
+charset = utf-8
+
+guidelines = 80, 120, 160
+
+[*.{c,h}]
+indent_style = tab
+indent_size = 8
+
+[*.{sh}]
+indent_style = tab
+indent_size = 8
+
+[*.{md,txt}]
+indent_style = space
+indent_size = 2
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,4 @@
+bin/
+opt/
+
+**/.*.swp
diff --git a/.gitmodules b/.gitmodules
@@ -0,0 +1,3 @@
+[submodule "thirdparty/msvc-wine"]
+ path = thirdparty/msvc-wine
+ url = https://github.com/mstorsjo/msvc-wine.git
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,18 @@
+The MIT-Zero License
+
+Copyright (c) 2025 Mikołaj Lenczewski <mikolaj@lenczewski.org>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/README b/README
@@ -0,0 +1,11 @@
+toyspp
+==============================================================================
+A small collection of C++ data structures, algorithms, and macros. Written in
+(reasonably) portable C++20. Includes basic test programs.
+
+toyspp: Building
+------------------------------------------------------------------------------
+To build for linux, simply run `build.sh`. To build for windows (from under
+linux), run `setup_win.sh` and then run `build_win.sh`. To clean, simply run
+`clean.sh`. To also clean the `opt/` directory created when setting up the
+windows SDK, run `distclean.sh`.
diff --git a/build_linux.sh b/build_linux.sh
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+CC="clang++"
+WARNINGS="-Wall -Wextra -Wpedantic ${WERROR:+-Werror} -Wno-format-pedantic"
+FLAGS="-std=c++20 -Og -g -fuse-ld=lld"
+
+set -ex
+
+mkdir -p bin
+
+$CC -o bin/test test.cpp $WARNINGS $FLAGS
diff --git a/build_win.sh b/build_win.sh
@@ -0,0 +1,13 @@
+#!/bin/sh
+
+BIN="$(realpath ./opt/bin/x64)" . ./thirdparty/msvc-wine/msvcenv-native.sh
+
+CC="clang++ --target=x86_64-pc-windows-msvc"
+WARNINGS="-Wall -Wextra -Wpedantic ${WERROR:+-Werror} -Wno-format-pedantic"
+FLAGS="-std=c++20 -Og -g -gcodeview -fuse-ld=lld -Wl,/debug:full,/pdb:"
+
+set -ex
+
+mkdir -p bin
+
+$CC -o bin/test.exe test.cpp $WARNINGS $FLAGS
diff --git a/clean.sh b/clean.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -ex
+
+rm -rf bin
diff --git a/distclean.sh b/distclean.sh
@@ -0,0 +1,7 @@
+#!/bin/sh
+
+set -ex
+
+rm -rf opt
+
+exec clean.sh
diff --git a/memory.cpp b/memory.cpp
@@ -0,0 +1,267 @@
+#include "memory.hpp"
+
+#if defined(_WIN32)
+# include <windows.h>
+# include <memoryapi.h>
+namespace {
+ uint8_t* Win32PageAlloc(size_t size, size_t alignment)
+ {
+ assert(Test::Utility::IsPowerOfTwo(alignment));
+ assert(Test::Memory::MEM_ALIGN_4_KIB <= alignment);
+
+ uintptr_t aligned_size = Test::Utility::AlignNext(size, alignment);
+
+ DWORD prot = PAGE_READWRITE;
+ DWORD flags = MEM_RESERVE | MEM_COMMIT;
+ LPVOID ptr = VirtualAlloc(nullptr, aligned_size, flags, prot);
+
+ return (uint8_t*) ptr;
+ }
+
+ Test::Memory::MirrorAllocResult Win32MirrorAlloc(size_t size, size_t mirrors)
+ {
+ assert(Test::Utility::IsAlignedTo(size, Test::Memory::MEM_ALIGN_4_KIB));
+
+ Test::Memory::MirrorAllocResult result{};
+
+ (void) size;
+ (void) mirrors;
+
+ return result;
+ }
+}
+
+#elif defined(__linux__)
+# define _GNU_SOURCE 1
+# include <sys/mman.h>
+# include <unistd.h>
+namespace {
+ uint8_t* LinuxPageAlloc(size_t size, size_t alignment)
+ {
+ assert(Test::Utility::IsPowerOfTwo(alignment));
+ assert(Test::Memory::MEM_ALIGN_4_KIB <= alignment);
+
+ int prot = PROT_READ | PROT_WRITE;
+ int flags = MAP_PRIVATE | MAP_ANONYMOUS;
+
+ uintptr_t aligned_size = Test::Utility::AlignNext(size, alignment);
+ void *unaligned_ptr = mmap(nullptr, aligned_size, PROT_NONE, flags, -1, 0);
+ if (unaligned_ptr == MAP_FAILED)
+ return nullptr;
+
+ uintptr_t aligned_base = Test::Utility::AlignNext((uintptr_t) unaligned_ptr, alignment);
+ void *aligned_ptr = mmap((void *) aligned_base, size, prot, flags | MAP_FIXED, -1, 0);
+ assert(aligned_ptr != MAP_FAILED);
+
+ if (Test::Utility::IsAlignedTo(aligned_base, Test::Memory::MEM_ALIGN_2_MIB))
+ madvise(aligned_ptr, size, MADV_HUGEPAGE);
+
+ munmap(unaligned_ptr, aligned_base - (uintptr_t) aligned_ptr);
+
+ return (uint8_t*) aligned_ptr;
+ }
+
+ Test::Memory::MirrorAllocResult LinuxMirrorAlloc(size_t size, size_t mirrors)
+ {
+ assert(Test::Utility::IsAlignedTo(size, Test::Memory::MEM_ALIGN_4_KIB));
+
+ Test::Memory::MirrorAllocResult result{};
+
+ result.len = size;
+ result.cap = size * mirrors;
+
+ int prot = PROT_READ | PROT_WRITE;
+ int buffer_flags = MAP_PRIVATE | MAP_ANONYMOUS;
+ int mirror_flags = MAP_SHARED | MAP_FIXED;
+
+ result.memfd = memfd_create("linux mirror alloc", MFD_CLOEXEC);
+ if (result.memfd < 0) {
+ goto error;
+ }
+
+ ftruncate(result.memfd, result.cap);
+
+ result.ptr = (uint8_t*) mmap(nullptr, result.cap, PROT_NONE, buffer_flags, -1, 0);
+ if (result.ptr == MAP_FAILED) {
+ close(result.memfd);
+ goto error;
+ }
+
+ for (size_t i = 0; i < mirrors; i++) {
+ uint8_t* base = result.ptr + (result.len * i);
+ void *mirror = mmap(base, result.len, prot, mirror_flags, result.memfd, 0);
+ if (mirror == MAP_FAILED) {
+ munmap(result.ptr, result.cap);
+ close(result.memfd);
+ goto error;
+ }
+ }
+
+ return result;
+
+error:
+ result.memfd = -1;
+ result.ptr = nullptr;
+ result.len = result.cap = 0;
+
+ return result;
+ }
+}
+
+#else
+# error "Unknown platform, must be one of: windows linux"
+#endif
+
+namespace Test::Memory {
+ uint8_t *GenAlloc(size_t size, size_t alignment) {
+ assert(Utility::IsPowerOfTwo(alignment));
+
+ size_t upper_bound = size + (alignment - 1);
+
+ uintptr_t ptr = (uintptr_t) malloc(upper_bound);
+ uintptr_t res = Utility::AlignNext(ptr, alignment);
+
+ return (uint8_t *) res;
+ }
+
+ uint8_t *PageAlloc(size_t size, size_t alignment) {
+ if (alignment < MEM_ALIGN_4_KIB)
+ alignment = MEM_ALIGN_4_KIB;
+
+#if defined(_WIN32)
+ return Win32PageAlloc(size, alignment);
+#elif defined(__linux__)
+ return LinuxPageAlloc(size, alignment);
+#else
+ return nullptr;
+#endif
+ }
+
+ MirrorAllocResult MirrorAlloc(size_t size, size_t mirrors) {
+#if defined(_WIN32)
+ return Win32MirrorAlloc(size, mirrors);
+#elif defined(__linux__)
+ return LinuxMirrorAlloc(size, mirrors);
+#else
+ return nullptr;
+#endif
+ }
+
+ void LinearAlloc::Init(uint8_t *buf, size_t cap)
+ {
+ ptr = buf;
+ this->cap = cap;
+ len = 0;
+ }
+
+ void LinearAlloc::Reset()
+ {
+ len = 0;
+ }
+
+ uint8_t *LinearAlloc::AllocRaw(size_t size, size_t alignment)
+ {
+ assert(size);
+ assert(alignment);
+ assert(Utility::IsPowerOfTwo(alignment));
+
+ uintptr_t currentPtr = (uintptr_t) ptr + len;
+ uintptr_t endPtr = (uintptr_t) ptr + cap;
+
+ uintptr_t alignedPtr = Utility::AlignNext(currentPtr, alignment);
+ if (endPtr < alignedPtr + size)
+ return nullptr;
+
+ len = (alignedPtr + size) - (uintptr_t) ptr;
+
+ return (uint8_t *) alignedPtr;
+ }
+
+ void BlockAlloc::Init(uint8_t *buf, size_t cap, size_t block_size, size_t block_alignment)
+ {
+ assert(Utility::IsPowerOfTwo(block_alignment));
+ assert(Utility::IsAlignedTo((uintptr_t) buf, block_alignment));
+
+ assert(sizeof(FreeListNode) <= block_size);
+ assert(alignof(FreeListNode) <= block_alignment);
+
+ ptr = buf;
+ this->cap = cap;
+ this->block_size = block_size;
+ this->block_alignment = block_alignment;
+
+ Reset();
+ }
+
+ void BlockAlloc::Reset()
+ {
+ freelist = nullptr;
+
+ for (size_t i = 0; i < cap / block_size; i++) {
+ uint8_t *block = ptr + (block_size * i);
+
+ FreeListNode *node = (FreeListNode *) block;
+ node->next = freelist;
+ freelist = node;
+ }
+ }
+
+ uint8_t *BlockAlloc::AllocRaw()
+ {
+ if (freelist == nullptr)
+ return nullptr;
+
+ FreeListNode *node = freelist;
+ freelist = node->next;
+
+ return (uint8_t *) node;
+ }
+
+ void BlockAlloc::Free(uint8_t *ptr)
+ {
+ FreeListNode *node = (FreeListNode *) ptr;
+ node->next = freelist;
+ freelist = node;
+ }
+
+ void StackAlloc::Init(uint8_t *buf, size_t cap)
+ {
+ ptr = buf;
+ this->cap = cap;
+ len = 0;
+ }
+
+ void StackAlloc::Reset()
+ {
+ len = 0;
+ }
+
+ StackAlloc::Result StackAlloc::AllocRaw(size_t size, size_t alignment)
+ {
+ assert(size);
+ assert(alignment);
+ assert(Utility::IsPowerOfTwo(alignment));
+
+ uintptr_t currentPtr = (uintptr_t) ptr + len;
+ uintptr_t endPtr = (uintptr_t) ptr + cap;
+
+ uintptr_t alignedPtr = Utility::AlignNext(currentPtr, alignment);
+ if (endPtr < alignedPtr + size) {
+ Result result{};
+ return result;
+ }
+
+ len = (alignedPtr + size) - (uintptr_t) ptr;
+
+ Result result{};
+ result.ptr = (uint8_t *) alignedPtr;
+ result.len = size;
+ result.saveptr = (uint8_t *) currentPtr;
+ return result;
+ }
+
+ void StackAlloc::Free(Result region)
+ {
+ len = region.saveptr - ptr;
+ }
+}
diff --git a/memory.hpp b/memory.hpp
@@ -0,0 +1,111 @@
+#ifndef MEMORY_HPP
+#define MEMORY_HPP
+
+#include <cstdint>
+#include <cstdlib>
+
+#include <new>
+#include <utility>
+
+#include "utility.hpp"
+
+namespace Test::Memory {
+ constexpr size_t MEM_ALIGN_4_KIB = 4 * 1024;
+ constexpr size_t MEM_ALIGN_2_MIB = 2 * 1024 * 1024;
+ constexpr size_t MEM_ALIGN_1_GIB = 1 * 1024 * 1024 * 1024;
+
+ uint8_t *GenAlloc(size_t size, size_t alignment);
+ uint8_t *PageAlloc(size_t size, size_t alignment);
+
+ struct MirrorAllocResult {
+ int memfd;
+ uint8_t *ptr;
+ size_t len, cap;
+ };
+
+ MirrorAllocResult MirrorAlloc(size_t size, size_t mirrors);
+
+ struct LinearAlloc {
+ void Init(uint8_t *buf, size_t cap);
+
+ void Reset();
+
+ uint8_t *AllocRaw(size_t size, size_t alignment);
+
+ template<typename T, size_t Count = 1, size_t Align = alignof(T)>
+ T* Alloc(auto&&... args) {
+ uint8_t *buffer = AllocRaw(sizeof(T) * Count, Align);
+ if (buffer == nullptr)
+ return nullptr;
+
+ return new (buffer) T(std::forward<decltype(args)>(args)...);
+ }
+
+ private:
+ uint8_t *ptr;
+ size_t cap, len;
+ };
+
+ struct BlockAlloc {
+ void Init(uint8_t *buf, size_t cap, size_t block_size, size_t block_alignment);
+
+ template <typename T>
+ void Init(T *buf, size_t cap) {
+ Init((uint8_t *) buf, cap * sizeof(T), sizeof(T), alignof(T));
+ }
+
+ void Reset();
+
+ uint8_t *AllocRaw();
+
+ template <typename T>
+ T *Alloc(auto&&... args) {
+ assert(sizeof(T) <= block_size);
+ assert(alignof(T) <= block_alignment);
+
+ uint8_t *block = AllocRaw();
+ if (block == nullptr)
+ return nullptr;
+
+ return new (block) T(std::forward<decltype(args)>(args)...);
+ }
+
+ void Free(uint8_t *ptr);
+
+ private:
+ uint8_t *ptr;
+ size_t cap, block_size, block_alignment;
+
+ struct FreeListNode {
+ FreeListNode *next;
+ };
+
+ FreeListNode *freelist;
+ };
+
+ struct StackAlloc {
+ void Init(uint8_t *buf, size_t cap);
+
+ void Reset();
+
+ struct Result {
+ uint8_t *ptr;
+ size_t len;
+
+ private:
+ uint8_t *saveptr;
+
+ friend StackAlloc;
+ };
+
+ Result AllocRaw(size_t size, size_t alignment);
+
+ void Free(Result region);
+
+ private:
+ uint8_t *ptr;
+ size_t cap, len;
+ };
+}
+
+#endif /* MEMORY_HPP */
diff --git a/setup_win.sh b/setup_win.sh
@@ -0,0 +1,9 @@
+#!/bin/sh
+
+set -ex
+
+git submodule update --init --recursive
+
+mkdir -p opt
+python3 ./thirdparty/msvc-wine/vsdownload.py --dest opt
+./thirdparty/msvc-wine/install.sh opt
diff --git a/test.cpp b/test.cpp
@@ -0,0 +1,119 @@
+#include "utility.hpp"
+#include "memory.hpp"
+
+#include <cstdio>
+
+struct alignas(8) mystruct {
+ int a, b, c, d;
+};
+
+int
+main(void)
+{
+ uint8_t *arr0 = Test::Memory::GenAlloc(sizeof(struct mystruct), alignof(struct mystruct));
+ assert(arr0);
+
+ struct mystruct *mystruct0 = (struct mystruct *) arr0;
+ mystruct0->a = 42;
+
+ printf("arr0: %p, mystruct0.a: %d\n", arr0, mystruct0->a);
+
+ uint8_t *arr1 = Test::Memory::PageAlloc(sizeof(struct mystruct), Test::Memory::MEM_ALIGN_2_MIB);
+ assert(arr1);
+
+ struct mystruct *mystruct1 = (struct mystruct *) arr1;
+ mystruct1->a = 69;
+
+ printf("arr1: %p, mystruct1.a: %d\n",
+ arr1, mystruct1->a);
+
+ Test::Memory::MirrorAllocResult arr2 = Test::Memory::MirrorAlloc(Test::Memory::MEM_ALIGN_4_KIB, 2);
+ assert(arr2.ptr);
+
+ struct mystruct *mystruct2a = (struct mystruct *) arr2.ptr;
+ struct mystruct *mystruct2b = (struct mystruct *) (arr2.ptr + arr2.len);
+
+ mystruct2a->a = 100;
+
+ printf("arr2: %p, mystruct2a.a: %d, mystruct2b.a: %d\n",
+ arr2.ptr, mystruct2a->a, mystruct2b->a);
+
+ {
+ uint8_t buf[1024];
+ Test::Memory::LinearAlloc arena{};
+ arena.Init(buf, sizeof buf);
+
+ arena.Reset();
+ struct mystruct *mystruct = arena.Alloc<struct mystruct>(1, 2, 3, 4);
+ assert(mystruct);
+
+ printf("LinearAlloc: mystruct: %p, %d, %d, %d, %d\n",
+ mystruct, mystruct->a, mystruct->b, mystruct->c, mystruct->d);
+
+ struct mystruct *mystruct2 = arena.Alloc<struct mystruct>(0, 0, 0, 0);
+ assert(mystruct2);
+ assert(mystruct2 != mystruct);
+
+ printf("LinearAlloc: mystruct2: %p, %d, %d, %d, %d\n",
+ mystruct2, mystruct2->a, mystruct2->b, mystruct2->c, mystruct2->d);
+ }
+
+ {
+ uint8_t buf[1024];
+ Test::Memory::BlockAlloc blocks{};
+ blocks.Init(buf, sizeof buf, sizeof(mystruct), alignof(mystruct));
+
+ struct mystruct *mystruct = blocks.Alloc<struct mystruct>(1, 2, 3, 4);
+ assert(mystruct);
+
+ printf("BlockAlloc: mystruct: %p, %d, %d, %d, %d\n",
+ mystruct, mystruct->a, mystruct->b, mystruct->c, mystruct->d);
+
+ struct mystruct *mystruct2 = blocks.Alloc<struct mystruct>(0, 0, 0, 0);
+ assert(mystruct2);
+ assert(mystruct2 != mystruct);
+
+ printf("BlockAlloc: mystruct2: %p, %d, %d, %d, %d\n",
+ mystruct2, mystruct2->a, mystruct2->b, mystruct2->c, mystruct2->d);
+ }
+
+ {
+ uint8_t buf[1024];
+ Test::Memory::StackAlloc stack{};
+ stack.Init(buf, sizeof buf);
+
+ Test::Memory::StackAlloc::Result region0 = stack.AllocRaw(256, 16);
+ assert(region0.ptr);
+
+ printf("StackAlloc: region0: %p\n", region0.ptr);
+
+ {
+ Test::Memory::StackAlloc::Result region1 = stack.AllocRaw(64, 64);
+ assert(region1.ptr);
+
+ printf("StackAlloc: region1: %p\n", region1.ptr);
+
+ stack.Free(region1);
+ }
+
+ {
+ Test::Memory::StackAlloc::Result region2 = stack.AllocRaw(64, 64);
+ assert(region2.ptr);
+
+ printf("StackAlloc: region2: %p\n", region2.ptr);
+
+ }
+
+ stack.Free(region0);
+
+ Test::Memory::StackAlloc::Result region3 = stack.AllocRaw(64, 64);
+ assert(region3.ptr);
+
+ printf("StackAlloc: region3: %p\n", region3.ptr);
+ }
+
+ return 0;
+}
+
+#include "utility.cpp"
+#include "memory.cpp"
diff --git a/thirdparty/msvc-wine b/thirdparty/msvc-wine
@@ -0,0 +1 @@
+Subproject commit 44dc13b5e62ecc2373fbe7e4727a525001f403f4
diff --git a/utility.cpp b/utility.cpp
@@ -0,0 +1 @@
+#include "utility.hpp"
diff --git a/utility.hpp b/utility.hpp
@@ -0,0 +1,41 @@
+#ifndef UTILITY_HPP
+#define UTILITY_HPP
+
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+
+namespace Test::Utility {
+ constexpr bool IsPowerOfTwo(uintptr_t value) {
+ return (value & (value - 1)) == 0;
+ }
+
+ constexpr bool IsAlignedTo(uintptr_t value, size_t alignment) {
+ assert(IsPowerOfTwo(alignment));
+
+ uintptr_t mask = (alignment - 1);
+ uintptr_t res = value & mask;
+
+ return res == 0;
+ }
+
+ constexpr uintptr_t AlignPrev(uintptr_t value, size_t alignment) {
+ assert(IsPowerOfTwo(alignment));
+
+ uintptr_t mask = ~(alignment - 1);
+ uintptr_t res = value & mask;
+
+ return res;
+ }
+
+ constexpr uintptr_t AlignNext(uintptr_t value, size_t alignment) {
+ assert(IsPowerOfTwo(alignment));
+
+ uintptr_t upper_bound = value + (alignment - 1);
+ uintptr_t res = AlignPrev(upper_bound, alignment);
+
+ return res;
+ }
+}
+
+#endif /* UTILITY_HPP */
