Moveset resolver

moveset.c

#include <stddef.h>
#include <stdint.h>

#define assert(c)    while (!(c)) *(volatile int *)0 = 0
#define countof(a)   (size)(sizeof(a) / sizeof(*(a)))
#define new(a, t, n) (t *)alloc(a, sizeof(t), _Alignof(t), n)

typedef int32_t   b32;
typedef uint32_t  u32;
typedef uint64_t  u64;
typedef uintptr_t uptr;
typedef ptrdiff_t size;
typedef char      byte;

typedef struct {
    char *beg;
    char *end;
} arena;

static void *alloc(arena *a, size objsize, size align, size count)
{
    size available = a->end - a->beg;
    size padding = (uptr)a->end & (align - 1);
    if (count > (available - padding)/objsize) {
        assert(0);
    }
    size total = objsize * count;
    char *r = a->end -= padding + total;
    for (size i = 0; i < total; i++) {
        r[i] = 0;
    }
    return r;
}

static u32 *newbits(size len, arena *perm)
{
    size n = (len + 31) >> 5;
    return new(perm, u32, n);
}

static u32 bitget(u32 *b, size i)
{
    return b[i>>5] & (u32)1<<(i & 31);
}

static void bitset(u32 *b, size i)
{
    b[i>>5] |= (u32)1<<(i & 31);
}

static u64 hash(char *s)
{
    u64 h = 0x100;
    for (; *s; s++) {
        h ^= *s & 255;
        h *= 1111111111111111111u;
    }
    return h;
}

static b32 equals(char *a, char *b)
{
    for (; *a && *a==*b; a++, b++) {}
    return *a == *b;
}

// Maps a path to its dependent/position metadata
typedef struct map map;
struct map {
    map  *child[4];
    char *path;
    map  *dependent;
    size  position;
};

static map *upsert(map **m, char *path, arena *perm)
{
    for (u64 h = hash(path); *m; h <<= 2) {
        if (equals((*m)->path, path)) {
            return *m;
        }
        m = &(*m)->child[h>>62];
    }
    if (perm) {
        *m = new(perm, map, 1);
        (*m)->path = path;
    }
    return *m;
}

typedef struct move move;
struct move {
    move *next;
    char *src;
    char *dst;
};

// Compute an optimal rename sequence to rename each source to its
// destination without clobbering. Due to cycles, some renames require a
// temporary name. Only one temporary is needed at a time. A null "src"
// or "dst" in the output indicates the temporary file.
static move *resolve(char **src, char **dst, size len, arena *perm, arena scratch)
{
    move  *head = 0;
    move **tail = &head;
    u32 *done = newbits(len, &scratch);

    // Populate the source set
    map  *srcset = 0;
    map **srcs = new(&scratch, map *, len);
    for (size i = 0; i < len; i++) {
        srcs[i] = upsert(&srcset, src[i], &scratch);
        if (i && (srcs[0]==srcs[i] || srcs[i]->position)) {
            return 0;  // duplicate
        }
        srcs[i]->position = i;
    }

    // Validate the destination set
    map *dstset = 0;
    for (size i = 0; i < len; i++) {
        map *d = upsert(&dstset, dst[i], &scratch);
        if (d->position) {
            return 0;  // duplicate
        }
        d->position = 1;  // mark as seen
    }

    // Resolve all non-cycles, potentially out of order
    for (size i = 0; i < len; i++) {
        map *dep = upsert(&srcset, dst[i], 0);
        if (dep && dep!=srcs[i] && !bitget(done, dep->position)) {
            dep->dependent = srcs[i];
        } else {
            for (map *next = srcs[i]; next; next = next->dependent) {
                move *r = *tail = new(perm, move, 1);
                tail = &r->next;
                r->src = src[next->position];
                r->dst = dst[next->position];
                bitset(done, next->position);
            }
        }
    }

    // Find and break cycles using a temporary file
    for (size i = 0; i < len; i++) {
        if (bitget(done, i)) continue;

        // Move earliest item to a temporary path
        move *r = *tail = new(perm, move, 1);
        tail = &r->next;
        r->src = src[i];
        bitset(done, i);

        // Resolve all dependents
        for (map *next = srcs[i]->dependent; next; next = next->dependent) {
            if (bitget(done, next->position)) break;
            move *r = *tail = new(perm, move, 1);
            tail = &r->next;
            r->src = src[next->position];
            r->dst = dst[next->position];
            bitset(done, next->position);
        }

        // Rename from temporary path to destination
        r = *tail = new(perm, move, 1);
        tail = &r->next;
        r->dst = dst[i];
    }

    return head;
}


// Test

static b32   oswrite(void *, size);
static void *osalloc(size);

static arena newarena(size cap)
{
    arena r = {0};
    r.beg = osalloc(cap);
    r.end = r.beg + cap;
    return r;
}

static void outstr(char *s)
{
    size len = 0;
    for (; s[len]; len++) {}
    oswrite(s, len);
}

static void test(void)
{
    arena perm = newarena(1<<25);
    arena scratch = newarena(1<<25);

    char *src[] = { "t0", "t1", "t2", "a" };
    char *dst[] = { "t1", "t2", "t0", "a" };
    size len = countof(src);
    move *r = resolve(src, dst, len, &perm, scratch);
    for (; r; r = r->next) {
        outstr(r->src ? r->src : "(tmp)");
        outstr(" -> ");
        outstr(r->dst ? r->dst : "(tmp)");
        outstr("\n");
    }
}


// Platform

#if _WIN32
// $ cc -nostartfiles -o moveset moveset.c
// $ cl moveset.c /link /subsystem:console kernel32.lib
#define W32(r) __declspec(dllimport) r __stdcall
W32(void)   ExitProcess(u32);
W32(uptr)   GetStdHandle(u32);
W32(void *) VirtualAlloc(void *, size, u32, u32);
W32(b32)    WriteFile(uptr, void *, u32, u32 *, uptr);

static b32 oswrite(void *buf, size len)
{
    u32 dummy;
    uptr stdout = GetStdHandle(-11);
    return WriteFile(stdout, buf, (u32)len, &dummy, 0);
}

static void *osalloc(size len)
{
    return VirtualAlloc(0, len, 0x3000, 4);
}

void mainCRTStartup(void)
{
    test();
    ExitProcess(0);
}

#else  // plain old C
#include <stdlib.h>
#include <unistd.h>

static b32 oswrite(void *buf, size len)
{
    return write(1, buf, len) == len;
}

static void *osalloc(size len)
{
    return malloc(len);
}

int main(void)
{
    test();
}
#endif