X_List 02/02
Kenneth Jamieson
tron1 at tronsbox.xei.com
Sun Feb 10 14:35:12 AEST 1991
Submitted by: tron1 at tronsbox
Archive-name: X_List/part 2
---- Cut Here and unpack ----
#!/bin/sh
# this is X_List.02 (part 2 of X_List)
# do not concatenate these parts, unpack them in order with /bin/sh
# file x_list/src/x_list.h continued
#
touch 2>&1 | fgrep '[-amc]' > /tmp/s3_touch$$
if [ -s /tmp/s3_touch$$ ]
then
TOUCH=can
else
TOUCH=cannot
fi
rm -f /tmp/s3_touch$$
CurArch=2
if test ! -r s3_seq_.tmp
then echo "Please unpack part 1 first!"
exit 1; fi
( read Scheck
if test "$Scheck" != $CurArch
then echo "Please unpack part $Scheck next!"
exit 1;
else exit 0; fi
) < s3_seq_.tmp || exit 1
echo "x - Continuing file x_list/src/x_list.h"
sed 's/^X//' << 'SHAR_EOF' >> x_list/src/x_list.h
X/* Gives you the node number of the node you are on */
X
X#ifdef IS_CPP
X
Xclass X_List {
X struct x_list * list;
X public:
X X_List();
X X_List( void * name );
X int add( void * data );
X void * get();
X int head();
X int tail();
X int put( void * data);
X int del();
X int next();
X int prev();
X int count();
X int set_user( void * name );
X void * get_user();
X int nodenum();
X int goto_node( int target );
X void * operator[](int);
X ~X_List();
X};
X
X
X#endif
X
X#endif
X
X
SHAR_EOF
echo "File x_list/src/x_list.h is complete"
chmod 0440 x_list/src/x_list.h || echo "restore of x_list/src/x_list.h fails"
if [ $TOUCH = can ]
then
touch -am 0209182491 x_list/src/x_list.h
fi
set `wc -c x_list/src/x_list.h`;Wc_c=$1
if test "$Wc_c" != "3423"
then echo original size 3423, current size $Wc_c;fi
# ============= x_list/distrib ==============
echo "x - extracting x_list/distrib (Text)"
sed 's/^X//' << 'SHAR_EOF' > x_list/distrib &&
X/*
X Shareware license document : sharew.h 1.1 2/3/91
X*/
X/*
X
XThis text in this file is copyright (c) 1991 by Kenneth Jamieson.
X
XThe author may be reached at the US MAIL address listed below, or
Xby sending unix mail to ...
X
X tron1 at tronsbox.xei.com or
X ...!uunet!tronsbox.xei.com!tron1 or
X yelling "Hey Ken!" if you happen to be close enough.
X
X
XAll rights are reserved by Kenneth Jamieson.
X
XYou are granted permission to use this code under the following
Xrestrictions:
X
XNOTE: All occurrences of the word "code" below will apply to
X all files, text, program source code and documentation.
X
X1) This code cannot be used in any program that is to be distributed
X to anyone other than that program's author without the
X written permission of Kenneth Jamieson. This permission will be granted
X under the terms of registration listed below.
X
X2) This code may be used for a trial period of thirty (30) days.
X At that time, you mus either register the code as below or
X discontinue it's use.
X
X3) UNDER NO CIRCUMSTANCES may this code (registered or not) be used or
X distributed in any way that will prevent it's future distribution
X under the terms of this license except by Kenneth Jamieson.
X
X This specifically includes (but is not limited to) any code that
X is to be distributed under the terms of the Free Software
X Foundation's General Public License.
X
X4) Kenneth Jamieson reserves all rights to this code.
X
X5) NO WARRANTY is given or implied as to the usefulness or correctness of
X this code for any purpose at all, whether this code is registered or not.
X
X
XREGISTRATION:
X
X You are encouraged to register this code no matter what you use it for,
X but you MUST register this code if you need written permission under
X the terms above for distribution or intend to use it after the
X trial period expires.
X
X In order to register this code, just send $15 US to the author at the
X address listed below.
X
X Kenneth Jamieson
X P.o. Box 387
X Kearny NJ 07023
X USA
X
X Once registered you will receive permission to use this code in your own
X programs under the following restrictions:
X
X 1) Your program or documentation must mention that this code is in use,
X and provide your user with information about where to obtain this
X code. This information must be provided as part of the initial
X cost (if any) of your software.
X
X 2) If you distribute the source to your program, then the source
X for this code must accompany your code complete and unaltered.
X
X 3) UNDER NO CIRCUMSTANCES may this code (registered or not) be used or
X distributed in any way that will prevent it's future distribution
X under the terms of this license except by Kenneth Jamieson.
X
X This specifically includes (but is not limited to) any code that
X is to be distributed under the terms of the Free Software
X Foundation's General Public License.
X
X 4) Kenneth Jamieson reserves all rights to this code.
X
X 5) NO WARRANTY is given or implied as to the usefulness or correctness of
X this code for any purpose at all, whether this code is registered or not.
X
X In addition, you will get a list of any known bugs and work-arounds,
X notice of the next update (if any), and at least one "thank you".
X
X*/
X
X-----------------------------------------------------
X* UNIX is a trademark of AT&T
X* Amiga is a trademark of Commodore Business Machines
X* MS-DOS is a trademark of Microsoft Inc
X
X
SHAR_EOF
chmod 0640 x_list/distrib || echo "restore of x_list/distrib fails"
if [ $TOUCH = can ]
then
touch -am 0209213891 x_list/distrib
fi
set `wc -c x_list/distrib`;Wc_c=$1
if test "$Wc_c" != "3602"
then echo original size 3602, current size $Wc_c;fi
# ============= x_list/docs ==============
echo "x - extracting x_list/docs (Text)"
sed 's/^X//' << 'SHAR_EOF' > x_list/docs &&
X **************************
X * X_List documentation *
X **************************
X
X Let's get this legal stuff out of the way !
X
X
XThis text in this file is copyright (c) 1991 by Kenneth Jamieson.
X
XThe author may be reached at the US MAIL address listed below, or
Xby sending unix mail to ...
X
X tron1 at tronsbox.xei.com or
X ...!uunet!tronsbox.xei.com!tron1 or
X yelling "Hey Ken!" if you happen to be close enough.
X
X
X USING X_LIST IN YOUR PROGRAMS
X =============================
X
X In order to use X_List in your programs, you must do three things.
X
X 1) Include the file x_list.h in any program that will use the
X functions or structures from x_list.
X
X 2) Link the file x_list.a (x_list.lib for ms-dos/amiga) to your
X program.
X
X 3) #define the symbol "IS_CPP" when you compile your code.
X
X 4) Call these routines!
X
X
X
X THEORY
X ==========
X
X This is a dynamic size list that maintains pointers to
X arbitrary data for the programmer.
X
X This list can be thought of as index card catalog.
X In this analogy, the "current node" would be the one that the
X catalog is open to at the moment, and you can move forward
X or back (previous/next) at will.
X
X Unlike a card catalogue, these "nodes" are not sorted by
X these routines, it will be in the order you left it. If you need
X to maintain sorted lists, pick up the hash table routines that I will
X be releasing soon ( a week or two ).
X
X
X "C" Routines
X ================
X
Xstruct x_list_entry *init_xlist_entry():
X
X RETURNS: struct x_list_entry *, or NULL on error
X
X You will probably never need to call this routine direct.
X It allocates space for, and initializes, one x_list_entry structure.
X
X
Xstruct x_list *init_xlist():
X
X RETURNS: struct x_list *, or NULL on error
X
X It allocates space for, and initializes, one x_list structure.
X
X The return value will be your "handle" onto the list, you will
X need to supply it to all of the rest of these routines under "C".
X
X You can look into "x_list.h" for the definition, but for
X compatibility reasons, NEVER rely on this structure being the same
X internally. Access it only through the supplied functions.
X
X If for some reason the initialization fails, will return a NULL.
X
X
Xint add_xlist( struct x_list *, void *):
X
X RETURNS: TRUE if success, FALSE if error
X
X Attempts to add the void pointer into the list. It will be appended
X to the lists tail in all cases.
X
X A failure can mean either the x_list handle was invalid, or the
X system is out of memory to give you.
X
X This is the only way to increase the size of a list. This will
X also increment the list size counter. The "current node" is set
X to the node we just created
X
X
Xvoid * get_xlist(struct x_list * ):
X
X RETURNS: data pointer stored in current node or NULL if error
X
X Note ... there is no way to distinguish an error from a case where
X you (the user) really did store a null in the list.
X
X
Xint head_xlist( struct x_list * )
X
X RETURNS: TRUE if success, FALSE if error
X
X This call will re-set the "current node" pointer to the first node
X in the list.
X
X An error is usually the result of a bad x_list handle being passed
X int this routine.
X
X
Xint tail_xlist( struct x_list * )
X
X RETURNS: TRUE if success, FALSE if error
X
X This call will re-set the "current node" pointer to the last node
X in the list.
X
X An error is usually the result of a bad x_list handle being passed
X int this routine.
X
X
Xint put_xlist( struct x_list *, void * ):
X
X RETURNS: TRUE if success, FALSE if error
X
X Stores the void pointer passed in into the node at the
X "current node" pointer for the list.
X
X Failure can be cause by a invalid list handle, or if there IS
X no node at "current node". This can happen if this routine is
X called when there has bee no preceding "add_xlist" call. In that
X case, the list is empty!
X
X This routine does NOT increment the list size counter.
X Also, the "current node" pointer is unchanged.
X
X
Xint del_xlist( struct x_list * ):
X
X RETURNS: TRUE if success, FALSE if error.
X
X Kills the node at "current node" and will re-weave the list.
X It also de-allocates the memory used to store that node in the
X list and decrements the list size counter.
X
X The next node in the list becomes the "current node", if the node
X deleted is the last node in the list, then the "current node" will
X be the new last item in the list.
X
X An error can be cause by a bad list handle, or if the list is
X empty.
X
X
Xint next_xlist( struct x_list * ):
X
X RETURNS: TRUE if success, FALSE if error
X
X Moves the "current node" pointer to the next node in the list.
X It will fail if there IS no next node. And in fact, is one of the
X best ways to tell if you are at the end of the list...
X
X
Xint prev_xlist( struct x_list * ):
X
X RETURNS: TRUE if success, FALSE if error
X
X Moves the "current node" pointer to the previous node in the list.
X It will fail if there IS no previous node. And in fact, is one of the
X best ways to tell if you are at the head of the list of the list...
X
X
Xint get_count_xlist( struct x_list * xlist ):
X
X RETURNS: The number of nodes in the list
X
X Every time "add_xlist" is called with success, it will increment
X the counter. The return value from this function then, is
X in effect a count of the number of add_xlist requests.
X
X
Xint free_xlist( struct x_list * ):
X
X RETURNS: TRUE on success, FALSE on error
X
X Attempts to free all the memory associated with this list. It will
X del_xlist() all the nodes, then free the structure you are using for a
X handle.
X
X NOTICE: Immediately on the success of this function, your
X x_list structure is NO LONGERER VALID.
X
X
Xint set_user_xlist( struct x_list *, void * ):
X
X RETURNS: TRUE on success, FALSE if error
X
X Each list carries around one special pointer. You can use this for
X anything you want. It is stored in the x_list structure. This
X routine will let you set it.
X
X Errors here are usually a invalid x_list structure.
X
X
Xvoid * get_user_xlist( struct x_list * ):
X
X RETURNS: pointer or NULL
X
X Will return what you set with a "set_user_xlist" call.
X
X Will return whatever is there. It is set to NULL
X by "init_xlist".
X
X
Xint goto_xlist( struct x_list *, int ):
X
X RETURNS: TRUE for success, FALSE on error
X
X Will attempt to set the "current node" to the node represented by the
X second argument. It will fail if the number requested is
X bigger than the size of the list, or if it is less than 0.
X
X NOTE: The node numbers are not guarenteed to remain
X unchanged through a "del_xlist()". If you goto the
X 5'th node, delete node 4, the go to the 5'th again, you are
X at what used to be node 6. The node numbers are
X counted from the head of the list (that one is 0).
X
X
Xint get_nodenum_xlist( struct x_list * xlist ):
X
X RETURNS: The number of the "current node"
X
X The number returned means that at this time,
X the "current node" is this number from the
X head. This would be the same as the subscript
X in an array.
X
X
X "C++" Routines
X ================
X
X For the most part, the interface to C++ is not very fancy. It doesn't
Xreally need to be. I can't personally see and operators that need overloading
Xfor this class.
X
X But -- as I go on I will think about what I can do to make it
Xmore "C++"ish. Any suggestions welcome.
X
XConstructors:
X
XX_List::X_List() and
XX_List::X_List( char * )
X
X These will create and initialize one x_list structure, the second
X for will also do a "set_user_xlist" with the char * supplied.
X
X You can use these in the forms ..
X
X X_List foo;
X X_List foo("This is a test");
X
X
XDestructors:
X
XX_List::~X_List()
X
X Will perform the equivalent of a "free_xlist" and free all memory
X allocated by this instance of the class.
X
X
XOperators:
X
Xvoid * X_List::operator[]( int )
X
X Will allow you to treat the list as if it were an array of
X X_List::count() size. Will return a NULL if it is an error or
X invalid node. Also, if the value stored in that node IS a
X NULL, then that will be returned. This means that you cannot
X be 100% sure if it failed. If you suspect and error,
X try a X_List::goto( int ) call with the same subscript
X and see if IT fails.
X
X If the list node holds a pointer to an integer, the
X object "list" was an X_List, and the list was bigger than 10
X nodes......
X
X int * foo;
X
X foo = list[10];
X
X
XMember Functions:
X
Xint X_List::add( void * )
X
X RETURNS: TRUE for success, FALSE for error
X
X This is just like it "C" counterpart, but the
X struct x_list * is not needed of course. Adds the pointer to the
X list.
X
X
Xvoid * X_List::get()
X
X RETURNS: void *
X
X Will fetch the data from "current node".
X
X See the details on the "C" function "get_xlist" for more info.
X
X
Xint X_List::head()
X
X RETURNS: TRUE for success, FALSE for error
X
X Makes the "current node" equal to the first node.
X
X
Xint X_List::tail()
X
X RETURNS: TRUE for success, FALSE for error
X
X Makes the "current node" equal to the last node.
X
X
Xint X_List::put( void * )
X
X RETURNS: TRUE for success, FALSE for error
X
X Will replace the data for the "current node".
X For failure diagnosis see the "C" routine "put_xlist" above.
X
X
Xint X_List::del()
X
X RETURNS: TRUE for success, FALSE for error
X
X Attempts to delete the "current node", see the "C" function
X "del_xlist" above
X
X
Xint X_List::next()
X
X RETURNS: TRUE for success, FALSE for error
X
X Will move the "current node" pointer to the next node in the list.
X
X Reference the function "next_xlist".
X
X
Xint X_List::prev()
X
X RETURNS: TRUE for success, FALSE for error
X
X Will move the "current node" pointer to the previous node in the list.
X
X Reference the function "prev_xlist".
X
X
Xint X_List::count()
X
X RETURNS: The number of valid nodes in the list
X
X Check the "C" function "get_count_xlist" above.
X
X
Xint X_List::set_user( void * )
X
X RETURNS: TRUE for success, FALSE for error
X
X Performs the function of "set_user_xlist".
X
X
Xvoid * X_List::get_user()
X
X RETURNS: The pointer of the user data area.
X
X You set this pointer with the constructor or with the
X "set_user" member function.
X
X
Xint X_List::nodenum()
X
X RETURNS: The number of the current node.
X
X Check out the "get_nodenum_xlist" function.
X
X
Xint X_List::goto_node( int )
X
X RETURNS: TRUE if success, FALSE on error
X
X Will set the "current node" pointer to the
X n'th item in the list as does the
X "goto_node" function.
X
X
X
X
X-----------------------------------------------------
X* UNIX is a trademark of AT&T
X* Amiga is a trademark of Commodore Business Machines
X* MS-DOS is a trademark of Microsoft Inc
X
X
SHAR_EOF
chmod 0640 x_list/docs || echo "restore of x_list/docs fails"
if [ $TOUCH = can ]
then
touch -am 0209213891 x_list/docs
fi
set `wc -c x_list/docs`;Wc_c=$1
if test "$Wc_c" != "10905"
then echo original size 10905, current size $Wc_c;fi
# ============= x_list/install ==============
echo "x - extracting x_list/install (Text)"
sed 's/^X//' << 'SHAR_EOF' > x_list/install &&
X **************************************
X * Installing the X_List source files *
X **************************************
X
X Let's get this legal stuff out of the way !
X
X
XThis text in this file is copyright (c) 1991 by Kenneth Jamieson.
X
XThe author may be reached at the US MAIL address listed below, or
Xby sending unix mail to ...
X
X tron1 at tronsbox.xei.com or
X ...!uunet!tronsbox.xei.com!tron1 or
X yelling "Hey Ken!" if you happen to be close enough.
X
X
X FOR ALL SYSTEMS
X ===============
X
X Since many of my shareware stuff build upon other parts of my
X shareware code, I am going to ask that you actually set aside a
X directory somewhere to unpack and build my code in. I realize that
X this is presumptuous of me, but it is a good way to solve certain
X problems.
X
X Once you have decided what that directory will be and made it,
X unpack this stuff into it. The resulting directory tree should look
X like this:
X
X (whatever) /--include Will hold all the completed include files
X | /
X \---------lib Will hold all the built libraries.
X \
X \--x_list (This code's home) doc files
X \
X \-src The source code for these routines.
X All the .h .c and make* files.
X
X Future shareware code will also install the finished .h and
X library files in that top level include and lib directories. This way,
X once you teach you compiler where to find THEM, you will always have
X my stuff there. (grin)
X
X By the way, you probably got some files called "foo" in
X one or two directories. They are there only to force the creation
X of those directories.
X
X
X UNIX INSTALLATION
X =================
X (If you got this as a shar or cpio, much of the directory set up
X is all done)
X
X 1) If your directory structure after unpacking doesn't look like the
X above .. fix it! ;-).
X
X 2) Copy make.unx to Makefile for SYSV.
X Copy make.bsd to Makefile for Berkley and SUNOS.
X
X 3) Edit the Makefile to reflect your site and paths, also to decide
X if you want to have the "C" or "C++" versions built.
X
X 4) Type "make".
X
X 5) If that worked, type "testit" to test the library. If not, report
X the bugs to me 1/2 :-) .
X
X 6) Type "make install", this will transfer the library and .h
X files out to the top level include and lib dirs.
X
X 7) Type "make clean" to delete the .o's and so on.
X
X 8) Have fun!
X
X
X AMIGA INSTALLATION
X ==================
X (If you got this as a shar or zoo, much of the directory set up
X is all done as long as you said "zoo e//" to unpack.)
X
X 1) If your directory structure after unpacking doesn't look like the
X above .. fix it! ;-).
X
X
X 2a) FOR SAS/C 5.10 REGULAR ANSI "C"
X
X Copy make.sas makefile.
X
X 2b) FOR LATTICE C++ VERSION 1.0
X
X Copy make.cpp makefile.
X
X
X 3) Edit the Makefile to reflect your site and paths.
X
X 4) Type "lmk".
X
X 5) If that worked, type "testit" to test the library. If not, report
X the bugs to me 1/2 :-) .
X
X 6) Type "make install", this will transfer the library and .h
X files out to the top level include and lib dirs.
X
X 7) Type "make clean" to delete the .o's and so on.
X
X 8) Have fun!
X
X
X
X MS-DOS TURBO C/C++ INSTALLATION
X ===============================
X
X (If you got this as a shar or zoo, much of the directory set up
X is all done as long as you said "zoo e//" to unpack.)
X
X 1) If your directory structure after unpacking doesn't look like the
X above .. fix it! ;-).
X
X 2) Copy make.tcc to makefile.
X
X 3) Edit the Makefile to reflect your site and paths and to select
X if you want the C++ stuff built for you.
X
X 4) Type "make".
X
X 5) If that worked, type "testit" to test the library. If not, report
X the bugs to me 1/2 :-) .
X
X NOTE: On some MS-DOS machines (MINE!) the makefile will
X fail and say "cannot load tcc.exe". I STRONGLY
X suspect that this is a memory problem. If you find
X a solution I would live it. On other machines it runs
X fine.
X
X If you are one of the lucky one's, don't despair.. do
X this at your DOS prompt:
X
X make -n > maketcc.bat
X
X Then just type "maketcc" and it will work fine but the
X "echo"'s messages are a bit messed. Sorry .. patch on the
X way as soon as I figure a way around it!
X
X 6) Type "make install", this will transfer the library and .h
X files out to the top level include and lib dirs.
X
X 7) Type "make clean" to delete the .o's and so on.
X
X 8) Have fun!
X
X
X
X-----------------------------------------------------
X* UNIX is a trademark of AT&T
X* Amiga is a trademark of Commodore Business Machines
X* MS-DOS is a trademark of Microsoft Inc
X
X
X-----------------------------------------------------
X* UNIX is a trademark of AT&T
X* Amiga is a trademark of Commodore Business Machines
X* MS-DOS is a trademark of Microsoft Inc
X
X
SHAR_EOF
chmod 0640 x_list/install || echo "restore of x_list/install fails"
if [ $TOUCH = can ]
then
touch -am 0209213891 x_list/install
fi
set `wc -c x_list/install`;Wc_c=$1
if test "$Wc_c" != "5022"
then echo original size 5022, current size $Wc_c;fi
# ============= x_list/readme ==============
echo "x - extracting x_list/readme (Text)"
sed 's/^X//' << 'SHAR_EOF' > x_list/readme &&
X
X :*:*:*:*: IMPORTANT :*:*:*:*:
X
X READ THE FILE "distrib" BEFORE TO BEGIN TO
X USE OR COMPILE THIS CODE!
X
X
X Hi ! X_List stands for "Xanadu List", it is a project that I have been
Xplaying with on and off for over a year. While there is not much code,
Xit has been a long road to understanding this stuff enough that I was
Xhappy with the results.
X
X I have always, as programmer, had a great fear of pointers. Well,
Xmaybe fear is to strong a word by I was certainly not fond of the little
Xdevils. And NOTHING will bring you face to face with pointers faster than
Xa good doubly linked list.
X
X I sat there. Oh, I could use some canned list routines, but
XI wanted to KNOW what was happening in there. I wanted to be able to
Xlook at the source and say "AHA!". Well, I couldn't. The routines I could
Xget the source to were way over my head, and not commented well.
X
X So what I have done is look at what MY needs for list processing
Xwere, under both C and C++, and write the routines to do them. Along the way,
XI have tried to comment the code pretty well, and in the file "lists" you will
Xfind a mini-tutorial about what a list is and why we use them. The code in
Xhere is probably not as commented as you would like (or me!) but it is better
Xthan most, and combined with "lists" you should be fine.
X
X This code is shareware, and so you should read the "distrib" file
Xbefore you use this code. It is pretty lenient I feel, and hopefully you
Xwon't find it restrictive. In addition, hopefully I can make some money for
Xa new hard drive ;-). Also, please upload this archive unaltered to any
XBBS or network to would like. Shareware lives by being spread!
X
X This code was developed with Turbo C++ 1.0 under the VP/ix emulator
Xof Interactive Systems Unix SysV3.2.
X
X Every attempt has been made to make this code run under the
Xfollowing environments:
X
X 1: Unix. Any ANSI C or C++ 2.0 variant. SYSV, BSD and SUNOS.
X (can anyone confirm g++?)
X
X 2: Ms-Dos. Turbo C++ and Turbo C.
X (can anyone confirm MSC?)
X
X 3: Amiga. Lattice C++ 1.0 and SAS/C 5.10
X Note: I used SAS/C 5.10 as the C back end to the
X Lattice C++ compiler.
X
X
X I personally run it under all three, in both C and C++ programs so
Xyou should be ok.
X
X Have fun! Read "distrib" and "install" next, "lists" for a
Xoverview of linked lists, and "docs" for the documentation for the routines
Xhere and happy listing!
X
X
XNOTE FOR UNIX USERS:
X
X Forgive the fact that these text files have dos format CR-LF line
Xterminators in them, there was no reason to have two versions and stripping
Xthem is easy enough.
X
X - Kenneth Jamieson
X
X
X
X-----------------------------------------------------
X* UNIX is a trademark of AT&T
X* Amiga is a trademark of Commodore Business Machines
X* MS-DOS is a trademark of Microsoft Inc
X
X
SHAR_EOF
chmod 0640 x_list/readme || echo "restore of x_list/readme fails"
if [ $TOUCH = can ]
then
touch -am 0209213891 x_list/readme
fi
set `wc -c x_list/readme`;Wc_c=$1
if test "$Wc_c" != "2856"
then echo original size 2856, current size $Wc_c;fi
# ============= x_list/lists ==============
echo "x - extracting x_list/lists (Text)"
sed 's/^X//' << 'SHAR_EOF' > x_list/lists &&
X
X *********
X * LISTS *
X *********
X
X
X Let's get this legal stuff out of the way !
X
X
XThis text in this file is copyright (c) 1991 by Kenneth Jamieson.
X
XThe author may be reached at the US MAIL address listed below, or
Xby sending unix mail to ...
X
X tron1 at tronsbox.xei.com or
X ...!uunet!tronsbox.xei.com!tron1 or
X yelling "Hey Ken!" if you happen to be close enough.
X
X
X Ok, now, about lists.... This will be a simple text to
Xintroduce some of the basic list theory so that you can use the
Xroutines in this library.
X
X I am using a "doubly linked list", this is a list where
Xevery piece of data knows where to find every other one... consider the
Xchart below. (I will number the "nodes" for clarity):
X
X 1-2-3-4-5
X
X That is a 5 node list, where the node on the left is the parent
Xor previous node, and the one on the right is the child or next node.
X
X Now, lets store some data here, and introduce a concept or two.
XI am going to stand the list on it's side this time.
X
X *1 (red)
X |
X 2 (green)
X |
X 3 (blue)
X |
X 4 (yellow)
X |
X 5 (orange)
X
X See the "*" ? I am going to use that to show the "current" node in
Xthe list. Now, we have put colors "in" the nodes. We can move that
X"*" up or down the list, to the next and previous nodes.
X
X We can replace the data that is in the current node, and we can
Xadd nodes to the end. Also, we can delete a node completely.
X
X Any list that you can move "previous: and "next" in is
Xdoubly-linked. A singly-linked list only lest you move "next".
X
X
X
XWHY USE LISTS AS A PROGRAMMER ?
X
X
X With respect to "C" programming, why do we use lists at all ?
X
X Let's say you are going to get a list of names from a user,
Xand you don't know how many names you will get. You have 2 choices if you
Xhave to keep those names in memory...
X
X 1) Allocate more space than you will "EVER" need.
X
X Advantage - You don't have to worry about lists! It is just
X an array for you!
X
X Disadvantage - You often allocate MUCH more space than you
X really use. Thus, you waste memory. Also, it is
X generally good to avoid putting limits into a program
X like "You can only enter 1000 names". A lack of
X limits makes your code efficient (space wise) and
X more flexible.
X
X 2) Use lists!
X
X Advantage - You never waste space (a bit on the list
X overhead .. but not that much usually). You can
X adapt to almost anything.
X
X Disadvantage - Lists are a pain! De-bugging list code
X can drive you up a wall!
X
X
X Since I obviously feel you will want to use lists, let's talk
X more about them....
X
X
X
X
XHOW TO IMPLEMENT A DOUBLY-LINKED LIST FOR C and C++:
X
X I am not going to go into great detail of all the low level code here,
Xbecause you can just go look at the source in x_list.c to see most of that.
XHere, we will take a look at the design considerations we should have for C
Xand C++.
X
X The natural thing to build a linked list of is pointers. This
Xallows us a lot of flexibility. Consider the example below....
X
Xstruct node{
X struct node * prev;
X struct node * next;
X void * data;
X}
X
X This structure will for the basis for our list. Because we want
Xa doubly-linked list, we have two list pointers here, on that points to the
Xaddress of the next node, and one to the previous node. The void * that
Xis there is the data we are going to store in the list. It is nice to
Xstore a pointer as the data of the list so that we do not
Xlimit the things we can use the list for.
X
X We can actually make a list out of these things. They are
Xcomplete to form a simple list. Consider the program below:
X
Xmain(){
X struct node node1;
X struct node node2;
X
X node1.prev = NULL;
X node1.next = &node2;
X node2.prev = &node1;
X node2.next = NULL;
X}
X
X
X That programs forms a list. Node1 knows where to find node2 and
Xthe opposite is true. There IS no previous node for node1 so that is
XNULL. In the same manner, there is no next node from node2 so that is also
Xset to NULL.
X
X That's it ! Thats the magic of lists. If I have a pointer to
Xnode2, I can find node one at &node2->prev and so on.
X
X Now, that is not EVERYTHING about it (it never is .. :-) ).
XThe whole point of the list is that we want to make it bigger as we
Xgo along, not declare it at the start of the program like we did above.
X
X So let's look at a minor variation:
X (I will show only the code here, assume that the structure
X "node" is defined for this program in a header file or something)
X
X
X1 #include <malloc.h> /* Get the memory stuff */
X2 main(){
X3 struct node * node1;
X4
X5 node1 = (struct node *)malloc( sizeof(struct node) );
X6 node1->prev = NULL;
X7
X8 node1->next = (struct node *)malloc( sizeof( struct node ) );
X9 node1->next->next = NULL;
X10 node1->next->prev = node1;
X11 }
X
X WHAT HAPPENED!! you say ?
X
X Trust me, it isn't that bad. Let's take it step by step.
X
X First, obviously it would not compile with those line numbers.
XOk.. second, you will see that we only declared one pointer. The
Xpointer for the first node. That is the ONLY pointer we cannot infer
Xfrom the list. YOU WILL ALWAYS HAVE AT LEAST ONE POINTER declared as
Xa "base" for the list.
X
X Step by step then....
X
XLINE 1 : We included the file for the malloc() call because we
X use that call this time.
X
XLINE 2 : Start the program :-).
X
XLINE 3 : Declare a place to store the pointer for node1.
X
XLINE 5 : We allocate space for our first node, and store the
X pointer for it in the variable node1.
X
XLINE 6 : There will never be a node BEFORE node1. So the
X address of the previous node in NULL. It is
X important that you PUT a NULL there yourself
X because you are not sure of it's value.
X
X The DEFINITION of the "head" or "top" of
X a list is "the node with no previous node". There
X will only ever be one node like this in a list.
X
XLINE 8 : We are going to save a step here. We are going to
X allocate space for another node, and store it's
X pointer right into the space for it in node1. In this
X manner, we do NOT need to declare another variable.
X
X While this looks confusing, it really isn't. The only
X place that the address of node2 is relevant from
X at this time is node1.
X
XLINE 9 : We are at the end of the list (we only have
X two nodes at this time) .. so there is no
X "next" node. Since we don't have a
X pointer for node2, we need to say "node1->next" every
X time we want to talk about node2, but there are ways to
X solve this problem in later examples.
X
XLINE 10: Now, to complete the list, we need to tell
X node2 about node1's address.
X
X So, we set the pervious node pointer in node2
X to be node1's pointer.
X
X
X The weave is now complete and we have a linked
Xlist. You can see though, that we need some better way to
Xmove from node to node. Because it would be a real pain
Xabout 5 nodes in ... could you imagine :
X
X node1->next->next->next->next
X
X It would get silly real fast!
X
X So, what I have done in this library is just
Xkeep another structure for each list. It has a pointer to the
Xfirst node in that list, a pointer to the last node, and a
Xpointer to the current node.
X
X The current node makes the list act a LOT like a
Xloose leaf notebook. If you think of an empty list, you have
Xa notebook with nothing in it at all. In this analogy, you
Xmust add a piece of paper before you can write anything into the
Xlist. You do that as I showed you above, by adding a new node.
X
X The current node is just a marker, an indication of
Xwhere the notebook is open to right now. If we continue or
Xexample above, we have the pointer to the first node in the
Xlist stored as "node1" ... we will want to deal with node2 to
Xfor a while, so we can just say ...
X
X current_node = node1->next;
X
X Get it ?? This way, we don't have to say "node1->next"
Xall the time. When the time comes to deal with node1 again, we can
Xjust say ...
X
X current_node = node1;
X
X And there we are.
X
X Now, in a list with many nodes, it is even more important
Xbecause to get to node 5 it is tough to say ..
X
X current-node = node1->next->next->next->next;
X
X But it is EASY to say ....
X
X current_node = node1;
X for( x = 0; x < 4; x++ ){
X current_node = current_node->next;
X }
X
X THAT code can take us to the 5 node in the list as well,
Xbecause we can just keep advancing. If we are at node 5, and want
Xto get to node 4, we can just say ..
X
X current_node = current_node->prev;
X
X So, you see that if you have the concept of a current node,
Xand the pointer to the first node in the list, you are capable
Xof going forward and backwards in the list.
X
X Since the last node of a list is the only node with a
Xnext pointer of NULL, we can find it very easy now.
X
X if( current_node->next |= NULL ){
X current_node = current_node->next;
X }
X
X That will leave current_node set to the last node in the
Xlist without any trouble at all, no matter where you happen to
Xbe.
X
X The last thing I will show you about is how to delete a
Xnode. Suppose we want to remove the current_node from the list
Xcompletely. What do we have to do ???? Well, the parent of the
Xcurrent node has to be pointed to the child of the current
Xnode so that the chain is not broken..
X
X current_node->prev->next = current_node->next;
X
X And the child of the current node has to be told of
Xit's new parent (since it isn't us any more!)..
X
X current_node->next->prev = current_node->prev;
X
X Now, the chain is intact, and the ONLY place there is a
Xpointer to the current node is in the current_node variable! We
Xwant to free that memory, so we should say ...
X
X free(current_node);
X current_node = node1;
X
X That de-allocates that memory, and leaves us with a
Xvalid current node pointer.
X
X Now you should be able to look at my code and have
Xsome idea what it is doing. Have fun!
X
X
X
SHAR_EOF
chmod 0640 x_list/lists || echo "restore of x_list/lists fails"
if [ $TOUCH = can ]
then
touch -am 0209213891 x_list/lists
fi
set `wc -c x_list/lists`;Wc_c=$1
if test "$Wc_c" != "9972"
then echo original size 9972, current size $Wc_c;fi
rm -f s3_seq_.tmp
echo "You have unpacked the last part"
exit 0
--
========[ Xanadu Enterprises Inc. Amiga & Unix Software Development]=======
= "I know how you feel, you don't know if you want to hit me or kiss me - =
= --- I get a lot of that." Madonna as Breathless Mahoney (Dick Tracy) =
=========== Ken Jamieson: uunet!tronsbox.xei.com!tron1 ===================
= NONE of the opinions represented here are endorsed by anybody. =
=== The Romantic Encounters BBS 201-759-8450(PEP) / 201-759-8568(2400) ====
More information about the Alt.sources
mailing list