/*
 * Copyright info: this file is in the public domain.
 *
 * Work with file times.
 *
 * By default, reads pathnames from stdin and just echos them to stdout
 *  with the mtime of each file prepended to its line, formatted as a
 *  simple decimal number, a la strftime(3)'s %s format, with one space
 *  between the timestamp and the pathname.
 *
 * -h
 * -H
 *	Follow (-h) or don't follow (-H) symbolic links - this
 *	corresponds to using stat(2) versus lstat(2).  The default is -h.
 *
 * -newest n
 *	Drops all but the n newest files.
 *
 * -oldest n
 *	Drops all but the n oldest files.
 *
 * -mtime
 * -atime
 * -ctime
 *	Use the indicated timestamp.  (-mtime is the default; it is
 *	provided to permit overriding an earlier -atime or -ctime.)
 *
 * -0
 *	Pathnames are terminated with \0 rather than \n, for both input
 *	and output.
 *
 * -i0
 *	Like -0 but affects input only.
 *
 * -o0
 *	Like -0 but affects output only.
 *
 * -fmt f
 *	Format times using f as a format string to strftime(3).  Note
 *	that nothing is provided between the format string and the
 *	pathname; if you want a separator there, provide it in the
 *	format.  A zero-length argument can be used to effectively
 *	suppress the timestamps entirely.  -fmt "%s " is the default.
 *
 * -fail how
 *	How to handle paths for which stat/lstat fails.  how can be
 *
 *	drop
 *		Silently drop them entirely, as if they didn't appear
 *		in the input at all.
 *	warn
 *		Drop them, but print a warning for each one.
 *	zero
 *		Treat them as having zero timestamps.
 *
 *	The default is warn.
 *
 * -sort how
 *	How to sort the output.  how can be
 *
 *	name
 *		Sort by pathname, using naïve strcmp() comparison.
 *	basename
 *		Sort by the portion of the pathname after the last
 *		slash.  Ties are broken based on `name' sorting.
 *	time
 *		Sort by timestamp, oldest first.
 *	input
 *		Output order equals input order.
 *
 *	Any of these (yes, even input) can be prefixed with "r-" to
 *	reverse the resulting sort order.  The default is input.
 *
 * -dump
 *	This is designed for use with -restore.  It overrides -fmt and
 *	-atime/-mtime/-ctime.  It is like a version of -fmt that (a)
 *	preserves sub-second precision and (b) encapsulates both mtime
 *	and atime.  The details of the timestamp encoding are not
 *	documented; they are private between -dump and -restore and are
 *	not a supported external interface.  The encoding is, however,
 *	promised to be portable between machines of different
 *	endianness or word size, and does not use any characters which
 *	are not printable ASCII (the output may include such
 *	characters, but only in the pathnames themselves); it also
 *	appears entirely before the pathname.  -dump mode effectively
 *	forces -H, pays attention to -fail and -0/-o0, and is
 *	incompatible with -restore, but ignores other options.
 *
 * -restore
 *	This reads pathnames from stdin, as usual, except that each
 *	pathname is prefixed by timestamp information produced -dump.
 *	The timestamps are restored to the files.  This pays attention
 *	to -0/-i0 and is incompatible with -dump, but ignores other
 *	options.  It never follows symlinks, using lutimes(2) rather
 *	than utimes(2), and errors (such as ENOENT) from setting the
 *	time are always reported.
 *
 * When any sort order other than input, or -newest or -oldest, is
 *  used, no output can be produced until all input has been read.
 *
 * If the last pathname is partial - that is, if there is input but it
 *  does not end with the appropriate input terminator - a warning is
 *  printed and a terminator is effectively supplied.
 *
 * With -newest and -oldest, if the cutoff falls partway through a
 *  group of files with equal timestamps, no promises are made about
 *  which ones get kept.
 */

#include <time.h>
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <strings.h>
#include <sys/stat.h>
#include <sys/time.h>

extern const char *__progname;

typedef enum {
	  OPMODE_NORMAL = 1,
	  OPMODE_DUMP,
	  OPMODE_RESTORE
	  } OPMODE;

typedef enum {
	  SORT_INPUT = 1,
	  SORT_TIME,
	  SORT_NAME,
	  SORT_BASENAME
	  } SORTORDER;

