#include <windows.h>
#include <stdio.h>
#include <assert.h>

/* #define DEBUG */
#if defined(DEBUG)
#include "xmalloc.h"

#define ERROR_COUNT 8
void *zmalloc(size_t n, int id) {
  void *p;
  static int count = 0;
  if (count++ >= ERROR_COUNT)
    return 0;
#undef ERROR_COUNT
  p = xmalloc(n, id);
  return p;
}

void zfree(void *p, int id) {
  xfree(p, id);
}

#else
#define zmalloc(x, y) malloc(x)
#define zfree(x, y) free(x)
#define xmallocdump()
#endif

#define ID_NODE  1001
#define FILEPATH 1002
#define MASKPATH 1003
#define TREEDATA 1004

/********************************************/
/* for CP932/Shift-JIS */
int isHasSecondByte(int c) {
  if (c >= 0x81 && c <= 0x9f)
    return 1;
  if (c >= 0xe0 && c <= 0xfc)
    return 1;
  return 0;
}

int getLastChar(char *path) {
  int rc;
  char *p;
  int flagHasSecondByte;
  for (p = path, flagHasSecondByte = 0; *p; p++) {
    if (!flagHasSecondByte) {
      rc = (rc << 8) & *p;
      flagHasSecondByte = 0;
    } else { /* is SecondByte */
      flagHasSecondByte = isHasSecondByte(*p);
      rc = *p;
    }
  }
  return rc;
}
/********************************************/

struct node {
  void *data;
  int c;
  struct node *left, *right;
};

void *push(struct node **root, void *data, int (*cmp)(void *, void *)) {
  struct node *p;
  if (!*root) {
    if ((p = zmalloc(sizeof(struct node), ID_NODE)) == NULL) {
      fprintf(stderr, "push: cannot allocate enough memory.(struct node), aborted\n");
      return 0;
    }
    p->data = data;
    p->left = p->right = NULL;
    *root = p;
    return data;
  } 
  if ((*cmp)(data, (*root)->data) < 0) {
    return push(&((*root)->left), data, cmp);
  } else {
    return push(&((*root)->right), data, cmp);
  }
}

void *pop(struct node **root) {
  struct node *p;
  void *data;
  if (*root == NULL) {
    return NULL;
  }
  if ((*root)->left) {
    data = pop(&((*root)->left));
    return data;
  }
  p = *root;
  data = p->data;
  *root = p->right;
  zfree(p, ID_NODE);
  return data;
}

/*--------------------------------------------------------------------*/
char *mallocStrCat(char *s1, char *s2, int id) {
  int n1, n2;
  char *c;
  n1 = strlen(s1);
  n2 = strlen(s2);
  if ((c = zmalloc(n1 + n2 + 1, id)) == 0)
    return 0;
  strcpy(c, s1);
  strcpy(c + n1, s2);
  return c;
}

char *mallocPathCat(char *dir, char *file, int id) {
  char *s1, *s2;
  int last;
  last = getLastChar(dir);
  if (last != '\\') {
    s1 = mallocStrCat(dir, "\\", id);
    if (s1 == 0)
      return 0;
  } else {
    s1 = dir;
  }
  s2 = mallocStrCat(s1, file, id);
  zfree(s1, id);
  if (s2 == 0)
    return 0;
  return s2;
}

char *mallocReplicaPath(char *path, int id) {
  char *rc;
  if ((rc = zmalloc(strlen(path) + 1, id)) != 0)
    strcpy(rc, path);
  return rc;
}

/*--------------------------------------------------------------------*/
struct filedata {
  unsigned int size;
  char *filename;
};

int comp(struct filedata *a, struct filedata *b) {
  if (a->size > b->size)
    return -1;
  if (a->size < b->size)
    return 1;
  assert(a->size == b->size);
  return strcmp(a->filename, b->filename);
}

