/*-------------------------------------------------------------------------
 *
 * list.c
 *	  implementation for PostgreSQL generic linked list package
 *
 *
 * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql-server/src/backend/nodes/list.c,v 1.55 2003/11/29 19:51:49 pgsql Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "nodes/pg_list.h"

/*
 * Return a freshly allocated List. Since empty non-NIL lists are
 * invalid, new_list() also allocates the head cell of the new list:
 * the caller should be sure to fill in that cell's data.
 */
static List *
new_list(NodeTag type)
{
	List		*new_list;
	ListCell	*new_head;

	new_head = palloc(sizeof(*new_head));
	new_head->next = NULL;

	new_list = palloc(sizeof(*new_list));
	new_list->type = type;
	new_list->length = 1;
	new_list->head = new_head;
	new_list->tail = new_head;

	return new_list;
}

/*
 * Allocate a new cell and make it the head of the specified list. The
 * data in the new head cell is undefined; the caller should be sure
 * to fill it in
 */
static void
new_head_cell(List *list)
{
	ListCell *new_head;

	new_head = palloc(sizeof(*new_head));
	new_head->next = list->head;

	list->head = new_head;
	list->length++;
}

/*
 * Allocate a new cell and make it the tail of the specified list. The
 * data in the new tail cell is undefined; the caller should be sure
 * to fill it in
 */
static void
new_tail_cell(List *list)
{
	ListCell *new_tail;

	new_tail = palloc(sizeof(*new_tail));
	new_tail->next = NULL;

	list->tail->next = new_tail;
	list->tail = new_tail;
	list->length++;
}

/*
 * Append a pointer to the list. A pointer to the modified list is
 * returned. Note that this function may or may not destructively
 * modify the list; callers should always use this function's return
 * value, rather than continuing to use the pointer passed as the
 * first argument.
 */
List *
list_append(List *list, void *datum)
{
	if (list == NIL)
		list = new_list(T_List);
	else
		new_tail_cell(list);

	cell_value(list_tail(list)) = datum;
	return list;
}

/*
 * Append an integer to the specified list. See list_append()
 */
List * 
list_append_int(List *list, int datum)
{
	if (list == NIL)
		list = new_list(T_IntList);
	else
		new_tail_cell(list);

	cell_value_int(list_tail(list)) = datum;
	return list;
}

/*
 * Append an OID to the specified list. See list_append()
 */
List * 
list_append_oid(List *list, Oid datum)
{
	if (list == NIL)
		list = new_list(T_OidList);
	else
		new_tail_cell(list);

	cell_value_oid(list_tail(list)) = datum;
	return list;
}

/*
 * Private convenience routine: allocate a new tail cell and place the
 * data from the specified cell into it. The data is copied via a
 * shallow copy, not a deep copy.
 */
static List *
list_append_auto(List *list, ListCell *cell)
{
	/* XXX: broken if list == NIL */
	switch (list->type)
	{
		case T_List:
			return list_append(list, cell_value(cell));
		case T_IntList:
			return list_append_int(list, cell_value_int(cell));
		case T_OidList:
			return list_append_oid(list, cell_value_oid(cell));
		default:
		{
			/* Keep the compiler quiet; never reached */
			Assert(false);
			return NIL;
		}
	}
}

/*
 * Prepend a pointer to the list. A pointer to the modified list is
 * returned. Note that this function may or may not destructively
 * modify the list; callers should always use this function's return
 * value, rather than continuing to use the pointer passed as the
 * first argument.
 */
List *
list_prepend(List *list, void *datum)
{
	if (list == NIL)
		list = new_list(T_List);
	else
		new_head_cell(list);

	cell_value(list_head(list)) = datum;
	return list;
}

/*
 * Prepend an integer to the list. See list_prepend()
 */
List * 
list_prepend_int(List *list, int datum)
{
	if (list == NIL)
		list = new_list(T_IntList);
	else
		new_head_cell(list);

	cell_value_int(list_head(list)) = datum;
	return list;
}

/*
 * Prepend an OID to the list. See list_prepend()
 */
List * 
list_prepend_oid(List *list, Oid datum)
{
	if (list == NIL)
		list = new_list(T_OidList);
	else
		new_head_cell(list);

	cell_value_oid(list_head(list)) = datum;
	return list;
}

/*
 * Concatenate list2 to the end of list1, and return list1. list1 is
 * destructively changed. Callers should be sure to use the return
 * value as the new pointer to the concatenated list: the 'list1'
 * input pointer may or may not be the same as the returned pointer.
 *
 * The nodes in list2 are merely appended to the end of list1 in-place
 * (i.e. they aren't copied). So freeing list2 will also invalidate a
 * portion of list1.
 */
List *
list_conc(List *list1, List *list2)
{
	if (list1 == NIL)
		return list2;
	if (list2 == NIL)
		return list1;
	if (list1 == list2)
		elog(ERROR, "cannot list_conc() a list to itself");

	list1->length += list2->length;
	list1->tail->next = list2->head;
	list1->tail = list2->tail;

	return list1;
}

