Datastructure supporting both explicit heap and implicit stack allocation

[thin latch]

I am looking for a way to iterate over the rows of a row-major order matrix, without any copying or additional allocations.

So far the matrix data lives on the heap.

const rows = 4;
const columns = 8;

m = Matrix(f32).random(allocator, rows, columns);
defer m.deinit();

From what I understand heap allocations are relatively expensive. So I was thinking of implementing a RowIterator, whos next() function would return a stack allocated Matrix who's data is a slice to a row in the original matrix.

var row_iterator = m.iter_rows();
while (row_iterator.next()) |row| {
    // Do stuff
}

The assumption is that the programmer ensures that the matrix is not deinitalized, while iterating over the rows.

Is it a bad practise to have a datastructure which can be both stack or heap allocated, depending on how you initialize it?

[lusty shale]

wdym by stack allocation?

[thin latch]

Sorry, my question was imprecise, as the matrix data is always stored on the heap.

A better question might be, is it ok to have a datastructure that can handle both owned and unowned data.

Owned as in the matrix explicitely allocates space on the heap for it's data when being initalized.

Unowned as in the matrix does not allocate anything on the heap but receives a slice on initialization, which belongs to a different "owned" matrix.

[lusty shale]

ah, well as long as your api is intuitive and doesnt leak anything id say its fine.

although you could probably implement the RowIterator a lot easier just by doing

fn RowIterator(comptime T: type) type {
  return struct {
    mat: *const Matrix(T),
    col_index: usize,
    row_index: usize,
  
    pub fn next(self: *RowIterator) ?T {
      // ...
      // add/subtract from row_index/col_index here
      // ...
      return self.mat[self.col_index][self.row_index];
    } 
  };
}

[lusty shale]

usually with other data structures that have data that "could potentially be heap or stack" youd use an ArenaAllocator, so you wouldnt have to figure out which ones need to be freed and which dont, or you'd just make everything heap, like with a StringHashMap

[thin latch]

Do you have any ideas on how to make the API intuitive so it becomes clear you shouldn't free the owned matrix, when there are still unowned matrices refering to it?

(Other then documeting it in the doc string 😄)

[lusty shale]

a doc comment /// over the iter_rows function stating the returned RowIterator takes a pointer to the matrix and thus shouldn't outlive it should be enough

iterators in zig function pretty much exactly like that, they hold a pointer to the actual data and are expected to not outlive the thing theyre iterating over

(see ReverseIterator for a simple (ish) example)

important part is here:

    return struct {
        ptr: Pointer, // pointer to data
        index: usize, // current index
        pub fn next(self: *@This()) ?Element {
            if (self.index == 0) return null;
            self.index -= 1;
            return self.ptr[self.index]; // assumes the data lives long enough
        }