Source Code 1994 March/Source_Code_CD-ROM_Walnut_Creek_March_1994.iso/compsrcs/reviewed/volume03/chipset2/08

Text File | 1993-03-13 | 18.8 KB | 779 lines

From decwrl!athertn!sander.cupertino.ca.us![e-mail] Wed Jan  6 13:53:38 EST 1993
Submit chipset-2 08/10
#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 8 (of 10)."
# Contents:  src/list/dlist.man
# Wrapped by paul@sander on Sun Nov 22 15:41:54 1992
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f src/list/dlist.man -a "${1}" != "-c" ; then
  echo shar: Will not over-write existing file \"src/list/dlist.man\"
else
echo shar: Extracting \"src/list/dlist.man\" \(16973 characters\)
sed "s/^X//" >src/list/dlist.man <<'END_OF_src/list/dlist.man'
X.TH DLIST
X.SH NAME
Xdll_dump, dll_setup, dll_freeSetup, dll_new, dll_destroy,
Xdll_traverse, dll_rank, dll_delRank, dll_data, dll_setData,
Xdll_first, dll_next, dll_last, dll_prev, dll_join
X-- General purpose doubly-linked list manipulation
X.sp
Xdll_search, dll_insert, dll_delete -- Sorted doubly-linked list manipulation
X.sp
Xdll_pushf, dll_pushr, dll_push, dll_popf, dll_popr, dll_pop, dll_peekf,
Xdll_peekr, dll_peek
X-- Unsorted doubly-linked list manipulation
X.SH SYNOPSIS
X#include <dlist.h>
X.sp
X#ifdef __STDC__
X.sp
XDLL_SETUP dll_setup(int(*comp)(void*,void*), void *data)
X.sp
Xvoid dll_freeSetup(DLL_SETUP setup)
X.sp
XDL_LIST dll_new(DLL_SETUP setup)
X.sp
Xvoid dll_destroy(DL_LIST list, void (*free_key)(void*,void*),
Xvoid (*free_data)(void*,void*), void *info)
X.sp
Xint dll_insert(DL_LIST list, void *key, void *data)
X.sp
Xvoid    *dll_delete(DL_LIST list, void *key, void **data)
X.sp
Xvoid *dll_search(DL_LIST list, void *target, void **data)
X.sp
Xvoid dll_traverse(DL_LIST list, void (*fn)(void*,void*,void*), void *parms)
X.sp
Xvoid dll_dump(DL_LIST list, void (*key_dump)(void*,void*,void*), void *info)
X.sp
Xvoid *dll_first(DL_LIST list, void **data)
X.sp
Xvoid *dll_last(DL_LIST list, void **data)
X.sp
Xvoid *dll_next(DL_LIST list, void **data)
X.sp
Xvoid *dll_prev(DL_LIST list, void **data)
X.sp
XDL_LIST dll_join(DL_LIST list1, DL_LIST list2)
X.sp
Xvoid *dll_rank(DL_LIST list, int rank, void **data)
X.sp
Xvoid *dll_delRank(DL_LIST list, int rank, void **data)
X.sp
Xvoid *dll_data(DL_LIST list)
X.sp
Xvoid dll_setData(DL_LIST list, void *data)
X.sp
Xvoid *dll_pushf(DL_LIST list, void *key, void *data)
X.sp
Xvoid *dll_pushr(DL_LIST list, void *key, void *data)
X.sp
Xvoid *dll_push(DL_LIST list, int where, void *key, void *data)
X.sp
Xvoid *dll_popf(DL_LIST list, void **data)
X.sp
Xvoid *dll_popr(DL_LIST list, void **data)
X.sp
Xvoid *dll_pop(DL_LIST list, int where, void **data)
X.sp
Xvoid *dll_peekf(DL_LIST list, void **data)
X.sp
Xvoid *dll_peekr(DL_LIST list, void **data)
X.sp
Xvoid *dll_peek(DL_LIST list, int where, void **data)
X.sp
X#else
X.sp
XDLL_SETUP dll_setup(comp, data)
X.br
Xint    (*comp)();
X.br
Xvoid    *data;
X.sp
Xvoid dll_freeSetup(setup)
X.br
XDLL_SETUP    setup;
X.sp
XDL_LIST dll_new(setup)
X.br
XDLL_SETUP    setup;
X.sp
Xvoid dll_destroy(list,free_key,free_data,info)
X.br
XDL_LIST    list;
X.br
Xvoid    (*free_key)();
X.br
Xvoid    (*free_data)();
X.br
Xvoid    *info;
X.sp
Xint dll_insert(list,key,data)
X.br
XDL_LIST    list;
X.br
Xvoid    *key;
X.br
Xvoid    *data;
X.sp
Xvoid    *dll_delete(list,key,data)
X.br
XDL_LIST    list;
X.br
Xvoid    *key;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_search(list,target,data)
X.br
XDL_LIST    list;
X.br
Xvoid    *target;
X.br
Xvoid    **data;
X.sp
Xvoid dll_traverse(list,fn,parms)
X.br
XDL_LIST    list;
X.br
Xvoid    (*fn)();
X.br
Xvoid    *parms;
X.sp
Xvoid dll_dump(list,key_dump,info)
X.br
XDL_LIST    list;
X.br
Xvoid    (*key_dump)();
X.br
Xvoid    *info;
X.sp
Xvoid *dll_first(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_last(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_next(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_prev(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    **data;
X.sp
XDL_LIST dll_join(list1,list2)
X.br
XDL_LIST list1;
X.br
XDL_LIST list2;
X.sp
Xvoid *dll_rank(list,rank,data)
X.br
XDL_LIST    list;
X.br
Xint    rank;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_delRank(list,rank,data)
X.br
XDL_LIST    list;
X.br
Xint    rank;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_data(list)
X.br
XDL_LIST    list;
X.sp
Xvoid dll_setData(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    *data;
X.sp
Xvoid *dll_pushf(list,key,data)
X.br
XDL_LIST    list;
X.br
Xvoid    *key;
X.br
Xvoid    *data;
X.sp
Xvoid *dll_pushr(list,key,data)
X.br
XDL_LIST    list;
X.br
Xvoid    *key;
X.br
Xvoid    *data;
X.sp
Xvoid *dll_push(list,where,key,data)
X.br
XDL_LIST    list;
X.br
Xint    where;
X.br
Xvoid    *key;
X.br
Xvoid    *data;
X.sp
Xvoid *dll_popf(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_popr(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_pop(list,where,data)
X.br
XDL_LIST    list;
X.br
Xint    where;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_peekf(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_peekr(list,data)
X.br
XDL_LIST    list;
X.br
Xvoid    **data;
X.sp
Xvoid *dll_peek(list,where,data)
X.br
XDL_LIST    list;
X.br
Xint    where;
X.br
Xvoid    **data;
X.sp
X#endif
X.SH DESCRIPTION
XThese functions implement a doubly-linked list data structure.  The list
Xitself stores only pointers to the client's data, and relies on
Xclient-provided functions for any comparisons and storage deallocation.
X.sp
X.B dll_setup
Xbuilds a setup structure before a doubly-linked list can be created,
Xand returns a pointer to it;
XNULL is returned if an error occurs.  The setup structure is a magic
Xcookie that can be used to set up many doubly-linked lists.
XIt must be freed by calling
X.BR dll_freeSetup .
XThe setup structure can be freed any time after
X.B dll_new
Xis called.
XThe client specifies a pointer to a function that compares two
Xclient-provided data structures.  The comparison function,
X.BR comp ,
Xhas the following interface:
X.RS
X.B
Xint comp(k1,k2)
X.br
X.B
Xvoid *k1,*k2;
X.RE
XThe result of this function is less than 0 if the object pointed to by k1 is
X"less than"
Xthe object pointed to by k2, 0 if they are "equal", and greater than 0
Xotherwise.
XClient-provided data structures that
Xcompare greater by this function will appear later in the lexical order
Xof the data stored in the list.
XThis pointer may be NULL if none of the sorted list functions are called.
XThe client may also specify the initial value of the data returned by
X.B dll_getData
Xafter a list is instantiated.
X.sp
X.B dll_freeSetup
Xfrees the setup structure created by
X.BR dll_setup .
XIt can be called any time after
X.B dll_new
Xis called.  Doubly-linked lists do not require their setup structures to exist
Xafter they are created.
X.sp
X.B dll_new
Xcreates a new doubly-linked list.  Given a DLL_SETUP setup structure,
X.B dll_new
Xreturns a pointer to a handle for the doubly-linked list,
Xor NULL if an error occurs.
X.sp
X.B dll_destroy
Xdeallocates all storage allocated to a doubly-linked list.
XThe client provides pointers
Xto visitation functions that are called once for each item stored in the
Xlist.  The items are visited in arbitrary order.  If
XNULL is passed instead of a pointer to a function, no action is taken for
Xthe client-provided data or key, but the list structure itself is freed.
XThe
X.B free_key
Xand
X.B free_data
Xparameters specify functions that free the keys and user-specified data
Xstored in the list.  The
X.B free_data
Xfunction is always called before the
X.B free_key
Xfunction.  The
X.B info
Xparameter is passed along to the visitation functions without modification.
XThe interfaces for these functions follow:
X.sp
X    void freeThis(keyOrData,info)
X.br
X    void    *keyOrData;
X.br
X    void    *info;
X.sp
X.B dll_insert
Xinserts a new item into a sorted list.  1 is returned if the insertion was
Xsuccessful, -1 is returned if the new key matches another key that has
Xalready been inserted into the list, and 0 is returned in the event of an
Xerror.  The
X.B data
Xparameter is a pointer to a user-defined data structure that is stored with
Xthe key, and can be retrieved by any access or deletion function.
X.sp
X.B dll_delete
Xdeletes an item from an sorted list.
XThe value returned is the key value passed to
X.B dll_insert
Xwhen the item was inserted, or NULL if the item is not found.  The
X.B data
Xparameter returns the pointer stored with the key when
X.B dll_insert
Xwas called, or is undefined when the key is not found.
X.sp
X.B dll_search
Xsearches for an item in a sorted list.
XThe value returned is the key value passed to
X.B dll_insert
Xwhen the item was inserted, or NULL if the item is not found.  The
X.B data
Xparameter returns the pointer stored with the key when
X.B dll_insert
Xwas called, or is undefined if the key is not found.
X.sp
X.B dll_traverse
Xtraverses the list, calling a client-provided visitation function
X.B fn
Xonce for each item stored there.
X.B fn
Xhas the following interface:
X.RS
X.B
Xvoid fn(item,parms,data)
X.br
X.B
Xvoid *item;
X.B
X.br
X.B
Xvoid *parms;
X.br
X.B
Xvoid *data;
X.RE
X.B item
Xis the key pointer stored when the item was inserted into the list.
X.B parms
Xis an arbitrary pointer that the client wishes to pass to the visitation
Xfunction, but is otherwise unused by the doubly-linked list implementation.
X.B data
Xis a pointer to a user-defined structure that is stored with the key when
Xthe item is stored in the list.
XItems are visited in their lexical order if the list is sorted.  If the list
Xis not sorted, items are visited in the order they were inserted via
X.B dll_pushr
Xor in the reverse order they were inserted via
X.BR dll_pushf .
X.sp
X.B dll_dump
Xdisplays the contents of the list to stdout, along with some diagnostic and
Xstatistical information.  The
X.B key_dump
Xfunction is called once for each item in the list, in arbitrary order.  It
Xmay be NULL if no action is desired.  Its interface follows:
X.RS
X.B
Xvoid key_dump(key,data,info)
X.br
X.B
Xvoid *key;
X.br
X.B
Xvoid *data;
X.br
X.B
Xvoid *info;
X.RE
XWhere
X.B key
Xis a key stored in the doubly-linked list, and
X.B data
Xis the user-defined pointer stored with the key at the time the item was
Xinserted into the list.
X.sp
X.B dll_first
Xreturns the item that falls earliest in the lexical order of the items
Xstored in an ordered list,
Xthe earliest item pushed onto the list via dll_pushr,
Xthe latest item pushed onto the list via dll_pushf,
Xor NULL if the list is empty.  The user-defined pointer
Xstored with the key is also returned in the
X.B data
Xparameter.
X.sp
X.B dll_last
Xreturns the item that falls latest in the lexical order of the items
Xstored in a sorted list,
Xthe latest item pushed onto the list via dll_pushr,
Xthe earliest item pushed onto the list via dll_pushl,
Xor NULL if the list is empty.  The user-defined pointer
Xstored with the key is also returned in the
X.B data
Xparameter.
X.sp
X.B dll_next
Xreturns the next item toward the end of the doubly-linked list after the last
Xcall to
X.BR dll_first ,
X.BR dll_next ,
X.BR dll_prev ,
X.BR dll_rank ,
Xor
X.BR dll_search.
XIf the list is sorted, the key is the next higher one in the lexical order
Xof the keys stored in the list.
XIf
X.B dll_search
Xfailed to find an item,
X.B dll_next
Xreturns the next item higher in the lexical order that was stored in the list.
XNULL is returned if the end of the list is overrun, or if the list has been
Xmodified since the last call to
X.BR dll_first ,
X.BR dll_next ,
X.BR dll_prev ,
X.BR dll_rank ,
Xor
X.BR dll_search.
XIf an item is found, the user-defined pointer stored with the key is also
Xreturned in the
X.B data
Xparameter.
X.sp
X.B dll_prev
Xreturns the next item toward the beginning of the doubly-linked list after the
Xlast call to
X.BR dll_last ,
X.BR dll_next ,
X.BR dll_prev ,
X.BR dll_rank ,
Xor
X.BR dll_search.
XIf the list is sorted, the key is the next lower one in the lexical order
Xof the keys stored in the list.
XIf
X.B dll_search
Xfailed to find an item,
X.B dll_prev
Xreturns the next item lower in the lexical order that was stored in the list.
XNULL is returned if the beginning of the list is overrun, or if the list has
Xbeen modified since the last call to
X.BR dll_last ,
X.BR dll_next ,
X.BR dll_prev ,
X.BR dll_rank ,
Xor
X.BR dll_search.
XIf an item is found, the user-defined pointer stored with the key is also
Xreturned in the
X.B data
Xparameter.
X.sp
X.B dll_join
Xconcatenates two lists and returns the result.  The lists can be concatenated
Xonly if the following conditions are met:  Both lists are non-empty; if the
Xlists are ordered, their comparison function pointers must be identical, and
Xthe last item in the first list must not be lexically higher than the first
Xitem in the second list; if both lists have their global data items set, then
Xthey must be identical (otherwise, at most one of the global data items can
Xbe set and it is added to the result).  If either list pointer is NULL, then
Xthe other list is returned.  If one list is empty and the other list's global
Xdata item is set, then the non-empty list is returned with its global data
Xitem set to the second list's global data item.  In any case, both parameters
Xpassed to
X.B dll_join
Xshould be considered invalid after the call, and only its return value should
Xbe used.  List handles are destroyed as appropriate.
X.sp
X.B dll_rank
Xreturns the key in the doubly-linked list that falls in the
X.BR rank th
Xposition in the list.
XThe
X.B rank
Xparameter is zero-based.
XNULL is returned if the specified rank is less than 0 or greater or equal to
Xthe number of keys stored in the list.
XIf the call succeeds, the list is left in a state such that
X.B dll_next
Xand
X.B dll_prev
Xbehave as expected.  The user-defined pointer stored with the key is also
Xreturned in the
X.B data
Xparameter.
X.sp
X.B dll_delRank
Xdeletes the key stored in the specified position in the doubly-linked list.
XThe value returned is the same as that passed to
X.BR dll_insert ,
X.BR dll_pushf ,
Xor
X.B dll_pushr
Xwhen the item was inserted, or NULL if the specified
X.B rank
Xis invalid.
X.B rank
Xis zero-based, and must be less than the number of keys stored in the list.
XThe user-defined pointer stored with the key is also returned in the
X.B data
Xparameter.
X.sp
X.B dll_data
Xreturns a client-defined pointer that is stored in the list handle.  This
Xpointer is set by calling
X.BR dll_setData .
XThis pointer is otherwise unused by the doubly-linked list implementation,
Xbut is useful for storing data with the list as a whole.
X.sp
X.B dll_setData
Xsets a list's global pointer that is returned by
X.BR dll_data .
X.sp
X.B dll_pushf
Xinserts an item at the beginning of an unsorted list.  It returns the
X.B key
Xparameter if it is successful, NULL otherwise.
X.sp
X.B dll_pushr
Xinserts an item at the back of an unsorted list.  It returns the
X.B key
Xparameter if it is successful, NULL otherwise.
X.sp
X.B dll_push
Xinserts an item at one end of an unsorted list.
XIf DLL_FRONT is passed as the
X.B where
Xparameter, the item is pushed onto the front of the list.
XIf DLL_BACK is passed as the
X.B where
Xparameter, the item is pushed onto the back of the list.  It returns the
X.B key
Xparameter if it is successful, NULL otherwise.
X.sp
X.B dll_popf
Xdeletes an item from the beginning of a list, returning the key stored when
Xthe item was inserted.  The data stored with the key is returned in the
X.B data
Xparameter.
X.sp
X.B dll_popr
Xdeletes an item from the back of a list, returning the key stored when the
Xitem was inserted.  The data stored with the key is returned in the
X.B data
Xparameter.
X.sp
X.B dll_pop
Xdeletes an item from one end of a list, returning the key stored when the
Xitem was inserted.  The data stored with the key is returned in the
X.B data
Xparameter.
XIf DLL_FRONT is passed as the
X.B where
Xparameter, the item is deleted from the front of the list.
XIf DLL_BACK is passed as the
X.B where
Xparameter, the item is deleted from the back of the list.
X.sp
X.B dll_peekf
Xreturns the key stored at the beginning of the list, without modifying the
Xstate of the list in any way.  It differs from
X.B dll_first
Xin that it does not affect subsequent calls to
X.B dll_next
Xor
X.BR dll_prev .
XThe data stored with the key is returned in the
X.B data
Xparameter.
X.sp
X.B dll_peekr
Xreturns the key stored at the back of the list, without modifying the
Xstate of the list in any way.  It differs from
X.B dll_last
Xin that it does not affect subsequent calls to
X.B dll_next
Xor
X.BR dll_prev .
XThe data stored with the key is returned in the
X.B data
Xparameter.
X.sp
X.B dll_peek
Xreturns the key stored at one end of the list, without modifying the
Xstate of the list in any way.  If DLL_FRONT is passed as the
X.B where
Xparameter, the key at the beginning of the list is returned.  If DLL_BACK
Xis passed as the
X.B where
Xparameter, the key at the back of the list is returned.
XThis call does not affect subsequent calls to
X.B dll_next
Xor
X.BR dll_prev .
XThe data stored with the key is returned in the
X.B data
Xparameter.
X.sp
X.B NOTE:
XNULL can safely be passed as the
X.B data
Xparameter in any of the access functions
X.RB ( dll_search ,
X.BR dll_first ,
X.BR dll_next ,
X.BR dll_last ,
X.BR dll_peek ,
X.BR dll_peekf ,
X.BR dll_peekr ,
X.BR dll_prev ,
Xor
X.BR dll_rank )
Xor deletion functions
X.RB ( dll_pop ,
X.BR dll_popf ,
X.BR dll_popr ,
X.BR dll_delete ,
Xor
X.BR dll_delRank ).
X.sp
XWorst case performance characteristics are listed below.
XHere, "n" is the number of items stored in the list.
X.RS
Xdll_search:    O(n)
X.br
Xdll_new:        O(1)
X.br
Xdll_destroy:    O(n)
X.br
Xdll_insert:    O(n)
X.br
Xdll_pushf:    O(1)
X.br
Xdll_pushr:    O(1)
X.br
Xdll_push:    O(1)
X.br
Xdll_delete:    O(n)
X.br
Xdll_popf:    O(1)
X.br
Xdll_popr:    O(1)
X.br
Xdll_pop:    O(1)
X.br
Xdll_traverse:    O(n)
X.br
Xdll_next:        O(1)
X.br
Xdll_prev:        O(1)
X.br
Xdll_first:        O(1)
X.br
Xdll_last:        O(1)
X.br
Xdll_rank:    O(n)
X.br
Xdll_delRank:    O(n)
X.br
Xdll_peekf:    O(1)
X.br
Xdll_peekr:    O(1)
X.br
Xdll_peek:    O(1)
X.br
Xdll_data:    O(1)
X.br
Xdll_setData:    O(1)
X.RE
X.SH BUGS
XThis implementation has not been tested on nearly
Xenough platforms.
X.sp
X.B dll_dump
Xassumes that pointers are the same size as integers, and that they can be
Xdisplayed in total in eight hexidecimal digits.
X.sp
X.B dll_destroy
Xdoes not touch the list's global data pointer, i.e. the pointer returned by
X.BR dll_data .
XIf this pointer is used, the client must explicitly free any data.
END_OF_src/list/dlist.man
if test 16973 -ne `wc -c <src/list/dlist.man`; then
    echo shar: \"src/list/dlist.man\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of archive 8 \(of 10\).
cp /dev/null ark8isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 9 10 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 10 archives.
    echo "Now edit common.mk and do a 'make all'"
    rm -f ark[1-9]isdone ark[1-9][0-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0