How to sort array of structs by a field?

kj4tmp · October 5, 2024, 9:44pm

I need to sort a bounded array of structs by one of their fields.

I found std.mem.sort but I’m having a little trouble figuring out how to use it?

The full problem is this:

Verify an array of memory areas is not overlapping using their start address and byte length.

I plan on attacking this problem like this:

Verify all start addresses are unique (otherwise sort won’t work?).
Sort the memory areas by start address.
Compare starting addresses and byte length after sorting to make sure they don’t overlap.

const std = @import("std");

const MemoryArea = struct {
    start_addr: u32,
    byte_length: u16,
};

const MemoryAreas = struct {
    areas: std.BoundedArray(MemoryArea, 16),

    pub fn sortByStartAddr(self: *MemoryAreas) !void {}

    pub fn sortAndVerifyNonOverlapping(self: *MemoryAreas) !void {}
};

I don’t need high performance, the size of the data is the same as above. I am prioritizing a simple solution.

kj4tmp · October 5, 2024, 10:05pm

aha there is an example here

github.com

ziglang/zig/blob/d23db9427b82d7dc798442accf34729c16e92f2d/lib/std/sort.zig#L168


      
              heap,
          };
          
          const context_sort_funcs = &[_]fn (usize, usize, anytype) void{
              // blockContext,
              pdqContext,
              insertionContext,
              heapContext,
          };
          
          const IdAndValue = struct {
              id: usize,
              value: i32,
          
              fn lessThan(context: void, a: IdAndValue, b: IdAndValue) bool {
                  _ = context;
                  return a.value < b.value;
              }
          };
          
          test "stable sort" {

Sze · October 6, 2024, 10:34am

I think sort will work, it just means that the sub-ranges of elements that compare equal will have either some arbitrary order for non-stable sorts, or if you use a stable sort they should keep their relative order to before.

So I would start with sorting and then you can iterate over it and check if there are any duplicates by comparing to the previous element. Pick the first element as the previous element and iterate from the 2nd to the end. This means you can check for duplicates with constant space, instead of needing some hash table of seen elements etc.

I think your 3. point can be done in a similar way, if it is sorted by the addresses then non of the address+length should be bigger then the next start address, so you could have a previous_end_address and compare with that. I think that would mean that you can do the sort and verify everything with a single loop over the data checking both for duplicates and the end address at the same time.

kj4tmp · October 6, 2024, 10:12pm

Got something working


pub const SMPDOBitLength = struct {
    /// index of this sync manager
    sm_idx: u8,
    /// start address in esc memory
    start_addr: u32,
    pdo_byte_length: u16,
    /// total bit length of PDOs assigned to this sync manager.
    pdo_bit_length: u16,
    direction: PDODirection,
};

pub const SMPDOBitLengths = struct {
    pdo_bit_lengths: std.BoundedArray(SMPDOBitLength, max_sm) = .{},

    fn lessThan(context: void, a: SMPDOBitLength, b: SMPDOBitLength) bool {
        _ = context;
        return a.start_addr < b.start_addr;
    }

    pub fn sortAndVerifyNonOverlapping(self: *SMPDOBitLengths) !void {
        std.sort.insertion(SMPDOBitLength, self.pdo_bit_lengths.slice(), {}, SMPDOBitLengths.lessThan);

        assert(std.sort.isSorted(SMPDOBitLength, self.pdo_bit_lengths.slice(), {}, SMPDOBitLengths.lessThan));
        for (0..self.pdo_bit_lengths.len) |i| {
            // skip last one
            if (i == self.pdo_bit_lengths.len - 1) continue;
            const this_sm = self.pdo_bit_lengths.slice()[i];
            const next_sm = self.pdo_bit_lengths.slice()[i + 1];
            if (this_sm.start_addr + this_sm.pdo_byte_length > next_sm.start_addr or
                this_sm.start_addr == next_sm.start_addr)
            {
                std.log.warn("overlapping sync managers: {}, {}", .{ self.pdo_bit_lengths.slice()[i], self.pdo_bit_lengths.slice()[i + 1] });
                return error.OverlappingSM;
            }
        }
    }
};


test "sort and verfiy non overlapping SMPDOBitLengths" {
    var pdo_bit_lengths = SMPDOBitLengths{};
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1000, .sm_idx = 2 });
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 998, .sm_idx = 4 });
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1002, .sm_idx = 1 });
    try pdo_bit_lengths.sortAndVerifyNonOverlapping();

    try std.testing.expectEqual(@as(u32, 998), pdo_bit_lengths.pdo_bit_lengths.slice()[0].start_addr);
    try std.testing.expectEqual(@as(u32, 1000), pdo_bit_lengths.pdo_bit_lengths.slice()[1].start_addr);
    try std.testing.expectEqual(@as(u32, 1002), pdo_bit_lengths.pdo_bit_lengths.slice()[2].start_addr);
}

