/*

 * Motif

 *

 * Copyright (c) 1987-2012, The Open Group. All rights reserved.

 *

 * These libraries and programs are free software; you can

 * redistribute them and/or modify them under the terms of the GNU

 * Lesser General Public License as published by the Free Software

 * Foundation; either version 2 of the License, or (at your option)

 * any later version.

 *

 * These libraries and programs are distributed in the hope that

 * they will be useful, but WITHOUT ANY WARRANTY; without even the

 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR

 * PURPOSE. See the GNU Lesser General Public License for more

 * details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with these librararies and programs; if not, write

 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth

 * Floor, Boston, MA 02110-1301 USA

 * 

 */

#include "xmlist.h"

/************************************************************

 *

 *  Stack code.

 *

 ************************************************************/

#define STACK_INC 25

/************************************************************

 *

 *  Stack Manipulation code.

 *

 ************************************************************/

/*	Function Name: _XmStackInit

 *	Description: Initializes the stack.

 *	Arguments: none

 *	Returns: the stack

 */

XmStack

_XmStackInit()

{

    return((XmStack) XtCalloc(sizeof(XmStackRec), (Cardinal) 1));

}

/*	Function Name: _XmStackFree

 *	Description: Frees all data associated with the stack.

 *	Arguments: stack - the stack

 *	Returns: none

 */

void

_XmStackFree(XmStack stack)

{

    XtFree((XtPointer) stack->elems);

    XtFree((XtPointer) stack);

}

/*	Function Name: _XmStackPush

 *	Description: Pushes an element onto the stack

 *	Arguments: stack - the stack

 *                 elem - element to push onto it.

 *	Returns: none

 */

void

_XmStackPush(XmStack stack, XtPointer elem)

{

    if ((++stack->top) >= stack->alloc) {

	stack->alloc += STACK_INC;

	stack->elems = 

	    (XtPointer *) XtRealloc((XtPointer) stack->elems,

				    sizeof(XtPointer) * stack->alloc);

    }

    stack->elems[stack->top] = elem;

#ifdef STACK_DEBUG

    printf("Pushing %d as elem %d\n", (int) elem, stack->top);    

#endif

}

/*	Function Name: _XmStackPop

 *	Description: Pops an element off of the stack.

 *	Arguments: stack - stack to pop off of.

 *	Returns: elem - the element that has been popped.

 */

XtPointer

_XmStackPop(XmStack stack)

{

    if (stack->top <= 0)

	return(NULL);		/* no elements on the stack. */

#ifdef STACK_DEBUG

    printf("Popping %d from elem %d\n", 

	   (int) stack->elems[stack->top], stack->top);

#endif

    return(stack->elems[(stack->top)--]);

}

/************************************************************

 *

 *  Queue code.

 *

 ************************************************************/

#ifdef QUEUE_DEBUG

#define QUEUE_INC 5

#else

#define QUEUE_INC 25

#endif

/************************************************************

 *

 *  Queue Manipulation code.

 *

 ************************************************************/

/*	Function Name: _XmQueueInit

 *	Description: Initializes the queue.

 *	Arguments: none

 *	Returns: the queue

 */

XmQueue

_XmQueueInit()

{

    return((XmQueue) XtCalloc(sizeof(XmQueueRec), (Cardinal) 1));

}

/*	Function Name: _XmQueueFree

 *	Description: Frees all data associated with the queue.

 *	Arguments: queue - the queue

 *	Returns: none

 */

void

_XmQueueFree(XmQueue queue)

{

    int count;

    _XmQElem *elem = queue->first;

    XmStack stack = _XmStackInit();

    for (count = 0; count < 2; count++) {

	while (elem != NULL) {

	    if (elem->alloced) 

		_XmStackPush(stack, (XtPointer) elem);

	    elem = elem->next;

	}

	elem = queue->free_elems;

    }

    while ((elem = (_XmQElem *) _XmStackPop(stack)) != NULL)

	XtFree((XtPointer) elem);

    _XmStackFree(stack);

    XtFree((XtPointer) queue);

}

/*	Function Name: QueuePush

 *	Description: Pushes an element onto the queue

 *	Arguments: queue - the queue

 *                 data_in - the data to push onto the queue.

 *	Returns: none

 */

/*

 * This is being removed because its name was not changed when compiled

 * -DBX.  This means that there is already a QueuePush() defined in the

 * BX 3.1 bx.o, so integrating the EPak into BX causes multiply defined

 * symbols.  Luckily, this function is not currently used in EPak.  We

 * can remove this only when we don't support EPak integration into

 * BX 3.0 or BX 3.1.

 */

#ifdef notdef

void

QueuePush(XmQueue queue, XtPointer data_in)

