Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk1.iso/altsrc/articles/11146

Internet Message Format | 1994-08-20 | 50KB

Path: wupost!udel!news.udel.edu!darwin.sura.net!howland.reston.ans.net!agate!darkstar.UCSC.EDU!news.hal.COM!decwrl!src.dec.com!crl.dec.com!nntpd.lkg.dec.com!mrnews.mro.dec.com!zuunix.zuo.dec.com!pbs
From: [e-mail] (Philip Shearer @ZUO-DC EBS-Team)
Newsgroups: alt.sources
Subject: tsearch(3) replacment with tseachAVL btree
Followup-To: comp.unix.programmer
Date: 19 Aug 1994 16:14:03 GMT
Organization: Digital Equipment Corporation - Marlboro, MA
Lines: 1842
Message-ID: <332lob$[e-mail]>
NNTP-Posting-Host: zuunix.zuo.dec.com
Summary: C source replacment of tsearch(3) with tseachAVL() btree.
Keywords: tsearch AVL btree
X-Newsreader: Tin 1.1 PL3

Archive-name: tsearchAVL
Submitted-by: [e-mail]

echo "-------------------------X---CUT HERE---X--------------------------------"
echo "This is a shell archive (shar)  file."
echo "Fri Aug 19 17:35:03 MET DST 1994"
echo "To unpack. Remove everything above including the line 'CUT HERE',"
echo "save in a file, and unpack with 'sh file'."
echo this shar file contains:
echo  -rw-r--r--   1 pbs      users       4734 Aug 19 17:33 README
echo  -rw-r--r--   1 pbs      users       3447 Aug 19 17:06 avltree.h
echo  -rw-r--r--   1 pbs      users      24344 Aug 19 17:04 avltree.c
echo  -rw-r--r--   1 pbs      users       4894 Aug 19 14:32 atest.c
echo  -rw-r--r--   1 pbs      users       5531 Aug 17 14:43 btest.c
echo  -rw-r--r--   1 pbs      users        961 Aug 19 15:32 makefile
echo
echo "If this archive is complete, you will see the following message at the end:"
echo shar: End of shell archive.
echo
if test -f README -a README != "-c" ; then
    echo shar: Will not over-write existing file "README"
