/*
 *			X D U . C
 *
 * Display the output of "du" in an X window.
 *
 * Phillip C. Dykstra
 * <phil@arl.mil>
 * 4 Sep 1991.
 * 
 * Copyright (c)	Phillip C. Dykstra	1991, 1993, 1994
 * The X Consortium, and any party obtaining a copy of these files from
 * the X Consortium, directly or indirectly, is granted, free of charge, a
 * full and unrestricted irrevocable, world-wide, paid up, royalty-free,
 * nonexclusive right and license to deal in this software and
 * documentation files (the "Software"), including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons who receive
 * copies from any such party to do so.  This license includes without
 * limitation a license to do the foregoing actions under any patents of
 * the party supplying this software to the X Consortium.
 */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "version.h"

#define	MAXDEPTH	80	/* max elements in a path */
#define	MAXNAME		1024	/* max pathname element length */
#define	MAXPATH		4096	/* max total pathname length */
#define	NCOLS		5	/* default number of columns in display */

/* What we IMPORT from xwin.c */
void xsetup(int *argcp, char **argv);
void xmainloop(void);
void xclear(void);
void xrepaint(void);
void xdrawrect(char *name, off_t size, int x, int y, int width, int height);

int ncols = NCOLS;

/* internal routines */
void addtree();
void parse_file();
void parse_entry();
void dumptree();
void clearrects();
void sorttree();

/* order to sort paths by */
#define	ORD_FIRST	1
#define	ORD_LAST	2
#define	ORD_ALPHA	3
#define	ORD_SIZE	4
#define	ORD_RALPHA	5
#define	ORD_RSIZE	6
#define	ORD_DEFAULT	ORD_FIRST
int order = ORD_DEFAULT;

/*
 * Rectangle Structure
 * Stores window coordinates of a displayed rectangle
 * so that we can "find" it again on key presses.
 */
struct rect {
	int	left;
	int	top;
	int	width;
	int	height;
};

/*
 * Node Structure
 * Each node in the path tree is linked in with one of these.
 */
struct node {
	char	*name;
	off_t	size;		/* from here down in the tree */
	long	num;		/* entry number - for resorting */
	struct	rect rect;	/* last drawn screen rectangle */
	struct	node *peer;	/* siblings */
	struct	node *child;	/* list of children if !NULL */
	struct	node *parent;	/* backpointer to parent */
} top;
struct node *topp = &top;
#define	NODE_NULL ((struct node *)0)
long nnodes = 0;

/*
 * create a new node with the given name and size info
 */
struct node *
makenode (char *name, off_t size)
{
	struct	node	*np;

	np = (struct node *)calloc(1,sizeof(struct node));
	np->name = strdup(name);
	np->size = size;
	np->num = nnodes;
	nnodes++;

	return	np;
}

/*
 * Return the node (if any) which has a draw rectangle containing
 * the given x,y point.
 */
struct node *
findnode (struct node *treep, int x, int y)
{
	struct	node	*np;
	struct	node	*np2;

	if (treep == NODE_NULL)
		return	NODE_NULL;

	if (x >= treep->rect.left && x < treep->rect.left+treep->rect.width
	 && y >= treep->rect.top && y < treep->rect.top+treep->rect.height) {
		/*printf("found %s\n", treep->name);*/
		return	treep;	/* found */
	}

	/* for each child */
	for (np = treep->child; np != NULL; np = np->peer) {
		if ((np2 = findnode(np,x,y)) != NODE_NULL)
			return	np2;
	}
	return	NODE_NULL;
}

/*
 * return a count of the number of children of a given node
 */
int
numchildren (struct node *nodep)
{
	int	n;

	if (nodep == NODE_NULL)
		return	0;

	n = 0;
	for (nodep = nodep->child; nodep != NODE_NULL; nodep=nodep->peer)
		n++;

	return	n;
}

/*
 * fix_tree - This function repairs the tree when certain nodes haven't
 * 	      had their sizes initialized. [DPT911113]
 *	      * * * This function is recursive * * *
 */
off_t
fix_tree (struct node *top)
{
	struct node *nd;

	if (top == NODE_NULL)		/* recursion end conditions */
		return 0;
	if (top->size >= 0) 		/* also halt recursion on valid size */
		return top->size;	/* (remember: sizes init. to -1) */

	top->size = 0;
	for (nd = top->child; nd != NODE_NULL; nd = nd->peer)
		top->size += fix_tree(nd);

	return top->size;
}

static char usage[] = "\
Usage: xdu [-options ...] filename\n\
   or  xdu [-options ...] < du.out\n\
\n\
Graphically displays the output of du in an X window\n\
  options include:\n\
  -s          Don't display size information\n\
  +s          Display size information (default)\n\
  -n          Sort in numerical order (largest first)\n\
  -rn         Sort in reverse numerical order\n\
  -a          Sort in alphabetical order\n\
  -ra         Sort in reverse alphabetical order\n\
  -c num      Set number of columns to num\n\
  Toolkit options: -fg, -bg, -rv, -display, -geometry, etc.\n\
";

