/*
  $Log: list.c,v $
  Revision 1.5  2003/07/14 13:36:58  ivo
  use space() instead of malloc

  Revision 1.4  2000/10/10 08:53:52  ivo
  include dmalloc.h header if DMALLOC defined

  Revision 1.4  2000/10/10 08:04:34  ivo
  include dmalloc header id DMALLOC defined

  Revision 1.3  1998/03/30 14:24:51  ivo
  use RNA package utils.h

  Revision 1.2  1997/10/09  19:01:50  steve
  *** empty log message ***

  Revision 1.1  1997/08/04 21:05:32  walter
  Initial revision

*/
/*
   (C) 1991 Kendall Bennett.
*/

#include <stdio.h>
#include <stdlib.h>
#include "utils.h"
#include "list.h"

/*@unused@*/
static char rcsid[] = "$Id: list.c,v 1.5 2003/07/14 13:36:58 ivo Exp $";

#define PUBLIC
PUBLIC void *
lst_newnode (int size)
/****************************************************************************
*
* Function:	lst_newnode
* Parameters:	size - Amount of memory to allocate for node
* Returns:      Pointer to the allocated node's user space.
*
* Description:	Allocates the memory required for a node, adding a small
*		header at the start of the node. We return a reference to
*		the user space of the node, as if it had been allocated via
*		malloc().
*
****************************************************************************/
{
  LST_BUCKET *node;

  node = (LST_BUCKET *) space (size + sizeof (LST_BUCKET));

  return LST_USERSPACE (node);	/* Return pointer to user space */
}

PUBLIC void
lst_freenode (void *node)
/****************************************************************************
*
* Function:	lst_freenode
* Parameters:	node - Node to free.
*
* Description:  Frees a node previously allocated with lst_newnode().
*
****************************************************************************/
{
  free (LST_HEADER (node));
}

PUBLIC LIST *
lst_init (void)
/****************************************************************************
*
* Function:	lst_init
* Returns:      Pointer to a newly created list.
*
* Description:	Initialises a list and returns a pointer to it.
*
****************************************************************************/
{
  LIST *l;

  if ((l = (LIST *) space (sizeof (LIST))) != NULL)
    {
      l->count = 0;
      l->head = &(l->hz[0]);
      l->z = &(l->hz[1]);
      l->head->next = l->z->next = l->z;
    }

  return l;
}

PUBLIC void
lst_kill (LIST * l, void (*freeNode) (void *node))
/****************************************************************************
*
* Function:	lst_kill
* Parameters:	l - List to kill
*		freeNode - Pointer to user routine to free a node
*
* Description:	Kills the list l, by deleting all of the elements contained
*		within the list one by one and then deleting the list
*		itself. Note that we call the user supplied routine
*		(*freeNode)() to free each list node. This allows the user
*		program to perform any extra processing needed to kill each
*		node (if each node contains pointers to other items on the
*		heap for example). If no extra processing is required, just
*		pass the address of lst_freenode(), ie:
*
*		lst_kill(myList,lst_freenode);
*
****************************************************************************/
{
  LST_BUCKET *n, *p;

  n = l->head->next;
  while (n != l->z)
    {				/* Free all nodes in list  */
      p = n;
      n = n->next;
      (*freeNode) (LST_USERSPACE (p));
    }
  free (l);			/* Free the list itself    */
}

PUBLIC void
lst_insertafter (LIST * l, void *node, void *after)
/****************************************************************************
*
* Function:	lst_insertafter
* Parameters:	l - List to insert node into
*		node - Pointer to user space of node to insert
*		after - Pointer to user space of node to insert node after
*
* Description:	Inserts a new node into the list after the node 'after'. To
*		insert a new node at the beginning of the list, user the
*		macro LST_HEAD in place of 'after'. ie:
*
*		lst_insertafter(mylist,node,LST_HEAD(mylist));
*
****************************************************************************/
{
  LST_BUCKET *n = LST_HEADER (node), *a = LST_HEADER (after);

  n->next = a->next;
  a->next = n;
  l->count++;
}

PUBLIC void *
lst_deletenext (LIST * l, void *node)
/****************************************************************************
*
* Function:	lst_deletenext
* Parameters:	l - List to delete node from.
*		node - Node to delete the next node from
* Returns:	Pointer to the deleted node's userspace.
*
* Description:	Removes the node AFTER 'node' from the list l.
*
****************************************************************************/
{
  LST_BUCKET *n = LST_HEADER (node);

  node = LST_USERSPACE (n->next);
  n->next = n->next->next;
  l->count--;
  return node;
}

PUBLIC void *
lst_first (LIST * l)
/****************************************************************************
*
* Function:	lst_first
* Parameters:	l - List to obtain first node from
* Returns:	Pointer to first node in list, NULL if list is empty.
*
* Description:	Returns a pointer to the user space of the first node in
*		the list. If the list is empty, we return NULL.
*
****************************************************************************/
{
  LST_BUCKET *n;

  n = l->head->next;
  return (n == l->z ? NULL : LST_USERSPACE (n));
}

