/************************************************************************* llist.c - Low level linklist.c, containing functions required by screen.c and input.c Programmer - E.J.Pugh, FIAP Copyright - (C) Edward James Pugh, 17-Dec-1989 **************************************************************************/ #include "llist.h" #include /* define useful macros */ #define MALLOC(x) ((x *)malloc(sizeof(x))) /************************************************************************** NewList - Creates a new linked list. Description - Creates a header record for a new linked list. Parameters - NewList() Returns - A pointer of llist_t to the new header record if successful, else NULL. ***************************************************************************/ llist_t *NewList(void) { llist_t *new; /* attempt memory allocation */ if (new = MALLOC(llist_t)) { /* initialize component values */ new->length = 0; new->first = new->last = NULL; } /* return address of new header record */ return (new); } /************************************************************************** NewNode - Creates a new link list node. Description - Creates a new node for linking in a list and assigns initial values as passed. Parameters - NewNode(item, next, prev) LLDATA *item; pointer to record structure. llnode_t *next; pointer to next node. llnode_t *prev; pointer to prev node. Returns - Pointer to new node if successful, else NULL. ***************************************************************************/ llnode_t *NewNode(LLDATA *item, llnode_t *next, llnode_t *prev) { llnode_t *new; /* attempt allocation */ if (new = MALLOC(llnode_t)) { new->item = item; new->next = next; new->prev = prev; } return(new); } /*************************************************************************** AppendItem - Linked List Append. Description - Appends an item to the end of a linked list. Parameters - AppendItem(list, item) llist_t *list; pointer to linked list header structure. LLDATA *item; data pointer. Returns - A llist_t pointer to the list added to else NULL. ***************************************************************************/ llist_t *AppendItem(llist_t *list, LLDATA *item) { llnode_t *new; if(new = NewNode(item, NULL, list->last)) { if(list->length) list->last->next = new; else list->first = new; list->last = new; list->length++; return(list); } return(NULL); } /************************************************************************** DeleteNode - Delete linked list node. Description - Deletes a node from a linked list and frees the space allocated to it. Parameters - DeleteNode(header, node, kill) llist_t *header; header pointer. llnode_t *node ; node pointer. BOOLEAN kill; TRUE to free memory, else FALSE. Returns - A pointer to the last element in the list. ***************************************************************************/ llnode_t *DeleteNode(llist_t *header, llnode_t *node, BOOLEAN kill) { /* is it the first in the list ? */ if(node->prev == NULL) header->first = node->next; else node->prev->next = node->next; /* is it the last in the list ? */ if(node->next == NULL) header->last = node->prev; else node->next->prev = node->prev; if(kill) free(node); header->length--; return(header->last); } /*************************************************************************** MakeCirc - Make Circular Description - Makes a linear list circular. Parameters - MakeCirc(list) llist_t *list; list for conversion. Returns - A llist_t pointer to the list converted, or NULL if the list is empty. ***************************************************************************/ llist_t *MakeCirc(llist_t *list) { if(list->length) { list->first->prev = list->last; list->last->next = list->first; return(list); } return(NULL); } /*************************************************************************** MakeLinear - Make Linear Description - Forces a given list to linear format Parameters - MakeLinear(list) llist_t *list; pointer to list for conversion. Returns - A pointer of llist_t to the list converted, else NULL if the list is empty. ***************************************************************************/ llist_t *MakeLinear(llist_t *list) { if(list->length) { list->first->prev = NULL; list->last->next = NULL; return(list); } return(NULL); } /*************************************************************************** PullStack - Pull Stack Description - Pulls an item from anywhere off of the stack and frees the associated node structure Parameters - PullStack(stack, node) llstack_t *stack; llnode_t *node; Returns - An llnode_t pointer to the top of the stack, NULL if the stack is empty. ***************************************************************************/ llnode_t *PullStack(llstack_t *stack, llnode_t *node) { if(node->next) /* not the top item */ node->next->prev = node->prev; else stack->top = node->prev; if(node->prev) /* not the last item */ node->prev->next = node->next; stack->length --; free(node); return(stack->top); } /*************************************************************************** PopStack - Pop Stack. Description - Pops the top item off the stack. Parameters - PopStack(stack) llstack_t *stack; pointer to stack header. Returns - A LLDATA pointer to the data item popped. ***************************************************************************/ LLDATA *PopStack(llstack_t *stack) { LLDATA *item = NULL; llnode_t *node; if((stack)&&(stack->length)) { node = stack->top; item = stack->top->item; if(node->prev) node->prev->next = NULL; stack->top = node->prev; stack->length--; free(node); } return(item); } /*************************************************************************** PushStack - Push Stack. Description - Pushes an item onto the stack. Parameters - PushStack(stack, item) llstack_t *stack; pointer to stack header. LLDATA *item; pointer to data for pushing. Returns - llnode_t pointer to the new node created, else NULL. ***************************************************************************/ llnode_t *PushStack(llstack_t *stack, LLDATA *item) { llnode_t *new; if(new = NewNode(item, NULL, stack->top)) { if(stack->length) stack->top->next = new; stack->length++; stack->top = new; } return(new); }