int
main (int argc, char **argv)
{
	top.name = strdup("[root]");
	top.size = -1;

	xsetup(&argc,argv);
	if (argc == 1) {
		if (isatty(fileno(stdin))) {
			fprintf(stderr, "%s", usage);
			exit(1);
		} else {
			parse_file("-");
		}
	} else if (argc == 2 && strcmp(argv[1],"-help") != 0) {
		parse_file(argv[1]);
	} else {
		fprintf(stderr, "%s", usage);
		exit(1);
	}
	top.size = fix_tree(&top);

	/*dumptree(&top,0);*/
	if (order != ORD_DEFAULT)
		sorttree(&top, order);

	topp = &top;
	/* don't display root if only one child */
	if (numchildren(topp) == 1)
		topp = topp->child;

	xmainloop();
	exit(0);
}

void
parse_file(char *filename)
{
	char	buf[4096];
	char	name[4096];
	intmax_t size;
	FILE	*fp;

	if (strcmp(filename, "-") == 0) {
		fp = stdin;
	} else {
		if ((fp = fopen(filename, "r")) == 0) {
			fprintf(stderr, "xdu: can't open \"%s\"\n", filename);
			exit(1);
		}
	}
	while (fgets(buf,sizeof(buf),fp) != NULL) {
		sscanf(buf, "%jd %4095[^\n]\n", &size, name);
		/*printf("%jd %s\n", size, name);*/
		parse_entry(name,(off_t)size);
	}
	fclose(fp);
}

/* bust up a path string and link it into the tree */
void
parse_entry(char *name, off_t size)
{
	char	*path[MAXDEPTH]; /* break up path into this list */
	char	buf[MAXNAME];	 /* temp space for path element name */
	int	arg, indx;
	int	length;		/* nelson@reed.edu - trailing / fix */

	if (*name == '/')
		name++;		/* skip leading / */

	length = strlen(name);
	if ((length > 0) && (name[length-1] == '/')) {
		/* strip off trailing / (e.g. GNU du) */
		name[length-1] = 0;
	}

	arg = 0; indx = 0;
	bzero(path,sizeof(path));
	bzero(buf,sizeof(buf));
	while (*name) {
		if (*name == '/') {
			buf[indx] = 0;
			path[arg++] = strdup(buf);
			indx = 0;
			if (arg >= MAXDEPTH)
				break;
		} else {
			buf[indx++] = *name;
			if (indx >= MAXNAME)
				break;
		}
		name++;
	}
	buf[indx] = 0;
	path[arg++] = strdup(buf);
	path[arg] = NULL;

	addtree(&top,path,size);
}

/*
 *  Determine where n1 should go compared to n2
 *    based on the current sorting order.
 *  Return -1 if is should be before.
 *          0 if it is a toss up.
 *	    1 if it should go after.
 */
int
compare(struct node *n1, struct node *n2, int order)
{
	int	ret;

	switch (order) {
	case ORD_SIZE:
		ret = n2->size - n1->size;
		if (ret == 0)
			return strcmp(n1->name,n2->name);
		else
			return ret;
		break;
	case ORD_RSIZE:
		ret = n1->size - n2->size;
		if (ret == 0)
			return strcmp(n1->name,n2->name);
		else
			return ret;
		break;
	case ORD_ALPHA:
		return strcmp(n1->name,n2->name);
		break;
	case ORD_RALPHA:
		return strcmp(n2->name,n1->name);
		break;
	case ORD_FIRST:
		/*return -1;*/
		return (n1->num - n2->num);
		break;
	case ORD_LAST:
		/*return 1;*/
		return (n2->num - n1->num);
		break;
	}

	/* shouldn't get here */
	fprintf(stderr,"xdu: bad insertion order\n");
	return	0;
}

void
insertchild(
    struct node *nodep,	/* parent */
    struct node *childp,	/* child to be added */
    int order		/* FIRST, LAST, ALPHA, SIZE */
)
{
	struct node *np, *np1;

	if (nodep == NODE_NULL || childp == NODE_NULL)
		return;
	if (childp->peer != NODE_NULL) {
		fprintf(stderr, "xdu: can't insert child with peers\n");
		return;
	}

	childp->parent = nodep;
	if (nodep->child == NODE_NULL) {
		/* no children, order doesn't matter */
		nodep->child = childp;
		return;
	}
	/* nodep has at least one child already */
	if (compare(childp,nodep->child,order) < 0) {
		/* new first child */
		childp->peer = nodep->child;
		nodep->child = childp;
		return;
	}
	np1 = nodep->child;
	for (np = np1->peer; np != NODE_NULL; np = np->peer) {
		if (compare(childp,np,order) < 0) {
			/* insert between np1 and np */
			childp->peer = np;
			np1->peer = childp;
			return;
		}
		np1 = np;
	}
	/* at end, link new child on */
	np1->peer = childp;
}

