/*
 * Configurable ps-like program.
 * Sorting support routines.
 *
 * Copyright (c) 2010 David I. Bell
 * Permission is granted to use, distribute, or modify this source,
 * provided that this copyright notice remains intact.
 */

#include "ips.h"
#include "expr.h"


#define	MAX_SORT	50	/* maximum items to allow sorting by */
#define	SORT_ALLOC_SIZE	100	/* reallocation size for sorting */


/*
 * Types of values to sort on.
 */
typedef	int	SORT_TYPE;

#define	SORT_NORMAL		1	/* normal sort on column value */
#define	SORT_REVERSE		2	/* reverse sort on column value */
#define	SORT_NORMAL_EXPR	3	/* sort on expression evaluation */
#define	SORT_REVERSE_EXPR	4	/* reverse sort on expression */


/*
 * One item of sorting.
 */
typedef	struct
{
	SORT_TYPE	type;		/* type of sort */
	COLUMN *	column;		/* column to sort by */
	TREE *		tree;		/* expression tree to sort by */
} SORT_ITEM;


/*
 * Data to specify sorting conditions.
 */
static	int		sortCount;		/* number of items in table */
static	SORT_ITEM	sortTable[MAX_SORT];	/* table of sorting items */


/*
 * Data used during the actual sorting.
 */
static	int		procSortSize;		/* entries in sort table */
static	PROC **		procSortTable;		/* proc sorting table */


/*
 * Local procedures.
 */
static	int	SortFunction(const void * e1, const void * e2);
static	int	CompareSortingItems(const PROC * proc1, const PROC * proc2);


/*
 * Get the use flags for all the columns that we sort by.
 * This just means find all references to columns, and OR together
 * the use flags for each column.
 */
USEFLAG
GetSortingUseFlags(void)
{
	const SORT_ITEM *	item;
	USEFLAG			flags;

	flags = USE_NONE;

	for (item = sortTable; item < &sortTable[sortCount]; item++)
	{
		switch (item->type)
		{
			case SORT_NORMAL:
			case SORT_REVERSE:
				flags |= item->column->useFlag;

				break;

			case SORT_NORMAL_EXPR:
			case SORT_REVERSE_EXPR:
				flags |= GetNodeUseFlags(item->tree->root);

				break;

			default:
				break;
		}
	}

	return flags;
}


/*
 * Clear all sorting.
 */
void
ClearSorting(void)
{
	sortCount = 0;
}


/*
 * Append items to do sorting according to the indicated column names.
 * The sorting can be the normal forwards sort, or else a reverse sort.
 * The arguments are column names, no expressions are allowed here.
 */
BOOL
AppendColumnSort(ARGS * ap, BOOL reverse)
{
	SORT_TYPE	type;
	SORT_ITEM *	item;
	const char *	name;
	COLUMN *	column;
	int		count;
	int		i;
	char *		table[MAX_WORDS];

	type = (reverse ? SORT_REVERSE : SORT_NORMAL);

	count = ExpandArguments(ap, table, MAX_WORDS);

	if (count < 0)
		return FALSE;

	for (i = 0; i < count; i++)
	{
		if (sortCount >= MAX_SORT)
		{
			fprintf(stderr, "Too many sort items\n");

			return FALSE;
		}

		name = table[i];

		column = FindColumn(name);

		if (column == NULL)
		{
			fprintf(stderr, "Bad sorting column name %s\n", name);

			return FALSE;
		}

		item = &sortTable[sortCount];

		item->type = type;
		item->column = column;
		item->tree = NULL;

		sortCount++;
	}

	return TRUE;
}


/*
 * Routine to append a sort expression to the sorting list.
 * The sorting can be the normal forwards sort, or else a reverse sort.
 */
BOOL
AppendExpressionSort(ARGS * ap, BOOL reverse)
{
	SORT_TYPE	type;
	SORT_ITEM *	item;
	char *		str;

	type = (reverse ? SORT_REVERSE_EXPR : SORT_NORMAL_EXPR);

	if (ap->count <= 0)
	{
		fprintf(stderr, "Missing sort expression\n");

		return FALSE;
	}

	ap->count--;
	str = *ap->table++;

	if (sortCount >= MAX_SORT)
	{
		fprintf(stderr, "Too many sort items\n");

		return FALSE;
	}

	item = &sortTable[sortCount];

	item->type = type;
	item->column = NULL;
	item->tree = (TREE *) malloc(sizeof(TREE));

	if (item->tree == NULL)
	{
		fprintf(stderr, "Cannot allocate memory\n");

		return FALSE;
	}

	if (!ParseTree(item->tree, str, 0))
		return FALSE;

	sortCount++;

	return TRUE;
}


/*
 * Sort the process list.
 */
