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

char* cmdname;

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

struct Candidate {
   char* pathname;
   off_t size;
   struct Candidate* next;
};

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

typedef struct Hogs {
   struct Candidate* candidates; /* sorted, smallest 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 = 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->candidates->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->candidates;
      while (p && size >= p->size) {
	 last = p; p = p->next;
      }
      member->next = p;
      if (last) {
	 last->next = member;
      } else {
	 hogs->candidates = member;
      }
      ++hogs->filled;
      if (hogs->filled > hogs->wanted) {
	 struct Candidate* member = hogs->candidates;
	 hogs->candidates = hogs->candidates->next;
	 --hogs->filled;
	 free(member->pathname); free(member);
      }
   }
}

int main(int argc, char** argv) {
   cmdname = *argv++; --argc;
   const char* dirpath = ".";
   if (argc > 0) {
      dirpath = *argv++; --argc;
   }
   if (argc != 0) usage();

   Hogs hogs = {
      .candidates = 0,
      .head = 0, .tail = 0,
      .wanted = 10, .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);
   }

   for (struct Candidate* member = hogs.candidates; member;
	 member = member->next) {
      printf("%10d %s\n", member->size, member->pathname);
   }
}