Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/misc/volume37/linkedlist/part01

Text File | 1993-05-04 | 58.0 KB | 2,415 lines

Newsgroups: comp.sources.misc
From: [e-mail] (Anita Eijs)
Subject: v37i036:  linkedlist - Generic Linked List Package, Part01/02
Message-ID: <csm-v37i036=[e-mail]>
X-Md4-Signature: bf3ce1eff0daaa6d0be911c12a01aef0
Date: Tue, 4 May 1993 15:43:54 GMT
Approved: [e-mail]

Submitted-by: [e-mail] (Anita Eijs)
Posting-number: Volume 37, Issue 36
Archive-name: linkedlist/part01
Environment: UNIX, MS-DOS, VAX/VMS, Macintosh
Supersedes: linkedlist: Volume 30, Issue 22

LinkedList Version: 0.8, May 1992

The Generic Linked List Package is a package to define, create, update, query
and delete one or more (nodes of) linked lists, to sort linked lists, and so
on. The user doesn't have to take care of allocating a number of bytes for a
node, inserting on the right place, deleting and freeing a node and so on.

Different kind of linked lists can be defined. In a singly linked list
each node points to the next node, in a doubly linked list each node
points also to the previous node. A chain is a list in which the last
node has a NULL-pointer and in a circular linked list the last node
points back to the first node.

The package consists of a set of C-functions :
    lDef        define linked list
    lInfo        get information about linked list
    lSort        sort linked list
    lDel        delete linked list
    lDelAll        delete all linked lists
    lDump        dump a linked list to a file
    lUndump        undump a linked list from a file
    lInsNode    insert node
    lInfoNode    get information about node
    lGetNode    get node
    lFndNode    find node
    lFndFlagNode    get node by flag
    lUpdNode    update current node
    lDelNode    delete node
    lInfoIndxNode    get information about node by index
    lGetIndxNode    get node by index
    lUpdIndxNode    update node by index
    lDelIndxNode    delete node by index

The Generic Linked List Package is ported to UNIX, MS-DOS, VAX/VMS and
Macintosh.

Please look at the README file and the manual pages for more detailed
information !

        Anita

    +--------------------------------------------------------+
    | TNO - BOUW, PO-box 49, 2600 AA  Delft, The Netherlands |
    | FAX : [phone]         E-MAIL : [e-mail] |
    +--------------------------------------------------------+
------- cut here ------------------------------------------------
#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# Contents:  README Doc Makefile list.c sorted.c
# Wrapped by kent@sparky on Tue May  4 10:37:10 1993
PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 1 (of 2)."'
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
  echo shar: Extracting \"'README'\" \(1996 characters\)
  sed "s/^X//" >'README' <<'END_OF_FILE'
X                Generic Linked List
X                ===================
X
X
XThe distribution of the Generic Linked List package (Version 0.8, May 1993)
Xincludes the following files:
X
X    Doc/Intro.3        - [nt]roff manual pages
X    Doc/lDef.3
X    Doc/lDel.3
X    Doc/lDelAll.3
X    Doc/lDelIndxNode.3
X    Doc/lDelNode.3
X    Doc/lDump.3
X    Doc/lFndFlagNode.3
X    Doc/lFndNode.3
X    Doc/lGetNode.3
X    Doc/lGetIndxNode.3
X    Doc/lInfo.3
X    Doc/lInfoIndxNode.3
X    Doc/lInfoNode.3
X    Doc/lInsNode.3
X    Doc/lSort.3
X    Doc/lUndump.3
X    Doc/lUpdIndxNode.3
X    Doc/lUpdNode.3
X    Makefile        - Berkeley or System V Makefile
X    Makefile.BCC        - Borland C++ v3.1 Makefile
X    README            - this file !
X    CHANGES            - list of changes
X    Tools_makerule        - make rules for Makefile
X    example.c        - example of use of Generic Linked List routines
X    sorted.c        - example of several sorting solutions
X    sorttest.c        - test of sorting theories in lSort
X    list.c            - Generic Linked List sources
X    list.h            - Generic Linked List defines and prototypes
X
X
XThe installation of the Generic Linked List library is pretty simple :
X
X1)    Check the environment settings (TOOLS_HOME, DIR, LIB and RULE) in
X    the Makefile.
X
X2)    Check the environment settings (RANLIB) in the Tools_makerule.
X
X3)    Enter 'make newlib' at the UNIX prompt.
X
X4)    Enter 'make test' or 'make example' to create the executable of
X    the program 'example' at the UNIX prompt.
X
X
XI also ported the Generic Linked List to MSDOS, VAX-VMS and Macintosh. I
Xdidn't create a library on those machines, but I treated list.c and list.h
Xthe same as all the other source-files (*.[ch]) of the program.
X
X
XThe Generic Linked List is in the public domain. It is available at our FTP
Xarchive (ftp.tno.nl or hermes.bouw.tno.nl), just retrieve te files :
X    /pub/TNO/BOUW/Bouwinf/linkedlist_0.8.README
X    /pub/TNO/BOUW/Bouwinf/linkedlist_0.8.shar
X
X
XIf you have any comments, suggestions, or find any bugs, or make any changes
Xyou'd like to share, please let me know.
X
X
XAnita Eijs    ([e-mail])
XTNO - BOUW - BouwInformatica
XP.O. Box 49
X2600 AA Delft
XThe Netherlands
XFAX : [phone]
END_OF_FILE
  if test 1996 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
  fi
  # end of 'README'
fi
if test ! -d 'Doc' ; then
    echo shar: Creating directory \"'Doc'\"
    mkdir 'Doc'
fi
if test -f 'Makefile' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'Makefile'\"
else
  echo shar: Extracting \"'Makefile'\" \(1810 characters\)
  sed "s/^X//" >'Makefile' <<'END_OF_FILE'
X# Generic Linked List
X#
X# Anita Eijs, TNO-BOUW, BouwInformatica, September 1989
X
X# Compiler options
XCC    = gcc
XCFLAGS    =
X
XTOOLS_HOME    = /usr1/user/anita/usr2/Tools
X
X# Name of current directory
XDIR    = List
X
X# Name of library
XLIB    = $(TOOLS_HOME)/Lib/list.a
X
X# Include rules for package
XMAKERULE= Tools_makerule
XRULE    = $(TOOLS_HOME)/$(MAKERULE)
Xinclude $(RULE)
X
X# Contents of current directory
XLIST    = Makefile Makefile.BCC \
X    README CHANGES \
X    list.c list.h \
X    example.c sorted.c sorttest.c
X
X# Documentation
XDOC    = \
X    Doc/Intro.3        Doc/lDef.3        Doc/lDel.3 \
X    Doc/lDelAll.3        Doc/lDelIndxNode.3    Doc/lDelNode.3 \
X    Doc/lDump.3        Doc/lFndFlagNode.3    Doc/lFndNode.3 \
X    Doc/lGetNode.3        Doc/lGetIndxNode.3    Doc/lInfo.3 \
X    Doc/lInfoIndxNode.3    Doc/lInfoNode.3        Doc/lInsNode.3 \
X    Doc/lSort.3        Doc/lUndump.3        Doc/lUpdIndxNode.3 \
X    Doc/lUpdNode.3
X
X# Object dependencies
XOBJ    = list.o
X
XLIB_OBJ    = $(LIB)(list.o)
X
X# The targets
Xusage:
X        $(ECHO)
X        $(ECHO) $(USAGE_ID)
X        $(ECHO) $(USAGE_TARGETS)
X        $(ECHO) $(USAGE_USAGE)
X        $(ECHO) $(USAGE_LIB)
X        $(ECHO) $(USAGE_NEWLIB)
X        $(ECHO) $(USAGE_OFILES)
X        $(ECHO) $(USAGE_TEST)
X        $(ECHO) $(USAGE_TAR)
X        $(ECHO)
X        $(ECHO) $(USAGE_DEFLTS1)
X        $(ECHO) $(USAGE_DEFLTS2)
X        $(ECHO) $(USAGE_DEFLTS3)
X
Xall: ofiles newlib example sorttest sorted
X
Xlib:        $(LIB_OBJ)
X        $(RANLIB) $(LIB)
X
Xnewlib:        $(OBJ)
X        $(AR) r $(LIB) *.o
X        rm -f *.o
X        $(RANLIB) $(LIB)
X
Xofiles:        $(OBJ)
X
Xtest:        example sorttest sorted
X
Xexample:    $(LIB) example.o
X        $(CC) -o example example.o $(LIB)
X
Xsorttest:    $(LIB) sorttest.o
X        $(CC) -o sorttest sorttest.o $(LIB)
X
Xsorted:        $(LIB) sorted.o
X        $(CC) -o sorted sorted.o $(LIB)
X
Xtar:
X        $(ECHO) "Making tar-file in $(TARFILE)"
X        cp ../$(MAKERULE) $(MAKERULE)
X        tar cvf $(TARFILE) $(MAKERULE) $(LIST) $(DOC)
X        rm $(MAKERULE)
X
Xclean:
X        $(ECHO) "Cleaning Directory"
X        rm $(OBJ) example sorttest sorted
END_OF_FILE
  if test 1810 -ne `wc -c <'Makefile'`; then
    echo shar: \"'Makefile'\" unpacked with wrong size!
  fi
  # end of 'Makefile'
