home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume37 / linkedlist / part01 next >
Text File  |  1993-05-04  |  59KB  |  2,415 lines

  1. Newsgroups: comp.sources.misc
  2. From: anita@bouw.tno.nl (Anita Eijs)
  3. Subject: v37i036:  linkedlist - Generic Linked List Package, Part01/02
  4. Message-ID: <csm-v37i036=linkedlist.104312@sparky.IMD.Sterling.COM>
  5. X-Md4-Signature: bf3ce1eff0daaa6d0be911c12a01aef0
  6. Date: Tue, 4 May 1993 15:43:54 GMT
  7. Approved: kent@sparky.imd.sterling.com
  8.  
  9. Submitted-by: anita@bouw.tno.nl (Anita Eijs)
  10. Posting-number: Volume 37, Issue 36
  11. Archive-name: linkedlist/part01
  12. Environment: UNIX, MS-DOS, VAX/VMS, Macintosh
  13. Supersedes: linkedlist: Volume 30, Issue 22
  14.  
  15. LinkedList Version: 0.8, May 1992
  16.  
  17. The Generic Linked List Package is a package to define, create, update, query
  18. and delete one or more (nodes of) linked lists, to sort linked lists, and so
  19. on. The user doesn't have to take care of allocating a number of bytes for a
  20. node, inserting on the right place, deleting and freeing a node and so on.
  21.  
  22. Different kind of linked lists can be defined. In a singly linked list
  23. each node points to the next node, in a doubly linked list each node
  24. points also to the previous node. A chain is a list in which the last
  25. node has a NULL-pointer and in a circular linked list the last node
  26. points back to the first node.
  27.  
  28. The package consists of a set of C-functions :
  29.     lDef        define linked list
  30.     lInfo        get information about linked list
  31.     lSort        sort linked list
  32.     lDel        delete linked list
  33.     lDelAll        delete all linked lists
  34.     lDump        dump a linked list to a file
  35.     lUndump        undump a linked list from a file
  36.     lInsNode    insert node
  37.     lInfoNode    get information about node
  38.     lGetNode    get node
  39.     lFndNode    find node
  40.     lFndFlagNode    get node by flag
  41.     lUpdNode    update current node
  42.     lDelNode    delete node
  43.     lInfoIndxNode    get information about node by index
  44.     lGetIndxNode    get node by index
  45.     lUpdIndxNode    update node by index
  46.     lDelIndxNode    delete node by index
  47.  
  48. The Generic Linked List Package is ported to UNIX, MS-DOS, VAX/VMS and
  49. Macintosh.
  50.  
  51. Please look at the README file and the manual pages for more detailed
  52. information !
  53.  
  54.         Anita
  55.  
  56.     +--------------------------------------------------------+
  57.     | TNO - BOUW, PO-box 49, 2600 AA  Delft, The Netherlands |
  58.     | FAX : +31 15 122182         E-MAIL : anita@bouw.tno.nl |
  59.     +--------------------------------------------------------+
  60. ------- cut here ------------------------------------------------
  61. #! /bin/sh
  62. # This is a shell archive.  Remove anything before this line, then feed it
  63. # into a shell via "sh file" or similar.  To overwrite existing files,
  64. # type "sh file -c".
  65. # Contents:  README Doc Makefile list.c sorted.c
  66. # Wrapped by kent@sparky on Tue May  4 10:37:10 1993
  67. PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin ; export PATH
  68. echo If this archive is complete, you will see the following message:
  69. echo '          "shar: End of archive 1 (of 2)."'
  70. if test -f 'README' -a "${1}" != "-c" ; then 
  71.   echo shar: Will not clobber existing file \"'README'\"
  72. else
  73.   echo shar: Extracting \"'README'\" \(1996 characters\)
  74.   sed "s/^X//" >'README' <<'END_OF_FILE'
  75. X                Generic Linked List
  76. X                ===================
  77. X
  78. X
  79. XThe distribution of the Generic Linked List package (Version 0.8, May 1993)
  80. Xincludes the following files:
  81. X
  82. X    Doc/Intro.3        - [nt]roff manual pages
  83. X    Doc/lDef.3
  84. X    Doc/lDel.3
  85. X    Doc/lDelAll.3
  86. X    Doc/lDelIndxNode.3
  87. X    Doc/lDelNode.3
  88. X    Doc/lDump.3
  89. X    Doc/lFndFlagNode.3
  90. X    Doc/lFndNode.3
  91. X    Doc/lGetNode.3
  92. X    Doc/lGetIndxNode.3
  93. X    Doc/lInfo.3
  94. X    Doc/lInfoIndxNode.3
  95. X    Doc/lInfoNode.3
  96. X    Doc/lInsNode.3
  97. X    Doc/lSort.3
  98. X    Doc/lUndump.3
  99. X    Doc/lUpdIndxNode.3
  100. X    Doc/lUpdNode.3
  101. X    Makefile        - Berkeley or System V Makefile
  102. X    Makefile.BCC        - Borland C++ v3.1 Makefile
  103. X    README            - this file !
  104. X    CHANGES            - list of changes
  105. X    Tools_makerule        - make rules for Makefile
  106. X    example.c        - example of use of Generic Linked List routines
  107. X    sorted.c        - example of several sorting solutions
  108. X    sorttest.c        - test of sorting theories in lSort
  109. X    list.c            - Generic Linked List sources
  110. X    list.h            - Generic Linked List defines and prototypes
  111. X
  112. X
  113. XThe installation of the Generic Linked List library is pretty simple :
  114. X
  115. X1)    Check the environment settings (TOOLS_HOME, DIR, LIB and RULE) in
  116. X    the Makefile.
  117. X
  118. X2)    Check the environment settings (RANLIB) in the Tools_makerule.
  119. X
  120. X3)    Enter 'make newlib' at the UNIX prompt.
  121. X
  122. X4)    Enter 'make test' or 'make example' to create the executable of
  123. X    the program 'example' at the UNIX prompt.
  124. X
  125. X
  126. XI also ported the Generic Linked List to MSDOS, VAX-VMS and Macintosh. I
  127. Xdidn't create a library on those machines, but I treated list.c and list.h
  128. Xthe same as all the other source-files (*.[ch]) of the program.
  129. X
  130. X
  131. XThe Generic Linked List is in the public domain. It is available at our FTP
  132. Xarchive (ftp.tno.nl or hermes.bouw.tno.nl), just retrieve te files :
  133. X    /pub/TNO/BOUW/Bouwinf/linkedlist_0.8.README
  134. X    /pub/TNO/BOUW/Bouwinf/linkedlist_0.8.shar
  135. X
  136. X
  137. XIf you have any comments, suggestions, or find any bugs, or make any changes
  138. Xyou'd like to share, please let me know.
  139. X
  140. X
  141. XAnita Eijs    (anita@bouw.tno.nl)
  142. XTNO - BOUW - BouwInformatica
  143. XP.O. Box 49
  144. X2600 AA Delft
  145. XThe Netherlands
  146. XFAX : +31 15 843990
  147. END_OF_FILE
  148.   if test 1996 -ne `wc -c <'README'`; then
  149.     echo shar: \"'README'\" unpacked with wrong size!
  150.   fi
  151.   # end of 'README'
  152. fi
  153. if test ! -d 'Doc' ; then
  154.     echo shar: Creating directory \"'Doc'\"
  155.     mkdir 'Doc'
  156. fi
  157. if test -f 'Makefile' -a "${1}" != "-c" ; then 
  158.   echo shar: Will not clobber existing file \"'Makefile'\"
  159. else
  160.   echo shar: Extracting \"'Makefile'\" \(1810 characters\)
  161.   sed "s/^X//" >'Makefile' <<'END_OF_FILE'
  162. X# Generic Linked List
  163. X#
  164. X# Anita Eijs, TNO-BOUW, BouwInformatica, September 1989
  165. X
  166. X# Compiler options
  167. XCC    = gcc
  168. XCFLAGS    =
  169. X
  170. XTOOLS_HOME    = /usr1/user/anita/usr2/Tools
  171. X
  172. X# Name of current directory
  173. XDIR    = List
  174. X
  175. X# Name of library
  176. XLIB    = $(TOOLS_HOME)/Lib/list.a
  177. X
  178. X# Include rules for package
  179. XMAKERULE= Tools_makerule
  180. XRULE    = $(TOOLS_HOME)/$(MAKERULE)
  181. Xinclude $(RULE)
  182. X
  183. X# Contents of current directory
  184. XLIST    = Makefile Makefile.BCC \
  185. X    README CHANGES \
  186. X    list.c list.h \
  187. X    example.c sorted.c sorttest.c
  188. X
  189. X# Documentation
  190. XDOC    = \
  191. X    Doc/Intro.3        Doc/lDef.3        Doc/lDel.3 \
  192. X    Doc/lDelAll.3        Doc/lDelIndxNode.3    Doc/lDelNode.3 \
  193. X    Doc/lDump.3        Doc/lFndFlagNode.3    Doc/lFndNode.3 \
  194. X    Doc/lGetNode.3        Doc/lGetIndxNode.3    Doc/lInfo.3 \
  195. X    Doc/lInfoIndxNode.3    Doc/lInfoNode.3        Doc/lInsNode.3 \
  196. X    Doc/lSort.3        Doc/lUndump.3        Doc/lUpdIndxNode.3 \
  197. X    Doc/lUpdNode.3
  198. X
  199. X# Object dependencies
  200. XOBJ    = list.o
  201. X
  202. XLIB_OBJ    = $(LIB)(list.o)
  203. X
  204. X# The targets
  205. Xusage:
  206. X        $(ECHO)
  207. X        $(ECHO) $(USAGE_ID)
  208. X        $(ECHO) $(USAGE_TARGETS)
  209. X        $(ECHO) $(USAGE_USAGE)
  210. X        $(ECHO) $(USAGE_LIB)
  211. X        $(ECHO) $(USAGE_NEWLIB)
  212. X        $(ECHO) $(USAGE_OFILES)
  213. X        $(ECHO) $(USAGE_TEST)
  214. X        $(ECHO) $(USAGE_TAR)
  215. X        $(ECHO)
  216. X        $(ECHO) $(USAGE_DEFLTS1)
  217. X        $(ECHO) $(USAGE_DEFLTS2)
  218. X        $(ECHO) $(USAGE_DEFLTS3)
  219. X
  220. Xall: ofiles newlib example sorttest sorted
  221. X
  222. Xlib:        $(LIB_OBJ)
  223. X        $(RANLIB) $(LIB)
  224. X
  225. Xnewlib:        $(OBJ)
  226. X        $(AR) r $(LIB) *.o
  227. X        rm -f *.o
  228. X        $(RANLIB) $(LIB)
  229. X
  230. Xofiles:        $(OBJ)
  231. X
  232. Xtest:        example sorttest sorted
  233. X
  234. Xexample:    $(LIB) example.o
  235. X        $(CC) -o example example.o $(LIB)
  236. X
  237. Xsorttest:    $(LIB) sorttest.o
  238. X        $(CC) -o sorttest sorttest.o $(LIB)
  239. X
  240. Xsorted:        $(LIB) sorted.o
  241. X        $(CC) -o sorted sorted.o $(LIB)
  242. X
  243. Xtar:
  244. X        $(ECHO) "Making tar-file in $(TARFILE)"
  245. X        cp ../$(MAKERULE) $(MAKERULE)
  246. X        tar cvf $(TARFILE) $(MAKERULE) $(LIST) $(DOC)
  247. X        rm $(MAKERULE)
  248. X
  249. Xclean:
  250. X        $(ECHO) "Cleaning Directory"
  251. X        rm $(OBJ) example sorttest sorted
  252. END_OF_FILE
  253.   if test 1810 -ne `wc -c <'Makefile'`; then
  254.     echo shar: \"'Makefile'\" unpacked with wrong size!
  255.   fi
  256.   # end of 'Makefile'
  257. fi
  258. if test -f 'list.c' -a "${1}" != "-c" ; then 
  259.   echo shar: Will not clobber existing file \"'list.c'\"
  260. else
  261.   echo shar: Extracting \"'list.c'\" \(40715 characters\)
  262.   sed "s/^X//" >'list.c' <<'END_OF_FILE'
  263. X/*
  264. X**    Anita Eijs    TNO-BOUW, BouwInformatica    May 1989
  265. X**
  266. X**    Generic Linked List Package
  267. X**
  268. X**    Updates:
  269. X**    900402    New routine:
  270. X**            lIndxNode    Get node by index.
  271. X**
  272. X**    900925    New routine:
  273. X**            lError    print error message in lERROR_FILE
  274. X**
  275. X**    901129    New routines:
  276. X**            lDump    Dump a linked list to a file.
  277. X**            lUndump    Undump a linked list from a file.
  278. X**
  279. X**    910301    'Mac'ed by Vinnie:
  280. X**            ListPtr = ListyPtr
  281. X**            Byte = byte
  282. X**            includes
  283. X**            typecasts
  284. X**
  285. X**    910316    New routine:
  286. X**            lFlagNode    Get node by flag.
  287. X**
  288. X**    ***** Version 0.7, March 1992 *****
  289. X**
  290. X**    930401    Several updates by Anita and Shane.
  291. X**        Some functions renamed:
  292. X**            lIndxNode --> lGetIndxNode
  293. X**            lFlagNode --> lFndFlagNode
  294. X**        New routines:
  295. X**            lSort        Sort a linked list.
  296. X**            lInfoIndxNode    Get information about node by index.
  297. X**            lDelIndxNode    Delete node by index.
  298. X**            lUpdIndxNode    Update node by index.
  299. X**        Parameter where added to lFndFlagNode to find several nodes
  300. X**        matching the requested flag.
  301. X**        Defines are made more specific; FIRST is renamed in lFIRST, etc.
  302. X**
  303. X**    ***** Version 0.8, May 1993 *****
  304. X*/
  305. X
  306. X#ifdef MAC
  307. X#define    MAC_OR_VAXC
  308. X#endif
  309. X#ifdef VAXC
  310. X#define    MAC_OR_VAXC
  311. X#define    MSDOS_OR_VAXC
  312. X#endif
  313. X#ifdef MSDOS
  314. X#define    MSDOS_OR_VAXC
  315. X#endif
  316. X
  317. X#ifdef MAC
  318. X#include    <unix.h>    /* open, creat, write, read, close */
  319. X#include    <stddef.h>    /* sizeof */
  320. X#endif
  321. X
  322. X#ifdef MAC_OR_VAXC
  323. X#include    <stdlib.h>
  324. X#else
  325. X#include    <malloc.h>
  326. X#endif
  327. X
  328. X#ifdef MSDOS
  329. X#include    <io.h>    /* open, creat, write, read, close */
  330. X#endif
  331. X
  332. X#include    <stdio.h>
  333. X#include    "list.h"
  334. X
  335. X/* -------------------------------------------------------------------------- */
  336. X
  337. X#ifndef NULL
  338. X#define    NULL    0
  339. X#endif
  340. X
  341. X#undef    FREE
  342. X#define FREE(VAR) if (VAR != NULL) free((char *)VAR);
  343. X#undef    MALLOC
  344. X#define MALLOC(VAR, TYPE) \
  345. X    if ((VAR = (TYPE *)malloc(sizeof(TYPE))) == NULL) { \
  346. X        fprintf(stderr, "No more memory for malloc().\n"); \
  347. X    }
  348. X#undef    CALLOC
  349. X#define CALLOC(VAR, TYPE, NR) \
  350. X    if ((VAR = (TYPE *)calloc(NR, sizeof(TYPE))) == NULL) {\
  351. X        fprintf(stderr, "No more memory for calloc().\n"); \
  352. X    }
  353. X
  354. X#undef    BYTE_COPY
  355. X#define BYTE_COPY(FROM, TO, SIZE) \
  356. X    { \
  357. X        register Byte    *frm = FROM, \
  358. X                *to = TO; \
  359. X        int        i = SIZE; \
  360. X        while (i--) *to++ = *frm++; \
  361. X    }
  362. X
  363. X#define    BIN_WRITE    1    /* necessary for binary file access */
  364. X#define    BIN_READ    0
  365. X#define    PMODE        0666
  366. X
  367. X/* -------------------------------------------------------------------------- */
  368. X
  369. X#ifndef ANSI
  370. Xtypedef    int        (*Func)();
  371. Xtypedef    unsigned char    Byte;
  372. X#endif
  373. X
  374. Xtypedef struct lnode {
  375. X    Byte        *data;    /* data of user */
  376. X    int        size;    /* size (number of bytes) of data */
  377. X    int        flag;    /* user information flag */
  378. X    struct lnode    *prv;    /* previous node */
  379. X    struct lnode    *nxt;    /* next node */
  380. X} ListNode, *NodePtr;
  381. X
  382. Xtypedef struct listhdr {
  383. X    int        id;        /* identifier of linked list */
  384. X    int        sd;        /* singly or doubly linked */
  385. X    int        cc;        /* chain or circular list */
  386. X    int        n;        /* number of nodes */
  387. X    NodePtr        first;        /* address of first node */
  388. X    NodePtr        current;    /* address of current node */
  389. X    NodePtr        last;        /* address of last node */
  390. X    struct listhdr    *nxt;        /* next linked list */
  391. X} ListHdr, *ListPtr;
  392. X
  393. Xtypedef struct header {    /* general info of linked list for dump file */
  394. X    int    sd;
  395. X    int    cc;
  396. X    int    n;
  397. X} Header;
  398. X
  399. Xtypedef struct info {    /* general info of node for dump file */
  400. X    int    size;
  401. X    int    flag;
  402. X} Info;
  403. X
  404. X/* -------------------------------------------------------------------------- */
  405. X
  406. X#ifdef ANSI
  407. Xstatic ListPtr    getAddress(int id);
  408. Xstatic void    delNodes(NodePtr node, int n);
  409. Xstatic void    delListInfo(ListPtr list);
  410. Xstatic void    lError(char *str, int code, int int1, int int2, char *str1);
  411. Xstatic int    setWhchNode(int id, int which, char *fname);
  412. Xstatic int    setIndxNode(int id, int index, char *fname);
  413. Xstatic int    partition(NodePtr *array, int order, Func func, int lb, int ub,
  414. X            int *pj);
  415. Xstatic int    stack_empty(int id);
  416. Xstatic int    intInSet(int intgr, int *set, int set_n);
  417. X#else
  418. Xstatic ListPtr    getAddress();
  419. Xstatic void    delNodes();
  420. Xstatic void    delListInfo();
  421. Xstatic void    lError();
  422. Xstatic int    setWhchNode();
  423. Xstatic int    setIndxNode();
  424. Xstatic int    partition();
  425. Xstatic int    stack_empty();
  426. Xstatic int    intInSet();
  427. X#endif
  428. X
  429. X/* -------------------------------------------------------------------------- */
  430. X
  431. Xstatic ListHdr    firstlist = { 1, 0, 0, 0, NULL, NULL, NULL, NULL };
  432. Xstatic ListPtr    ld = &firstlist;
  433. Xstatic int    idMax = 2;
  434. X
  435. X/* -------------------------------------------------------------------------- */
  436. X
  437. X/*******************************************************************************
  438. X** Define a new linked list and create info about it.
  439. X**
  440. X** Parameters:
  441. X**    In    int    sd    singly or doubly linked
  442. X**                (lSINGLY, lDOUBLY)
  443. X**    In    int    cc    chain or circular linked
  444. X**                (lCHAIN, lCIRCULAR)
  445. X**
  446. X** Return on success:
  447. X**    identifier of linked list
  448. X** Return on error:
  449. X**    lWRONG_SD, lWRONG_CC
  450. X*/
  451. X#ifdef ANSI
  452. Xint
  453. XlDef(int sd, int cc)
  454. X#else
  455. Xint
  456. XlDef(sd, cc)
  457. Xint    sd, cc;
  458. X#endif
  459. X{
  460. X    ListPtr        list, new;
  461. X    static int    set1[] = { lSINGLY, lDOUBLY },
  462. X            set2[] = { lCHAIN, lCIRCULAR };
  463. X
  464. X        /* check parameters */
  465. X    if (intInSet(sd, set1, 2) != 0) {
  466. X        lError("lDef", lWRONG_SD, sd, 0, NULL);
  467. X        return(lWRONG_SD);
  468. X    }
  469. X    if (intInSet(cc, set2, 2) != 0) {
  470. X        lError("lDef", lWRONG_CC, cc, 0, NULL);
  471. X        return(lWRONG_CC);
  472. X    }
  473. X
  474. X    list = ld;
  475. X    while (list->nxt != NULL && list->sd != 0)
  476. X        list = list->nxt;
  477. X    if (list->sd != 0) {    /* new list */
  478. X        MALLOC(new, ListHdr);
  479. X        new->id = idMax++;
  480. X        new->sd = sd;
  481. X        new->cc = cc;
  482. X        new->n = 0;
  483. X        new->first = new->current = new->last = NULL;
  484. X        new->nxt = NULL;
  485. X        list->nxt = new;
  486. X        return(new->id);
  487. X    } else {        /* new list on existing place */
  488. X        list->sd = sd;
  489. X        list->cc = cc;
  490. X        return(list->id);
  491. X    }
  492. X}
  493. X
  494. X/*******************************************************************************
  495. X** Get info of linked list.
  496. X**
  497. X** Parameters:
  498. X**    In    int    id    identifier of linked list
  499. X**    Out    int    *sd    singly or doubly linked
  500. X**                (lSINGLY, lDOUBLY)
  501. X**    Out    int    *cc    chain or cicular linked
  502. X**                (lCHAIN, lCIRCULAR)
  503. X**    Out    int    *n    number of nodes
  504. X**
  505. X** Return on success:
  506. X**    lSUCCESS
  507. X** Return on error:
  508. X**    lUNKNOWN_ID
  509. X*/
  510. X#ifdef ANSI
  511. Xint
  512. XlInfo(int id, int *sd, int *cc, int *n)
  513. X#else
  514. Xint
  515. XlInfo(id, sd, cc, n)
  516. Xint    id, *sd, *cc, *n;
  517. X#endif
  518. X{
  519. X    ListPtr    list;
  520. X
  521. X        /* check parameters */
  522. X    if ((list = getAddress(id)) == NULL) {
  523. X        lError("lInfo", lUNKNOWN_ID, id, 0, NULL);
  524. X        return(lUNKNOWN_ID);
  525. X    }
  526. X
  527. X        /* copy information */
  528. X    *sd = list->sd;
  529. X    *cc = list->cc;
  530. X    *n = list->n;
  531. X
  532. X    return(lSUCCESS);
  533. X}
  534. X
  535. X/*******************************************************************************
  536. X** Sort a linked list.
  537. X**
  538. X** Parameters:
  539. X**    In    int    id    identifier of linked list
  540. X**    In    int    order    sorting order
  541. X**                (lDESCENDING, lASCENDING)
  542. X**    In    int    theory    sorting theory
  543. X**                (lBUBBLE, lHEAP, lINSERT, lQUICK, lSELECTION)
  544. X**    In    Func    func    number of nodes
  545. X**
  546. X** Return on success:
  547. X**    lSUCCESS
  548. X** Return on error:
  549. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_ORDER, lWRONG_THEORY
  550. X*/
  551. X#ifdef ANSI
  552. Xint lSort(int id, int order, int theory, Func func)
  553. X#else
  554. Xint
  555. XlSort(id, order, theory, func)
  556. Xint    id, order, theory;
  557. XFunc    func;
  558. X#endif
  559. X{
  560. X    int        node_n, i, s, f, k, where, j, cmp;
  561. X    ListPtr        list;
  562. X    NodePtr        temp, temp2, *array;
  563. X    static int    set1[] = { lASCENDING, lDESCENDING },
  564. X            set2[] = { lBUBBLE, lHEAP, lINSERT, lQUICK,
  565. X                lSELECTION };
  566. X
  567. X        /* check parameters */
  568. X    if ((list = getAddress(id)) == NULL) {
  569. X        lError("lSort", lUNKNOWN_ID, id, 0, NULL);
  570. X        return(lUNKNOWN_ID);
  571. X    }
  572. X    if (list->n == 0) {
  573. X        lError("lSort", lEMPTY_LIST, id, 0, NULL);
  574. X        return(lEMPTY_LIST);
  575. X    }
  576. X    if (intInSet(order, set1, 2) != 0) {
  577. X        lError("lSort", lWRONG_ORDER, id, 0, NULL);
  578. X        return(lWRONG_ORDER);
  579. X    }
  580. X    if (intInSet(theory, set2, 5) != 0) {
  581. X        lError("lSort", lWRONG_THEORY, id, 0, NULL);
  582. X        return(lWRONG_THEORY);
  583. X    }
  584. X
  585. X    node_n = list->n;
  586. X        /* allocate 1 extra so I can nave a null in it */
  587. X    CALLOC(array, NodePtr, node_n+1);
  588. X
  589. X    list->current = list->first;
  590. X    for (i=0; i<node_n && list->current != NULL ; i++) {
  591. X        array[i] = list->current;
  592. X        list->current = (list->current)->nxt;
  593. X    }
  594. X    array[node_n] = NULL;
  595. X
  596. X    switch (theory) {
  597. X    case lBUBBLE: {
  598. X        int    switched = 1;
  599. X
  600. X        for (i=0; i < node_n-1 && switched == 1; i++) {
  601. X            switched = 0;
  602. X            for (j=0; j < node_n-i-1; j++) {
  603. X                cmp = (*func)(array[j]->data, array[j+1]->data);
  604. X                if ((order == lASCENDING && cmp == l2LT1)
  605. X                 || (order == lDESCENDING && cmp == l1LT2)) {
  606. X                    temp = array[j];
  607. X                    array[j] = array[j+1];
  608. X                    array[j+1] = temp;
  609. X
  610. X                    switched = 1;
  611. X                }
  612. X            }
  613. X        }
  614. X        break;
  615. X    } /* end of lBUBBLE */
  616. X    case lHEAP:
  617. X        for (i=1; i<node_n; i++) {
  618. X            temp = array[i];
  619. X
  620. X            s = i;
  621. X            f = (s-1)/2;
  622. X            cmp = (*func)(array[f]->data, temp->data);
  623. X            while (s > 0 && ((order == lASCENDING && cmp == l1LT2)
  624. X             || (order == lDESCENDING && cmp == l2LT1))) {
  625. X                array[s] = array[f];
  626. X                s = f;
  627. X                f = (s-1)/2;
  628. X                cmp = (*func)(array[f]->data, temp->data);
  629. X            }
  630. X
  631. X            array[s] = temp;
  632. X        }
  633. X        for (i=node_n-1; i>0; i--) {
  634. X            temp = array[i];
  635. X            array[i] = array[0];
  636. X            f = 0;
  637. X
  638. X            if (i == 1)
  639. X                s = -1;
  640. X            else
  641. X                s = 1;
  642. X            cmp = (*func)(array[2]->data, array[1]->data);
  643. X            if (i > 2 && ((order == lASCENDING && cmp == l2LT1)
  644. X             || (order == lDESCENDING && cmp == l1LT2)))
  645. X                s = 2;
  646. X
  647. X            if (s >= 0)
  648. X                cmp = (*func)(temp->data, array[s]->data);
  649. X            while (s >= 0 && ((order == lASCENDING && cmp == l1LT2)
  650. X             || (order == lDESCENDING && cmp == l2LT1))) {
  651. X                array[f] = array[s];
  652. X                f = s;
  653. X
  654. X                s = 2*f+1;
  655. X                if (s+1 <= i-1) {
  656. X                    cmp = (*func)(array[s]->data,
  657. X                        array[s+1]->data);
  658. X                    if (cmp < 0)
  659. X                        s = s+1;
  660. X                }
  661. X                if (s > i-1)
  662. X                    s = -1;
  663. X                if (s >= 0)
  664. X                    cmp = (*func)(temp->data,
  665. X                        array[s]->data);
  666. X            }
  667. X            array[f] = temp;
  668. X        }
  669. X        break;
  670. X    case lINSERT:
  671. X        for (i=1; i<node_n; i++) {
  672. X            temp = array[i];
  673. X            cmp = (*func)(temp->data, array[i-1]->data);
  674. X            for (j=i-1; j>=0
  675. X             && ((order == lASCENDING && cmp == l1LT2)
  676. X             || (order == lDESCENDING && cmp == l2LT1)); j--) {
  677. X                temp2 = array[j];
  678. X                array[j] = array[j+1];
  679. X                array[j+1] = temp2;
  680. X                if (j > 0)
  681. X                    cmp = (*func)(temp->data,
  682. X                        array[j-1]->data);
  683. X            }
  684. X        }
  685. X        break;
  686. X    case lQUICK: {
  687. X        struct bndtype {
  688. X            int lb;
  689. X            int ub;
  690. X        }        newbnds;
  691. X        int        newbndsSz = sizeof(struct bndtype),
  692. X                stack = lDef(lDOUBLY, lCHAIN);
  693. X
  694. X        newbnds.lb = 0;
  695. X        newbnds.ub = node_n-1;
  696. X            /* basicly a push */
  697. X        lInsNode(stack, lLAST, &newbnds, newbndsSz, 0);
  698. X
  699. X            /* repeat as long as there are any unsorted subarrays
  700. X            ** on the stack */
  701. X        while (!stack_empty(stack)) {
  702. X                /* a pop */
  703. X            lGetNode(stack, lCURRENT, &newbnds, newbndsSz);
  704. X            lDelNode(stack, lCURRENT);
  705. X            while (newbnds.ub > newbnds.lb) {
  706. X                    /* process next sub array */
  707. X                partition(array, order, (*func), newbnds.lb,
  708. X                    newbnds.ub, &j);
  709. X                    /* stack the larger subarray */
  710. X                if (j-newbnds.lb > newbnds.ub-j) {
  711. X                        /* stack lower subarray */
  712. X                    i = newbnds.ub;
  713. X                    newbnds.ub = j-1;
  714. X                        /* basicly a push */
  715. X                    lInsNode(stack, lLAST, &newbnds,
  716. X                        newbndsSz, 0);
  717. X                        /* process upper subarray */
  718. X                    newbnds.lb = j+1;
  719. X                    newbnds.ub = i;
  720. X                } else {
  721. X                        /* stack upper subarray */
  722. X                    i = newbnds.lb;
  723. X                    newbnds.lb = j+1;
  724. X                        /* basicly a push */
  725. X                    lInsNode(stack, lLAST, &newbnds,
  726. X                        newbndsSz, 0);
  727. X                        /* process lower subarray */
  728. X                    newbnds.lb = i;
  729. X                    newbnds.ub = j-1;
  730. X                }
  731. X            }
  732. X        }
  733. X        lDel(stack);
  734. X        break;
  735. X    } /* end of lQUICK */
  736. X    case lSELECTION: {
  737. X        int    indx;
  738. X
  739. X        for (i=node_n-1; i>0 ; i--) {
  740. X            temp = array[0];
  741. X            indx = 0;
  742. X
  743. X            for (j=1; j<=i; j++) {
  744. X                cmp = (*func)(array[j]->data, temp->data);
  745. X                if ((order == lASCENDING && cmp == l2LT1)
  746. X                 || (order == lDESCENDING && cmp == l1LT2)) {
  747. X                    temp = array[j];
  748. X                    indx = j;
  749. X                }
  750. X            }
  751. X            array[indx] = array[i];
  752. X            array[i] = temp;
  753. X        }
  754. X        break;
  755. X    } /* end of lSELECTION */
  756. X    } /* end of switch */
  757. X
  758. X        /* init list to start and reset it */
  759. X    list->first = array[0];
  760. X    list->last = array[node_n-1];
  761. X
  762. X    list->current = list->first;
  763. X    for (k=0; k<node_n; k++) {
  764. X        if (k == 0)
  765. X            where = lFIRST;
  766. X        else if (k == node_n)
  767. X            where = lLAST;
  768. X        else
  769. X            where = lNEXT;
  770. X
  771. X        switch (where) {
  772. X        case lFIRST:
  773. X            if (list->cc == lCIRCULAR)
  774. X                (list->first)->prv = (list->last);
  775. X
  776. X            if (list->sd == lDOUBLY)
  777. X                array[k]->prv = NULL;
  778. X
  779. X            array[k]->nxt = array[k+1];
  780. X            break;
  781. X
  782. X        case lNEXT:
  783. X            if (list->sd == lDOUBLY)
  784. X                (list->first)->prv = array[k-1];
  785. X
  786. X            array[k]->nxt = array[k+1];
  787. X            break;
  788. X
  789. X        case lLAST:
  790. X            if (list->sd == lDOUBLY)
  791. X                array[k]->prv = array[k-1];
  792. X
  793. X            if (list->cc == lCIRCULAR)
  794. X                array[k]->nxt = list->first;
  795. X            else
  796. X                array[k]->nxt = NULL;
  797. X            break;
  798. X        }
  799. X    }
  800. X    FREE(array);
  801. X
  802. X    return(lSUCCESS);
  803. X}
  804. X
  805. X/*******************************************************************************
  806. X** Dump a linked list to a file.
  807. X**
  808. X** Parameters:
  809. X**    In    int    id    identifier of linked list
  810. X**    In    char    *file    name of linked list dump file
  811. X**
  812. X** Return on success:
  813. X**    lSUCCESS
  814. X** Return on error:
  815. X**    lUNKNOWN_ID, lOPEN_ERROR
  816. X**
  817. X** File structure:
  818. X**    <header> { <info> <data> }
  819. X**    header.n    number of <info>-<data>-combinations (nodes)
  820. X**    info.size    size of <data>
  821. X*/
  822. X#ifdef ANSI
  823. Xint
  824. XlDump(int id, char *file)
  825. X#else
  826. Xint
  827. XlDump(id, file)
  828. Xint    id;
  829. Xchar    *file;
  830. X#endif
  831. X{
  832. X#ifndef MSDOS
  833. X    int    open(), creat(), write(), close();
  834. X#endif
  835. X
  836. X    int    fdDump, i;
  837. X    ListPtr    list;
  838. X    NodePtr    node;
  839. X    Info    info;
  840. X    Header    header;
  841. X
  842. X        /* check parameters */
  843. X    if ((list = getAddress(id)) == NULL) {
  844. X        lError("lDump", lUNKNOWN_ID, id, 0, NULL);
  845. X        return(lUNKNOWN_ID);
  846. X    }
  847. X
  848. X    fdDump = open(file, BIN_WRITE);
  849. X    if (fdDump == -1) {
  850. X        fdDump = creat(file, PMODE);
  851. X        if (fdDump == -1) {
  852. X            lError("lDump", lOPEN_ERROR, 0, 0, file);
  853. X            return(lOPEN_ERROR);
  854. X        }
  855. X    }
  856. X
  857. X    header.sd = list->sd;
  858. X    header.cc = list->cc;
  859. X    header.n = list->n;
  860. X    write(fdDump, (char *) &header, sizeof(Header));
  861. X
  862. X    node = list->first;
  863. X    for (i=0; i<header.n; i++) {
  864. X        info.size = node->size;
  865. X        info.flag = node->flag;
  866. X        write(fdDump, (char *) &info, sizeof(Info));
  867. X        write(fdDump, (char *) node->data, node->size);
  868. X        node = node->nxt;
  869. X    }
  870. X
  871. X    close(fdDump);
  872. X
  873. X    return(lSUCCESS);
  874. X}
  875. X
  876. X/*******************************************************************************
  877. X** Undump a linked list from a file.
  878. X**
  879. X** Parameters:
  880. X**    In    char    *file    name of linked list dump file
  881. X**
  882. X** Return on success:
  883. X**    lSUCCESS
  884. X** Return on error:
  885. X**    lOPEN_ERROR
  886. X*/
  887. X#ifdef ANSI
  888. Xint
  889. XlUndump(char *file)
  890. X#else
  891. Xint
  892. XlUndump(file)
  893. Xchar    *file;
  894. X#endif
  895. X{
  896. X#ifndef MSDOS
  897. X    int    open(), read(), close();
  898. X#endif
  899. X
  900. X    int    fdDump, i, id;
  901. X    Info    info;
  902. X    Header    header;
  903. X    Byte    *data;
  904. X
  905. X        /* check parameters */
  906. X    fdDump = open(file, BIN_READ);
  907. X    if (fdDump == -1) {
  908. X        lError("lDump", lOPEN_ERROR, 0, 0, file);
  909. X        return(lOPEN_ERROR);
  910. X    }
  911. X
  912. X    read(fdDump, (char *) &header, sizeof(Header));
  913. X    id = lDef(header.sd, header.cc);
  914. X
  915. X    for (i=0; i<header.n; i++) {
  916. X        read(fdDump, (char *) &info, sizeof(Info));
  917. X        CALLOC(data, Byte, info.size);
  918. X        read(fdDump, (char *) data, info.size);
  919. X        lInsNode(id, lLAST, data, info.size, info.flag);
  920. X        FREE(data);
  921. X    }
  922. X
  923. X    close(fdDump);
  924. X
  925. X    return(id);
  926. X}
  927. X
  928. X/*******************************************************************************
  929. X** Delete a linked list and clear info about it.
  930. X**
  931. X** Parameters:
  932. X**    In    int    id    identifier of linked list
  933. X**
  934. X** Return on success:
  935. X**    lSUCCESS
  936. X** Return on error:
  937. X**    lUNKNOWN_ID
  938. X*/
  939. X#ifdef ANSI
  940. Xint
  941. XlDel(int id)
  942. X#else
  943. Xint
  944. XlDel(id)
  945. Xint    id;
  946. X#endif
  947. X{
  948. X    ListPtr    list;
  949. X
  950. X        /* check parameters */
  951. X    if ((list = getAddress(id)) == NULL) {
  952. X        lError("lDel", lUNKNOWN_ID, id, 0, NULL);
  953. X        return(lUNKNOWN_ID);
  954. X    }
  955. X
  956. X        /* delete all nodes */
  957. X    delNodes(list->first, list->n);
  958. X        /* reset info as deleted linked list */
  959. X    list->sd = list->cc = list->n = 0;
  960. X    list->first = list->current = list->last = NULL;
  961. X
  962. X    return(lSUCCESS);
  963. X}
  964. X
  965. X/*******************************************************************************
  966. X** Delete all linked list and all info about those lists.
  967. X**
  968. X** No parameters.
  969. X**
  970. X** Return on success:
  971. X**    lSUCCESS
  972. X** Return on error:
  973. X**    lNO_LIST
  974. X*/
  975. X#ifdef ANSI
  976. Xint
  977. XlDelAll(void)
  978. X#else
  979. Xint
  980. XlDelAll()
  981. X#endif
  982. X{
  983. X    ListPtr    list, nxt;
  984. X
  985. X    if (ld == NULL) {
  986. X        lError("lDelAll", lNO_LIST, 0, 0, NULL);
  987. X        return(lNO_LIST);
  988. X    }
  989. X
  990. X    list = ld;
  991. X    while (list != NULL) {
  992. X        nxt = list->nxt;
  993. X        if (list->sd != 0 && list->cc != 0)
  994. X            lDel(list->id);    /* delete when not already deleted */
  995. X        list = nxt;
  996. X    }
  997. X    delListInfo(ld->nxt);
  998. X        /* save info of initial list */
  999. X    firstlist.id = 1;
  1000. X    firstlist.sd = firstlist.cc = firstlist.n = 0;
  1001. X    firstlist.first = firstlist.current = firstlist.last = NULL;
  1002. X    firstlist.nxt = NULL;
  1003. X    ld = &firstlist;
  1004. X    idMax = 2;
  1005. X
  1006. X    return(lSUCCESS);
  1007. X}
  1008. X
  1009. X/*******************************************************************************
  1010. X** Insert a node in linked list.
  1011. X**
  1012. X** Parameters:
  1013. X**    In    int    id    identifier of linked list
  1014. X**    In    int    where    place where node must be inserted
  1015. X**                (lFIRST, lBEFORE, lAFTER, lLAST)
  1016. X**    In    Byte    *data    data of node
  1017. X**    In    int    size    size of data
  1018. X**    In    int    flag    user information flag
  1019. X**
  1020. X** Return on success:
  1021. X**    lSUCCESS
  1022. X** Return on error:
  1023. X**    lUNKNOWN_ID, lWRONG_WHERE
  1024. X*/
  1025. X#ifdef ANSI
  1026. Xint
  1027. XlInsNode(int id, int where, Byte *data, int size, int flag)
  1028. X#else
  1029. Xint
  1030. XlInsNode(id, where, data, size, flag)
  1031. Xint    id, where, size, flag;
  1032. XByte    *data;
  1033. X#endif
  1034. X{
  1035. X    ListPtr        list;
  1036. X    NodePtr        node, new;
  1037. X    static int    set[] = { lFIRST, lBEFORE, lAFTER, lLAST };
  1038. X
  1039. X        /* check parameters */
  1040. X    if ((list = getAddress(id)) == NULL) {
  1041. X        lError("lInsNode", lUNKNOWN_ID, id, 0, NULL);
  1042. X        return(lUNKNOWN_ID);
  1043. X    }
  1044. X    if (intInSet(where, set, 4) != 0) {
  1045. X        lError("lInsNode", lWRONG_WHERE, where, 0, NULL);
  1046. X        return(lWRONG_WHERE);
  1047. X    }
  1048. X
  1049. X        /* create new node */
  1050. X    MALLOC(new, ListNode);
  1051. X    CALLOC(new->data, Byte, size);
  1052. X    BYTE_COPY(data, new->data, size);
  1053. X    new->size = size;
  1054. X    new->flag = flag;
  1055. X
  1056. X        /* specific insert cases */
  1057. X    if (list->first == NULL)
  1058. X        where = lONE_NODE;    /* first node in list */
  1059. X    else if (list->current == list->first && where == lBEFORE)
  1060. X        where = lFIRST;        /* before first is like insert first */
  1061. X    else if (list->current == list->last && where == lAFTER)
  1062. X        where = lLAST;        /* after last is like insert last */
  1063. X
  1064. X    switch (where) {
  1065. X    case lONE_NODE:
  1066. X        if (list->cc == lCHAIN)
  1067. X            new->prv = new->nxt = NULL;
  1068. X        else {
  1069. X            if (list->sd == lDOUBLY)
  1070. X                new->prv = new;
  1071. X            else
  1072. X                new->prv = NULL;
  1073. X            new->nxt = new;
  1074. X        }
  1075. X        list->first = list->last = new;
  1076. X        break;
  1077. X    case lFIRST:
  1078. X        new->prv = (list->first)->prv;
  1079. X        new->nxt = list->first;
  1080. X        if (list->cc == lCIRCULAR)
  1081. X            (list->last)->nxt = new;
  1082. X        else
  1083. X            (list->last)->nxt = NULL;
  1084. X        if (list->sd == lDOUBLY)
  1085. X            (list->first)->prv = new;
  1086. X        list->first = new;
  1087. X        break;
  1088. X    case lBEFORE:
  1089. X        new->prv = (list->current)->prv;    /* == NULL if lSINGLY */
  1090. X        new->nxt = list->current;
  1091. X
  1092. X        if (list->sd == lDOUBLY) {
  1093. X            ((list->current)->prv)->nxt = new;
  1094. X            (list->current)->prv = new;
  1095. X        } else {
  1096. X            node = list->first;
  1097. X                /* search for last before current */
  1098. X            while (node->nxt != list->current && node != list->last)
  1099. X                node = node->nxt;
  1100. X            node->nxt = new;
  1101. X        }
  1102. X        if (list->current == list->first)
  1103. X            list->first = new;
  1104. X        break;
  1105. X    case lAFTER:
  1106. X        if (list->sd == lDOUBLY)
  1107. X            new->prv = list->current;
  1108. X        else
  1109. X            new->prv = NULL;
  1110. X        new->nxt = (list->current)->nxt;
  1111. X        if (list->sd == lDOUBLY) {
  1112. X            ((list->current)->nxt)->prv = new;
  1113. X            (list->current)->prv = new;
  1114. X        }
  1115. X        (list->current)->nxt = new;
  1116. X        if (list->current == list->last)
  1117. X            list->last = new;
  1118. X        break;
  1119. X    case lLAST:
  1120. X        node = list->last;
  1121. X        if (list->sd == lDOUBLY)
  1122. X            new->prv = node;
  1123. X        else
  1124. X            new->prv = NULL;
  1125. X        if (list->cc == lCIRCULAR)
  1126. X            new->nxt = list->first;
  1127. X        else
  1128. X            new->nxt = NULL;
  1129. X        if (list->sd == lDOUBLY && list->cc == lCIRCULAR)
  1130. X            (list->first)->prv = new;
  1131. X        node->nxt = new;
  1132. X        list->last = new;
  1133. X        break;
  1134. X    }
  1135. X
  1136. X    list->n++;
  1137. X    list->current = new;
  1138. X
  1139. X    return(lSUCCESS);
  1140. X}
  1141. X
  1142. X/*******************************************************************************
  1143. X** Get info of node of linked list.
  1144. X**
  1145. X** Parameters:
  1146. X**    In    int    id    identifier of linked list
  1147. X**    In    int    which    which node must be inspected
  1148. X**                (lFIRST, lPREVIOUS, lCURRENT, lNEXT, lLAST)
  1149. X**    Out    int    *size    size of data of node
  1150. X**    Out    int    *flag    user information flag
  1151. X**
  1152. X** Return on success:
  1153. X**    lSUCCESS
  1154. X** Return on error:
  1155. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, lEOL, lNOT_DOUBLY
  1156. X*/
  1157. X#ifdef ANSI
  1158. Xint
  1159. XlInfoNode(int id, int which, int *size, int *flag)
  1160. X#else
  1161. Xint
  1162. XlInfoNode(id, which, size, flag)
  1163. Xint    id, which, *size, *flag;
  1164. X#endif
  1165. X{
  1166. X    ListPtr    list;
  1167. X    int    rtrn;
  1168. X
  1169. X    rtrn = setWhchNode(id, which, "lInfoNode");
  1170. X    if (rtrn != lSUCCESS)    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, */
  1171. X        return(rtrn);    /* lEOL, lNOT_DOUBLY */
  1172. X
  1173. X    list = getAddress(id);    /* already checked in setWhchNode */
  1174. X
  1175. X        /* copy information */
  1176. X    *size = (list->current)->size;
  1177. X    *flag = (list->current)->flag;
  1178. X
  1179. X    return(lSUCCESS);
  1180. X}
  1181. X
  1182. X/*******************************************************************************
  1183. X** Get data of node.
  1184. X**
  1185. X** Parameters:
  1186. X**    In    int    id    identifier of linked list
  1187. X**    In    int    which    which node must be retrieved
  1188. X**                (lFIRST, lPREVIOUS, lCURRENT, lNEXT, lLAST)
  1189. X**    Out    Byte    *data    data of node
  1190. X**    In    int    size    size of data
  1191. X**
  1192. X** Return on success:
  1193. X**    lSUCCESS, lFIRST, lLAST
  1194. X** Return on error:
  1195. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, lEOL, lNOT_DOUBLY, lSIZE_NE
  1196. X*/
  1197. X#ifdef ANSI
  1198. Xint
  1199. XlGetNode(int id, int which, Byte *data, int size)
  1200. X#else
  1201. Xint
  1202. XlGetNode(id, which, data, size)
  1203. Xint    id, which, size;
  1204. XByte    *data;
  1205. X#endif
  1206. X{
  1207. X    ListPtr    list;
  1208. X    int    rtrn;
  1209. X
  1210. X    rtrn = setWhchNode(id, which, "lInfoNode");
  1211. X    if (rtrn != lSUCCESS)    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH, */
  1212. X        return(rtrn);    /* lEOL, lNOT_DOUBLY */
  1213. X
  1214. X    list = getAddress(id);    /* already checked in setWhchNode */
  1215. X
  1216. X        /* expected data and node must have same size */
  1217. X    if ((list->current)->size != size) {
  1218. X        lError("lGetNode", lSIZE_NE, size, (list->current)->size, NULL);
  1219. X        return(lSIZE_NE);
  1220. X    }
  1221. X
  1222. X    BYTE_COPY((list->current)->data, data, size);
  1223. X
  1224. X    if (list->current == list->first)
  1225. X        return(lFIRST);
  1226. X    else if (list->current == list->last)
  1227. X        return(lLAST);
  1228. X
  1229. X    return(lSUCCESS);
  1230. X}
  1231. X
  1232. X/*******************************************************************************
  1233. X** Find node.
  1234. X**
  1235. X** Parameters:
  1236. X**    In    int    id    identifier of linked list
  1237. X**    In    int    where    from where must be searched
  1238. X**    In    Func    func    function for checking the data on conditions
  1239. X**    In    Byte    *ptr    data for comparison in function
  1240. X**    Out    Byte    *data    data of node
  1241. X**    In    int    size    size of data
  1242. X**
  1243. X** Return on success:
  1244. X**    lFOUND, lFIRST, lLAST, lNOT_FOUND
  1245. X** Return on error:
  1246. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHERE, lUNKNOWN_FUNC, lNOT_DOUBLY
  1247. X*/
  1248. X#ifdef ANSI
  1249. Xint
  1250. XlFndNode(int id, int where, Func func, Byte *ptr, Byte *data, int size)
  1251. X#else
  1252. Xint
  1253. XlFndNode(id, where, func, ptr, data, size)
  1254. Xint    id, where, size;
  1255. XFunc    func;
  1256. XByte    *ptr, *data;
  1257. X#endif
  1258. X{
  1259. X    NodePtr        node;
  1260. X    ListPtr        list;
  1261. X    int        cmp = lNOT_FOUND;
  1262. X    static int    set[] = { lFIRST, lNEXT, lPREVIOUS, lLAST };
  1263. X
  1264. X        /* check parameters */
  1265. X    if ((list = getAddress(id)) == NULL) {
  1266. X        lError("lFndNode", lUNKNOWN_ID, id, 0, NULL);
  1267. X        return(lUNKNOWN_ID);
  1268. X    }
  1269. X    if (list->n == 0) {
  1270. X        lError("lFndNode", lEMPTY_LIST, id, 0, NULL);
  1271. X        return(lEMPTY_LIST);
  1272. X    }
  1273. X    if (intInSet(where, set, 4) != 0) {
  1274. X        lError("lFndNode", lWRONG_WHERE, where, 0, NULL);
  1275. X        return(lWRONG_WHERE);
  1276. X    }
  1277. X    if (func == NULL) {
  1278. X        lError("lFndNode", lUNKNOWN_FUNC, (int) func, 0, NULL);
  1279. X        return(lUNKNOWN_FUNC);
  1280. X    }
  1281. X
  1282. X        /* set node for where searching must start */
  1283. X    switch (where) {
  1284. X    case lFIRST:    node = list->first;    break;
  1285. X    case lNEXT:
  1286. X    case lPREVIOUS:    node = list->current;    break;
  1287. X    case lLAST:    node = list->last;    break;
  1288. X    }
  1289. X
  1290. X        /* expected data and node must have same size */
  1291. X    if ((where == lFIRST || where == lLAST) && node->size == size) {
  1292. X        BYTE_COPY(node->data, data, size);
  1293. X        cmp = (*func)(ptr, data);
  1294. X    }
  1295. X
  1296. X    switch (where) {
  1297. X    case lFIRST:    /* search forward */
  1298. X    case lNEXT:
  1299. X        while (cmp != lFOUND && node->nxt != NULL
  1300. X         && node != list->last) {
  1301. X            node = node->nxt;
  1302. X                /* expected data and node must have same size */
  1303. X            if (node->size == size) {
  1304. X                BYTE_COPY(node->data, data, size);
  1305. X                cmp = (*func)(ptr, data);
  1306. X            }
  1307. X        }
  1308. X        if (cmp == lFOUND) {
  1309. X            list->current = node;
  1310. X            if (list->current == list->last)
  1311. X                return(lLAST);
  1312. X        }
  1313. X        break;
  1314. X    case lPREVIOUS:    /* search backward */
  1315. X    case lLAST:
  1316. X        if (list->sd != lDOUBLY && cmp == lNOT_FOUND) {
  1317. X            lError("lFndNode", lNOT_DOUBLY, id, 0, NULL);
  1318. X            return(lNOT_DOUBLY);
  1319. X        }
  1320. X        while (cmp != lFOUND && node->prv != NULL
  1321. X         && node->prv != list->first) {
  1322. X            node = node->prv;
  1323. X                /* expected data and node must have same size */
  1324. X            if (node->size == size) {
  1325. X                BYTE_COPY(node->data, data, size);
  1326. X                cmp = (*func)(ptr, data);
  1327. X            }
  1328. X        }
  1329. X        if (cmp == lFOUND) {
  1330. X            list->current = node;
  1331. X            if (list->current == list->first)
  1332. X                return(lFIRST);
  1333. X        }
  1334. X        break;
  1335. X    }
  1336. X
  1337. X    return(cmp);    /* lFOUND, lNOT_FOUND */
  1338. X}
  1339. X
  1340. X/*******************************************************************************
  1341. X** Get node by flag.
  1342. X**
  1343. X** Parameters:
  1344. X**    In    int    id    identifier of linked list
  1345. X**    In    int    flag    flag of node which must be retrieved
  1346. X**    Out    Byte    *data    data of node
  1347. X**    In    int    size    size of data
  1348. X**
  1349. X** Return on success:
  1350. X**    lFOUND, lFIRST, lLAST, lNOT_FOUND
  1351. X** Return on error:
  1352. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHERE, lSIZE_NE
  1353. X*/
  1354. X#ifdef ANSI
  1355. Xint
  1356. XlFndFlagNode(int id, int where, int flag, Byte *data, int size)
  1357. X#else
  1358. Xint
  1359. XlFndFlagNode(id, where, flag, data, size)
  1360. Xint    id, where, flag, size;
  1361. XByte    *data;
  1362. X#endif
  1363. X{
  1364. X    NodePtr        node;
  1365. X    ListPtr        list;
  1366. X    static int    set[] = { lFIRST, lNEXT, lPREVIOUS, lLAST };
  1367. X
  1368. X        /* check parameters */
  1369. X    if ((list = getAddress(id)) == NULL) {
  1370. X        lError("lFndFlagNode", lUNKNOWN_ID, id, 0, NULL);
  1371. X        return(lUNKNOWN_ID);
  1372. X    }
  1373. X    if (list->n == 0) {
  1374. X        lError("lFndFlagNode", lEMPTY_LIST, id, 0, NULL);
  1375. X        return(lEMPTY_LIST);
  1376. X    }
  1377. X    if (intInSet(where, set, 4) != 0) {
  1378. X        lError("lFndFlagNode", lWRONG_WHERE, where, 0, NULL);
  1379. X        return(lWRONG_WHERE);
  1380. X    }
  1381. X
  1382. X        /* set node for where searching must start */
  1383. X    switch (where) {
  1384. X    case lFIRST:
  1385. X        node = list->first;
  1386. X        break;
  1387. X    case lNEXT:
  1388. X        if ((list->current)->nxt == NULL)
  1389. X            return(lNOT_FOUND);    /* end of list reached */
  1390. X        node = (list->current)->nxt;
  1391. X        break;
  1392. X    case lPREVIOUS:
  1393. X        if ((list->current)->prv == NULL)
  1394. X            return(lNOT_FOUND);    /* begin of list reached */
  1395. X        node = (list->current)->prv;
  1396. X        break;
  1397. X    case lLAST:
  1398. X        node = list->last;
  1399. X        break;
  1400. X    }
  1401. X
  1402. X        /* search till begin/end of list */
  1403. X    switch (where) {
  1404. X    case lFIRST:    /* search forward */
  1405. X    case lNEXT:
  1406. X        while (node->flag != flag && node != list->last)
  1407. X            node = node->nxt;
  1408. X        break;
  1409. X    case lPREVIOUS:    /* search backward */
  1410. X    case lLAST:
  1411. X        if (list->sd != lDOUBLY) {
  1412. X            lError("lFndFlagNode", lNOT_DOUBLY, id, 0, NULL);
  1413. X            return(lNOT_DOUBLY);
  1414. X        }
  1415. X        while (node->flag != flag && node != list->first)
  1416. X            node = node->prv;
  1417. X        break;
  1418. X    }
  1419. X
  1420. X    list->current = node;
  1421. X
  1422. X        /* extra flag-check for last node of list */
  1423. X    if ((list->current)->flag != flag) {
  1424. X        lError("lFndFlagNode", lNOT_FOUND, id, 0, NULL);
  1425. X        return(lNOT_FOUND);
  1426. X    }
  1427. X
  1428. X        /* expected data and node must have same size */
  1429. X    if ((list->current)->size != size) {
  1430. X        lError("lFndFlagNode", lSIZE_NE, size, (list->current)->size,
  1431. X            NULL);
  1432. X        return(lSIZE_NE);
  1433. X    }
  1434. X
  1435. X    BYTE_COPY((list->current)->data, data, size);
  1436. X
  1437. X    if (list->current == list->first)
  1438. X        return(lFIRST);
  1439. X    else if (list->current == list->last)
  1440. X        return(lLAST);
  1441. X
  1442. X    return(lFOUND);
  1443. X}
  1444. X
  1445. X/*******************************************************************************
  1446. X** Update curent node.
  1447. X**
  1448. X** Parameters:
  1449. X**    In    int    id    identifier of linked list
  1450. X**    In    Byte    *data    updated data of node
  1451. X**    In    int    size    size of data
  1452. X**    In    int    flag    updated user information flag
  1453. X**
  1454. X** Return on success:
  1455. X**    lSUCCESS
  1456. X** Return on error:
  1457. X**    lUNKNOWN_ID, lEMPTY_LIST
  1458. X*/
  1459. X#ifdef ANSI
  1460. Xint
  1461. XlUpdNode(int id, Byte *data, int size, int flag)
  1462. X#else
  1463. Xint
  1464. XlUpdNode(id, data, size, flag)
  1465. Xint    id, size, flag;
  1466. XByte    *data;
  1467. X#endif
  1468. X{
  1469. X    ListPtr    list;
  1470. X
  1471. X        /* check parameters */
  1472. X    if ((list = getAddress(id)) == NULL) {
  1473. X        lError("lUpdNode", lUNKNOWN_ID, id, 0, NULL);
  1474. X        return(lUNKNOWN_ID);
  1475. X    }
  1476. X    if (list->n == 0) {
  1477. X        lError("lUpdNode", lEMPTY_LIST, id, 0, NULL);
  1478. X        return(lEMPTY_LIST);
  1479. X    }
  1480. X
  1481. X        /* if same size, replace node by updated node */
  1482. X        /* if not same size, insert updated node on current place */
  1483. X    if ((list->current)->size != size) {
  1484. X        FREE((list->current)->data);
  1485. X        CALLOC((list->current)->data, Byte, size);
  1486. X        (list->current)->size = size;
  1487. X    }
  1488. X    (list->current)->flag = flag;
  1489. X    BYTE_COPY(data, (list->current)->data, size);
  1490. X
  1491. X    return(lSUCCESS);
  1492. X}
  1493. X
  1494. X/*******************************************************************************
  1495. X** Delete node.
  1496. X**
  1497. X** Parameters:
  1498. X**    In    int    id    identifier of linked list
  1499. X**    In    int    which    which node must be deleted
  1500. X**                (lFIRST, lCURRENT, lLAST)
  1501. X**
  1502. X** Return on success:
  1503. X**    lSUCCESS
  1504. X** Return on error:
  1505. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_WHICH
  1506. X*/
  1507. X#ifdef ANSI
  1508. Xint
  1509. XlDelNode(int id, int which)
  1510. X#else
  1511. Xint
  1512. XlDelNode(id, which)
  1513. Xint    id, which;
  1514. X#endif
  1515. X{
  1516. X    NodePtr        node, prv, nxt;
  1517. X    ListPtr        list;
  1518. X    static int    set[] = { lFIRST, lCURRENT, lLAST };
  1519. X
  1520. X        /* check parameters */
  1521. X    if ((list = getAddress(id)) == NULL) {
  1522. X        lError("lDelNode", lUNKNOWN_ID, id, 0, NULL);
  1523. X        return(lUNKNOWN_ID);
  1524. X    }
  1525. X    if (list->n == 0) {
  1526. X        lError("lDelNode", lEMPTY_LIST, id, 0, NULL);
  1527. X        return(lEMPTY_LIST);
  1528. X    }
  1529. X    if (intInSet(which, set, 3) != 0) {
  1530. X        lError("lDelNode", lWRONG_WHICH, which, 0, NULL);
  1531. X        return(lWRONG_WHICH);
  1532. X    }
  1533. X
  1534. X        /* specific delete cases */
  1535. X    if (list->n == 1)
  1536. X        which = lONE_NODE;    /* one node in linked list */
  1537. X    else if (which == lCURRENT && list->first == list->current)
  1538. X        which = lFIRST;        /* current is also first node */
  1539. X    else if (which == lCURRENT && list->last == list->current)
  1540. X        which = lLAST;        /* current is also last node */
  1541. X
  1542. X    switch (which) {
  1543. X    case lONE_NODE:
  1544. X        node = list->first;
  1545. X        list->first = list->current = list->last = NULL;
  1546. X        break;
  1547. X    case lFIRST:
  1548. X        node = list->first;
  1549. X        nxt = node->nxt;
  1550. X        if (list->cc == lCIRCULAR) {
  1551. X            prv = list->last;
  1552. X            prv->nxt = nxt;
  1553. X        } else
  1554. X            prv = node->prv;    /* == NULL if lSINGLY */
  1555. X        if (list->sd == lDOUBLY)
  1556. X            nxt->prv = prv;
  1557. X        list->first = list->current = nxt;
  1558. X        break;
  1559. X    case lCURRENT:
  1560. X        node = list->current;
  1561. X        nxt = node->nxt;
  1562. X        if (list->sd == lDOUBLY) {
  1563. X            prv = node->prv;
  1564. X            nxt->prv = prv;
  1565. X        } else {
  1566. X            prv = node = list->first;
  1567. X            while (node != list->current) {
  1568. X                prv = node;
  1569. X                node = node->nxt;
  1570. X            }
  1571. X            if (prv == node)
  1572. X                prv = list->last;
  1573. X        }
  1574. X        prv->nxt = nxt;
  1575. X        list->current = nxt;
  1576. X        break;
  1577. X    case lLAST:
  1578. X        node = list->last;
  1579. X        if (list->sd == lDOUBLY)
  1580. X            prv = node->prv;
  1581. X        else {
  1582. X            if (list->current != list->last)
  1583. X                prv = node = list->current;
  1584. X            else
  1585. X                prv = node = list->first;
  1586. X            while (node != list->last) {
  1587. X                prv = node;
  1588. X                node = node->nxt;
  1589. X            }
  1590. X        }
  1591. X        nxt = node->nxt;
  1592. X        if (list->sd == lDOUBLY && list->cc == lCIRCULAR)
  1593. X            nxt->prv = prv;
  1594. X        prv->nxt = nxt;
  1595. X        list->last = list->current = prv;
  1596. X        break;
  1597. X    }
  1598. X
  1599. X    FREE(node->data);
  1600. X    FREE(node);
  1601. X    list->n--;
  1602. X
  1603. X    return(lSUCCESS);
  1604. X}
  1605. X
  1606. X/*******************************************************************************
  1607. X** Get information about node by index.
  1608. X**
  1609. X** Parameters:
  1610. X**    In    int    id    identifier of linked list
  1611. X**    In    int    index    index of node which must be inspected
  1612. X**    Out    int    *size    size of data of node
  1613. X**    Out    int    *flag    user information flag
  1614. X**
  1615. X** Return on success:
  1616. X**    lSUCCESS
  1617. X** Return on error:
  1618. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
  1619. X*/
  1620. X#ifdef ANSI
  1621. Xint
  1622. XlInfoIndxNode(int id, int index, int *size, int *flag)
  1623. X#else
  1624. Xint
  1625. XlInfoIndxNode(id, index, size, flag)
  1626. Xint    id, index, *size, *flag;
  1627. X#endif
  1628. X{
  1629. X    ListPtr    list;
  1630. X    int    rtrn;
  1631. X
  1632. X    rtrn = setIndxNode(id, index, "lInfoIndxNode");
  1633. X    if (rtrn != lSUCCESS)
  1634. X        return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
  1635. X
  1636. X    list = getAddress(id);    /* already checked in setIndxNode */
  1637. X
  1638. X        /* copy information */
  1639. X    *size = (list->current)->size;
  1640. X    *flag = (list->current)->flag;
  1641. X
  1642. X    return(lSUCCESS);
  1643. X}
  1644. X
  1645. X/*******************************************************************************
  1646. X** Get node by index.
  1647. X**
  1648. X** Parameters:
  1649. X**    In    int    id    identifier of linked list
  1650. X**    In    int    index    index of node which must be retrieved
  1651. X**    Out    Byte    *data    data of node
  1652. X**    In    int    size    size of data
  1653. X**
  1654. X** Return on success:
  1655. X**    lSUCCESS, lFIRST, lLAST
  1656. X** Return on error:
  1657. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX, lSIZE_NE
  1658. X*/
  1659. X#ifdef ANSI
  1660. Xint
  1661. XlGetIndxNode(int id, int index, Byte *data, int size)
  1662. X#else
  1663. Xint
  1664. XlGetIndxNode(id, index, data, size)
  1665. Xint    id, index, size;
  1666. XByte    *data;
  1667. X#endif
  1668. X{
  1669. X    ListPtr    list;
  1670. X    int    rtrn;
  1671. X
  1672. X    rtrn = setIndxNode(id, index, "lGetIndxNode");
  1673. X    if (rtrn != lSUCCESS)
  1674. X        return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
  1675. X
  1676. X    list = getAddress(id);    /* already checked in setIndxNode */
  1677. X
  1678. X        /* expected data and node must have same size */
  1679. X    if ((list->current)->size != size) {
  1680. X        lError("lGetIndxNode", lSIZE_NE, size, (list->current)->size,
  1681. X            NULL);
  1682. X        return(lSIZE_NE);
  1683. X    }
  1684. X
  1685. X    BYTE_COPY((list->current)->data, data, size);
  1686. X
  1687. X    if (list->current == list->first)
  1688. X        return(lFIRST);
  1689. X    else if (list->current == list->last)
  1690. X        return(lLAST);
  1691. X
  1692. X    return(lSUCCESS);
  1693. X}
  1694. X
  1695. X/*******************************************************************************
  1696. X** Update node by index.
  1697. X**
  1698. X** Parameters:
  1699. X**    In    int    id    identifier of linked list
  1700. X**    In    int    index    index of node which must be updated
  1701. X**    In    Byte    *data    updated data of node
  1702. X**    In    int    size    size of data
  1703. X**    In    int    flag    updated user information flag
  1704. X**
  1705. X** Return on success:
  1706. X**    lSUCCESS
  1707. X** Return on error:
  1708. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
  1709. X*/
  1710. X#ifdef ANSI
  1711. Xint
  1712. XlUpdIndxNode(int id, int index, Byte *data, int size, int flag)
  1713. X#else
  1714. Xint
  1715. XlUpdIndxNode(id, index, data, size, flag)
  1716. Xint    id, index, size, flag;
  1717. XByte    *data;
  1718. X#endif
  1719. X{
  1720. X    ListPtr    list;
  1721. X    int    rtrn;
  1722. X
  1723. X    rtrn = setIndxNode(id, index, "lUpdIndxNode");
  1724. X    if (rtrn != lSUCCESS)
  1725. X        return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
  1726. X
  1727. X    list = getAddress(id);    /* already checked in setIndxNode */
  1728. X
  1729. X        /* if same size, replace node by updated node */
  1730. X        /* if not same size, insert updated node on current place */
  1731. X    if ((list->current)->size != size) {
  1732. X        FREE((list->current)->data);
  1733. X        CALLOC((list->current)->data, Byte, size);
  1734. X        (list->current)->size = size;
  1735. X    }
  1736. X    (list->current)->flag = flag;
  1737. X    BYTE_COPY(data, (list->current)->data, size);
  1738. X
  1739. X    return(lSUCCESS);
  1740. X}
  1741. X
  1742. X/*******************************************************************************
  1743. X** Delete node by index.
  1744. X**
  1745. X** Parameters:
  1746. X**    In    int    id    identifier of linked list
  1747. X**    In    int    index    index of node which must be deleted
  1748. X**
  1749. X** Return on success:
  1750. X**    lSUCCESS
  1751. X** Return on error:
  1752. X**    lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX
  1753. X*/
  1754. X#ifdef ANSI
  1755. Xint
  1756. XlDelIndxNode(int id, int index)
  1757. X#else
  1758. Xint
  1759. XlDelIndxNode(id, index)
  1760. Xint    id, index;
  1761. X#endif
  1762. X{
  1763. X    int    rtrn;
  1764. X
  1765. X    rtrn = setIndxNode(id, index, "lDelIndxNode");
  1766. X    if (rtrn != lSUCCESS)
  1767. X        return(rtrn);    /* lUNKNOWN_ID, lEMPTY_LIST, lWRONG_INDEX */
  1768. X
  1769. X    return(lDelNode(id, lCURRENT));    /* lSUCCESS */
  1770. X}
  1771. X
  1772. X/* ---------- static local functions ---------------------------------------- */
  1773. X
  1774. X/* get address of list data */
  1775. X#ifdef ANSI
  1776. Xstatic ListPtr
  1777. XgetAddress(int id)
  1778. X#else
  1779. Xstatic ListPtr
  1780. XgetAddress(id)
  1781. Xint    id;
  1782. X#endif
  1783. X{
  1784. X    ListPtr    list;
  1785. X
  1786. X    list = ld;
  1787. X    while (list != NULL && list->id != id)
  1788. X        list = list->nxt;
  1789. X
  1790. X    if (list == NULL)
  1791. X        return(NULL);    /* id not found */
  1792. X
  1793. X    if (list->sd == 0 && list->cc == 0)    /* deleted linked list */
  1794. X        return(NULL);    /* deleted linked list */
  1795. X
  1796. X    return(list);
  1797. X}
  1798. X
  1799. X/* delete nodes of a linked list */
  1800. X#ifdef ANSI
  1801. Xstatic void
  1802. XdelNodes(NodePtr node, int n)
  1803. X#else
  1804. Xstatic void
  1805. XdelNodes(node, n)
  1806. XNodePtr    node;
  1807. Xint    n;
  1808. X#endif
  1809. X{
  1810. X    NodePtr    nxt;
  1811. X    int    i;
  1812. X
  1813. X    for (i=0; i<n; i++) {
  1814. X        nxt = node->nxt;
  1815. X        FREE(node->data);
  1816. X        FREE(node);
  1817. X        node = nxt;
  1818. X    }
  1819. X}
  1820. X
  1821. X/* delete info about linked list */
  1822. X#ifdef ANSI
  1823. Xstatic void
  1824. XdelListInfo(ListPtr list)
  1825. X#else
  1826. Xstatic void
  1827. XdelListInfo(list)
  1828. XListPtr    list;
  1829. X#endif
  1830. X{
  1831. X    ListPtr    nxt;
  1832. X
  1833. X    while (list != NULL) {
  1834. X        nxt = list->nxt;
  1835. X        FREE(list);
  1836. X        list = nxt;
  1837. X    }
  1838. X}
  1839. X
  1840. X/* print error message in lERROR_FILE */
  1841. X#ifdef ANSI
  1842. Xstatic void
  1843. XlError(char *str, int code, int int1, int int2, char *str1)
  1844. X#else
  1845. Xstatic void
  1846. XlError(str, code, int1, int2, str1)
  1847. Xchar    *str, *str1;
  1848. Xint    code, int1, int2;
  1849. X#endif
  1850. X{
  1851. X#ifndef MSDOS
  1852. X    char    mess[60];
  1853. X    FILE    *fpError, *fopen();
  1854. X
  1855. X    switch (code) {
  1856. X    case lWRONG_SD:
  1857. X        sprintf(mess, "Parameter 'sd' has wrong value : %d", int1);
  1858. X        break;
  1859. X    case lWRONG_CC:
  1860. X        sprintf(mess, "Parameter 'cc' has wrong value : %d", int1);
  1861. X        break;
  1862. X    case lWRONG_WHERE:
  1863. X        sprintf(mess, "Parameter 'where' has wrong value : %d", int1);
  1864. X        break;
  1865. X    case lWRONG_WHICH:
  1866. X        sprintf(mess, "Parameter 'which' has wrong value : %d", int1);
  1867. X        break;
  1868. X    case lUNKNOWN_ID:
  1869. X        sprintf(mess, "List id '%d' is unknown", int1);
  1870. X        break;
  1871. X    case lUNKNOWN_FUNC:
  1872. X        sprintf(mess, "Function '%d' is unknown", int1);
  1873. X        break;
  1874. X    case lNO_LIST:
  1875. X        sprintf(mess, "There are no lists defined");
  1876. X        break;
  1877. X    case lEMPTY_LIST:
  1878. X#ifdef DEBUG
  1879. X        sprintf(mess, "List '%d' is empty", int1);
  1880. X        break;
  1881. X#else
  1882. X        return;
  1883. X#endif
  1884. X    case lEOL:
  1885. X#ifdef DEBUG
  1886. X        sprintf(mess, "End of list '%d' reached", int1);
  1887. X        break;
  1888. X#else
  1889. X        return;
  1890. X#endif
  1891. X    case lNOT_FOUND:
  1892. X#ifdef DEBUG
  1893. X        sprintf(mess, "Node not found in list '%d'", int1);
  1894. X        break;
  1895. X#else
  1896. X        return;
  1897. X#endif
  1898. X    case lNOT_DOUBLY:
  1899. X        sprintf(mess, "List '%d' is not doubly linked", int1);
  1900. X        break;
  1901. X    case lSIZE_NE:
  1902. X        sprintf(mess,
  1903. X            "Size of expected data '%d' and node '%d' not equal",
  1904. X            int1, int2);
  1905. X        break;
  1906. X    case lWRONG_INDEX:
  1907. X        sprintf(mess, "Index '%d' out of range [1:%d]", int1, int2);
  1908. X        break;
  1909. X    case lOPEN_ERROR:
  1910. X        sprintf(mess, "Can't open dump-file '%s'\n", str1);
  1911. X        break;
  1912. X    case lWRONG_ORDER:
  1913. X        sprintf(mess, "Parameter 'order' has wrong value : %d", int1);
  1914. X        break;
  1915. X    case lWRONG_THEORY:
  1916. X        sprintf(mess, "Parameter 'theory' has wrong value : %d", int1);
  1917. X        break;
  1918. X    }
  1919. X
  1920. X    fpError = fopen(lERROR_FILE, "a");
  1921. X    if (fpError == NULL) {
  1922. X        fprintf(stderr, "Can't open error-file '%s'\n", lERROR_FILE);
  1923. X        fprintf(stderr, "Error, '%s': %s\n", str, mess);
  1924. X    } else {
  1925. X        fprintf(fpError, "Error, '%s': %s\n", str, mess);
  1926. X        fclose(fpError);
  1927. X    }
  1928. X#endif
  1929. X}
  1930. X
  1931. X#ifdef ANSI
  1932. Xstatic int
  1933. XsetWhchNode(int id, int which, char *fname)
  1934. X#else
  1935. Xstatic int
  1936. XsetWhchNode(id, which, fname)
  1937. Xint    id, which;
  1938. Xchar    *fname;
  1939. X#endif
  1940. X{
  1941. X    ListPtr        list;
  1942. X    static int    set[] = { lFIRST, lNEXT, lCURRENT, lPREVIOUS, lLAST };
  1943. X
  1944. X        /* check parameters */
  1945. X    if ((list = getAddress(id)) == NULL) {
  1946. X        lError(fname, lUNKNOWN_ID, id, 0, NULL);
  1947. X        return(lUNKNOWN_ID);
  1948. X    }
  1949. X    if (list->n == 0) {
  1950. X        lError(fname, lEMPTY_LIST, id, 0, NULL);
  1951. X        return(lEMPTY_LIST);
  1952. X    }
  1953. X    if (intInSet(which, set, 5) != 0) {
  1954. X        lError(fname, lWRONG_WHICH, which, 0, NULL);
  1955. X        return(lWRONG_WHICH);
  1956. X    }
  1957. X
  1958. X        /* search for requested node */
  1959. X    switch (which) {
  1960. X    case lFIRST:
  1961. X        list->current = list->first;
  1962. X        break;
  1963. X    case lNEXT:
  1964. X        if ((list->current)->nxt == NULL) {
  1965. X            lError(fname, lEOL, id, 0, NULL);
  1966. X            return(lEOL);
  1967. X        }
  1968. X        list->current = (list->current)->nxt;
  1969. X        break;
  1970. X    case lCURRENT:
  1971. X        break;
  1972. X    case lPREVIOUS:
  1973. X        if (list->sd != lDOUBLY) {
  1974. X            lError(fname, lNOT_DOUBLY, id, 0, NULL);
  1975. X            return(lNOT_DOUBLY);
  1976. X        }
  1977. X        if ((list->current)->prv == NULL) {
  1978. X            lError(fname, lEOL, id, 0, NULL);
  1979. X            return(lEOL);
  1980. X        }
  1981. X        list->current = (list->current)->prv;
  1982. X        break;
  1983. X    case lLAST:
  1984. X        list->current = list->last;
  1985. X        break;
  1986. X    }
  1987. X
  1988. X    return(lSUCCESS);
  1989. X}
  1990. X
  1991. X#ifdef ANSI
  1992. Xstatic int
  1993. XsetIndxNode(int id, int index, char *fname)
  1994. X#else
  1995. Xstatic int
  1996. XsetIndxNode(id, index, fname)
  1997. Xint    id, index;
  1998. Xchar    *fname;
  1999. X#endif
  2000. X{
  2001. X    ListPtr    list;
  2002. X    int    i;
  2003. X
  2004. X        /* check parameters */
  2005. X    if ((list = getAddress(id)) == NULL) {
  2006. X        lError(fname, lUNKNOWN_ID, id, 0, NULL);
  2007. X        return(lUNKNOWN_ID);
  2008. X    }
  2009. X    if (list->n == 0) {
  2010. X        lError(fname, lEMPTY_LIST, id, 0, NULL);
  2011. X        return(lEMPTY_LIST);
  2012. X    }
  2013. X    if (index < 1 || list->n < index) {
  2014. X        lError(fname, lWRONG_INDEX, index, list->n, NULL);
  2015. X        return(lWRONG_INDEX);
  2016. X    }
  2017. X
  2018. X    if (index == 1)
  2019. X        list->current = list->first;
  2020. X    else if (index == list->n)
  2021. X        list->current = list->last;
  2022. X    else {
  2023. X        list->current = list->first;
  2024. X        for (i=1; i<index; i++)
  2025. X            list->current = (list->current)->nxt;
  2026. X    }
  2027. X
  2028. X    return(lSUCCESS);
  2029. X}
  2030. X
  2031. X/* local function for QUICK sort */
  2032. X#ifdef ANSI
  2033. Xstatic int
  2034. Xpartition(NodePtr *array, int order, Func func, int lb, int ub, int *pj)
  2035. X#else
  2036. Xstatic int
  2037. Xpartition(array, order, func, lb, ub, pj)
  2038. XNodePtr    *array;
  2039. Xint    order, lb, ub, *pj;
  2040. XFunc    func;
  2041. X#endif
  2042. X{
  2043. X    int    down, up, cmp;
  2044. X    NodePtr    temp, a;
  2045. X
  2046. X    a = array[lb];
  2047. X    up = ub;
  2048. X    down = lb;
  2049. X
  2050. X    while (down < up) {
  2051. X        cmp = (*func)(array[down]->data, a->data);
  2052. X        while (down < ub
  2053. X         && ((order == lASCENDING && (cmp == l1LT2 || cmp == lSAME))
  2054. X         || (order == lDESCENDING && (cmp == l2LT1 || cmp == lSAME)))) {
  2055. X            down++;
  2056. X            cmp = (*func)(array[down]->data, a->data);
  2057. X        }
  2058. X        cmp = (*func)(array[up]->data, a->data);
  2059. X        while ((order == lASCENDING && cmp == l2LT1)
  2060. X         || (order == lDESCENDING && cmp == l1LT2)) {
  2061. X            up--;
  2062. X            cmp = (*func)(array[up]->data, a->data);
  2063. X        }
  2064. X
  2065. X        if (down < up) {    /* interchange */
  2066. X            temp = array[down];
  2067. X            array[down] = array[up];
  2068. X            array[up] = temp;
  2069. X        }
  2070. X    }
  2071. X    array[lb] = array[up];
  2072. X    array[up] = a;
  2073. X    *pj = up;
  2074. X}
  2075. X
  2076. X/* local function for QUICK sort */
  2077. X#ifdef ANSI
  2078. Xstatic int
  2079. Xstack_empty(int id)
  2080. X#else
  2081. Xstatic int
  2082. Xstack_empty(id)
  2083. Xint    id;
  2084. X#endif
  2085. X{
  2086. X    int    sd, cc, n;
  2087. X
  2088. X        /* check to see if linked list exists */
  2089. X    if (lInfo(id, &sd, &cc, &n) == lUNKNOWN_ID)
  2090. X        return(1);    /* linked list is non-existant */
  2091. X    if (n == 0)
  2092. X        return(1);
  2093. X    return(0);
  2094. X}
  2095. X
  2096. X/* ---------- static local functions (~anita/Tools/Clib) -------------------- */
  2097. X
  2098. X/* check if integer belongs to set of integers */
  2099. Xstatic int
  2100. XintInSet(intgr, set, set_n)
  2101. Xint    intgr, *set, set_n;
  2102. X{
  2103. X    int    i = 0;
  2104. X
  2105. X    while (set[i] != intgr && i < set_n)
  2106. X        i++;
  2107. X
  2108. X        /* 0 = yes, 1 = no */
  2109. X    return((i == set_n) ? 1 : 0);
  2110. X}
  2111. END_OF_FILE
  2112.   if test 40715 -ne `wc -c <'list.c'`; then
  2113.     echo shar: \"'list.c'\" unpacked with wrong size!
  2114.   fi
  2115.   # end of 'list.c'
  2116. fi
  2117. if test -f 'sorted.c' -a "${1}" != "-c" ; then 
  2118.   echo shar: Will not clobber existing file \"'sorted.c'\"
  2119. else
  2120.   echo shar: Extracting \"'sorted.c'\" \(7970 characters\)
  2121.   sed "s/^X//" >'sorted.c' <<'END_OF_FILE'
  2122. X#include    <stdio.h>
  2123. X#include    <string.h>
  2124. X#include    "list.h"
  2125. X
  2126. Xstatic void    addPersonSorted(), addPerson();
  2127. Xstatic int    fndNxtPerson(), sortPerson(), compare();
  2128. X
  2129. Xtypedef struct person {
  2130. X    char    lastname[15];
  2131. X    char    firstname[15];
  2132. X} Person, *PersonPtr;
  2133. Xint    personSz = sizeof(Person);
  2134. X
  2135. Xmain()
  2136. X{
  2137. X    Person    person;
  2138. X    int    id, code;
  2139. X
  2140. X/* ------- first solution --------------------------------------------------- */
  2141. Xfprintf(stdout, "..... Insert sorted by last name .....\n");
  2142. X    id = lDef(lSINGLY, lCHAIN);
  2143. X    addPersonSorted(id, "Ernie", "Makris");
  2144. X    addPersonSorted(id, "Anita", "Eijs");
  2145. X    addPersonSorted(id, "John", "Johnson");
  2146. X    addPersonSorted(id, "Bart", "Simpson");
  2147. X    addPersonSorted(id, "James", "Bond");
  2148. X    addPersonSorted(id, "Al", "Bundy");
  2149. X
  2150. X    code = lGetNode(id, lFIRST, &person, personSz);
  2151. X    while (code != lEOL && code != lEMPTY_LIST) {
  2152. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2153. X        code = lGetNode(id, lNEXT, &person, personSz);
  2154. X    }
  2155. X    code = lDel(id);
  2156. X
  2157. X/* ------- second solution -------------------------------------------------- */
  2158. Xfprintf(stdout, "..... Insert unsorted .....\n");
  2159. X    id = lDef(lSINGLY, lCHAIN);
  2160. X    addPerson(id, "Ernie", "Makris");
  2161. X    addPerson(id, "Anita", "Eijs");
  2162. X    addPerson(id, "John", "Johnson");
  2163. X    addPerson(id, "Bart", "Simpson");
  2164. X    addPerson(id, "James", "Bond");
  2165. X    addPerson(id, "Al", "Bundy");
  2166. X
  2167. X    code = lGetNode(id, lFIRST, &person, personSz);
  2168. X    while (code != lEOL && code != lEMPTY_LIST) {
  2169. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2170. X        code = lGetNode(id, lNEXT, &person, personSz);
  2171. X    }
  2172. X
  2173. Xfprintf(stdout, "..... Sort by last name .....\n");
  2174. X    id = sortPerson(id);
  2175. X
  2176. X    code = lGetNode(id, lFIRST, &person, personSz);
  2177. X    while (code != lEOL && code != lEMPTY_LIST) {
  2178. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2179. X        code = lGetNode(id, lNEXT, &person, personSz);
  2180. X    }
  2181. X
  2182. X    code = lDel(id);
  2183. X
  2184. X/* ------- third solution --------------------------------------------------- */
  2185. Xfprintf(stdout, "..... Insert unsorted .....\n");
  2186. X    id = lDef(lSINGLY, lCHAIN);
  2187. X    addPerson(id, "Ernie", "Makris");
  2188. X    addPerson(id, "Anita", "Eijs");
  2189. X    addPerson(id, "John", "Johnson");
  2190. X    addPerson(id, "Bart", "Simpson");
  2191. X    addPerson(id, "James", "Bond");
  2192. X    addPerson(id, "Al", "Bundy");
  2193. X
  2194. X    code = lGetNode(id, lFIRST, &person, personSz);
  2195. X    while (code != lEOL && code != lEMPTY_LIST) {
  2196. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2197. X        code = lGetNode(id, lNEXT, &person, personSz);
  2198. X    }
  2199. X
  2200. Xfprintf(stdout, "..... Sort by last name ..... Bubble ASCENDING .....\n");
  2201. X    code = lSort(id, lASCENDING, lBUBBLE, compare);
  2202. X
  2203. X    code = lGetNode(id, lFIRST, &person, personSz);
  2204. X    while (code != lEOL && code != lEMPTY_LIST) {
  2205. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2206. X        code = lGetNode(id, lNEXT, &person, personSz);
  2207. X    }
  2208. X
  2209. Xfprintf(stdout, "..... Sort by last name ..... Bubble DESCENDING .....\n");
  2210. X    code = lSort(id, lDESCENDING, lBUBBLE, compare);
  2211. X
  2212. X    code = lGetNode(id, lFIRST, &person, personSz);
  2213. X    while (code != lEOL && code != lEMPTY_LIST) {
  2214. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2215. X        code = lGetNode(id, lNEXT, &person, personSz);
  2216. X    }
  2217. X
  2218. Xfprintf(stdout, "..... Sort by last name ..... Heap ASCENDING .....\n");
  2219. X    code = lSort(id, lASCENDING, lHEAP, compare);
  2220. X
  2221. X    code = lGetNode(id, lFIRST, &person, personSz);
  2222. X    while (code != lEOL && code != lEMPTY_LIST) {
  2223. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2224. X        code = lGetNode(id, lNEXT, &person, personSz);
  2225. X    }
  2226. X
  2227. Xfprintf(stdout, "..... Sort by last name ..... Heap DESCENDING .....\n");
  2228. X    code = lSort(id, lDESCENDING, lHEAP, compare);
  2229. X
  2230. X    code = lGetNode(id, lFIRST, &person, personSz);
  2231. X    while (code != lEOL && code != lEMPTY_LIST) {
  2232. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2233. X        code = lGetNode(id, lNEXT, &person, personSz);
  2234. X    }
  2235. X
  2236. Xfprintf(stdout, "..... Sort by last name ..... Insert ASCENDING .....\n");
  2237. X    code = lSort(id, lASCENDING, lINSERT, compare);
  2238. X
  2239. X    code = lGetNode(id, lFIRST, &person, personSz);
  2240. X    while (code != lEOL && code != lEMPTY_LIST) {
  2241. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2242. X        code = lGetNode(id, lNEXT, &person, personSz);
  2243. X    }
  2244. X
  2245. Xfprintf(stdout, "..... Sort by last name ..... Insert DESCENDING .....\n");
  2246. X    code = lSort(id, lDESCENDING, lINSERT, compare);
  2247. X
  2248. X    code = lGetNode(id, lFIRST, &person, personSz);
  2249. X    while (code != lEOL && code != lEMPTY_LIST) {
  2250. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2251. X        code = lGetNode(id, lNEXT, &person, personSz);
  2252. X    }
  2253. X
  2254. Xfprintf(stdout, "..... Sort by last name ..... Quick ASCENDING .....\n");
  2255. X    code = lSort(id, lASCENDING, lQUICK, compare);
  2256. X
  2257. X    code = lGetNode(id, lFIRST, &person, personSz);
  2258. X    while (code != lEOL && code != lEMPTY_LIST) {
  2259. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2260. X        code = lGetNode(id, lNEXT, &person, personSz);
  2261. X    }
  2262. X
  2263. Xfprintf(stdout, "..... Sort by last name ..... Quick DESCENDING .....\n");
  2264. X    code = lSort(id, lDESCENDING, lQUICK, compare);
  2265. X
  2266. X    code = lGetNode(id, lFIRST, &person, personSz);
  2267. X    while (code != lEOL && code != lEMPTY_LIST) {
  2268. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2269. X        code = lGetNode(id, lNEXT, &person, personSz);
  2270. X    }
  2271. X
  2272. Xfprintf(stdout, "..... Sort by last name ..... Selection ASCENDING .....\n");
  2273. X    code = lSort(id, lASCENDING, lSELECTION, compare);
  2274. X
  2275. X    code = lGetNode(id, lFIRST, &person, personSz);
  2276. X    while (code != lEOL && code != lEMPTY_LIST) {
  2277. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2278. X        code = lGetNode(id, lNEXT, &person, personSz);
  2279. X    }
  2280. X
  2281. Xfprintf(stdout, "..... Sort by last name ..... Selection DESCENDING .....\n");
  2282. X    code = lSort(id, lDESCENDING, lSELECTION, compare);
  2283. X
  2284. X    code = lGetNode(id, lFIRST, &person, personSz);
  2285. X    while (code != lEOL && code != lEMPTY_LIST) {
  2286. X        fprintf(stdout, "%s, %s\n", person.lastname, person.firstname);
  2287. X        code = lGetNode(id, lNEXT, &person, personSz);
  2288. X    }
  2289. X
  2290. X    code = lDel(id);
  2291. X}
  2292. X
  2293. Xstatic void
  2294. XaddPersonSorted(id, first, last)
  2295. Xint    id;
  2296. Xchar    *first, *last;
  2297. X{
  2298. X    Person    person, new;
  2299. X    char    tmp[15];
  2300. X    int    code;
  2301. X
  2302. X        /* find next last name */
  2303. X    strcpy(&tmp[0], last);
  2304. X    code = lFndNode(id, lFIRST, fndNxtPerson, &tmp[0], &person, personSz);
  2305. X
  2306. X    strcpy(new.lastname, last);
  2307. X    strcpy(new.firstname, first);
  2308. X
  2309. X        /* insert data in alphabetical order */
  2310. X    if (code == lEMPTY_LIST || code == lFIRST)
  2311. X        code = lInsNode(id, lFIRST, &new, personSz, 0);
  2312. X    else if (code == lNOT_FOUND)
  2313. X        code = lInsNode(id, lLAST, &new, personSz, 0);
  2314. X    else
  2315. X        code = lInsNode(id, lBEFORE, &new, personSz, 0);
  2316. X}
  2317. X
  2318. X/* find next by specified last name before which specified name must be */
  2319. X/* inserted (alphabetical order) */
  2320. Xstatic int
  2321. Xcompare(p1, p2, order)
  2322. XPersonPtr    p1, p2;
  2323. Xint        order;
  2324. X{
  2325. X    int    k = strcmp(p1->lastname, p2->lastname);
  2326. X
  2327. X    if (k == 0)
  2328. X        return(lSAME);
  2329. X    else if (k > 0)
  2330. X        return(l2LT1);
  2331. X    else if (k < 0)
  2332. X        return(l1LT2);
  2333. X}
  2334. X
  2335. X/* find next by specified last name before which specified name must be */
  2336. X/* inserted (alphabetical order) */
  2337. Xstatic int
  2338. XfndNxtPerson(last, data)
  2339. Xchar        *last;
  2340. XPersonPtr    data;
  2341. X{
  2342. X    if (strcmp(last, data->lastname) < 0)
  2343. X        return(lFOUND);
  2344. X    else
  2345. X        return(lNOT_FOUND);
  2346. X}
  2347. X
  2348. Xstatic void
  2349. XaddPerson(id, first, last)
  2350. Xint    id;
  2351. Xchar    *first, *last;
  2352. X{
  2353. X    Person    new;
  2354. X    int    code;
  2355. X
  2356. X    strcpy(new.lastname, last);
  2357. X    strcpy(new.firstname, first);
  2358. X    code = lInsNode(id, lLAST, &new, personSz, 0);
  2359. X}
  2360. X
  2361. Xstatic int
  2362. XsortPerson(id)
  2363. Xint    id;
  2364. X{
  2365. X    Person    person, next;
  2366. X    char    tmp[15];
  2367. X    int    code, id2;
  2368. X
  2369. X    id2 = lDef(lSINGLY, lCHAIN);
  2370. X
  2371. X    code = lGetNode(id, lFIRST, &person, personSz);
  2372. X    while (code != lEOL && code != lEMPTY_LIST) {
  2373. X
  2374. X            /* find next last name */
  2375. X        strcpy(&tmp[0], person.lastname);
  2376. X        code = lFndNode(id2, lFIRST, fndNxtPerson, &tmp[0], &next,
  2377. X            personSz);
  2378. X
  2379. X            /* insert data in alphabetical order */
  2380. X        if (code == lEMPTY_LIST || code == lFIRST)
  2381. X            code = lInsNode(id2, lFIRST, &person, personSz, 0);
  2382. X        else if (code == lNOT_FOUND)
  2383. X            code = lInsNode(id2, lLAST, &person, personSz, 0);
  2384. X        else
  2385. X            code = lInsNode(id2, lBEFORE, &person, personSz, 0);
  2386. X
  2387. X        code = lGetNode(id, lNEXT, &person, personSz);
  2388. X    }
  2389. X    code = lDel(id);
  2390. X    return(id2);
  2391. X}
  2392. END_OF_FILE
  2393.   if test 7970 -ne `wc -c <'sorted.c'`; then
  2394.     echo shar: \"'sorted.c'\" unpacked with wrong size!
  2395.   fi
  2396.   # end of 'sorted.c'
  2397. fi
  2398. echo shar: End of archive 1 \(of 2\).
  2399. cp /dev/null ark1isdone
  2400. MISSING=""
  2401. for I in 1 2 ; do
  2402.     if test ! -f ark${I}isdone ; then
  2403.     MISSING="${MISSING} ${I}"
  2404.     fi
  2405. done
  2406. if test "${MISSING}" = "" ; then
  2407.     echo You have unpacked both archives.
  2408.     rm -f ark[1-9]isdone
  2409. else
  2410.     echo You still must unpack the following archives:
  2411.     echo "        " ${MISSING}
  2412. fi
  2413. exit 0
  2414. exit 0 # Just in case...
  2415.