home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / compsrcs / unix / volume26 / uutraf / part04 < prev    next >
Encoding:
Text File  |  1993-05-07  |  39.3 KB  |  1,580 lines
  1. Newsgroups: comp.sources.unix
  2. From: decvax!concert.net!woods%robohack (Greg A. Woods)
  3. Subject: v26i239: uutraf - UUCP Traffic Analysis and Reporting, Part04/04
  4. Sender: unix-sources-moderator@efficacy.home.vix.com
  5. Approved: vixie@efficacy.home.vix.com
  6.  
  7. Submitted-By: decvax!concert.net!woods%robohack (Greg A. Woods)
  8. Posting-Number: Volume 26, Issue 239
  9. Archive-Name: uutraf/part04
  10.  
  11. #! /bin/sh
  12. # This is a shell archive.  Remove anything before this line, then unpack
  13. # it by saving it into a file and typing "sh file".  To overwrite existing
  14. # files, type "sh file -c".  You can also feed this as standard input via
  15. # unshar, or by typing "sh <file", e.g..  If this archive is complete, you
  16. # will see the following message at the end:
  17. #        "End of archive 4 (of 4)."
  18. # Contents:  dlst.shar
  19. # Wrapped by woods@robohack.uucp on Thu Nov 12 02:48:46 EST 1992
  20. PATH=/bin:/usr/bin:/usr/ucb ; export PATH
  21. if test -f 'dlst.shar' -a "${1}" != "-c" ; then 
  22.   echo shar: Will not clobber existing file \"'dlst.shar'\"
  23. else
  24. echo shar: Extracting \"'dlst.shar'\" \(36973 characters\)
  25. sed "s/^X//" >'dlst.shar' <<'END_OF_FILE'
  26. X#! /bin/sh
  27. X# This is a shell archive.  Remove anything before this line, then unpack
  28. X# it by saving it into a file and typing "sh file".  To overwrite existing
  29. X# files, type "sh file -c".  You can also feed this as standard input via
  30. X# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
  31. X# will see the following message at the end:
  32. X#        "End of shell archive."
  33. X# Contents:  README Makefile-dist dlst.3 dlst.h list.c alist.c llist.c
  34. X# Wrapped by woods@robohack on Sun Nov  8 16:36:52 1992
  35. XPATH=/bin:/usr/bin:/usr/ucb ; export PATH
  36. Xif test -f 'README' -a "${1}" != "-c" ; then 
  37. X  echo shar: Will not clobber existing file \"'README'\"
  38. Xelse
  39. Xecho shar: Extracting \"'README'\" \(1701 characters\)
  40. Xsed "s/^X//" >'README' <<'END_OF_FILE'
  41. XX
  42. XX    libdlst - dynamic lists
  43. XX
  44. XXThis is a simple set of C language tools for building lists.  It has
  45. XXbeen designed in an object-oriented fashion, and can be easily
  46. XXextended to offer support for all sorts of lists.  Currently a
  47. XXdoubly-linked list type, and an array-list type, are offered.
  48. XX
  49. XXSorry, but the documentation is a bit sparse yet....
  50. XX
  51. XXIf you wish add support for new types of lists, please examine dlst.h.
  52. XX
  53. XXNote that this code uses <sccsid.h>, <sysdefs.h>, and <libc.h>.  If
  54. XXyour compiler does not search the current directory for <>'ed files,
  55. XXthen you'll have to install these files in INCDIR or /usr/include, or
  56. XXwherever the "standard places" are, before you build the library.
  57. XX
  58. XXIf this package did not include the above required headers, you'll
  59. XXfind them with the package in which dlst was shipped (probably as
  60. XXexternhdr.shar).  Go back and install them first.
  61. XX
  62. XXYou should save a copy of the original Makefile, then edit it to your
  63. XXrequirements.  When you're ready, just type 'make'!  If all goes well,
  64. XXyou should be able to 'make install', and be ready to use the library.
  65. XX
  66. XXNOTE:    This library is a re-write of an idea presented in "Object
  67. XX    Oriented Programming in C", David Brumbaugh; The_C_Users_
  68. XX    Journal; July 1990, Vol. 8, No. 7.  The linked-list sort
  69. XX    routine in llist.c is used (i.e. translated to C from Pascal)
  70. XX    with apologies (though not many!) to R. Sedgewick, from his
  71. XX    book "Algorithms", 1983, p. 149.
  72. XX
  73. XXThis library is in the public domain.  Use as you see fit.
  74. XX
  75. XX#ident    "@(#)dlst:README    1.4    92/10/12 16:34:32 (woods)"
  76. XX--
  77. XX                        Greg A. Woods
  78. XX
  79. XXwoods@robohack.UUCP woods@Elegant.COM  VE3TCP    UniForum Canada & ECI
  80. XX+1 416 443-1734 [home] +1 416 362-XRSA [work]    Toronto, Ontario; CANADA
  81. XEND_OF_FILE
  82. Xif test 1701 -ne `wc -c <'README'`; then
  83. X    echo shar: \"'README'\" unpacked with wrong size!
  84. Xfi
  85. X# end of 'README'
  86. Xfi
  87. Xif test -f 'Makefile-dist' -a "${1}" != "-c" ; then 
  88. X  echo shar: Will not clobber existing file \"'Makefile-dist'\"
  89. Xelse
  90. Xecho shar: Extracting \"'Makefile-dist'\" \(3470 characters\)
  91. Xsed "s/^X//" >'Makefile-dist' <<'END_OF_FILE'
  92. XX#! /bin/make -f
  93. XX#
  94. XX#    a very simple Makefile for libdlst
  95. XX#
  96. XX
  97. XX#ident    "@(#)dlst:Makefile    1.6    92/10/12 16:34:09 (woods)"
  98. XX
  99. XXSHELL = /bin/sh
  100. XX
  101. XXLOCAL = /usr/local
  102. XX
  103. XXBINDIR = $(LOCAL)/bin
  104. XXLIBDIR = $(LOCAL)/lib
  105. XXINCDIR = $(LOCAL)/include
  106. XXMANEXT = 3
  107. XXMANDIR = $(LOCAL)/man/man$(MANEXT)
  108. XX
  109. XX# Select the right definition for your system, unless you are compiling on
  110. XX# one of the following:  SunOS, ULTRIX, AIX, XENIX.
  111. XX# 
  112. XX#    v7:    SYSTYPE= -DV7        /* UNTESTED "The Real Thing!"(tm) ;-) */
  113. XX#   any BSD:    SYSTYPE= -DBSD
  114. XX#    SysIII: SYSTYPE= -DSYSIII    /* UNTESTED */
  115. XX#    SysV:    SYSTYPE= -DSYSV         /* generic AT&T or USG unix */
  116. XX#    SysVr1:    SYSTYPE= -DSYSVR1    /* UNTESTED i.e. the original SysV */
  117. XX#    SysVr2:    SYSTYPE= -DSYSVR2    /* yes, 3b1'ers, this is you too! */
  118. XX#    SysVr3: SYSTYPE= -DSYSVR3
  119. XX#    SysVr4: SYSTYPE= -DSYSVR4
  120. XX#   any P1003.1:SYSTYPE= -D_POSIX_SOURCE
  121. XX#
  122. XXSYSTYPE        = -DSYSVR3
  123. XX
  124. XX# NOTE:  you'll have to define DUMB_VOID if your compiler doesn't fully
  125. XX# understand the 'void' keyword.  (The most common error indicating this
  126. XX# symptom is "operands of ':' have incompatible types" for invocations of the
  127. XX# lst_top()/lst_bottom() macros.)  If it doesn't understand 'void' at all,
  128. XX# then you should also define REDEF_VOID.
  129. XX#
  130. XX#DEFS = $(SYSTYPE) -DDUMB_VOID
  131. XX#DEFS = $(SYSTYPE) -DDUMB_VOID -DREDEF_VOID
  132. XX#
  133. XXDEFS = $(SYSTYPE)
  134. XX
  135. XX# Use 'make DEBUG=-DDEBUG' to compile in debugging code
  136. XX# Use 'make DEBUG=-DNDEBUG' to turn off assert()s
  137. XX#
  138. XXDEBUG = 
  139. XX
  140. XX# Use 'make OPTIM= SDB=-g' to build for a debugger
  141. XX#
  142. XXOPTIM = -O
  143. XXSDB = 
  144. XX
  145. XXCFLAGS = $(OPTIM) $(SDB) -I$(INCDIR) $(DEFS) $(DEBUG)
  146. XXLDFLAGS = -L$(LIBDIR)
  147. XX
  148. XX# Another sample:
  149. XX#
  150. XX#CFLAGS = $(OPTIM) $(SDB) -I$(LOCAL)/include $(DEBUG) $(DEFS) -pipe -ansi \
  151. XX#    -Wall -Wshadow -Wpointer-arith -Wcast-qual -Wwrite-strings \
  152. XX#    -Dscanf=DONT_USE_SCANF -Dgets=DONT_USE_GETS
  153. XX#CC = gcc
  154. XX
  155. XXLINTARGS = -ax
  156. XX
  157. XXLIB = dlst
  158. XXLIBRARY = lib$(LIB).a
  159. XXLINTLIB = llib-l$(LIB).ln
  160. XXMANPAGES = $(LIB).nro
  161. XX
  162. XXOBJECTS = list.o alist.o llist.o
  163. XXSOURCES = list.c alist.c llist.c
  164. XXINCLUDES = $(LIB).h
  165. XXOTHER = README Makefile-dist
  166. XXDOCS = $(LIB).3
  167. XX
  168. XX# for making distributions only!
  169. XX#
  170. XXEXTERN_HDRS = ../../head/sccsid.h ../../head/sysdefs.h ../../head/libc.h
  171. XX
  172. XXdefault: $(LIBRARY)
  173. XX
  174. XXall: $(LIBRARY) $(LINTLIB)
  175. XX
  176. XXlib$(LIB).a: $(OBJECTS)
  177. XX    ar ru $(LIBRARY) $(OBJECTS)
  178. XX    -ranlib $(LIBRARY)
  179. XX
  180. XXlist.o: $(INCLUDES)
  181. XXalist.o: $(INCLUDES)
  182. XXllist.o: $(INCLUDES)
  183. XX
  184. XXinstall:    $(LIBRARY) $(LINTLIB) $(INCLUDES) $(DOCS)
  185. XX    cp $(LIBRARY) $(LIBDIR)
  186. XX    cp llib-l$(LIB).ln $(LIBDIR)
  187. XX    cp $(INCLUDES) $(INCDIR)
  188. XX    cp $(DOCS) $(MANDIR)
  189. XX
  190. XXlintlibrary $(LINTLIB):    $(SOURCES) $(INCLUDES)
  191. XX    lint $(LINTARGS) -o $(LIB) $(DEFS) -I$(INCDIR) $(SOURCES)
  192. XX
  193. XXlint:
  194. XX    lint $(LINTARGS) -p $(DEFS) -I$(INCDIR) $(SOURCES)
  195. XX
  196. XXclean:
  197. XX    rm -f $(OBJECTS) core
  198. XX
  199. XXclobber: clean
  200. XX    rm -f $(LIBRARY) $(LINTLIB)
  201. XX
  202. XXshar: $(LIB).shar
  203. XX
  204. XX# using 'make dist' prevents ever patching Makefile-dist...
  205. XX#
  206. XXdist: $(LIB).shar Makefile-dist
  207. XX
  208. XXfulldist: fullshar Makefile-dist
  209. XX
  210. XXcleandist:
  211. XX    rm -f $(LIB).shar
  212. XX
  213. XXMakefile-dist:    Makefile
  214. XX    @echo "Are you sure? [<DEL> to abort] \c"; read junk
  215. XX    rm -f Makefile-dist
  216. XX    cp Makefile Makefile-dist
  217. XX
  218. XX$(LIB).shar: $(OTHER) $(DOCS) $(INCLUDES) $(SOURCES)
  219. XX    shar -b -t 'Please read the file README first' \
  220. XX        $(OTHER) $(DOCS) $(INCLUDES) $(SOURCES) > $(LIB).shar
  221. XX
  222. XXfullshar: $(OTHER) $(DOCS) $(INCLUDES) $(SOURCES) externhdr.shar
  223. XX    shar -b -t 'Please read the file README first' \
  224. XX        $(OTHER) $(DOCS) $(INCLUDES) $(SOURCES) externhdr.shar > $(LIB).shar
  225. XX
  226. XXexternhdr.shar: $(EXTERN_HDRS) Makefile
  227. XX    shar -b -t 'Please install in local include directory' \    
  228. XX        $(EXTERN_HDRS) > externhdr.shar
  229. XEND_OF_FILE
  230. Xif test 3470 -ne `wc -c <'Makefile-dist'`; then
  231. X    echo shar: \"'Makefile-dist'\" unpacked with wrong size!
  232. Xfi
  233. X# end of 'Makefile-dist'
  234. Xfi
  235. Xif test -f 'dlst.3' -a "${1}" != "-c" ; then 
  236. X  echo shar: Will not clobber existing file \"'dlst.3'\"
  237. Xelse
  238. Xecho shar: Extracting \"'dlst.3'\" \(6210 characters\)
  239. Xsed "s/^X//" >'dlst.3' <<'END_OF_FILE'
  240. XX'\"
  241. XX'\"    dlst.3 - dlst library manual page
  242. XX'\"
  243. XX'\" command-line control (-rXn) for the .TH arguments:
  244. XX.nr X
  245. XX.if \nX=0 .ds x} DLST 3 "Local Libraries" "\&"
  246. XX.if \nX=1 .ds x} DLST 3 "Local Libraries"
  247. XX.if \nX=2 .ds x} DLST 3 "" "\&"
  248. XX.if \nX=3 .ds x} DLST "" "" "\&"
  249. XX.\"
  250. XX.\"    Fixed-width "code" font.  (`.ds C CW')
  251. XX.\"
  252. XX.ds C CW
  253. XX.\".fp 7 \*C    \" you may need to load this font too
  254. XX.\"
  255. XX.\" Use this as .ft \*C (remember the .ft P)
  256. XX.\"
  257. XX.\" In-line select a font for programme text appearing `inline' in
  258. XX.\" the text.  Use the same selection choices as for code blocks.
  259. XX.\" Prepend `\&' in case the trailing arg starts w/ a period.
  260. XX.\"
  261. XX.\" Usage:
  262. XX.\"    .eP foo         (`foo' in code font)
  263. XX.\"    .eP foo mp      (`foomp', `foo' in code font, `mp' not)
  264. XX.\"    .eP foo mp ka   (`kafoomp', `foo' in code font, rest not)
  265. XX.\"
  266. XX.\" Sorry it's not too intuitive, but that's troff for ya!  Anything
  267. XX.\" better would be many lines of if's checking no. of args.
  268. XX.\"
  269. XX.de eP
  270. XX.    nh
  271. XX\&\\$3\c
  272. XX.    ft \\*C
  273. XX\\$1\fP\\$2\"            fixed-width font (not broke...)
  274. XX.    hy
  275. XX..
  276. XX.\"     A wee bit of neat stuff to get tabs to work with .ft \*C
  277. XX.\"
  278. XX.ft \*C
  279. XX.nr x \w'        '\" find width of 8 spaces.
  280. XX.ft P
  281. XX.rm DT
  282. XX.de DT\"default tabs
  283. XX.\" set tabs using width calculated above
  284. XX.ta \nxu +\nxu +\nxu +\nxu +\nxu +\nxu +\nxu +\nxu +\nxu +\nxu +\nxu +\nxu
  285. XX..
  286. XX.\"
  287. XX.TH \*(x}
  288. XX.SH NAME
  289. XXdlst: lst_\(**, alist_\(**, llist_\(** \- dynamic list operations
  290. XX.SH SYNOPSIS
  291. XX.nf
  292. XX.eP "cc ... -ldlst"
  293. XX.PP
  294. XX.eP "#include <sysdefs.h>"
  295. XX.eP "#include <sys/types.h>"
  296. XX.eP "#include <dlst.h>"
  297. XX.PP
  298. XX.eP "lst_t    \(**lst_new()"
  299. XX.eP "void    lst_destroy(list)"
  300. XX.eP "bool    lst_attop(list)"
  301. XX.eP "bool    lst_atbottom(list)"
  302. XX.eP "bool    lst_isempty(list)"
  303. XX.eP "bool    lst_add(list, datum)"
  304. XX.eP "bool    lst_find(list, datum, cmpfn)"
  305. XX.eP "bool    lst_prev(list)"
  306. XX.eP "bool    lst_next(list)"
  307. XX.eP "cmp_t    lst_cmp(list, datum_1, datum_2)"
  308. XX.eP "VOID    lst_top(list)"
  309. XX.eP "VOID    lst_bottom(list)"
  310. XX.eP "VOID    lst_seek(list, where, from)"
  311. XX.eP "VOID    lst_replace(list, datum)"
  312. XX.eP "VOID    lst_delete(list)"
  313. XX.eP "VOID    lst_display(list, dispfn)"
  314. XX.eP "UnivPtr    lst_current(list)"
  315. XX.eP "UnivPtr    lst_car(list)"
  316. XX.eP "UnivPtr    lst_cdr(list)"
  317. XX.eP "size_t    lst_total(list)"
  318. XX.eP "size_t    lst_ltell(list)"
  319. XX.PP
  320. XX.eP "llst_t    \(**llst_new()"
  321. XX.eP "void    llst_destroy(llist)"
  322. XX.eP "bool    llst_attop(llist)"
  323. XX.eP "bool    llst_atbottom(llist)"
  324. XX.eP "bool    llst_isempty(llist)"
  325. XX.eP "bool    llst_add(llist, datum)"
  326. XX.eP "bool    llst_find(llist, datum, cmpfn)"
  327. XX.eP "bool    llst_prev(llist)"
  328. XX.eP "bool    llst_next(llist)"
  329. XX.eP "cmp_t    llst_cmp(llist, datum_1, datum_2)"
  330. XX.eP "VOID    llst_top(llist)"
  331. XX.eP "VOID    llst_bottom(llist)"
  332. XX.eP "VOID    llst_seek(llist, where, from)"
  333. XX.eP "VOID    llst_replace(llist, datum)"
  334. XX.eP "VOID    llst_delete(llist)"
  335. XX.eP "VOID    llst_display(llist, dispf)"
  336. XX.eP "UnivPtr    llst_current(llist)"
  337. XX.eP "UnivPtr    llst_car(llist)"
  338. XX.eP "UnivPtr    llst_cdr(llist)"
  339. XX.eP "size_t    llst_total(llist)"
  340. XX.eP "size_t    llst_ltell(llist)"
  341. XX.eP "VOID    llst_sort(llist, cmpfn)"
  342. XX.PP
  343. XX.eP "alst_t    \(**alst_new()"
  344. XX.eP "void    alst_destroy(alist)"
  345. XX.eP "bool    alst_attop(alist)"
  346. XX.eP "bool    alst_atbottom(alist)"
  347. XX.eP "bool    alst_isempty(alist)"
  348. XX.eP "bool    alst_add(alist, datum)"
  349. XX.eP "bool    alst_find(alist, datum, cmpfn)"
  350. XX.eP "bool    alst_prev(alist)"
  351. XX.eP "bool    alst_next(alist)"
  352. XX.eP "cmp_t    alst_cmp(alist, datum_1, datum_2)"
  353. XX.eP "VOID    alst_top(alist)"
  354. XX.eP "VOID    alst_seek(alist, where, from)"
  355. XX.eP "VOID    alst_bottom(alist)"
  356. XX.eP "VOID    alst_replace(alist, datum)"
  357. XX.eP "VOID    alst_delete(alist)"
  358. XX.eP "VOID    alst_display(alist, dispfn)"
  359. XX.eP "UnivPtr    alst_current(alist)"
  360. XX.eP "UnivPtr    alst_car(alist)"
  361. XX.eP "UnivPtr    alst_cdr(alist)"
  362. XX.eP "size_t    alst_total(alist)"
  363. XX.eP "size_t    alst_ltell(alist)"
  364. XX.PP
  365. XX.fi
  366. XXThe following declarations describe the argument types for the above
  367. XXfunctions:
  368. XX.nf
  369. XX.eP "lst_t    \(**list;"
  370. XX.eP "llst_t    \(**llist;"
  371. XX.eP "alst_t    \(**alist;"
  372. XX.eP "UnivPtr    datum, datum_1, datum_2;"
  373. XX.eP "cmp_t    (\(**cmpfn)(UnivPtr datum_1, UnivPtr datum_2);"
  374. XX.eP "void    (\(**dispfn)(UnivPtr datum);"
  375. XX.eP "size_t    where;    /\(** list element "index" \(**/"
  376. XX.eP "int    from;    /\(** ala lseek()'s SEEK_SET, etc. \(**/"
  377. XX.fi
  378. XX.SH DESCRIPTION
  379. XX.\" arguments in bold, functions in italic,
  380. XXFor the time being, I'm going to assume you can intuit the meaning of
  381. XXthe functions based on their name and return value.  At some point
  382. XXI'm going to experiment with some literate programming techniques to
  383. XXprovide documentation for each function.  There's always the ultimate
  384. XXsource of information and enlightenment!
  385. XX.eP ":-)"
  386. XX.SS "Generic Lists"
  387. XXThe macros prefixed with
  388. XX.eP lst_
  389. XXform the interface to the generic list object type.
  390. XX.SS "Double-Linked Lists"
  391. XXThe macros prefixed with
  392. XX.eP llst_
  393. XXform the interface to the doubly-linked list object type.
  394. XX.SS "Lists in Arrays"
  395. XXThe macros prefixed with
  396. XX.eP lst_
  397. XXform the interface to the array list object type.
  398. XX.\".SH RETURNS
  399. XX.SH CAVEATS
  400. XXThis library was written as an experiment in object oriented
  401. XXprogramming using standard C, and thus may not be the most optimal
  402. XXrepresentation of they underlying data structures.  For example, most
  403. XXfunction calls are through a jump table, and the user-visible calls
  404. XXare in fact pre-processor macros.
  405. XX.PP
  406. XXThe
  407. XX.eP alst_t
  408. XXfunctions are not complete, and must be further sub-classed to
  409. XXimplement any useful function.  They are provided only as an example.
  410. XX.\".SH FILES
  411. XX.\" lists of associated files
  412. XX.SH NOTES
  413. XXThis library depends upon a custom localisation header
  414. XX.eP <sysdefs.h>
  415. XXto make it portable to non-ANSI C compilers.  Particular attention
  416. XXmust be paid to the use of the keyword
  417. XX.eP void
  418. XXand the macro
  419. XX.eP VOID .
  420. XX.\".SH "SEE ALSO"
  421. XX.\" just plain old list of comma-separated function(S).
  422. XX.SH AUTHOR
  423. XXGreg A. Woods
  424. XX.eP <woods@robohack.UUCP>
  425. XX.SH HISTORY
  426. XXThis library began life as a set of routines to wrap around the
  427. XXlinked-list sort routine, and then was re-written using an idea
  428. XXpresented in ``Object Oriented Programming in C'', by David Brumbaugh;
  429. XX.IR "The C Users Journal" ;
  430. XXJuly 1990, Vol. 8, No. 7.
  431. XX.PP
  432. XXThe linked-list sort routine in
  433. XX.eP llist.c
  434. XXis used (i.e. translated to C from Pascal) with apologies (though not
  435. XXmany! -- the translation was ugly!) to R. Sedgewick, from his book
  436. XX.IR "Algorithms" ,
  437. XX1983, p. 149.
  438. XX.SH COPYRIGHT
  439. XXThe
  440. XX.B dlst
  441. XXlibrary and this manual page are in the Public Domain.
  442. XX.PP
  443. XX.eP "#ident    ``@(#)dlst:dlst.3    1.3    92/07/12 15:04:31 (woods)''
  444. XEND_OF_FILE
  445. Xif test 6210 -ne `wc -c <'dlst.3'`; then
  446. X    echo shar: \"'dlst.3'\" unpacked with wrong size!
  447. Xfi
  448. X# end of 'dlst.3'
  449. Xfi
  450. Xif test -f 'dlst.h' -a "${1}" != "-c" ; then 
  451. X  echo shar: Will not clobber existing file \"'dlst.h'\"
  452. Xelse
  453. Xecho shar: Extracting \"'dlst.h'\" \(5567 characters\)
  454. Xsed "s/^X//" >'dlst.h' <<'END_OF_FILE'
  455. XX/*
  456. XX *    dlst.h - dynamic list classes
  457. XX */
  458. XX
  459. XX#define SID_H    "@(#)dlst:dlst.h    1.5    92/07/12 14:59:15 (woods)"
  460. XX#define SID_NM    dlst_sccsid
  461. XX#include <sccsid.h>
  462. XX
  463. XX/* WARNING: these are bound to cause trouble for someone! */
  464. XX#ifndef DLST_HAVE_BOOL
  465. XXtypedef int    bool;        /* boolean result */
  466. XX#endif
  467. XX#ifndef DLST_HAVE_CMP_T
  468. XXtypedef int    cmp_t;        /* comparison result */
  469. XX#endif
  470. XX
  471. XX#ifndef TRUE
  472. XX# define TRUE    1
  473. XX#endif
  474. XX#ifndef FALSE
  475. XX# define FALSE    0
  476. XX#endif
  477. XX
  478. XX/*
  479. XX * generic list base class methods definition
  480. XX *
  481. XX * NOTE:  The proper way to do this is to define the arguments to the
  482. XX * methods with prototyping, but since that's not available we'll do it
  483. XX * below with a set of macros for "sending" the messages.
  484. XX */
  485. XX#define LIST_CLASS    \
  486. XX        bool    (*attop)(), \
  487. XX            (*atbottom)(), \
  488. XX            (*isempty)(), \
  489. XX            (*add)(), \
  490. XX            (*prev)(), \
  491. XX            (*next)(), \
  492. XX            (*seek)(), \
  493. XX            (*find)(); \
  494. XX        cmp_t    (*cmp)(); \
  495. XX        VOID    (*top)(), \
  496. XX            (*bottom)(), \
  497. XX            (*replace)(), \
  498. XX            (*delete)(), \
  499. XX            (*display)(); \
  500. XX        UnivPtr    (*current)(), \
  501. XX            (*cdr)(), \
  502. XX            (*car)(); \
  503. XX        size_t    (*total)(), \
  504. XX            (*ltell)();
  505. XX
  506. XXtypedef struct list {
  507. XX    LIST_CLASS
  508. XX} lst_t;
  509. XX
  510. XX/*
  511. XX * constructor and destructor
  512. XX */
  513. XXextern lst_t    *new_list();
  514. XXextern void    destroy_list();
  515. XX
  516. XX/*
  517. XX * method "messages"
  518. XX *
  519. XX * NOTE:  make sure we don't de-reference NULL!
  520. XX */
  521. XX#define lst_new            new_list
  522. XX#define lst_destroy(list)    destroy_list(list)
  523. XX#define lst_attop(list)        ((list) ? ((*((list)->attop))(list)) : 0)
  524. XX#define lst_atbottom(list)    ((list) ? ((*((list)->atbottom))(list)) : 0)
  525. XX#define lst_isempty(list)    ((list) ? ((*((list)->isempty))(list)) : 0)
  526. XX#define lst_add(list, el)    ((list) ? ((*((list)->add))(list, el)) : 0)
  527. XX#define lst_find(list, el, fn)    ((list) ? ((*((list)->find))(list, el, fn)) : 0)
  528. XX#define lst_cmp(list, a, b)    ((list) ? ((*((list)->cmp))(list, a, b)) : (cmp_t) 0)
  529. XX#define lst_prev(list)        ((list) ? ((*((list)->prev))(list)) : 0)
  530. XX#define lst_next(list)        ((list) ? ((*((list)->next))(list)) : 0)
  531. XX#define lst_top(list)        ((list) ? ((*((list)->top))(list)) : (VOID) 0)
  532. XX#define lst_bottom(list)    ((list) ? ((*((list)->bottom))(list)) : (VOID) 0)
  533. XX#define lst_seek(list, w, s)    ((list) ? ((*((list)->seek))(list, w, s)) : 0)
  534. XX#define lst_replace(list, el)    ((list) ? ((*((list)->replace))(list, el)) : (VOID) 0)
  535. XX#define lst_delete(list)    ((list) ? ((*((list)->delete))(list)) : (VOID) 0)
  536. XX#define lst_display(list, f)    ((list) ? ((*((list)->display))(list, f)) : (VOID) 0)
  537. XX#define lst_current(list)    ((list) ? ((*((list)->current))(list)) : (UnivPtr) 0)
  538. XX#define lst_car(list)        ((list) ? ((*((list)->car))(list)) : (UnivPtr) 0)
  539. XX#define lst_cdr(list)        ((list) ? ((*((list)->cdr))(list)) : (UnivPtr) 0)
  540. XX#define lst_total(list)        ((list) ? ((*((list)->total))(list)) : (size_t) 0)
  541. XX#define lst_ltell(list)        ((list) ? ((*((list)->ltell))(list)) : (size_t) 0)
  542. XX
  543. XX/*
  544. XX * a doubly linked list sub-class methods definition.
  545. XX *
  546. XX * NOTE:  data elements are also defined.
  547. XX */
  548. XXtypedef struct llist_element {
  549. XX    struct llist_element    *nxt;
  550. XX    struct llist_element    *prv;
  551. XX    UnivPtr            d;
  552. XX} llel_t;
  553. XX
  554. XX#define LINKED_LIST_CLASS \
  555. XX        LIST_CLASS \
  556. XX        VOID    (*sort)(); \
  557. XX        llel_t    *first_el; \
  558. XX        llel_t    *last_el; \
  559. XX        llel_t    *curr_el; \
  560. XX        size_t    num_el;
  561. XX
  562. XXtypedef struct llist {
  563. XX    LINKED_LIST_CLASS
  564. XX} llst_t;
  565. XX
  566. XX/*
  567. XX * constructor and destructor
  568. XX */
  569. XXextern llst_t    *new_llist();
  570. XXextern void    destroy_llist();
  571. XX
  572. XX/*
  573. XX * method "messages"
  574. XX */
  575. XX#define llst_new        new_llist
  576. XX#define llst_destroy(list)    destroy_llist(list)
  577. XX#define llst_attop(list)    lst_attop(list)
  578. XX#define llst_atbottom(list)    lst_atbottom(list)
  579. XX#define llst_isempty(list)    lst_isempty(list)
  580. XX#define llst_add(list, el)    lst_add(list, el)
  581. XX#define llst_find(list, el, fn)    lst_find(list, el, fn)
  582. XX#define llst_cmp(list, a, b)    lst_cmp(list, a, b)
  583. XX#define llst_prev(list)        lst_prev(list)
  584. XX#define llst_next(list)        lst_next(list)
  585. XX#define llst_top(list)        lst_top(list)
  586. XX#define llst_seek(list, w, s)    lst_seek(list, w, s)
  587. XX#define llst_bottom(list)    lst_bottom(list)
  588. XX#define llst_replace(list, el)    lst_replace(list, el)
  589. XX#define llst_delete(list)    lst_delete(list)
  590. XX#define llst_display(list, f)    lst_display(list, f)
  591. XX#define llst_current(list)    lst_current(list)
  592. XX#define llst_car(list)        lst_car(list)
  593. XX#define llst_cdr(list)        lst_cdr(list)
  594. XX#define llst_total(list)    lst_total(list)
  595. XX#define llst_ltell(list)    lst_ltell(list)
  596. XX#define llst_sort(list, f)    ((list) ? ((*((list)->sort))(list, f)) : (VOID) 0)
  597. XX
  598. XX/*
  599. XX * an array list sub-class methods definition
  600. XX *
  601. XX * NOTE:  data elements are also defined.
  602. XX */
  603. XX#define ARRAY_LIST_CLASS \
  604. XX        LIST_CLASS \
  605. XX        size_t    curr_el; \
  606. XX        size_t    num_el;
  607. XX
  608. XXtypedef struct alist {
  609. XX    ARRAY_LIST_CLASS
  610. XX} alst_t;
  611. XX
  612. XX/*
  613. XX * constructor and destructor
  614. XX */
  615. XXextern alst_t    *new_alist();
  616. XXextern void    destroy_alist();
  617. XX
  618. XX/*
  619. XX * method "messages"
  620. XX */
  621. XX#define alst_new        new_alist
  622. XX#define alst_destroy(list)    destroy_alist(list)
  623. XX#define alst_attop(list)    lst_attop(list)
  624. XX#define alst_atbottom(list)    lst_atbottom(list)
  625. XX#define alst_isempty(list)    lst_isempty(list)
  626. XX#define alst_add(list, el)    lst_add(list, el)
  627. XX#define alst_find(list, el, fn)    lst_find(list, el, fn)
  628. XX#define alst_cmp(list, a, b)    lst_cmp(list, a, b)
  629. XX#define alst_prev(list)        lst_prev(list)
  630. XX#define alst_next(list)        lst_next(list)
  631. XX#define alst_top(list)        lst_top(list)
  632. XX#define alst_seek(list, w, s)    lst_seek(list, w, s)
  633. XX#define alst_bottom(list)    lst_bottom(list)
  634. XX#define alst_replace(list, el)    lst_replace(list, el)
  635. XX#define alst_delete(list)    lst_delete(list)
  636. XX#define alst_display(list, f)    lst_display(list, f)
  637. XX#define alst_current(list)    lst_current(list)
  638. XX#define alst_car(list)        lst_car(list)
  639. XX#define alst_cdr(list)        lst_cdr(list)
  640. XX#define alst_total(list)    lst_total(list)
  641. XX#define alst_ltell(list)    lst_ltell(list)
  642. XEND_OF_FILE
  643. Xif test 5567 -ne `wc -c <'dlst.h'`; then
  644. X    echo shar: \"'dlst.h'\" unpacked with wrong size!
  645. Xfi
  646. X# end of 'dlst.h'
  647. Xfi
  648. Xif test -f 'list.c' -a "${1}" != "-c" ; then 
  649. X  echo shar: Will not clobber existing file \"'list.c'\"
  650. Xelse
  651. Xecho shar: Extracting \"'list.c'\" \(3792 characters\)
  652. Xsed "s/^X//" >'list.c' <<'END_OF_FILE'
  653. XX/*
  654. XX *    list.c - generic list class methods
  655. XX */
  656. XX
  657. XX#define SID    "@(#)dlst:list.c    1.5    92/10/03 23:37:50 (woods)"
  658. XX#include <sccsid.h>
  659. XX
  660. XX#if defined(USE_STDDEF) || REALSTDC || (__STDC__ - 0) == 1
  661. XX# include <stddef.h>    /* should do before sysdefs.h */
  662. XX#endif
  663. XX#include <sysdefs.h>    /* localisation helpers */
  664. XX#include <sys/types.h>    /* for size_t, if avail. */
  665. XX#include <stdio.h>    /* only for "FILE" used in <libc.h> */
  666. XX#include <assert.h>
  667. XX#if defined(USG) || defined(SYSV)
  668. XX# include <malloc.h>
  669. XX# include <memory.h>
  670. XX# include <unistd.h>
  671. XX#endif
  672. XX#include <libc.h>
  673. XX#include "dlst.h"
  674. XX
  675. XX/*
  676. XX * Sillyness to keep assigments of invalid_op from making noise
  677. XX */
  678. XXtypedef VOID    (*voidfn)();
  679. XXtypedef bool    (*boolfn)();
  680. XXtypedef cmp_t    (*cmp_tfn)();
  681. XXtypedef size_t    (*size_tfn)();
  682. XXtypedef UnivPtr    (*UnivPtrFn)();
  683. XX
  684. XXstatic void    invalid_op();
  685. XX
  686. XX/*
  687. XX * all must have the same types as in LIST_CLASS in list.h
  688. XX *
  689. XX * NOTE:  Not all of these are defined!
  690. XX */
  691. XXstatic bool    attop(),
  692. XX        atbottom(),
  693. XX        isempty(),
  694. XX        add(),
  695. XX        prev(),
  696. XX        next(),
  697. XX        seek(),
  698. XX        find();
  699. XXstatic    cmp_t    cmp();
  700. XXstatic    VOID    top(),
  701. XX        bottom(),
  702. XX        replace(),
  703. XX        delete(),
  704. XX        display();
  705. XXstatic    UnivPtr    current(),
  706. XX        cdr(),
  707. XX        car();
  708. XXstatic    size_t    total(),
  709. XX        ltell();
  710. XX
  711. XX/*
  712. XX *    safety feature
  713. XX */
  714. XXstatic void
  715. XXinvalid_op()
  716. XX{
  717. XX    assert(0);
  718. XX    return;        /* usually not reached! */
  719. XX}
  720. XX
  721. XX/*
  722. XX *    constructor
  723. XX */
  724. XXlst_t    *
  725. XXnew_list()
  726. XX{
  727. XX    lst_t    *new;
  728. XX
  729. XX    if ((new = (lst_t *) malloc(sizeof(lst_t))) == NULL)
  730. XX        return(NULL);
  731. XX
  732. XX    new->attop = (boolfn) invalid_op;
  733. XX    new->atbottom = (boolfn) invalid_op;
  734. XX    new->isempty = (boolfn) isempty;
  735. XX    new->add = (boolfn) invalid_op;
  736. XX    new->find = (boolfn) invalid_op;
  737. XX    new->cmp = (cmp_tfn) invalid_op;
  738. XX    new->prev = (boolfn) invalid_op;
  739. XX    new->next = (boolfn) invalid_op;
  740. XX    new->top = (voidfn) invalid_op;
  741. XX    new->bottom = (voidfn) invalid_op;
  742. XX    new->seek = seek;
  743. XX    new->replace = (voidfn) invalid_op;
  744. XX    new->delete = (voidfn) invalid_op;
  745. XX    new->display = (voidfn) invalid_op;
  746. XX    new->current = (UnivPtrFn) invalid_op;
  747. XX    new->cdr = (UnivPtrFn) invalid_op;
  748. XX    new->car = (UnivPtrFn) invalid_op;
  749. XX    new->total = (size_tfn) total;
  750. XX    new->ltell = (size_tfn) invalid_op;
  751. XX
  752. XX    return(new);
  753. XX}
  754. XX
  755. XX/*
  756. XX *    destructor
  757. XX */
  758. XXvoid
  759. XXdestroy_list(this)
  760. XX    lst_t    *this;
  761. XX{
  762. XX    if (this)
  763. XX        free(this);
  764. XX    return;
  765. XX}
  766. XX
  767. XX/*
  768. XX *    methods -- these may not be optimum for all sub-classes
  769. XX */
  770. XX
  771. XXstatic bool
  772. XXisempty(this)
  773. XX    lst_t    *this;
  774. XX{
  775. XX    return(lst_total(this) == 0);
  776. XX}
  777. XX
  778. XXstatic bool
  779. XXseek(this, where, from)
  780. XX    lst_t    *this;
  781. XX    size_t    where;        /* destination element or offset */
  782. XX    int    from;        /* arg. similar to lseek(2s) */
  783. XX{
  784. XX    size_t    count;
  785. XX
  786. XX    if (!this)
  787. XX        return(FALSE);
  788. XX    /*
  789. XX     * NOTE:  upon failure, the current element is always set to the
  790. XX     * top.  This is because we don't want to be re-cursive in re-setting
  791. XX     * our position, in case the data is really corrupted.
  792. XX     */
  793. XX    switch (from) {
  794. XX    case SEEK_SET:
  795. XX        lst_top(this);
  796. XX        for (count = (long) 0; count < where; ++count) {
  797. XX            if (lst_atbottom(this)) {
  798. XX                lst_top(this);
  799. XX                return(FALSE);
  800. XX            }
  801. XX            (void) lst_next(this);
  802. XX        }
  803. XX        break;
  804. XX    case SEEK_CUR:
  805. XX        if (where > 0) {
  806. XX            for (count = (long) 0; count < where; ++count) {
  807. XX                if (lst_atbottom(this)) {
  808. XX                    lst_top(this);
  809. XX                    return(FALSE);
  810. XX                }
  811. XX                (void) lst_next(this);
  812. XX            }
  813. XX        } else if (where < 0) {
  814. XX            for (count = (long) 0; count < where; ++count) {
  815. XX                if (lst_attop(this))
  816. XX                    return(FALSE);
  817. XX                (void) lst_prev(this);
  818. XX            }
  819. XX        }
  820. XX        break;
  821. XX    case SEEK_END:
  822. XX        lst_bottom(this);
  823. XX        for (count = (long) 0; count < where; ++count) {
  824. XX            if (lst_attop(this))
  825. XX                return(FALSE);
  826. XX            (void) lst_prev(this);
  827. XX        }
  828. XX        break;
  829. XX    }
  830. XX    return(TRUE);
  831. XX}
  832. XX
  833. XXstatic size_t
  834. XXtotal(this)
  835. XX    lst_t    *this;
  836. XX{
  837. XX    size_t    thisone,
  838. XX        count = (long) 0;
  839. XX
  840. XX    if (!this)
  841. XX        return(0);
  842. XX    thisone = lst_ltell(this);
  843. XX    lst_top(this);
  844. XX    do {
  845. XX        if (!lst_atbottom(this)) {
  846. XX            ++count;
  847. XX            lst_next(this);
  848. XX        }
  849. XX    } while (!lst_atbottom(this));
  850. XX    lst_seek(this, thisone, SEEK_SET);
  851. XX    return(count);
  852. XX}
  853. XEND_OF_FILE
  854. Xif test 3792 -ne `wc -c <'list.c'`; then
  855. X    echo shar: \"'list.c'\" unpacked with wrong size!
  856. Xfi
  857. X# end of 'list.c'
  858. Xfi
  859. Xif test -f 'alist.c' -a "${1}" != "-c" ; then 
  860. X  echo shar: Will not clobber existing file \"'alist.c'\"
  861. Xelse
  862. Xecho shar: Extracting \"'alist.c'\" \(3735 characters\)
  863. Xsed "s/^X//" >'alist.c' <<'END_OF_FILE'
  864. XX/*
  865. XX *    alist.c - array list sub-class methods
  866. XX */
  867. XX
  868. XX#define SID    "@(#)dlst:alist.c    1.5    92/10/03 23:37:12 (woods)"
  869. XX#include <sccsid.h>
  870. XX
  871. XX/*
  872. XX * This is a mid-level class.  The basic structure, as well as simple
  873. XX * movement methods have been defined.  However, a further sub-class is
  874. XX * required to define the actual array elements, their addition, deletion,
  875. XX * and other data-related functions.
  876. XX */
  877. XX
  878. XX#if defined(USE_STDDEF) || REALSTDC || (__STDC__ - 0) == 1
  879. XX# include <stddef.h>    /* should do before sysdefs.h */
  880. XX#endif
  881. XX#include <sysdefs.h>    /* localisation helpers */
  882. XX#include <sys/types.h>    /* for size_t, if avail. */
  883. XX#include <stdio.h>    /* only for "FILE" used in <libc.h> */
  884. XX#include <assert.h>
  885. XX#if defined(USG) || defined(SYSV)
  886. XX# include <malloc.h>
  887. XX# include <memory.h>
  888. XX# include <unistd.h>
  889. XX#endif
  890. XX#include <libc.h>
  891. XX#include "dlst.h"
  892. XX
  893. XX/*
  894. XX * all must have the same types as in LIST_CLASS in list.h
  895. XX *
  896. XX * NOTE:  Not all of these are defined below!
  897. XX */
  898. XXstatic bool    attop(),
  899. XX        atbottom(),
  900. XX        isempty(),
  901. XX        add(),
  902. XX        prev(),
  903. XX        next(),
  904. XX        seek(),
  905. XX        find();
  906. XXstatic cmp_t    cmp();
  907. XXstatic VOID    top(),
  908. XX        bottom(),
  909. XX        replace(),
  910. XX        delete(),
  911. XX        display(),
  912. XX        sort();
  913. XXstatic UnivPtr    current(),
  914. XX        cdr(),
  915. XX        car();
  916. XXstatic size_t    total(),
  917. XX        ltell();
  918. XX
  919. XX/*
  920. XX *    constructor
  921. XX */
  922. XXalst_t    *
  923. XXnew_alist()
  924. XX{
  925. XX    lst_t    *lst;
  926. XX    alst_t    *new;
  927. XX
  928. XX    if ((lst = lst_new()) == NULL)
  929. XX        return(NULL);
  930. XX
  931. XX    if ((new = (alst_t *) malloc(sizeof(alst_t))) == NULL) {
  932. XX        lst_destroy(lst);
  933. XX        return(NULL);
  934. XX    }
  935. XX    (void) memcpy(new, lst, sizeof(*lst));    /* mucho assumptions! */
  936. XX    lst_destroy(lst);
  937. XX
  938. XX    new->attop = attop;
  939. XX    new->atbottom = atbottom;
  940. XX    new->next = next;
  941. XX    new->prev = prev;
  942. XX    new->seek = seek;
  943. XX    new->top = top;
  944. XX    new->bottom = bottom;
  945. XX    new->total = total;
  946. XX    return(new);
  947. XX}
  948. XX
  949. XX/*
  950. XX * destructor
  951. XX */
  952. XXvoid
  953. XXdestroy_alist(this)
  954. XX    alst_t    *this;
  955. XX{
  956. XX    /*
  957. XX     * NOTE:  the super (or parent) object has already been
  958. XX     * destroyed in the constructor for this object.
  959. XX     */
  960. XX    if (this)
  961. XX        free(this);
  962. XX    return;
  963. XX}
  964. XX
  965. XXstatic size_t
  966. XXtotal(this)
  967. XX    alst_t    *this;
  968. XX{
  969. XX    if (!this)
  970. XX        return(0);
  971. XX    return(this->num_el);
  972. XX}
  973. XX
  974. XXstatic bool
  975. XXattop(this)
  976. XX    alst_t    *this;
  977. XX{
  978. XX    assert(this);
  979. XX    return(this->curr_el == 0);
  980. XX}
  981. XX
  982. XXstatic bool
  983. XXatbottom(this)
  984. XX    alst_t    *this;
  985. XX{
  986. XX    assert(this);
  987. XX    return(this->curr_el == this->num_el);
  988. XX}
  989. XX
  990. XXstatic bool
  991. XXnext(this)
  992. XX    alst_t    *this;
  993. XX{
  994. XX    if (!this)
  995. XX        return(FALSE);
  996. XX    assert(this->curr_el >= 0 && this->curr_el <= this->num_el);
  997. XX    if (this->curr_el >= this->num_el)    /* >= in case NDEBUG set */
  998. XX        return(FALSE);
  999. XX    this->curr_el++;
  1000. XX    return(TRUE);
  1001. XX}
  1002. XX
  1003. XXstatic bool
  1004. XXprev(this)
  1005. XX    alst_t    *this;
  1006. XX{
  1007. XX    if (!this)
  1008. XX        return(FALSE);
  1009. XX    assert(this->curr_el >= 0 && this->curr_el <= this->num_el);
  1010. XX    if (!this->curr_el)
  1011. XX        return(FALSE);
  1012. XX    this->curr_el--;
  1013. XX    return(TRUE);
  1014. XX}
  1015. XX
  1016. XXstatic VOID
  1017. XXtop(this)
  1018. XX    alst_t    *this;
  1019. XX{
  1020. XX    if (!this)
  1021. XX        return;
  1022. XX    this->curr_el = 0;
  1023. XX    return;
  1024. XX}
  1025. XX
  1026. XXstatic VOID
  1027. XXbottom(this)
  1028. XX    alst_t    *this;
  1029. XX{
  1030. XX    if (!this)
  1031. XX        return;
  1032. XX    this->curr_el = this->num_el - 1;
  1033. XX    return;
  1034. XX}
  1035. XX
  1036. XXstatic bool
  1037. XXseek(this, where, from)
  1038. XX    alst_t    *this;
  1039. XX    size_t    where;        /* destination element or offset */
  1040. XX    int    from;        /* arg. similar to lseek(2s) */
  1041. XX{
  1042. XX    if (!this)
  1043. XX        return(FALSE);
  1044. XX    /*
  1045. XX     * NOTE:  There is still no major amount of checking in here.  The
  1046. XX     * seek operation does not change your current element, as the linked
  1047. XX     * list implementation does.
  1048. XX     */
  1049. XX    switch (from) {
  1050. XX    case SEEK_SET:
  1051. XX        if (where < this->num_el)
  1052. XX            this->curr_el = where;
  1053. XX        else
  1054. XX            return(FALSE);
  1055. XX        break;
  1056. XX    case SEEK_CUR:
  1057. XX        if (where > 0) {
  1058. XX            if ((this->curr_el + where) < this->num_el)
  1059. XX                this->curr_el += where;
  1060. XX            else
  1061. XX                return(FALSE);
  1062. XX        } else {
  1063. XX            if ((this->curr_el - where) > 0)
  1064. XX                this->curr_el -= where;
  1065. XX            else
  1066. XX                return(FALSE);
  1067. XX        }
  1068. XX        break;
  1069. XX    case SEEK_END:
  1070. XX        if (where <= this->num_el)
  1071. XX            this->curr_el = this->num_el - where;
  1072. XX        else
  1073. XX            return(FALSE);
  1074. XX        break;
  1075. XX    }
  1076. XX    return(TRUE);
  1077. XX}
  1078. XEND_OF_FILE
  1079. Xif test 3735 -ne `wc -c <'alist.c'`; then
  1080. X    echo shar: \"'alist.c'\" unpacked with wrong size!
  1081. Xfi
  1082. X# end of 'alist.c'
  1083. Xfi
  1084. Xif test -f 'llist.c' -a "${1}" != "-c" ; then 
  1085. X  echo shar: Will not clobber existing file \"'llist.c'\"
  1086. Xelse
  1087. Xecho shar: Extracting \"'llist.c'\" \(8033 characters\)
  1088. Xsed "s/^X//" >'llist.c' <<'END_OF_FILE'
  1089. XX/*
  1090. XX *    llist.c - linked list sub-class methods
  1091. XX */
  1092. XX
  1093. XX#define SID    "@(#)dlst:llist.c    1.5    92/10/03 23:38:06 (woods)"
  1094. XX#include <sccsid.h>
  1095. XX
  1096. XX#if defined(USE_STDDEF) || REALSTDC || (__STDC__ - 0) == 1
  1097. XX# include <stddef.h>    /* should do before sysdefs.h */
  1098. XX#endif
  1099. XX#include <sysdefs.h>    /* localisation helpers */
  1100. XX#include <sys/types.h>    /* for size_t, if avail. */
  1101. XX#include <stdio.h>    /* only for "FILE" used in <libc.h> */
  1102. XX#include <assert.h>
  1103. XX#if defined(USG) || defined(SYSV)
  1104. XX# include <malloc.h>
  1105. XX# include <memory.h>
  1106. XX# include <unistd.h>
  1107. XX#endif
  1108. XX#include <libc.h>
  1109. XX#include "dlst.h"
  1110. XX
  1111. XXstatic void    invalid_op();
  1112. XXstatic llel_t    *sort_list();
  1113. XXstatic llel_t    *merge_list();
  1114. XX
  1115. XX/*
  1116. XX * Sillyness to keep assigments of invalid_op from making noise
  1117. XX */
  1118. XXtypedef VOID    (*voidfn)();
  1119. XX
  1120. XX/*
  1121. XX * all must have the same types as in LIST_CLASS in list.h
  1122. XX *
  1123. XX * NOTE:  Not all of these are defined below!
  1124. XX */
  1125. XXstatic bool    attop(),
  1126. XX        atbottom(),
  1127. XX        isempty(),
  1128. XX        add(),
  1129. XX        prev(),
  1130. XX        next(),
  1131. XX        seek(),
  1132. XX        find();
  1133. XXstatic cmp_t    cmp();
  1134. XXstatic VOID    top(),
  1135. XX        bottom(),
  1136. XX        replace(),
  1137. XX        delete(),
  1138. XX        display(),
  1139. XX        sort();
  1140. XXstatic UnivPtr    current(),
  1141. XX        cdr(),
  1142. XX        car();
  1143. XXstatic size_t    total(),
  1144. XX        ltell();
  1145. XX
  1146. XX/*
  1147. XX *    safety feature
  1148. XX */
  1149. XXstatic void
  1150. XXinvalid_op()
  1151. XX{
  1152. XX    assert(0);
  1153. XX}
  1154. XX
  1155. XX/*
  1156. XX *    constructor
  1157. XX */
  1158. XXllst_t    *
  1159. XXnew_llist()
  1160. XX{
  1161. XX    lst_t    *lst;
  1162. XX    llst_t    *new;
  1163. XX
  1164. XX    if ((lst = lst_new()) == NULL)
  1165. XX        return(NULL);
  1166. XX
  1167. XX    if ((new = (llst_t *) malloc(sizeof(llst_t))) == NULL) {
  1168. XX        lst_destroy(lst);
  1169. XX        return(NULL);
  1170. XX    }
  1171. XX    (void) memcpy(new, lst, sizeof(*lst));    /* WARNING:  assumptions! */
  1172. XX
  1173. XX    lst_destroy(lst);    /* throw away original super-object */
  1174. XX
  1175. XX    new->attop = attop;
  1176. XX    new->atbottom = atbottom;
  1177. XX    new->isempty = isempty;
  1178. XX    new->top = top;
  1179. XX    new->bottom = bottom;
  1180. XX    new->next = next;
  1181. XX    new->prev = prev;
  1182. XX    new->add = add;
  1183. XX    new->find = find;
  1184. XX    new->current = current;
  1185. XX    new->replace = replace;
  1186. XX    new->delete = delete;
  1187. XX    new->display = (voidfn) invalid_op;
  1188. XX    new->ltell = ltell;
  1189. XX    new->total = total;    /* over-ride super-class definition */
  1190. XX    new->sort = (voidfn) sort;
  1191. XX
  1192. XX    new->first_el = NULL;
  1193. XX    new->last_el = NULL;
  1194. XX    new->curr_el = NULL;
  1195. XX    new->num_el = 0;
  1196. XX
  1197. XX    return(new);
  1198. XX}
  1199. XX
  1200. XX/*
  1201. XX *    destructor
  1202. XX */
  1203. XXvoid
  1204. XXdestroy_llist(this)
  1205. XX    llst_t    *this;
  1206. XX{
  1207. XX    if (!this)
  1208. XX        return;
  1209. XX    llst_bottom(this);
  1210. XX    while (this->curr_el)
  1211. XX        llst_delete(this);
  1212. XX    /*
  1213. XX     * NOTE:  the super (or parent) object has already been
  1214. XX     * destroyed in the constructor for this object.
  1215. XX     */
  1216. XX    if (this)
  1217. XX        free(this);
  1218. XX    return;
  1219. XX}
  1220. XX
  1221. XX/*
  1222. XX *    methods -- these may not be optimum for all sub-classes
  1223. XX */
  1224. XX
  1225. XXstatic bool
  1226. XXattop(this)
  1227. XX    llst_t    *this;
  1228. XX{
  1229. XX    assert(this);
  1230. XX    return(this->curr_el == this->first_el);
  1231. XX}
  1232. XX
  1233. XXstatic bool
  1234. XXatbottom(this)
  1235. XX    llst_t    *this;
  1236. XX{
  1237. XX    assert(this);
  1238. XX    return(this->curr_el == this->last_el);
  1239. XX}
  1240. XX
  1241. XXstatic bool
  1242. XXisempty(this)
  1243. XX    llst_t    *this;
  1244. XX{
  1245. XX    assert(this);
  1246. XX    return(this->first_el == NULL);
  1247. XX}
  1248. XX
  1249. XXstatic VOID
  1250. XXtop(this)
  1251. XX    llst_t    *this;
  1252. XX{
  1253. XX    if (!this)
  1254. XX        return;
  1255. XX    this->curr_el = this->first_el;
  1256. XX    return;
  1257. XX}
  1258. XX
  1259. XXstatic VOID
  1260. XXbottom(this)
  1261. XX    llst_t    *this;
  1262. XX{
  1263. XX    if (!this)
  1264. XX        return;
  1265. XX    this->curr_el = this->last_el;
  1266. XX    return;
  1267. XX}
  1268. XX
  1269. XXstatic bool
  1270. XXnext(this)
  1271. XX    llst_t    *this;
  1272. XX{
  1273. XX    if (!this)
  1274. XX        return(FALSE);
  1275. XX    if (!this->curr_el || !this->curr_el->nxt)
  1276. XX        return(FALSE);
  1277. XX    this->curr_el = this->curr_el->nxt;
  1278. XX    return(TRUE);
  1279. XX}
  1280. XX
  1281. XXstatic bool
  1282. XXprev(this)
  1283. XX    llst_t    *this;
  1284. XX{
  1285. XX    if (!this)
  1286. XX        return(FALSE);
  1287. XX    if (!this->curr_el || !this->curr_el->prv)
  1288. XX        return(FALSE);
  1289. XX    this->curr_el = this->curr_el->prv;
  1290. XX    return(TRUE);
  1291. XX}
  1292. XX
  1293. XXstatic bool
  1294. XXadd(this, datum)
  1295. XX    llst_t    *this;
  1296. XX    UnivPtr    datum;
  1297. XX{
  1298. XX    llel_t    *new;
  1299. XX
  1300. XX    if (!this)
  1301. XX        return(FALSE);
  1302. XX    if ((new = (llel_t *) malloc(sizeof(llel_t))) == NULL)
  1303. XX        return(FALSE);
  1304. XX    new->d = datum;
  1305. XX    this->num_el++;
  1306. XX    if (!this->first_el) {
  1307. XX        this->first_el = new;
  1308. XX        this->last_el = new;
  1309. XX        new->prv = NULL;
  1310. XX        new->nxt = NULL;
  1311. XX    } else if (this->curr_el == this->last_el) {
  1312. XX        assert(this->curr_el->nxt == NULL);
  1313. XX        this->curr_el->nxt = new;
  1314. XX        this->last_el = new;
  1315. XX        new->prv = this->curr_el;
  1316. XX        new->nxt = NULL;
  1317. XX    } else {
  1318. XX        new->nxt = this->curr_el->nxt;
  1319. XX        this->curr_el->nxt->prv = new;
  1320. XX        this->curr_el->nxt = new;
  1321. XX        new->prv = this->curr_el;
  1322. XX    }
  1323. XX    this->curr_el = new;
  1324. XX    return(TRUE);
  1325. XX}
  1326. XX
  1327. XXstatic VOID
  1328. XXdelete(this)
  1329. XX    llst_t    *this;
  1330. XX{
  1331. XX    llel_t    *old;
  1332. XX
  1333. XX    if (!this)
  1334. XX        return;
  1335. XX    if (!(old = this->curr_el))
  1336. XX        return;
  1337. XX    if (this->last_el == this->curr_el) {
  1338. XX        this->curr_el = this->last_el = old->prv;
  1339. XX        this->curr_el->nxt = NULL;
  1340. XX    } else if (this->first_el == this->curr_el) {
  1341. XX        this->curr_el = this->first_el = old->nxt;
  1342. XX        this->curr_el->prv = NULL;
  1343. XX    } else {
  1344. XX        this->curr_el = old->prv;
  1345. XX        old->nxt->prv = this->curr_el;
  1346. XX        this->curr_el->nxt = old->nxt;
  1347. XX    }
  1348. XX    if (old->d)
  1349. XX        free(old->d);
  1350. XX    free(old);
  1351. XX    return;
  1352. XX}
  1353. XX
  1354. XXstatic UnivPtr
  1355. XXcurrent(this)
  1356. XX    llst_t    *this;
  1357. XX{
  1358. XX    if (!this || !this->curr_el)
  1359. XX        return(NULL);
  1360. XX    return(this->curr_el->d);
  1361. XX}
  1362. XX
  1363. XXstatic VOID
  1364. XXreplace(this, datum)
  1365. XX    llst_t    *this;
  1366. XX    UnivPtr    datum;
  1367. XX{
  1368. XX    assert(this && this->curr_el);
  1369. XX    this->curr_el->d = datum;
  1370. XX    return;
  1371. XX}
  1372. XX
  1373. XXstatic size_t
  1374. XXltell(this)
  1375. XX    llst_t    *this;
  1376. XX{
  1377. XX    size_t    thisone = 0;
  1378. XX    llel_t    *elem;
  1379. XX
  1380. XX    if (!this)
  1381. XX        return(0);
  1382. XX    if (!(elem = this->first_el))
  1383. XX        return(0);
  1384. XX    while (elem != this->curr_el) {
  1385. XX        thisone++;
  1386. XX        elem = elem->nxt;
  1387. XX    }
  1388. XX    return(thisone);
  1389. XX}
  1390. XX
  1391. XXstatic size_t
  1392. XXtotal(this)
  1393. XX    llst_t    *this;
  1394. XX{
  1395. XX#ifdef NO_COUNT
  1396. XX    size_t    len = 0;
  1397. XX    llel_t    *elem;
  1398. XX
  1399. XX    if (!this)
  1400. XX        return(0);
  1401. XX    if (!(elem = this->first_el))
  1402. XX        return(0);
  1403. XX    while (elem) {
  1404. XX        len++;
  1405. XX        elem = elem->nxt;
  1406. XX    }
  1407. XX    return(len);
  1408. XX#else
  1409. XX    if (!this)
  1410. XX        return(0);
  1411. XX    return(this->num_el);
  1412. XX#endif
  1413. XX}
  1414. XX
  1415. XXstatic bool
  1416. XXfind(this, el, fn)
  1417. XX    llst_t    *this;
  1418. XX    char    *el;
  1419. XX    cmp_t    (*fn)();
  1420. XX{
  1421. XX    if (!this)
  1422. XX        return(FALSE);
  1423. XX    llst_top(this);
  1424. XX    do {
  1425. XX        if ((*fn)(el, llst_current(this)) == 0)
  1426. XX            return(TRUE);
  1427. XX    } while (llst_next(this));
  1428. XX    return(FALSE);
  1429. XX}
  1430. XX
  1431. XXstatic VOID
  1432. XXsort(this, fn)
  1433. XX    llst_t    *this;
  1434. XX    cmp_t    (*fn)();
  1435. XX{
  1436. XX    if (!this)
  1437. XX        return;
  1438. XX    this->first_el = sort_list(this->first_el, fn);
  1439. XX    this->curr_el = this->first_el;
  1440. XX    while (this->curr_el && this->curr_el->nxt)
  1441. XX        this->curr_el = this->curr_el->nxt;
  1442. XX    this->last_el = this->curr_el;
  1443. XX    this->curr_el = this->first_el;
  1444. XX    return;
  1445. XX}
  1446. XX
  1447. XX/*
  1448. XX * with apologies (though not many!) to R. Sedgewick: Algorithms
  1449. XX * (1983) - p.  149
  1450. XX */
  1451. XXstatic llel_t *
  1452. XXsort_list(lst, fn)
  1453. XX    llel_t    *lst;            /* pointer to first element */
  1454. XX    cmp_t    (*fn)();        /* comparison function */
  1455. XX{
  1456. XX    size_t    lst_len = 0;        /* number of elements */
  1457. XX    llel_t    *lst_a;
  1458. XX    llel_t    *lst_b;
  1459. XX    size_t    i;
  1460. XX
  1461. XX    if (!lst || !lst->nxt)                /* recursion termination */
  1462. XX        return(lst);
  1463. XX
  1464. XX    lst_a = lst;
  1465. XX    while (lst_a->nxt) {
  1466. XX        lst_len++;
  1467. XX        lst_a = lst_a->nxt;
  1468. XX    }
  1469. XX        
  1470. XX    lst_a = lst;                /* set head of first half */
  1471. XX    for (i = 1; i < (lst_len / 2); i++)    /* skip half (note division) */
  1472. XX        lst = lst->nxt;
  1473. XX
  1474. XX    lst_b = lst->nxt;            /* set head of last half */
  1475. XX    lst->nxt = NULL;            /* terminate lst_a */
  1476. XX    lst_b->prv = NULL;            /* and the backptr too */
  1477. XX
  1478. XX    return(merge_list(sort_list(lst_a, fn), sort_list(lst_b, fn), fn));
  1479. XX}
  1480. XX
  1481. XX
  1482. XX/*
  1483. XX *    merge_list - merge two lists
  1484. XX */
  1485. XX/*
  1486. XX * with apologies (though not many!) to R. Sedgewick: Algorithms
  1487. XX * (1983) - p. 148
  1488. XX */
  1489. XXstatic llel_t *
  1490. XXmerge_list(lst_a, lst_b, fn)
  1491. XX    llel_t    *lst_a;            /* pointer to first half */
  1492. XX    llel_t    *lst_b;            /* pointer to second half */
  1493. XX    cmp_t    (*fn)();        /* data comparison function */
  1494. XX{
  1495. XX    llel_t    *head;            /* head of the merged list */
  1496. XX    llel_t    *tail;            /* walking tail */
  1497. XX
  1498. XX    /*
  1499. XX     * first, pick the head of the list
  1500. XX     */
  1501. XX    if (!lst_a && !lst_b)
  1502. XX        return(NULL);
  1503. XX    else if (!lst_a)
  1504. XX        return(lst_b);
  1505. XX    else if (!lst_b)
  1506. XX        return(lst_a);
  1507. XX
  1508. XX    if ((*fn)(lst_a->d, lst_b->d) <= 0) {
  1509. XX        head = lst_a;
  1510. XX        tail = lst_a;
  1511. XX        lst_a = lst_a->nxt;
  1512. XX    } else {
  1513. XX        head = lst_b;
  1514. XX        tail = lst_b;
  1515. XX        lst_b = lst_b->nxt;
  1516. XX    }
  1517. XX    /*
  1518. XX     * while there are still elements on both lists, point to
  1519. XX     * the list with the next item as determined by strcmp()
  1520. XX     */
  1521. XX    while (lst_a && lst_b) {
  1522. XX        if ((*fn)(lst_a->d, lst_b->d) <= 0) {
  1523. XX            tail->nxt = lst_a;
  1524. XX            lst_a->prv = tail;
  1525. XX            tail = lst_a;
  1526. XX            lst_a = lst_a->nxt;
  1527. XX        } else {
  1528. XX            tail->nxt = lst_b;
  1529. XX            lst_b->prv = tail;
  1530. XX            tail = lst_b;
  1531. XX            lst_b = lst_b->nxt;
  1532. XX        }
  1533. XX    }
  1534. XX    /*
  1535. XX     * NOTE: the new list is already terminated.  Now, attatch any
  1536. XX     * remaining odd lists
  1537. XX     */
  1538. XX    if (lst_a) {
  1539. XX        tail->nxt = lst_a;
  1540. XX        lst_a->prv = tail;
  1541. XX    } else if (lst_b) {
  1542. XX        tail->nxt = lst_b;
  1543. XX        lst_b->prv = tail;
  1544. XX    }
  1545. XX    return(head);    /* return the head of the merged lists */
  1546. XX}
  1547. XEND_OF_FILE
  1548. Xif test 8033 -ne `wc -c <'llist.c'`; then
  1549. X    echo shar: \"'llist.c'\" unpacked with wrong size!
  1550. Xfi
  1551. X# end of 'llist.c'
  1552. Xfi
  1553. Xecho shar: End of shell archive.
  1554. Xecho "Please read the file README first"
  1555. Xexit 0
  1556. END_OF_FILE
  1557. if test 36973 -ne `wc -c <'dlst.shar'`; then
  1558.     echo shar: \"'dlst.shar'\" unpacked with wrong size!
  1559. fi
  1560. # end of 'dlst.shar'
  1561. fi
  1562. echo shar: End of archive 4 \(of 4\).
  1563. cp /dev/null ark4isdone
  1564. MISSING=""
  1565. for I in 1 2 3 4 ; do
  1566.     if test ! -f ark${I}isdone ; then
  1567.     MISSING="${MISSING} ${I}"
  1568.     fi
  1569. done
  1570. if test "${MISSING}" = "" ; then
  1571.     echo You have unpacked all 4 archives.
  1572.     echo "Please read the file README first"
  1573.     rm -f ark[1-9]isdone
  1574. else
  1575.     echo You still need to unpack the following archives:
  1576.     echo "        " ${MISSING}
  1577. fi
  1578. ##  End of shell archive.
  1579. exit 0
  1580.