else
echo shar: Extracting README \(      4735 characters\)
sed 's/^X//'<< 'END_OF_README' > README
XSubject: tsearch(3) replacment with tseachAVL btree
XFollowup-To: comp.unix.programmer
X
XArchive-name: tsearchAVL
XSubmitted-by: [e-mail]
X
XCopyright (c) 1992 Lomarline Ltd
X@(#)avltree README 1.2 8/16/94 14:34:18 LMRN
X_POSIX_SOURCE complient.
XCompiler(s)  : SunOS 4.1, System V Rel 3, OSF1
X
XPermission to use, copy, modify, distribute, and sell this software and
Xits documentation for any purpose is hereby granted without fee, provided
Xthat the above copyright notices and this permission notice appear in
Xall copies of the software and related documentation.
X
XTHE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
XEXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
XWARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
X
XIN NO EVENT SHALL LOMARLINE LTD BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
XINDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER
XRESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF THE
XPOSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT OF OR
XIN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
X
X
X
X
XReplacement functions to perform tsearch etc, with a AVL balanced tree
Xstructure. AVL balance is when the height of left and right subtree
Xfrom each node differ by one at most.
X
X  void *tsearchAVL( void *key, void **rootp, int (*compar)() );
X  void *tfindAVL( void *key, void **rootp, int (*compar)() );
X  void *tdeleteAVL( void *key, void **rootp, int (*compar)() );
X  void twalkAVL( void *root, void (*action)() );
X
XSee the manual entries for tsearch(3) for more details.
X
XHow to use this code:
X---------------------
X
XThe make files and the example programs sould be self explanitory.
X
XIf you wish to use the avltree.c module as strait replacement for
Xthe standard library calls compile the module with -DAVL.
X
XAdd #include "avltree.h" to your source file and recomplie your
Xsource with -DAVL and link in the avltree.o module.
X
XThe header file "avltree.h" has in it #defines which replace
Xthe standard tsearch() with tsearchAVL() etc if the AVL flag is set.
X
X
XIf you wish to take advantage of tdeleteAVL returning a pointer to
Xthe information of the deleted node so that it can be freed then
Xcompile the avltree.c module without the -DAVL.
X
XAdd #include "avltree.h" to your source files, alter the tsearch() to
XtsearchAVL() etc and then compile your source without the -DAVL flag
Xand  link in the avltree.o module.
X
XWARNING:
X--------
X
XWith reference to the above.
X
XThere is one area where theses functions move away from the standard.
XIf the module avltree.c is compiled without the AVL flag set then
Xthe tdelete function returns a pointer to the information containd in the
Xdeleted node rather than the address of a pointer to the parent node
Xinformation.
X
XThis is because the parent node is not of much use in an AVL tree.
XThe pointer to the information contained in the deleted not is of more
Xuse because this information can then be freed by the user application
Xif necessary.
X
XWhat is the advantage of an AVL tree?
X-------------------------------------
X
XThere are two fundemental problems with a B tree.
X
XThe furthur away that the data is form random when placed into a btree
Xthe greater the liklyhood of degeneration. In the worst case if the
Xdata is sorted the the data will not be in a tree but a linked list.
X
XOver time as inserts and deletes are made a tree structure may
Xdegenerate.
X
XAVL trees take care of both theses problems becase the software
Xautomaticaly rebalances the tree so that it is never more than one level
Xaway from balance.
X
XSo the AVL tree will automate away the need to worry about the ordering
Xof data placed into a btree.
X
XUnless your data is close to random and you do not intend to delete
Xand insert more than you find then tsearchAVL will probably
Xbe usefull for you.
X
XCredits
X-------
X
XThis software was origenally written by Neil Barker for a project
Xwhich went belly up for lack of funds.
X
XI, Philip Shearer modified the source for clartity and so that the
Xreturns were consistent with those of the standard library.
X
XTo help find the bugs I looked at:
XAVL Trees V2.0, 5-September-1993 Paul Vixie, a copy of which is kept on
Xgatekeeper.dec.com
X93.09.06 pub/usenet/comp.sources.unix/volume27/avl-subs/part01
X
X(If we had known about an earlier version of this code back in 1990 we
Xwould never have written our own!)
X
XNeil used the same book as Paul Vixie
X
XAlgorithms & Data Structures
XNiklaus Wirth, Prentice-Hall 1986, ISBN 0-13-022005-1.
X
XWhich explains why the code looks some what similar.
XWhile debugging the code I did not have A&DS to hand so I used one called:
X
XData structures in ANSI C
XS. Sengupta and P. Edwards, Academic Press 1991, ISBN 0-12-635655-1.
X
END_OF_README
if test       4735 -ne `wc -c < README `; then
    echo shar: \"README\" unpacked with wrong size!       4735
fi
# end of overwriting check
fi
if test -f avltree.h -a README != "-c" ; then
    echo shar: Will not over-write existing file "avltree.h"
else
echo shar: Extracting avltree.h \(      3447 characters\)
sed 's/^X//'<< 'END_OF_avltree.h' > avltree.h
X#ifndef __AVLTREE_H
X#define __AVLTREE_H
X
X/*
X SCCS stuff
X*/
X
X#ifndef SCCS     /* only pick up one SCCS string per module */
X# define SCCS
X# ifndef    lint
X    static char e4d_sccs[] = "@(#)avltree.h  1.2 8/16/94 14:34:18 LMRN";
X#  ifndef COPYRIGHT
X#    define COPYRIGHT
X     static char copyright[] =  "@Copyright (c) 1992 Lomarline " ;
X#  endif
X# endif
X#endif
X/*------------------------------------------------------------------------------
X * Notice:
X * Permission to use, copy, modify, distribute, and sell this software and
X * its documentation for any purpose is hereby granted without fee, provided
X * that the above copyright notices and this permission notice appear in
X * all copies of the software and related documentation.
X *
X * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
X * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
X * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
X *
X * IN NO EVENT SHALL LOMARLINE LTD BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
X * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER
X * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF THE
X * POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT OF OR
X * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
X *------------------------------------------------------------------------------
X*/
X
X/*
X* This is modle should complement the standard search.h functions.
X*/
X
X#include  <search.h>
X
X/*------------------------------------------------------------------
X*To relace the standard binary tree unix functions with the avl ones
X*set AVL in the comple line to -DAVL
X*----------------------------------*/
X#ifdef AVL
X#    define tsearch(kp,rpp,cfn) tsearchAVL(kp,rpp,cfn)
X#    define tfind(kp,rpp,cfn)   tfindAVL(kp,rpp,cfn)
X#    define tdelete(kp,rpp,cfn) tdeleteAVL(kp,rpp,cfn)
X#    define twalk(rp,afn)       twalkAVL(rp,afn)
X#endif
X/*-------------------------------------------------------------------
X* if the std_header <search.h> is included in the module
X* then this VISIT enunerated type will already be defined so
X* watch out for a clash.
X*--------------------*/
X
X
X#ifdef USE_THIS_VISIT
X#undef USE_THIS_VISIT
X#endif
X
X#ifdef __osf__
X#if ! defined ( _SEARCH_H_ ) || ! defined _XOPEN_SOURCE
X#        define USE_THIS_VISIT
X#    endif
X#endif
X
X
X#ifdef USE_THIS_VISIT
X    typedef enum { preorder, postorder, endorder, leaf } VISIT;
X#endif
X
X/*------------------------------------------------------------------*/
X#if defined( __STDC__ ) && ! defined( NeedFunctionPrototypes )
X#define NeedFunctionPrototypes
X#endif
X
X/*------------------------------------------------------------------*/
X#if defined ( __cplusplus ) && ! defined ( _BEGIN_CPLUSPLUS )
X#    define _BEGIN_CPLUSPLUS extern "C" {
X#    define _END_CPLUSPLUS }
X#endif
X
X_BEGIN_CPLUSPLUS
X
Xextern void    *tsearchAVL(
X#ifdef NeedFunctionPrototypes
X     const void *key,
X     void **rootp,
X     int (*compar)( const void *, const void * )
X#endif
X);
X
Xextern void    *tfindAVL(
X#ifdef NeedFunctionPrototypes
X     const void *key,
X     void **rootp,
X     int (*compar)( const void *, const void * )
X#endif
X);
X
Xextern void    *tdeleteAVL(
X#ifdef NeedFunctionPrototypes
X     const void *key,
X     void **rootp,
X     int (*compar)( const void *, const void * )
X#endif
X);
X
Xextern void twalkAVL(
X#ifdef NeedFunctionPrototypes
X    const void * root,
X    void (*action)(const void *, VISIT, int )
X#endif
X);
X_END_CPLUSPLUS
X
X#endif /* __AVLTREE_H */
END_OF_avltree.h
if test       3447 -ne `wc -c < avltree.h `; then
    echo shar: \"avltree.h\" unpacked with wrong size!       3447
fi
# end of overwriting check
fi
if test -f avltree.c -a README != "-c" ; then
    echo shar: Will not over-write existing file "avltree.c"
else
echo shar: Extracting avltree.c \(     24344 characters\)
sed 's/^X//'<< 'END_OF_avltree.c' > avltree.c
X#ifndef _POSIX_SOURCE
X#   define _POSIX_SOURCE 1
X#endif
X
X/*
X SCCS stuff
X*/
X
X#ifndef SCCS     /* only pick up one SCCS string per module */
X# define SCCS
X# ifndef    lint
X   static char e4d_sccs[] = "@(#)avltree.c    1.2 8/16/94 14:34:18 LMRN";
X#  ifndef COPYRIGHT
X#    define COPYRIGHT
X     static char copyright[] =  "Copyright (c) 1992 Lomarline Ltd " ;
X#  endif
X# endif
X#endif
X
X/*-----------------------------------------------------------------------------
X * Date         : 25 February 1992
X * Version      : 1.2
X * Last Update  : 92/06/06 15:00:50
X * Author       : Lomarline Ltd
X * Compiler(s)  : SunOS 4.1, System V Rel 3, OSF1
X * Module Name  : avltree.c
X * Description  :
X *    Replacement functions to perform tsearch etc, with a AVL balanced tree
X *    structure.  AVL balance is when the height of left and right subtree
X *    from each node differ by one at most.
X *
X * Global Functions:
X *    void *tsearchAVL( void *key, void **rootp, int (*compar)() )
X *    void *tfindAVL( void *key, void **rootp, int (*compar)() )
X *    void *tdeleteAVL( void *key, void **rootp, int (*compar)() )
X *    void twalkAVL( void *root, void (*action)() )
X *
X * Notice:
X * Permission to use, copy, modify, distribute, and sell this software and
X * its documentation for any purpose is hereby granted without fee, provided
X * that the above copyright notices and this permission notice appear in
X * all copies of the software and related documentation.
X *
X * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
X * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
X * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
X *
X * IN NO EVENT SHALL LOMARLINE LTD BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
X * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER
X * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF THE
X * POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT OF OR
X * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
X *------------------------------------------------------------------------------
X*/
X
X#define global
X
X#include <stdio.h>
X#include <malloc.h>
X
X#include <search.h>
X#include "avltree.h"
X
X#ifndef TRUE
X#    define TRUE     1
X#    define FALSE 0
X#endif
X
Xstruct Node
X{
X    short        balance;  /* height of left subtree - height of right subtree */
X    void        *info;
X    struct Node    *left;
X    struct Node    *right;
X};
X
X
X/*------------------------------------------------------------------------------
X* Debug and trace info
X *------------------------------------------------------------------------------
X*/
X
X/*
X* If set to zero then All trace is not compiled in
X* The maximum setting at the moment is 300 which will only show entry and exit
X* to txxx functions
X*/
X#define Avl_DEBUG  000
X
X#if !defined ( Avl_DEBUG ) || ( Avl_DEBUG == 0 )
X#    define Avl_Enter(level,name)
X#    define Avl_Trace(level,string)
X#    define Avl_Return return
X#else
X/*
X* If you wish to view only one of the txxx functions and it's children then
X* set one of the following
X*/
X#    define Avl_ts (000 * -1)
X#    define Avl_td (000 * -1)
X#    define Avl_tw (000 * -1)
X#    define Avl_tf (000 * -1)
X
X    static long avl_depth ;
X    static long avl_level ;
X
X#    define Avl_Trace(level,string_p)\
X        do\
X        { if(( Avl_DEBUG >= (level) ) && ( avl_fname_p!= NULL))\
X          fprintf(stdout,"Avl_Trace:[%d]%s: %s\n",avl_depth,avl_fname_p,string_p );\
X        }while(0)
X/*
X* NB this must be placed after the initalization of local variables and
X* before the first assignment statment
X*/
X#    define Avl_Enter(level,name_p) \
X        char *avl_fname_p ;{ avl_level = (level) ;avl_fname_p=name_p, \
X        ++avl_depth ; Avl_Trace((level),"Enter"); }
X
X#    define Avl_Return { Avl_Trace(avl_level,"Return"); --avl_depth; } ; return
X
X#endif
X
X
X
X/*------------------------------------------------------------------------------
X * Description:
X *
X *
X * Notes:
X *
X * Parameters:
X *    nodeInfoPtr - Node to locate or insert.
X *    ptr         - Current node in the tree.
X *    rb_flag     - rebalance flag
X *    compar      - Node contents comparison function.
X *
X *
X *
X * Returns:
X *    NULL        - If node already exists.
X *    otherwise   - Inserted Node.
X *
X *------------------------------------------------------------------------------
X*/
X
X#ifdef NeedFunctionPrototypes
Xstatic void *
Xsearch(
X    const void            *key,
X    struct Node    **rootp ,
X    int            *rb_flag ,
X    int            (*compar)(const void *, const void *)
X)
X#else
Xstatic void *
Xsearch( key, rootp, rb_flag, compar )
X    void            *key;
X    struct Node    **rootp;
X    int            *rb_flag;
X    int            (*compar)();
X#endif
X{
X    struct Node *p1;
X    struct Node *p2;
X    void            *keyInsert;
X    int            direction;
X
X    Avl_Enter(Avl_ts+300,"search") ;
X
X    if ( *rootp == NULL )
X    {
X        Avl_Trace(Avl_ts+310,"No tree create one");
X
X        if ( (*rootp = (struct Node *)malloc( sizeof( struct Node ) )) != NULL )
X        {
X            *rb_flag        = TRUE;
X            (*rootp)->info    = (void *) key;
X            (*rootp)->left    = NULL;
X            (*rootp)->right   = NULL;
X            (*rootp)->balance = 0;
X            keyInsert         = (void *) &((*rootp)->info);
X        }
X        else
X            keyInsert = NULL;
X        Avl_Return keyInsert;
X    }
X
X    direction = compar( key, (*rootp)->info )  ;
X
X    if ( direction < 0 )
X    {
X        Avl_Trace(Avl_ts+320,"Move left");
X
X        keyInsert = search( key, &((*rootp)->left), rb_flag, compar );
X
X        if ( *rb_flag && (keyInsert != NULL) )
X        {
X
X            Avl_Trace(Avl_ts+330,"left  branch has grown longer");
X
X            switch( (*rootp)->balance )
X            {
X            case 1:
X                Avl_Trace(Avl_ts+340,"right branch was longer, now in balance");
X
X                (*rootp)->balance = 0;
X                *rb_flag = FALSE;
X                break;
X
X            case 0:
X                Avl_Trace(Avl_ts+340,
X                    "was in balance, now the left branch is one longer");
X
X                (*rootp)->balance = -1;
X                break;
X
X            case -1:
X                Avl_Trace(Avl_ts+340,"left is to long so rebalance");
X
X                p1 = (*rootp)->left;
X
X                if ( p1->balance < 0 )
X                {
X                    Avl_Trace(Avl_ts+350,"single LL rotation");
X
X                    (*rootp)->left    = p1->right;
X                    p1->right         = *rootp;
X                    (*rootp)->balance = 0;
X                    *rootp            = p1;
X                }
X                else
X                {
X                    Avl_Trace(Avl_ts+350,"double LR rotation");
X
X                    p2                = p1->right;
X                    p1->right         = p2->left;
X                    p2->left          = p1;
X                    (*rootp)->left    = p2->right;
X                    p2->right         = *rootp;
X                    (*rootp)->balance = ( p2->balance < 0 ) ?  1 : 0;
X                    p1->balance       = ( p2->balance > 0 ) ? -1 : 0;
X                    *rootp            = p2 ;
X                }
X
X                (*rootp)->balance = 0;
X                *rb_flag = FALSE;
X
X                break;
X
X            }    /*    switch    */
X
X        }    /*    if    */
X
X    }
X    else if ( direction > 0 )
X    {
X        Avl_Trace(Avl_ts+320,"Move right");
X
X        keyInsert = search( key, &((*rootp)->right), rb_flag, compar );
X
X        if ( *rb_flag && (keyInsert != NULL) )
X        {
X            Avl_Trace(Avl_ts+330,"right branch has grown longer");
X
X            switch( (*rootp)->balance )
X            {
X            case -1:
X            Avl_Trace(Avl_ts+340,"left branch was longer, now in balance");
X                (*rootp)->balance = 0;
X                *rb_flag = FALSE;
X                break;
X
X            case 0:
X            Avl_Trace(Avl_ts+340,"was in balance, now the right branch is longer");
X                (*rootp)->balance = 1;
X                break;
X
X            case 1:
X            Avl_Trace(Avl_ts+340,"right is to long so rebalance");
X                p1 = (*rootp)->right;
X
X                if ( p1->balance > 0 )
X                {
X                    Avl_Trace(Avl_ts+350,"single RR rotation");
X
X                    (*rootp)->right   = p1->left;
X                    p1->left          = *rootp;
X                    (*rootp)->balance = 0;
X                    *rootp            = p1;
X                }
X                else
X                {
X                    Avl_Trace(Avl_ts+350,"double RL rotation");
X
X                    p2                = p1->left;
X                    p1->left          = p2->right;
X                    p2->right         = p1;
X                    (*rootp)->right   = p2->left;
X                    p2->left          = *rootp;
X                    (*rootp)->balance = ( p2->balance > 0 ) ? -1 : 0;
X                    p1->balance          = ( p2->balance < 0 ) ?  1 : 0;
X                    *rootp            = p2;
X                }
X
X                (*rootp)->balance = 0;
X                *rb_flag = FALSE;
X
X                break;
X            }
X        }    /*    if    */
X    }
X    else
X    {
X        Avl_Trace(Avl_ts+320,"direction == 0, got a match");
X        *rb_flag    = FALSE;
X        keyInsert    = (void *) &((*rootp)->info);
X    }
X
X    Avl_Return keyInsert;
X}
X
X
X/*------------------------------------------------------------------------------
X * Description:
X *    As per tsearch(3).
X *
X * Notes:
X *
X * Parameters:
X *    key         - Node to locate or insert.
X *    rootp       - Tree's root node.
X *    compar      - Node contents comparison function.
X *
X *
X * Returns:
X *    NULL        - If node already exists.
X *    otherwise   - Inserted Node.
X *
X *------------------------------------------------------------------------------
X*/
X
X#ifdef NeedFunctionPrototypes
Xglobal void    *
XtsearchAVL(
X    const void    *key  ,
X    void    **rootp ,
X    int    (*compar)(const void *, const void *)
X)
X#else
Xglobal void    *
XtsearchAVL( key, rootp, compar )
X    void    *key;
X    void    **rootp;
X    int    (*compar)();
X#endif
X{
X    void * rtn ;
X    int    rb_flag = FALSE;
X
X    Avl_Enter(Avl_ts+200,"tsearchAVL") ;
X
X    rtn = search( key, (struct Node **)rootp, &rb_flag, compar );
X    Avl_Return rtn ;
X}
X
X/*------------------------------------------------------------------------------
X * Description:
X *    As per tfind(3).
X *
X * tfind() searches for an entry in the binary tree, Avl_Returning a pointer to
X * that entry when a match is found.  However, when key is not matched,
X * tfind() Avl_Returns a null pointer.
X *
X * Notes:
X *
X * Parameters:
X *    key         - Node to locate.
X *    rootp       - Tree's root node.
X *    compar      - Node contents comparison function.
X *
X *
X * Returns:
X *    NULL         -
X *    otherwise    -
X *
X *------------------------------------------------------------------------------
X*/
X
X#ifdef NeedFunctionPrototypes
Xglobal void    *
XtfindAVL(
X    const void        *key,
X    void        **rootp,
X    int    (*compar)(const void *, const void *)
X)
X#else
Xglobal void    *
XtfindAVL( key, rootp, compar )
X    void        *key;
X    void        **rootp;
X    int        (*compar)();
X#endif
X{
X    int    direction;
X    void * rtn ;
X
X    Avl_Enter(Avl_tf+200,"tfindAVL") ;
X
X    if ( *rootp == NULL )
X    {
X        Avl_Trace(Avl_tf+210,"rootp is Null");
X        Avl_Return NULL;
X    }
X
X    direction = compar( key, ((struct Node *)(*rootp))->info );
X
X    if ( direction < 0 )
X    {
X        Avl_Trace(Avl_tf+210,"direction < 0, Going left");
X        rtn = tfindAVL(
X            key,
X            (void **)&(((struct Node *)(*rootp))->left),
X            compar );
X    }
X    else if ( direction > 0 )
X    {
X        Avl_Trace(Avl_tf+210,"direction > 0, Going right");
X        rtn = tfindAVL(
X            key,
X            (void **)&(((struct Node *)(*rootp))->right),
X            compar );
X    }
X    else
X    {
X        Avl_Trace(Avl_tf+210,"direction == 0 , Got a match");
X        rtn = &((struct Node *)(*rootp))->info;
X    }
X
X    Avl_Return  rtn ;
X}
X
X
X/*------------------------------------------------------------------------------
X * Description:
X *  Rebalance tree on the left
X *
X *
X * Notes:
X *
X * Parameters:
X *    ptr        -  pointer to (sub) tree ;
X *    rb_flag    -  rebalance flag
X *
X *
X * Returns:
X *    None
X *
X *------------------------------------------------------------------------------
X*/
X
X#ifdef NeedFunctionPrototypes
Xstatic void
Xbal_left(
X    struct Node    **rootp ,
X    int            *rb_flag
X)
X#else
Xstatic void
Xbal_left( rootp, rb_flag )
X    struct Node    **rootp;
X    int            *rb_flag;
X#endif
X{
X    struct Node    *p1;
X    struct Node    *p2;
X    int            b1;
X    int            b2;
X
X    Avl_Enter(Avl_td+400,"bal_left") ;
X
X    switch( (*rootp)->balance )
X    {
X    case -1:
X        Avl_Trace(Avl_td+410,"was imbalanced, fixed implicitly");
X        (*rootp)->balance = 0;
X        break;
X
X    case 0:
X        Avl_Trace(Avl_td+410,"was okay, is now one out");
X        (*rootp)->balance = 1;
X        *rb_flag = FALSE;
X        break;
X
X    case 1:
X        Avl_Trace(Avl_td+410,"was alreay one out, so rebalance");
X        p1 = (*rootp)->right;
X        b1 = p1->balance;
X
X        if ( b1 >= 0 )
X        {
X            Avl_Trace(Avl_td+410,"single RR rotation");
X
X            (*rootp)->right    = p1->left;
X            p1->left            = *rootp;
X
X            if ( b1 == 0 )
X            {
X                (*rootp)->balance = 1;
X                p1->balance = -1;
X                *rb_flag = FALSE;
X            }
X            else
X            {
X                (*rootp)->balance = 0;
X                p1->balance = 0;
X            }
X
X            *rootp = p1;
X        }
X        else
X        {
X            Avl_Trace(Avl_td+410,"double RL rotation");
X
X            p2              = p1->left;
X            b2              = p2->balance;
X            p1->left        = p2->right;
X            p2->right       = p1;
X            (*rootp)->right = p2->left;
X            p2->left        = *rootp;
X
X            (*rootp)->balance = ( b2 ==  1 ) ? -1 : 0;
X            p1->balance     = ( b2 == -1 ) ?  1 : 0;
X            *rootp          = p2;
X            p2->balance     = 0;
X        }
X        break;
X
X    }    /*    switch    */
X
X    Avl_Return ;
X}    /*    bal_left    */
X
X
X/*------------------------------------------------------------------------------
X * Description:
X *
X *
X * Notes:
X *
X * Parameters:
X *    rootp        - pointer to (sub) tree
X *    rb_flag    - repbalnce flag
X *
X *
X * Returns:
X *    None
X *
X *------------------------------------------------------------------------------
X*/
X
X#ifdef NeedFunctionPrototypes
Xstatic void
Xbal_right(
X    struct Node    **rootp,
X    int            *rb_flag
X)
X#else
Xstatic void
Xbal_right( rootp, rb_flag )
Xstruct Node    **rootp;
Xint            *rb_flag;
X#endif
X{
X    struct Node    *p1;
X    struct Node    *p2;
X    int            b1;
X    int            b2;
X
X    Avl_Enter(Avl_td+400,"bal_right") ;
X
X    switch( (*rootp)->balance )
X    {
X    case 1:
X        Avl_Trace(Avl_td+410,"was imbalanced, fixed implicitly");
X        (*rootp)->balance = 0;
X        break;
X
X    case 0:
X        Avl_Trace(Avl_td+410,"was okay, is now one out");
X        (*rootp)->balance = -1;
X        *rb_flag = FALSE;
X        break;
X
X    case -1:
X        Avl_Trace(Avl_td+410,"was already one out, so rebalance");
X        p1 = (*rootp)->left;
X        b1 = p1->balance;
X
X        if ( b1 <= 0 )
X        {
X            Avl_Trace(Avl_td+410,"single LL rotation");
X
X            (*rootp)->left = p1->right;
X            p1->right = *rootp;
X
X            if ( b1 == 0 )
X            {
X                (*rootp)->balance = -1;
X                p1->balance = 1;
X                *rb_flag = FALSE;
X            }
X            else
X            {
X                (*rootp)->balance = 0;
X                p1->balance = 0;
X            }
X
X            *rootp = p1;
X        }
X        else
X        {
X            Avl_Trace(Avl_td+410,"double LR rotation");
X
X            p2              = p1->right;
X            b2              = p2->balance;
X            p1->right       = p2->left;
X            p2->left        = p1;
X            (*rootp)->left  = p2->right;
X            p2->right       = *rootp;
X
X            (*rootp)->balance = ( b2 == -1 ) ?  1 : 0;
X            p1->balance     = ( b2 ==  1 ) ? -1 : 0;
X            *rootp          = p2;
X            p2->balance     = 0;
X        }
X        break;
X
X    }    /*    switch    */
X
X    Avl_Return ;
X}    /*    bal_right    */
X
X
X/*------------------------------------------------------------------------------
X * Description:
X *  This is called initally from delete but it is recursive.
X *  It is responsible for removing a node when both
X *  subnodes contain data.
X *
X * Notes:
X *
X * Parameters:
X *    rootp      - Node with two children
X *    q          -
X *    rb_flag    - rebalanc flag
X *
X *
X * Returns:
X *    None
X *
X *------------------------------------------------------------------------------
X*/
X
X#ifdef NeedFunctionPrototypes
Xstatic void
Xdel(
X    struct Node    **rootp ,
X    struct Node **q ,
X    int            *rb_flag
X)
X#else
Xstatic void
Xdel( rootp, q, rb_flag )
X    struct Node    **rootp;
X    struct Node **q ;
X    int            *rb_flag;
X#endif
X{
X    Avl_Enter(Avl_td+400,"del") ;
X
X    if ( (*rootp)->right != NULL )
X    {
X        Avl_Trace(Avl_td+410,"Moving right");
X        del( &((*rootp)->right), q , rb_flag );
X
X        if ( *rb_flag )
X        {
X            Avl_Trace(Avl_td+410,"Rebalancing right");
X            bal_right( rootp, rb_flag );
X        }
X    }
X    else
X    {
X        /*
X         * Delete is only called if both nodes exist
X         */
X        Avl_Trace(Avl_td+410,"Moving to the left and repositioning  data");
X        (*q)->info = (*rootp)->info;
X        *q = *rootp ;
X        *rootp = (*rootp)->left;
X        *rb_flag = TRUE;
X    }
X
X    Avl_Return ;
X}    /*    del    */
X
X
X/*------------------------------------------------------------------------------
X * Description:
X *              Deletes a node form the table and reblances the tree if
X *              required.
X *
X * Notes:
X *              It is not realy meaning full to Avl_Return a pointer to the
X *              parents address but this is done to comply with the UNIX
X *              man tsearch entrys.
X *
X * Parameters:
X *    key       -
X *    ptr       - pointer to (sub) tree
X *    rb_flag   - rebalance flag
X *    compar    - Node contents comparison function.
X *
X *
X * Returns:
X *    parent    - NULL if no matching node found
X *              or pointer to parent node
X *                 if the parentNode parameter is not NUll
X *              otherwise Avl_Returns a pointer to the deleted nodes information
X *
X *------------------------------------------------------------------------------
X*/
X
X#ifdef NeedFunctionPrototypes
Xstatic void *
Xdelete(
X    const void   *key ,
X    struct Node **rootp ,
X    int         *rb_flag ,
X    int         (*compar)(const void *, const void *),
X    struct Node **parentNode
X)
X#else
Xstatic void *
Xdelete( key, rootp, rb_flag, compar, parentNode )
X    void        *key;
X    struct Node **rootp;
X    int         *rb_flag;
X    int         (*compar)();
X    struct Node **parentNode ;
X#endif
X{
X    int    direction;
X
X    void   **infoPtr ;
X
X    struct Node    *q;
X
X    Avl_Enter(Avl_td+300,"delete") ;
X
X    if ( *rootp == NULL )
X    {
X        Avl_Trace(Avl_td+310,"No node maches key");
X        *rb_flag = FALSE;
X        Avl_Return NULL ;
X    }
X
X
X    direction = compar( key, (*rootp)->info ) ;
X
X
X    if ( direction == 0 )
X    {
X        Avl_Trace(Avl_td+310,"We have a match ==  We want to delete this node");
X        /*
X         * if parentNode NULL then Avl_Return a pointer to the info
X         * else Avl_Return the address of a pointer to the parent node
X         */
X        if ( parentNode == NULL )
X        {
X            Avl_Trace(Avl_td+330,"Return (deleted node) info");
X            infoPtr = (*rootp)->info ;
X        }
X        else
X        {
X            /*
X             * Then we were at the root node so we will
X             * have to return a new root node so set it
X             * to NULL here and test for it in the "if"
X             * conditions below
X             */
X            if ( parentNode == rootp )
X            {
X                Avl_Trace(Avl_td+330,"Return infoPtr = rootp");
X                infoPtr = NULL ;
X            }
X            else
X            {
X                Avl_Trace(Avl_td+330,"Return infoPtr = parentNode" );
X                infoPtr = &(*parentNode)->info ;
X            }
X        }
X
X        q = *rootp;
X
X        if ( q->right == NULL )
X        {
X            Avl_Trace(Avl_td+340,
X            "We have no right node so assign left node to rootp");
X            *rootp    = q->left;
X            *rb_flag        = TRUE;
X            if( q->left == NULL )
X            {
X                Avl_Trace(Avl_td+350,"We have no left node either");
X                    /*infoPtr = NULL ;*/
X            }
X            else if ( infoPtr == NULL )
X                    infoPtr = &(*rootp)->info ;
X        }
X        else if ( q->left == NULL )
X        {
X            Avl_Trace(Avl_td+340,
X            "We have a right node but no left one so assign rightnode to pointer");
X
X            *rootp    = q->right;
X            *rb_flag        = TRUE;
X            if ( infoPtr == NULL )
X                    infoPtr = &(*rootp)->info ;
X        }
X        else
X        {
X            Avl_Trace(Avl_td+340,
X            "We have both nodes but this one must go so delete this one and rebalance");
X            del( &(q->left),&q, rb_flag );
X
X            if ( *rb_flag )
X                bal_left( rootp, rb_flag );
X
X            if ( infoPtr == NULL )
X            {
X                     Avl_Trace(Avl_td+340,
X                    "PBS We have both nodes infoPtr was NOT NULL");
X                    infoPtr = &(*rootp)->info ;
X            }
X        }
X
X        free( (void *)q );
X        q = NULL;
X
X        Avl_Return  infoPtr ;
X    }
X
X    if( parentNode != NULL )
X    {
X        Avl_Trace(Avl_td+320,"Parent node SET to root Node");
X        parentNode = rootp ;
X    }
X    else
X    {
X        Avl_Trace(Avl_td+320,"Parent node NOT set to root Node");
X    }
X
X    if ( direction < 0 )
X    {
X        Avl_Trace(Avl_td+350,"key is < node,  Move down the left leaf");
X
X        infoPtr = delete( key, &((*rootp)->left), rb_flag, compar, parentNode );
X
X        if ( *rb_flag )
X        {
X            Avl_Trace(Avl_td+350,"We found our target (direction < 0)");
X            bal_left( rootp, rb_flag );
X        }
X    }
X    else if ( direction > 0 )
X    {
X        Avl_Trace(Avl_td+350,"key is > node, Move down the right leaf");
X
X        infoPtr = delete( key, &((*rootp)->right), rb_flag, compar, parentNode );
X
X        if ( *rb_flag )
X        {
X            Avl_Trace(Avl_td+350,"We found our target (direction < 0)");
X            bal_right( rootp, rb_flag );
X        }
X    }
X
X    Avl_Return infoPtr ;
X}    /*    delete    */
X
X
X/*------------------------------------------------------------------------------
X * Description:
X *    As per tdelete(3).
X * The tdelete() function deletes a node from a binary search tree. Parameters
X * for this function are used in the same way as for the tsearch() function.
X * The variable pointed to by the rootp parameter is changed when the deleted
X * node was the root of the binary tree.  The tdelete() function Avl_Returns a
X * pointer to the parent of the deleted node, or a null pointer if the node is
X * not found.
X *
X * Notes:
X *       If this module is compiled with the AVL macro NOT set then
X *       the value Avl_Returned,(if not NULL), is a pointer to the
X *       information stored in the deleted node.
X *       This will be of more use in most applications because this
X *       memory will have to be freed by the calling application.
X *       Returning the address of the pointer to the parent of the deleted
X *       node is not of much use in an AVLtree.
X *
X * Parameters:
X *    key - Node to delete.
X *    rootp       - Tree's root node.
X *    compar      - Node contents comparison function.
X *
X *
X * Returns:
X *    NULL        - If node does not exist .
X *    otherwise   - AVL == TRUE  a pointer to the deleted nodes parent.
X *                               or if the deleted node was root the new root.
X *    otherwise   - AVL == FALSE a pointer to the information stored in the
X *                               deleted node
X *
X *------------------------------------------------------------------------------
X*/
X#ifdef NeedFunctionPrototypes
Xglobal void    *
XtdeleteAVL(
X    const void    *key ,
X    void    **rootp ,
X    int    (*compar)(const void *, const void *)
X)
X#else
Xglobal void    *
XtdeleteAVL( key, rootp, compar )
X    void    *key;
X    void    **rootp;
X    int    (*compar)();
X#endif
X{
X    int    rb_flag = FALSE;
X    void **parentNode ;
X    void *rtn ;
X    Avl_Enter(Avl_td+200,"tdeleteAVL") ;
X
X#ifdef AVL
X    parentNode = rootp ;
X#else
X    parentNode = NULL ;
X#endif
X
X    rtn = delete(
X        key,
X        (struct Node **)rootp,
X        &rb_flag,
X        compar,
X        (struct Node **) parentNode
X        );
X
X    Avl_Return rtn ;
X
X}    /*    tdeleteAVL    */
X
X/*------------------------------------------------------------------------------
X * Description:
X *    Test for a leaf node (node without any children).
X *
X * Notes:
X *
X * Parameters:
X *    nodePtr - Node.
X *
X *
X * Returns:
X *    0       - If nodePtr points to a non leaf node.
X *    1       - If nodePtr points to a leaf node.
X *
X *------------------------------------------------------------------------------
X*/
X
X#ifdef NeedFunctionPrototypes
Xstatic int
XleafNode(
X    struct Node    *nodePtr
X)
X#else
Xstatic int
XleafNode( nodePtr )
X    struct Node    *nodePtr;
X#endif
X{
X    Avl_Enter(Avl_tw+300,"leafNode") ;
X    Avl_Return (nodePtr->left == NULL) && (nodePtr->right == NULL);
X}
X
X/*------------------------------------------------------------------------------
X * Description:
X *    As per twalk(3).
X *
X * The twalk() function traverses a binary search tree.  The root parameter
X * specifies the root of the binary tree to be traversed. Any node in a binary
X * tree can be used as the root node for a walk below that node.  The action
X * parameter is the name of a routine to be invoked at each node.  This action
X * routine is called with three parameters.  The first parameter specifies the
X * address of the visited node.  The second parameter specifies a value from
X * an enum data type, which is defined in the search.h include file as fol-
X * lows:
X *             typedef enum { preorder, postorder, endorder, leaf } VISIT
X *
X * The value of the second parameter in the action routine depends on whether
X * this is the first (preorder), second (postorder), or third (endorder) time
X * that the node has been visited during a depth-first, left-to-right traver-
X * sal of the tree, or whether the node is a leaf.  (A leaf is a node that is
X * not the parent of another node).  The third parameter in the action routine
X * is the level of the node in the binary tree with the root being level 0
X * (zero).
X *
X * Notes:
X *
X * Parameters:
X *    root    - Node to use as root for the walk.
X *    action  - Function to be performed on each node.
X *
X *
X * Returns:
X *    None
X *
X *-----------------------------------------------------------------------------
X */
X
X#ifdef NeedFunctionPrototypes
Xglobal void
XtwalkAVL(
X    const void        *root ,
X    void        (*action)(const void *, VISIT, int )
X)
X#else
Xglobal void
XtwalkAVL( root, action )
X    void        *root;
X    void        (*action)();
X#endif
X{
X    static int    level = -1;
X
X    Avl_Enter(Avl_tw+200,"twalkAVL") ;
X
X    if ( root != NULL )
X    {
X        level++;
X
X        if ( leafNode( (struct Node *)root ) )
X        {
X            action( &((struct Node *)root)->info, leaf, level);
X        }
X        else
X        {
X            action( &((struct Node *)root)->info, preorder, level);
X            twalkAVL( (void *)(((struct Node *)root)->left), action );
X            action( &((struct Node *)root)->info, postorder, level);
X            twalkAVL( (void *)(((struct Node *)root)->right), action );
X            action( &((struct Node *)root)->info, endorder, level);
X        }
X
X        level--;
X    }
X    else
X    {
X        Avl_Trace(Avl_tw+210,"root != NULL");
X    }
X    Avl_Return ;
X}
END_OF_avltree.c
if test      24344 -ne `wc -c < avltree.c `; then
    echo shar: \"avltree.c\" unpacked with wrong size!      24344
fi
# end of overwriting check
fi
if test -f atest.c -a README != "-c" ; then
    echo shar: Will not over-write existing file "atest.c"
else
echo shar: Extracting atest.c \(      4894 characters\)
sed 's/^X//'<< 'END_OF_atest.c' > atest.c
X/*
X* This program demonstrates that if an original tsearch program is
X* modified with the inclusion of "avltree.h" and
X* both this program and avltree.c are compiled with the AVL flag
X* set then the return by tdeletavl() substiitute function is the
X* parent just as in the standard functions.
X*/
X
X#include <malloc.h>
X#include <stdio.h>
X#include <string.h>
X#include <search.h>
X
X
X#include <search.h>
X#include "avltree.h"
X
X#define DNUM 0
Xtypedef struct Info_s
X{
X    int i ;
X    char name[200] ;
X}Info_t ;
X
XInfo_t info[] =
X{
X    { 0,"root"   ,}, { 0,"somebody" ,}, { 0,"nobody"   ,},
X    { 0,"demon"  ,}, { 0,"fred"     ,}, { 0,"ugand"    ,},
X    { 0,"tokoyo" ,}, { 0,"arthur"   ,}, { 0,"joan"     ,},
X    { 0,"criss"  ,}, { 0,"larry"    ,}, { 0,"tom"      ,},
X    { 0,"adam"   ,}, { 0,"eve"      ,}, { 0,"matthias" ,},
X    { 0,"stone"  ,}, { 0,"magic"    ,}, { 0,"trash80"  ,},
X    { 0,"stephen",}, { 0,"madman"   ,}, { 0,"usles"     ,},
X    { 0,"smith"  ,}, { 0,"pullen"   ,}, { 0,"stieger"  ,},
X    { 0,"crosby" ,}, { 0,"anders"   ,}, { 0,"schmid"   ,},
X    { 0,"rabbit" ,}, { 0,"steve"    ,}, { 0,"dog"      ,},
X    { 0,"gassa"  ,}, { 0,"kurtis"   ,}, { 0,"paul"     ,},
X    { 0,"badone" ,}, { 0,"kevin"    ,}, { 0,"maggi"    ,},
X    { 0,"roland" ,}, { 0,"casaulta" ,}, { 0,"mad"      ,},
X    { 0,"" ,}
X} ;
X
X/*----------------------------------------------------------------------
X*----------------------------------------------------------------------*/
Xint scmpr(Info_t *key_p, Info_t *info_pp )
X{
X    if ( key_p == NULL || info_pp == NULL )
X    {
X        fprintf(stdout,"Memory error %d %d \n",key_p, info_pp);
X        return 0 ;
X    }
X#ifdef DEBUG
X    fprintf(stdout,"kn = %s info = %s\n",key_p->name,info_pp->name);
X#endif
X
X    return strcmp(key_p->name,info_pp->name) ;
X}
X
X/*----------------------------------------------------------------------
X*----------------------------------------------------------------------*/
Xint icmpr(Info_t *key_p,Info_t *info_pp )
X{
X    if ( key_p == NULL || info_pp == NULL )
X    {
X        fprintf(stdout,"Memory error \n");
X        return 0 ;
X    }
X    return info_pp->i - key_p->i ;
X}
X
X/*----------------------------------------------------------------------
X* This will procude a sorted list when called from twalk
X*----------------------------------------------------------------------*/
Xstatic int counter ;
Xvoid action(Info_t **info_pp, VISIT visit, int level  )
X{
X    switch( visit )
X    {
X    case  preorder:
X    break ;
X    case postorder:
X
X        printf("%3d postorder: %d, %2d %s\n",counter++,level,(*info_pp)->i,(*info_pp)->name);
X
X    break ;
X    case endorder:
X    break ;
X    case leaf  :
X        printf("%3d leaf     : %d, %2d %s\n",counter++,level,(*info_pp)->i,(*info_pp)->name);
X    break ;
X    default :
X        printf("%3d default  : %d, %2d %s\n",counter++,level,(*info_pp)->i,(*info_pp)->name);
X    break ;
X    }
X
X    return ;
X}
X
X/*----------------------------------------------------------------------
X*----------------------------------------------------------------------*/
Xmain()
X{
X
X    int i ;
X    int numOfElements ;
X    Info_t **info_pp ;
X    Info_t *tree ;
X    tree = NULL ;
X
X#ifdef AVL
X    printf("AVL IS SET\n");
X#else
X    printf("AVL is NOT set\n");
X#endif
X    for( i = 0 ; info[i].name[0] != 0 ; i++)
X        info[i].i = i ;
X
X    numOfElements = i ;
X
X    for( i = 0 ; i  < numOfElements ; i++ )
X    {
X        info_pp = (Info_t **) tsearch(&info[i], &tree, scmpr ) ;
X        printf("tsearch %2d %10s\n", (*info_pp)->i , (*info_pp)->name);
X    }
X
X    printf("\nSorted data ---------------------------------------------------\n");
X    twalk( tree, action ) ;
X
X    printf("\ncheck that all elements are in the tree ------------------------\n");
X    for ( i = 0 ; i < numOfElements ; i ++ )
X    {
X        info_pp = (Info_t **) tfind(&info[i],&tree,scmpr );
X
X        if( info_pp == NULL )
X            printf(" Not found %2d %10s,", info[i].i, info[i].name);
X        else
X            printf("     FOUND %2d %10s,", (*info_pp)->i , (*info_pp)->name);
X        if ( i%3 == 2 )
X        printf("\n");
X    }
X    printf("\n");
X
X
X    printf("deleteing[%d]   %2d %10s\n\n",DNUM, info[DNUM].i, info[DNUM].name);
X
X    info_pp = (Info_t **) tdelete(&info[DNUM],&tree, scmpr ) ;
X
X#ifdef AVL
X    printf("\nAVL is set so avltree should return the parent as standard\n");
X#else
X    printf("\nAVL not set so using libray calls tsearch() etc\n");
X#endif
X    printf("parent %2d %10s\n\n", (*info_pp)->i , (*info_pp)->name);
X
X    printf("\ncheck only one data item has been removed ----------------------\n");
X    for ( i = 0 ; i < numOfElements ; i ++ )
X    {
X        info_pp = (Info_t **) tfind(&info[i],&tree ,scmpr );
X
X        if( info_pp == NULL )
X            printf(" Not found %2d %10s,", info[i].i, info[i].name);
X        else
X            printf("     FOUND %2d %10s,", (*info_pp)->i , (*info_pp)->name);
X        if ( i%3 == 2 )
X        printf("\n");
X    }
X        printf("\n");
X
X    printf("Test that data alreay deleted returns a NULL\n");
X    info_pp = (Info_t **) tdelete(&info[DNUM],&tree, scmpr ) ;
X    printf("past tdeleteAVL\n");
X    if ( info_pp != NULL )
X        printf("[%d] not deleted\t%d >%s<\n\n",
X            DNUM,(*info_pp)->i, (*info_pp)->name);
X    else
X        printf("This is corredt, NULL returned\n\n");
X}
END_OF_atest.c
if test       4894 -ne `wc -c < atest.c `; then
    echo shar: \"atest.c\" unpacked with wrong size!       4894
fi
# end of overwriting check
fi
if test -f btest.c -a README != "-c" ; then
    echo shar: Will not over-write existing file "btest.c"
else
echo shar: Extracting btest.c \(      5531 characters\)
sed 's/^X//'<< 'END_OF_btest.c' > btest.c
X/*
X* this program shows that it the modules are compiled witout the
X* AVL flag set that the return on tdeleteAVL is the data in the deleted node
X* so that it can "destructed by an application function
X*/
X
X#include <malloc.h>
X#include <stdio.h>
X#include <string.h>
X#include <search.h>
X
X
X#include <search.h>
X#include "avltree.h"
X
X#define DNUM 4
X
Xtypedef struct Info_s
X{
X    int i ;
X    char name[200] ;
X}Info_t ;
X
XInfo_t info[] =
X{
X    { 0,"root"   ,}, { 0,"somebody" ,}, { 0,"nobody"   ,},
X    { 0,"demon"  ,}, { 0,"fred"     ,}, { 0,"ugand"    ,},
X    { 0,"tokoyo" ,}, { 0,"arthur"   ,}, { 0,"joan"     ,},
X    { 0,"criss"  ,}, { 0,"larry"    ,}, { 0,"tom"      ,},
X    { 0,"adam"   ,}, { 0,"eve"      ,}, { 0,"matthias" ,},
X    { 0,"stone"  ,}, { 0,"magic"    ,}, { 0,"trash80"  ,},
X    { 0,"stephen",}, { 0,"madman"   ,}, { 0,"usles"     ,},
X    { 0,"smith"  ,}, { 0,"pullen"   ,}, { 0,"stieger"  ,},
X    { 0,"crosby" ,}, { 0,"anders"   ,}, { 0,"schmid"   ,},
X    { 0,"rabbit" ,}, { 0,"steve"    ,}, { 0,"dog"      ,},
X    { 0,"gassa"  ,}, { 0,"kurtis"   ,}, { 0,"paul"     ,},
X    { 0,"badone" ,}, { 0,"kevin"    ,}, { 0,"maggi"    ,},
X    { 0,"roland" ,}, { 0,"casaulta" ,}, { 0,"mad"      ,},
X    { 0,"" ,}
X} ;
X
X/*----------------------------------------------------------------------
X*----------------------------------------------------------------------*/
Xint scmpr(Info_t *key_p, Info_t *info_pp )
X{
X    if ( key_p == NULL || info_pp == NULL )
X    {
X        fprintf(stdout,"Memory error %d %d \n",key_p, info_pp);
X        return 0 ;
X    }
X#ifdef DEBUG
X    fprintf(stdout,"kn = %s info = %s\n",key_p->name,info_pp->name);
X#endif
X
X    return strcmp(key_p->name,info_pp->name) ;
X}
X
X/*----------------------------------------------------------------------
X*----------------------------------------------------------------------*/
Xint icmpr(Info_t *key_p,Info_t *info_pp )
X{
X    if ( key_p == NULL || info_pp == NULL )
X    {
X        fprintf(stdout,"Memory error \n");
X        return 0 ;
X    }
X    return info_pp->i - key_p->i ;
X}
X
X/*----------------------------------------------------------------------
X* This will procude a sorted list when called from twalkAVL
X*----------------------------------------------------------------------*/
Xstatic int counter ;
Xvoid action(Info_t **info_pp, VISIT visit, int level  )
X{
X    switch( visit )
X    {
X    case  preorder:
X    break ;
X    case postorder:
X        printf("%3d postorder: %d, %2d %s\n",
X            counter++,level,(*info_pp)->i,(*info_pp)->name);
X
X    break ;
X    case endorder:
X    break ;
X    case leaf  :
X        printf("%3d leaf     : %d, %2d %s\n",
X            counter++,level,(*info_pp)->i,(*info_pp)->name);
X    break ;
X    default :
X        printf("%3d default  : %d, %2d %s\n",
X            counter++,level,(*info_pp)->i,(*info_pp)->name);
X    break ;
X    }
X
X    return ;
X}
X
X/*----------------------------------------------------------------------
X*----------------------------------------------------------------------*/
Xmain()
X{
X
X    int i ;
X    int j ;
X    int numOfElements ;
X    Info_t **info_pp ;
X    Info_t *info_p ;
X    Info_t *tree ;
X    tree = NULL ;
X
X#ifdef AVL
X    printf("AVL IS SET\n");
X#else
X    printf("AVL is NOT set\n");
X#endif
X
X    for( i = 0 ; info[i].name[0] != 0 ; i++)
X        info[i].i = i ;
X
X    numOfElements = i ;
X
X    /*
X     * add an index number to each element
X     */
X    for( i = 0 ; i  < numOfElements ; i++ )
X    {
X        info_pp = (Info_t **) tsearchAVL(&info[i], &tree, scmpr ) ;
X        printf("tsearchAVL %2d %10s\n", (*info_pp)->i, (*info_pp)->name);
X    }
X
X    twalkAVL( tree, action ) ;
X
X    /*
X     * check that all elements are in the tree
X     */
X    for ( i = 0 ; i < numOfElements ; i ++ )
X    {
X        info_pp = (Info_t **) tfindAVL(&info[i],&tree,scmpr );
X
X        if( info_pp == NULL )
X            printf(" Not found %2d %10s,", info[i].i, info[i].name);
X        else
X            printf("     FOUND %2d %10s,", (*info_pp)->i, (*info_pp)->name);
X
X        if ( i%3 == 2 )
X            printf("\n");
X    }
X    printf("\n");
X
X    /*
X     * remove all elements from the AVL tree
X     */
X    for (  j = 0 ; j < numOfElements ; j ++ )
X    {
X        printf("Before Delete -------------------------\n");
X        printf("[%2d] target\t%2d %10s\n", j, info[j].i, info[j].name);
X
X#ifdef AVL
X        info_pp = (Info_t **) tdeleteAVL(&info[j],&tree, scmpr ) ;
X        if ( info_pp != NULL )
X            printf("[%2d] parent\t%2d %10s\n\n",j,(*info_pp)->i,(*info_pp)->name);
X#else
X        info_p = (Info_t *) tdeleteAVL(&info[j],&tree, scmpr ) ;
X        if ( info_p != NULL )
X            printf("[%2d] deleted\t%2d %10s\n\n",j,info_p->i, info_p->name);
X        /*
X         * Can't be freed bacause a fixed array
X         *if( info_p != NULL )
X         *    free(info_p);
X         */
X#endif
X
X        /*
X         * Check that the elements have been removed
X         */
X
X        for ( i = 0 ; i < numOfElements ; i ++ )
X        {
X            info_pp = (Info_t **) tfindAVL(&info[i],&tree ,scmpr );
X
X            if( info_pp == NULL )
X                printf(" Not found %2d %10s,", info[i].i, info[i].name);
X            else
X                printf("     FOUND %2d %10s,", (*info_pp)->i, (*info_pp)->name);
X
X            if ( i%3 == 2 )
X                printf("\n");
X        }
X        printf("\n");
X        printf("After Delete -------------------------\n");
X    }
X
X/*------------------------------------------------------------------*/
X    printf("Test that data alreay deleted returns a NULL\n");
X#ifdef AVL
X    info_p = (Info_t *) tdeleteAVL(&info[DNUM],&tree, scmpr ) ;
X    info_pp = &info_p ;
X    if ( info_p != NULL )
X#else
X    info_pp = (Info_t **)  tdeleteAVL(&info[DNUM],&tree, scmpr ) ;
X    if ( info_pp != NULL )
X#endif
X        printf("[%d] deleted\t%d >%s<\n\n",
X            DNUM, (*info_pp)->i, (*info_pp)->name);
X    else
X        printf("This is corredt, NULL returned\n\n");
X
X
X    printf("Before -------------------------------------------------------\n");
X    printf("twalkAVL tree_p == %d\n",(long) tree);
X    twalkAVL( tree, action ) ;
X    printf("After --------------------------------------------------------\n");
X}
END_OF_btest.c
if test       5531 -ne `wc -c < btest.c `; then
    echo shar: \"btest.c\" unpacked with wrong size!       5531
fi
# end of overwriting check
fi
if test -f makefile -a README != "-c" ; then
    echo shar: Will not over-write existing file "makefile"
else
echo shar: Extracting makefile \(       961 characters\)
sed 's/^X//'<< 'END_OF_makefile' > makefile
X#####################################################################
X#
X# The makefile for the AVLtree software
X#
X# atest    == standard tsearch program with stdlib
X# atestavl == standard tsearch program with avltree.o
X#
X# btest    == test without AVL flag set, returns deleteed node info
X# btestavl == test with AVL flag set,  returns pointer to parent node
X#####################################################################
X
XCFLAGS=-g
XDFLAGS=-DAVL
X
Xall: atest atestavl btest btestavl
X
X
Xatest: atest.c
X     cc atest.c -o atest $(CFLAGS)
X
Xatestavl: avltree.o atest.c
X     cc atest.c -o atestavl $(CFLAGS) $(DFLAGS)  avltree.o
X
X
Xbtest: tree.o btest.c
X    cc btest.c -o btest $(CFLAGS) tree.o
X
Xbtestavl: avltree.o btest.c
X    cc btest.c -o btestavl $(CFLAGS) $(DFLAGS) avltree.o
X
X
Xavltree.o: avltree.c makefile
X    cc avltree.c -c $(CFLAGS) $(DFLAGS)
X
Xtree.o: avltree.c makefile
X    cc -o tree.o avltree.c -c $(CFLAGS)
X
X
X
Xclean:
X    rm -f *.o atest atestavl btest btestavl core
END_OF_makefile
if test        961 -ne `wc -c < makefile `; then
    echo shar: \"makefile\" unpacked with wrong size!        961
fi
# end of overwriting check
fi
echo shar: End of shell archive.