/*
* list.c
* A package for managing doubly-linked lists.
*/
#include "list.h"
#include <stdlib.h>
/* Prototypes of
static functions: */
static void
list_delete_element (List *p_list, Element *p_elem);
/*
------------------------------------------------------------------------
* Function: list_init
*/
List *list_init ()
{
List
*p_list;
/* Allocate a new List object. */
p_list = (List *) malloc (sizeof(List));
/* Set its fields
to indicate and empty list. */
p_list->p_head = NULL;
p_list->p_tail = NULL;
p_list->size = 0;
return
(p_list);
}
/*
------------------------------------------------------------------------
* Function: list_prepend
*/
void list_prepend (List *p_list,
double x)
{
Element *p_elem;
/* Sanity check: */
if
(p_list == NULL)
exit(-1);
/* Allocate a new Element object and set its fields. */
p_elem = (Element *) malloc (sizeof(Element));
p_elem->value = x;
p_elem->p_prev = NULL;
p_elem->p_next = NULL;
/* Set the element
as the new list head. */
if
(p_list->p_head != NULL)
{
/* The new element should be placed before the current list
head. */
p_list->p_head->p_prev = p_elem;
p_elem->p_next = p_list->p_head;
/* Set the new
element as the new list head. */
p_list->p_head = p_elem;
}
else
{
/* The list is empty - the new element should be both its head
and
its tail. */
p_list->p_head = p_elem;
p_list->p_tail = p_elem;
}
/* Increment the
list size. */
p_list->size++;
return;
}
/*
------------------------------------------------------------------------
* Function: list_append
*/
void list_append (List *p_list, double x)
{
Element *p_elem;
/* Sanity check: */
if
(p_list == NULL)
exit(-1);
/* Allocate a new Element object and set its fields. */
p_elem = (Element *) malloc (sizeof(Element));
p_elem->value = x;
p_elem->p_prev = NULL;
p_elem->p_next = NULL;
/* Set the element
as the new list tail. */
if
(p_list->p_tail != NULL)
{
/* The new element should be placed after the current list
tail. */
p_list->p_tail->p_next = p_elem;
p_elem->p_prev = p_list->p_tail;
/* Set the new
element as the new list tail. */
p_list->p_tail = p_elem;
}
else
{
/* The list is empty - the new element should be both its head
and
its tail. */
p_list->p_head = p_elem;
p_list->p_tail = p_elem;
}
/* Increment the
list size. */
p_list->size++;
return;
}
/*
------------------------------------------------------------------------
* Function: list_find
*/
const Element *list_find (const List *p_list, double
x)
{
Element *p_elem;
/* Sanity check: */
if
(p_list == NULL)
exit(-1);
/* Go over the
list. */
p_elem = p_list->p_head;
while
(p_elem != NULL)
{
/* Check if the
current element contains the requested value. */
if
(p_elem->value == x)
return (p_elem);
/* Proceed to the next element. */
p_elem = p_elem->p_next;
}
/* If we reached
here, the value is not found in the list. */
return
(NULL);
}
/*
------------------------------------------------------------------------
* Function: list_delete
*/
int list_delete (List *p_list, double x)
{
Element *p_elem;
/* Sanity check: */
if
(p_list == NULL)
exit(-1);
/* Find the element
containing x in the list. */
p_elem = (Element *) list_find (p_list, x);
if
(p_elem == NULL)
/* The value x is not found in the list: */
return
(0);
/* Delete p_elem
from the list. */
list_delete_element (p_list, p_elem);
return
(1);
}
/*
------------------------------------------------------------------------
* Function: list_pop_first
*/
double list_pop_first (List
*p_list)
{
double x;
/* Sanity checks:
*/
if
(p_list == NULL || p_list->size == 0)
exit(-1);
/* Keep the value
of the list head. */
x = p_list->p_head->value;
/* Delete the list
head, and return the value it stored. */
list_delete_element (p_list,
p_list->p_head);
return
(x);
}
/*
------------------------------------------------------------------------
* Function: list_pop_last
*/
double list_pop_last (List
*p_list)
{
double x;
/* Sanity checks:
*/
if
(p_list == NULL || p_list->size == 0)
exit(-1);
/* Keep the value
of the list tail. */
x = p_list->p_tail->value;
/* Delete the list
tail, and return the value it stored. */
list_delete_element (p_list,
p_list->p_tail);
return
(x);
}
/* ------------------------------------------------------------------------
* Function: list_reset
*/
void list_reset (List *p_list)
{
Element *p_elem;
/* Sanity check: */
if
(p_list == NULL)
exit(-1);
while
(p_list->p_head != NULL)
{
/* Keep track of
the current list head. */
p_elem = p_list->p_head;
/* Make the
second element the new list head. */
p_list->p_head =
p_list->p_head->p_next;
/* Free memory. */
free (p_elem);
}
/* Reset the rest
of the fields. */
p_list->p_tail = NULL;
p_list->size = 0;
return;
}
/*
------------------------------------------------------------------------
* Function: list_delete_element
* Purpose:
Delete the given element from the list.
* Input:
p_list - The list.
* p_elem - The element to be deleted.
* Returns:
Nothing.
*/
static void
list_delete_element (List *p_list, Element *p_elem)
{
/* Link the
previous element and the next element of p_elem so none of
them will keep
pointing to p_elem. */
if
(p_elem->p_prev != NULL)
{
/* Make the
previous element point to the next element (skip p_elem). */
p_elem->p_prev->p_next =
p_elem->p_next;
}
else
{
/* p_elem is the
current list head - assign the next element as the
new head. */
p_list->p_head = p_elem->p_next;
}
if
(p_elem->p_next != NULL)
{
/* Make the
previous element point to the next element (skip p_elem). */
p_elem->p_next->p_prev =
p_elem->p_prev;
}
else
{
/* p_elem is the
current list tail - assign the previous element as the
new tail. */
p_list->p_tail = p_elem->p_prev;
}
/* Free p_elem itself. */
free (p_elem);
/* Update the list
size. */
p_list->size--;
return;
}