rax-test.c iteratorUnitTests in zig

[travisstaloch]

Hey Lloris, I'm tw0st3p on twitch. I know you're thinking of doing some kind of testing to make sure your code is producing the same results as the original. I thought this might help toward that goal. The code below uses raxInsert() and raxFind() functions from zig. The extern definitions make passing zig strings easier. I left commented out wrapper versions which work also and omit the len parameter.

Maybe this is useful to you. I don't know I was just just bored and found this interesting. :man_shrugging:

// copy all .c and .h files from antirez/rax to a folder named 'raxc'
// mkdir raxc && cp path/to/antirez/rax/*{.h,.c} raxc

// compile the rax c libs
// cd raxc && zig build-lib -lc --c-source rc4rand.c && zig build-lib -lc --c-source rax.c

// run this file's tests, linking rax c libs and including c headers
// cd .. && zig test -lc -lrax -lrc4rand -Iraxc -Lraxc test-rax.zig

const rax = @cImport({
    @cInclude("stddef.h");
    @cInclude("rax.h");
    @cInclude("rc4rand.h");
});

const std = @import("std");

// fn raxInsert(r: *rax.rax, s: [:0]const u8, data: *c_void, old: [*c]?*c_void) c_int {
//     return rax.raxInsert(r, @intToPtr([*c]u8, @ptrToInt(s.ptr)), s.len, data, old);
// }

// fn raxFind(r: *rax.rax, s: [:0]const u8) *c_void {
//     return rax.raxFind(r, @intToPtr([*c]u8, @ptrToInt(s.ptr)), s.len);
// }

extern fn raxInsert(r: *rax.rax, s: [*:0]const u8, len: usize, data: *c_void, old: [*c]?*c_void) c_int;
extern fn raxFind(r: *rax.rax, s: [*:0]const u8, len: usize) *c_void;

test "basics" {
    const r = rax.raxNew();
    var key: [:0]const u8 = "asdf";
    var data = @as(usize, 2);
    std.debug.assert(1 == raxInsert(r, key.ptr, key.len, &data, null));
    std.debug.assert(0 == raxInsert(r, key.ptr, key.len, &data, null));

    std.debug.assert(raxFind(r, key.ptr, key.len) != rax.raxNotFound);
    std.debug.assert(@ptrToInt(raxFind(r, key.ptr, key.len)) == @ptrToInt(&data));
}

test "iteratorUnitTests(void)" {
    var t = rax.raxNew();
    const toadds = [_][:0]const u8{
        "alligator",
        "alien",
        "baloon",
        "chromodynamic",
        "romane",
        "romanus",
        "romulus",
        "rubens",
        "ruber",
        "rubicon",
        "rubicundus",
        "all",
        "rub",
        "ba",
    };

    var x: usize = 0;
    while (x < 10000) : (x += 1) _ = rax.rc4rand();

    for (toadds) |toadd, i| {
        var _i = i;
        _ = raxInsert(t, toadd.ptr, toadd.len, &_i, null);
    }

    var iter: rax.raxIterator = undefined;
    rax.raxStart(&iter, t);

    const Test = struct {
        seek: [:0]const u8,
        seekop: [:0]const u8,
        expected: ?[:0]const u8,
        const Self = @This();
        fn init(seek: [:0]const u8, seekop: [:0]const u8, expected: ?[:0]const u8) Self {
            return Self{ .seek = seek, .seekop = seekop, .expected = expected };
        }
    };

    const tests = [_]Test{
        //     /* Seek value. */       /* Expected result. */
        Test.init("rpxxx", "<=", "romulus"),
        Test.init("rom", ">=", "romane"),
        Test.init("rub", ">=", "rub"),
        Test.init("rub", ">", "rubens"),
        Test.init("rub", "<", "romulus"),
        Test.init("rom", ">", "romane"),
        Test.init("chro", ">", "chromodynamic"),
        Test.init("chro", "<", "baloon"),
        Test.init("chromz", "<", "chromodynamic"),
        Test.init("", "^", "alien"),
        Test.init("zorro", "<=", "rubicundus"),
        Test.init("zorro", "<", "rubicundus"),
        Test.init("zorro", "<", "rubicundus"),
        Test.init("", "$", "rubicundus"),
        Test.init("ro", ">=", "romane"),
        Test.init("zo", ">", null),
        Test.init("zo", "==", null),
        Test.init("romane", "==", "romane"),
    };

    for (tests) |tst, i| {
        _ = rax.raxSeek(&iter, tst.seekop, @intToPtr([*c]u8, @ptrToInt(tst.seek.ptr)), tst.seek.len);
        const retval = rax.raxNext(&iter);

        if (tst.expected != null) {
            if (tst.expected.?.len != iter.key_len or !std.mem.eql(u8, tst.expected.?, iter.key[0..iter.key_len])) {
                std.debug.warn("Iterator unit test error: test {}, {} expected, {} reported. len {} key_len {}\n", .{ i, tst.expected, iter.key[0..iter.key_len], tst.expected.?.len, iter.key_len });
                return error.FailedTest;
            }
        } else {
            if (retval != 0) {
                std.debug.warn("Iterator unit test error: EOF expected in test {}\n", .{i});
                return error.FailedTest;
            }
        }
    }
    rax.raxStop(&iter);
    rax.raxFree(t);
}

[kristoff-it]

Hey tw0st3p, thank you. I did some more work today, I got to a point where I really want to see the original code run so that I can double check my understanding because I suspect I might have found a case where the algorithm could be improved (unlikely, but who knows).

So next stream I'm going to try your code out for sure. I want to see the debug prints from the C code, so if you happen to be online, make sure to say hi :)

Thanks again!

[travisstaloch]

Hey I guess I missed you today. Just sat down as your stream was ending I think. Hope to catch you next time. I'll check out the vod and see what you were up to.

[travisstaloch]

I translated a few more tests. Each test is named exactly after the function from test-rax.c which it is translated from. I put this code into gist: https://gist.github.com/travisstaloch/d2dc26daa6f02ed6ed7093369c582f28

Last one was tricky and was segfaulting in raxRemove becasue I had mis-defined data: *c_void rather than data: **c_void. :fearful:

Looks like you made some good progress. Look forward to your next stream.