typedef enum {
	  TK_MTIME = 1,
	  TK_ATIME,
	  TK_CTIME
	  } TIMEKIND;

typedef enum {
	  FAIL_DROP = 1,
	  FAIL_WARN,
	  FAIL_ZERO
	  } FAILHOW;

typedef enum {
	  SFN_STAT = 1,
	  SFN_LSTAT
	  } STATFN;

static OPMODE opmode = OPMODE_NORMAL;
static STATFN statfn = SFN_STAT;
static int newest = 0;
static int oldest = 0;
static TIMEKIND timekind = TK_MTIME;
static char iterm = '\n';
static char oterm = '\n';
static const char *fmt = "%s ";
static FAILHOW failhow = FAIL_WARN;
static SORTORDER order = SORT_INPUT;
static int revorder = 0;

typedef unsigned long long int SERIAL;

typedef struct f F;
typedef struct dll DLL;
typedef struct sll SLL;

struct f {
  time_t stamp;
  char *path;
  char *base;
  SERIAL serial;
  } ;

struct dll {
  DLL *flink;
  DLL *blink;
  F f;
  } ;

struct sll {
  SLL *link;
  F f;
  } ;

static DLL *timelist;
static int timen;
static int timemax;
static SLL *filelist;
static SERIAL serial = 0;

#define DUMP_BASE 69
static const char dumpdig[DUMP_BASE]
 = "_%+-,./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

static int set_sort(const char *arg)
{
 if (!strncmp(arg,"r-",2))
  { revorder = 1;
    arg += 2;
  }
 else
  { revorder = 0;
  }
 if (!strcmp(arg,"name"))
  { order = SORT_NAME;
  }
 else if (!strcmp(arg,"basename"))
  { order = SORT_BASENAME;
  }
 else if (!strcmp(arg,"time"))
  { order = SORT_TIME;
  }
 else if (!strcmp(arg,"input"))
  { order = SORT_INPUT;
  }
 else
  { fprintf(stderr,"%s: unrecognized sort order `%s'\n",__progname,arg);
    return(1);
  }
 return(0);
}

static int set_fail(const char *arg)
{
 if (!strcmp(arg,"drop"))
  { failhow = FAIL_DROP;
  }
 else if (!strcmp(arg,"warn"))
  { failhow = FAIL_WARN;
  }
 else if (!strcmp(arg,"zero"))
  { failhow = FAIL_ZERO;
  }
 else
  { fprintf(stderr,"%s: unrecognized fail action `%s'\n",__progname,arg);
    return(1);
  }
 return(0);
}

static int set_dump(void)
{
 switch (opmode)
  { case OPMODE_NORMAL:
       opmode = OPMODE_DUMP;
       break;
    case OPMODE_DUMP:
       break;
    case OPMODE_RESTORE:
       fprintf(stderr,"%s: -dump is incompatible with -restore\n",__progname);
       return(1);
       break;
    default:
       abort();
       break;
  }
 return(0);
}

static int set_restore(void)
{
 switch (opmode)
  { case OPMODE_NORMAL:
       opmode = OPMODE_RESTORE;
       break;
    case OPMODE_RESTORE:
       break;
    case OPMODE_DUMP:
       fprintf(stderr,"%s: -restore is incompatible with -dump\n",__progname);
       return(1);
       break;
    default:
       abort();
       break;
  }
 return(0);
}

