linked-list/c/linked-list.c

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef struct node nodeT;

struct node {
    uint_fast64_t value;
    nodeT *next;
};

typedef struct result {
    size_t count;
    double total_time;
    double avg_time;
    uint_fast64_t sum;
} resultT;

nodeT *build(size_t n) {
    nodeT *first = malloc(sizeof(nodeT));
    nodeT *last = first;
    for (size_t i = 1; i < n; i++) {
        nodeT *node = malloc(sizeof(nodeT));
        node->value = i;
        last->next = node;
        last = node;
    }
    last->next = first;
    return first;
}

resultT traverse(nodeT *p) {
    struct timespec ts0;
    size_t n = 0;
    uint_fast64_t sum = 0;
    clock_gettime(CLOCK_MONOTONIC, &ts0);
    for (;;) {
        for (uint_fast32_t i = 0; i < 1000000; i++) {
            p = p->next;
            sum += p->value;
            n++;
        }

        struct timespec ts1;
        clock_gettime(CLOCK_MONOTONIC, &ts1);
        double dt = (ts1.tv_sec - ts0.tv_sec) + (ts1.tv_nsec - ts0.tv_nsec) / 1E9;
        if (dt >= 1) {
            resultT r;
            r.count = n;
            r.total_time = dt;
            r.avg_time = dt / n;
            r.sum = sum;
            return r;
        }
    }
}

void teardown(nodeT *p) {
    nodeT *first = p;
    do {
        nodeT *next = p->next;
        p->value = 0;
        p->next = NULL;
        free(p);
        p = next;
    } while (p != first);
}

int main (void) {
    size_t n;
    for (n = 2; ; n *= 2) {
        nodeT *p = build(n);
        resultT r = traverse(p);
        printf("%zu %zu %g %g %" PRIuFAST64 "\n",
               n, r.count, r.total_time, r.avg_time, r.sum);
        teardown(p);
    }
}