---

slist.c

/*  slist.c - Single linked list.
 *            This file is part of the FreeLCD package.
 *
 *  $Id: slist_8c-source.html,v 1.1 2003/02/16 22:50:41 unicorn Exp $
 *
 *  This program is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License as published by the
 *  Free Software Foundation; either version 2 of the License, or (at your
 *  option) any later version.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 *  MA  02111-1307  USA
 *
 *  Copyright (c) 2002, 2003, Jeroen van den Berg <unicorn@hippie.nu>
 */

#include <stdlib.h>
#include <assert.h>

#include "slist.h"
#include "xmalloc.h"

/*---------------------------------------------------------------- _nop --*/
static void
_nop (void *data)
{
  /* Do nothing */
}

/*----------------------------------------------------- _simple_compare --*/
static inline int
_simple_compare (const void *data, const void *compare)
{
  return data == compare;
}

/*---------------------------------------------------------- slist_init --*/
void
slist_init (slist * s)
{
  assert (s);
  s->head = 0;
  s->tail = 0;
}

/*------------------------------------------------ slist_delete_special --*/
void
slist_delete_special (slist * s, void (*func) (void *))
{
  slist_e *tmp;
  assert (s);

  while (s->head)
    {
      func (s->head->data);
      tmp = s->head;
      s->head = s->head->next;
      free (tmp);
    }
}

/*-------------------------------------------------------- slist_delete --*/
void
slist_delete (slist * s)
{
  assert (s);
  slist_delete_special (s, free);
}

/*---------------------------------------------- slist_delete_list_only --*/
void
slist_delete_list_only (slist * s)
{
  assert (s);
  slist_delete_special (s, _nop);
}

/*--------------------------------------------------------- slist_first --*/
void *
slist_first (const slist * s)
{
  assert (s);
  return s->head ? s->head->data : 0;
}

/*---------------------------------------------------------- slist_last --*/
void *
slist_last (const slist * s)
{
  assert (s);
  return s->tail ? s->tail->data : 0;
}

/*------------------------------------------------------- slist_at_iter --*/
void *
slist_at_iter (slist_iter iter)
{
  return iter.curr ? iter.curr->data : 0;
}

/*------------------------------------------------------- slist_prepend --*/
void
slist_prepend (slist * s, void *data)
{
  slist_e *newelem = xmalloc (sizeof (slist_e));
  assert (s);

  newelem->next = s->head;
  newelem->data = data;
  s->head = newelem;
}

/*-------------------------------------------------------- slist_append --*/
void
slist_append (slist *s, void *data)
{
  slist_e *newelem = xmalloc (sizeof (slist_e));
  assert (s);

  newelem->next = 0;
  newelem->data = data;
  
  if (s->tail)
    s->tail->next = newelem;
  else
    s->head = newelem;
  
  s->tail = newelem;
}

/*-------------------------------------------------------- slist_insert --*/
void
slist_insert (slist *s, slist_iter *iter, void *data)
{
  assert (s);
  assert (iter);

  if (!iter->prev)
    {
      slist_prepend (s, data);
      iter->prev = s->head;
    }
  else if (!iter->curr)
    {
      slist_append (s, data);
      iter->prev = s->tail;
    }
  else
    {
      slist_e *newelem = xmalloc (sizeof (slist_e));

      newelem->next = iter->curr;
      iter->prev->next = newelem;
      iter->prev = newelem;
      newelem->data = data;
    }
}

/*-------------------------------------------------- slist_remove_first --*/
void*
slist_remove_first (slist *s)
{
  void *removed_data = 0;
  slist_e *tmp;
  assert (s);

  if (s->head)
    {
      removed_data = s->head->data;
      tmp = s->head->next;
      free (s->head);
      s->head = tmp;

      if (!s->head)
        s->tail = 0;
    }

  return removed_data;
}