/* add path as a child of top - recursively */
void
addtree(struct node *top, char *path[], off_t size)
{
	struct	node *np;

	/*printf("addtree(\"%s\",\"%s\",%d)\n", top->name, path[0], size);*/

	/* check all children for a match */
	for (np = top->child; np != NULL; np = np->peer) {
		if (strcmp(path[0],np->name) == 0) {
			/* name matches */
			if (path[1] == NULL) {
				/* end of the chain, save size */
				np->size = size;
				return;
			}
			/* recurse */
			addtree(np,&path[1],size);
			return;
		}
	}
	/* no child matched, add a new child */
	np = makenode(path[0],-1);
	insertchild(top,np,order);

	if (path[1] == NULL) {
		/* end of the chain, save size */
		np->size = size;
		return;
	}
	/* recurse */
	addtree(np,&path[1],size);
	return;
}

/* debug tree print */
void
dumptree(struct node *np, int level)
{
	int	i;
	struct	node *subnp;

	for (i = 0; i < level; i++)
		printf("   ");

	printf("%s %jd\n", np->name, (intmax_t)np->size);
	for (subnp = np->child; subnp != NULL; subnp = subnp->peer) {
		dumptree(subnp,level+1);
	}
}

void
sorttree(struct node *np, int order)
{
	struct	node *subnp;
	struct	node *np0, *np1, *np2, *np3;

	/* sort the trees of each of this nodes children */
	for (subnp = np->child; subnp != NODE_NULL; subnp = subnp->peer) {
		sorttree(subnp, order);
	}
	/* then put the given nodes children in order */
	np0 = np;	/* np0 points to node before np1 */
	for (np1 = np->child; np1 != NODE_NULL; np1 = np1->peer) {
		np2 = np1;	/* np2 points to node before np3 */
		for (np3 = np1->peer; np3 != NODE_NULL; np3 = np3->peer) {
			if (compare(np3,np1,order) < 0) {
				/* swap links */
				if (np0 == np)
					np0->child = np3;
				else
					np0->peer = np3;
				np2->peer = np3->peer;
				np3->peer = np1;

				/* adjust pointers */
				np1 = np3;
				np3 = np2;
			}
			np2 = np3;
		}
		np0 = np1;
	}
}

void drawchildren(struct node *nodep, struct rect rect);
/*
 * Draws a node in the given rectangle, and all of its children
 * to the "right" of the given rectangle.
 */
void
drawnode(
    struct node *nodep,	/* node whose children we should draw */
    struct rect rect	/* rectangle to draw all children in */
)
{
	struct rect subrect;

	/*printf("Drawing \"%s\" %d\n", nodep->name, nodep->size);*/

	xdrawrect(nodep->name, nodep->size,
		rect.left,rect.top,rect.width,rect.height);

	/* save current screen rectangle for lookups */
	nodep->rect.left = rect.left;
	nodep->rect.top = rect.top;
	nodep->rect.width = rect.width;
	nodep->rect.height = rect.height;

	/* draw children in subrectangle */
	subrect.left = rect.left+rect.width;
	subrect.top = rect.top;
	subrect.width = rect.width;
	subrect.height = rect.height;
	drawchildren(nodep, subrect);
}

/*
 * Draws all children of a node within the given rectangle.
 * Recurses on children.
 */
void
drawchildren(
    struct node *nodep,	/* node whose children we should draw */
    struct rect rect	/* rectangle to draw all children in */
)
{
	off_t	totalsize;
	int	totalheight;
	struct	node	*np;
	double	fractsize;
	int	height;
	int	top;

	/*printf("Drawing children of \"%s\", %d\n", nodep->name, nodep->size);*/
	/*printf("In [%d,%d,%d,%d]\n", rect.left,rect.top,rect.width,rect.height);*/

	top = rect.top;
	totalheight = rect.height;
	totalsize = nodep->size;
	if (totalsize == 0) {
		/* total the sizes of the children */
		totalsize = 0;
		for (np = nodep->child; np != NULL; np = np->peer)
			totalsize += np->size;
		nodep->size = totalsize;
	}

	/* for each child */
	for (np = nodep->child; np != NULL; np = np->peer) {
		fractsize = np->size / (double)totalsize;
		height = fractsize * totalheight + 0.5;
		if (height > 1) {
			struct rect subrect;
			/*printf("%s, drawrect[%d,%d,%d,%d]\n", np->name,
				rect.left,top,rect.width,height);*/
			xdrawrect(np->name, np->size,
				rect.left,top,rect.width,height);

			/* save current screen rectangle for lookups */
			np->rect.left = rect.left;
			np->rect.top = top;
			np->rect.width = rect.width;
			np->rect.height = height;

			/* draw children in subrectangle */
			subrect.left = rect.left+rect.width;
			subrect.top = top;
			subrect.width = rect.width;
			subrect.height = height;
			drawchildren(np, subrect);

			top += height;
		}
	}
}

