确保gcc/valgrind/cachegrind有安装,然后
`$ make bench`
Implementation见list.c:filterOther和filterLinus。
*.o | |
main | |
*.out |
#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; | |
} |
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 *); | |
#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; | |
} | |
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 | |