static void handleargs(int ac, char **av)
{
 int skip;
 int errs;

 skip = 0;
 errs = 0;
 for (ac--,av++;ac;ac--,av++)
  { if (skip > 0)
     { skip --;
       continue;
     }
    if (**av != '-')
     { fprintf(stderr,"%s: stray argument `%s'\n",__progname,*av);
       errs = 1;
       continue;
     }
    if (0)
     {
needarg:;
       fprintf(stderr,"%s: %s needs a following argument\n",__progname,*av);
       errs = 1;
       continue;
     }
#define WANTARG() do { if (++skip >= ac) goto needarg; } while (0)
    if (!strcmp(*av,"-h"))
     { statfn = SFN_STAT;
     }
    else if (!strcmp(*av,"-H"))
     { statfn = SFN_LSTAT;
     }
    else if (!strcmp(*av,"-newest"))
     { WANTARG();
       oldest = 0;
       newest = atoi(av[skip]);
     }
    else if (!strcmp(*av,"-oldest"))
     { WANTARG();
       newest = 0;
       oldest = atoi(av[skip]);
     }
    else if (!strcmp(*av,"-mtime"))
     { timekind = TK_MTIME;
     }
    else if (!strcmp(*av,"-atime"))
     { timekind = TK_ATIME;
     }
    else if (!strcmp(*av,"-ctime"))
     { timekind = TK_CTIME;
     }
    else if (!strcmp(*av,"-0"))
     { iterm = '\0';
       oterm = '\0';
     }
    else if (!strcmp(*av,"-i0"))
     { iterm = '\0';
     }
    else if (!strcmp(*av,"-o0"))
     { oterm = '\0';
     }
    else if (!strcmp(*av,"-fmt"))
     { WANTARG();
       fmt = av[skip];
     }
    else if (!strcmp(*av,"-fail"))
     { WANTARG();
       errs |= set_fail(av[skip]);
     }
    else if (!strcmp(*av,"-sort"))
     { WANTARG();
       errs |= set_sort(av[skip]);
     }
    else if (!strcmp(*av,"-dump"))
     { errs |= set_dump();
     }
    else if (!strcmp(*av,"-restore"))
     { errs |= set_restore();
     }
    else
     { fprintf(stderr,"%s: unrecognized option `%s'\n",__progname,*av);
       errs = 1;
     }
#undef WANTARG
  }
 if (errs) exit(1);
}

static void setup(void)
{
 timelist = 0;
 timen = 0;
 if (newest) timemax = newest; else timemax = oldest;
 filelist = 0;
}

static void print_output(const char *path, time_t stamp)
{
 if (*fmt)
  { struct tm *tm;
    static char *ob = 0;
    static int ol = 0;
    int n;
    tm = localtime(&stamp);
    if (! ob)
     { ob = malloc(4);
       ol = 4;
     }
    while (1)
     { n = strftime(ob,ol,fmt,tm);
       if (n) break;
       ol += ol >> 1;
       free(ob);
       ob = malloc(ol);
     }
    fwrite(ob,1,n,stdout);
  }
 fputs(path,stdout);
 putchar(oterm);
}

static void input_line_normal(const char *l, int len, int slash)
{
 F *f;
 SLL *sll;
 DLL *dll;
 DLL *drop;
 struct stat stb;
 time_t stamp;
 int s;

 if (timemax)
  { dll = malloc(sizeof(DLL));
    f = &dll->f;
  }
 else
  { sll = malloc(sizeof(SLL));
    f = &sll->f;
  }
 switch (statfn)
  { case SFN_STAT:
       s = stat(l,&stb);
       break;
    case SFN_LSTAT:
       s = lstat(l,&stb);
       break;
    default:
       abort();
       break;
  }
 if (s < 0)
  { switch (failhow)
     { case FAIL_DROP:
	  return;
	  break;
       case FAIL_WARN:
	  fprintf(stderr,"%s: %s: %s\n",__progname,l,strerror(errno));
	  return;
	  break;
       case FAIL_ZERO:
	  stamp = 0;
	  break;
       default:
	  abort();
	  break;
     }
  }
 else
  { switch (timekind)
     { case TK_MTIME: stamp = stb.st_mtime; break;
       case TK_ATIME: stamp = stb.st_atime; break;
       case TK_CTIME: stamp = stb.st_ctime; break;
       default: abort(); break;
     }
  }
 if (!timemax && !revorder && (order == SORT_INPUT))
  { print_output(l,stamp);
    free(sll);
    return;
  }
 f->path = 0;
 f->serial = serial++;
 f->stamp = stamp;
 if (timemax)
  { dll->flink = timelist;
    dll->blink = 0;
    if (timelist) timelist->blink = dll;
    timelist = dll;
    if (timen < timemax)
     { timen ++;
     }
    else
     { drop = dll;
       for (dll=dll->flink;dll;dll=dll->flink)
	{ if ( newest ? (dll->f.stamp < drop->f.stamp)
		      : (dll->f.stamp > drop->f.stamp) ) drop = dll;
	}
       if (drop->flink) drop->flink->blink = drop->blink;
       if (drop->blink) drop->blink->flink = drop->flink; else timelist = drop->flink;
       if (f == &drop->f) f = 0;
       free(drop->f.path);
       free(drop);
     }
  }
 else
  { sll->link = filelist;
    filelist = sll;
  }
 if (f)
  { f->path = malloc(len);
    bcopy(l,f->path,len);
    if (slash < 0) f->base = f->path; else f->base = f->path + slash + 1;
  }
}

