/*
 * Copyright (c) 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.
 *
 * $Id: t-ringinsert.h,v 1.1 2004/09/10 18:53:13 ca Exp $
 */

/*
needs:
RING_CMP(el1, el2) function/macro to compare two ring elements
*/

/*
**  RING_INSERT -- insert new elem into ring
**
**	Parameters:
**		elem -- previous element (may be NULL)
**		new -- element to insert
**
**	Returns:
**		usual sm_error code
**
**	Invariant:
**	if not all elements in the ring are the same then there is
**	exactly one element F for which: L=pred(F) > F ("First"/"Head"),
**	(and succ(L)=F: L: Last, F: First)
**	for all others E: pred <= E.
**	for each element E:
**	if E isn't the first nor the last: pred(E) <= E <= succ(E)
**	if E is the first: pred(E) >= E <= succ(E)
**	if E is the last: pred(E) <= E >= succ(E)
**
**	Problem: there's no explicit head (or tail) of the "list"
**	because it is a ring: X -> B -> D -> E -> X
**	hence the code must be prepared to "walk" in any direction
**	and stop when it reaches "First"/"Last", or when it comes
**	back to the start.
*/

static sm_ret_T
ring_insert(sm_ring_P elem, sm_ring_P new)
{
	int direction;
	sm_ring_P nxt, cur;

	if (elem == NULL)
	{
		SM_RING_INIT(new);
		return SM_SUCCESS;
	}

	nxt = cur = elem;
	direction = RING_CMP(new, nxt);
	if (direction == 0)
	{
		SM_RING_APPEND(elem, new);
		return SM_SUCCESS;
	}
	else if (direction < 0)
	{
		/*
		**  initial: new < nxt
		**  go to the "left" (pred)
		**  stop if new >= nxt (can't be on first round)
		**	found place to insert (append to nxt)
		**  stop if nxt > cur (L > F)
		**	this means new is less than every element in the ring
		**	and nxt is the largest element, hence new must be
		**	appended to nxt
		**  stop if elem is reached:
		**	this means new is less than every element in the ring
		**	and elem is the largest element, hence new must be
		**	appended to elem (= nxt)
		*/

		while ((nxt = sm_ring_pred(nxt)) != elem &&
			!(RING_CMP(new, nxt) >= 0 || RING_CMP(nxt, cur) > 0))
		{
			cur = nxt;
		}
		SM_RING_APPEND(nxt, new);
	}
	else
	{
		/*
		**  initial: new > nxt
		**  go to the "right" (succ)
		**  stop if new <= nxt (can't be on first round)
		**	found place to insert (prepend to nxt)
		**  stop if nxt < cur (F > L)
		**	this means new is greater than every element in the ring
		**	and next is the smallest element, hence new must be
		**	prepended to nxt
		**  stop if elem is reached:
		**	this means new is greater than every element in the ring
		**	and elem is the smallest element, hence new must be
		**	prepended to elem (= nxt)
		*/

		while ((nxt = sm_ring_succ(nxt)) != elem &&
			!(RING_CMP(new, nxt) <= 0 || RING_CMP(nxt, cur) < 0))
		{
			cur = nxt;
		}
		SM_RING_PREPEND(nxt, new);
	}
	return SM_SUCCESS;
}