void
SortProcesses(void)
{
	int	count;
	PROC *	proc;
	PROC **	procPtr;

	/*
	 * If we need to grow the sorting table to include new processes,
	 * then do so.
	 */
	if (procAllocCount >= procSortSize)
	{
		procSortSize = procAllocCount + SORT_ALLOC_SIZE;

		procSortTable = (PROC **) realloc(procSortTable,
			(sizeof(PROC *) * (procSortSize + 1)));

		if (procSortTable == NULL)
		{
			fprintf(stderr, "Cannot allocate memory\n");
			exit(1);
		}
	}

	/*
	 * Put the process entries into the sort table.
	 */
	count = 0;

	for (proc = processList; proc; proc = proc->next)
		procSortTable[count++] = proc;

	procSortTable[count] = NULL_PROC;

	/*
	 * Sort the entries in the table.
	 */
	qsort((void *) procSortTable, count, sizeof(PROC *), SortFunction);

	/*
	 * Relink the processes into a new list according to the sorted
	 * table pointers.
	 */
	procPtr = procSortTable;

	processList = *procPtr;

	while (*procPtr)
	{
		procPtr[0]->next = procPtr[1];
		procPtr++;
	}
}


/*
 * Function called by qsort to compare two processes for the correct
 * sorting order.  Returns -1 if the first process is first, 1 if the
 * second process is first, or 0 if they are equal.  (But there should
 * be no case where two different processes actually sort as equal.)
 */
static int
SortFunction(const void * e1, const void * e2)
{
	const PROC **	procPtr1;
	const PROC **	procPtr2;
	const PROC *	proc1;
	const PROC *	proc2;
	int		status;

	procPtr1 = (const PROC **) e1;
	procPtr2 = (const PROC **) e2;

	proc1 = *procPtr1;
	proc2 = *procPtr2;

	/*
	 * Check for processes which are not to be shown so as to
	 * avoid any hard work comparing them to sort them.
	 */
	if (!proc1->isShown || !proc2->isShown)
	{
		if (proc1->isShown)
			return -1;

		if (proc2->isShown)
			return 1;

		return 0;
	}

	/*
	 * Do sorting based on any specified sorting items,
	 * which can be column names or arbitrary expressions.
	 */
	status = CompareSortingItems(proc1, proc2);

	if (status != 0)
		return status;

	/*
	 * They appear equal for all sorting items, so do a sort on
	 * their process ids.
	 */
	if (proc1->pid < proc2->pid)
		return -1;

	if (proc1->pid > proc2->pid)
		return 1;

	/*
	 * The process ids match, so sort on their thread ids.
	 * Always put the main thread first.
	 */
	if ((proc1->tid == NO_THREAD_ID) && (proc2->tid != NO_THREAD_ID))
		return -1;

	if ((proc1->tid != NO_THREAD_ID) && (proc2->tid == NO_THREAD_ID))
		return 1;

	if ((proc1->tid == proc1->pid) && (proc2->tid != proc2->pid))
		return -1;

	if ((proc1->tid != proc1->pid) && (proc2->tid == proc2->pid))
		return 1;

	if (proc1->tid < proc2->tid)
		return -1;

	if (proc1->tid > proc2->tid)
		return 1;

	/*
	 * There are multiple processes with the same ids.
	 * Sort on their start times (newer processes first).
	 */
	if (proc1->startTimeTicks > proc2->startTimeTicks)
		return -1;

	if (proc1->startTimeTicks < proc2->startTimeTicks)
		return -1;

	return 0;
}


/*
 * Compare two processes using the defined list of sorting items.
 * The comparison can be on column values or on arbitrary expressions.
 * Returns -1 if the first process is less, 1 if the first process is
 * more, or 0 if they are identical.
 */
static int
CompareSortingItems(const PROC * proc1, const PROC * proc2)
{
	SORT_ITEM *	item;
	TREE *		tree;
	int		status;
	VALUE		value1;
	VALUE		value2;

	if (proc1 == proc2)
		return 0;

	for (item = sortTable; item < &sortTable[sortCount]; item++)
	{
		switch (item->type)
		{
			case SORT_NORMAL:
				status = item->column->sortFunc(proc1, proc2);

				break;

			case SORT_REVERSE:
				status = -item->column->sortFunc(proc1, proc2);

				break;

			case SORT_NORMAL_EXPR:
			case SORT_REVERSE_EXPR:
				tree = item->tree;
				tree->proc = proc1;
				value1 = EvaluateNode(tree, tree->root);

				tree->proc = proc2;
				value2 = EvaluateNode(tree, tree->root);

				if (!CompareValues(value1, value2, &status))
					return 0;

				if (item->type == SORT_REVERSE_EXPR)
					status = -status;

				break;

			default:
				status = 0;
				break;
		}

		if (status != 0)
			return status;
	}

	return 0;
}

/* END CODE */