kj4tmp · October 6, 2024, 10:16pm

Just read this, great tip!

pub fn sortAndVerifyNonOverlapping(self: *SMPDOBitLengths) !void {
        std.sort.insertion(SMPDOBitLength, self.pdo_bit_lengths.slice(), {}, SMPDOBitLengths.lessThan);
        assert(std.sort.isSorted(SMPDOBitLength, self.pdo_bit_lengths.slice(), {}, SMPDOBitLengths.lessThan));
        for (1..self.pdo_bit_lengths.len) |i| {
            const this_sm = self.pdo_bit_lengths.slice()[i];
            const last_sm = self.pdo_bit_lengths.slice()[i - 1];
            if (last_sm.start_addr + last_sm.pdo_byte_length > this_sm.start_addr or
                last_sm.start_addr == this_sm.start_addr)
            {
                std.log.warn("overlapping sync managers: {}, {}", .{ this_sm, last_sm });
                return error.OverlappingSM;
            }
        }
    }

Sze · October 6, 2024, 10:20pm

now just add this before the for loop:

if(self.pdo_bit_lengths.len <= 1) return;

I think 1..1 would evaluate to an empty loop and be fine, but I think 1..0 would be illegal in zig.

kj4tmp · October 6, 2024, 10:22pm

full implementation if anyone comes back to this

pub const SMPDOBitLength = struct {
    /// index of this sync manager
    sm_idx: u8,
    /// start address in esc memory
    start_addr: u32,
    pdo_byte_length: u16,
    /// total bit length of PDOs assigned to this sync manager.
    pdo_bit_length: u16,
    direction: PDODirection,
};

pub const SMPDOBitLengths = struct {
    pdo_bit_lengths: std.BoundedArray(SMPDOBitLength, max_sm) = .{},

    fn lessThan(context: void, a: SMPDOBitLength, b: SMPDOBitLength) bool {
        _ = context;
        return a.start_addr < b.start_addr;
    }

    pub fn sortAndVerifyNonOverlapping(self: *SMPDOBitLengths) !void {
        if (self.pdo_bit_lengths.len <= 1) return;

        std.sort.insertion(SMPDOBitLength, self.pdo_bit_lengths.slice(), {}, SMPDOBitLengths.lessThan);
        assert(std.sort.isSorted(SMPDOBitLength, self.pdo_bit_lengths.slice(), {}, SMPDOBitLengths.lessThan));
        for (1..self.pdo_bit_lengths.len) |i| {
            const this_sm = self.pdo_bit_lengths.slice()[i];
            const last_sm = self.pdo_bit_lengths.slice()[i - 1];
            if (last_sm.start_addr + last_sm.pdo_byte_length > this_sm.start_addr or
                last_sm.start_addr == this_sm.start_addr)
            {
                std.log.warn("overlapping sync managers: {}, {}", .{ this_sm, last_sm });
                return error.OverlappingSM;
            }
        }
    }
};

test "sort and verfiy non overlapping SMPDOBitLengths" {
    var pdo_bit_lengths = SMPDOBitLengths{};
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1000, .sm_idx = 2 });
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 998, .sm_idx = 4 });
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1002, .sm_idx = 1 });
    try pdo_bit_lengths.sortAndVerifyNonOverlapping();

    try std.testing.expectEqual(@as(u32, 998), pdo_bit_lengths.pdo_bit_lengths.slice()[0].start_addr);
    try std.testing.expectEqual(@as(u32, 1000), pdo_bit_lengths.pdo_bit_lengths.slice()[1].start_addr);
    try std.testing.expectEqual(@as(u32, 1002), pdo_bit_lengths.pdo_bit_lengths.slice()[2].start_addr);
}

test "overlapping sync managers" {
    var pdo_bit_lengths = SMPDOBitLengths{};
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1000, .sm_idx = 3 });
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 3, .start_addr = 998, .sm_idx = 3 });
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1002, .sm_idx = 3 });
    try std.testing.expectError(error.OverlappingSM, pdo_bit_lengths.sortAndVerifyNonOverlapping());
}

test "overlapping sync managers non unique start addr" {
    var pdo_bit_lengths = SMPDOBitLengths{};
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1000, .sm_idx = 3 });
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1000, .sm_idx = 3 });
    try pdo_bit_lengths.pdo_bit_lengths.append(SMPDOBitLength{ .direction = .tx, .pdo_bit_length = 12, .pdo_byte_length = 2, .start_addr = 1002, .sm_idx = 3 });
    try std.testing.expectError(error.OverlappingSM, pdo_bit_lengths.sortAndVerifyNonOverlapping());
}