okaylib

C++20 STL replacement for realtime and memory-constrained domains.

goals

Replace some of the C++20 STL with absolutely no concern for backwards compatibility. Backport and improve std::ranges ranges and range adaptors such as enumerate, sliding_window, etc. Provide a variety of containers which all use polymorphic allocators by default, and error by value instead of using exceptions. Additionally provide multithreading primitives for C++20 users, such as a thread pool and coroutine runtime. Provide serialization to string and JSON for all types. Do bounds / error checking in both release and debug mode specifically to detect undefined behavior (with an OKAYLIB_FAST_UNSAFE macro to disable it).

okaylib is a personal project which is intended to focus many disparate efforts of mine to make C and C++ libraries into one mega-project. I have plan to use it myself in some of my other projects, but any actual releases (along with support for build systems that people actually use, like CMake) are a ways off.

examples

int main(int argc, const char* argv[])
{
    using namespace ok;
    slice<const char*> arguments = raw_slice(*argv, size_t(argc));

    // print out arguments with their indices
    for (auto& [ arg, index ] : enumerate(arguments)) {
        fmt::println("Argument {}: {}", index, arg);
    }

    // skip arguments that start with the word "skip", to demonstrate .keep_if()
    constexpr auto does_not_start_with_skip = [](const char* str){
        return !ascii_view::from_cstring(str).startswith("skip");
    };
    for (auto& [ arg, index ] : iter(arguments).keep_if(does_not_start_with_skip).enumerate()) {
        fmt::println("Argument {}: {}", index, arg);
    }
}

Demonstration of allocators (non-polymorphic usage, static dispatch), and arraylist_t.

int main()
{
    using namespace ok;
    c_allocator_t working_allocator;

    // we are going to allocate out this memory, but it's not enough, on
    // purpose, to demonstrate OOM error handling
    maybe_undefined_array_t<uint8_t, 2> raw_bytes;

    // create an arena which allocates into the 2 byte stack buffer given above
    arena_t arena(raw_bytes);

    // create an arraylist of arraylists which contain ints
    arraylist_t alist =
        arraylist::empty<arraylist_t<int, arena_t<>>>(working_allocator);

    // to demonstrate that c_allocator_t works, just allocate some unused space
    alist.increase_capacity_by_at_least(10).or_panic();

    // arraylist has a constructor, `arraylist::copy_items_from_iterator`. Pass
    // in that constructor followed by its arguments (the allocator that the
    // sub-arraylist should use, and the items to copy into it).
    constexpr auto initial_contents = maybe_undefined_array_t{1, 2, 3, 4, 5, 6};
    const auto append_status = alist.append(arraylist::copy_items_from_iterator,
                                            arena, iter(initial_contents));

    // The above operation should fail because we gave the sub arraylist the
    // arena with not enough space to allocate
    fmt::println("Tried to create a new array inside of `alist`, got return code {}", append_status);
    fmt::println("Size of `alist`: {}", alist.size());
}

Outputs:

Tried to create a new array inside of `alist`, got return code [status::alloc::error::oom]
Size of `alist`: 0

todo

