/*
** sort.c in /home/wapiflapi/Projects/misc/gruik/
**
** Made by Wannes Rombouts
** Login   <rombou_w@epitech.eu>
**
** Started on  Wed Jun  4 15:12:23 2014 Wannes Rombouts
** Last update Wed Jun  4 17:55:28 2014 Wannes Rombouts
*/

#include    <unistd.h>
#include    <stdlib.h>
#include    <stdio.h>
#include    <string.h>
#include    <fcntl.h>
#include    <err.h>
#include    <sys/mman.h>
#include    <sys/stat.h>

struct entry {
  char const    *text;
  size_t    size;
  unsigned int  val;
};

static void process_file(char const *data, size_t size)
{
  struct entry  *array;
  size_t    asize;
  size_t    afill;

  afill = 0;
  asize = 32;
  if (!(array = calloc(asize, sizeof *array)))
    err(EXIT_FAILURE, "malloc");

  data = data;
  size = size;

  while (size > 0)
    {
      char const *nextn;
      unsigned int nb;

      if (!(nextn = memchr(data, '\n', size)))
    nextn = data + size;
      size -= nextn - data;

      /*
      ** Carefull, nextn might not be mapped if no terminating \n.
      */

      if (nextn > data)
    {
      if (afill == asize)
        {
          /*
          ** Should check overflows here but I'm lazy.
          */
          asize *= 2;
          if (!(array = realloc(array, asize * sizeof *array)))
        err(EXIT_FAILURE, "realloc");
        }

      array[afill].text = data;
      array[afill].size = nextn - data;

      /*
      ** Assume positive numbers.
      */

      for (nb = 0; '0' <= *data && *data <= '9'; ++data)
        nb = nb * 10 + *data - '0';
      array[afill].val = nb;

      afill += 1;
    }
      else
    {
      /*
      ** Group change: sort & print.
      ** Not using quick sort because it is not faster
      ** than insertion sort for sorting small sets.
      ** libc's implementation is slow anyway, probably
      ** due to all the function calls that can't be inlined.
      */

      int i, j;
      struct entry x;

      for (i = 1; i < afill; ++i)
        {
          x = array[i];
          for (j = i; j > 0 && array[j-1].val > x.val; --j)
        array[j] = array[j-1];
          array[j] = x;
        }

      for (i = 0; i < afill; ++i)
        fwrite(array[i].text, 1, array[i].size + 1, stdout);
      fputc('\n', stdout);

      afill = 0;
    }

      data = nextn + 1;
      size -= 1;
    }

  free(array);
}

int     main(int argc, char **argv)
{
  int       fd;
  void      *data;
  struct stat   sbuf;

  if (argc < 2)
    errx(EXIT_FAILURE, "Usage: %s data_file", argv[0]);

  if ((fd = open(argv[1], O_RDONLY)) < 0)
    err(EXIT_FAILURE, "open");

  if (fstat(fd, &sbuf) < 0)
    err(EXIT_FAILURE, "fstat");

  if (sbuf.st_size)
    {
      if ((data = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE,
               fd, 0)) == MAP_FAILED)
    err(EXIT_FAILURE, "mmap");

      process_file(data, sbuf.st_size);

      munmap(data, sbuf.st_size);
    }

  close(fd);

  return 0;
}