simple_list.c

Path MPICH-V for MPICH the MPI Implementation

/** @file simple_list.c implements the list functions */
#include "config.h"
#include <stdlib.h>
#include "debug.h"
#include "simple_list.h"



void * ll_remove_head( LinkedList_t* pll )
{
  sElement_t* pElem = pll->head;
  void * data;

  if( pElem == NULL )
    {
      ASSERT( pll->tail == NULL );
      ASSERT( pll->size == 0 );
      return NULL;
    }
  if( pll->head == pll->tail )
    {
      pll->head =NULL;
      pll->tail = NULL;
      pll->size--;
      data = (pElem->data);
      free(pElem);
      return data;
    }

  pll->head = pElem->pNext;
  pll->size--;
  data = (pElem->data);
  free(pElem);
  return data;
}



void* ll_remove( LinkedList_t* pll, void* data )
{
  sElement_t *pElem, *pLast;
  void* pData = NULL;

  if( pll->head == NULL ) return NULL;
  if( data == pll->head->data )
    {
      pData = ll_remove_head( pll );
      return pData;
    }

  pLast = pll->head;
  pElem = pLast->pNext;
  while( (pElem != NULL) && (pElem->data != data) )
    {
      pLast = pElem;
      pElem = pElem->pNext;
    }
  if( pElem != NULL )
    {
      ASSERT( pElem->data == data );
      pLast->pNext = pElem->pNext;
      pData = pElem->data;

      if( pElem->pNext == NULL )
	pll->tail = pLast; /* remove the tail */
      pll->size--;
      free(pElem);
    }
  return pData;
}

void *ll_remove_by_key( LinkedList_t* pll,  int (*fct)(void*, void *), void *param)
{
  sElement_t *pElem, *pLast;
  void *pData = NULL;

  if( pll->head == NULL)
    return NULL;
  if( fct(pll->head->data, param) )
    {
      pData = ll_remove_head(pll);
      return pData;
    }
  pLast = pll->head;
  for(pElem = pll->head->pNext; pElem; pElem = pElem->pNext )
    {
      if( fct(pElem->data, param) )
	{
          pLast->pNext = pElem->pNext;
          pData = pElem->data;
	  if( pElem->pNext == NULL )
	    pll->tail = pLast;

	  pll->size--;
	  free(pElem);
	  break;
	}
      pLast = pElem;
    }
  return pData;
}


void* ll_add_head( LinkedList_t* pll, void* data )
{
  sElement_t* pElem;

  pElem = malloc(sizeof(sElement_t));
  pElem->data = data;

  if( pll->head == NULL )
    {
      ASSERT( pll->tail == NULL );
      pll->head = pElem;
      pll->tail = pElem;
      pElem->pNext = NULL;
    }
  else
    {
      pElem->pNext = pll->head;
      pll->head = pElem;
    }
  pll->size++;
  return data;
}


void* ll_add_tail( LinkedList_t* pll, void* data )
{
    sElement_t* pElem;
    pElem = malloc(sizeof(sElement_t));
    pElem->data = data;

    pElem->pNext = NULL;
    if( pll->tail == NULL )
      {
	ASSERT( pll->head == NULL );
	pll->head = pElem;
      }
    else
      {
	pll->tail->pNext = pElem;
      }
    pll->tail = pElem;
    pll->size++;
    return data;
}


void *ll_find_by_key( LinkedList_t* pll,  int (*fct)(void*, void *), void *param)
{
    sElement_t *pElem;
    void *pData = NULL;

    if( pll->head == NULL)
      return NULL;
    for(pElem = pll->head; pElem; pElem = pElem->pNext )
      {
	if( fct(pElem->data, param) )
	  {
	    pData = pElem->data;
	    break;
	  }
      }
    return pData;
}

void ll_dump( LinkedList_t* pll, void (*fct)(void*) )
{
  sElement_t* pElem;

  printi( "ll", "Linked list %p dump", pll );
  pElem = pll->head;
  while( pElem != NULL )
    {
    if( fct == NULL )
      printi( "ll", "<%p>", pElem->data);
    else
      fct( pElem->data );
    pElem = pElem->pNext;
  }
}

LinkedList_t* ll_create( LinkedList_t* pList )
{
    if( pList == NULL )
      pList = (LinkedList_t*)calloc( 1, sizeof(LinkedList_t) );
    pList->head = pList->tail = NULL;
    pList->size = 0;
    return pList;
}


/* added on 02/27/03 : P.L
   add a data in linked list, sorted by comparator fct given in argument
*/
void* ll_add_sorted( LinkedList_t *pll,void *data, int (*comparator)(void *,void *))
{
  sElement_t *pElem;
  sElement_t * prev;
  sElement_t * tmp;

  tmp = malloc(sizeof(sElement_t));
  ASSERT(tmp);
  tmp->pNext = NULL;
  tmp->data = data;

  if( pll->head == NULL)
    {
      /* begin new linked list with 'data' */

      pll->head = tmp;
      pll->tail = tmp;
      pll->size = 1;
      return data;
    }

  /* pll->head != NULL */

  /* data to add at head */
  if (comparator(data , (pll->head->data)))
    {
      tmp->pNext = pll->head;
      pll->head = tmp;
      (pll->size)++;
      return data;
    }

  /* data to add in middle */
  pElem = pll->head->pNext;
  prev = pll->head;
  for (; pElem ; pElem = pElem->pNext)
    {
      if(comparator(data , (pElem->data)))
	{
	  prev->pNext = tmp;
	  tmp->pNext = pElem;
	  (pll->size)++;
	  return data;
	}
      prev = pElem;
    }

  /* data to add at tail */
  pll->tail->pNext = tmp;
  pll->tail = tmp;
  (pll->size)++;
  return data;
}


void
free_ll_elem (sElement_t * element)
{
  free (element->data);
  free (element);
}