PUBLIC void *
lst_next (void *prev)
/****************************************************************************
*
* Function:	lst_next
* Parameters:	prev - Previous node in list to obtain next node from
* Returns:	Pointer to the next node in the list, NULL at end of list.
*
* Description:	Returns a pointer to the user space of the next node in the
*		list given a pointer to the user space of the previous node.
*		If we have reached the end of the list, we return NULL. The
*		end of the list is detected when the next pointer of a node
*		points back to itself, as does the dummy last node's next
*		pointer. This enables us to detect the end of the list
*		without needed access to the list data structure itself.
*
*		NOTE:	We do no checking to ensure that 'prev' is NOT a
*			NULL pointer.
*
****************************************************************************/
{
  LST_BUCKET *n = LST_HEADER (prev);

  n = n->next;
  return (n == n->next ? NULL : LST_USERSPACE (n));
}

/* Static globals required by merge()   */

static LST_BUCKET *z;
static int (*cmp) (void *, void *);

static LST_BUCKET *
merge (LST_BUCKET * a, LST_BUCKET * b, LST_BUCKET ** end)
/****************************************************************************
*
* Function:	merge
* Parameters:	a,b - Sublist's to merge
* Returns:	Pointer to the merged sublists.
*
* Description:	Merges two sorted lists of nodes together into a single
*		sorted list.
*
****************************************************************************/
{
  LST_BUCKET *c;

  /* Go through the lists, merging them together in sorted order  */

  c = z;
  while (a != z && b != z)
    {
      if ((*cmp) (LST_USERSPACE (a), LST_USERSPACE (b)) <= 0)
	{
	  c->next = a;
	  c = a;
	  a = a->next;
	}
      else
	{
	  c->next = b;
	  c = b;
	  b = b->next;
	}
    };

  /* If one of the lists is not exhausted, then re-attach it to the end
   * of the newly merged list
   */

  if (a != z)
    c->next = a;
  if (b != z)
    c->next = b;

  /* Set *end to point to the end of the newly merged list        */

  while (c->next != z)
    c = c->next;
  *end = c;

  /* Determine the start of the merged lists, and reset z to point to
   * itself
   */

  c = z->next;
  z->next = z;
  return c;
}

PUBLIC void
lst_mergesort (LIST * l, int (*cmp_func) (void *, void *))
/****************************************************************************
*
* Function:	lst_mergesort
* Parameters:	l - List to merge sort
*		cmp_func - Function to compare two user spaces
*
* Description:	Mergesort's all the nodes in the list. 'cmp' must point to
*		a comparison function that can compare the user spaces of
*		two different nodes. 'cmp' should work the same as
*		strcmp(), in terms of the values it returns.
*
****************************************************************************/
{
  int i, N;
  LST_BUCKET *a, *b;		/* Pointers to sublists to merge                */
  LST_BUCKET *c;		/* Pointer to end of sorted sublists            */
  LST_BUCKET *head;		/* Pointer to dummy head node for list          */
  LST_BUCKET *todo;		/* Pointer to sublists yet to be sorted         */
  LST_BUCKET *t;		/* Temporary                                                            */

  /* Set up globals required by merge() and pointer to head       */

  z = l->z;
  cmp = cmp_func;
  head = l->head;

  for (N = 1, a = z; a != head->next; N = N + N)
    {
      todo = head->next;
      c = head;
      while (todo != z)
	{

	  /* Build first sublist to be merged, and splice from main list
	   */

	  a = t = todo;
	  for (i = 1; i < N; i++)
	    t = t->next;
	  b = t->next;
	  t->next = z;
	  t = b;

	  /* Build second sublist to be merged and splice from main list
	   */

	  for (i = 1; i < N; i++)
	    t = t->next;
	  todo = t->next;
	  t->next = z;

	  /* Merge the two sublists created, and set 'c' to point to the
	   * end of the newly merged sublists.
	   */

	  c->next = merge (a, b, &t);
	  c = t;
	}
    }
}

#ifdef LIST_TEST

/*---------------------------------------------------------------*/
/*---------------------------------------------------------------*/

/* Simple program to test the list routines */

typedef struct
{
  char name[40];
  int age;
}
REC;

/*---------------------------------------------------------------*/

int
my_cmp (REC * r1, REC * r2)
{
  return strcmp (r1->name, r2->name);
}

/*---------------------------------------------------------------*/

void
main (void)
{
  LIST *list;
  int done = 0;
  REC *rec;
  char line[80];

  list = lst_init ();

  printf ("Type a list of names and ages. Empty line quits\n\n");

  while (!done)
    {
      rec = lst_newnode (sizeof (REC));
      gets (line);
      if ((done = (line[0] == '\0')) != 1)
	{
	  strcpy (rec->name, line);
	  gets (line);
	  rec->age = atoi (line);
	  lst_insertafter (list, rec, LST_HEAD (list));
	}
    };

  printf ("\nThe list you typed in was:\n\n");

  for (rec = lst_first (list); rec; rec = lst_next (rec))
    printf ("Name: %s, Age: %d\n", rec->name, rec->age);

  printf ("\nSorting the list...\n\n");

  lst_mergesort (list, my_cmp);

  for (rec = lst_first (list); rec; rec = lst_next (rec))
    printf ("Name: %s, Age: %d\n", rec->name, rec->age);

  lst_kill (list, lst_freenode);
}

/*---------------------------------------------------------------*/

#endif