/*--------------------------------------------------------------------------- * AVLSORT From,To,COLSTART/k,WIDTH/k,TABSTOP/k,CASE/s,REVERSE/s,STRIP/s * * Amiga Usage: * From input file (default stdin) * To output file (default stdout) * COLSTART nn start at column nn (default is 1) * WIDTH nn width of sort field (default is entire line) * TABSTOP nn expand tabs (default is no expansion) * CASE case sensitive (default case insensitive) * REVERSE sort in reverse order * STRIP strip trailing white space * OPT T|C|R|S same as TABSTOP 8 | CASE | REVERSE | STRIP * * Copyright © 1990, 1991 by Robert L. Pyron. All Rights Reserved. * This program may be freely distributed, provided that all the files in * this archive are included. Bug fixes and improvements are welcome, * please send these to me on BIX (rpyron). * * Version 1.1, Robert L. Pyron, 19 June 1991 * * This is an update to AVLSORT.LZH, posted previously on BIX. There are * several bug fixes and an algorithm improvement: * * -- Better tracking of memory * -- Check for control-C, -D, -E, and -F * -- Split into several source files * -- Identical lines are now placed in a linked list * *--------------------------------------------------------------------------- */ #include #include #include #include #include #include #include #include #include #include #include "avltree.h" #include "getline.h" #include "isatty.h" #include "mem.h" /*--------------------------------------------------------------------------- * ARP support *--------------------------------------------------------------------------- */ extern struct ArpBase *ArpBase; /* Template and Extended Help for GADS(), from ARP */ char *CLI_Template = "From,To,COL=COLSTART/k,WID=WIDTH/k," "TAB=TABS=TABSTOP/k,CASE/s,R=REVERSE/s," "STRIP/s,OPT/k"; char *CLI_Help = "Usage:\n" " From input file (default stdin)\n" " To output file (default stdout)\n" " COLSTART nn start at column nn (default is 1)\n" " WIDTH nn width of sort field (default is entire line)\n" " TABSTOP nn expand tabs (default is no expansion)\n" " CASE case sensitive (default case insensitive)\n" " REVERSE sort in reverse order\n" ; /*--------------------------------------------------------------------------- * Typedefs and defines *--------------------------------------------------------------------------- */ #define ISSPACE(c) (isascii(c) && isspace(c)) #define FALSE 0 #define TRUE 1 #define TEXTMAX 32767 #define BREAKFLAGS (SIGBREAKF_CTRL_C | SIGBREAKF_CTRL_D | \ SIGBREAKF_CTRL_E | SIGBREAKF_CTRL_F ) typedef unsigned char UCHAR; typedef unsigned short USHORT; typedef unsigned long ULONG; typedef UCHAR *PCHAR; typedef void *PVOID; typedef struct MinNode MINNODE; typedef struct _MYNODE { union { AVLNODE avlnode; MINNODE minnode; } v; PCHAR text; ULONG textlen; struct List chain; } MYNODE; typedef MYNODE *PNODE; #define SZOF_MYNODE sizeof(MYNODE) typedef int (*PFNCOMPARE) (const char *, const char *, unsigned int); /*--------------------------------------------------------------------------- * Prototypes *--------------------------------------------------------------------------- */ static void handlebreak (LONG mask); static FILE *redirect (char *filename, char *mode, FILE *oldfp, int errlevel ); static int __regargs cmdparse (int argc, char **argv); static MYNODE * __regargs newnode (PCHAR text, ULONG textlen); static void __regargs printtree (MYNODE * p); static int __regargs cmprtc (void *keyP, AVLNODE *nodeP); static AVLNODE * __regargs mknode (AVLTREE *treeP, void *keyP, void *dataP, AVLNODE *enodeP); static void __regargs rmnode (AVLTREE *treeP, AVLNODE *nodeP); /*--------------------------------------------------------------------------- * Global data *--------------------------------------------------------------------------- */ /* * User may specify the following parameters on command line: */ char *infile = NULL; /* input file name, default stdin */ char *outfile = NULL; /* output file name, default stdout */ long colstart = 0; /* start column, default 1 */ long colwidth = TEXTMAX; /* width, default full line */ long tabstop = 0; /* translate tabs, default no translate */ int caseflag = 0; /* case sensitivity, default off */ int reverseflag = 0; /* reverse sort, default off */ int stripflag = 0; /* strip trailing blanks, default off */ /* * This is our AVL tree. */ AVLTREE avlTree = { NULL, /* ptr to root node */ cmprtc, /* compare node to arbitrary data */ mknode, /* create node */ rmnode /* destroy node */ }; #define avlRoot ((MYNODE *)avlTree.t_rootP) /* * Pointer to string comparison function. If case sensitivity * is off (default), use strnicmp(). Otherwise use strncmp(). */ PFNCOMPARE pfnCompare = (PFNCOMPARE) strnicmp; /* * jmp_buf struct for handlebreak(). */ jmp_buf break_jmp_buf; /*--------------------------------------------------------------------------- *--------------------------------------------------------------------------- */ static void handlebreak (LONG mask) { if (mask) { fflush (stdout); fflush (stderr); fprintf (stderr, "*** BREAK\n"); longjmp (break_jmp_buf, 20); } } /*--------------------------------------------------------------------------- * Notice int return type, we are returning a value to Arp startup code. *--------------------------------------------------------------------------- */ int main (int argc, char **argv) { long line_number; MYNODE * pnew; int status; register PCHAR textbuf; int textlen; /*-------------------------------------- * Set up jump buffer for handlebreak(). *-------------------------------------- */ if (status = setjmp(break_jmp_buf)) goto hell; status = 20; /* assume the worst */ /*------------------------------- * Get options from command line. *------------------------------- */ if (cmdparse (argc, argv)) goto hell; if (--colstart < 0) colstart = 0; /* convert to zero-based */ if (colwidth <= 0) colwidth = TEXTMAX; if (caseflag) pfnCompare = (PFNCOMPARE) strncmp; if (infile && !*infile) infile = NULL; else if (infile && strcmp (infile, "-") == 0) infile = NULL; else if (infile && strcmp (infile, "=") == 0) infile = NULL; if (outfile && !*outfile) outfile = infile; else if (outfile && strcmp (outfile, "-") == 0) outfile = NULL; else if (outfile && strcmp (outfile, "=") == 0) outfile = infile; /*-------------------------------------------- * Redirect stdin to named file, if specified. *-------------------------------------------- */ if (infile) redirect (infile, "r", stdin, 20); if (!isatty(fileno(stdin))) setvbuf(stdin,NULL,_IOFBF,16384); /*----------------------- * Allocate line buffers. *----------------------- */ if ((textbuf = ArpAlloc (TEXTMAX+1)) == NULL) { fprintf (stderr, "?? Out of memory\n"); goto hell; } /*---------------------------------- * Read file; put each line in tree. *---------------------------------- */ line_number = 0; while ((textlen = getline(textbuf,TEXTMAX,tabstop,stdin)) >= 0) { /*--------------------------------------------- * Call ARP function to check for break signal. *--------------------------------------------- */ CheckBreak (BREAKFLAGS, handlebreak); if (stripflag) { while (textlen && ISSPACE(textbuf[textlen-1]) ) textbuf[--textlen] = '\0'; } if (!(pnew = newnode(textbuf, (ULONG)textlen))) goto hell; switch (avlinsert (&avlTree, pnew, NULL)) { case -1: /* error */ fprintf (stderr, "?? Cannot insert line (%lu): %s\n", line_number, pnew->text); goto hell; case 0: /* success */ break; case 1: /* duplicate key */ fprintf (stderr, "?? Duplicate key (%lu): %s\n", line_number, pnew->text); goto hell; default: fprintf (stderr, "?? Unknown return from avlinsert()\n"); goto hell; } line_number++; } /*--------------------------------------------- * Print file. * Redirect stdout to named file, if specified. * Close stdin because may be same file. *--------------------------------------------- */ fclose (stdin); if (outfile) redirect (outfile, "w", stdout, 20); if (!isatty(fileno(stdout))) setvbuf(stdout,NULL,_IOFBF,16384); printtree (avlRoot); status = 0; /* ok */ hell: myfreeall (); return (status); } /*-------------------------------------------------------------------- * We link with S. Vigna's ARP startup code, which calls GADS() for us * and returns the result as argv[]. We can ignore argc, which is the * number of arguments actually supplied on the command line. *-------------------------------------------------------------------- */ static int __regargs cmdparse (int argc, char **argv) { char *junk = NULL; int error = 0; if (argc <= 0) { /* Workbench */ return (-1); } else if (argc > 10) { fprintf (stderr, "?? Too many arguments\n%s\n%s\n", CLI_Help, CLI_Template); return (-1); } infile = argv[1]; /* From */ outfile = argv[2]; /* To */ if (argv[3]) /* COLSTART */ { colstart = strtol (argv[3], &junk, 10); if (junk && *junk) { fprintf (stderr, "?? Invalid digit \"%c\" for COLSTART\n", *junk); error = -1; } } if (argv[4]) /* WIDTH */ { colwidth = strtol (argv[4], &junk, 10); if (junk && *junk) { fprintf (stderr, "?? Invalid digit \"%c\" for WIDTH\n", *junk); error = -1; } } if (argv[5]) /* TABSTOP */ { tabstop = strtol (argv[5], &junk, 10); if (tabstop < 0) { fprintf (stderr, "?? Invalid TABSTOP\n" ); error = -1; } else if (junk && *junk) { fprintf (stderr, "?? Invalid digit \"%c\" for TABSTOP\n", *junk); error = -1; } } caseflag = (argv[6] != NULL); /* CASE */ reverseflag = (argv[7] != NULL); /* REVERSE */ stripflag = (argv[8] != NULL); /* STRIP */ if (argv[9]) /* OPT */ { strupr (argv[9]); if (strchr(argv[9],'T') && !tabstop) tabstop = 8; if (strchr(argv[9],'C')) caseflag = TRUE; if (strchr(argv[9],'R')) reverseflag = TRUE; if (strchr(argv[9],'S')) stripflag = TRUE; if (strchr(argv[9],'X')) tabstop = -1; } return (error); } /*--------------------------------------------------------------------------- * Initialize a new node to be inserted in the tree. *--------------------------------------------------------------------------- */ static MYNODE * __regargs newnode (PCHAR text, ULONG textlen) { PCHAR ptext; MYNODE * pnew = NULL; static AVLNODE avldummy = {NULL, NULL, 0}; if (ptext = myalloc (textlen + 1)) { if (pnew = myalloc (SZOF_MYNODE)) { strcpy (ptext, text); pnew->v.avlnode = avldummy; pnew->text = ptext; pnew->textlen = textlen; NewList (&pnew->chain); } } return (pnew); } /*--------------------------------------------------------------------------- * * int cmprtc( keyP, nodeP ) * void *keyP; * AVLNODE *nodeP; * * CMPRTC compares a given key against a key associated * with a node. * * keyP the address of a key (interpreted in * whatever way is applicable) * nodeP the address of an AVLNODE structure * to which the key should be compared. * * It shall return * -1 if keyP is less than the key associated with nodeP key; * 0 if they match; * +1 if keyP is greater than the key associated with nodeP. * * IMPLEMENTATION NOTE: * For this application, keyP points to a previously-allocated * AVL node. *--------------------------------------------------------------------------- */ static int __regargs cmprtc (void *keyP, AVLNODE * nodeP) { MYNODE * kp = (MYNODE *) keyP; MYNODE * np = (MYNODE *) nodeP; PCHAR ktext = kp->text + colstart; PCHAR ntext = np->text + colstart; int khastext = (kp->textlen > colstart); int nhastext = (np->textlen > colstart); int cmp; /*--------------------------------------------------------------- * If both lines are long enough, apply the comparison function. * If only one line is long enough, it should precede the other. * If neither line is long enough, call them equal (for now). *--------------------------------------------------------------- */ if (khastext && nhastext) cmp = (*pfnCompare) (ktext, ntext, colwidth); else { /*-------------------------------------- * k n -> cmp * ---------- * 0 0 0 equal * 1 0 -1 key has precedence * 0 1 1 node has precedence * 1 1 n/a handled by if(), above *-------------------------------------- */ cmp = nhastext - khastext; } /*-------------------- * Return -1, 0, or 1. *-------------------- */ return (cmp > 0) - (cmp < 0); } /*--------------------------------------------------------------------------- * AVLNODE *mknode( treeP, keyP, dataP, enodeP ) * AVLTREE *treeP; * void *keyP; * void *dataP; * AVLNODE *enodeP; * * MKNODE creates a node on behalf of tree insertion. * * treeP the address of the tree description structure * keyP the address of any key associated with the node * dataP the address of any data associated with the node * enodeP the address of any node that already exists in * the tree for keyP. * * If enodeP is not NULL, then this routine is being called * to replace the data in an existing node. It can signal * its unwillingness to do this by returning NULL as its * return value, otherwise it must return the address of the * existing node. Otherwise (if enodeP is NULL), this * routine should allocate (or otherwise create) a new node * and fill it in. * * MKNODE shall return the address of the node constructed, * or NULL if no node was made. * * IMPLEMENTATION NOTE: * For this application, keyP points to a previously-allocated * AVL node. *--------------------------------------------------------------------------- */ static AVLNODE * __regargs mknode (AVLTREE * treeP, void *keyP, void *dataP, AVLNODE * enodeP) { if (enodeP) { AddTail (&((MYNODE *) enodeP)->chain, (struct Node *)keyP); return ((AVLNODE *) enodeP); } else return ((AVLNODE *) keyP); } /*--------------------------------------------------------------------------- * void rmnode( treeP, nodeP ) * AVLTREE *treeP; * AVLNODE *nodeP; * * RMNODE is called to delete a node and its information. * * treeP is the address of the tree description structure; * nodeP is the address of the node to delete. * * It is called when a node is removed from a tree; it may * do what it likes and does not return any information. * * IMPLEMENTATION NOTE: * For this application, we cannot do anything. *--------------------------------------------------------------------------- */ static void __regargs rmnode (AVLTREE * treeP, AVLNODE * nodeP) { } /*--------------------------------------------------------------------------- * Print the tree to stdout (which may have been redirected). *--------------------------------------------------------------------------- */ static void __regargs printtree (MYNODE * pnode) { MYNODE *xp; if (!pnode) return; /*--------------------------------------------- * Call ARP function to check for break signal. *--------------------------------------------- */ CheckBreak (BREAKFLAGS, handlebreak); if (reverseflag) { printtree ((MYNODE *) (pnode->v.avlnode.n_rightP)); while (xp = (MYNODE *) RemTail (&pnode->chain)) puts(xp->text); puts (pnode->text); printtree ((MYNODE *) (pnode->v.avlnode.n_leftP)); } else { printtree ((MYNODE *) (pnode->v.avlnode.n_leftP)); puts (pnode->text); while (xp = (MYNODE *) RemHead (&pnode->chain)) puts(xp->text); printtree ((MYNODE *) (pnode->v.avlnode.n_rightP)); } } /*--------------------------------------------------------------------------- * Redirect file handle to named file. * Altered from version in REDIRECT.C, * so we can use longjmp() rather than exit(). *--------------------------------------------------------------------------- */ static FILE * redirect( char *filename, char *mode, FILE *oldfp, int errlevel ) { FILE *newfp; if (!mode) { fprintf( stderr, "?? freopen() error for file %s\n", filename ); longjmp (break_jmp_buf,errlevel); } if ( filename && *filename ) newfp = freopen( filename, mode, oldfp ); else newfp = oldfp; if ( newfp == NULL ) { fprintf( stderr, "?? Cannot open file %s for %s\n", filename, (*mode == 'r') ? "input" : (*mode == 'w') ? "output" : (*mode == 'a') ? "append" : "(unknown mode)" ); longjmp (break_jmp_buf,errlevel); } else if ( newfp != oldfp ) { fprintf( stderr, "?? freopen() error for file %s\n", filename ); longjmp (break_jmp_buf,errlevel); } else return( newfp ); }