Zig Operate on runtime known-Length array without allocator?

Question

I think this might be less about the bubble sort itself and more about my understanding of Zig’s "style" .

My Goal

I’d like to implement bubble sort in Zig so that it returns a new array. This setup would make it easier to write simple, one-line tests.

The Problem

I can't just do that :

pub fn bubbleSort(arr: []const u8,) []const u8 {
    var arrSorted = [_]u8{0} ** arr.len;
    std.mem.copyForwards(u8, &arrSorted, arr);
    ...
}

as zig will point out that arr.len is a not known compile-time property

so i ended up doing that :

const std = @import("std");

/// O(n^2)
pub fn bubbleSort(arr: []const u8, comptime len: u8) []const u8 {
    var arrSorted = [_]u8{0} ** len;
    std.mem.copyForwards(u8, &arrSorted, arr);

    for (0..arrSorted.len) |i| {
        for (0..arrSorted.len - i - 1) |j| {
            if (arrSorted[j] > arrSorted[j + 1]) {
                const tmp = arrSorted[j];
                arrSorted[j] = arrSorted[j + 1];
                arrSorted[j + 1] = tmp;
            }
        }
    }

    return &arrSorted;
}

test "bubble sort" {
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 1, 102, 7, 4, 8, 9 }, 6));
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 102, 7, 4, 1, 8, 9 }, 6));
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 1, 102, 7, 4, 9, 8 }, 6));
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 9, 1, 102, 7, 4, 8 }, 6));
    try std.testing.expectEqualSlices(u8, &[_]u8{ 1, 4, 7, 8, 9, 102 }, bubbleSort(&[_]u8{ 1, 7, 4, 8, 9, 102 }, 6));
}

Here, I pass the length of the array as a parameter. By specifying this value directly in "plain text," it’s known at compile time, so all of this works.

My question

I know I could pass an allocator to my bubbleSort function, have it allocate memory for my array, and then defer freeing that memory in the calling code block. Would that be the right approach for what I want to achieve here?

Is there any other, simpler, faster, or more elegant way to do this?

Thanks for reading, and sorry if the title or post isn’t perfect—I couldn’t come up with a better way to explain it.

I tried to return a new array from my function without the need of an allocator or a comptime kwnown property and failed.

sigod · Accepted Answer · 2024-11-13 19:14:25Z

1

To be fair, I'm not sure if your goal of having nice one-liners in tests is achievable. Here's how the sort function is tested in the standard library: std/sort.zig:225
Your best bet is to define a helper function that does all of the heavy lifting, and you can just call it multiple times. For example:

test "example sort" {
    try help_test_sorting(std.testing.allocator, &[_]u8{ 1, 4, 7, 8, 9, 102 }, &[_]u8{ 1, 102, 7, 4, 8, 9 });
    try help_test_sorting(std.testing.allocator, &[_]u8{ 1, 4, 7, 8, 9, 102 }, &[_]u8{ 102, 7, 4, 1, 8, 9 });
    try help_test_sorting(std.testing.allocator, &[_]u8{ 1, 4, 7, 8, 9, 102 }, &[_]u8{ 1, 102, 7, 4, 9, 8 });
    try help_test_sorting(std.testing.allocator, &[_]u8{ 1, 4, 7, 8, 9, 102 }, &[_]u8{ 9, 1, 102, 7, 4, 8 });
    try help_test_sorting(std.testing.allocator, &[_]u8{ 1, 4, 7, 8, 9, 102 }, &[_]u8{ 1, 7, 4, 8, 9, 102 });
}

fn help_test_sorting(allocator: std.mem.Allocator, expected: []const u8, input: []const u8) !void {
    const inputAllocated = try allocator.dupe(u8, input);
    defer allocator.free(inputAllocated);
    std.sort.heap(u8, inputAllocated, void{}, std.sort.asc(u8));
    try std.testing.expectEqualSlices(u8, expected, inputAllocated);
}

Zig has these options for memory allocation:

Accept an allocator.
Accept the target memory.
Update the result in-line. This is often the best, because it isolates the operation. So you're free to use any memory allocation strategy you like.
Use a global allocator.

You may notice that your approach:

var arrSorted = [_]u8{0} ** len;
// ...
return &arrSorted;

is not listed in the available options. This is because it's illegal to do that. It's a common mistake newcomers make, especially if they have experience with GC languages. The memory is only owned by the function while it's executing, once it exits the memory would be reused by other functions. Depending on the program execution, this can either yeild correct results or complete nonsense.

edited Nov 13, 2024 at 19:14

answered Nov 13, 2024 at 18:35

sigod

6,7652 gold badges28 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

FObersteiner Over a year ago

see also Pointers to Temporary Memory on ziggit.dev. The problem is, it's not technically illegal - otherwise, the compiler should prevent you from doing it IMHO, but that is not the case atm.

Arakan Over a year ago

The link to the documentation really helped thanks, i do come from a "GC background". I need to look more into the inline keyword in zig.

Collectives™ on Stack Overflow

Zig Operate on runtime known-Length array without allocator?

My Goal

The Problem

My question

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

My Goal

The Problem

My question

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related