/* file: list.c
 *
 * The implementation of a basic double-linked list
 */

#include <stdlib.h>

#include "list.h"

typedef struct BBGCell       CELL;

/* local procedures */
void  FreeCell        ( CELL *pCell, LIST *pList );
CELL *AllocCell       ( void );
void  InvalidateCell  ( CELL *pCell );

/* hidden structs */
struct BBGList
{
  CELL  *_pFirstCell;
  CELL  *_pLastCell;
  int    _iterators;
  int    _size;
  int    _valid;
};

struct BBGCell
{
  CELL  *_pNextCell;
  CELL  *_pPrevCell;
  void  *_pContent;
  int    _valid;
};

struct BBGIterator
{
  LIST  *_pList;
  CELL  *_pCell;
};

/* Function: AllocList
 *
 * Parameters: none
 * Returns: *LIST
 *
 * Allocates one empty linked list and returns a pointer to it.
 */
LIST *AllocList()
{
  LIST *pList;

  pList = malloc(sizeof(*pList));
  pList->_pFirstCell = NULL;
  pList->_pLastCell = NULL;
  pList->_iterators = 0;
  pList->_valid = 1;
  pList->_size = 0;

  return pList;
}
/* Function: AllocIterator
 *
 * Parameters: *LIST
 * Returns: *ITERATOR
 *
 * Creates an iterator for a given list, and returns a pointer to it.
 */
ITERATOR *AllocIterator(LIST *pList)
{
  ITERATOR *pIter;

  pIter = malloc(sizeof(*pIter));
  pIter->_pList = pList;

  if (pList != NULL)
  {
    pList->_iterators++;
    pIter->_pCell = pList->_pFirstCell;
  }
  else
    pIter->_pCell = NULL;

  return pIter;
}

CELL *AllocCell()
{
  CELL *pCell;

  pCell = malloc(sizeof(*pCell));
  pCell->_pNextCell = NULL;
  pCell->_pPrevCell = NULL;
  pCell->_pContent = NULL;
  pCell->_valid = 1;

  return pCell;
}
/* Function: AttachToList
 *
 * Parameters: *void, *LIST
 * Returns: nothing
 *
 * Will allocate memory for a cell, and let the cell point
 * to the location of the content given. The cell is then
 * attached to the beginning of the list.
 *
 * NOTICE: If the given content is already located in the
 * list, it will NOT be added.
 */
void AttachToList(void *pContent, LIST *pList)
{
  CELL *pCell;
  int found = 0;

  for (pCell = pList->_pFirstCell; pCell != NULL; pCell = pCell->_pNextCell)
  {
    if (!pCell->_valid)
      continue;

    if (pCell->_pContent == pContent)
    {
      found = 1;
      break;
    }
  }

  /* do not attach to list if already here */
  if (found)
    return;

  pCell = AllocCell();
  pCell->_pContent = pContent;
  pCell->_pNextCell = pList->_pFirstCell;

  if (pList->_pFirstCell != NULL)
    pList->_pFirstCell->_pPrevCell = pCell;
  if (pList->_pLastCell == NULL)
    pList->_pLastCell = pCell;

  pList->_pFirstCell = pCell;

  pList->_size++;
}
/* Function: DetachFromList
 *
 * Parameters: *void, *LIST
 * Returns: void
 *
 * Scans the list and removes the cell with the given content.
 * The cell is free'd from memory. The content of the cell is
 * not free'd.
 */
void DetachFromList(void *pContent, LIST *pList)
{
  CELL *pCell;

  for (pCell = pList->_pFirstCell; pCell != NULL; pCell = pCell->_pNextCell)
  {
    if (pCell->_pContent == pContent)
    {
      InvalidateCell(pCell);
      pList->_size--;
      return;
    }
  }
}
/* Function: FreeIterator
 *
 * Parameters: *ITERATOR
 * Returns: nothing
 *
 * Destroys the iterator.
 */
void FreeIterator(ITERATOR *pIter)
{
  LIST *pList = pIter->_pList;

  if (pList != NULL)
  {
    pList->_iterators--;

    /* if this is the only iterator, free all invalid cells */
    if (pList->_iterators <= 0)
    {
      CELL *pCell, *pNextCell;

      for (pCell = pList->_pFirstCell; pCell != NULL; pCell = pNextCell)
      {
        pNextCell = pCell->_pNextCell;

        if (!pCell->_valid)
          FreeCell(pCell, pList);
      }

      if (!pList->_valid)
        FreeList(pList);
    }
  }

  free(pIter);
}
/* Function: FreeList
 *
 * Parameters: *LIST
 * Returns: nothing
 *
 * Destroys all cells in the list and finally the list.
 */
void FreeList(LIST *pList)
{
  CELL *pCell, *pNextCell;

  /* if we have any unfinished iterators, wait for later */
  if (pList->_iterators > 0)
  {
    pList->_valid = 0;
    return;
  }

  for (pCell = pList->_pFirstCell; pCell != NULL; pCell = pNextCell)
  {
    pNextCell = pCell->_pNextCell;

    FreeCell(pCell, pList);
  }

  free(pList);
}

void FreeCell(CELL *pCell, LIST *pList)
{
  if (pList->_pFirstCell == pCell)
    pList->_pFirstCell = pCell->_pNextCell;

  if (pList->_pLastCell == pCell)
    pList->_pLastCell = pCell->_pPrevCell;

  if (pCell->_pPrevCell != NULL)
    pCell->_pPrevCell->_pNextCell = pCell->_pNextCell;

  if (pCell->_pNextCell != NULL) 
    pCell->_pNextCell->_pPrevCell = pCell->_pPrevCell;

  free(pCell);
}

void InvalidateCell(CELL *pCell)
{
  pCell->_valid = 0;
}
/* Function: NextInList
 *
 * Arguments: *ITERATOR
 * Returns: *void
 *
 * Returns the content of the cell that the iterator is
 * currently pointing to, and moves the iterator to the next
 * cell in the list.
 *
 * Will return NULL if there are no more cells in the list.
 */
void *NextInList(ITERATOR *pIter)
{
  void *pContent = NULL;

  /* skip invalid cells */
  while (pIter->_pCell != NULL && !pIter->_pCell->_valid)
  {
    pIter->_pCell = pIter->_pCell->_pNextCell;
  }

  if (pIter->_pCell != NULL)
  {
    pContent = pIter->_pCell->_pContent;
    pIter->_pCell = pIter->_pCell->_pNextCell;
  }

  return pContent;
}
/* Function: SizeOfList
 *
 * Paramters: *LIST
 * Returns: int
 *
 * Returns the amount of cells in the list
 */
int SizeOfList(LIST *pList)
{
  return pList->_size;
}