static void print_encoded_timespec(FILE *to, const struct timespec *ts)
{
 unsigned long long int t;
 int c;
 int s;

 t = (ts->tv_sec * 1000000000ULL) + ts->tv_nsec;
 s = 0;
 do
  { c = t % DUMP_BASE;
    s += c;
    putc(dumpdig[c],to);
    t /= DUMP_BASE;
  } while (t);
 putc(dumpdig[s%DUMP_BASE],to);
}

static void input_line_dump(const char *l)
{
 struct stat stb;
 int rv;

 rv = lstat(l,&stb);
 if (rv < 0)
  { switch (failhow)
     { case FAIL_DROP:
	  return;
	  break;
       case FAIL_WARN:
	  fprintf(stderr,"%s: %s: %s\n",__progname,l,strerror(errno));
	  return;
	  break;
       case FAIL_ZERO:
	  stb.st_atimespec.tv_sec = 0;
	  stb.st_atimespec.tv_nsec = 0;
	  stb.st_mtimespec.tv_sec = 0;
	  stb.st_mtimespec.tv_nsec = 0;
	  break;
       default:
	  abort();
	  break;
     }
  }
 print_encoded_timespec(stdout,&stb.st_atimespec);
 putchar('=');
 print_encoded_timespec(stdout,&stb.st_mtimespec);
 putchar(' ');
 fputs(l,stdout);
 putchar(oterm);
}

static const char *parse_encoded_timestamp(const char **cpp, struct timespec *ts)
{
 unsigned long long int t;
 unsigned long long int m;
 unsigned long long int lastt;
 const char *cp;
 void *xp;
 int x;
 int s;
 int lastx;
 int n;

 cp = *cpp;
 t = 0;
 m = 1;
 n = 0;
 s = 0;
 while (1)
  { xp = memchr(&dumpdig[0],*cp,DUMP_BASE);
    if (xp == 0) break;
    cp ++;
    x = ((const char *)xp) - &dumpdig[0];
    lastt = t;
    s += x;
    t += m * x;
    m *= DUMP_BASE;
    lastx = x;
    n ++;
  }
 if (n < 2) return("too short");
 s -= lastx;
 if ((s % DUMP_BASE) != lastx) return("checksum wrong");
 *cpp = cp;
 ts->tv_sec = lastt / 1000000000ULL;
 ts->tv_nsec = lastt % 1000000000ULL;
 return(0);
}

static void input_line_restore(const char *l, int len)
{
 const char *l0;
 struct timespec a_ts;
 struct timespec m_ts;
 struct timeval tv[2];
 const char *err;

 void gripe(const char *msg)
  { fprintf(stderr,"%s: corrupt encoded timestamp (%s): %.30s%s\n",
	__progname,msg,l0,(len>30)?"...":"");
  }

 l0 = l;
 err = parse_encoded_timestamp(&l,&a_ts);
 if (err)
  { gripe(err);
    return;
  }
 if (*l != '=')
  { gripe("no =");
    return;
  }
 l ++;
 err = parse_encoded_timestamp(&l,&m_ts);
 if (err)
  { gripe(err);
    return;
  }
 if (*l != ' ')
  { gripe("no space");
    return;
  }
 l ++;
 tv[0].tv_sec = a_ts.tv_sec;
 tv[0].tv_usec = a_ts.tv_nsec / 1000;
 tv[1].tv_sec = m_ts.tv_sec;
 tv[1].tv_usec = m_ts.tv_nsec / 1000;
 if (lutimes(l,&tv[0]) < 0)
  { fprintf(stderr,"%s: lutimes %s: %s\n",__progname,l,strerror(errno));
  }
}

