#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/time.h>
#include <sys/resource.h>

typedef union __genlink {
	struct {
		union __genlink	*qcl_prev;
		union __genlink	*qcl_next;
	} qcl; /* Queue of Cycle List */
	void	*point[2];
	union	__genlink *link[2];
} genlink;

void
qcl_init(genlink *root) {
	root->qcl.qcl_next = root;
	root->qcl.qcl_prev = root;
}

void
qcl_insert_after(genlink *root, genlink *p) {
	genlink	*next;

	p->qcl.qcl_prev = root;
	p->qcl.qcl_next = (next = root->qcl.qcl_next);
	root->qcl.qcl_next = p;
	next->qcl.qcl_prev = p;
}

#define COUNT	10000000
#define REPEAT	1000

long long
rusage_print(const char *s, struct rusage *oru) {
	struct	rusage ru;
	int	sec;
	int	usec;
	long long ret;

	getrusage(RUSAGE_SELF, &ru);
	sec = ru.ru_utime.tv_sec - oru->ru_utime.tv_sec;
	if ((usec = ru.ru_utime.tv_usec - oru->ru_utime.tv_usec) < 0) {
		sec--;
		usec = 1000000 + usec;
	}
	printf("%s: user time %d.%6.6d\n", s, sec, usec);
	fflush(stdout);
	ret = sec*1000000;
	ret += usec;
	return ret;
}

main() {
	genlink	root;
	genlink	*p;
	genlink	*base;
	int	i;
	int	k;
	struct rusage ru;
	long long tm_normal;
	long long tm_align4;
	long long tm_align2;

	if ((base = malloc((COUNT + 1)*sizeof(genlink))) == NULL) {
		fprintf(stderr, "malloc failed\n");
		exit(1);
	}

	bzero(base, (COUNT + 1)*sizeof(genlink));
	getrusage(RUSAGE_SELF, &ru);
	bzero(base, (COUNT + 1)*sizeof(genlink));
	qcl_init(&root);
	for (i = 0; i < COUNT; i++) {
		p = (genlink *)(((char *)(&base[i])) + sizeof(genlink)); // add compenstion.
		qcl_insert_after(&root, p);
	}
	for (k = 0, p = &root; k < REPEAT; k++)
		for (i = 0; i < COUNT; i++)
			p = p->qcl.qcl_next;
	tm_normal = rusage_print("align for two pointers", &ru);

	bzero(base, (COUNT + 1)*sizeof(genlink));
	getrusage(RUSAGE_SELF, &ru);
	bzero(base, (COUNT + 1)*sizeof(genlink));
	qcl_init(&root);
	for (i = 0; i < COUNT; i++) {
		p = (genlink *)(((char *)(&base[i])) + 4);
		qcl_insert_after(&root, p);
	}
	for (k = 0, p = &root; k < REPEAT; k++)
		for (i = 0; i < COUNT; i++)
			p = p->qcl.qcl_next;
	tm_align4 = rusage_print("align for 4 bytes", &ru);

	bzero(base, (COUNT + 1)*sizeof(genlink));
	getrusage(RUSAGE_SELF, &ru);
	bzero(base, (COUNT + 1)*sizeof(genlink));
	qcl_init(&root);
	for (i = 0; i < COUNT; i++) {
		p = (genlink *)(((char *)(&base[i])) + 2);
		qcl_insert_after(&root, p);
	}
	for (k = 0, p = &root; k < REPEAT; k++)
		for (i = 0; i < COUNT; i++)
			p = p->qcl.qcl_next;
	tm_align2 = rusage_print("align for 2 bytes", &ru);

	printf("          Normal    Align4    Align2\n");
	printf("Normal  %8.2f  %8.2f  %8.2f\n",
		((double)tm_normal*100)/tm_normal,
		((double)tm_normal*100)/tm_align4,
		((double)tm_normal*100)/tm_align2
	);
	printf("Align4  %8.2f  %8.2f  %8.2f\n",
		((double)tm_align4*100)/tm_normal,
		((double)tm_align4*100)/tm_align4,
		((double)tm_align4*100)/tm_align2
	);
	printf("Align2  %8.2f  %8.2f  %8.2f\n",
		((double)tm_align2*100)/tm_normal,
		((double)tm_align2*100)/tm_align4,
		((double)tm_align2*100)/tm_align2
	);
}