/*--------------------------------------------------- slist_remove_last --*/
void*
slist_remove_last (slist *s)
{
  void    *removed_data = 0;
  slist_e *tmp;
  assert (s);

  if (s->tail)
    {
      removed_data = s->tail->data;
      if (s->head == s->tail)
        {
          free (s->tail);
          s->head = 0;
          s->tail = 0;

          return removed_data;
        }
      tmp = s->head;

      while (tmp->next != s->tail)
        tmp = tmp->next;

      tmp->next = 0;
      free (s->tail);
      s->tail = tmp;
    }
  
  return removed_data;
}

/*--------------------------------------------------- slist_remove_iter --*/
void*
slist_remove_at_iter (slist *s, slist_iter iter)
{
  void *removed_data = 0;
  assert (s);
  
  if (!iter.curr)
    return removed_data;

  removed_data = iter.curr->data;
  if (!iter.prev)
    {
      slist_remove_first (s);
    }
  else
    {
      iter.prev->next = iter.curr->next;
      if (iter.curr == s->tail)
        s->tail = iter.prev;

      free (iter.curr);
    }
  
  return removed_data;
}

/*---------------------------------------------------- slist_begin_iter --*/
slist_iter
slist_begin_iter (const slist *s)
{
  slist_iter begin;
  assert (s);

  begin.curr = s->head;
  begin.prev = 0;

  return begin;
}

/*------------------------------------------------------ slist_end_iter --*/
slist_iter
slist_end_iter (const slist *s)
{
  slist_iter end;
  assert (s);

  end.curr = 0;
  end.prev = s->tail;

  return end;
}

/*------------------------------------------------- slist_iter_and_next --*/
void *
slist_iter_and_next (slist_iter *iter)
{
  void *prev_data = 0;
  assert (iter);

  if (iter->curr)
    {
      prev_data  = iter->curr->data;
      iter->prev = iter->curr;
      iter->curr = iter->curr->next;
    }
  
  return prev_data;
}

/*------------------------------------------------------ slist_for_each --*/
void
slist_for_each (const slist * s, void (*func) (void *data, void* userdata),
                void *userdata)
{
  assert (s);
  assert (func);

  slist_for_each_range (slist_begin_iter (s), slist_end_iter (s), 
                        func, userdata);
}

/*------------------------------------------------ slist_for_each_range --*/
void
slist_for_each_range (slist_iter begin, slist_iter end,
                      void (*func) (void *data, void* userdata),
                      void *userdata)
{
  slist_e *elem = begin.curr;
  assert (func);

  if (elem)
    {
      while (elem != end.curr)
        {
          func (elem->data, userdata);
          elem = elem->next;
        }
    }
}

/*---------------------------------------------------------- slist_find --*/
slist_iter
slist_find (const slist * s, const void *data)
{
  assert (s);

  /*  The _simple_compare() function is defined near the top, and only
   *  compares the two given pointers.
   */
  return slist_find_if (s, data, _simple_compare);
}

/*------------------------------------------------------- slist_find_if --*/
slist_iter
slist_find_if (const slist * s,
               const void *compare,
               int (*compare_func) (const void *data, const void *compare))
{
  slist_iter i = slist_begin_iter (s);
  assert (s);
  assert (compare_func);

  while (i.curr && !compare_func (i.curr->data, compare))
    slist_iter_and_next (&i);

  return i;
}

/*------------------------------------------------------- slist_iter_eq --*/
int
slist_iter_eq (slist_iter a, slist_iter b)
{
  return a.curr == b.curr && a.prev == b.prev;
}

/*--------------------------------------------------- slist_iter_at_end --*/
int
slist_iter_at_end (slist_iter iter)
{
  return iter.curr == 0;
}

/*-------------------------------------------------------- slist_length --*/
unsigned int
slist_length (const slist *s)
{
  unsigned int  length = 0;
  const slist_e *elem = s->head;
  assert (s);

  while (elem)
    {
      ++length;
      elem = elem->next;
    }
  
  return length;
}


#ifdef UNIT_TEST_SLIST_C

