Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume38/linkedlist/part01

Text File | 1993-08-12 | 64KB | 2,531 lines

Newsgroups: comp.sources.misc
From: [e-mail] (Anita Eijs)
Subject: v38i117:  linkedlist - Generic Linked List Package, Part01/02
Message-ID: <csm-v38i117=[e-mail]>
X-Md4-Signature: efd03753dbd25f67c85d0dd22c51fcc8
Sender: [e-mail] (Kent Landfield)
Organization: Sterling Software
Date: Thu, 12 Aug 1993 14:17:28 GMT
Approved: [e-mail]

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

LinkedList Version: 0.10, August 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
    lSize        get number of nodes of 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 Doc/lGetNode.3 example.c list.c sorted.c
# Wrapped by kent@sparky on Thu Aug 12 09:13:07 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'\" \(2301 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.10, August 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/lSize.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.BCC        - some additional info about Borland port
X    Makefile.Amiga        - Amiga SAS C 6.0 Makefile
X    ReadMe.Amiga        - some additional info about Amiga port
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. (Skip symbol define ERROR_FILE from CFLAGS.)
X
X2)    Check the environment settings (RANLIB) in the Tools_makerule.
X
X3)    Be sure that the LIB-directory is created.
X
X4)    Enter 'make newlib' at the UNIX prompt.
X
X5)    Enter 'make test' or 'make example' to create the executable of
X    the program 'example' at the UNIX prompt.
X
X
XThe Generic Linked List package is also ported to MSDOS, VAX-VMS, Macintosh
Xand Amiga. On those machines the library was not created, but the source-
Xfiles list.c and list.h were treated the same as all the other source-files
X(*.[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 the files :
X    /pub/TNO/BOUW/Bouwinf/linkedlist_0.10.README
X    /pub/TNO/BOUW/Bouwinf/linkedlist_0.10.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 2301 -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 'Doc/lGetNode.3' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'Doc/lGetNode.3'\"
else
  echo shar: Extracting \"'Doc/lGetNode.3'\" \(1402 characters\)
  sed "s/^X//" >'Doc/lGetNode.3' <<'END_OF_FILE'
X'.so tmac.clman
X.TH "lGetNode"
X.IX lGetNode
X.SH NAME
XlGetNode - Get node.
X.SH SYNOPSIS
Xint
X.BR "lGetNode" "(id, which, data, size)"
X.br
X.RT
X.RP
XIn    int    id    identifier of linked list
X.RP
XIn    int    which    which node must be retrieved
X.RP
XOut    Byte    *data    data of node
X.RP
XIn    int    size    size of data
X.DT
X.SH DESCRIPTION
X\fBlGetNode\fP gets the data of a node of a linked list. Which node must
Xbe retrieved can be specified by \fIwhich\fP. The first node, the current
Xnode, the node before or after the current node and the node at the end
Xof the list can be retrieved.
X.br
XBackward retrieving is only possible for doubly linked list. A previous
Xnode can't be retrieved for singly linked lists.
X.br
XWhen the retrieved node is the first or the last node, the return code
Xwill have the value lFIRST or lLAST. For the other nodes the routine
Xreturns lSUCCESS.
XWhen the linked list contains only one node, the return code will have
Xthe value lFIRST, when retrieving backward, and the value lLAST, when
Xretrieving forward.
X.SH PARAMETER DEFINITIONS
X.if t .ta 0.2i 1.5i
X\fIwhich\fP :
X.nf
X    lFIRST    first node
X    lPREVIOUS    previous node
X    lCURRENT    current node
X    lNEXT    next node
X    lLAST    last node
X.fi
X.SH RETURN CODES
X.nf
XReturn on success :
X    lSUCCESS, lFIRST, lLAST
XReturn on error :
X.fi
X.in +0.2i
XlUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, lEOL, lSIZE_NE, lNOT_DOUBLY
X.in -0.2i
X.SH AUTHOR
XAnita Eijs (TNO - Bouw - BouwInformatica)
END_OF_FILE
  if test 1402 -ne `wc -c <'Doc/lGetNode.3'`; then
    echo shar: \"'Doc/lGetNode.3'\" unpacked with wrong size!
  fi
  # end of 'Doc/lGetNode.3'
fi
if test -f 'example.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'example.c'\"
else
  echo shar: Extracting \"'example.c'\" \(3536 characters\)
  sed "s/^X//" >'example.c' <<'END_OF_FILE'
X#ifdef    AMIGA
X#include        <string.h>
X#endif
X
X#include        <stdio.h>
X#include        "list.h"
X
Xtypedef struct rapport {
X    char        title[30];
X    char        author[15];
X    int        date;
X} Rapport;
Xint    rapSz = sizeof(Rapport);
X
X#ifdef ANSI
Xstatic void    insRap(int id, int where, int flag, char *title, char *author,
X                int date);
Xstatic void    prRapAll(int id);
Xstatic void    prRap(int code, Rapport *rpprt);
Xstatic int    search(int *date, Rapport *rpprt);
Xstatic int    compare(Rapport *data1, Rapport *data2);
X#else
Xstatic void    insRap(), prRapAll(), prRap();
Xstatic int    search(), compare();
X#endif
X
Xint
Xmain()
X{
X    int            id, code, search_date;
X    Rapport        rap;
X
X    id = lDef(lSINGLY, lCHAIN);
X
X    insRap(id, lFIRST, 1, "Book 1", "People", 890129);
X    insRap(id, lFIRST, 2, "Book 2", "More People", 890130);
X    insRap(id, lLAST, 1, "Book 3", "Lots of People", 890131);
X
X    fprintf(stdout, "lGetNode\n");
X    prRapAll(id);
X
X/*
X** The following routine calls will generate the file '=listError='.
X*/
X    fprintf(stdout, "lGetIndxNode\n");
X    code = lGetIndxNode(id, 4, &rap, rapSz);
X    prRap(code, &rap);
X    code = lGetIndxNode(id, 2, &rap, rapSz);
X    prRap(code, &rap);
X    code = lGetIndxNode(id, -1, &rap, rapSz);
X    prRap(code, &rap);
X    code = lGetIndxNode(id, 3, &rap, rapSz);
X    prRap(code, &rap);
X
X    fprintf(stdout, "lFndNode\n");
X    search_date = 890129;
X    code = lFndNode(id, lFIRST, search, &search_date, &rap, rapSz);
X    prRap(code, &rap);
X    code = lFndNode(id, lNEXT, search, &search_date, &rap, rapSz);
X    prRap(code, &rap);
X    code = lFndNode(id, lNEXT, search, &search_date, &rap, rapSz);
X    prRap(code, &rap);
X
X/*
X** The following routine call will generate the binary file 'dump'.
X*/
X    code = lDump(id, "dump");
X    fprintf(stdout, "lDump : %d\n", code);
X
X    lDel(id);
X
X    id = lUndump("dump");
X    fprintf(stdout, "lUndump : %d\n", id);
X
X    insRap(id, lFIRST, 4, "Book 4", "The Author", 891127);
X
X    prRapAll(id);
X
X    fprintf(stdout, "lFndFlagNode\n");
X    code = lFndFlagNode(id, lFIRST, 1, &rap, rapSz);
X    prRap(code, &rap);
X    code = lFndFlagNode(id, lNEXT, 1, &rap, rapSz);
X    prRap(code, &rap);
X    code = lFndFlagNode(id, lFIRST, 2, &rap, rapSz);
X    prRap(code, &rap);
X    code = lFndFlagNode(id, lFIRST, 7, &rap, rapSz);
X    prRap(code, &rap);
X
X    fprintf(stdout, "Untouched list\n");
X    prRapAll(id);
X
X    fprintf(stdout, "lSort\n");
X    lSort(id, lDESCENDING, lBUBBLE, compare);
X    prRapAll(id);
X
X    fprintf(stdout, "lSort\n");
X    lSort(id, lASCENDING, lHEAP, compare);
X    prRapAll(id);
X
X    lDelAll();
X}
X
Xstatic void
XinsRap(id, where, flag, title, author, date)
Xint        id, where, flag, date;
Xchar        *title, *author;
X{
X    int        code;
X    Rapport    rap;
X
X    strcpy(rap.title, title);
X    strcpy(rap.author, author);
X    rap.date = date;
X    code = lInsNode(id, where, &rap, rapSz, flag);
X}
X
Xstatic void
XprRapAll(id)
Xint    id;
X{
X    int        code;
X    Rapport    rap;
X
X    code = lGetNode(id, lFIRST, &rap, rapSz);
X    prRap(code, &rap);
X    while (code == lFIRST || code == lSUCCESS || code == lLAST) {
X        code = lGetNode(id, lNEXT, &rap, rapSz);
X        prRap(code, &rap);
X    }
X}
X
Xstatic void
XprRap(code, rpprt)
Xint            code;
XRapport        *rpprt;
X{
X    if (code >= 0)
X        fprintf(stdout, "Rapport : '%s' '%s' '%d'\n", rpprt->title,
X            rpprt->author, rpprt->date);
X    else
X        fprintf(stdout, "Return code = %d\n", code);
X}
X
Xstatic int
Xsearch(date, rpprt)
Xint            *date;
XRapport        *rpprt;
X{
X    if (rpprt->date > *date)
X        return(lFOUND);
X    else
X        return(lNOT_FOUND);
X}
X
Xstatic int
Xcompare(data1, data2)
XRapport *data1, *data2;
X{
X    int    k = strcmp(data1->author, data2->author);
X
X    if (k == 0)
X        return(lSAME);    /* key1 == key2 */
X    else if (k > 0)
X        return(l2LT1);    /* key1 > key2 */
X    else if (k < 0)
X        return(l1LT2);    /* key1 < key2 */
X}
END_OF_FILE
  if test 3536 -ne `wc -c <'example.c'`; then
    echo shar: \"'example.c'\" unpacked with wrong size!
  fi
  # end of 'example.c'
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'\" \(40617 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**    ***** Version 0.9, June 1993 *****
X**
X**    930801    New routine:
X**            lSize    Get number of nodes in linked list.
X**
X**    ***** Version 0.10, August 1993 *****
X**
X*/
X
X#ifdef __MSDOS__
X#define    MSDOS
X#define    ANSI
X#endif
X
X#ifdef UNIX
X#include    <malloc.h>
X#endif
X
X#ifdef MSDOS
X#include    <malloc.h>
X#include    <io.h>        /* open, creat, write, read, close */
X    /* added for Borland or other MSDOS C compilers */
X#include    <stdlib.h>
X#include    <fcntl.h>
X#include    <sys\types.h>
X#include    <sys\stat.h>
X#include    <string.h>
X#endif
X
X#ifdef VAXC
X#include    <stdlib.h>
X#endif
X
X#ifdef MAC
X#include    <unix.h>    /* open, creat, write, read, close */
X#include    <stddef.h>    /* sizeof */
X#include    <stdlib.h>
X#endif
X
X#ifdef AMIGA
X#include    <stdlib.h>
X#include    <fcntl.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        return(lOUT_OF_MEMORY); \
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        return(lOUT_OF_MEMORY); \
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    /* necessary for binary file access */
X#ifdef MSDOS
X#define    BIN_WRITE    O_WRONLY|O_BINARY
X#define    BIN_READ    O_RDONLY|O_BINARY
X#define    PMODE        S_IREAD
X#else
X#define    BIN_WRITE    1
X#define    BIN_READ    0
X#define    PMODE        0666
X#endif
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 void    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 void    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*/
Xint
XlDef(sd, cc)
Xint    sd, cc;
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*/
Xint
XlInfo(id, sd, cc, n)
Xint    id, *sd, *cc, *n;
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** Get number of nodes in linked list.
X**
X** Parameters:
X**    In    int    id    identifier of linked list
X**
X** Return on success:
X**    number of nodes
X** Return on error:
X**    lUNKNOWN_ID
X*/
Xint
XlSize(id)
Xint    id;
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    return(list->n);
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*/
Xint
XlSort(id, order, theory, func)
Xint    id, order, theory;
XFunc    func;
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        /* one node is already sorted */
X    if (list->n == 1)
X        return(lSUCCESS);
X
X    node_n = list->n;
X        /* allocate 1 extra so I can have 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            if (i > 2) {
X                cmp = (*func)(array[2]->data, array[1]->data);
X                if ((order == lASCENDING && cmp == l2LT1)
X                 || (order == lDESCENDING && cmp == l1LT2))
X                    s = 2;
X            }
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 ((order == lASCENDING
X                        && cmp == l1LT2) ||
X                     (order == lDESCENDING
X                        && cmp == l2LT1))
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*/
Xint
XlDump(id, file)
Xint    id;
Xchar    *file;
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*/
Xint
XlUndump(file)
Xchar    *file;
X{
X#ifndef MSDOS
X#ifndef AMIGA
X    int    open(), read(), close();
X#endif
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*/
Xint
XlDel(id)
Xint    id;
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*/
Xint
XlDelAll()
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*/
Xint
XlInsNode(id, where, data, size, flag)
Xint    id, where, size, flag;
XByte    *data;
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)->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*/
Xint
XlInfoNode(id, which, size, flag)
Xint    id, which, *size, *flag;
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*/
Xint
XlGetNode(id, which, data, size)
Xint    id, which, size;
XByte    *data;
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->n == 1) {
X        if (which == lPREVIOUS || which == lLAST)
X            return(lFIRST);
X        else if (which == lNEXT || which == lFIRST)
X            return(lLAST);
X        else
X            return(lLAST);    /* which == lCURRENT */
X    } else 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    which    from which node must be searched and in which
X**                direction
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_WHICH, lUNKNOWN_FUNC, lNOT_DOUBLY
X*/
Xint
XlFndNode(id, which, func, ptr, data, size)
Xint    id, which, size;
XFunc    func;
XByte    *ptr, *data;
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(which, set, 4) != 0) {
X        lError("lFndNode", lWRONG_WHICH, which, 0, NULL);
X        return(lWRONG_WHICH);
X    }
X    if (func == NULL) {
X        lError("lFndNode", lUNKNOWN_FUNC, (int) func, 0, NULL);
X        return(lUNKNOWN_FUNC);
X    }
X
X        /* set node where searching must start */
X    switch (which) {
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 ((which == lFIRST || which == lLAST) && node->size == size) {
X        BYTE_COPY(node->data, data, size);
X        cmp = (*func)(ptr, data);
X    }
X
X    switch (which) {
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    which    from which node must be searched and in which
X**                direction
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_WHICH, lSIZE_NE
X*/
Xint
XlFndFlagNode(id, which, flag, data, size)
Xint    id, which, flag, size;
XByte    *data;
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(which, set, 4) != 0) {
X        lError("lFndFlagNode", lWRONG_WHICH, which, 0, NULL);
X        return(lWRONG_WHICH);
X    }
X
X        /* set node where searching must start */
X    switch (which) {
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 (which) {
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->n == 1) {
X        if (which == lPREVIOUS || which == lLAST)
X            return(lFIRST);
X        else if (which == lNEXT || which == lFIRST)
X            return(lLAST);
X        else
X            return(lLAST);    /* which == lCURRENT */
X    } else 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 current 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*/
Xint
XlUpdNode(id, data, size, flag)
Xint    id, size, flag;
XByte    *data;
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*/
Xint
XlDelNode(id, which)
Xint    id, which;
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*/
Xint
XlInfoIndxNode(id, index, size, flag)
Xint    id, index, *size, *flag;
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*/
Xint
XlGetIndxNode(id, index, data, size)
Xint    id, index, size;
XByte    *data;
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->n == 1)
X        return(lLAST);
X    else 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*/
Xint
XlUpdIndxNode(id, index, data, size, flag)
Xint    id, index, size, flag;
XByte    *data;
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*/
Xint
XlDelIndxNode(id, index)
Xint    id, index;
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 */
Xstatic ListPtr
XgetAddress(id)
Xint    id;
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 */
Xstatic void
XdelNodes(node, n)
XNodePtr    node;
Xint    n;
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 */
Xstatic void
XdelListInfo(list)
XListPtr    list;
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' when '-DERROR_FILE' is added as
X** cc option in the makefile */
Xstatic void
XlError(str, code, int1, int2, str1)
Xchar    *str, *str1;
Xint    code, int1, int2;
X{
X#ifdef ERROR_FILE
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 in '%s': %s\n", str, mess);
X        fclose(fpError);
X    }
X#endif
X}
X
Xstatic int
XsetWhchNode(id, which, fname)
Xint    id, which;
Xchar    *fname;
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
Xstatic int
XsetIndxNode(id, index, fname)
Xint    id, index;
Xchar    *fname;
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 */
Xstatic void
Xpartition(array, order, func, lb, ub, pj)
XNodePtr    *array;
Xint    order, lb, ub, *pj;
XFunc    func;
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 */
Xstatic int
Xstack_empty(id)
Xint    id;
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 40617 -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'\" \(8260 characters\)
  sed "s/^X//" >'sorted.c' <<'END_OF_FILE'
X#include    <stdio.h>
X#include    <string.h>
X#include    "list.h"
X
Xtypedef struct person {
X    char    lastname[15];
X    char    firstname[15];
X} Person, *PersonPtr;
Xint    personSz = sizeof(Person);
X
X#ifdef ANSI
Xstatic void    addPerson(int id, char *first, char *last);
Xstatic void    addPersonSorted(int id, char *first, char *last);
Xstatic int    compare(PersonPtr p1, PersonPtr p2, int order);
Xstatic int    fndNxtPerson(char *last, PersonPtr data);
Xstatic int    sortPerson(int id);
X#else
Xstatic void    addPerson(), addPersonSorted();
Xstatic int    compare(), fndNxtPerson(), sortPerson();
X#endif
X
Xint
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 8260 -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...