void *
list_nth(List *list, int n)
{
	ListCell *match;

	Assert(list != NIL);
	Assert(n >= 0);
	Assert(n <= (list->length - 1));
	Assert(list->type == T_List);

	/* Does the caller actually mean to fetch the tail? */
	if (n == list->length - 1)
		return cell_value(list_tail(list));

	for (match = list->head; n-- > 0; match = match->next)
		;

	return cell_value(match);
}

List *
list_truncate(List *list, int new_size)
{
	ListCell	*cell;
	int			 n;

	if (new_size <= 0)
		return NIL;		/* truncate to zero length */

	/* If asked to effectively extend the list, do nothing */
	if (new_size >= list->length)
		return list;

	n = 0;
	foreach (cell, list)
	{
		n++;
		if (n == new_size)
		{
			cell->next = NULL;
			list->tail = cell;
			list->length = new_size;
			return list;
		}
	}

	/* keep the compiler quiet; never reached */
	Assert(false);
	return list;
}

/*
 * Return true iff 'datum' is a member of the list. Equality is
 * determined by using equal(), so callers should ensure that they
 * pass a Node as 'datum'
 */
bool
list_member(List *list, void *datum)
{
	ListCell *cell;

	foreach (cell, list)
	{
		if (equal(cell_value(cell), datum))
			return true;
	}

	return false;
}

/*
 * Return true iff 'datum' is a member of the list. Equality is
 * determined by using simple pointer comparison.
 */
bool
list_member_simple(List *list, void *datum)
{
	ListCell *cell;

	Assert(list == NIL || IsA(list, List));

	foreach (cell, list)
	{
		if (cell_value(cell) == datum)
			return true;
	}

	return false;
}

/*
 * Return true iff the integer 'datum' is a member of the list.
 */
bool
list_member_int(List *list, int datum)
{
	ListCell *cell;

	Assert(list == NIL || IsA(list, OidList));

	foreach (cell, list)
	{
		if (cell_value_int(cell) == datum)
			return true;
	}

	return false;
}

/*
 * Return true iff the OID 'datum' is a member of the list.
 */
bool
list_member_oid(List *list, Oid datum)
{
	ListCell *cell;

	Assert(list == NIL || IsA(list, IntList));

	foreach (cell, list)
	{
		if (cell_value_oid(cell) == datum)
			return true;
	}

	return false;
}

/*
 * Private convenience routine: return true iff 'cell' is a member of
 * 'list', using the comparison rules specified by 'simple'.
 */
static bool
list_member_auto(List *list, ListCell *cell, bool simple)
{
	/* A zero-cell list can't have any members */
	if (list == NIL)
		return false;

	switch (list->type)
	{
		case T_List:
		{
			if (simple)
				return list_member_simple(list, cell_value(cell));
			else
				return list_member(list, cell_value(cell));
		}
		case T_IntList:
			return list_member_int(list, cell_value_int(cell));
		case T_OidList:
			return list_member_oid(list, cell_value_oid(cell));
		default:
		{
			/* Keep the compiler quiet; never reached */
			Assert(false);
			return false;
		}
	}
}

/*
 * Remove 'cell' from 'list'; 'prev' is the previous element to 'cell'
 * in 'list', if any (i.e. prev == NULL iff list->head == cell)
 */
static List *
remove_list_cell(List *list, ListCell *cell, ListCell *prev)
{
	list->length--;
	/*
	 * If we just removed the last node from the last, free it and
	 * return 'NIL', which is the only valid representation of a
	 * zero-length list.
	 */
	if (list->length == 0)
	{
		list_free(list);
		return NIL;
	}

	/*
	 * Otherwise, adjust the necessary list links, deallocate the
	 * particular node we've removed, and return the list we were
	 * given.
	 */
	if (prev)
		prev->next = cell->next;

	if (list->head == cell)
		list->head = cell->next;

	if (list->tail == cell)
		list->tail = prev;

	pfree(cell);
	return list;
}

List *
list_remove(List *list, void *datum)
{
	ListCell	*cell;
	ListCell	*prev;

	prev = NULL;
	foreach (cell, list)
	{
		if (equal(cell_value(cell), datum))
			return remove_list_cell(list, cell, prev);

		prev = cell;
	}

	/* Didn't find a match: return the list unmodified */
	return list;
}

List *
list_remove_simple(List *list, void *datum)
{
	ListCell	*cell;
	ListCell	*prev;

	prev = NULL;
	foreach (cell, list)
	{
		if (cell_value(cell) == datum)
			return remove_list_cell(list, cell, prev);

		prev = cell;
	}

	/* Didn't find a match: return the list unmodified */
	return list;
}

List *
list_remove_int(List *list, int datum)
{
	ListCell	*cell;
	ListCell	*prev;

	prev = NULL;
	foreach (cell, list)
	{
		if (cell_value_int(cell) == datum)
			return remove_list_cell(list, cell, prev);

		prev = cell;
	}

	/* Didn't find a match: return the list unmodified */
	return list;
}

