adk/tools/sortfile.c

   1 /*-
   2  * Copyright (c) 2010
   3  *      Thorsten Glaser <tg@mirbsd.org>
   4  *
   5  * Provided that these terms and disclaimer and all copyright notices
   6  * are retained or reproduced in an accompanying document, permission
   7  * is granted to deal in this work without restriction, including un-
   8  * limited rights to use, publicly perform, distribute, sell, modify,
   9  * merge, give away, or sublicence.
  10  *
  11  * This work is provided "AS IS" and WITHOUT WARRANTY of any kind, to
  12  * the utmost extent permitted by applicable law, neither express nor
  13  * implied; without malicious intent or gross negligence. In no event
  14  * may a licensor, author or contributor be held liable for indirect,
  15  * direct, other damage, loss, or other issues arising in any way out
  16  * of dealing in the work, even if advised of the possibility of such
  17  * damage or existence of a defect, except proven that it results out
  18  * of said person's immediate fault when using the work as intended.
  19  */
  20
  21 #include <sys/types.h>
  22 #include <sys/mman.h>
  23 #include <sys/stat.h>
  24 #include <err.h>
  25 #include <fcntl.h>
  26 #include <limits.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <unistd.h>
  30
  31 struct ptrsize {
  32         const char *ptr;
  33         size_t size;
  34 };
  35
  36 static void *xrecalloc(void *, size_t, size_t);
  37 static int cmpfn(const void *, const void *);
  38
  39 #define MUL_NO_OVERFLOW (1UL << (sizeof (size_t) * 8 / 2))
  40
  41 #ifndef SIZE_MAX
  42 #ifdef SIZE_T_MAX
  43 #define SIZE_MAX        SIZE_T_MAX
  44 #else
  45 #define SIZE_MAX        ((size_t)-1)
  46 #endif
  47 #endif
  48
  49 #if !defined(MAP_FAILED)
  50 /* XXX imake style */
  51 #  if defined(__linux)
  52 #define MAP_FAILED      ((void *)-1)
  53 #  elif defined(__bsdi__) || defined(__osf__) || defined(__ultrix)
  54 #define MAP_FAILED      ((caddr_t)-1)
  55 #  endif
  56 #endif
  57
  58 static void *
  59 xrecalloc(void *ptr, size_t nmemb, size_t size)
  60 {
  61         void *rv;
  62
  63         if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
  64             nmemb > 0 && SIZE_MAX / nmemb < size)
  65                 errx(1, "attempted integer overflow: %zu * %zu", nmemb, size);
  66         size *= nmemb;
  67         if ((rv = realloc(ptr, size)) == NULL)
  68                 err(1, "cannot allocate %zu bytes", size);
  69         return (rv);
  70 }
  71
  72 int
  73 sortfile(char *infile, char *outfile)
  74 {
  75         int fd, fdout;
  76         size_t fsz, asz, anents;
  77         char *cp, *thefile, *endfile;
  78         struct ptrsize *thearray;
  79
  80         if ((fd = open(infile, O_RDONLY)) < 0)
  81                 err(1, "open: %s", infile);
  82         else {
  83                 struct stat sb;
  84
  85                 /* reasonable maximum size: 3/4 of SIZE_MAX */
  86                 fsz = (SIZE_MAX / 2) + (SIZE_MAX / 4);
  87
  88                 if (fstat(fd, &sb))
  89                         err(1, "stat: %s", infile);
  90                 if (sb.st_size > fsz)
  91                         errx(1, "file %s too big, %llu > %zu", infile,
  92                             (unsigned long long)sb.st_size, fsz);
  93                 fsz = (size_t)sb.st_size;
  94         }
  95
  96         if ((thefile = mmap(NULL, fsz, PROT_READ, MAP_FILE | MAP_PRIVATE,
  97             fd, (off_t)0)) == MAP_FAILED)
  98                 err(1, "mmap %zu bytes from %s", fsz, infile);
  99         /* last valid byte in the file, must be newline anyway */
 100         endfile = thefile + fsz - 1;
 101
 102         thearray = xrecalloc(NULL, (asz = 8), sizeof(thearray[0]));
 103         thearray[(anents = 0)].ptr = cp = thefile;
 104
 105         while ((cp = memchr(cp, '\n', endfile - cp)) != NULL) {
 106                 /* byte after the \n */
 107                 if (++cp > endfile)
 108                         /* end of file */
 109                         break;
 110                 thearray[anents].size = cp - thearray[anents].ptr;
 111                 if (++anents == asz)
 112                         /* resize array */
 113                         thearray = xrecalloc(thearray, (asz <<= 1),
 114                             sizeof(thearray[0]));
 115                 thearray[anents].ptr = cp;
 116         }
 117         thearray[anents].size = endfile - thearray[anents].ptr + 1;
 118
 119         qsort(thearray, ++anents, sizeof(thearray[0]), cmpfn);
 120
 121         if ((fdout = open(outfile, O_WRONLY | O_CREAT, S_IRWXU)) < 0)
 122                 err(1, "open: %s", outfile);
 123         else {
 124                 for (asz = 0; asz < anents; ++asz)
 125                         if ((size_t)write(fdout, thearray[asz].ptr,
 126                             thearray[asz].size) != thearray[asz].size)
 127                                 err(1, "write %zu bytes", thearray[asz].size);
 128         }
 129
 130         if (munmap(thefile, fsz))
 131                 warn("munmap");
 132
 133         free(thearray);
 134         close(fd);
 135
 136         return (0);
 137 }
 138
 139 static int
 140 cmpfn(const void *p1, const void *p2)
 141 {
 142         int rv;
 143         const struct ptrsize *a1 = (const struct ptrsize *)p1;
 144         const struct ptrsize *a2 = (const struct ptrsize *)p2;
 145
 146         if ((rv = memcmp(a1->ptr, a2->ptr, (a1->size > a2->size ?
 147             a2->size : a1->size) - /* '\n' */ 1)) != 0)
 148                 /* unequal in the common part */
 149                 return (rv);
 150
 151         /* shorter string is smaller */
 152         return (a1->size > a2->size ? 1 : a1->size == a2->size ? 0 : -1);
 153 }