home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 446.lha / avlsort / avlsort.c < prev    next >
C/C++ Source or Header  |  1990-12-02  |  19KB  |  736 lines
  1. /*---------------------------------------------------------------------------
  2.  * AVLSORT From,To,COLSTART/k,WIDTH/k,CASE/s,REVERSE/s
  3.  *
  4.  * AMIGA Usage: AvlSort <infile> [TO outfile] [starting at column] \
  5.  *            [CASE-sensitive] [REVERSE order]
  6.  *
  7.  * MSDOS Usage: AVLSORT [infile] [outfile] [/COL n] [/WID n] [/U] [/R]
  8.  *    infile    default is stdin
  9.  *    outfile    default is stdout
  10.  *    /COL n    start column; default is 1 (may use /C:n)
  11.  *    /WID n    column width; default is all (may use /W:n)
  12.  *    /U    unique case (case-sensitive)
  13.  *    /R    reverse order
  14.  *
  15.  * Copyright (C) 1990 by Robert L. Pyron
  16.  *
  17.  * "This software may be used at will, provided that all credits
  18.  * and style be left in place, and that its distribution is not
  19.  * restricted."
  20.  *
  21.  * Robert L. Pyron, 24 June 90
  22.  * BIX: rpyron
  23.  *---------------------------------------------------------------------------
  24.  */
  25.  
  26. #include <ctype.h>
  27. #include <math.h>
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include <string.h>
  31. #include "avl.h"
  32.  
  33. #if    defined(LATTICE) && defined(AMIGA)    /* We link with ARP */
  34.  #include <Arp/ArpBase.h>
  35. #else
  36.  #include <malloc.h>
  37.  #define ArpAlloc(n) malloc( (unsigned short) (n) )
  38. #endif
  39.  
  40. /*---------------------------------------------------------------------------
  41.  * Typedefs and defines
  42.  *---------------------------------------------------------------------------
  43.  */
  44.  
  45. #define FALSE    0
  46. #define TRUE    1
  47. #define    TEXTMAX    32768
  48.  
  49. typedef    unsigned char    UCHAR;
  50. typedef    unsigned short    USHORT;
  51. typedef    unsigned long    ULONG;
  52. typedef    UCHAR *        PCHAR;
  53. typedef void *        PVOID;
  54.  
  55. typedef    struct _MYNODE {
  56.     AVLNODE    avlnode;
  57.     PCHAR    text;
  58.     ULONG    textlen;
  59.     ULONG    lineno;
  60.     } MYNODE;
  61. typedef    MYNODE        *PNODE;
  62. #define    SZOF_MYNODE    sizeof(MYNODE)
  63.  
  64. typedef    int  (*PFNCOMPARE) __ARGS((const char *, const char *, unsigned int));
  65.  
  66.  
  67. /*---------------------------------------------------------------------------
  68.  * Prototypes
  69.  *---------------------------------------------------------------------------
  70.  */
  71.  
  72. int    cmdparse __ARGS(( int argc, char **argv ));
  73. PVOID    myalloc __ARGS(( ULONG size ));
  74. PNODE    newnode __ARGS(( PCHAR text, ULONG textlen, ULONG lineno ));
  75. void    printtree __ARGS(( PNODE p ));
  76.  
  77. int    cmprtc  __ARGS(( void *keyP, AVLNODE *nodeP ));
  78. AVLNODE *mknode __ARGS(( AVLTREE *treeP, void *keyP, void *dataP, AVLNODE *enodeP ));
  79. void    rmnode  __ARGS(( AVLTREE *treeP, AVLNODE *nodeP ));
  80.  
  81. /*---------------------------------------------------------------------------
  82.  * Global data
  83.  *---------------------------------------------------------------------------
  84.  */
  85.  
  86. #if    defined(LATTICE) && defined(AMIGA)
  87.  
  88.     /* Template and Extended Help for GADS(), from ARP */
  89.  
  90. extern    struct ArpBase    *ArpBase;
  91.  
  92. char    *CLI_Template    = "From,To,COLSTART/k,WIDTH/k,CASE/s,REVERSE/s";
  93. char    *CLI_Help    = "Usage: AvlSort <infile> [TO outfile] "
  94.               "[starting at column] [CASE-sensitive]";
  95.  
  96. #else    /* Microsoft, MSDOS or OS2 */
  97.  
  98. char    *program    = "AVLSORT";
  99. char    *usage        = "Usage: %s [infile] [outfile] [/COL n] [/WID n] [/U] [/R]";
  100.  
  101. #endif
  102.  
  103.     /* User may specify the following parameters on command line: */
  104.  
  105. char    *infile        = NULL;        /* input file name, default stdin */
  106. char    *outfile    = NULL;        /* output file name, default stdout */
  107. long    colstart    = 0;        /* start column, default 1 */
  108. long    colwidth    = TEXTMAX-1;    /* width, default full line */
  109. int    caseflag    = 0;        /* case sensitivity, default off */
  110. int    reverseflag    = 0;        /* reverse sort, default off */
  111.  
  112.     /* This is our AVL tree. */
  113.  
  114. AVLTREE    avlTree = {
  115.     NULL,
  116.     (PFNCMPRTC)cmprtc,
  117.     (PFNMKNODE)mknode,
  118.     (PFNRMNODE)rmnode
  119.     };
  120. #define    avlRoot    ((PNODE)avlTree.t_rootP)
  121.  
  122.     /*-----------------------------------------------------------
  123.      * Pointer to string comparison function. If case sensitivity
  124.      * is off (default), use strnicmp().  Otherwise use strncmp().
  125.      *------------------------------------------------------------
  126.      */
  127.  
  128. PFNCOMPARE    pfnCompare = (PFNCOMPARE) strnicmp;
  129.  
  130.  
  131. /*---------------------------------------------------------------------------
  132.  * Notice int return type, we are returning a value to Arp startup code.
  133.  *---------------------------------------------------------------------------
  134.  */
  135.  
  136. int    main( int argc, char **argv )
  137. {
  138. register int    byte;
  139.     int    lastch;
  140.     long    line_number    = 0;
  141.     PNODE    pnew;
  142.     int    status        = 10;    /* assume the worst */
  143. register PCHAR    textbuf;
  144.     ULONG    textlen;
  145.  
  146.     if ( (textbuf = ArpAlloc(TEXTMAX)) == NULL)
  147.     {
  148.         fprintf( stderr, "?? Out of memory\n" );
  149.         goto hell;
  150.     }
  151.  
  152.     /*-------------------------------
  153.      * Get options from command line.
  154.      *-------------------------------
  155.      */
  156.  
  157.     if (cmdparse(argc,argv))
  158.         goto hell;
  159.  
  160.     if (--colstart < 0)    colstart = 0;    /* convert to zero-based */
  161.     if (colwidth <= 0)    colwidth = TEXTMAX - 1;
  162.     if (caseflag)        pfnCompare = (PFNCOMPARE) strncmp;
  163.  
  164.     /*--------------------------------------------
  165.      * Redirect stdin to named file, if specified.
  166.      *--------------------------------------------
  167.      */
  168.  
  169.     if (infile && *infile)
  170.     {
  171.         /* redirect stdin to specified file */
  172.  
  173.         FILE    *fp = freopen( infile, "r", stdin );
  174.  
  175.         if (fp == NULL)
  176.         {
  177.             fprintf( stderr,
  178.                  "?? Cannot open file %s for input\n",
  179.                  infile );
  180.             goto hell;
  181.         }
  182.         else if (fp != stdin)
  183.         {
  184.             fprintf( stderr, "?? freopen() error\n" );
  185.             goto hell;
  186.         }
  187.     }
  188.  
  189.     /*-----------------------------------------------------
  190.      * Read file, putting each line in the appropriate bin.
  191.      *-----------------------------------------------------
  192.      */
  193.  
  194.     lastch = (int) ' ';
  195.     while ( lastch != EOF )
  196.     {
  197.         /*----------------------------------------------------------
  198.          * Read a line.  We assume that file is opened in text mode.
  199.          *----------------------------------------------------------
  200.          */
  201.  
  202.         textlen = 0;
  203.         while ( byte = getchar() )
  204.         {
  205.             if (byte == EOF || byte == '\n' || byte == '\r')
  206.                 break;
  207.  
  208.             textbuf[textlen++] = (UCHAR) byte;
  209.             if (textlen == TEXTMAX)
  210.             {
  211.                 fprintf( stderr,
  212.                     "?? Fatal error: line exceeds %lu bytes.\n",
  213.                     TEXTMAX-1 );
  214.                 goto hell;
  215.             }
  216.         }
  217.         if (byte == EOF && textlen == 0)
  218.             break;
  219.  
  220.         lastch = byte;
  221.         textbuf[textlen] = (UCHAR) '\0';
  222.  
  223.         /*---------------------------------------------
  224.          * Allocate space for line, and insert in tree.
  225.          *---------------------------------------------
  226.          */
  227.  
  228.         if ( (pnew = newnode(textbuf,textlen,line_number)) == NULL )
  229.             goto hell;
  230.  
  231.         switch (avlinsert(&avlTree, pnew, NULL) )
  232.         {
  233.         case -1:    /* error */
  234.             fprintf( stderr, "?? Cannot insert line (%lu): %s\n",
  235.                 pnew->lineno, pnew->text );
  236.             break;
  237.  
  238.         case  0:    /* success */
  239.             break;
  240.  
  241.         case  1:    /* duplicate key */
  242.             fprintf( stderr, "?? Duplicate key (%lu): %s\n",
  243.                 pnew->lineno, pnew->text );
  244.             break;
  245.         }
  246.  
  247.         line_number++;
  248.     }                
  249.  
  250.     /*---------------------------------------------
  251.      * Redirect stdout to named file, if specified.
  252.      * Close stdin because may be same file.
  253.      *---------------------------------------------
  254.      */
  255.  
  256.     if (outfile && *outfile)
  257.     {
  258.         /* redirect stdout to specified file */
  259.  
  260.         FILE    *fp = freopen( outfile, "w", stdout );
  261.         if (fp == NULL)
  262.         {
  263.             fprintf( stderr,
  264.                  "?? Cannot open file %s for output\n",
  265.                  outfile );
  266.             goto hell;
  267.         }
  268.         else if (fp != stdout)
  269.         {
  270.             fprintf( stderr, "?? freopen() error\n" );
  271.             goto hell;
  272.         }
  273.     }
  274.  
  275.     /*------------
  276.      * Print file.
  277.      *------------
  278.      */
  279.  
  280.     printtree( avlRoot );
  281.  
  282.     status = 0;    /* ok */
  283.  
  284. hell:
  285.     return( status );
  286. }
  287.  
  288. #if    defined(LATTICE) && defined(AMIGA)    /* Amiga; we link with ARP */
  289.  
  290. /*--------------------------------------------------------------------
  291.  * We link with S. Vigna's ARP startup code, which calls GADS() for us
  292.  * and returns the result as argv[].  We can ignore argc, which is the
  293.  * number of arguments actually supplied on the command line.
  294.  *--------------------------------------------------------------------
  295.  */
  296.  
  297. int    cmdparse( int argc, char **argv )
  298. {
  299.     char    *junk = NULL;
  300.     int    error = 0;
  301.  
  302.     if (argc <= 0)
  303.     {
  304.         /* Workbench */
  305.         return( -1 );
  306.     }
  307.     else if (argc > 7)
  308.     {
  309.         fprintf( stderr,
  310.              "?? Too many arguments\n%s\n%s\n",
  311.              CLI_Help, CLI_Template );
  312.         return( -1 );
  313.     }
  314.  
  315.     infile = argv[1];
  316.     outfile = argv[2];
  317.     if (argv[3])
  318.     {
  319.         colstart = strtol( argv[3], &junk, 10 );
  320.         if (junk && *junk)
  321.         {
  322.             fprintf( stderr,
  323.                  "?? Invalid digit \"%c\" for COLSTART\n",
  324.                  *junk );
  325.             error = -1;
  326.         }
  327.     }
  328.     if (argv[4])
  329.     {
  330.         colwidth = strtol( argv[4], &junk, 10 );
  331.         if (junk && *junk)
  332.         {
  333.             fprintf( stderr,
  334.                  "?? Invalid digit \"%c\" for WIDTH\n",
  335.                  *junk );
  336.             error = -1;
  337.         }
  338.     }
  339.     caseflag = (argv[5] != NULL);
  340.     reverseflag = (argv[6] != NULL);
  341.  
  342.     return( error );
  343. }
  344.  
  345. #else        /* Microsoft MSDOS or OS2; we have to roll our own parser */
  346.  
  347. /*-------------------------------------------------------------------
  348.  *    Usage: AVLSORT [infile] [outfile] [/COL n] [/WID n] [/U] [/R]
  349.  *        infile    default is stdin
  350.  *        outfile    default is stdout
  351.  *        /COL n    start column; default is 1 (may use /C:n)
  352.  *        /WID n    column width; default is all (may use /W:n)
  353.  *        /U        unique case (case-sensitive)
  354.  *        /R        reverse order
  355.  *-------------------------------------------------------------------
  356.  */
  357.  
  358. #define    MATCHn(s,t,n)    (strnicmp(s,t,n) == 0)
  359.  
  360. int    cmdparse( int argc, char **argv )
  361. {
  362.     char    c, *p, *colon, *junk = NULL;
  363.     int    i, helpflag = FALSE;
  364.     int    error = 0;
  365.  
  366.     /*------------------
  367.      * Get program name.
  368.      *------------------
  369.      */
  370.  
  371.     if (argc > 0)
  372.     {
  373.         if   (!argv[0] || !*argv[0])        ;  /* use default */
  374.         else if (p = strrchr(argv[0],'\\')) program = p+1;
  375.         else if (p = strrchr(argv[0],':'))  program = p+1;
  376.         else                    program = argv[0];
  377.  
  378.         strupr(program);
  379.     }
  380.  
  381.     /*------------------------------
  382.      * First pass: look for options.
  383.      *------------------------------
  384.      */
  385.  
  386.     for (i = 1; (i < argc) && !helpflag ; i++)
  387.     {
  388.         junk = NULL;
  389.  
  390.         if ( !(p = argv[i]) || !(c = *argv[i]) )
  391.             continue;        /* no argument */
  392.  
  393.         else if ( c == '?')        /* user requested help */
  394.             helpflag = TRUE;
  395.  
  396.         else if (c != '/' && c != '-')    /* not a switch */
  397.             continue;
  398.  
  399.         else if (MATCHn(p+1,"COL",3) && (i+1) < argc)
  400.         {
  401.             colstart = strtol( argv[i+1], &junk, 0 );
  402.             *argv[i+1] = 0;        /* ignore on second pass */
  403.         }
  404.  
  405.         else if ( MATCHn(p+1,"C",1) && (colon = strchr(p+1,':')) )
  406.             colstart = strtol( colon+1, &junk, 0 );
  407.  
  408.         else if (MATCHn(p+1,"WID",3) && (i+1) < argc)
  409.         {
  410.             colwidth = strtol( argv[i+1], &junk, 0 );
  411.             *argv[i+1] = 0;        /* ignore on second pass */
  412.         }
  413.  
  414.         else if ( MATCHn(p+1,"W",1) && (colon = strchr(p+1,':')) )
  415.             colwidth = strtol( colon+1, &junk, 0 );
  416.  
  417.         else if ( MATCHn(p+1,"U",1) )
  418.             caseflag = TRUE;
  419.  
  420.         else if ( MATCHn(p+1,"R",1) )
  421.             reverseflag = TRUE;
  422.  
  423.         else
  424.             helpflag = 1;
  425.  
  426.         if ( junk && *junk )        /* numeric field error */
  427.             helpflag = TRUE;
  428.     }
  429.  
  430.     /*----------------------------------
  431.      * Second pass: look for file names.
  432.      *----------------------------------
  433.      */
  434.  
  435.     for (i = 1; (i < argc) && !helpflag ; i++)
  436.     {
  437.         if (!argv[i] || !*argv[i])    /* no argument here */
  438.             continue;
  439.  
  440.         else if (*argv[i] == '-' || *argv[i] == '/')    /* switch */
  441.             continue;
  442.  
  443.         else if (!infile)
  444.             infile = strupr(argv[i]);
  445.  
  446.         else if (!outfile)
  447.             outfile = strupr(argv[i]);
  448.  
  449.         else
  450.             helpflag = 1;
  451.     }
  452.  
  453.     /*-----------------------
  454.      * Help requested? Error?
  455.      *-----------------------
  456.      */
  457.  
  458.     if (helpflag)
  459.     {
  460.         fprintf( stderr, usage, program );
  461.         return( -1 );
  462.     }
  463.  
  464.     if (outfile && strcmp(outfile,"=") == 0)
  465.         outfile = infile;
  466.  
  467.     return( 0 );
  468. }
  469.  
  470. #endif    /* cmdparse() */
  471.  
  472. /*---------------------------------------------------------------------
  473.  * We request relatively large chunks of memory, and hand out pieces as
  474.  * necessary.  We let Arp keep track, so we need not bother to free the
  475.  * memory when we are done.
  476.  *---------------------------------------------------------------------
  477.  */
  478.  
  479. #define    ALLOCMAX 0xFF00        /* largest size we can handle */
  480. #define    ALLOCMIN 1024        /* minimum size to allocate */
  481.  
  482. PVOID    myalloc( ULONG size )
  483. {
  484.     static    PCHAR    pointer    = NULL;
  485.     static    ULONG    offset    = 0;
  486.     PVOID    p    = NULL;
  487.  
  488.     /*-------------------------------------------------------
  489.      * Round requested size up to a multiple of 4.
  490.      * This should be adequate for alignment of most objects.
  491.      *-------------------------------------------------------
  492.      */
  493.  
  494.     size = (size + 3) & 0xFFFFFFFCL;
  495.  
  496.     /*----------------------------------------------------------
  497.      * There is a limit to how much we can allocate at one time.
  498.      *----------------------------------------------------------
  499.      */
  500.  
  501.     if (size > ALLOCMAX)
  502.         return( NULL );
  503.  
  504.     /*------------------------------------------------------
  505.      * For objects above a certain minimum size, we allocate
  506.      * a separate block.  This should help when we have a
  507.      * mixture of large and small objects.
  508.      *------------------------------------------------------
  509.      */
  510.  
  511.     if ( (size >= ALLOCMIN) && (p = ArpAlloc(size)) )
  512.         return( p );
  513.  
  514.     /*-------------------------------------------------
  515.      * If there is no room for new object in previously
  516.      * allocated block, we allocate another block.
  517.      *-------------------------------------------------
  518.      */
  519.  
  520.     if ( !pointer || (size > ALLOCMAX-offset) )    /* prevent overflow */
  521.     {
  522.         pointer = ArpAlloc(ALLOCMAX);
  523.          offset = 0;
  524.     }
  525.  
  526.     /*-----------------------------------------------
  527.      * If there is a block hanging around, it should
  528.      * have room for this object.  Carve off a piece.
  529.      *-----------------------------------------------
  530.      */
  531.  
  532.     if (pointer)
  533.     {
  534.         p = (PVOID) (pointer + offset);
  535.         offset += size;
  536.         return( p );
  537.     }
  538.     else
  539.         return( NULL );
  540. }
  541.  
  542. /*---------------------------------------------------------------------------
  543.  * Initialize a new node to be inserted in the tree.
  544.  *---------------------------------------------------------------------------
  545.  */
  546.  
  547. PNODE    newnode( PCHAR text, ULONG textlen, ULONG lineno )
  548. {
  549.     PCHAR    ptext;
  550.     PNODE    pnew     = NULL;
  551. static    AVLNODE    avldummy = { NULL, NULL, 0 };
  552.  
  553.     if ( (ptext = myalloc(textlen+1)) && (pnew = myalloc(SZOF_MYNODE)) )
  554.     {
  555.         strcpy( ptext, text );
  556.         pnew->avlnode    = avldummy;
  557.         pnew->text    = ptext;
  558.         pnew->textlen    = textlen;
  559.         pnew->lineno    = lineno;
  560.     }
  561.     return( pnew );
  562. }
  563.  
  564. /*---------------------------------------------------------------------------
  565.  *
  566.  *    int cmprtc( keyP, nodeP )
  567.  *        void    *keyP;
  568.  *        AVLNODE    *nodeP;
  569.  *    
  570.  *    CMPRTC compares a given key against a key associated
  571.  *    with a node.
  572.  *
  573.  *    keyP    the address of a key (interpreted in
  574.  *        whatever way is applicable)
  575.  *    nodeP    the address of an AVLNODE structure
  576.  *        to which the key should be compared.
  577.  *
  578.  *    It shall return
  579.  *        -1 if keyP is less than the key associated with nodeP key;
  580.  *         0 if they match;
  581.  *        +1 if keyP is greater than the key associated with nodeP.
  582.  *
  583.  *    IMPLEMENTATION NOTE:
  584.  *    For this application, keyP points to a previously-allocated
  585.  *    AVL node.
  586.  *---------------------------------------------------------------------------
  587.  */
  588.  
  589. int    cmprtc( void *keyP, AVLNODE *nodeP )
  590. {
  591.     PNODE    kp    = (PNODE) keyP;
  592.     PNODE    np    = (PNODE) nodeP;
  593.     PCHAR    ktext    = kp->text + colstart;
  594.     PCHAR    ntext    = np->text + colstart;
  595.     int    khastext = (kp->textlen > colstart);
  596.     int    nhastext = (np->textlen > colstart);
  597.     int    cmp;
  598.  
  599.     /*---------------------------------------------------------------*/
  600.     /* If both lines are long enough, apply the comparison function. */
  601.     /* If only one line is long enough, it should precede the other. */
  602.     /* If neither line is long enough, call them equal (for now).     */
  603.     /*---------------------------------------------------------------*/
  604.  
  605.     if (khastext && nhastext)
  606.         cmp = (*pfnCompare)( ktext, ntext, colwidth );
  607.     else
  608.     {
  609.         /*--------------------------------------*/
  610.         /* k n -> cmp                */
  611.         /* ----------                */
  612.         /* 0 0     0    equal            */
  613.         /* 1 0    -1    key has precedence    */
  614.         /* 0 1     1    node has precedence    */
  615.         /* 1 1    n/a    handled by if(), above    */
  616.         /*--------------------------------------*/
  617.  
  618.         cmp = nhastext - khastext;
  619.     }
  620.  
  621.     /*-------------------------------------------------------*/
  622.     /* If the lines are equal, then the line that came first */
  623.     /*    in the original file should have precedence.     */
  624.     /* Otherwise, make sure we return 1 or -1.         */
  625.     /*-------------------------------------------------------*/
  626.  
  627.     if (cmp == 0)
  628.     {
  629.         /*------------------------------------------------------*/
  630.         /* k < n  : (0 - 1) = -1    key has precedence    */
  631.         /* k > n  : (1 - 0) = 1        node has precedence    */
  632.         /* k == n : (0 - 0) = 0        error, should not match    */
  633.         /*------------------------------------------------------*/
  634.  
  635.         return (kp->lineno > np->lineno) - (kp->lineno < np->lineno);
  636.     }
  637.     else
  638.     {
  639.         /*------------------------------------------------------*/
  640.         /* cmp == 0 : n/a        handled by if(), above    */
  641.         /* cmp < 0  : (0 - 1) = -1    key has precedence    */
  642.         /* cmp > 0  : (1 - 0) = 1    node has precedence    */
  643.         /*------------------------------------------------------*/
  644.  
  645.         return (cmp > 0) - (cmp < 0);
  646.     }
  647. }
  648.  
  649. /*---------------------------------------------------------------------------
  650.  *    AVLNODE *mknode( treeP, keyP, dataP, enodeP )
  651.  *        AVLTREE    *treeP;
  652.  *        void    *keyP;
  653.  *        void    *dataP;
  654.  *        AVLNODE    *enodeP;
  655.  *    
  656.  *    MKNODE creates a node on behalf of tree insertion.
  657.  *    
  658.  *    treeP    the address of the tree description structure
  659.  *    keyP    the address of any key associated with the node
  660.  *    dataP    the address of any data associated with the node
  661.  *    enodeP    the address of any node that already exists in
  662.  *        the tree for keyP.
  663.  *
  664.  *    If enodeP is not NULL, then this routine is being called
  665.  *    to replace the data in an existing node.  It can signal
  666.  *    its unwillingness to do this by returning NULL as its
  667.  *    return value, otherwise it must return the address of the
  668.  *    existing node.  Otherwise (if enodeP is NULL), this
  669.  *    routine should allocate (or otherwise create) a new node
  670.  *    and fill it in.
  671.  *    
  672.  *    MKNODE shall return the address of the node constructed,
  673.  *    or NULL if no node was made.
  674.  *
  675.  *    IMPLEMENTATION NOTE:
  676.  *    For this application, keyP points to a previously-allocated
  677.  *    AVL node.
  678.  *---------------------------------------------------------------------------
  679.  */
  680.  
  681. AVLNODE *mknode( AVLTREE *treeP, void *keyP, void *dataP, AVLNODE *enodeP )
  682. {
  683.     if (enodeP)
  684.         return( (AVLNODE *)NULL );
  685.     else
  686.         return( (AVLNODE *)keyP );
  687. }
  688.  
  689. /*---------------------------------------------------------------------------
  690.  *    void rmnode( treeP, nodeP )
  691.  *        AVLTREE    *treeP;
  692.  *        AVLNODE    *nodeP;
  693.  *    
  694.  *    RMNODE is called to delete a node and its information.
  695.  *    
  696.  *    treeP is the address of the tree description structure;
  697.  *    nodeP is the address of the node to delete.
  698.  *    
  699.  *    It is called when a node is removed from a tree; it may
  700.  *    do what it likes and does not return any information.
  701.  *
  702.  *    IMPLEMENTATION NOTE:
  703.  *    For this application, we cannot do anything.
  704.  *---------------------------------------------------------------------------
  705.  */
  706.  
  707. void    rmnode( AVLTREE *treeP, AVLNODE *nodeP )
  708. {
  709. }
  710.  
  711. /*---------------------------------------------------------------------------
  712.  * Print the tree to stdout (which may have been redirected).
  713.  *---------------------------------------------------------------------------
  714.  */
  715.  
  716. void    printtree( PNODE p )
  717. {
  718.     if (!p)
  719.         return;
  720.  
  721.     else if (reverseflag)
  722.     {
  723.         printtree( (PNODE)(p->avlnode.n_rightP) );
  724.         puts( p->text );
  725.         printtree( (PNODE)(p->avlnode.n_leftP) );
  726.     }
  727.  
  728.     else
  729.     {
  730.         printtree( (PNODE)(p->avlnode.n_leftP) );
  731.         puts( p->text );
  732.         printtree( (PNODE)(p->avlnode.n_rightP) );
  733.     }
  734. }
  735.  
  736.