/*
 * Copyright (c) 2002-2004 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: t-sortq.c,v 1.10 2004/12/29 23:47:29 ca Exp $")

#include "sm/assert.h"
#include "sm/error.h"
#include "sm/time.h"
#include "sm/heap.h"
#include "sm/test.h"
#include "sm/queue.h"

#include <stdio.h>

#define ELEMS	1024
#define ITER	100

static int elems = ELEMS;
static int Verbose = 0;

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

CIRCLEQ_HEAD(cq, cq_entry) cq_head;

typedef struct cq_entry cq_entry_T;
typedef struct cq cq_T;

#define WH_UNSORTED	0
#define WH_SORTED	1

static sm_ret_T
ins(cq_T *hd, cq_entry_T *entry)
{
	cq_entry_T *lp;

	CIRCLEQ_FOREACH(lp, hd, entries)
	{
		if (lp->item > entry->item)
		{
			CIRCLEQ_INSERT_BEFORE(hd, lp, entry, entries);
			return SM_SUCCESS;
		}
	}
	CIRCLEQ_INSERT_TAIL(hd, entry, entries);
	return SM_SUCCESS;
}


static sm_ret_T
chk(cq_T *hd, int cnt)
{
	cq_entry_T *lp;
	int i, prev;

	prev = -1;
	i = 0;
	CIRCLEQ_FOREACH(lp, hd, entries)
	{
		if (prev > lp->item)
		{
			return SM_FAILURE;
		}
		prev = lp->item;
		++i;
	}
	if (i != cnt)
	{
		return SM_FAILURE;
	}
	return SM_SUCCESS;
}


static void
test_cq(int iter)
{
	int i, j;
	cq_T head;
	cq_entry_T *cqe;
	sm_ret_T ret;

	cqe = (cq_entry_T *) sm_malloc(elems * sizeof(*cqe));
	SM_TEST(cqe != NULL);
	if (cqe == NULL)
		return;

	srand((uint) cqe + iter);
	for (j = 0; j < iter; j++)
	{
		CIRCLEQ_INIT(&head);
		SM_TEST(CIRCLEQ_EMPTY(&head));
		for (i = 0; i < elems; i++)
			cqe[i].item = (int) rand();

		for (i = 0; i < elems; i++)
		{
			ret = ins(&head, &(cqe[i]));
			SM_TEST(ret == SM_SUCCESS);
			ret = chk(&head, i + 1);
			SM_TEST(ret == SM_SUCCESS);
		}
	}
	sm_free(cqe);
}

static sm_ret_T
ins2(cq_T *hd, cq_entry_T *entry)
{
	cq_entry_T *lp;

	CIRCLEQ_FOREACH(lp, hd, entries)
	{
		if (lp->which != WH_SORTED || lp->item > entry->item)
		{
			CIRCLEQ_INSERT_BEFORE(hd, lp, entry, entries);
			return SM_SUCCESS;
		}
	}
	CIRCLEQ_INSERT_TAIL(hd, entry, entries);
	return SM_SUCCESS;
}

static sm_ret_T
chk2(cq_T *hd, int cnt)
{
	cq_entry_T *lp;
	int i, prev;

	prev = -1;
	i = 0;
	CIRCLEQ_FOREACH(lp, hd, entries)
	{
		if (Verbose > 0)
			printf("%4d: %10d (%d)\n", i, lp->item, lp->which);
		if (lp->which == WH_SORTED)
		{
			if (prev > lp->item)
				return SM_FAILURE;
			prev = lp->item;
			++i;
		}
		else
			break;
	}
	if (i != cnt)
	{
		if (Verbose > 1)
			printf("i=%d, cnt=%d\n", i, cnt);
		return SM_FAILURE;
	}
	return SM_SUCCESS;
}

static void
test_cq2(int iter)
{
	int i, j, r, items;
	cq_T head;
	cq_entry_T *cqe;
	sm_ret_T ret;
	struct timeval now;

	cqe = (cq_entry_T *) sm_malloc(elems * sizeof(*cqe));
	SM_TEST(cqe != NULL);
	if (cqe == NULL)
		return;

	i = gettimeofday(&now, NULL);
	srand((uint) cqe + iter + now.tv_usec);
	for (j = 0; j < iter; j++)
	{
		CIRCLEQ_INIT(&head);
		SM_TEST(CIRCLEQ_EMPTY(&head));
		for (i = 0; i < elems; i++)
		{
			cqe[i].item = (int) rand();
			r = (int) rand();
			cqe[i].which = (r & 0x10) ? WH_UNSORTED : WH_SORTED;
			if (Verbose > 2)
				printf("%4d: %10d (%d) %d\n", i, cqe[i].item, cqe[i].which, j);
		}
		for (i = 0; i < elems; i++)
		{
			if (cqe[i].which == WH_UNSORTED)
			{
				CIRCLEQ_INSERT_TAIL(&head, &(cqe[i]), entries);
			}
		}

		items = 0;
		for (i = 0; i < elems; i++)
		{
			if (cqe[i].which == WH_SORTED)
			{
				ret = ins2(&head, &(cqe[i]));
				SM_TEST(ret == SM_SUCCESS);
				++items;
				ret = chk2(&head, items);
				SM_TEST(ret == SM_SUCCESS);
			}
		}
	}
	sm_free(cqe);
}


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

	iter = ITER;
	while ((c = getopt(argc, argv, "e:l:V")) != -1)
	{
		switch (c)
		{
		  case 'e':
			elems = atoi(optarg);
			break;
		  case 'l':
			iter = atoi(optarg);
			break;
		  case 'V':
			Verbose++;
			break;
#if 0
		  default:
			usage(argv[0]);
			return(1);
#endif /* 0 */
		}
	}
	sm_test_begin(argc, argv, "test sorted queue");
	test_cq(iter);
	test_cq2(iter);
	return sm_test_end();
}