• polymorphic allocator interface
• remove expand_front and co from allocator interface
• arena allocator
• linked arena allocator (arena but it uses a backward linked list of separate blocks)
• interface for arena allocators which passes function pointers to destructors, allowing the arenas to keep a list of destructors to call
• block allocator
• slab allocator
• page allocator
• remapping page allocator
• <memory_resource> wrapper allocator
• linked blockpool allocator (like block allocator but noncontiguous buffer)
• linked slab allocator (like slab allocator but implemented with linked blockpools instead of block allocators)
• <type_traits> reimplementation
• <tuple> reimplementation
• <atomic> reimplementation (partially complete, for unsigned ints)
• <compare> replacement
• compile time nameof function, which gets a const char* of the string display name of the type.
• compile time reflection on the field types and names of POD structs
• compile time reflection on the names of enum variants, string <-> enum conversion
• "result" type: optional with enum error value. like std::expected, kind of
• "opt" type: optional but supports reference types with rebinding assignment
• opt and result are constexpr + trivial, if their payloads are
• slice type: like span but not default constructible as null/empty, and bounds-checked by default
• defer statement
• stdmem: functions for checking if slices are overlapping, contained within, etc
• new iterators, with lower barrier to entry. not backwards compatible with algorithms that use legacy iterators or c++20 iterators. Designed for easy implementation, good codegen, and immediate rangelike support (type with iterator stuff should also be a range)
• WIP SIMD vector and matrix types, explicit by default but with optional operator overloading. inspired by DirectXMath
• A dynamic bit array and a static bit array with boolean-like iterators, to prove capability of new iterators
• std::ranges reimplementation, with some new views. enumerate, zip, take, drop, join, keep_if, reverse, transform. Template specialization / optimization when the viewed type is array-like.
• More views (which will require allocation + error handling): sliding window, chunking view, split view.
• Add user-defined error values to the result. Also add some kind of anyhow error type result.
• sane std::string replacement, inspired a bit by Godot's String
• static_string: const char* replacement which stores its length and has a lot of nice string operations. never does allocation.
• A low friction variant which is something like std::variant<int, float, string>
• A fast hashmap, maybe one of the flat hash sets / maps from Google, with support for emplace_back which can error by value
• A std::vector replacement with a better name (ok::arraylist?) which does not throw and supports emplace_back or push_back erroring by value. can yield its contents with some slice<T> release() function
• A std::inplace_vector replacement: ok::fixed_arraylist_t
• A collection whose items can be accessed by a stable handle, instead of index, but keeps items in contiguous memory for fast iteration. Includes generation information in handle for lock and key type memory saftey and debugging.
• An arraylist type which does not store its elements contiguously but rather in roughly cache-line-sized blocks, then has an array of pointers to blocks. constant time lookup and less memory fragementation
• an allocator aware unique_ptr replacement
• an allocator aware shared_ptr replacement
• fold/reduce function(s) compatible with above views
• reimplementation of <algorithm> stuff: stable_sort, sort, copy_if, copy, move, count, count_if mismatch find, starts_with, ends_with, contains, fill, find_if, any_of, all_of, is_sorted, unique, shuffle, rotate, reverse, swap, binary_search, equal, max_element, max, min, min_element, minmax_element, clamp, and copying vs. in-place variants for all algorithms. This is rangelike though- no need for begin() and end() as separate arguments
• coroutine-running threadpool with work queues and task stealing
• threadpool compatibility for some views which are embarassingly parellel, like count* or max_element. Specific threadsafe container iterator type? iterables are all extremely templated, so this will be interesting.
• standard coroutine types: task, generator
• coroutines which can use thread's context allocator
• Zig buildsystem module which makes it easy to import it into a zig project and propagate up information about compilation flags (get an error if you do something like enable bounds checking but a library youre calling into explicitly disables them)
• One day, far down the line: c++ modules support for zig build system, add c++ modules support to okaylib.

misc improvements / backlog

• Remove static_asserts from all fmt::formatters so users can check if something with a view in it is formattable with fmt::is_formattable. replace w/ enable_if.
• Remove dependency on <memory> header from okay/detail/addressof.h
• Add option to disable undefined behavior checks which are normally on in both release and debug mode (such as array bounds checks on iterators)
• Offer alternative version of (or redo) *_arc_t types so that weak pointers also keep the object alive. Maybe change the name of "weak" arc to something like "frozen" arc.
• Create "minimum viable" ranges for forward, multipass, bidirectional, random access, and contiguous ranges, to test conformance of all the views
• Add tests for all the views with a finite + random access range
• Make sure every constructor of opt and res (converting constructors esp.) have test coverage
• Add better static asserts for when you use an invalid range with a pipe operator- right now errors come from inside the range adaptor closure
• Add some concept of being infinite and arraylike. Currently infinite ranges like ok::indices are not arraylike, which makes enumerate(array) more space efficient than zip(array, indices).
• Add something like alloc::flags::allow_overlapping for when the user wants to grow the buffer as much as possible in one atomic operation, allowing for the allocator to figure out if maybe expanding back is a good way to achieve that. The user can find out if the returned memory is overlapping by calling ok::memoverlaps

relevant papers and blogs

• The One Ranges Proposal
• Pipe support for user-defined range adaptors
• Introduction of std::colony to the standard library
• Barry's C++ Blog:
  • T* makes for a poor optional<T&>
  • What's the right hash table API?
  • (the most influential on the ranges design alongside Pipe support for user-defined range adaptors) above: What's so hard about views::enumerate?
• Improving STL Allocators
• Upgrading the Interface of Allocators using API Versioning
  • Referenced by Improving STL Allocators
• Size feedback in operator new