{

    _XmQElem *elem = _Xm_GetNewElement(queue);

    _Xm_AddQueue(queue, queue->last, elem);

    if (queue->first == NULL) 

	queue->first = elem;

    queue->last = elem;

    elem->data = data_in;

#ifdef QUEUE_DEBUG

    printf("Pushing %d\n", (int) data_in);

#endif

}

#endif

/*	Function Name: _XmQueuePop

 *	Description: Pops an element off of the queue.

 *	Arguments: queue - queue to pop off of.

 *	Returns: elem - the element that has been popped.

 */

XtPointer

_XmQueuePop(XmQueue queue)

{

    _XmQElem *first = _Xm_RemQueue(&queue->first);

    if (queue->first == NULL)

	queue->last = NULL;

    if (first == NULL)

	return(NULL);

    _Xm_AddQueue(NULL, queue->free_elems, first);

#ifdef QUEUE_DEBUG

    printf("Popping %d\n", (int) first->data);

#endif

    return(first->data);

}

/*	Function Name: _XmQueueCount

 *	Description: Returns the number of items in the queue

 *	Arguments: queue - queue to check.

 *	Returns: number of items in queue.

 */

int

_XmQueueCount(XmQueue queue)

{

    register int i;

    register _XmQElem *elem = queue->first;

    for (i = 0; elem != NULL; i++)

	elem = elem->next;

    return(i);

}

/*	Function Name: _XmQueuePrint

 *	Description: Prints out the real and free nodes of the queue.

 *	Arguments: queue - queue to print.

 *	Returns: none.

 */

#ifdef QUEUE_DEBUG

void

_XmQueuePrint(XmQueue queue)

{

    _XmQElem *elem;

    printf("Elements:\n");

    for (elem = queue->first; elem != NULL; elem = elem->next)

	printf("Element - %d\n", elem->data);

    printf("Reverse Elements:\n");

    for (elem = queue->last; elem != NULL; elem = elem->prev)

	printf("Element - %d\n", elem->data);

    printf("Free Elements:\n");

    for (elem = queue->free_elems; elem != NULL; elem = elem->next)

	printf("Free Element - %d\n", elem->data);

}

#endif

/************************************************************

 *

 *  Internal Used (Utils Lib) functions.

 *

 ************************************************************/

/*	Function Name: _Xm_AddQueue

 *	Description: Adds an element to the queue, after the element specified.

 *	Arguments: queue - Queue to add to, if NULL then we may be adding

 *                         to the free items list.

 *                 after - the element is added after this one.

 *                 elem - element to add.

 *	Returns: none.

 */

void

_Xm_AddQueue(XmQueue queue, _XmQElem *after, _XmQElem *elem)

{

    if (elem != NULL) {

	elem->prev = after;

	if (after == NULL) 

	    /*

	     * If queue is NULL then this is being added to the 

	     * free elements queue, and we make certain assumptions, like

	     * we are always adding to then end of the list, so that

	     * we never will try to add before the first element.

	     */

	    if (queue != NULL) {

		elem->next = queue->first;

		if (elem->next != NULL)

		    elem->next->prev = elem;

	    }

	    else

		elem->next = NULL;

	else

	    elem->next = after->next;

    }

    if (after != NULL) {

	if (after->next != NULL)

	    after->next->prev = elem;

	after->next = elem;

    }

}

/*	Function Name: _Xm_RemQueue

 *	Description: Removes the specified element form a queue, and sets

 *                   the queue to point to the next element.

 *	Arguments: queue - the queue to remove it from.

 *	Returns: the element removed.

 */

_XmQElem *

_Xm_RemQueue(_XmQElem ** queue)

{

    _XmQElem * elem = *queue;

    if (elem != NULL) {

	*queue = elem->next;

	if (elem->next != NULL)

	    elem->next->prev = elem->prev;

	if (elem->prev != NULL)

	    elem->prev->next = elem->next;

    }

    return(elem);

}

/*	Function Name: GetNewElement

 *	Description: Gets an element off the free_elems list, allocates

 *                   more elems if necessary.

 *	Arguments: queue - the queue to get the element from.

 *	Returns: an element.

 */

_XmQElem *

_Xm_GetNewElement(XmQueue queue)

{

    _XmQElem *elem;

    if ((elem = _Xm_RemQueue(&queue->free_elems)) == NULL) {

	register int i;

	/*

	 * We are out of free elements, alloc some more.

	 */

	queue->free_elems = (_XmQElem *) XtCalloc(sizeof(_XmQElem), QUEUE_INC);

	queue->free_elems->alloced = True;

	queue->free_elems->next = elem = queue->free_elems + 1;

	for (i = 1; i < (QUEUE_INC - 1); i++, elem++) {

	    elem->prev = elem - 1;

	    elem->next = elem + 1;

	}

	elem->prev = elem - 1;

	/*

	 * Pop an element off the free elements queue.

	 */

	elem = _Xm_RemQueue(&queue->free_elems);

    }

    return(elem);

}

