/*
 * Copyright (c) 2002-2005 Sendmail, Inc. and its suppliers.
 *	All rights reserved.
 *
 * By using this file, you agree to the terms and conditions set
 * forth in the LICENSE file which can be found at the top level of
 * the sendmail distribution.
 */

#include "sm/generic.h"
SM_RCSID("@(#)$Id: b-lists.c,v 1.10 2005/04/14 17:14:02 ca Exp $")

#include "sm/assert.h"
#include "sm/magic.h"
#include "sm/heap.h"
#include "sm/test.h"
#include "sm/queue.h"

#include <stdio.h>

#include <sys/time.h>
#define toseconds(x, y)	(x.tv_sec - y.tv_sec)

static int Verbose = 0;
struct timeval t1, t2;

#define GT(ti) do {	\
	if (gettimeofday((ti), NULL) < 0)	\
		perror("gettimeofday");	\
	} while (0)
#define START() GT(&t1)
#define END() GT(&t2)
#define DONE() do { if (Verbose > 0) \
	printf("function time: %ld seconds\n", toseconds(t2, t1));	\
	} while (0)

#define ELEMS	1024
#define ITER	100

struct tq_entry
{
	int			item;
	TAILQ_ENTRY(tq_entry)	entries;
};

TAILQ_HEAD(tq, tq_entry) tq_head;

typedef struct tq_entry tq_entry_T;
typedef struct tq tq_T;

static void
test_tq(int iter)
{
	int i, j, old, count;
	tq_T head;
	tq_entry_T *tqe, *np;

	TAILQ_INIT(&head);
	SM_TEST(TAILQ_EMPTY(&head));
	tqe = (tq_entry_T *) sm_malloc(ELEMS * sizeof(*tqe));
	for (i = 0; i < ELEMS; i++)
		tqe[i].item = i;

	START();
	for (j = 0; j < iter; j++)
	{
		TAILQ_INIT(&head);
		for (i = 0; i < ELEMS; i++)
		{
			TAILQ_INSERT_TAIL(&head, &(tqe[i]), entries);
		}
		old = -1;
		count = 0;
		TAILQ_FOREACH(np, &head, entries)
		{
			SM_TEST(old < np->item);
			old = np->item;
			++count;
		}
	}
	END();
	DONE();
	sm_free(tqe);
}

struct sl_entry
{
	int			item;
	SLIST_ENTRY(sl_entry)	entries;
};

SLIST_HEAD(sl, sl_entry) sl_head;

typedef struct sl_entry sl_entry_T;
typedef struct sl sl_T;

static void
test_sl(int iter)
{
	int i, j, old, count;
	sl_T head;
	sl_entry_T *sle, *np;

	SLIST_INIT(&head);
	SM_TEST(SLIST_EMPTY(&head));
	sle = (sl_entry_T *) sm_malloc(ELEMS * sizeof(*sle));
	for (i = 0; i < ELEMS; i++)
		sle[i].item = i;

	START();
	for (j = 0; j < iter; j++)
	{
		SLIST_INIT(&head);
		for (i = 0; i < ELEMS; i++)
		{
			/* tail doesn't work... */
			SLIST_INSERT_HEAD(&head, &(sle[i]), entries);
		}
		old = ELEMS + 1;
		count = 0;
		SLIST_FOREACH(np, &head, entries)
		{
			SM_TEST(old > np->item);
			old = np->item;
			++count;
		}
	}
	END();
	DONE();
	sm_free(sle);
}

struct li_entry
{
	int			item;
	LIST_ENTRY(li_entry)	entries;
};

LIST_HEAD(li, li_entry) li_head;

typedef struct li_entry li_entry_T;
typedef struct li li_T;

static void
test_li(int iter)
{
	int i, j, old, count;
	li_T head;
	li_entry_T *lie, *np;

	LIST_INIT(&head);
	SM_TEST(LIST_EMPTY(&head));
	lie = (li_entry_T *) sm_malloc(ELEMS * sizeof(*lie));
	for (i = 0; i < ELEMS; i++)
		lie[i].item = i;

	START();
	for (j = 0; j < iter; j++)
	{
		LIST_INIT(&head);
		for (i = 0; i < ELEMS; i++)
		{
			/* tail doesn't work... */
			LIST_INSERT_HEAD(&head, &(lie[i]), entries);
		}
		old = ELEMS + 1;
		count = 0;
		LIST_FOREACH(np, &head, entries)
		{
			SM_TEST(old > np->item);
			old = np->item;
			++count;
		}
	}
	END();
	DONE();
	sm_free(lie);
}

struct cq_entry
{
	int			item;
	CIRCLEQ_ENTRY(cq_entry)	entries;
};

