/*
* 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