/* Sorts the output of "du" in preorder and formats its succintly */
/* See the copyright notice at the end of this file. */


#include <string.h>
#include <stdlib.h>
#include <stdio.h>

typedef int bool;
#define TRUE 1
#define FALSE 0

#define	PATH_MAX 1024 /* max characters in a pathname */

typedef struct DirNode *DirList;

typedef struct DirNode {
    char *name;         /* Node name, a component of a pathname */
    int size;           /* Size of this node, as given by "du" */
    DirList children;   /* Children of this node */
    DirList rest;       /* Next sibling of this node */
  } DirNode;
  
/* PROTOTYPES */

int main(int argc, char **argv);

void readname(char *name, long maxlen);
  /*
    Reads a pathname from "stdin", skipping initial blanks, until
    end-of-line.  Complains if there are more than "maxlen" characters
    in the pathname.  Stores the pathanme into "*name",
    null-terminated. */
    
void addfile(DirList *rootp, char *name, long size);
  /* 
    Finds a node for the file whose pathname is "*name",
    in the file tree whose root is **rootp. 
    Increments the "size" field of that node by the given value. 
    The node (and any intermediate nodes) are created as needed, 
    with zero size field. */
  
int complength (char *name);
  /* 
    Returns the length of the first component of "name", up to 
    the first "/" or NUL. */

bool samename(char *cname, int clen, char *nname);
  /* 
    Returns TRUE iff the substring "cname[0..clen-1]" matches 
    the null-terminated string "*nname". */

void sortfiles(DirList *rootp);
  /*
    Sorts the file tree recursively by decreasing "size" field. */

DirList sortlist(DirList p);
  /*
    Sorts the top-level of list "p" by decreasing size. */

void printfiles(DirList p);
  /*
    Prints the sorted directory tree, replacing parent names 
    by ". ". */

long listlength(DirList p);
/* 
  Number of entries in list, i.e. min "k" such that 
  "p->rest^k = NULL". */

void error (char *msg);
  /* 
    Prints string $*msg$ to $stderr$ and stops. */

void programerror (char *msg, char *file, unsigned int line, char* proc);
  /* 
    Prints string $file:line: (*proc) *msg$ to $stderr$ and stops. */

#define assert(test, msg) \
  { if (!(test)) programerror((msg), __FILE__, __LINE__, __FUNCTION__); }
  /* 
    If test is false, prints $*msg$ and stops.
    It is declared as a mscro, rather than as a procedure, 
    in order to avoid evaluating $msg$ when $test$ is true.  */

/* IMPLEMENTATIONS */

int main(int argc, char **argv)
  {
    DirList root = NULL;
    long size;
    int res;
    char *name = ((char*) malloc(PATH_MAX + 1));
    assert(argc == 1, "this program takes no parameters");
    while (TRUE) 
      {
        res = scanf("%ld", &size);
        if (res == EOF) break;
        readname(name, PATH_MAX);
        addfile(&root, name, size);
      }
    /* DEBUG: printfiles(root); */
    sortfiles(&root);
    printfiles(root);
    fclose(stdout);
    return 0;
  }

void readname(char *name, long maxlen)
  {
    long k = 0;
    char c;
    do 
      { c = getchar(); if (c == EOF) error("unexpected EOF"); } 
    while ((c == ' ') || (c == '\t'));
    while (c != '\n')
      {
        if (k >= maxlen) 
          error("file name too long");
        if ((c == ' ') || (c == '\t') || (c == '\r') || (c == '\f')) 
          error("embedded blanks in file name");
        name[k] = c; k++;
        c = getchar();
      }
    name[k] = '\0';
  }
  
