#include <dirent.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>

const char* cmdname; // argv[0] of main()

void usage() {
   fprintf(stderr, "Usage: %s [-N] [dir]\n", cmdname);
   exit(1);
}

struct Candidate {
   char* pathname;
   off_t size;
   struct Candidate* next; // next candidate with a size >= our size
   struct Candidate* prev; // next candidate with a size <= our size
};

void nomem() {
   fprintf(stderr, "%s: out of memory.\n", cmdname); exit(1);
}

typedef struct Hogs {
   struct Candidate* smallest; /* sorted, smallest first */
   struct Candidate* largest; /* sorted, largest first */
   struct Candidate* head; struct Candidate* tail; // queue
   unsigned int wanted; // maximal number of candidates
   unsigned int filled; // number of elements in candidates
} Hogs;

void add_directory(struct Hogs* hogs, const char* dirpath) {
   struct Candidate* member = malloc(sizeof(struct Candidate));
   if (!member) nomem();
   member->pathname = strdup(dirpath); member->size = 0;
   member->next = member->prev = 0;
   if (hogs->head) {
      hogs->tail->next = member;
   } else {
      hogs->head = member;
   }
   hogs->tail = member;
}

void add_file(struct Hogs* hogs, const char* pathname, off_t size) {
   if (hogs->filled < hogs->wanted || size > hogs->smallest->size) {
      struct Candidate* member = malloc(sizeof(struct Candidate));
      if (!member) nomem();
      member->pathname = strdup(pathname); member->size = size;
      struct Candidate* last = 0; struct Candidate* p = hogs->smallest;
      while (p && size >= p->size) {
	 last = p; p = p->next;
      }
      member->next = p; member->prev = last;
      if (last) {
	 last->next = member;
      } else {
	 hogs->smallest = member;
      }
      if (p) {
	 p->prev = member;
      } else {
	 hogs->largest = member;
      }
      ++hogs->filled;
      if (hogs->filled > hogs->wanted) {
	 struct Candidate* member = hogs->smallest;
	 hogs->smallest = hogs->smallest->next;
	 hogs->smallest->prev = 0;
	 --hogs->filled;
	 free(member->pathname); free(member);
      }
   }
}

void free_hogs(struct Hogs* hogs) {
   struct Candidate* member = hogs->smallest;
   while (member) {
      struct Candidate* old = member; member = member->next;
      free(old->pathname); free(old);
   }
   hogs->smallest = hogs->largest = 0;
}

int main(int argc, char** argv) {
   cmdname = *argv++; --argc;
   const char* cp = strrchr(cmdname, '/');
   if (cp) cmdname = cp + 1; // strip to basename

   unsigned int wanted = 10;
   if (argc > 0 && **argv == '-') {
      int intval = atoi(*argv + 1);
      if (intval <= 0) usage();
      wanted = intval;
      ++argv; --argc;
   }
   const char* dirpath = ".";
   if (argc > 0) {
      dirpath = *argv++; --argc;
   }
   if (argc != 0) usage();

   Hogs hogs = {
      .smallest = 0, .largest = 0,
      .head = 0, .tail = 0,
      .wanted = wanted, .filled = 0,
   };

   add_directory(&hogs, dirpath);
   while (hogs.head) {
      struct Candidate* member = hogs.head;
      hogs.head = member->next;
      if (hogs.head == 0) {
	 hogs.tail = 0;
      }

      DIR* dir = opendir(member->pathname);
      if (!dir) {
	 perror(member->pathname); continue;
      }
      size_t pathlen = strlen(member->pathname);
      struct dirent* dirent;
      while ((dirent = readdir(dir))) {
	 if (strcmp(dirent->d_name, ".") == 0) continue;
	 if (strcmp(dirent->d_name, "..") == 0) continue;
	 char* path = malloc(pathlen + strlen(dirent->d_name) + 2);
	 if (!path) nomem();
	 strcpy(path, member->pathname);
	 strcat(path, "/"); strcat(path, dirent->d_name);

	 struct stat statbuf;
	 if (lstat(path, &statbuf) < 0) {
	    perror(path); free(path); continue;
	 }
	 if (S_ISDIR(statbuf.st_mode)) {
	    add_directory(&hogs, path);
	 } else if (S_ISREG(statbuf.st_mode)) {
	    add_file(&hogs, path, statbuf.st_size);
	 }
	 free(path);
      }
      closedir(dir);
      free(member->pathname); free(member);
   }

   for (struct Candidate* member = hogs.largest; member;
	 member = member->prev) {
      printf("%10jd %s\n", (intmax_t) member->size, member->pathname);
   }
   free_hogs(&hogs);
}