home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Usenet 1994 October
/
usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso
/
misc
/
volume37
/
linkedlist
/
part01
next >
Wrap
Text File
|
1993-05-04
|
59KB
|
2,415 lines
Newsgroups: comp.sources.misc
From: anita@bouw.tno.nl (Anita Eijs)
Subject: v37i036: linkedlist - Generic Linked List Package, Part01/02
Message-ID: <csm-v37i036=linkedlist.104312@sparky.IMD.Sterling.COM>
X-Md4-Signature: bf3ce1eff0daaa6d0be911c12a01aef0
Date: Tue, 4 May 1993 15:43:54 GMT
Approved: kent@sparky.imd.sterling.com
Submitted-by: anita@bouw.tno.nl (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 : +31 15 122182 E-MAIL : anita@bouw.tno.nl |
+--------------------------------------------------------+
------- 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 (anita@bouw.tno.nl)
XTNO - BOUW - BouwInformatica
XP.O. Box 49
X2600 AA Delft
XThe Netherlands
XFAX : +31 15 843990
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...