CIRCLEQ_HEAD(cq, cq_entry) cq_head;

typedef struct cq_entry cq_entry_T;
typedef struct cq cq_T;

static void
test_cq(int iter)
{
	int i, j, old, count;
	cq_T head;
	cq_entry_T *cqe, *np;

	CIRCLEQ_INIT(&head);
	SM_TEST(CIRCLEQ_EMPTY(&head));
	cqe = (cq_entry_T *) sm_malloc(ELEMS * sizeof(*cqe));
	for (i = 0; i < ELEMS; i++)
		cqe[i].item = i;

	START();
	for (j = 0; j < iter; j++)
	{
		CIRCLEQ_INIT(&head);
		for (i = 0; i < ELEMS; i++)
		{
			CIRCLEQ_INSERT_TAIL(&head, &(cqe[i]), entries);
		}
		old = -1;
		count = 0;
		CIRCLEQ_FOREACH(np, &head, entries)
		{
			SM_TEST(old < np->item);
			old = np->item;
			++count;
		}
	}
	END();
	DONE();
	sm_free(cqe);
}


struct sq_entry
{
	int			item;
	SIMPLEQ_ENTRY(sq_entry)	entries;
};

SIMPLEQ_HEAD(sq, sq_entry) sq_head;

typedef struct sq_entry sq_entry_T;
typedef struct sq sq_T;

static void
test_sq(int iter)
{
	int i, j, old, count;
	sq_T head;
	sq_entry_T *sqe, *np;

	SIMPLEQ_INIT(&head);
	SM_TEST(SIMPLEQ_EMPTY(&head));
	sqe = (sq_entry_T *) sm_malloc(ELEMS * sizeof(*sqe));
	for (i = 0; i < ELEMS; i++)
		sqe[i].item = i;

	START();
	for (j = 0; j < iter; j++)
	{
		SIMPLEQ_INIT(&head);
		for (i = 0; i < ELEMS; i++)
		{
			SIMPLEQ_INSERT_TAIL(&head, &(sqe[i]), entries);
		}
		old = -1;
		count = 0;
		SIMPLEQ_FOREACH(np, &head, entries)
		{
			SM_TEST(old < np->item);
			old = np->item;
			++count;
		}
	}
	END();
	DONE();
	sm_free(sqe);
}


int
main(int argc, char *argv[])
{
	int c, iter;

	iter = ITER;
	while ((c = getopt(argc, argv, "l:")) != -1)
	{
		switch (c)
		{
		  case 'l':
			iter = atoi(optarg);
			break;
#if 0
		  default:
			usage(argv[0]);
			return(1);
#endif /* 0 */
		}
	}
	if (iter > ITER)
		Verbose++;
	sm_test_begin(argc, argv, "test lists");
	if (Verbose > 0)
		printf("circleq: ");
	test_cq(iter);
	if (Verbose > 0)
		printf("tailq: ");
	test_tq(iter);
	if (Verbose > 0)
		printf("slist: ");
	test_sl(iter);
	if (Verbose > 0)
		printf("list: ");
	test_li(iter);
	if (Verbose > 0)
		printf("simpleq: ");
	test_sq(iter);
	return sm_test_end();
}

#if 0

cube.dev-lab$ ./b-lists -l 100000
circleq: function time: 18 seconds
tailq: function time: 21 seconds
slist: function time: 8 seconds
list: function time: 21 seconds
simpleq: function time: 16 seconds

zardoc.esmtp.org$ ./b-lists -l 100000
circleq: function time: 9 seconds
tailq: function time: 9 seconds
slist: function time: 7 seconds
list: function time: 9 seconds
simpleq: function time: 7 seconds

sun8.dev-lab$ ./b-lists -l 100000       
circleq: function time: 14 seconds
tailq: function time: 13 seconds
slist: function time: 11 seconds
list: function time: 13 seconds
simpleq: function time: 13 seconds

aix$ $ ./b-lists -l 100000
circleq: function time: 20 seconds
tailq: function time: 19 seconds
slist: function time: 18 seconds
list: function time: 19 seconds
simpleq: function time: 18 seconds

k7.esmtp.org$ ./b-lists -l 100000
circleq: function time: 7 seconds
tailq: function time: 6 seconds
slist: function time: 4 seconds
list: function time: 6 seconds
simpleq: function time: 5 seconds
512000005 of 512000005 tests completed successfully
k7.esmtp.org$ ./b-lists -l 1000000
circleq: function time: 63 seconds
tailq: function time: 61 seconds
slist: function time: 43 seconds
list: function time: 63 seconds
simpleq: function time: 49 seconds
825032709 of 825032709 tests completed successfully


#endif /* 0 */