List *
list_remove_oid(List *list, Oid datum)
{
	ListCell	*cell;
	ListCell	*prev;

	prev = NULL;
	foreach (cell, list)
	{
		if (cell_value_oid(cell) == datum)
			return remove_list_cell(list, cell, prev);

		prev = cell;
	}

	/* Didn't find a match: return the list unmodified */
	return list;
}

/*
 * Returns true iff c1 and c2 are equal ListCells, according to the
 * rules specified by 'simple'
 */
#define CELL_NOT_EQUAL(c1, c2, simple)			\
	(simple)									\
		? (cell_value(c1) != cell_value(c2))	\
		: (!equal(cell_value(c1), cell_value(c2)))

/*
 * Returns true iff list1 is equal to list2. Lists are equal if they
 * have the same length, the same type, and all their nodes are cell.
 *
 * If 'simple' is true, cell equality is determined by
 * pointer-equality comparison. Otherwise, equal() is used.
 */
bool
list_equal_private(List *list1, List *list2, bool simple)
{
	ListCell *c1;
	ListCell *c2;

	/*
	 * Return quickly for obviously nonequivalent lists
	 */
	if (list_length(list1) != list_length(list2))
		return false;
	if (list1->type != list2->type)
		return false;

	c1 = list_head(list1);
	c2 = list_head(list2);
	while (c1 != NULL || c2 != NULL)
	{
		if (CELL_NOT_EQUAL(c1, c2, simple))
			return false;

		c1 = cell_next(c1);
		c2 = cell_next(c2);
	}

	/*
	 * The lists are the same length, so we can't run out of one
	 * before the other
	 */
	Assert(c1 == NULL && c2 == NULL);
	return true;
}

/*
 * Generate the union of two lists. This is calculated by copying
 * list1 via list_copy(), then adding to it all the members of list2
 * that aren't already in list1.
 *
 * If 'simple' is true, duplicates are determined via simple pointer
 * equality. Otherwise, duplicates are determined via equal().
 *
 * Returns a new List, whose cells are the same as the appropriate
 * cells from list1 and list2 (i.e. the cells aren't copied)
 *
 * NB: Strangely, this function will NOT remove any duplicates that
 * are present in list1. Also, this function could probably be
 * implemented a lot faster if it were a performance bottleneck.
 */
List *
list_set_union_private(List *list1, List *list2, bool simple)
{
	List		*new_list;
	ListCell	*cell;

	new_list = list_copy(list1);
	foreach (cell, list2)
	{
		if (!list_member_auto(new_list, cell, simple))
			list_append_auto(new_list, cell);
	}

	return new_list;
}

/*
 * Return a freshly-allocated List that contains all the cells in
 * list1 that are not in list2. The list is freshly allocated via
 * palloc(), but the cells themselves point to the same objects as the
 * nodes from the input lists.
 *
 * If 'simple' is true, we determine duplicates in list2 via simple
 * pointer-equality comparisons. Otherwise, equal() is used.
 */
List *
list_set_difference_private(List *list1, List *list2, bool simple)
{
	ListCell	*cell;
	List		*new_list = NIL;

	if (list2 == NIL)
		return list_copy(list1);

	foreach (cell, list1)
	{
		if (!list_member_auto(list2, cell, simple))
			new_list = list_append_auto(new_list, cell);
	}

	return new_list;
}

/*
 * Free all the cells of the list, as well as the list itself. Any
 * objects that are pointed-to by the cells of the list are not freed.
 */
void
list_free(List *list)
{
	ListCell	*cell;

	cell = list_head(list);
	while (cell != NULL)
	{
		ListCell *tmp = cell;
		cell = cell_next(cell);
		pfree(tmp);
	}

	if (list)
		pfree(list);
}

/*
 * Return a copy the specified list. If 'deep' is true, objects
 * pointed-to by list cells are also copied via
 * copyObject(). Otherwise, pointed-to objects are not copied. The
 * storage for the new List is allocated via palloc().
 */
List *
list_copy_private(List *list, bool deep)
{
	List		*newlist;
	ListCell	*cell;
	ListCell	*prev;

	if (list == NIL)
		return NIL;

	/*
	 * For lists of integers and OIDs, shallow copy and deep copy are
	 * equivalent, so force the former because copyObject() can't
	 * handle integers or Oids
	 */
	if (IsA(list, IntList) || IsA(list, OidList))
		deep = false;

	newlist = new_list(list->type);
	newlist->length = list->length;

	/*
	 * Copy the head cell: new_node() has already allocated it
	 */
	if (deep)
		cell_value(list_head(newlist)) = copyObject(cell_value(list_head(list)));
	else
		newlist->head->data = list->head->data;

	prev = list_head(newlist);
	foreach (cell, list)
	{
		ListCell *newcell;

		newcell = palloc(sizeof(*newcell));

		if (deep)
			cell_value(newcell) = copyObject(cell_value(cell));
		else
			newcell->data = cell->data;

		prev->next = newcell;
		prev = newcell;
	}
	prev->next = NULL;
	newlist->tail = prev;

	return newlist;
}