void addfile(DirList *rootp, char *name, long size)
  {
    DirList *fatherp = rootp;
    DirList this;
    int cstart = 0;
    assert(rootp != NULL, "bad rootp");
    while (TRUE)
      {
        int clen = complength(&(name[cstart]));
        this = (*fatherp);
        while ((this != NULL) && (! (samename(&(name[cstart]), clen, this->name))))
          { this = this->rest; }
        if (this == NULL)
          { /* Insert a new node: */
            this = (DirNode *)malloc(sizeof(DirNode));
            this->name = (char *) malloc(clen + 1);
            strncpy(this->name, &(name[cstart]), clen);
            this->name[clen] = '\0';
            this->size = 0;
            this->children = NULL;
            this->rest = (*fatherp);
            (*fatherp) = this;
          }
        cstart += clen;
        if (name[cstart] == '\0')
          { /* Found record of entry */
            this->size = size;
            return;
          }
        cstart++;
        fatherp = &(this->children);
      }
  }

int complength (char *name)
  {
    int k = 0;
    while((name[k] != '\0') && (name[k] != '/')) k++;
    return k;
  }

bool samename(char *cname, int clen, char *nname)
  {
    int k = 0;
    while((k < clen) && (nname[k] != '\0'))
      { if (cname[k] != nname[k]) return(FALSE);
        k++;
      }
    return((k == clen) & (nname[k] == '\0'));
  }

void sortfiles(DirList *rootp)
  {
    DirList p;
    int top = -1;
    DirList stack[PATH_MAX];
    (*rootp) = sortlist(*rootp);
    p = (*rootp);
    /* "p" and "stack[0..top]" are sorted lists whose children need to be sorted. */
    while (p != NULL)
      {
        if (p->rest != NULL) 
          { top++; stack[top] = p->rest; }
        /* DEBUG: fprintf(stderr,                        */
        /* DEBUG:   "sort %s's children (%ld items)\n",  */
        /* DEBUG:   p->name, listlength(p->children)     */
        /* DEBUG: );                                     */
        p->children = sortlist(p->children);
        p = p->children;
        if ((p == NULL) && (top >= 0))
          { p = stack[top]; top--; }
      }
  }
          
DirList sortlist(DirList p)
  {  
    if ((p != NULL) && (p->rest != NULL))
      {
        DirList e = NULL; DirList o = NULL;
        /* Split even/odd, sort each, merge: */
        while (p != NULL) { DirList t = p->rest; p->rest = e; e = o; o = p; p = t; }
        e = sortlist(e); o = sortlist(o);
        { DirList *lastp = &p;
          while ((e != NULL) && (o != NULL))
            { DirList *thisp = ((e->size) >= (o->size) ? &e : &o);
              (*lastp) = (*thisp); lastp = &((*thisp)->rest); (*thisp) = (*lastp);
            }
          (*lastp) = (e != NULL ? e : o);
        }
      }
    return p;
  }
  
void printfiles(DirList p)
  {
    int top = -1;
    DirList stack[PATH_MAX];
    /* "stack[0..top]" are the ancestral directories of "p". */
    while (p != NULL)
      { int k;
        printf("%10d ", p->size);
        for(k=0; k<=top; k++) printf(". ");
        printf("%s", p->name);
        if (p->children != NULL) printf("/");
        printf("\n");
        top++; stack[top] = p; p = p->children; 
        while ((p == NULL) && (top >= 0))
          { p = (stack[top])->rest; top--; }
      }
  }
  
long listlength(DirList p)
{
  long k = 0;
  while (p != NULL) { k++; p = p->rest; }
  return k;
}

void error (char *msg)
  { fprintf (stderr, "*** %s\n", msg);
    exit(1);
  }
  
void programerror (char *msg, char *file, unsigned int line, char* proc)
  { fprintf (stderr, "*** %s:%u: (%s) %s\n", file, line, proc, msg);
    exit(1);
  }

/*
** Copyright notice:
**
** Copyright 1996 Institute of Computing, Unicamp.
**
** Permission to use this software for any purpose is hereby granted,
** provided that any substantial copy or mechanically derived version
** of this file that is made available to other parties is accompanied
** by this copyright notice in full, and is distributed under these same
** terms. 
**
** DISCLAIMER: This software is provided "as is" with no explicit or
** implicit warranty of any kind.  Neither the authors nor their
** employers can be held responsible for any losses or damages
** that might be attributed to its use.
**
** End of copyright notice.
*/