The goal of the code is to enable me to express a 2D array in an unsorted coordinate-sparse representation in my code (i.e. a list of individual x, y, value entries in any order), but have this converted at compile-time to a more-readily-accessed row-sparse representation of that array (i.e. an array of pointers to rows, with empty rows as null pointers).
The Code
#include <array>
#include <cassert>
#include <iterator>
namespace ct_sparse {
template<auto defs, std::iter_value_t<decltype(defs)>::value_t fill_value> struct lut;
template<typename value_t> struct def;
namespace {
template<typename Slot, std::size_t N>
struct SlotArenaAllocator {
std::array<Slot,N>& arena;
std::size_t next_available = 0;
constexpr SlotArenaAllocator(std::array<Slot,N>& arena): arena(arena) {}
constexpr Slot* allocate() {
if (next_available < N) {
return &arena[next_available++];
} else {
if consteval {
assert(next_available < N); // Not possible to dynamically allocate at compile time
} else {
return new Slot();
}
}
}
};
template<typename Iter>
constexpr std::size_t count_width(Iter& defs) {
std::size_t width = 0;
for (const auto & entry: defs) {
if (entry.x > width) {
width = entry.x;
}
}
return width + 1; //+1 since we also need a slot for col 0
}
template<typename Iter>
constexpr std::size_t count_height(Iter& defs) {
std::size_t height = 0;
for (const auto & entry: defs) {
if (entry.y > height) {
height = entry.y;
}
}
return height + 1; //+1 since we also need a slot for row 0
}
template<std::size_t HEIGHT, typename Iter>
constexpr std::size_t count_filled_rows(Iter& defs) {
std::array<bool, HEIGHT> row_exists = {false};
std::size_t row_count = 0;
for (const auto & entry: defs) {
if (! row_exists[entry.y]) {
row_exists[entry.y] = true;
++row_count;
}
}
return row_count;
}
template<auto defs>
struct table_size_info {
constexpr static std::size_t WIDTH = count_width(defs);
constexpr static std::size_t HEIGHT = count_height(defs);
constexpr static std::size_t FILLED_ROWS = count_filled_rows<HEIGHT>(defs);
};
}
template<typename T>
struct def {
using value_t = T;
std::size_t x;
std::size_t y;
value_t value;
};
template<auto defs, std::iter_value_t<decltype(defs)>::value_t fill_value>
struct lut {
using value_t = std::iter_value_t<decltype(defs)>::value_t;
using info = table_size_info<defs>;
using table_row_t = std::array<value_t, info::WIDTH>;
std::array<table_row_t*, info::HEIGHT> index = {nullptr}; // index into the arena
std::array<table_row_t, info::FILLED_ROWS> arena = {}; // compile-time arena to place non-empty rows
constexpr lut() {
auto allocator = SlotArenaAllocator(arena);
for (const auto & entry: defs) {
if (index[entry.y] == nullptr) {
index[entry.y] = allocator.allocate();
index[entry.y]->fill(fill_value);
}
(*index[entry.y])[entry.x] = entry.value;
}
}
constexpr value_t get(const std::size_t x, const std::size_t y) const {
if (x >= info::WIDTH || y >= info::HEIGHT) return fill_value;
if (index[y] == nullptr) return fill_value;
return (*index[y])[x];
}
};
}
Usage Example
I was able to get the amount of syntax required at point-of-use to something fairly simple, and it does work:
#include <iostream>
#include <array>
#include "ct_sparse.h"
constexpr std::array definitions(std::to_array<ct_sparse::def<int>>({
{1, 1, 11},
{1, 3, 13},
{2, 3, 23},
{3, 3, 33},
}));
constexpr ct_sparse::lut<definitions, -1> table;
int main() {
std::cout << "cols: " << decltype(table)::info::WIDTH << '\n';
std::cout << "rows: " << decltype(table)::info::HEIGHT << '\n';
std::cout << "filled: " << decltype(table)::info::FILLED_ROWS << '\n';
std::cout << "size: " << sizeof(table) << '\n';
constexpr int e11 = table.get(1,1);
std::cout << "compile-time access: e11 = " << e11 << '\n';
constexpr int e12 = table.get(1,2);
std::cout << "compile-time access: e12 = " << e12 << '\n';
std::cout << "run-time access of full array:\n";
for (std::size_t y = 0; y < 5; ++y) {
for (std::size_t x = 0; x < 5; ++x) {
int value = table.get(x, y);
std::cout << value << ' ';
}
std::cout << '\n';
}
return 0;
}
Which appropriately outputs that there are 4 columns, 4 rows, 2 filled rows, 64 bytes total, and both the compile-time and run-time accesses to the array work exactly as expected.
Inspecting the compiled result on godbolt.org makes it clear that the data layout is indeed what is desired:
table:
.quad 0
.quad table+32
.zero 8
.quad table+48
.long -1
.long 11
.long -1
.long -1
.long -1
.long 13
.long 23
.long 33
(Field order aside, that's more-or-less equivalent to this:)
const int row1[] = {-1, 11, -1, -1};
const int row3[] = {-1, 13, 23, 33};
const int * const table[] = {nullptr, row1, nullptr, row3};
Specific Concerns
Fixed Template Parameters
Due to the need to count up the rows to determine how large of an arena is needed at compile-time, I couldn't find a way to avoid passing the definitions list as a template parameter. As a result, this same implementation wouldn't work at runtime; it only works if definitions is itself at least implicitly constexpr.
It would be possible to have the using code call count_height and then count_filled_rows itself, and only pass the results as template parameters, but that would inflate the syntax and make it only marginally more flexible, since the results from counting the rows of a non-constexpr input still wouldn't be valid template parameters.
I've considered that it could work to just pass in the empty definitions list for that case (making the type of lut<std::to_array<ct_sparse::def<int>>({}), -1>); add logic to the constructor to run through the input to find the width, height, and number of filled rows; store that size info in member fields; and then depend on dynamic allocation to give me somewhere to put each actual row.
This would mean those extra fields would be present in the data layout for the compile-time version as well -- and despite that, I'd still have to if consteval at every reference to info::FILLED_ROWS in order keep accesses to the compile-time ones appropriately constexpr. (AFACT there's no way to make our theoretical lut.filled_rows field const-enough to let the get use it and still be constexpr, but without forcing initializer-list initialization that would in turn dissalow having count_filled_rows depend on the result of the same evaluation of count_height as used to initialize a potential lut.height.)
Lifetime Management
In addition to the other issues, there's also an issue when it comes to trying to use dynamic memory at runtime. The current partial attempt at this you can still see in SlotArenaAllocator, but it should be clear that this would leak memory due to the lack of any attempt at lifetime management for the new-ed Slots, just returning them as bare pointers:
constexpr Slot* allocate() {
if (next_available < N) {
return &arena[next_available++];
} else {
if consteval {
assert(next_available < N); // Not possible to dynamically allocate at compile time
} else {
return new Slot(); // this leaks memory
}
}
}
On the other side though, while I'd like to handle it as a std::unique_ptr, it wouldn't be valid to go the other way either, since converting any of the actual arena slots into unique_ptrs would result in a double-free when both the arena array and the index pointer get destructed.
It seems like there's some way to resolve this by properly implementing some of the STL memory_resource interfaces for the arena and allocator, but I've not been able to make much headway in understanding how to proceed there.
Conclusion
The code I have works fine for my usage for the moment, and providing just a wholly separate implementation for non-constexpr uses wouldn't be difficult. But for future use it would be fairly desirable to be able to transparently unify them and make it not constexpr-only; any suggestions for how to approach this would be appreciated.