void *
xmalloc (size_t size)
{
  void *alloc = malloc (size);

  if (alloc == 0)
    {
      printf ("out of memory (malloc)\n");
      exit (EXIT_FAILURE);
    }

  return alloc;
}

void 
multiply (void *value, void* result)
{
  *(int*)result *= *(int*)value;
}

int 
is_seven (const void *value, const void *compare)
{
  return *(int*)value == 7;
}

int
main (int argc, char **argv)
{
  slist list;
  int   data[] = { 5, 6, 7, 8, 9, 10 };
  slist_iter i;
  slist_iter end;
  int   result = 1;


  slist_init (&list);
  slist_append (&list, &data[1]);

  if (slist_first (&list) != &data[1])
    {
      printf ("first slist_first() failed\n");
      exit (1);
    }
  
  if (slist_last (&list) != &data[1])
    {
      printf ("first slist_last() failed\n");
      exit (1);
    }

  slist_append (&list, &data[3]);
  slist_prepend (&list, &data[0]);
  if (slist_first (&list) != &data[0])
    {
      printf ("second slist_first() failed\n");
      exit (1);
    }
  if (slist_last (&list) != &data[3])
    {
      printf ("second slist_last() failed\n");
      exit (1);
    }
    
  i   = slist_begin_iter (&list);
  end = slist_end_iter (&list);

  if (slist_at_iter (i) != &data[0])
    {
      printf ("first slist_at_iter() failed\n");
      exit (1);
    }
  
  if (slist_iter_and_next (&i) != &data[0])
    {
      printf ("first slist_iter_and_next() failed\n");
      exit (1);
    }

  if (slist_at_iter (i) != &data[1])
    {
      printf ("second slist_at_iter() failed\n");
      exit (1);
    }
  
  
  slist_iter_and_next (&i);
  slist_insert (&list, &i, &(data[2]));
  
  if (i.prev->data != &(data[2]))
    {
      printf ("first slist_insert() failed\n");
      exit (1);
    }

  slist_insert (&list, &end, &(data[4]));

  if (slist_last (&list) != &(data[4]))
    {
      printf ("third slist_last() failed\n");
      exit (1);
    }
  

  if (slist_length (&list) != 5)
    {
      printf ("slist_length() failed (%i)\n", slist_length (&list));
      exit (1);
    }
  
  slist_for_each (&list, multiply, &result);
  if (result != 15120)
    {
      printf ("slist_for_each() failed (%i)\n", result);
      exit (1);
    }
  
  i = slist_find (&list, &(data[2]));
  if (slist_at_iter (i) != &(data[2]))
    {
      printf ("slist_find() failed\n");
      exit (1);
    }
      
  result = 1;
  slist_for_each_range (i, end, multiply, &result);
  if (result != 504)
    {
      printf ("slist_for_each_range() failed (%i)\n", result);
      exit (1);
    }
  
  i = slist_find (&list, &(data[5]));
  if (!slist_iter_eq (i, end))
    {
      printf ("slist_find() succeeded, but should have failed\n");
      exit (1);
    }

  if (!slist_iter_at_end (i))
    {
      printf ("slist_iter_at_end() failed\n");
      exit (1);
    }
      
  i = slist_find_if (&list, 0, is_seven );
  if (slist_at_iter (i) != &(data[2]))
    {
      printf ("slist_find_if() failed\n");
      exit (1);
    }
      
  if (   slist_remove_first (&list) != &(data[0])
      || slist_first (&list) != &(data[1]))
    {
      printf ("slist_remove_first() failed\n");
      exit (1);
    }

  if (   slist_remove_last (&list) != &(data[4])
      || slist_last (&list) != &(data[3]))
    {
      printf ("slist_remove_last() failed\n");
      exit (1);
    }

  if (slist_remove_at_iter (&list, i) != &(data[2]))
    {
      printf ("slist_remove_iter() failed\n");
      exit (1);
    }

  slist_delete_list_only (&list);

  return 0;
}

#endif

---