算法比较。见http://coolshell.cn/articles/8990.html

.gitignore

*.o
main
*.out

README.md

确保gcc/valgrind/cachegrind有安装，然后

`$ make bench`

Implementation见list.c:filterOther和filterLinus。

list.c

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

#include "list.h"

Node *
mkNode(void *hd, Node *tl) {
    Node *res;
    res = malloc(sizeof(*res));
    res->hd = hd;
    res->tl = tl;
    return res;
}

static Node *
reverse1(Node *from, Node *to) {
    if (from == NULL) {
        return to;
    }
    else {
        void *hd = from->hd;
        Node *tl = from->tl;
        free(from);
        return reverse1(tl, mkNode(hd, to));
    }
}

Node *
enumFromTo(SuccFn succ, void *from, void *to) {
    Node *res = NULL;
    while (from != to) {
        res = mkNode(from, res);
        from = succ(from);
    }
    res = mkNode(to, res);
    return reverse1(res, NULL);
}

void
printList(PrintFn prnFn, Node *xs) {
    Node *orig = xs;
    printf("[");
    while (xs) {
        if (xs != orig) {
            printf(",");
        }
        prnFn(xs->hd);
        xs = xs->tl;
    }
    printf("]\n");
}

static int
constFalse(void *unused) {
    return 0;
}

void
freeList(DeallocFn dealloc, Node *node) {
}

Node *
filterOther(ToBoolFn toBool, Node *node) {
    Node *result = NULL;
    Node *prev = NULL;
    while (node) {
        if (toBool(node->hd)) {
            // Link to result
            if (!result) {
                prev = result = node;
            }
            else {
                prev->tl = node;
                prev = node;
            }
            node = node->tl;
        }
        else {
            Node *toDel = node;
            node = node->tl;

            free(toDel);
        }
    }
    return result;
}

Node *
filterLinus(ToBoolFn toBool, Node *node) {
    Node **result = &node;

    Node **currRef = result;
    Node *curr;
    while ((curr = *currRef)) {
        if (toBool(curr->hd)) {
            // Continue
            currRef = &curr->tl;
        }
        else {
            *currRef = curr->tl;
            free(curr);
        }
    }
    return *result;
}

list.h

typedef struct node {
    void        *hd;
    struct node *tl;
} Node;

typedef void *(*SuccFn)    (void *);
typedef void  (*PrintFn)   (void *);
typedef int   (*ToBoolFn)  (void *);
typedef void  (*DeallocFn) (void *);

Node *mkNode(void *, Node *);

Node *enumFromTo(SuccFn, void *, void *);

void printList(PrintFn, Node *);

void freeList(DeallocFn, Node *);

Node *filterOther(ToBoolFn, Node *);
Node *filterLinus(ToBoolFn, Node *);

main.c

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

static long
succLong(long i) {
    return i + 1;
}

static void
printLong(long i) {
    printf("%ld", i);
}

static int
isEven(long i) {
    return !(i & 1);
}

int
main(int argc, char **argv) {
    if (argc != 3) {
        return 1;
    }

    long enumTo = atoi(argv[1]);
    int isLinus = strcmp(argv[2], "--linus") == 0;

    Node *node = enumFromTo((void *) succLong, (void *) 1, (void *) enumTo);
    //printList((void *) printLong, node);

    if (isLinus)
        node = filterLinus((void *) isEven, node);
    else
        node = filterOther((void *) isEven, node);
    //printList((void *) printLong, node);

    //freeList(NULL, node);
    return 0;
}

Makefile

CC = gcc
CFLAGS = -Wall -O2
DEBUGFLAGS = -g

main : main.o list.o

bench : main
	valgrind --tool=cachegrind --cachegrind-out-file=linus.out \
		     ./main 1000000 --linus
	valgrind --tool=cachegrind --cachegrind-out-file=other.out \
		     ./main 1000000 --other
	cg_merge -o merged.out linus.out other.out
	rm linus.out other.out
	cg_annotate merged.out | less

%.o : %.c list.h
	$(CC) -c $< -o $@ $(CFLAGS) $(DEBUGFLAGS)

%.S : %.c list.h
	$(CC) -c $< -o $@ -S $(CFLAGS)

clean :
	rm main main.o list.o list.S merged.out