/*
 * Copyright (c) 2004, 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.
 */

/*
**  Use a tree for sorting.
**  Note: this requires unique keys, hence it doesn't work for something
**  like sorting domains.
*/

#include "sm/generic.h"
SM_RCSID("@(#)$Id: t-treeinsert.c,v 1.5 2005/04/14 17:08:56 ca Exp $")
#include "sm/types.h"
#include "sm/str.h"
#include "sm/bsd-tree.h"
#include "sm/mta.h"
#include "sm/test.h"
#include "sm/io.h"
#include "sm/sysexits.h"

static int Verbose = 0;

#define SMT_NOCHECKS	0x01
#define SMT_APPEND	0x02
#define SMT_LIST	0x04

#define SM_AQ_RCPTS	256
#define RCPT_MAX_LEN	256

static char *list[] = {
	"Sendmail.ORG",
	"sendmailx.org",
	"sendmail.com",
	"Sendmail.ORG",
	"sendmail.com",
	"Sendmail.COM",
	"Sendmail.COM",
	"sendmail.com",
	"sendmail.com",
	"sendmail.com",
	"sendmail.com",
	"sendmail.com",
	"sendmail.com",
	"sendmail.org",
	"csuchico.edu",
	"niu.edu",
	"uni-kiel.de",
	"vt.edu",
	"andrew.cmu.edu",
	"onet.pl",
	"Sendmail.ORG",
	"debian.org",
	"nmt.edu",
	"uwaterloo.ca",
	"yale.edu",
	"uni-erlangen.de",
	"yahoo.com",
	"earthlink.net",
	"hotmail.com",
	"hp.com",
	"polytechnique.fr",
	"gmail.com",
	NULL
	};

typedef struct aqt_root_S	aqt_root_T, *aqt_root_P;
typedef struct aqr_tree_S	aqr_tree_T, *aqr_tree_P;
typedef struct aq_rcpt_S	aq_rcpt_T, *aq_rcpt_P;

struct aqt_root_S
{
	RB_HEAD(aqr_tree_S, aq_rcpt_S)	aqt_root;
};


struct aq_rcpt_S
{
	sm_str_P		 aqr_domain;
	RB_ENTRY(aq_rcpt_S)	 aqr_entry;
};


/*
**  AQR_CMP -- compare two tnodes
**
**	Parameters:
**		na -- aq_rcpt a
**		nb -- aq_rcpt b
**
**	Returns:
**		usual comparison code (<0, 0, >0)
*/

static int
aqr_cmp(aq_rcpt_P na, aq_rcpt_P nb)
{
	SM_REQUIRE(na != NULL);
	SM_REQUIRE(nb != NULL);
	return sm_str_casecmp(na->aqr_domain, nb->aqr_domain);
}

RB_PROTOTYPE(aqr_tree_S, aq_rcpt_S, aqr_entry, aqr_cmp)
RB_GENERATE(aqr_tree_S, aq_rcpt_S, aqr_entry, aqr_cmp)

/*
**  TREE_INSERT -- insert new elem into tree
**
**	Parameters:
**		elem -- previous element (may be NULL)
**		new -- element to insert
**
**	Returns:
**		usual sm_error code
*/

static sm_ret_T
tree_insert(aqt_root_P aqt_root, aq_rcpt_P aq_rcpt)
{
	aq_rcpt_P aq_rcpt_h;

	aq_rcpt_h = RB_INSERT(aqr_tree_S, &(aqt_root->aqt_root), aq_rcpt);
#if 0
	if (aq_rcpt_h != NULL)
		return sm_error_perm(SM_EM_Q_EDBC, EEXIST);
#endif /* 0 */
	return SM_SUCCESS;
}