/************************************************************

 *

 *  List code.

 *

 ************************************************************/

/*

 * This code is very dependant on the queue manipulation code, they

 * are sharing much functionality, several of these functions are just

 * wrappers around the queue maipulation code.

 */

/*	Function Name: _XmListInit

 *	Description: Initializes the list.

 *	Arguments: none

 *	Returns: the queue

 */

XmList

_XmListInit()

{

    return((XmList) _XmQueueInit());

}

/*	Function Name: _XmListFree

 *	Description: Frees all data associated with the list.

 *	Arguments: list - the list

 *	Returns: none

 */

void

_XmListFree(XmList list)

{

    _XmQueueFree((XmQueue) list);

}

/*	Function Name: _XmListAddAfter

 *	Description: Adds an element after the specified element.

 *	Arguments: list - the list

 *                 elem - The element to add this one after.

 *                        If NULL then add this element to the beginning of 

 *                        the list

 *                 data_in - the data to push onto the queue.

 *	Returns: The new added element.

 */

XmListElem *

_XmListAddAfter(XmList list, XmListElem *elem_in, XtPointer data_in)

{

    XmListElem *elem = (XmListElem *) _Xm_GetNewElement((XmQueue) list);

    _Xm_AddQueue((XmQueue) list, elem_in, elem);

    if (elem_in == NULL) 

	list->first = elem;

    if (elem_in == list->last)

	list->last = elem;

    elem->data = data_in;

    return(elem);

}

/*	Function Name: _XmListAddBefore

 *	Description: Adds an element before the specified element.

 *	Arguments: list - the list

 *                 elem - The element to add this one before.

 *                        If NULL then add this element to the end of 

 *                        the list.

 *                 data_in - the data to push onto the queue.

 *	Returns: The new added element.

 */

XmListElem *

_XmListAddBefore(XmList list, XmListElem *elem_in, XtPointer data_in)

{

    XmListElem *after;

    if (elem_in == NULL) 

	after = list->last;

    else

	after = elem_in->prev;

    return(_XmListAddAfter(list, after, data_in));

}

/*	Function Name: _XmListRemove

 *	Description: Removes an element from the list.

 *	Arguments: list - the list to remove the element from.

 *	Returns: none.

 */

void

_XmListRemove(XmList list, XmListElem *elem)

{

    XmListElem *dead = (XmListElem *) _Xm_RemQueue((_XmQElem **) &elem);    

    /*

     * if NULL is passed, then no action is taken.

     */

    if (dead == NULL) 

	return;

    if (list->first == dead)

	if ((list->first = dead->next) == NULL)

	    list->last = NULL;

    if (list->last == dead)

	if ((list->last = dead->prev) == NULL)

	    list->first = NULL;

    _Xm_AddQueue(NULL, list->free_elems, (_XmQElem *) dead);

}

/*	Function Name: _XmListCount

 *	Description: Returns the number of items in the list.

 *	Arguments: list - list to check.

 *	Returns: number of items in list.

 */

int

_XmListCount(XmList list)

{

    return(_XmQueueCount((XmQueue) list));

}

/*	Function Name: _XmListExec

 *	Description: Executes a function on all nodes in the list.

 *	Arguments: list - the list to use.

 *                 start - the element to start with.

 *                 end - the element to end with.

 *                 exec_func - the function to execute.

 *                 data - data to pass to the function.

 *	Returns: NULL is returned if all items from start to end 

 *               have been operated on.  Otherwise the node in which

 *               the operation stopped is returned.

 *

 * NOTES: If start is NULL the start is the first element in the list.

 *        If end is NULL then all elements after start will be searched.

 *        The list is always executed if forward order from start -> 

 *        	start->next, start->next->next...

 *        

 */

XmListElem *

_XmListExec(XmList list, XmListElem *start, XmListElem *end, 

	 XmListFunc func, XtPointer data)

{

    if (start == NULL)

	start = list->first;

    for ( ; (start != end) && (start != NULL); start = start->next) {

	if (!(*func)(start, data))

	    return(start);

    }

    return(NULL);

}

/*	Function Name: _XmListPrint

 *	Description: Prints out the real and free nodes of the list.

 *	Arguments: list - list to print.

 *	Returns: none.

 */

#ifdef QUEUE_DEBUG

void

_XmListPrint(XmList list)

{

    _XmQueuePrint((XmQueue) list);

}

#endif