a solution for https://github.com/vlm/programming-exercise-c-1

normalize.c

/* # to compile:
 * $ gcc -march=native -O3 -Wall -o normalize normalize.c
 * # to run tests and benchmark:
 * $ time ./normalize chunky # tests/benchmarks chunky implementation
 * $ time ./normalize naive  # tests/benchmarks naive implementation
 * $ time ./normalize strdup # benchmarks strdup for comparison
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_PATH 2048
#define MAX_CHUNKS (MAX_PATH / 2 + 1)
#define ASSERT(x) { if (!(x)) abort() ; }

char *normalize(const char *s) {
    int chunks[MAX_CHUNKS] ;
    unsigned nchunks = 1, nlen = 0 ;
    const char *p = s ;
    char *r ;

#define TOP chunks[nchunks - 1]

#define SKIP(n) { \
    if (TOP > 0) { \
        chunks[nchunks ++] = -n ; \
        ASSERT(nchunks < MAX_CHUNKS) ; \
    } else \
        TOP -= n ; \
    p += n ; \
}

#define POP() { \
    if (nchunks > 1) { \
        nlen -= chunks[nchunks - 2] ; \
        chunks[nchunks - 2] = -chunks[nchunks - 2] ; \
        do { \
            nchunks -- ; \
            TOP += chunks[nchunks] ; \
        } while (nchunks > 1 && chunks[nchunks - 2] < 0) ; \
    } \
}

    TOP = 0 ;

    for (;;) {
        switch (*p) {
            case '/': SKIP(1) ; continue ;
            case '.':
                switch (p[1]) {
                    case '/': SKIP(2) ; continue ;
                    case 0:   SKIP(1) ; continue ;
                    case '.':
                        switch (p[2]) {
                            case '/': SKIP(3) ; POP() ; continue ;
                            case 0:   SKIP(2) ; POP() ; continue ;
                        }
                }
        }

        int n = 1 ;

        while (*p && *p != '/') {
            p ++ ;
            n ++ ;
        }

        chunks[nchunks ++] = n ;
        ASSERT(nchunks < MAX_CHUNKS) ;
        nlen += n ;

        if (!*p) break ;
        p ++ ;
    }

    r = malloc(nlen + 1) ;
    if (!r) return r ;
    r[0] = '/' ;
    unsigned curr = 1, acc = 0 ;

    for (unsigned i = 0; i < nchunks; i ++) {
        int c = chunks[i] ;
        if (c > 0)
            acc += c ;
        else {
            if (acc) {
                memcpy(r + curr, s, acc) ;
                curr += acc ;
                s += acc ;
                acc = 0 ;
            }
            s -= c ;
        }
    }
    if (acc)
        memcpy(r + curr, s, acc) ;

    return r ;
#undef TOP
#undef SKIP
#undef POP
}

char *naive(const char *s) {
    char *t = malloc(MAX_PATH), *p = t ;
    if (!t) return t ;

    *p = '/' ;

    do {
        switch (*s) {
            case '/':
                continue ;
            case '.':
                switch (s[1]) {
                    case '/':
                    case 0:
                        continue ;
                    case '.':
                        if (s[2] == '/' || s[2] == 0) {
                            s ++ ;

                            if (p - t > 0)
                                do
                                    p -- ;
                                while (*p != '/') ;

                            continue ;
                        }
                }
        }

        for (;;) {
            *++p = *s ;
            ASSERT(p < t + MAX_PATH - 1) ;
            if (*s == 0 || *s == '/') break ;
            s ++ ;
        }

    } while (*s ++) ;

    return t ;
}

static const struct { const char *src, *dst ; } tests[] = {
    {"", "/"},
    {".", "/"},
    {"..", "/"},
    {"foo", "/foo"},

    {"../bar", "/bar"},
    {"/foo/bar", "/foo/bar"},
    {"/foo/baraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/../baz", "/foo/baz"},
    {"/foo////bar/./baz/", "/foo/bar/baz/"},
    {"/foozzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz/../../baz", "/baz"},

    {"./aaaa/bb/cc/../dd/ee/../../fff/./g/./h", "/aaaa/bb/fff/g/h"},
    {"/aaa/bb/..", "/aaa/"},
    {"..qqq/zzz", "/..qqq/zzz"},
    {"/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/..", "/"}
} ;

#define N_TESTS (sizeof(tests) / sizeof(tests[0]))
#define BM_START 4

static void usage(const char *s) {
    fprintf(stderr, "usage: %s <chunky|naive|strdup>\n", s) ;
    exit(-1) ;
}

int main(int ac, const char *av[]) {
    unsigned bm_size = 0 ;
    char *(*f)(const char *) ;

    if (ac != 2) usage(*av) ;

    if (strcmp("chunky", av[1]) == 0)
        f = normalize ;
    else if (strcmp("strdup", av[1]) == 0)
        f = strdup ;
    else if (strcmp("naive", av[1]) == 0)
        f = naive ;
    else
        usage(*av) ;

    puts("## tests ##") ;
    for (unsigned i = 0; i < N_TESTS; i ++) {
        char *r = f(tests[i].src) ;
        printf("'%s' -> '%s': ", tests[i].src, tests[i].dst) ;

        if (i >= BM_START)
            bm_size += strlen(tests[i].src) ;

        if (strcmp(r, tests[i].dst))
            printf("FAIL: '%s'\n", r) ;
        else
            printf("ok\n") ;
        free(r) ;
    }

    int n = 1e7 ;
    printf("\n## benchmark (n = %d, %.1fMB) ##\n",
            n, (double)n / (1 << 20) * bm_size) ;

    while (n --)
        for (unsigned i = BM_START; i < N_TESTS; i ++)
            free(f(tests[i].src)) ;

    return 0 ;
}