static sm_ret_T
aqr_test1(aqt_root_P aqt_root, uint n)
{
	uint i;
	aq_rcpt_P aq_rcpt_nxt, aq_rcpt_prev;

	i = 0;
	aq_rcpt_prev = NULL;
	RB_FOREACH(aq_rcpt_nxt, aqr_tree_S, &(aqt_root->aqt_root))
	{
		if (Verbose > 0)
			sm_io_fprintf(smioerr,
				"LIST: %2u: aq_rcpt=%p, domain=%S\n",
				i, aq_rcpt_nxt, aq_rcpt_nxt->aqr_domain);
		++i;
		if (aq_rcpt_prev != NULL)
			SM_TEST(aqr_cmp(aq_rcpt_prev, aq_rcpt_nxt) <= 0);
		aq_rcpt_prev = aq_rcpt_nxt;
	}
	if (Verbose > 0)
	{
		if (i != n)
			sm_io_fprintf(smioerr, "i=%u, n=%u\n", i, n);
		else
			sm_io_fprintf(smioerr, "\n");
	}
	SM_TEST(i == n);
	sm_io_flush(smioerr);
	return SM_SUCCESS;
}

static sm_ret_T
aqr_test0(uint lim, uint flags)
{
	sm_ret_T ret;
	uint i;
	int r;
	sm_str_P str;
	char buf[RCPT_MAX_LEN];
	aq_rcpt_P aq_rcpt, aq_rcpt_prev;
	aqt_root_T aqt_root;

	aq_rcpt_prev = NULL;
	aq_rcpt = NULL;
	ret = SM_SUCCESS;
	srand(time(0));
	RB_INIT(&(aqt_root.aqt_root));
	for (i = 0; i < lim; i++)
	{
		aq_rcpt = sm_zalloc(sizeof(*aq_rcpt));
		SM_TEST_ERR(aq_rcpt != NULL);

		if (SM_IS_FLAG(flags, SMT_LIST) && i < SM_ARRAY_SIZE(list))
		{
			if (list[i] == NULL)
				break;
			strlcpy(buf, list[i], sizeof(buf));
		}
		else
		{
			r = rand();
			if (Verbose > 1)
				sm_io_fprintf(smioout, "i=%u, r=%8d\n", i, r);
			sm_snprintf(buf, sizeof(buf), "%d-domain.tld-%u", r, i);
		}

		str = sm_str_scpy0(NULL, buf, sizeof(buf));
		aq_rcpt->aqr_domain = str;
		str = NULL;
		ret = tree_insert(&aqt_root, aq_rcpt);
		if (sm_is_err(ret))
			goto error;
		aq_rcpt_prev = aq_rcpt;
		if (!SM_IS_FLAG(flags, SMT_NOCHECKS))
			ret = aqr_test1(&aqt_root, i + 1);
	}

	if (!SM_IS_FLAG(flags, SMT_NOCHECKS))
		ret = aqr_test1(&aqt_root, i);
	return ret;

  error:
	return ret;
}

static void
usage(const char *prg)
{
	sm_io_fprintf(smioerr, "usage: %s [options]\n", prg);
	sm_io_fprintf(smioerr, "Test AQ recipient sorting (domains are random numbers)\n");
	sm_io_fprintf(smioerr, "options:\n");
	sm_io_fprintf(smioerr, "-a    append only, don't sort\n");
	sm_io_fprintf(smioerr, "-n n  specify number of recipients to sort\n");
	sm_io_fprintf(smioerr, "-t    don't perform tests, just sort\n");
	sm_io_fprintf(smioerr, "-V    increase verbosity\n");
	exit(0);
}


int
main(int argc, char **argv)
{
	int c;
	uint n, flags;
	sm_ret_T r;
	char *prg;

	prg = argv[0];
	n = SM_AQ_RCPTS;
	flags = 0;
	while ((c = getopt(argc, argv, "aln:tV")) != -1)
	{
		switch (c)
		{
		  case 'a':
			flags |= SMT_NOCHECKS|SMT_APPEND;
			break;
		  case 'l':
			flags |= SMT_LIST;
			break;
		  case 'n':
			n = (uint) strtoul(optarg, NULL, 0);
			break;
		  case 't':
			flags |= SMT_NOCHECKS;
			break;
		  case 'V':
			++Verbose;
			break;
		  default:
			usage(prg);
			return(EX_USAGE);
		}
	}

	sm_test_begin(argc, argv, "test adbr 0");

	r = aqr_test0(n, flags);

	return sm_test_end();
}