/*--------------------------------------------------------------------*/
int task_digging(struct node **root, char *searchpath) {
  HANDLE hFileDigging;
  WIN32_FIND_DATA systemFindData;
  char *searchmask, *t;
  char *nextPath;
  struct filedata *filedataSizeName;

  hFileDigging = INVALID_HANDLE_VALUE;
  filedataSizeName = 0;
  searchmask = nextPath = 0;

  searchmask = mallocReplicaPath(searchpath, MASKPATH);
  if (searchmask == 0) {
    fprintf(stderr, "task_digging: memory full.<1>\n");
    goto error_handler;
  }
  if ((t = mallocPathCat(searchmask, "*.*", MASKPATH)) == 0) {
    fprintf(stderr, "task_digging: memory full.<2>\n");
    goto error_handler;
  }
  zfree(searchmask, MASKPATH);
  searchmask = t;

  if ((hFileDigging = FindFirstFile(searchmask, &systemFindData)) == INVALID_HANDLE_VALUE) {
    fprintf(stderr, "task_digging: returned invalid handle. <3>\n");
    goto error_handler;
  }
  do {
    if (strcmp(systemFindData.cFileName, ".") == 0)
      continue;
    if (strcmp(systemFindData.cFileName, "..") == 0)
      continue;

    nextPath = mallocReplicaPath(searchpath, FILEPATH);
    if (nextPath == 0) {
      fprintf(stderr, "task_digging: memory full.<4>\n");
      goto error_handler;
    }
    if ((t = mallocPathCat(nextPath, systemFindData.cFileName, FILEPATH)) == 0) {
      fprintf(stderr, "task_digging: memory full.<5>\n");
      goto error_handler;
    }
    zfree(nextPath, FILEPATH);
    nextPath = t;

    /* directory */
    if (systemFindData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) {
      if (!task_digging(root, nextPath)) {
        fprintf(stderr, "task_digging: recursion failure. <6>, pos: %s\n", nextPath);
        goto error_handler;
      }
      zfree(nextPath, FILEPATH);
    } else {

      /* file */
      if ((filedataSizeName = zmalloc(sizeof(struct filedata), TREEDATA)) == 0) {
        fprintf(stderr, "task_digging: pos:%s/%s, recursion failure.<7>\n", searchpath, nextPath);
        goto error_handler;
      }
      filedataSizeName->size = systemFindData.nFileSizeLow;
      filedataSizeName->filename = nextPath;
      if (push(root, filedataSizeName, (int (*)(void *, void *))comp) == 0) {
        fprintf(stderr, "task_digging: pos:%s/%s, recursion failure.<8>\n", searchpath, nextPath);
        goto error_handler;
      }
      filedataSizeName = 0;
      nextPath = 0;
    }
  } while (FindNextFile(hFileDigging, &systemFindData)); 
  zfree(searchmask, MASKPATH);
  FindClose(hFileDigging);
  return 1;

error_handler:
  zfree(searchmask, MASKPATH);
  zfree(nextPath, FILEPATH);
  zfree(filedataSizeName, TREEDATA);
  FindClose(hFileDigging);
  return 0;
}

#define OUTPUT_FILE_NUM 100
void task_vomitting(struct node **root, int init_n) {
  struct filedata *p;
  int n;

  n = init_n;
  while ((p = pop(root)) != 0) {
    if (n < OUTPUT_FILE_NUM) {
      printf("%9d: %s\n", p->size, p->filename);
      n++;
    }
    zfree(p->filename, FILEPATH);
    zfree(p, TREEDATA);
  }
}

/*--------------------------------------------------------------------*/
int task_main(char *dir) {
  struct node *root;
  char *searchpath;
  int err;

  root = 0;
  searchpath = 0;
  err = 0;

  if ((searchpath = zmalloc(strlen(dir) + 1, FILEPATH)) == 0)
    goto error_handler;
  
  strcpy(searchpath, dir);
  if (!task_digging(&root, searchpath))
    err = 1;
  putchar('\n');
  task_vomitting(&root, 0);
  zfree(searchpath, FILEPATH);
  if (!err)
    return 1;

error_handler:
  fprintf(stderr, "task_main: terminated with abnomality<9>\n");
  return 0;
}

int main(int argc, char *argv[]) {
  if (argc == 2) {
    if(!task_main(argv[1]))
      goto error;
  } else {
  error:
    fprintf(stderr, "usage: %s <dir>\n", argv[0]);
    xmallocdump();
    return 1;
  }
  xmallocdump();
  return 0;
}

/* end */