fi
if test -f 'list.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'list.c'\"
else
  echo shar: Extracting \"'list.c'\" \(40715 characters\)
  sed "s/^X//" >'list.c' <<'END_OF_FILE'
X/*
X**    Anita Eijs    TNO-BOUW, BouwInformatica    May 1989
X**
X**    Generic Linked List Package
X**
X**    Updates:
X**    900402    New routine:
X**            lIndxNode    Get node by index.
X**
X**    900925    New routine:
X**            lError    print error message in lERROR_FILE
X**
X**    901129    New routines:
X**            lDump    Dump a linked list to a file.
X**            lUndump    Undump a linked list from a file.
X**
X**    910301    'Mac'ed by Vinnie:
X**            ListPtr = ListyPtr
X**            Byte = byte
X**            includes
X**            typecasts
X**
X**    910316    New routine:
X**            lFlagNode    Get node by flag.
X**
X**    ***** Version 0.7, March 1992 *****
X**
X**    930401    Several updates by Anita and Shane.
X**        Some functions renamed:
X**            lIndxNode --> lGetIndxNode
X**            lFlagNode --> lFndFlagNode
X**        New routines:
X**            lSort        Sort a linked list.
X**            lInfoIndxNode    Get information about node by index.
X**            lDelIndxNode    Delete node by index.
X**            lUpdIndxNode    Update node by index.
X**        Parameter where added to lFndFlagNode to find several nodes
X**        matching the requested flag.
X**        Defines are made more specific; FIRST is renamed in lFIRST, etc.
X**
X**    ***** Version 0.8, May 1993 *****
X*/
X
X#ifdef MAC
X#define    MAC_OR_VAXC
X#endif
X#ifdef VAXC
X#define    MAC_OR_VAXC
X#define    MSDOS_OR_VAXC
X#endif
X#ifdef MSDOS
X#define    MSDOS_OR_VAXC
X#endif
X
X#ifdef MAC
X#include    <unix.h>    /* open, creat, write, read, close */
X#include    <stddef.h>    /* sizeof */
X#endif
X
X#ifdef MAC_OR_VAXC
X#include    <stdlib.h>
X#else
X#include    <malloc.h>
X#endif
X
X#ifdef MSDOS
X#include    <io.h>    /* open, creat, write, read, close */
X#endif
X
X#include    <stdio.h>
X#include    "list.h"
X
X/* -------------------------------------------------------------------------- */
X
X#ifndef NULL
X#define    NULL    0
X#endif
X
X#undef    FREE
X#define FREE(VAR) if (VAR != NULL) free((char *)VAR);
X#undef    MALLOC
X#define MALLOC(VAR, TYPE) \
X    if ((VAR = (TYPE *)malloc(sizeof(TYPE))) == NULL) { \
X        fprintf(stderr, "No more memory for malloc().\n"); \
X    }
X#undef    CALLOC
X#define CALLOC(VAR, TYPE, NR) \
X    if ((VAR = (TYPE *)calloc(NR, sizeof(TYPE))) == NULL) {\
X        fprintf(stderr, "No more memory for calloc().\n"); \
X    }
X
X#undef    BYTE_COPY
X#define BYTE_COPY(FROM, TO, SIZE) \
X    { \
X        register Byte    *frm = FROM, \
X                *to = TO; \
X        int        i = SIZE; \
X        while (i--) *to++ = *frm++; \
X    }
X
X#define    BIN_WRITE    1    /* necessary for binary file access */
X#define    BIN_READ    0
X#define    PMODE        0666
X
X/* -------------------------------------------------------------------------- */
X
X#ifndef ANSI
Xtypedef    int        (*Func)();
Xtypedef    unsigned char    Byte;
X#endif
X
Xtypedef struct lnode {
X    Byte        *data;    /* data of user */
X    int        size;    /* size (number of bytes) of data */
X    int        flag;    /* user information flag */
X    struct lnode    *prv;    /* previous node */
X    struct lnode    *nxt;    /* next node */
X} ListNode, *NodePtr;
X
Xtypedef struct listhdr {
X    int        id;        /* identifier of linked list */
X    int        sd;        /* singly or doubly linked */
X    int        cc;        /* chain or circular list */
X    int        n;        /* number of nodes */
X    NodePtr        first;        /* address of first node */
X    NodePtr        current;    /* address of current node */
X    NodePtr        last;        /* address of last node */
X    struct listhdr    *nxt;        /* next linked list */
X} ListHdr, *ListPtr;
X
Xtypedef struct header {    /* general info of linked list for dump file */
X    int    sd;
X    int    cc;
X    int    n;
X} Header;
X
Xtypedef struct info {    /* general info of node for dump file */
X    int    size;
X    int    flag;
X} Info;
X
X/* -------------------------------------------------------------------------- */
X
X#ifdef ANSI
Xstatic ListPtr    getAddress(int id);
Xstatic void    delNodes(NodePtr node, int n);
Xstatic void    delListInfo(ListPtr list);
Xstatic void    lError(char *str, int code, int int1, int int2, char *str1);
Xstatic int    setWhchNode(int id, int which, char *fname);
Xstatic int    setIndxNode(int id, int index, char *fname);
Xstatic int    partition(NodePtr *array, int order, Func func, int lb, int ub,
X            int *pj);
Xstatic int    stack_empty(int id);
Xstatic int    intInSet(int intgr, int *set, int set_n);
X#else
Xstatic ListPtr    getAddress();
Xstatic void    delNodes();
Xstatic void    delListInfo();
Xstatic void    lError();
Xstatic int    setWhchNode();
Xstatic int    setIndxNode();
Xstatic int    partition();
Xstatic int    stack_empty();
Xstatic int    intInSet();
X#endif
X
X/* -------------------------------------------------------------------------- */
X
Xstatic ListHdr    firstlist = { 1, 0, 0, 0, NULL, NULL, NULL, NULL };
Xstatic ListPtr    ld = &firstlist;
Xstatic int    idMax = 2;
X
X/* -------------------------------------------------------------------------- */
X
X/*******************************************************************************
X** Define a new linked list and create info about it.
X**
X** Parameters:
X**    In    int    sd    singly or doubly linked
X**                (lSINGLY, lDOUBLY)
X**    In    int    cc    chain or circular linked
X**                (lCHAIN, lCIRCULAR)
X**
X** Return on success:
X**    identifier of linked list
X** Return on error:
X**    lWRONG_SD, lWRONG_CC
X*/
X#ifdef ANSI
Xint
XlDef(int sd, int cc)
X#else
Xint
XlDef(sd, cc)
Xint    sd, cc;
X#endif
X{
X    ListPtr        list, new;
X    static int    set1[] = { lSINGLY, lDOUBLY },
X            set2[] = { lCHAIN, lCIRCULAR };
X
X        /* check parameters */
X    if (intInSet(sd, set1, 2) != 0) {
X        lError("lDef", lWRONG_SD, sd, 0, NULL);
X        return(lWRONG_SD);
X    }
X    if (intInSet(cc, set2, 2) != 0) {
X        lError("lDef", lWRONG_CC, cc, 0, NULL);
X        return(lWRONG_CC);
X    }
X
X    list = ld;
X    while (list->nxt != NULL && list->sd != 0)
X        list = list->nxt;
X    if (list->sd != 0) {    /* new list */
X        MALLOC(new, ListHdr);
X        new->id = idMax++;
X        new->sd = sd;
X        new->cc = cc;
X        new->n = 0;
X        new->first = new->current = new->last = NULL;
X        new->nxt = NULL;
X        list->nxt = new;
X        return(new->id);
X    } else {        /* new list on existing place */
X        list->sd = sd;
X        list->cc = cc;
X        return(list->id);
X    }
X}
X
X/*******************************************************************************
X** Get info of linked list.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    Out    int    *sd    singly or doubly linked
X**                (lSINGLY, lDOUBLY)
X**    Out    int    *cc    chain or cicular linked
X**                (lCHAIN, lCIRCULAR)
X**    Out    int    *n    number of nodes
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID
X*/
X#ifdef ANSI
Xint
XlInfo(int id, int *sd, int *cc, int *n)
X#else
Xint
XlInfo(id, sd, cc, n)
Xint    id, *sd, *cc, *n;
X#endif
X{
X    ListPtr    list;
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lInfo", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X
X        /* copy information */
X    *sd = list->sd;
X    *cc = list->cc;
X    *n = list->n;
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Sort a linked list.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    order    sorting order
X**                (lDESCENDING, lASCENDING)
X**    In    int    theory    sorting theory
X**                (lBUBBLE, lHEAP, lINSERT, lQUICK, lSELECTION)
X**    In    Func    func    number of nodes
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_ORDER, lWRONG_THEORY
X*/
X#ifdef ANSI
Xint lSort(int id, int order, int theory, Func func)
X#else
Xint
XlSort(id, order, theory, func)
Xint    id, order, theory;
XFunc    func;
X#endif
X{
X    int        node_n, i, s, f, k, where, j, cmp;
X    ListPtr        list;
X    NodePtr        temp, temp2, *array;
X    static int    set1[] = { lASCENDING, lDESCENDING },
X            set2[] = { lBUBBLE, lHEAP, lINSERT, lQUICK,
X                lSELECTION };
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lSort", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X    if (list->n == 0) {
X        lError("lSort", lEMPTY_LIST, id, 0, NULL);
X        return(lEMPTY_LIST);
X    }
X    if (intInSet(order, set1, 2) != 0) {
X        lError("lSort", lWRONG_ORDER, id, 0, NULL);
X        return(lWRONG_ORDER);
X    }
X    if (intInSet(theory, set2, 5) != 0) {
X        lError("lSort", lWRONG_THEORY, id, 0, NULL);
X        return(lWRONG_THEORY);
X    }
X
X    node_n = list->n;
X        /* allocate 1 extra so I can nave a null in it */
X    CALLOC(array, NodePtr, node_n+1);
X
X    list->current = list->first;
X    for (i=0; i<node_n && list->current != NULL ; i++) {
X        array[i] = list->current;
X        list->current = (list->current)->nxt;
X    }
X    array[node_n] = NULL;
X
X    switch (theory) {
X    case lBUBBLE: {
X        int    switched = 1;
X
X        for (i=0; i < node_n-1 && switched == 1; i++) {
X            switched = 0;
X            for (j=0; j < node_n-i-1; j++) {
X                cmp = (*func)(array[j]->data, array[j+1]->data);
X                if ((order == lASCENDING && cmp == l2LT1)
X                 || (order == lDESCENDING && cmp == l1LT2)) {
X                    temp = array[j];
X                    array[j] = array[j+1];
X                    array[j+1] = temp;
X
X                    switched = 1;
X                }
X            }
X        }
X        break;
X    } /* end of lBUBBLE */
X    case lHEAP:
X        for (i=1; i<node_n; i++) {
X            temp = array[i];
X
X            s = i;
X            f = (s-1)/2;
X            cmp = (*func)(array[f]->data, temp->data);
X            while (s > 0 && ((order == lASCENDING && cmp == l1LT2)
X             || (order == lDESCENDING && cmp == l2LT1))) {
X                array[s] = array[f];
X                s = f;
X                f = (s-1)/2;
X                cmp = (*func)(array[f]->data, temp->data);
X            }
X
X            array[s] = temp;
X        }
X        for (i=node_n-1; i>0; i--) {
X            temp = array[i];
X            array[i] = array[0];
X            f = 0;
X
X            if (i == 1)
X                s = -1;
X            else
X                s = 1;
X            cmp = (*func)(array[2]->data, array[1]->data);
X            if (i > 2 && ((order == lASCENDING && cmp == l2LT1)
X             || (order == lDESCENDING && cmp == l1LT2)))
X                s = 2;
X
X            if (s >= 0)
X                cmp = (*func)(temp->data, array[s]->data);
X            while (s >= 0 && ((order == lASCENDING && cmp == l1LT2)
X             || (order == lDESCENDING && cmp == l2LT1))) {
X                array[f] = array[s];
X                f = s;
X
X                s = 2*f+1;
X                if (s+1 <= i-1) {
X                    cmp = (*func)(array[s]->data,
X                        array[s+1]->data);
X                    if (cmp < 0)
X                        s = s+1;
X                }
X                if (s > i-1)
X                    s = -1;
X                if (s >= 0)
X                    cmp = (*func)(temp->data,
X                        array[s]->data);
X            }
X            array[f] = temp;
X        }
X        break;
X    case lINSERT:
X        for (i=1; i<node_n; i++) {
X            temp = array[i];
X            cmp = (*func)(temp->data, array[i-1]->data);
X            for (j=i-1; j>=0
X             && ((order == lASCENDING && cmp == l1LT2)
X             || (order == lDESCENDING && cmp == l2LT1)); j--) {
X                temp2 = array[j];
X                array[j] = array[j+1];
X                array[j+1] = temp2;
X                if (j > 0)
X                    cmp = (*func)(temp->data,
X                        array[j-1]->data);
X            }
X        }
X        break;
X    case lQUICK: {
X        struct bndtype {
X            int lb;
X            int ub;
X        }        newbnds;
X        int        newbndsSz = sizeof(struct bndtype),
X                stack = lDef(lDOUBLY, lCHAIN);
X
X        newbnds.lb = 0;
X        newbnds.ub = node_n-1;
X            /* basicly a push */
X        lInsNode(stack, lLAST, &newbnds, newbndsSz, 0);
X
X            /* repeat as long as there are any unsorted subarrays
X            ** on the stack */
X        while (!stack_empty(stack)) {
X                /* a pop */
X            lGetNode(stack, lCURRENT, &newbnds, newbndsSz);
X            lDelNode(stack, lCURRENT);
X            while (newbnds.ub > newbnds.lb) {
X                    /* process next sub array */
X                partition(array, order, (*func), newbnds.lb,
X                    newbnds.ub, &j);
X                    /* stack the larger subarray */
X                if (j-newbnds.lb > newbnds.ub-j) {
X                        /* stack lower subarray */
X                    i = newbnds.ub;
X                    newbnds.ub = j-1;
X                        /* basicly a push */
X                    lInsNode(stack, lLAST, &newbnds,
X                        newbndsSz, 0);
X                        /* process upper subarray */
X                    newbnds.lb = j+1;
X                    newbnds.ub = i;
X                } else {
X                        /* stack upper subarray */
X                    i = newbnds.lb;
X                    newbnds.lb = j+1;
X                        /* basicly a push */
X                    lInsNode(stack, lLAST, &newbnds,
X                        newbndsSz, 0);
X                        /* process lower subarray */
X                    newbnds.lb = i;
X                    newbnds.ub = j-1;
X                }
X            }
X        }
X        lDel(stack);
X        break;
X    } /* end of lQUICK */
X    case lSELECTION: {
X        int    indx;
X
X        for (i=node_n-1; i>0 ; i--) {
X            temp = array[0];
X            indx = 0;
X
X            for (j=1; j<=i; j++) {
X                cmp = (*func)(array[j]->data, temp->data);
X                if ((order == lASCENDING && cmp == l2LT1)
X                 || (order == lDESCENDING && cmp == l1LT2)) {
X                    temp = array[j];
X                    indx = j;
X                }
X            }
X            array[indx] = array[i];
X            array[i] = temp;
X        }
X        break;
X    } /* end of lSELECTION */
X    } /* end of switch */
X
X        /* init list to start and reset it */
X    list->first = array[0];
X    list->last = array[node_n-1];
X
X    list->current = list->first;
X    for (k=0; k<node_n; k++) {
X        if (k == 0)
X            where = lFIRST;
X        else if (k == node_n)
X            where = lLAST;
X        else
X            where = lNEXT;
X
X        switch (where) {
X        case lFIRST:
X            if (list->cc == lCIRCULAR)
X                (list->first)->prv = (list->last);
X
X            if (list->sd == lDOUBLY)
X                array[k]->prv = NULL;
X
X            array[k]->nxt = array[k+1];
X            break;
X
X        case lNEXT:
X            if (list->sd == lDOUBLY)
X                (list->first)->prv = array[k-1];
X
X            array[k]->nxt = array[k+1];
X            break;
X
X        case lLAST:
X            if (list->sd == lDOUBLY)
X                array[k]->prv = array[k-1];
X
X            if (list->cc == lCIRCULAR)
X                array[k]->nxt = list->first;
X            else
X                array[k]->nxt = NULL;
X            break;
X        }
X    }
X    FREE(array);
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Dump a linked list to a file.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    char    *file    name of linked list dump file
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lOPEN_ERROR
X**
X** File structure:
X**    <header> { <info> <data> }
X**    header.n    number of <info>-<data>-combinations (nodes)
X**    info.size    size of <data>
X*/
X#ifdef ANSI
Xint
XlDump(int id, char *file)
X#else
Xint
XlDump(id, file)
Xint    id;
Xchar    *file;
X#endif
X{
X#ifndef MSDOS
X    int    open(), creat(), write(), close();
X#endif
X
X    int    fdDump, i;
X    ListPtr    list;
X    NodePtr    node;
X    Info    info;
X    Header    header;
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lDump", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X
X    fdDump = open(file, BIN_WRITE);
X    if (fdDump == -1) {
X        fdDump = creat(file, PMODE);
X        if (fdDump == -1) {
X            lError("lDump", lOPEN_ERROR, 0, 0, file);
X            return(lOPEN_ERROR);
X        }
X    }
X
X    header.sd = list->sd;
X    header.cc = list->cc;
X    header.n = list->n;
X    write(fdDump, (char *) &header, sizeof(Header));
X
X    node = list->first;
X    for (i=0; i<header.n; i++) {
X        info.size = node->size;
X        info.flag = node->flag;
X        write(fdDump, (char *) &info, sizeof(Info));
X        write(fdDump, (char *) node->data, node->size);
X        node = node->nxt;
X    }
X
X    close(fdDump);
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Undump a linked list from a file.
X**
X** Parameters:
X**    In    char    *file    name of linked list dump file
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lOPEN_ERROR
X*/
X#ifdef ANSI
Xint
XlUndump(char *file)
X#else
Xint
XlUndump(file)
Xchar    *file;
X#endif
X{
X#ifndef MSDOS
X    int    open(), read(), close();
X#endif
X
X    int    fdDump, i, id;
X    Info    info;
X    Header    header;
X    Byte    *data;
X
X        /* check parameters */
X    fdDump = open(file, BIN_READ);
X    if (fdDump == -1) {
X        lError("lDump", lOPEN_ERROR, 0, 0, file);
X        return(lOPEN_ERROR);
X    }
X
X    read(fdDump, (char *) &header, sizeof(Header));
X    id = lDef(header.sd, header.cc);
X
X    for (i=0; i<header.n; i++) {
X        read(fdDump, (char *) &info, sizeof(Info));
X        CALLOC(data, Byte, info.size);
X        read(fdDump, (char *) data, info.size);
X        lInsNode(id, lLAST, data, info.size, info.flag);
X        FREE(data);
X    }
X
X    close(fdDump);
X
X    return(id);
X}
X
X/*******************************************************************************
X** Delete a linked list and clear info about it.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID
X*/
X#ifdef ANSI
Xint
XlDel(int id)
X#else
Xint
XlDel(id)
Xint    id;
X#endif
X{
X    ListPtr    list;
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lDel", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X
X        /* delete all nodes */
X    delNodes(list->first, list->n);
X        /* reset info as deleted linked list */
X    list->sd = list->cc = list->n = 0;
X    list->first = list->current = list->last = NULL;
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Delete all linked list and all info about those lists.
X**
X** No parameters.
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lNO_LIST
X*/
X#ifdef ANSI
Xint
XlDelAll(void)
X#else
Xint
XlDelAll()
X#endif
X{
X    ListPtr    list, nxt;
X
X    if (ld == NULL) {
X        lError("lDelAll", lNO_LIST, 0, 0, NULL);
X        return(lNO_LIST);
X    }
X
X    list = ld;
X    while (list != NULL) {
X        nxt = list->nxt;
X        if (list->sd != 0 && list->cc != 0)
X            lDel(list->id);    /* delete when not already deleted */
X        list = nxt;
X    }
X    delListInfo(ld->nxt);
X        /* save info of initial list */
X    firstlist.id = 1;
X    firstlist.sd = firstlist.cc = firstlist.n = 0;
X    firstlist.first = firstlist.current = firstlist.last = NULL;
X    firstlist.nxt = NULL;
X    ld = &firstlist;
X    idMax = 2;
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Insert a node in linked list.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    where    place where node must be inserted
X**                (lFIRST, lBEFORE, lAFTER, lLAST)
X**    In    Byte    *data    data of node
X**    In    int    size    size of data
X**    In    int    flag    user information flag
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lWRONG_WHERE
X*/
X#ifdef ANSI
Xint
XlInsNode(int id, int where, Byte *data, int size, int flag)
X#else
Xint
XlInsNode(id, where, data, size, flag)
Xint    id, where, size, flag;
XByte    *data;
X#endif
X{
X    ListPtr        list;
X    NodePtr        node, new;
X    static int    set[] = { lFIRST, lBEFORE, lAFTER, lLAST };
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lInsNode", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X    if (intInSet(where, set, 4) != 0) {
X        lError("lInsNode", lWRONG_WHERE, where, 0, NULL);
X        return(lWRONG_WHERE);
X    }
X
X        /* create new node */
X    MALLOC(new, ListNode);
X    CALLOC(new->data, Byte, size);
X    BYTE_COPY(data, new->data, size);
X    new->size = size;
X    new->flag = flag;
X
X        /* specific insert cases */
X    if (list->first == NULL)
X        where = lONE_NODE;    /* first node in list */
X    else if (list->current == list->first && where == lBEFORE)
X        where = lFIRST;        /* before first is like insert first */
X    else if (list->current == list->last && where == lAFTER)
X        where = lLAST;        /* after last is like insert last */
X
X    switch (where) {
X    case lONE_NODE:
X        if (list->cc == lCHAIN)
X            new->prv = new->nxt = NULL;
X        else {
X            if (list->sd == lDOUBLY)
X                new->prv = new;
X            else
X                new->prv = NULL;
X            new->nxt = new;
X        }
X        list->first = list->last = new;
X        break;
X    case lFIRST:
X        new->prv = (list->first)->prv;
X        new->nxt = list->first;
X        if (list->cc == lCIRCULAR)
X            (list->last)->nxt = new;
X        else
X            (list->last)->nxt = NULL;
X        if (list->sd == lDOUBLY)
X            (list->first)->prv = new;
X        list->first = new;
X        break;
X    case lBEFORE:
X        new->prv = (list->current)->prv;    /* == NULL if lSINGLY */
X        new->nxt = list->current;
X
X        if (list->sd == lDOUBLY) {
X            ((list->current)->prv)->nxt = new;
X            (list->current)->prv = new;
X        } else {
X            node = list->first;
X                /* search for last before current */
X            while (node->nxt != list->current && node != list->last)
X                node = node->nxt;
X            node->nxt = new;
X        }
X        if (list->current == list->first)
X            list->first = new;
X        break;
X    case lAFTER:
X        if (list->sd == lDOUBLY)
X            new->prv = list->current;
X        else
X            new->prv = NULL;
X        new->nxt = (list->current)->nxt;
X        if (list->sd == lDOUBLY) {
X            ((list->current)->nxt)->prv = new;
X            (list->current)->prv = new;
X        }
X        (list->current)->nxt = new;
X        if (list->current == list->last)
X            list->last = new;
X        break;
X    case lLAST:
X        node = list->last;
X        if (list->sd == lDOUBLY)
X            new->prv = node;
X        else
X            new->prv = NULL;
X        if (list->cc == lCIRCULAR)
X            new->nxt = list->first;
X        else
X            new->nxt = NULL;
X        if (list->sd == lDOUBLY && list->cc == lCIRCULAR)
X            (list->first)->prv = new;
X        node->nxt = new;
X        list->last = new;
X        break;
X    }
X
X    list->n++;
X    list->current = new;
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Get info of node of linked list.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    which    which node must be inspected
X**                (lFIRST, lPREVIOUS, lCURRENT, lNEXT, lLAST)
X**    Out    int    *size    size of data of node
X**    Out    int    *flag    user information flag
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, lEOL, lNOT_DOUBLY
X*/
X#ifdef ANSI
Xint
XlInfoNode(int id, int which, int *size, int *flag)
X#else
Xint
XlInfoNode(id, which, size, flag)
Xint    id, which, *size, *flag;
X#endif
X{
X    ListPtr    list;
X    int    rtrn;
X
X    rtrn = setWhchNode(id, which, "lInfoNode");
X    if (rtrn != lSUCCESS)    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, */
X        return(rtrn);    /* lEOL, lNOT_DOUBLY */
X
X    list = getAddress(id);    /* already checked in setWhchNode */
X
X        /* copy information */
X    *size = (list->current)->size;
X    *flag = (list->current)->flag;
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Get data of node.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    which    which node must be retrieved
X**                (lFIRST, lPREVIOUS, lCURRENT, lNEXT, lLAST)
X**    Out    Byte    *data    data of node
X**    In    int    size    size of data
X**
X** Return on success:
X**    lSUCCESS, lFIRST, lLAST
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, lEOL, lNOT_DOUBLY, lSIZE_NE
X*/
X#ifdef ANSI
Xint
XlGetNode(int id, int which, Byte *data, int size)
X#else
Xint
XlGetNode(id, which, data, size)
Xint    id, which, size;
XByte    *data;
X#endif
X{
X    ListPtr    list;
X    int    rtrn;
X
X    rtrn = setWhchNode(id, which, "lInfoNode");
X    if (rtrn != lSUCCESS)    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, */
X        return(rtrn);    /* lEOL, lNOT_DOUBLY */
X
X    list = getAddress(id);    /* already checked in setWhchNode */
X
X        /* expected data and node must have same size */
X    if ((list->current)->size != size) {
X        lError("lGetNode", lSIZE_NE, size, (list->current)->size, NULL);
X        return(lSIZE_NE);
X    }
X
X    BYTE_COPY((list->current)->data, data, size);
X
X    if (list->current == list->first)
X        return(lFIRST);
X    else if (list->current == list->last)
X        return(lLAST);
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Find node.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    where    from where must be searched
X**    In    Func    func    function for checking the data on conditions
X**    In    Byte    *ptr    data for comparison in function
X**    Out    Byte    *data    data of node
X**    In    int    size    size of data
X**
X** Return on success:
X**    lFOUND, lFIRST, lLAST, lNOT_FOUND
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHERE, lUNKNOWN_FUNC, lNOT_DOUBLY
X*/
X#ifdef ANSI
Xint
XlFndNode(int id, int where, Func func, Byte *ptr, Byte *data, int size)
X#else
Xint
XlFndNode(id, where, func, ptr, data, size)
Xint    id, where, size;
XFunc    func;
XByte    *ptr, *data;
X#endif
X{
X    NodePtr        node;
X    ListPtr        list;
X    int        cmp = lNOT_FOUND;
X    static int    set[] = { lFIRST, lNEXT, lPREVIOUS, lLAST };
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lFndNode", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X    if (list->n == 0) {
X        lError("lFndNode", lEMPTY_LIST, id, 0, NULL);
X        return(lEMPTY_LIST);
X    }
X    if (intInSet(where, set, 4) != 0) {
X        lError("lFndNode", lWRONG_WHERE, where, 0, NULL);
X        return(lWRONG_WHERE);
X    }
X    if (func == NULL) {
X        lError("lFndNode", lUNKNOWN_FUNC, (int) func, 0, NULL);
X        return(lUNKNOWN_FUNC);
X    }
X
X        /* set node for where searching must start */
X    switch (where) {
X    case lFIRST:    node = list->first;    break;
X    case lNEXT:
X    case lPREVIOUS:    node = list->current;    break;
X    case lLAST:    node = list->last;    break;
X    }
X
X        /* expected data and node must have same size */
X    if ((where == lFIRST || where == lLAST) && node->size == size) {
X        BYTE_COPY(node->data, data, size);
X        cmp = (*func)(ptr, data);
X    }
X
X    switch (where) {
X    case lFIRST:    /* search forward */
X    case lNEXT:
X        while (cmp != lFOUND && node->nxt != NULL
X         && node != list->last) {
X            node = node->nxt;
X                /* expected data and node must have same size */
X            if (node->size == size) {
X                BYTE_COPY(node->data, data, size);
X                cmp = (*func)(ptr, data);
X            }
X        }
X        if (cmp == lFOUND) {
X            list->current = node;
X            if (list->current == list->last)
X                return(lLAST);
X        }
X        break;
X    case lPREVIOUS:    /* search backward */
X    case lLAST:
X        if (list->sd != lDOUBLY && cmp == lNOT_FOUND) {
X            lError("lFndNode", lNOT_DOUBLY, id, 0, NULL);
X            return(lNOT_DOUBLY);
X        }
X        while (cmp != lFOUND && node->prv != NULL
X         && node->prv != list->first) {
X            node = node->prv;
X                /* expected data and node must have same size */
X            if (node->size == size) {
X                BYTE_COPY(node->data, data, size);
X                cmp = (*func)(ptr, data);
X            }
X        }
X        if (cmp == lFOUND) {
X            list->current = node;
X            if (list->current == list->first)
X                return(lFIRST);
X        }
X        break;
X    }
X
X    return(cmp);    /* lFOUND, lNOT_FOUND */
X}
X
X/*******************************************************************************
X** Get node by flag.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    flag    flag of node which must be retrieved
X**    Out    Byte    *data    data of node
X**    In    int    size    size of data
X**
X** Return on success:
X**    lFOUND, lFIRST, lLAST, lNOT_FOUND
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHERE, lSIZE_NE
X*/
X#ifdef ANSI
Xint
XlFndFlagNode(int id, int where, int flag, Byte *data, int size)
X#else
Xint
XlFndFlagNode(id, where, flag, data, size)
Xint    id, where, flag, size;
XByte    *data;
X#endif
X{
X    NodePtr        node;
X    ListPtr        list;
X    static int    set[] = { lFIRST, lNEXT, lPREVIOUS, lLAST };
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lFndFlagNode", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X    if (list->n == 0) {
X        lError("lFndFlagNode", lEMPTY_LIST, id, 0, NULL);
X        return(lEMPTY_LIST);
X    }
X    if (intInSet(where, set, 4) != 0) {
X        lError("lFndFlagNode", lWRONG_WHERE, where, 0, NULL);
X        return(lWRONG_WHERE);
X    }
X
X        /* set node for where searching must start */
X    switch (where) {
X    case lFIRST:
X        node = list->first;
X        break;
X    case lNEXT:
X        if ((list->current)->nxt == NULL)
X            return(lNOT_FOUND);    /* end of list reached */
X        node = (list->current)->nxt;
X        break;
X    case lPREVIOUS:
X        if ((list->current)->prv == NULL)
X            return(lNOT_FOUND);    /* begin of list reached */
X        node = (list->current)->prv;
X        break;
X    case lLAST:
X        node = list->last;
X        break;
X    }
X
X        /* search till begin/end of list */
X    switch (where) {
X    case lFIRST:    /* search forward */
X    case lNEXT:
X        while (node->flag != flag && node != list->last)
X            node = node->nxt;
X        break;
X    case lPREVIOUS:    /* search backward */
X    case lLAST:
X        if (list->sd != lDOUBLY) {
X            lError("lFndFlagNode", lNOT_DOUBLY, id, 0, NULL);
X            return(lNOT_DOUBLY);
X        }
X        while (node->flag != flag && node != list->first)
X            node = node->prv;
X        break;
X    }
X
X    list->current = node;
X
X        /* extra flag-check for last node of list */
X    if ((list->current)->flag != flag) {
X        lError("lFndFlagNode", lNOT_FOUND, id, 0, NULL);
X        return(lNOT_FOUND);
X    }
X
X        /* expected data and node must have same size */
X    if ((list->current)->size != size) {
X        lError("lFndFlagNode", lSIZE_NE, size, (list->current)->size,
X            NULL);
X        return(lSIZE_NE);
X    }
X
X    BYTE_COPY((list->current)->data, data, size);
X
X    if (list->current == list->first)
X        return(lFIRST);
X    else if (list->current == list->last)
X        return(lLAST);
X
X    return(lFOUND);
X}
X
X/*******************************************************************************
X** Update curent node.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    Byte    *data    updated data of node
X**    In    int    size    size of data
X**    In    int    flag    updated user information flag
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST
X*/
X#ifdef ANSI
Xint
XlUpdNode(int id, Byte *data, int size, int flag)
X#else
Xint
XlUpdNode(id, data, size, flag)
Xint    id, size, flag;
XByte    *data;
X#endif
X{
X    ListPtr    list;
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lUpdNode", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X    if (list->n == 0) {
X        lError("lUpdNode", lEMPTY_LIST, id, 0, NULL);
X        return(lEMPTY_LIST);
X    }
X
X        /* if same size, replace node by updated node */
X        /* if not same size, insert updated node on current place */
X    if ((list->current)->size != size) {
X        FREE((list->current)->data);
X        CALLOC((list->current)->data, Byte, size);
X        (list->current)->size = size;
X    }
X    (list->current)->flag = flag;
X    BYTE_COPY(data, (list->current)->data, size);
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Delete node.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    which    which node must be deleted
X**                (lFIRST, lCURRENT, lLAST)
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH
X*/
X#ifdef ANSI
Xint
XlDelNode(int id, int which)
X#else
Xint
XlDelNode(id, which)
Xint    id, which;
X#endif
X{
X    NodePtr        node, prv, nxt;
X    ListPtr        list;
X    static int    set[] = { lFIRST, lCURRENT, lLAST };
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError("lDelNode", lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X    if (list->n == 0) {
X        lError("lDelNode", lEMPTY_LIST, id, 0, NULL);
X        return(lEMPTY_LIST);
X    }
X    if (intInSet(which, set, 3) != 0) {
X        lError("lDelNode", lWRONG_WHICH, which, 0, NULL);
X        return(lWRONG_WHICH);
X    }
X
X        /* specific delete cases */
X    if (list->n == 1)
X        which = lONE_NODE;    /* one node in linked list */
X    else if (which == lCURRENT && list->first == list->current)
X        which = lFIRST;        /* current is also first node */
X    else if (which == lCURRENT && list->last == list->current)
X        which = lLAST;        /* current is also last node */
X
X    switch (which) {
X    case lONE_NODE:
X        node = list->first;
X        list->first = list->current = list->last = NULL;
X        break;
X    case lFIRST:
X        node = list->first;
X        nxt = node->nxt;
X        if (list->cc == lCIRCULAR) {
X            prv = list->last;
X            prv->nxt = nxt;
X        } else
X            prv = node->prv;    /* == NULL if lSINGLY */
X        if (list->sd == lDOUBLY)
X            nxt->prv = prv;
X        list->first = list->current = nxt;
X        break;
X    case lCURRENT:
X        node = list->current;
X        nxt = node->nxt;
X        if (list->sd == lDOUBLY) {
X            prv = node->prv;
X            nxt->prv = prv;
X        } else {
X            prv = node = list->first;
X            while (node != list->current) {
X                prv = node;
X                node = node->nxt;
X            }
X            if (prv == node)
X                prv = list->last;
X        }
X        prv->nxt = nxt;
X        list->current = nxt;
X        break;
X    case lLAST:
X        node = list->last;
X        if (list->sd == lDOUBLY)
X            prv = node->prv;
X        else {
X            if (list->current != list->last)
X                prv = node = list->current;
X            else
X                prv = node = list->first;
X            while (node != list->last) {
X                prv = node;
X                node = node->nxt;
X            }
X        }
X        nxt = node->nxt;
X        if (list->sd == lDOUBLY && list->cc == lCIRCULAR)
X            nxt->prv = prv;
X        prv->nxt = nxt;
X        list->last = list->current = prv;
X        break;
X    }
X
X    FREE(node->data);
X    FREE(node);
X    list->n--;
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Get information about node by index.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    index    index of node which must be inspected
X**    Out    int    *size    size of data of node
X**    Out    int    *flag    user information flag
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
X*/
X#ifdef ANSI
Xint
XlInfoIndxNode(int id, int index, int *size, int *flag)
X#else
Xint
XlInfoIndxNode(id, index, size, flag)
Xint    id, index, *size, *flag;
X#endif
X{
X    ListPtr    list;
X    int    rtrn;
X
X    rtrn = setIndxNode(id, index, "lInfoIndxNode");
X    if (rtrn != lSUCCESS)
X        return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
X
X    list = getAddress(id);    /* already checked in setIndxNode */
X
X        /* copy information */
X    *size = (list->current)->size;
X    *flag = (list->current)->flag;
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Get node by index.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    index    index of node which must be retrieved
X**    Out    Byte    *data    data of node
X**    In    int    size    size of data
X**
X** Return on success:
X**    lSUCCESS, lFIRST, lLAST
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX, lSIZE_NE
X*/
X#ifdef ANSI
Xint
XlGetIndxNode(int id, int index, Byte *data, int size)
X#else
Xint
XlGetIndxNode(id, index, data, size)
Xint    id, index, size;
XByte    *data;
X#endif
X{
X    ListPtr    list;
X    int    rtrn;
X
X    rtrn = setIndxNode(id, index, "lGetIndxNode");
X    if (rtrn != lSUCCESS)
X        return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
X
X    list = getAddress(id);    /* already checked in setIndxNode */
X
X        /* expected data and node must have same size */
X    if ((list->current)->size != size) {
X        lError("lGetIndxNode", lSIZE_NE, size, (list->current)->size,
X            NULL);
X        return(lSIZE_NE);
X    }
X
X    BYTE_COPY((list->current)->data, data, size);
X
X    if (list->current == list->first)
X        return(lFIRST);
X    else if (list->current == list->last)
X        return(lLAST);
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Update node by index.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    index    index of node which must be updated
X**    In    Byte    *data    updated data of node
X**    In    int    size    size of data
X**    In    int    flag    updated user information flag
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
X*/
X#ifdef ANSI
Xint
XlUpdIndxNode(int id, int index, Byte *data, int size, int flag)
X#else
Xint
XlUpdIndxNode(id, index, data, size, flag)
Xint    id, index, size, flag;
XByte    *data;
X#endif
X{
X    ListPtr    list;
X    int    rtrn;
X
X    rtrn = setIndxNode(id, index, "lUpdIndxNode");
X    if (rtrn != lSUCCESS)
X        return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
X
X    list = getAddress(id);    /* already checked in setIndxNode */
X
X        /* if same size, replace node by updated node */
X        /* if not same size, insert updated node on current place */
X    if ((list->current)->size != size) {
X        FREE((list->current)->data);
X        CALLOC((list->current)->data, Byte, size);
X        (list->current)->size = size;
X    }
X    (list->current)->flag = flag;
X    BYTE_COPY(data, (list->current)->data, size);
X
X    return(lSUCCESS);
X}
X
X/*******************************************************************************
X** Delete node by index.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**    In    int    index    index of node which must be deleted
X**
X** Return on success:
X**    lSUCCESS
X** Return on error:
X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
X*/
X#ifdef ANSI
Xint
XlDelIndxNode(int id, int index)
X#else
Xint
XlDelIndxNode(id, index)
Xint    id, index;
X#endif
X{
X    int    rtrn;
X
X    rtrn = setIndxNode(id, index, "lDelIndxNode");
X    if (rtrn != lSUCCESS)
X        return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
X
X    return(lDelNode(id, lCURRENT));    /* lSUCCESS */
X}
X
X/* ---------- static local functions ---------------------------------------- */
X
X/* get address of list data */
X#ifdef ANSI
Xstatic ListPtr
XgetAddress(int id)
X#else
Xstatic ListPtr
XgetAddress(id)
Xint    id;
X#endif
X{
X    ListPtr    list;
X
X    list = ld;
X    while (list != NULL && list->id != id)
X        list = list->nxt;
X
X    if (list == NULL)
X        return(NULL);    /* id not found */
X
X    if (list->sd == 0 && list->cc == 0)    /* deleted linked list */
X        return(NULL);    /* deleted linked list */
X
X    return(list);
X}
X
X/* delete nodes of a linked list */
X#ifdef ANSI
Xstatic void
XdelNodes(NodePtr node, int n)
X#else
Xstatic void
XdelNodes(node, n)
XNodePtr    node;
Xint    n;
X#endif
X{
X    NodePtr    nxt;
X    int    i;
X
X    for (i=0; i<n; i++) {
X        nxt = node->nxt;
X        FREE(node->data);
X        FREE(node);
X        node = nxt;
X    }
X}
X
X/* delete info about linked list */
X#ifdef ANSI
Xstatic void
XdelListInfo(ListPtr list)
X#else
Xstatic void
XdelListInfo(list)
XListPtr    list;
X#endif
X{
X    ListPtr    nxt;
X
X    while (list != NULL) {
X        nxt = list->nxt;
X        FREE(list);
X        list = nxt;
X    }
X}
X
X/* print error message in lERROR_FILE */
X#ifdef ANSI
Xstatic void
XlError(char *str, int code, int int1, int int2, char *str1)
X#else
Xstatic void
XlError(str, code, int1, int2, str1)
Xchar    *str, *str1;
Xint    code, int1, int2;
X#endif
X{
X#ifndef MSDOS
X    char    mess[60];
X    FILE    *fpError, *fopen();
X
X    switch (code) {
X    case lWRONG_SD:
X        sprintf(mess, "Parameter 'sd' has wrong value : %d", int1);
X        break;
X    case lWRONG_CC:
X        sprintf(mess, "Parameter 'cc' has wrong value : %d", int1);
X        break;
X    case lWRONG_WHERE:
X        sprintf(mess, "Parameter 'where' has wrong value : %d", int1);
X        break;
X    case lWRONG_WHICH:
X        sprintf(mess, "Parameter 'which' has wrong value : %d", int1);
X        break;
X    case lUNKNOWN_ID:
X        sprintf(mess, "List id '%d' is unknown", int1);
X        break;
X    case lUNKNOWN_FUNC:
X        sprintf(mess, "Function '%d' is unknown", int1);
X        break;
X    case lNO_LIST:
X        sprintf(mess, "There are no lists defined");
X        break;
X    case lEMPTY_LIST:
X#ifdef DEBUG
X        sprintf(mess, "List '%d' is empty", int1);
X        break;
X#else
X        return;
X#endif
X    case lEOL:
X#ifdef DEBUG
X        sprintf(mess, "End of list '%d' reached", int1);
X        break;
X#else
X        return;
X#endif
X    case lNOT_FOUND:
X#ifdef DEBUG
X        sprintf(mess, "Node not found in list '%d'", int1);
X        break;
X#else
X        return;
X#endif
X    case lNOT_DOUBLY:
X        sprintf(mess, "List '%d' is not doubly linked", int1);
X        break;
X    case lSIZE_NE:
X        sprintf(mess,
X            "Size of expected data '%d' and node '%d' not equal",
X            int1, int2);
X        break;
X    case lWRONG_INDEX:
X        sprintf(mess, "Index '%d' out of range [1:%d]", int1, int2);
X        break;
X    case lOPEN_ERROR:
X        sprintf(mess, "Can't open dump-file '%s'\n", str1);
X        break;
X    case lWRONG_ORDER:
X        sprintf(mess, "Parameter 'order' has wrong value : %d", int1);
X        break;
X    case lWRONG_THEORY:
X        sprintf(mess, "Parameter 'theory' has wrong value : %d", int1);
X        break;
X    }
X
X    fpError = fopen(lERROR_FILE, "a");
X    if (fpError == NULL) {
X        fprintf(stderr, "Can't open error-file '%s'\n", lERROR_FILE);
X        fprintf(stderr, "Error, '%s': %s\n", str, mess);
X    } else {
X        fprintf(fpError, "Error, '%s': %s\n", str, mess);
X        fclose(fpError);
X    }
X#endif
X}
X
X#ifdef ANSI
Xstatic int
XsetWhchNode(int id, int which, char *fname)
X#else
Xstatic int
XsetWhchNode(id, which, fname)
Xint    id, which;
Xchar    *fname;
X#endif
X{
X    ListPtr        list;
X    static int    set[] = { lFIRST, lNEXT, lCURRENT, lPREVIOUS, lLAST };
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError(fname, lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X    if (list->n == 0) {
X        lError(fname, lEMPTY_LIST, id, 0, NULL);
X        return(lEMPTY_LIST);
X    }
X    if (intInSet(which, set, 5) != 0) {
X        lError(fname, lWRONG_WHICH, which, 0, NULL);
X        return(lWRONG_WHICH);
X    }
X
X        /* search for requested node */
X    switch (which) {
X    case lFIRST:
X        list->current = list->first;
X        break;
X    case lNEXT:
X        if ((list->current)->nxt == NULL) {
X            lError(fname, lEOL, id, 0, NULL);
X            return(lEOL);
X        }
X        list->current = (list->current)->nxt;
X        break;
X    case lCURRENT:
X        break;
X    case lPREVIOUS:
X        if (list->sd != lDOUBLY) {
X            lError(fname, lNOT_DOUBLY, id, 0, NULL);
X            return(lNOT_DOUBLY);
X        }
X        if ((list->current)->prv == NULL) {
X            lError(fname, lEOL, id, 0, NULL);
X            return(lEOL);
X        }
X        list->current = (list->current)->prv;
X        break;
X    case lLAST:
X        list->current = list->last;
X        break;
X    }
X
X    return(lSUCCESS);
X}
X
X#ifdef ANSI
Xstatic int
XsetIndxNode(int id, int index, char *fname)
X#else
Xstatic int
XsetIndxNode(id, index, fname)
Xint    id, index;
Xchar    *fname;
X#endif
X{
X    ListPtr    list;
X    int    i;
X
X        /* check parameters */
X    if ((list = getAddress(id)) == NULL) {
X        lError(fname, lUNKNOWN_ID, id, 0, NULL);
X        return(lUNKNOWN_ID);
X    }
X    if (list->n == 0) {
X        lError(fname, lEMPTY_LIST, id, 0, NULL);
X        return(lEMPTY_LIST);
X    }
X    if (index < 1 || list->n < index) {
X        lError(fname, lWRONG_INDEX, index, list->n, NULL);
X        return(lWRONG_INDEX);
X    }
X
X    if (index == 1)
X        list->current = list->first;
X    else if (index == list->n)
X        list->current = list->last;
X    else {
X        list->current = list->first;
X        for (i=1; i<index; i++)
X            list->current = (list->current)->nxt;
X    }
X
X    return(lSUCCESS);
X}
X
X/* local function for QUICK sort */
X#ifdef ANSI
Xstatic int
Xpartition(NodePtr *array, int order, Func func, int lb, int ub, int *pj)
X#else
Xstatic int
Xpartition(array, order, func, lb, ub, pj)
XNodePtr    *array;
Xint    order, lb, ub, *pj;
XFunc    func;
X#endif
X{
X    int    down, up, cmp;
X    NodePtr    temp, a;
X
X    a = array[lb];
X    up = ub;
X    down = lb;
X
X    while (down < up) {
X        cmp = (*func)(array[down]->data, a->data);
X        while (down < ub
X         && ((order == lASCENDING && (cmp == l1LT2 || cmp == lSAME))
X         || (order == lDESCENDING && (cmp == l2LT1 || cmp == lSAME)))) {
X            down++;
X            cmp = (*func)(array[down]->data, a->data);
X        }
X        cmp = (*func)(array[up]->data, a->data);
X        while ((order == lASCENDING && cmp == l2LT1)
X         || (order == lDESCENDING && cmp == l1LT2)) {
X            up--;
X            cmp = (*func)(array[up]->data, a->data);
X        }
X
X        if (down < up) {    /* interchange */
X            temp = array[down];
X            array[down] = array[up];
X            array[up] = temp;
X        }
X    }
X    array[lb] = array[up];
X    array[up] = a;
X    *pj = up;
X}
X
X/* local function for QUICK sort */
X#ifdef ANSI
Xstatic int
Xstack_empty(int id)
X#else
Xstatic int
Xstack_empty(id)
Xint    id;
X#endif
X{
X    int    sd, cc, n;
X
X        /* check to see if linked list exists */
X    if (lInfo(id, &sd, &cc, &n) == lUNKNOWN_ID)
X        return(1);    /* linked list is non-existant */
X    if (n == 0)
X        return(1);
X    return(0);
X}
X
X/* ---------- static local functions (~anita/Tools/Clib) -------------------- */
X
X/* check if integer belongs to set of integers */
Xstatic int
XintInSet(intgr, set, set_n)
Xint    intgr, *set, set_n;
X{
X    int    i = 0;
X
X    while (set[i] != intgr && i < set_n)
X        i++;
X
X        /* 0 = yes, 1 = no */
X    return((i == set_n) ? 1 : 0);
X}
END_OF_FILE
  if test 40715 -ne `wc -c <'list.c'`; then
    echo shar: \"'list.c'\" unpacked with wrong size!
  fi
  # end of 'list.c'
fi
if test -f 'sorted.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'sorted.c'\"
else
  echo shar: Extracting \"'sorted.c'\" \(7970 characters\)
  sed "s/^X//" >'sorted.c' <<'END_OF_FILE'
X#include    <stdio.h>
X#include    <string.h>
X#include    "list.h"
X
Xstatic void    addPersonSorted(), addPerson();
Xstatic int    fndNxtPerson(), sortPerson(), compare();
X
Xtypedef struct person {
X    char    lastname[15];
X    char    firstname[15];
X} Person, *PersonPtr;
Xint    personSz = sizeof(Person);
X
Xmain()
X{
X    Person    person;
X    int    id, code;
X
X/* ------- first solution --------------------------------------------------- */
Xfprintf(stdout, "..... Insert sorted by last name .....\n");
X    id = lDef(lSINGLY, lCHAIN);
X    addPersonSorted(id, "Ernie", "Makris");
X    addPersonSorted(id, "Anita", "Eijs");
X    addPersonSorted(id, "John", "Johnson");
X    addPersonSorted(id, "Bart", "Simpson");
X    addPersonSorted(id, "James", "Bond");
X    addPersonSorted(id, "Al", "Bundy");
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X    code = lDel(id);
X
X/* ------- second solution -------------------------------------------------- */
Xfprintf(stdout, "..... Insert unsorted .....\n");
X    id = lDef(lSINGLY, lCHAIN);
X    addPerson(id, "Ernie", "Makris");
X    addPerson(id, "Anita", "Eijs");
X    addPerson(id, "John", "Johnson");
X    addPerson(id, "Bart", "Simpson");
X    addPerson(id, "James", "Bond");
X    addPerson(id, "Al", "Bundy");
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name .....\n");
X    id = sortPerson(id);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
X    code = lDel(id);
X
X/* ------- third solution --------------------------------------------------- */
Xfprintf(stdout, "..... Insert unsorted .....\n");
X    id = lDef(lSINGLY, lCHAIN);
X    addPerson(id, "Ernie", "Makris");
X    addPerson(id, "Anita", "Eijs");
X    addPerson(id, "John", "Johnson");
X    addPerson(id, "Bart", "Simpson");
X    addPerson(id, "James", "Bond");
X    addPerson(id, "Al", "Bundy");
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Bubble ASCENDING .....\n");
X    code = lSort(id, lASCENDING, lBUBBLE, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Bubble DESCENDING .....\n");
X    code = lSort(id, lDESCENDING, lBUBBLE, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Heap ASCENDING .....\n");
X    code = lSort(id, lASCENDING, lHEAP, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Heap DESCENDING .....\n");
X    code = lSort(id, lDESCENDING, lHEAP, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Insert ASCENDING .....\n");
X    code = lSort(id, lASCENDING, lINSERT, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Insert DESCENDING .....\n");
X    code = lSort(id, lDESCENDING, lINSERT, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Quick ASCENDING .....\n");
X    code = lSort(id, lASCENDING, lQUICK, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Quick DESCENDING .....\n");
X    code = lSort(id, lDESCENDING, lQUICK, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Selection ASCENDING .....\n");
X    code = lSort(id, lASCENDING, lSELECTION, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
Xfprintf(stdout, "..... Sort by last name ..... Selection DESCENDING .....\n");
X    code = lSort(id, lDESCENDING, lSELECTION, compare);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X
X    code = lDel(id);
X}
X
Xstatic void
XaddPersonSorted(id, first, last)
Xint    id;
Xchar    *first, *last;
X{
X    Person    person, new;
X    char    tmp[15];
X    int    code;
X
X        /* find next last name */
X    strcpy(&tmp[0], last);
X    code = lFndNode(id, lFIRST, fndNxtPerson, &tmp[0], &person, personSz);
X
X    strcpy(new.lastname, last);
X    strcpy(new.firstname, first);
X
X        /* insert data in alphabetical order */
X    if (code == lEMPTY_LIST || code == lFIRST)
X        code = lInsNode(id, lFIRST, &new, personSz, 0);
X    else if (code == lNOT_FOUND)
X        code = lInsNode(id, lLAST, &new, personSz, 0);
X    else
X        code = lInsNode(id, lBEFORE, &new, personSz, 0);
X}
X
X/* find next by specified last name before which specified name must be */
X/* inserted (alphabetical order) */
Xstatic int
Xcompare(p1, p2, order)
XPersonPtr    p1, p2;
Xint        order;
X{
X    int    k = strcmp(p1->lastname, p2->lastname);
X
X    if (k == 0)
X        return(lSAME);
X    else if (k > 0)
X        return(l2LT1);
X    else if (k < 0)
X        return(l1LT2);
X}
X
X/* find next by specified last name before which specified name must be */
X/* inserted (alphabetical order) */
Xstatic int
XfndNxtPerson(last, data)
Xchar        *last;
XPersonPtr    data;
X{
X    if (strcmp(last, data->lastname) < 0)
X        return(lFOUND);
X    else
X        return(lNOT_FOUND);
X}
X
Xstatic void
XaddPerson(id, first, last)
Xint    id;
Xchar    *first, *last;
X{
X    Person    new;
X    int    code;
X
X    strcpy(new.lastname, last);
X    strcpy(new.firstname, first);
X    code = lInsNode(id, lLAST, &new, personSz, 0);
X}
X
Xstatic int
XsortPerson(id)
Xint    id;
X{
X    Person    person, next;
X    char    tmp[15];
X    int    code, id2;
X
X    id2 = lDef(lSINGLY, lCHAIN);
X
X    code = lGetNode(id, lFIRST, &person, personSz);
X    while (code != lEOL && code != lEMPTY_LIST) {
X
X            /* find next last name */
X        strcpy(&tmp[0], person.lastname);
X        code = lFndNode(id2, lFIRST, fndNxtPerson, &tmp[0], &next,
X            personSz);
X
X            /* insert data in alphabetical order */
X        if (code == lEMPTY_LIST || code == lFIRST)
X            code = lInsNode(id2, lFIRST, &person, personSz, 0);
X        else if (code == lNOT_FOUND)
X            code = lInsNode(id2, lLAST, &person, personSz, 0);
X        else
X            code = lInsNode(id2, lBEFORE, &person, personSz, 0);
X
X        code = lGetNode(id, lNEXT, &person, personSz);
X    }
X    code = lDel(id);
X    return(id2);
X}
END_OF_FILE
  if test 7970 -ne `wc -c <'sorted.c'`; then
    echo shar: \"'sorted.c'\" unpacked with wrong size!
  fi
  # end of 'sorted.c'
fi
echo shar: End of archive 1 \(of 2\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked both archives.
    rm -f ark[1-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...