--- /dev/null
+/*
+ $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
git://source.jalview.org / jabaws.git / blobdiff