static int read_input(void)
{
 static char *b = 0;
 static int a = 0;
 int l;
 int c;
 int sl;

 void savec(int ch)
  { if (l >= a) b = realloc(b,a=l+8);
    b[l++] = ch;
  }

 l = 0;
 sl = -1;
 while (1)
  { c = getchar();
    if (c == iterm) break;
    if (c == EOF)
     { if (l == 0) return(0);
       fprintf(stderr,"%s: warning: missing terminator supplied at end of input\n",__progname);
       break;
     }
    if (c == '/') sl = l;
    savec(c);
  }
 savec('\0');
 switch (opmode)
  { case OPMODE_NORMAL:
       input_line_normal(b,l,sl);
       break;
    case OPMODE_DUMP:
       input_line_dump(b);
       break;
    case OPMODE_RESTORE:
       input_line_restore(b,l);
       break;
    default:
       abort();
       break;
  }
 return(1);
}

static void *next_dll(void *p)
{
 return(((DLL *)p)->flink);
}

static void setnext_dll(void *p, void *n)
{
 ((DLL *)p)->flink = n;
}

static F *getf_dll(void *p)
{
 return(&((DLL *)p)->f);
}

static const char *getpath_dll(void *p)
{
 return(((DLL *)p)->f.path);
}

static time_t getstamp_dll(void *p)
{
 return(((DLL *)p)->f.stamp);
}

static void *next_sll(void *p)
{
 return(((SLL *)p)->link);
}

static void setnext_sll(void *p, void *n)
{
 ((SLL *)p)->link = n;
}

static F *getf_sll(void *p)
{
 return(&((SLL *)p)->f);
}

static const char *getpath_sll(void *p)
{
 return(((SLL *)p)->f.path);
}

static time_t getstamp_sll(void *p)
{
 return(((SLL *)p)->f.stamp);
}

static int cmp_input(F *a, F *b)
{
 return(a->serial < b->serial);
}

static int cmp_time(F *a, F *b)
{
 return(a->stamp < b->stamp);
}

static int cmp_name(F *a, F *b)
{
 return(strcmp(a->path,b->path) < 0);
}

static int cmp_basename(F *a, F *b)
{
 int c;

 c = strcmp(a->base,b->base);
 if (c) return(c<0);
 return(strcmp(a->path,b->path)<0);
}

static void sort_and_print(void)
{
 void *root;
 void *(*next)(void *);
 void (*setnext)(void *, void *);
 F *(*getf)(void *);
 const char *(*getpath)(void *);
 time_t (*getstamp)(void *);
 int (*cmp)(F *, F *);

 void *sort(void *list)
  { void *a;
    void *b;
    void *t;
    void *p;
    if (!list || !(*next)(list)) return(list);
    a = 0;
    b = 0;
    while (list)
     { t = list;
       list = (*next)(list);
       (*setnext)(t,a);
       a = b;
       b = t;
     }
    a = sort(a);
    b = sort(b);
    p = 0;
    while (a || b)
     { if (!b || (a && (revorder ? !(*cmp)((*getf)(a),(*getf)(b))
				 : (*cmp)((*getf)(a),(*getf)(b)) )))
	{ t = a;
	  a = (*next)(a);
	}
       else
	{ t = b;
	  b = (*next)(b);
	}
       if (p) (*setnext)(p,t); else list = t;
       p = t;
     }
    if (! p) abort();
    (*setnext)(p,0);
    return(list);
  }

 if (timemax)
  { root = timelist;
    next = &next_dll;
    setnext = &setnext_dll;
    getf = &getf_dll;
    getpath = &getpath_dll;
    getstamp = &getstamp_dll;
  }
 else
  { root = filelist;
    next = &next_sll;
    setnext = &setnext_sll;
    getf = &getf_sll;
    getpath = &getpath_sll;
    getstamp = &getstamp_sll;
  }
 switch (order)
  { case SORT_INPUT: cmp = &cmp_input; break;
    case SORT_TIME: cmp = &cmp_time; break;
    case SORT_NAME: cmp = &cmp_name; break;
    case SORT_BASENAME: cmp = &cmp_basename; break;
    default: abort(); break;
  }
 root = sort(root);
 for (;root;root=(*next)(root)) print_output((*getpath)(root),(*getstamp)(root));
}

int main(int, char **);
int main(int ac, char **av)
{
 handleargs(ac,av);
 setup();
 while (read_input()) ;
 sort_and_print();
 exit(0);
}