/*
 * clear the rectangle information of a given node
 * and all of its decendents
 */
void
clearrects(struct node *nodep)
{
	struct	node	*np;

	if (nodep == NODE_NULL)
		return;

	nodep->rect.left = 0;
	nodep->rect.top = 0;
	nodep->rect.width = 0;
	nodep->rect.height = 0;

	/* for each child */
	for (np = nodep->child; np != NULL; np = np->peer) {
		clearrects(np);
	}
}

void
pwd(void)
{
	struct node *np;
	struct node *stack[MAXDEPTH];
	int num = 0;
	struct node *rootp;
	char path[MAXPATH];

	rootp = &top;
	if (numchildren(rootp) == 1)
		rootp = rootp->child;

	np = topp;
	while (np != NODE_NULL) {
		stack[num++] = np;
		if (np == rootp)
			break;
		np = np->parent;
	}

	path[0] = '\0';
	while (--num >= 0) {
		strcat(path,stack[num]->name);
		if (num != 0)
			strcat(path,"/");
	}
	printf("%s %jd (%.2f%%)\n", path, (intmax_t)topp->size,
		100.0*topp->size/rootp->size);
}

/**************** External Entry Points ****************/

void
press(int x, int y)
{
	struct node *np;

	/*printf("press(%d,%d)...\n",x,y);*/
	np = findnode(&top,x,y);
	/*printf("Found \"%s\"\n", np?np->name:"(null)");*/
	if (np == topp) {
		/* already top, go up if possible */
		if (np->parent != &top || numchildren(&top) != 1)
			np = np->parent;
		/*printf("Already top, parent = \"%s\"\n", np?np->name:"(null)");*/
	}
	if (np != NODE_NULL) {
		topp = np;
		xrepaint();
	}
}

void
reset(void)
{
	topp = &top;
	if (numchildren(topp) == 1)
		topp = topp->child;
	xrepaint();
}

void
repaint(int width, int height)
{
	struct	rect rect;

	/* define a rectangle to draw into */
	rect.top = 0;
	rect.left = 0;
	rect.width = width/ncols;
	rect.height = height;

	clearrects(&top);	/* clear current rectangle info */
	drawnode(topp,rect);	/* draw tree into given rectangle */
#if 0
	pwd();			/* display current path */
#endif
}

void
setorder(char *op)
{
	if (strcmp(op, "size") == 0) {
		order = ORD_SIZE;
	} else if (strcmp(op, "rsize") == 0) {
		order = ORD_RSIZE;
	} else if (strcmp(op, "alpha") == 0) {
		order = ORD_ALPHA;
	} else if (strcmp(op, "ralpha") == 0) {
		order = ORD_RALPHA;
	} else if (strcmp(op, "first") == 0) {
		order = ORD_FIRST;
	} else if (strcmp(op, "last") == 0) {
		order = ORD_LAST;
	} else if (strcmp(op, "reverse") == 0) {
		switch (order) {
		case ORD_ALPHA:
			order = ORD_RALPHA;
			break;
		case ORD_RALPHA:
			order = ORD_ALPHA;
			break;
		case ORD_SIZE:
			order = ORD_RSIZE;
			break;
		case ORD_RSIZE:
			order = ORD_SIZE;
			break;
		case ORD_FIRST:
			order = ORD_LAST;
			break;
		case ORD_LAST:
			order = ORD_FIRST;
			break;
		}
	} else {
		fprintf(stderr, "xdu: bad order \"%s\"\n", op);
	}
}

void
reorder(
    char *op	/* order name */
)
{
	setorder(op);
	sorttree(topp, order);
	xrepaint();
}

void
nodeinfo(void)
{
	struct node *np;

	/* display current root path */
	pwd();

	/* display each child of this node */
	for (np = topp->child; np != NULL; np = np->peer) {
		printf("%-8ld %s\n", np->size, np->name);
	}
}

void
helpinfo(void)
{
	fprintf(stdout, "\n\
XDU Version %s - Keyboard Commands\n\
  a  sort alphabetically\n\
  n  sort numerically (largest first)\n\
  f  sort first-in-first-out\n\
  l  sort last-in-first-out\n\
  r  reverse sort\n\
  /  goto the root\n\
  q  quit (also Escape)\n\
  i  info to standard out\n\
0-9  set number of columns (0=10)\n\
", XDU_VERSION);
}