home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume8 / nsort / nsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-10-07  |  5.9 KB  |  222 lines
  1. /*  File   : nsort.c
  2.     Author : Richard A. O'Keefe
  3.     Updated: 1988
  4.     Purpose: Fast sorting command for smallish files.
  5.  
  6.     This program has no copyright notice.  You can do anything you please
  7.     with it, except blame me if it doesn't work.
  8. */
  9.  
  10. #ifndef    lint
  11. static    char SCCSid[] = "%Z%%E% %M%    %I%";
  12. #endif/*lint*/
  13.  
  14. /*  nsort <input >output
  15.  
  16.     is a very simple sorting program which has been written to be as fast
  17.     as possible.  It is equivalent to sort with no arguments.  That is,
  18.     it sorts its standard input to its standard output, and compares
  19.     entire lines.
  20.  
  21.     It uses a natural merge, so if the input is already in order it takes
  22.     linear time, and it reads the entire file into memory, using a single
  23.     read() if the standard input is a regular file.
  24.  
  25.     Sorting random permutations of /usr/dict/words on a Sun-3/50:
  26.     sort(1) : 15 seconds  nsort :  8 seconds  (with SCSI disc)
  27.           17 seconds          11 seconds  (NFS over Ethernet)
  28. */
  29.  
  30. #include <stdio.h>
  31.  
  32. /*  The following values are taken from <sysexits.h>, but are copied here
  33.     in case you lack that BSD header file.
  34. */
  35. #define    EX_OK         0    /* nothing went wrong */
  36. #define    EX_USAGE    64    /* something wrong with the command line */
  37. #define    EX_SOFTWARE    70    /* internal error (here, memory ran out) */
  38. #define    EX_IOERR    71    /* transput error (here, read() trouble) */
  39.  
  40. #define    STDIN         0
  41.  
  42. extern    char *    malloc();
  43. extern    char *    strcpy();
  44. extern    int    strcmp();
  45. extern    int    strlen();
  46. extern    void    perror();
  47. extern    int    lseek();
  48. extern    int    read();
  49.  
  50. typedef struct item_rec *item_ptr;
  51.  
  52. struct item_rec
  53.     {    
  54.     item_ptr    next;
  55.     char*         data;
  56.     };
  57.  
  58. #define    IN_ORDER(x, y) (strcmp((x)->data, (y)->data) <= 0)
  59.  
  60.  
  61. item_ptr nat_sort(list)
  62.     item_ptr list;
  63.     {
  64.     item_ptr stack[30];
  65.     item_ptr *sp = stack;
  66.     int runs = 0;            /* total number of runs processed */
  67.     register item_ptr p, q, r;
  68.     struct item_rec header;
  69.     int k;
  70.  
  71.     while (p = list) {
  72.         /* pick up a run from the front of list, setting */
  73.         /* p = (pointer to beginning of run), list = (rest of list) */
  74.         if (q = p->next) {
  75.         list = q->next;
  76.         if (!IN_ORDER(p, q)) r = q, q = p, p = r;
  77.         p->next = q;
  78.         for (r = list; r && IN_ORDER(q, r); r = r->next)
  79.             q->next = r, q = r;
  80.         q->next = (item_ptr)0;
  81.         list = r;
  82.         } else {
  83.         list = (item_ptr)0;
  84.         }
  85.         runs++;
  86.         /* merge this run with 0 or more runs off the top of the stack */
  87.         for (k = runs; 1 &~ k; k >>= 1) {
  88.         q = *--sp;
  89.         r = &header;
  90.         while (q && p)
  91.             if (IN_ORDER(q, p)) {
  92.             r->next = q;
  93.             r = q, q = q->next;
  94.             } else {
  95.             r->next = p;
  96.             r = p, p = p->next;
  97.             }
  98.         r->next = q ? q : p;
  99.         p = header.next;
  100.         }
  101.         /* push the merged run onto the stack */
  102.         *sp++ = p;
  103.     }
  104.     if (sp == stack) return (item_ptr)0;
  105.     /* merge all the runs on the stack */
  106.     p = *--sp;
  107.     while (sp != stack) {
  108.         q = *--sp;
  109.         r = &header;
  110.         while (q && p)
  111.         if (IN_ORDER(q, p)) {
  112.             r->next = q;
  113.             r = q, q = q->next;
  114.         } else {
  115.             r->next = p;
  116.             r = p, p = p->next;
  117.         }
  118.         r->next = q ? q : p;
  119.         p = header.next;
  120.     }
  121.     return p;
  122.     }
  123.  
  124. item_ptr alloc_item(data)
  125.     char *data;
  126.     {
  127.     register item_ptr result;
  128.  
  129.     result = (item_ptr)malloc(sizeof *result + strlen(data) + 1);
  130.     if (result) {
  131.         result->next = (item_ptr)0;
  132.         result->data = strcpy((char*)result + sizeof *result, data);
  133.     }
  134.     return result;
  135.     }
  136.  
  137. /*  What we really want to do is to slurp the entire file in with one call
  138.     to read().  In order to do that, we need to know how much there is.  A
  139.     file's size can be determined either by calling fstat() or by using an
  140.     lseek() to the end.  The number you get from fstat() doesn't mean much
  141.     for pipes and terminals, so lseek() appears to be the better approach.
  142.     Note that even when stdin is connected to a file, part of it may have
  143.     been read already.  In that case, we should not include the part which
  144.     has been read.  So we do
  145.     i = lseek(STDIN, 0, 1)
  146.     to discover the current position (and simultaneously to find out if we
  147.     can use lseek() at all on this file descriptor).  One problem remains;
  148.     the size of the file may change while we are reading it.  In that case
  149.     we'll stop early if we have to, but if the file grows we'll miss stuff
  150.     added at the end.
  151. */
  152. main(argc, argv)
  153.     int argc;
  154.     char **argv;
  155.     {
  156.     struct item_rec header;
  157.     item_ptr p, q;
  158.     char *progname = argc >= 1 ? argv[0] : "nsort";
  159.     int i;
  160.  
  161.     if (argc != 1) {
  162.         fprintf(stderr, "Usage: %s <unordered >sorted\n", progname);
  163.         exit(EX_USAGE);
  164.     }
  165.     i = lseek(STDIN, 0, 1);    /* current position in stream */
  166.     if (i < 0) {        /* can't find out the size by seeking */
  167.         char buffer[1024];
  168.  
  169.         for (p = &header
  170.         ; fgets(buffer, sizeof buffer, stdin)
  171.         ; p->next = q, p = q) {
  172.         i = strlen(buffer);
  173.         if (i > 0 && buffer[i-1] == '\n') buffer[i-1] = '\0';
  174.         if (!(q = alloc_item(buffer))) {
  175.             fprintf(stderr, "%s: ran out of memory\n", progname);
  176.             exit(EX_SOFTWARE);
  177.         }
  178.     } else {
  179.         register char *b, *c;
  180.         register int n;
  181.  
  182.         n = lseek(STDIN, 0, 2) - i;    /* part of stdin may have been read */
  183.         (void) lseek(STDIN, i, 0);    /* go back to original position */
  184.         if (!(b = malloc(n+1))) {
  185.         fprintf(stderr, "%s: ran out of memory\n", progname);
  186.         exit(EX_SOFTWARE);
  187.         }
  188.         for (c = b; (i = n-(c-b)) > 0; c += i) {
  189.         i = read(STDIN, c, i);
  190.         if (i < 0) {
  191.             perror(progname);
  192.             exit(EX_IOERR);
  193.         } else 
  194.         if (i == 0) {
  195.             break;
  196.         }
  197.         }
  198.         /* it is possible that the file may have been truncated */
  199.         /* while we were reading it. */
  200.         n = c-b;
  201.         for (p = &header; n > 0; b = c, p->next = q, p = q) {
  202.         for (c = b; --n >= 0; c++)
  203.             if (*c == '\n') {
  204.             *c++ = '\0';
  205.             break;
  206.             }
  207.         if (n < 0) *c = '\0';
  208.         if (!(q = (item_ptr) malloc(sizeof *q))) {
  209.             fprintf(stderr, "nsort: ran out of memory\n");
  210.             exit(EX_SOFTWARE);
  211.         }
  212.         q->data = b;
  213.         }
  214.     }
  215.     p->next = (item_ptr)0;
  216.     p = header.next;
  217.     for (p = nat_sort(p); p; p = p->next)
  218.         puts(p->data);
  219.     exit(EX_OK);
  220.     }
  221.  
  222.