home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnuch40.zip / gnuchess-4.0.pl79 / src / binsort.c < prev    next >
C/C++ Source or Header  |  1998-09-28  |  46KB  |  1,650 lines
  1. /****************************************************************************
  2.   binsort.c
  3.  
  4.      This code is distributed under the terms and conditions of the
  5.      CCP4 licence agreement as `Part i)' software.  See the conditions
  6.      in the CCP4 manual for a copyright statement.
  7.      */
  8. #define VERSION "Z131093"                                                  /*
  9.  
  10. HOW TO USE
  11.  
  12. Just run binsort without any arguments and short manual will be printed
  13. on your screen.
  14.  
  15. WHAT IS BINSORT
  16.  
  17. binsort    was designed for sorting BINARY FIXED LENGTH records
  18. under UNIX (and possible others) operating system.
  19. Directives for sorting are present in command line, input is read from stdin,
  20. output written into stdout, message written into stderr. This allows
  21. binsort to be used as a filter.
  22.  
  23. SOMETHING ABOUT ALGORITHMS.
  24.  
  25. Program uses UNIX sort procedure qsort. Compare function "cmproutine"
  26. interprets an array of key descriptions by subsequent calling of data
  27. type specific functions. There are also separate functions which perform
  28. also mask processing among them. Cruical resource of each sort algorithm
  29. is a work space. binsort (as it does not know the file size in advance)
  30. allocates workspace of WORKASZ bytes, which can be reset before binsort
  31. compilation or altered through BINSORT_MEM external variable or -m switch.
  32. Work area is rounded to 4 record boundary and used by qsort to produce
  33. a set of sorted "runs", which are by merge distributed to 3 (of total 4)
  34. scratch files. These are created in directory SCRPATH, which can again be
  35. set before binsort compilation and altered by BINSORT_SCR external variable.
  36. No modifying switch is provided. Distribution and subsequent merging uses
  37. polyphase merge algorithm mentioned below. In this phase the work space
  38. is devided into 4 parts and serves as I/O buffers for scratch files.
  39.  
  40. WARRANTY
  41.  
  42. As usual, absolutly none. But you can address your complains during
  43. next few months to
  44.  
  45. zelinka@uk.ac.york,yorvic      (from the U.K. - Janet convention)
  46. zelinka@yorvic.york.ac.uk      (from the rest of the world)
  47.  
  48. NOTE
  49.  
  50. Do not critisize the programing style. This is a compromise between
  51. ANSI & old-fasioned C
  52. *****************************************************************************
  53. *****************************************************************************
  54.   merge
  55.  
  56. Polyphase merge sorting with "horizontal distribution"
  57. implemented for T = 4, P = T-1 = 3
  58. as published in:
  59.          Donald E. Knuth: The Art of Computer Programming Vol.3
  60.                           (Sorting and Searching) pp. 270-271
  61.                           Addison-Wesley Publishing Company, Inc. (1973)
  62.  
  63. *****************************************************************************/
  64. #define T                     4
  65. #define P                     3
  66.  
  67. /*#define FUNCPROTO   1        Good for debugging under ANSI C */
  68. /*#define ALIGNMENT  (sizeof(int))*/
  69. #define ALIGNMENT  (sizeof(double))
  70.  
  71.  
  72. #ifdef VAX_VMS
  73. #    include    stdio
  74. #    include    stdlib
  75. #    include    unixio
  76. #    include    processes
  77. #    include    time
  78. #else      /* UNIX */
  79. #    include <stdio.h>
  80. #    include <string.h>           /* string operations */
  81. #    include <fcntl.h>            /* for i/o */
  82. #    include <sys/types.h>        /* for statistics & io */
  83. #    include <sys/stat.h>         /* for i/o */
  84. #    include <errno.h>
  85. #    include <sys/param.h>        /* for statistics */
  86. #    include <sys/times.h>        /* for statistics */
  87. #    include <time.h>
  88. #    include <stdlib.h>
  89.  
  90. #    ifndef NOUNISTD        /* ESV, for instance, doesn't have it */
  91. #      include <unistd.h>
  92. #    endif
  93. #    ifndef  SEEK_SET
  94. #      if defined(ESV) && defined(SYSTYPE_BSD43)
  95. #       include <sys/file.h>
  96. #       define SEEK_SET L_SET
  97. #       ifndef L_END
  98. #         define L_END L_XTND /* necessary for ESV OS2.3 it seems */
  99. #       endif
  100. #       define SEEK_END L_END
  101. #      endif
  102. #    endif /* SEEK_SET */
  103. #endif     /* VAX_VMS - UNIX */
  104.  
  105. #include "binsort.h"              /* key data types definition */
  106.  
  107.  
  108. #define  tolower(c)     ((c > 'A' && c < 'Z') ? c + ('a'-'A') : c)
  109.  
  110. /*** System/machine/country dependent ***/
  111.  
  112. #define CLOCKFREQ             60             /* system clock frequence */
  113.  
  114.  
  115. /*** Site dependent, please modify if necessary***/
  116.  
  117. #define SCRPATH            "/tmp"          /* default scratch file path */
  118. #define    WORKASZ            1024000             /* Default work area size */
  119.  
  120. /*** Low level compare function ("prototype")                            ***
  121.  *** Returns 1 if rec1 > rec2    0 if rec1 == rec2     -1 if rec1 < rec2 ***/
  122.  
  123. /*** Internal key structure ***/
  124.  
  125. typedef struct key_dsc {          /* internal key description */
  126.   int        (*cmp_function)(     /* -> compare function */
  127. #      ifdef FUNCPROTO
  128.             char             *rec1,
  129.             char             *rec2,
  130.             struct key_dsc   *key
  131. #      endif /* FUNCPROTO */
  132.             );
  133.   short        key_type,          /* data type of key */
  134.                asc_desc_order;    /* asc/desc sort order */
  135.   int          key_pos,           /* 1st key byte position in record
  136.                      numbered from 0 */
  137.                key_length;        /* key length in given data type units */
  138.   union {                         /* mask description */
  139.   unsigned char  m_char;          /* mask for char data types */
  140.   unsigned short m_short;         /* mask for short data types */
  141.   unsigned long  m_long;          /* mask for long data types */
  142.   }            mask;              /* mask used BEFORE comparison */
  143. } *KEYDSC;
  144.  
  145. typedef int   (*CMPFUN)(
  146. #ifdef FUNCPROTO
  147.             char             *rec1,
  148.             char             *rec2,
  149.             struct key_dsc   *key
  150. #endif /* FUNCPROTO */
  151.             );
  152.  
  153. /*** Scratch tape structure ***/
  154.  
  155. struct scratch_tape {
  156.   int        fd;          /* tape file descriptor */
  157.   int        truns;       /* actual runs written into tape */
  158.   int        runlng;      /* current run length */
  159.   char      *buf;         /* i/o buffer */
  160.   char      *pbuf;        /* pointer to buffer */
  161. };
  162. static struct scratch_tape TAPE [T+1]; /* Number of the physical tape unit
  163.                       corresponding to logical tape unit
  164.                       number j */
  165.  
  166.  
  167. /*** routines used int this module ***/
  168. static void             advancerunrec(
  169. #ifdef FUNCPROTO
  170.                    struct scratch_tape  *ctape
  171. #endif /* FUNCPROTO */
  172.                    );
  173. static int              cmp_char(
  174. #ifdef FUNCPROTO
  175.                    char            *e1,
  176.                                char            *e2,
  177.                    KEYDSC           key
  178. #endif /* FUNCPROTO */
  179.                    );
  180. static int              cmp_uchar(
  181. #ifdef FUNCPROTO
  182.                    char            *e1,
  183.                                char            *e2,
  184.                    KEYDSC           key
  185. #endif /* FUNCPROTO */
  186.                    );
  187. static int              cmp_uchar_mask(
  188. #ifdef FUNCPROTO
  189.                    char            *e1,
  190.                                char            *e2,
  191.                    KEYDSC           key
  192. #endif /* FUNCPROTO */
  193.                    );
  194. static int              cmp_double(
  195. #ifdef FUNCPROTO
  196.                    char            *e1,
  197.                                char            *e2,
  198.                    KEYDSC           key
  199. #endif /* FUNCPROTO */
  200.                    );
  201. static int              cmp_float(
  202. #ifdef FUNCPROTO
  203.                    char            *e1,
  204.                                char            *e2,
  205.                    KEYDSC           key
  206. #endif /* FUNCPROTO */
  207.                    );
  208. static int              cmp_long(
  209. #ifdef FUNCPROTO
  210.                    char            *e1,
  211.                                char            *e2,
  212.                    KEYDSC           key
  213. #endif /* FUNCPROTO*/
  214.                    );
  215. static int              cmp_ulong(
  216. #ifdef FUNCPROTO
  217.                    char            *e1,
  218.                                char            *e2,
  219.                    KEYDSC           key
  220. #endif /* FUNCPROTO */
  221.                    );
  222. static int              cmp_ulong_mask(
  223. #ifdef FUNCPROTO
  224.                    char            *e1,
  225.                                char            *e2,
  226.                    KEYDSC           key
  227. #endif /* FUNCPROTO */
  228.                    );
  229. static int              cmp_short(
  230. #ifdef FUNCPROTO
  231.                    char            *e1,
  232.                                char            *e2,
  233.                    KEYDSC           key
  234. #endif /* FUNCPROTO */
  235.                    );
  236. static int              cmp_ushort(
  237. #ifdef FUNCPROTO
  238.                    char            *e1,
  239.                                char            *e2,
  240.                    KEYDSC           key
  241. #endif /* FUNCPROTO */
  242.                    );
  243. static int              cmp_ushort_mask(
  244. #ifdef FUNCPROTO
  245.                    char            *e1,
  246.                                char            *e2,
  247.                    KEYDSC           key
  248. #endif /* FUNCPROTO */
  249.                    );
  250. static int              cmproutine(
  251. #ifdef FUNCPROTO
  252.                    const void      *e1,
  253.                    const void      *e2
  254. #endif /* FUNCPROTO */
  255.                    );
  256. static int              pointer_cmproutine(
  257. #ifdef FUNCPROTO
  258.                    const void      *pe1,
  259.                    const void      *pe2
  260. #endif /* FUNCPROTO */
  261.                    );
  262. static int              fillworka(
  263. #ifdef FUNCPROTO
  264.                    void
  265. #endif /* FUNCPROTO */
  266.                    );
  267. static void             flushrunbuf(
  268. #ifdef FUNCPROTO
  269.                    void
  270. #endif /* FUNCPROTO */
  271.                    );
  272. static void             gettape(
  273. #ifdef FUNCPROTO
  274.                    int              num
  275. #endif /* FUNCPROTO */
  276.                    );
  277. static void             ioerr(
  278. #ifdef FUNCPROTO
  279.                    void
  280. #endif /* FUNCPROTO */
  281.                    );
  282. static void             linecmd(
  283. #ifdef FUNCPROTO
  284.                   int               argc,
  285.                               char             *argv []
  286. #endif /* FUNCPROTO */
  287.                   );
  288. int                     main(
  289. #ifdef FUNCPROTO
  290.                   int               argc,
  291.                               char             *argv []
  292. #endif /* FUNCPROTO */
  293.                   );
  294. static void             manual(
  295. #ifdef FUNCPROTO
  296.                    void
  297. #endif /* FUNCPROTO */
  298.                    );
  299. static void             memoryerr(
  300. #ifdef FUNCPROTO
  301.                    void
  302. #endif /* FUNCPROTO */
  303.                    );
  304. static void             merge(
  305. #ifdef FUNCPROTO
  306.                    void
  307. #endif /* FUNCPROTO */
  308.                    );
  309. static void             merge1(
  310. #ifdef FUNCPROTO
  311.                    struct scratch_tape   *p1
  312. #endif /* FUNCPROTO */
  313.                    );
  314. static void             merge2(
  315. #ifdef FUNCPROTO
  316.                    struct scratch_tape   *p1,
  317.                    struct scratch_tape   *p2
  318. #endif /* FUNCPROTO */
  319.                    );
  320. static void             merge3(
  321. #ifdef FUNCPROTO
  322.                    struct scratch_tape   *p1,
  323.                    struct scratch_tape   *p2,
  324.                    struct scratch_tape   *p3
  325. #endif /* FUNCPROTO */
  326.                    );
  327. static void             mergeruns(
  328. #ifdef FUNCPROTO
  329.                    void
  330. #endif /* FUNCPROTO */
  331.                    );
  332. static void             printkeys(
  333. #ifdef FUNCPROTO
  334.                    void
  335. #endif /* FUNCPROTO */
  336.                    );
  337. static void             proterr(
  338. #ifdef FUNCPROTO
  339.                    void
  340. #endif /* FUNCPROTO */
  341.                    );
  342. static void             prtstatist(
  343. #ifdef FUNCPROTO
  344.                    long             realtime
  345. #endif /* FUNCPROTO */
  346.                    );
  347. void                    putrunrec(
  348. #ifdef FUNCPROTO
  349.                    char            *rec
  350. #endif /* FUNCPROTO */
  351.                    );
  352. static int              readrun(
  353. #ifdef FUNCPROTO
  354.                    void
  355. #endif /* FUNCPROTO */
  356.                    );
  357. static void             rewindtape(
  358. #ifdef FUNCPROTO
  359.                    int               num
  360. #endif /* FUNCPROTO */
  361.                    );
  362. static void             sort(
  363. #ifdef FUNCPROTO
  364.                    int               nrecords,
  365.                    int               recsize
  366. #endif /* FUNCPROTO */
  367.                    );
  368. static void             pointer_sort(
  369. #ifdef FUNCPROTO
  370.                    int               nrecords
  371. #endif /* FUNCPROTO */
  372.                    );
  373. static void             testprint(
  374. #ifdef FUNCPROTO
  375.                    void
  376. #endif /* FUNCPROTO */
  377.                    );
  378. static void             writerun(
  379. #ifdef FUNCPROTO
  380.                    int               num,
  381.                    int               nrec
  382. #endif /* FUNCPROTO */
  383.                    );
  384. static void             my_exit(
  385. #ifdef FUNCPROTO
  386.                    int               status
  387. #endif /* FUNCPROTO */
  388.                    );
  389.  
  390. /*** Memory resources ***/
  391. static char     *scrpath = SCRPATH;
  392.  
  393. /*** Work area ***/
  394. static void    *workarea;            /* work area */
  395. static void    *pointer_area;
  396. static int      workasz = WORKASZ,   /* default work area maximal size */
  397.                 actworkasz = 0,      /* work area actual rounded size */
  398.                 workainrec = 0;      /*         - || -                in
  399.                         records */
  400. static int      scrbufsize;          /* scratch file buffer size (bytes) */
  401. static int      scrbufinrec;         /* scratch file buffer size (records) */
  402.  
  403. static int      sortmode;
  404. #define     RECORD_MODE    0
  405. #define     POINTER_MODE   1
  406.  
  407. /**** The routine manual gives you some information about the interface ***/
  408. static void
  409. manual()
  410. {
  411. fprintf(stderr,
  412. "\n\n\
  413. Command:\n\
  414. binsort key key_value [key keyvalue [...]] <infile >outfile\n\
  415. \n\
  416. Keys:\n\
  417.     -r n    n - length of one (FIXED LENGTH) record\n\
  418. \n\
  419.     -k typ:order:start[:length[:mask]] - key description.\n\
  420.         typ    - data type (c character) (C unsigned character)\n\
  421.                    (s short) (S unsigned short)\n\
  422.                                (l long) (L unsigned long)\n\
  423.                    (f float) (d double)\n\
  424.         order  - (a ascending)\n\
  425.                      (d descending)\n\
  426.         start  - position of the beginning of key from beginning\n\
  427.              of the record in bytes. 1st record byte has position 0.\n\
  428.         length - number of units of specified data type, default\n\
  429.                      value 1\n\
  430.             mask   - hexadecimal value interpreted as mask,\n\
  431.                      which is applied to data unit BEFORE comparison.\n\
  432.                      Mask can be used only with C, S, & L data types.\n\
  433.                      If mask is present, length must be given explicitly.\n\
  434. \n\
  435.      -m n   n - number of bytes used in main work area. Default is written\n\
  436.                 below\n\
  437. \n\
  438.      -v     with no value, verbose mode of binsort\n\
  439. \n\
  440. Environment variables:\n\
  441.      BINSORT_SCR    - scratch path\n\
  442.      BINSORT_MEM    - work area in bytes\n\
  443.      BINSORT_VERB   - (if set) program becomes talkative\n\
  444. \n\
  445. Bugs/Features:\n\
  446.     Data types other then short, char were not tested well.\n\
  447.     Each record is alligned on %d byte boundary. Some machines may\n\
  448.         require different alignment. In that case you must edit symbol\n\
  449.         ALIGNMENT in binsort.c (source file) and recompile it.\n\
  450.         Data fields withinin record itself must be properly aligned,\n\
  451.         otherwise BUS ERROR is invoked.\n\
  452.         Binsort does not check semantics of keyvalue data.\n\
  453. \n\
  454. Notes:\n\
  455.     Current work area size %dB,\n\
  456.     Current scratch file path %s.\n\
  457. \n\
  458. Version %s                            Good Luck\n\
  459.                                               J. Zelinka\n\
  460. ", ALIGNMENT, workasz, scrpath, VERSION);
  461. }
  462.  
  463. /*** Internal constants - do not change them ***/
  464.  
  465. #define INPUT                   0       /* stdin file descriptor */
  466. #define OUTPUT                  1       /* stdout file descriptor */
  467. #define    TRUE                    1
  468. #define    FALSE                   0
  469.  
  470. /*** Input switches ***/
  471.  
  472. #define F_LREC                  "-r"
  473. #define F_KEY                   "-k"
  474. #define F_MEM                   "-m"
  475. #define F_VERBOSE               "-v"
  476. #define F_ASC                   'a'
  477. #define F_DESC                  'd'
  478. #define F_CHAR                  'c'
  479. #define F_UCHAR                 'C'
  480. #define F_SHORT                 's'
  481. #define F_USHORT                'S'
  482. #define F_LONG                  'l'
  483. #define F_ULONG                 'L'
  484. #define F_FLOAT                 'f'
  485. #define F_DOUBLE                'd'
  486.  
  487. /*** internal variables ***/
  488.  
  489. static int      f_verbose = FALSE;      /* verbose flag */
  490.  
  491. /*** Record and it's attributes ***/
  492. static int      lrecl = 0,    /* fixed record length */
  493.                 actrecl,      /* record length rounded to suitable boundary */
  494.                 nkeys = 0,    /* number of sort keys */
  495.                 nrecs = 0,    /* number of all records */
  496.                 outnrecs = 0; /*  -  ||  -        as a check count */
  497. static struct key_dsc  *keys; /* key definitions */
  498.  
  499. /******************************* C O D E *********************************/
  500. main(argc, argv)
  501. int      argc;
  502. char    *argv[];
  503. {
  504.   time_t        oldrealtime, newrealtime;
  505.   char         *charvalue;
  506.   int           n_pointers;
  507.  
  508.   /*** real time init. ***/
  509.   oldrealtime = time(&oldrealtime);
  510.  
  511.   /*** environment variables processing ***/
  512.   if (charvalue = (char *) getenv ("BINSORT_MEM"))
  513.     workasz = atoi(charvalue);
  514.   if (charvalue = (char *) getenv ("BINSORT_SCR"))
  515.     scrpath = charvalue;
  516.   if (charvalue = (char *) getenv ("BINSORT_VERB"))
  517.     f_verbose = charvalue ? TRUE : FALSE;
  518.  
  519.   /*** Input parameters processing ***/
  520.   linecmd(argc, argv);     /* comands from command line */
  521.   if (f_verbose)
  522.     printkeys();
  523.  
  524.   /*** Work area initialization - make a decision about record/pointer
  525.        sort procedure NOW                                              ***/
  526.  
  527.   actrecl = lrecl + ((ALIGNMENT-(lrecl%ALIGNMENT)) % ALIGNMENT);
  528.                           /* record allignment */
  529.   if (f_verbose)
  530.     fprintf(stderr, "binsort -- requested/aligned record length %d/%d\n",
  531.         lrecl, actrecl);
  532.  
  533.   actworkasz = workasz - (workasz % (actrecl * 4)); /* rounded on 4 records
  534.                                boundary */
  535.   if (f_verbose)
  536.     fprintf(stderr, "binsort -- requested/aligned work area size %d/%d\n",
  537.         workasz, actworkasz);
  538.  
  539.   workainrec = actworkasz / actrecl;                /* lengths in records */
  540.   scrbufsize = actworkasz / 4;                      /* scratch file buffer */
  541.   scrbufinrec = scrbufsize / actrecl;
  542.   if (workainrec <= 50 || !(workarea = (char *)malloc(actworkasz)))
  543.     memoryerr();
  544.  
  545.   if (actrecl < (3 * sizeof(void *))) {              /* record sort */
  546.     sortmode = RECORD_MODE;
  547.     if (f_verbose)
  548.       fprintf(stderr, "binsort -- record mode choosen\n");
  549.   }
  550.   else {
  551.     sortmode = POINTER_MODE;
  552.     if (f_verbose)
  553.       fprintf(stderr, "binsort -- pointer mode choosen\n");
  554.  
  555.     /*** workarea must be devided into record & pointer parts ***/
  556.     
  557.     n_pointers = actworkasz / (actrecl + sizeof(void *));
  558.  
  559.     /*** n_pointers == n records (of course) ***/
  560.  
  561.     pointer_area = (char *)workarea + actrecl * n_pointers;
  562.   }
  563.  
  564.   /*** Sort processing ***/
  565.   if (f_verbose)
  566.     fprintf(stderr, "binsort -- sorting started\n");
  567.   merge();
  568.  
  569.   /*** Final statistics ***/
  570.   newrealtime = time(&newrealtime);
  571.   if (f_verbose) {
  572.     fprintf(stderr, "binsort -- End\n");
  573.     prtstatist(newrealtime-oldrealtime);
  574.   }
  575.   my_exit(0);
  576. }
  577.  
  578.  
  579. /*=============================================================*/
  580. static void
  581. linecmd(argc, argv)
  582. register int    argc;
  583. char        *argv[];
  584. {
  585.   register int                  i, j;
  586.   register struct key_dsc      *pkeys;
  587.   int                           d1, d2, d3;
  588.   char                          c, c1, c2;
  589.  
  590.  
  591.   for (i = 1; i < argc; ++i)    /* parse line, count keys */
  592.     if (!strcmp(argv[i], F_VERBOSE))
  593.       f_verbose = TRUE;
  594.     else if (!strcmp(argv[i], F_LREC)) {
  595.       ++i;
  596.       if (i == argc || sscanf(argv[i], "%d%1c", &lrecl, &c) != 1) {
  597.     manual();
  598.     fprintf(stderr, "binsort -- bad record length\n");
  599.     my_exit(1);
  600.       }
  601.     }
  602.     else if (!strcmp(argv[i], F_MEM)) {
  603.       ++i;
  604.       if (i == argc || sscanf(argv[i], "%d%1c", &workasz, &c) != 1) {
  605.     manual();
  606.     fprintf(stderr, "binsort -- bad memory specification\n");
  607.     my_exit(1);
  608.       }
  609.     }
  610.     else if (!strcmp(argv[i], F_KEY)) {
  611.       ++i;
  612.       if (i < argc
  613.              &&
  614.       (((j = sscanf(argv[i],"%1c:%1c:%d:%d:%x%1c",
  615.             &c1, &c2, &d1, &d2, &d3, &c)) == 5
  616.                         &&
  617.                (c1 == F_UCHAR || c1 == F_USHORT || c1 == F_ULONG))
  618.                    ||
  619.          (j == 4 || j == 3)
  620.                             &&
  621.                ((c1=tolower(c1)) == F_CHAR || c1 == F_SHORT ||
  622.                               c1 == F_LONG || c1 == F_FLOAT ||
  623.                           c1 == F_DOUBLE))
  624.               &&
  625.            (c2 == F_ASC || c2 == F_DESC))
  626.     ++nkeys;
  627.       else {
  628.     manual();
  629.     fprintf(stderr, "binsort -- bad key specification\n");
  630.     my_exit(1);
  631.       }
  632.     }
  633.     else {
  634.       manual();
  635.       fprintf(stderr, "binsort -- bad option\n");
  636.       my_exit(1);
  637.     }
  638.  
  639.   if (lrecl == 0) {
  640.     manual();
  641.     fprintf(stderr, "binsort -- bad record length\n");
  642.     my_exit(1);
  643.   }
  644.  
  645.   if (nkeys == 0) {
  646.     manual();
  647.     fprintf(stderr, "binsort -- no keys\n");
  648.     my_exit(1);
  649.   }
  650.  
  651.   pkeys = keys = (struct key_dsc *)malloc(nkeys * sizeof(struct key_dsc));
  652.   if (pkeys == NULL) memoryerr();
  653.   for (i = 1; i < argc; ++i)
  654.     if (!strcmp(argv[i], F_KEY)) {    /* key values */
  655.       d2 = 1;                           /* default length */
  656.       d3 = 0;                           /* default no mask */
  657.       ++i;
  658.       sscanf(argv[i],"%1c:%1c:%d:%d:%x%1c",&c1,&c2,&d1,&d2,&d3,&c);
  659.       pkeys->asc_desc_order = ( c2 == F_ASC) ? ASC : DESC;
  660.       pkeys->key_pos = d1;
  661.       pkeys->key_length = d2;
  662.  
  663.       switch (c1) {
  664.       case F_CHAR:   pkeys->key_type = CHAR;
  665.              pkeys->mask.m_char = 0;
  666.                  pkeys->cmp_function = cmp_char;
  667.                  break;
  668.       case F_UCHAR:  pkeys->key_type = UCHAR;
  669.              pkeys->mask.m_char = d3;
  670.                  if (d3)
  671.                pkeys->cmp_function = cmp_uchar_mask;
  672.                  else
  673.                pkeys->cmp_function = cmp_uchar;
  674.                  break;
  675.       case F_SHORT:  pkeys->key_type = SHORT;
  676.              pkeys->mask.m_short = 0;
  677.                  pkeys->cmp_function = cmp_short;
  678.                  break;
  679.       case F_USHORT: pkeys->key_type = USHORT;
  680.              pkeys->mask.m_short = d3;
  681.                  if (d3)
  682.                pkeys->cmp_function = cmp_ushort_mask;
  683.                  else
  684.                pkeys->cmp_function = cmp_ushort;
  685.                  break;
  686.       case F_LONG:   pkeys->key_type = LONG;
  687.              pkeys->mask.m_long = 0;
  688.                  pkeys->cmp_function = cmp_long;
  689.                  break;
  690.       case F_ULONG:  pkeys->key_type = ULONG;
  691.              pkeys->mask.m_long = d3;
  692.                  if (d3)
  693.                pkeys->cmp_function = cmp_ulong_mask;
  694.                  else
  695.                pkeys->cmp_function = cmp_ulong;
  696.                  break;
  697.       case F_FLOAT:  pkeys->key_type = FLOAT;
  698.                  pkeys->cmp_function = cmp_float;
  699.                  break;
  700.       case F_DOUBLE: pkeys->key_type = DOUBLE;
  701.                  pkeys->cmp_function = cmp_double;
  702.                  break;
  703.       default:       manual();
  704.                  fprintf(stderr, "binsort -- bad key type\n");
  705.                  my_exit(1);
  706.       }
  707.       ++pkeys;
  708.     }
  709. }
  710.  
  711.  
  712.  
  713. /*=============================================================*/
  714. static int
  715. readrun()             /*** Returns number of read (and sorted) records ***/
  716. {
  717.   static int          firsttimecalled = TRUE;  /* just a flag */
  718.   
  719.   register char  *prec, **pprec;
  720.   register int     numrec,         /* # of records read */
  721.                  i,              /* cycle paremater */
  722.                  fillsize;       /* # butes occupied by data */
  723.   
  724.   fillsize = fillworka();             /* fill (read into) area */
  725.   if (numrec = fillsize/actrecl) {    /* there are some records */
  726.     if (sortmode == RECORD_MODE)
  727.       sort(numrec, actrecl);
  728.     else
  729.       pointer_sort(numrec);
  730.   }
  731.   if (firsttimecalled) {
  732.     if (sortmode == RECORD_MODE) {
  733.       if (fillsize < actworkasz) {              /* merge necessary ? */
  734.     if (numrec = fillsize/actrecl) {    /* there are some records */
  735.       for (i = numrec, prec = workarea; i; --i, prec += actrecl)
  736.         if (fwrite(prec, sizeof(char), lrecl, stdout) != lrecl)
  737.           ioerr();
  738.       return(0);                            /* indicate end of data */
  739.     }
  740.       }
  741.     }
  742.     else {
  743.       if (((char *)workarea + fillsize) < (char *)pointer_area) { /* merge ? */
  744.     if (numrec = fillsize/actrecl) {    /* there are some records */
  745.       for (i = numrec, pprec = pointer_area; i; --i, ++pprec)
  746.         if (fwrite(*pprec, sizeof(char), lrecl, stdout) != lrecl)
  747.           ioerr();
  748.       return(0);                            /* indicate end of data */
  749.     }
  750.       }
  751.     }
  752.   }
  753.   firsttimecalled = FALSE;
  754.   return(numrec);
  755. }
  756.  
  757.  
  758. /*=====================================================================*/
  759. static int
  760. fillworka()    /* returns actual number of bytes occupated in workarea */
  761. {
  762.   register int    lng;
  763.   register char      *pw,             /* -> work area */
  764.   *pwe;            /* -> byte after work area */
  765.   register void     **ppointer;
  766.   
  767.   pw = (char *)workarea;
  768.   if (sortmode == RECORD_MODE)
  769.     pwe = pw + actworkasz;
  770.   else {
  771.     pwe = pointer_area;
  772.     ppointer = (void **)pointer_area;
  773.   }
  774.   
  775.   while (pw < pwe &&
  776.      (lng = fread((void *)pw, sizeof(char), lrecl, stdin)) == lrecl){
  777.     ++nrecs;
  778.     if (sortmode == POINTER_MODE)
  779.       *ppointer++ = (void *)pw;
  780.     pw += actrecl;
  781.   }
  782.   if (lng != lrecl && lng != 0)
  783.     proterr();
  784.   if (pw < pwe && !feof(stdin)) /* still free space and wrong input */
  785.     proterr();
  786.   if (f_verbose)
  787.     fprintf(stderr, "binsort -- %d bytes read into work area\n",
  788.         pw - (char *)workarea);
  789.   return(pw - (char *)workarea);
  790. }
  791.  
  792.  
  793. /*================================================================*/
  794. static void
  795. sort(nrecords, recsize)
  796. int          nrecords;
  797. int          recsize;
  798. {
  799.   qsort((void *)workarea, nrecords, recsize, cmproutine);
  800.   if (f_verbose)
  801.     fprintf(stderr, "binsort -- %d records sorted\n", nrecords);
  802. }
  803.  
  804.  
  805. /*================================================================*/
  806. static void
  807. pointer_sort(nrecords)
  808. int          nrecords;
  809. {
  810.   qsort(pointer_area, nrecords, sizeof(void *), pointer_cmproutine);
  811.   if (f_verbose)
  812.     fprintf(stderr, "binsort -- %d records sorted\n", nrecords);
  813. }
  814.  
  815. /*=================================================================*/
  816. static int
  817. cmproutine(e1, e2)
  818. void    *e1, *e2;           /* basics elements - records */
  819. {
  820.   register struct key_dsc      *pkey;
  821.   register int                  i, j;
  822.  
  823.   for (pkey = keys, i = nkeys; i; --i, ++pkey)
  824.     if (j = (*pkey->cmp_function)((char *)e1, (char *)e2, pkey))
  825.       return(pkey->asc_desc_order == ASC ? j : -j);
  826.   return(0);
  827. }
  828.  
  829.  
  830. /*=================================================================*/
  831. static int
  832. pointer_cmproutine(pe1, pe2)
  833. void      *pe1;
  834. void      *pe2;
  835. {
  836.   register struct key_dsc      *pkey;
  837.   register int                  i, j;
  838.  
  839.   for (pkey = keys, i = nkeys; i; --i, ++pkey)
  840.     if (j = (*pkey->cmp_function)(*((char **)pe1), *((char **)pe2), pkey))
  841.       return(pkey->asc_desc_order == ASC ? j : -j);
  842.   return(0);
  843. }
  844.  
  845.  
  846. /*=================================================================*/
  847. static int
  848. cmp_char(e1, e2, key)
  849. char            *e1, *e2;
  850. KEYDSC           key;
  851. {
  852.   register char      *p1, *p2;
  853.   register char          c1, c2;
  854.   register int        n;
  855.  
  856.   p1 = e1 + key->key_pos;
  857.   p2 = e2 + key->key_pos;
  858.  
  859.   for (n = key->key_length; n; --n, ++p1, ++p2)
  860.     if ((c1 = *p1) < (c2 = *p2))
  861.       return(-1);
  862.     else if (c1 > c2)
  863.       return(1);
  864.   return(0);
  865. }
  866.  
  867. static int
  868. cmp_uchar(e1, e2, key)
  869. char            *e1, *e2;
  870. KEYDSC           key;
  871. {
  872.   register unsigned char      *p1, *p2;
  873.   register unsigned char       c1, c2;
  874.   register int                 n;
  875.  
  876.   p1 = (unsigned char *)(e1 + key->key_pos);
  877.   p2 = (unsigned char *)(e2 + key->key_pos);
  878.  
  879.   for (n = key->key_length; n; --n, ++p1, ++p2)
  880.     if ((c1 = *p1) < (c2 = *p2))
  881.       return(-1);
  882.     else if (c1 > c2)
  883.       return(1);
  884.   return(0);
  885. }
  886.  
  887. static int
  888. cmp_uchar_mask(e1, e2, key)
  889. char            *e1, *e2;
  890. KEYDSC           key;
  891. {
  892.   register unsigned char      *p1, *p2;
  893.   register unsigned char       c1, c2;
  894.   register unsigned char       mask;
  895.   register int                 n;
  896.  
  897.   p1 = (unsigned char *)(e1 + key->key_pos);
  898.   p2 = (unsigned char *)(e2 + key->key_pos);
  899.   mask = key->mask.m_char;
  900.  
  901.   for (n = key->key_length; n; --n, ++p1, ++p2)
  902.     if ((c1 = *p1 & mask) < (c2 = *p2 & mask))
  903.       return(-1);
  904.     else if (c1 > c2)
  905.       return(1);
  906.   return(0);
  907. }
  908.  
  909. static int
  910. cmp_short(e1, e2, key)
  911. char            *e1, *e2;
  912. KEYDSC           key;
  913. {
  914.   register short     *p1, *p2;
  915.   register short      c1, c2;
  916.   register int        n;
  917.  
  918.   p1 = (short *)(e1 + key->key_pos);
  919.   p2 = (short *)(e2 + key->key_pos);
  920.  
  921.   for (n = key->key_length; n; --n, ++p1, ++p2)
  922.     if ((c1 = *p1) < (c2 = *p2))
  923.       return(-1);
  924.     else if (c1 > c2)
  925.       return(1);
  926.   return(0);
  927. }
  928.  
  929.  
  930. static int
  931. cmp_ushort(e1, e2, key)
  932. char            *e1, *e2;
  933. KEYDSC           key;
  934. {
  935.   register unsigned short     *p1, *p2;
  936.   register unsigned short      c1, c2;
  937.   register int                 n;
  938.  
  939.   p1 = (unsigned short *)(e1 + key->key_pos);
  940.   p2 = (unsigned short *)(e2 + key->key_pos);
  941.  
  942.   for (n = key->key_length; n; --n, ++p1, ++p2)
  943.     if ((c1 = *p1) < (c2 = *p2))
  944.       return(-1);
  945.     else if (c1 > c2)
  946.       return(1);
  947.   return(0);
  948. }
  949.  
  950.  
  951. static int
  952. cmp_ushort_mask(e1, e2, key)
  953. char            *e1, *e2;
  954. KEYDSC           key;
  955. {
  956.   register unsigned short     *p1, *p2;
  957.   register unsigned short      c1, c2;
  958.   register unsigned short      mask;
  959.   register int                 n;
  960.  
  961.   p1 = (unsigned short *)(e1 + key->key_pos);
  962.   p2 = (unsigned short *)(e2 + key->key_pos);
  963.   mask = key->mask.m_short;
  964.  
  965.   for (n = key->key_length; n; --n, ++p1, ++p2)
  966.     if ((c1 = *p1 & mask) < (c2 = *p2 & mask))
  967.       return(-1);
  968.     else if (c1 > c2)
  969.       return(1);
  970.   return(0);
  971. }
  972.  
  973.  
  974. static int
  975. cmp_long(e1, e2, key)
  976. char            *e1, *e2;
  977. KEYDSC           key;
  978. {
  979.   register long      *p1, *p2;
  980.   register long       c1, c2;
  981.   register int        n;
  982.  
  983.   p1 = (long *)(e1 + key->key_pos);
  984.   p2 = (long *)(e2 + key->key_pos);
  985.  
  986.   for (n = key->key_length; n; --n, ++p1, ++p2)
  987.     if ((c1 = *p1) < (c2 = *p2))
  988.       return(-1);
  989.     else if (c1 > c2)
  990.       return(1);
  991.   return(0);
  992. }
  993.  
  994.  
  995. static int
  996. cmp_ulong(e1, e2, key)
  997. char            *e1, *e2;
  998. KEYDSC           key;
  999. {
  1000.   register unsigned long      *p1, *p2;
  1001.   register unsigned long       c1, c2;
  1002.   register int                 n;
  1003.  
  1004.   p1 = (unsigned long *)(e1 + key->key_pos);
  1005.   p2 = (unsigned long *)(e2 + key->key_pos);
  1006.  
  1007.   for (n = key->key_length; n; --n, ++p1, ++p2)
  1008.     if ((c1 = *p1) < (c2 = *p2))
  1009.       return(-1);
  1010.     else if (c1 > c2)
  1011.       return(1);
  1012.   return(0);
  1013. }
  1014.  
  1015.  
  1016. static int
  1017. cmp_ulong_mask(e1, e2, key)
  1018. char            *e1, *e2;
  1019. KEYDSC           key;
  1020. {
  1021.   register unsigned long      *p1, *p2;
  1022.   register unsigned long       c1, c2;
  1023.   register unsigned long       mask;
  1024.   register int                 n;
  1025.  
  1026.   p1 = (unsigned long *)(e1 + key->key_pos);
  1027.   p2 = (unsigned long *)(e2 + key->key_pos);
  1028.   mask = key->mask.m_long;
  1029.  
  1030.   for (n = key->key_length; n; --n, ++p1, ++p2)
  1031.     if ((c1 = *p1 & mask) < (c2 = *p2 & mask))
  1032.       return(-1);
  1033.     else if (c1 > c2)
  1034.       return(1);
  1035.   return(0);
  1036. }
  1037.  
  1038.  
  1039. static int
  1040. cmp_float(e1, e2, key)
  1041. char            *e1, *e2;
  1042. KEYDSC           key;
  1043. {
  1044.   register float     *p1, *p2;
  1045.   register float      c1, c2;
  1046.   register float      n;
  1047.  
  1048.   p1 = (float *)(e1 + key->key_pos);
  1049.   p2 = (float *)(e2 + key->key_pos);
  1050.  
  1051.   for (n = key->key_length; n; --n, ++p1, ++p2)
  1052.     if ((c1 = *p1) < (c2 = *p2))
  1053.       return(-1);
  1054.     else if (c1 > c2)
  1055.       return(1);
  1056.   return(0);
  1057. }
  1058.  
  1059.  
  1060. static int
  1061. cmp_double(e1, e2, key)
  1062. char            *e1, *e2;
  1063. KEYDSC           key;
  1064. {
  1065.   register double    *p1, *p2;
  1066.   register double     c1, c2;
  1067.   register int        n;
  1068.  
  1069.   p1 = (double *)(e1 + key->key_pos);
  1070.   p2 = (double *)(e2 + key->key_pos);
  1071.  
  1072.   for (n = key->key_length; n; --n, ++p1, ++p2)
  1073.     if ((c1 = *p1) < (c2 = *p2))
  1074.       return(-1);
  1075.     else if (c1 > c2)
  1076.       return(1);
  1077.   return(0);
  1078. }
  1079.  
  1080.  
  1081.  
  1082. /*====================================================================*/
  1083. static void
  1084. proterr()            /* protocol error exit */
  1085. {
  1086.   fprintf(stderr, "binsort -- bad protocol, not fixed length records or\n");
  1087.   fprintf(stderr, "           bad keys\n");
  1088.   my_exit(1);
  1089. }
  1090.  
  1091.  
  1092. /*====================================================================*/
  1093. static void
  1094. ioerr()
  1095. {
  1096.   perror("binsort -- I/O error, f. computer or system");
  1097.   my_exit(1);
  1098. }
  1099.  
  1100.  
  1101. /*=====================================================================*/
  1102. static void
  1103. memoryerr()
  1104. {
  1105.   fprintf(stderr, "binsort -- Out of internal or external memory\n");
  1106.   fprintf(stderr, "           Use parameters to increase them\n");
  1107.   my_exit(1);
  1108. }
  1109.  
  1110. /*=====================================================================*/
  1111. static void
  1112. my_exit(status)
  1113. int     status;
  1114. {
  1115. fclose(stdin);
  1116. fclose(stdout);
  1117. fclose(stderr);
  1118. _exit(status);
  1119. }
  1120.  
  1121.  
  1122. /*=====================================================================*/
  1123. static void
  1124. printkeys()
  1125. {
  1126.   int             i, mask;
  1127.   struct key_dsc    *p;
  1128.   char                *ttype, *tasc;
  1129.  
  1130.   fputc('\n', stderr);
  1131.   fprintf(stderr, "binsort -- Max. internal memory  %d[B]\n", workasz);
  1132.   fprintf(stderr, "binsort -- Input record length   %d\n", lrecl);
  1133.   fprintf(stderr, "binsort -- key definitions:\n");
  1134.   for (i=0; i < nkeys;++i) {
  1135.     p = keys+i;
  1136.     mask = 0;
  1137.     switch (p->key_type) {
  1138.     case CHAR:    ttype = "char";
  1139.                 break;
  1140.     case UCHAR:    ttype = "uchar";
  1141.                 mask = p->mask.m_char;
  1142.                 break;
  1143.     case SHORT:    ttype = "short";
  1144.                 break;
  1145.     case USHORT:ttype = "ushort";
  1146.                 mask = p->mask.m_short;
  1147.                 break;
  1148.     case LONG:    ttype = "long";
  1149.                 break;
  1150.     case ULONG:    ttype= "ulong";
  1151.                 mask = p->mask.m_long;
  1152.                 break;
  1153.     case FLOAT:    ttype = "float";
  1154.                 break;
  1155.     case DOUBLE: ttype = "double";
  1156.                  break;
  1157.     }
  1158.     tasc = (p->asc_desc_order == ASC) ? "ascending" : "descending";
  1159.     fprintf(stderr,"           keytype %s order %s keypos %d keylng %d",
  1160.         ttype, tasc, p->key_pos, p->key_length);
  1161.     if (mask)
  1162.       fprintf(stderr, " mask %x", mask);
  1163.     fputc('\n', stderr);
  1164.   }
  1165.   fputc('\n', stderr);
  1166. }
  1167.  
  1168.  
  1169. /*=============================================================*/
  1170. static void
  1171. prtstatist(realtime)
  1172. long        realtime;
  1173. {
  1174.   struct tms    spenttime;
  1175.   int           tapenum;
  1176.   unsigned long one, total;
  1177.  
  1178.   fprintf(stderr,"\n\nbinsort statistics:\n");
  1179.   fprintf(stderr,"\tSorted records:\t\t\t%d\n", nrecs);
  1180.   fprintf(stderr,"\tInternal memory [bytes]:\t%d\n", actworkasz);
  1181.   fprintf(stderr,"\tScratch space used:\n");
  1182.   total = 0;
  1183.   for (tapenum = 1; tapenum <= 4; ++tapenum)
  1184.     if ((TAPE+tapenum)->fd != 0) {
  1185.       one = (unsigned long)lseek((TAPE+tapenum)->fd, 0L, SEEK_END);
  1186.       total += one;
  1187.       fprintf(stderr, "\t\ttape %2d: %10ld\n", tapenum, one);
  1188.     }
  1189.   fprintf(stderr,"\t\tTotal  : %10ld\n", total);
  1190.   fprintf(stderr,"\tReal time [s]:\t\t\t%d\n", (int)realtime + 1);
  1191.   times(&spenttime);
  1192.   fprintf(stderr,"\tUser time [s]:\t\t\t%.2f\n",
  1193.       (float)spenttime.tms_utime/(float)CLOCKFREQ);
  1194.   fprintf(stderr,"\tSystem time [s]:\t\t%.2f\n",
  1195.       (float)spenttime.tms_stime/(float)CLOCKFREQ);
  1196. }
  1197.  
  1198.  
  1199.  
  1200.  
  1201.  
  1202.  
  1203.  
  1204.  
  1205.  
  1206.  
  1207.  
  1208. /**************************************************************************
  1209.   merge
  1210.  
  1211. Polyphase merge sorting with "horizontal distribution"
  1212. implemented for T = 4, P = T-1 = 3
  1213. as published in:
  1214.          Donald E. Knuth: The Art of Computer Programming Vol.3
  1215.                           (Sorting and Searching) pp. 270-271
  1216.                           Addison-Wesley Publishing Company, Inc. (1973)
  1217.  
  1218. ***************************************************************************/
  1219. #define T                     4
  1220. #define P                     3
  1221.  
  1222.  
  1223. /*** 1st element of arrays is not used as indices start from 1 ***/
  1224.  
  1225. static int     j,         /* logical tape unit 1 <= j <= T */
  1226.                l,
  1227.                A [T+1],   /* The perfect Fibonacci distribution we are
  1228.                  striving for */
  1229.                D [T+1];   /* Number of dummy runs assumed to be present at
  1230.                  the beginning of logical tape unit number j */
  1231.  
  1232.  
  1233. static void
  1234. merge()
  1235. {
  1236.   register int        i, nrec, a;
  1237.   char               *pb;
  1238.   struct scratch_tape tmpTAPE;
  1239.   register int        tmpD;
  1240.  
  1241.  
  1242.   /*** My initialize ***/
  1243.   if ((nrec = readrun()) == 0)/* No records for merge */
  1244.     return;                   /* no merge phase necessary */
  1245.  
  1246.  /*D1:*** initialise ***/
  1247.   if (f_verbose)
  1248.     fprintf(stderr, "binsort -- disk merging started\n");
  1249.   for (j = 1; j < T; ++j) {
  1250.     A [j] = D [j] = 1;
  1251.     gettape(j);    /* open scratch file for TAPE [j] */
  1252.   }
  1253.   A [T] = D [T] = 0;
  1254.   gettape(T);
  1255.   l = j = 1;
  1256.  
  1257.  D2:/*** Input to tape j ***/
  1258.   writerun(j, nrec);
  1259.   ++((TAPE [j]).truns);
  1260.   --(D [j]);
  1261.   if ((nrec = readrun()) == 0) {      /* no aditional records */
  1262.     /*** Rewind tapes ***/
  1263.     for (i = 1, pb = workarea; i <= T; ++i, pb += scrbufsize) {
  1264.       (TAPE [i]).buf = pb;            /* allocate i/o buffer */
  1265.     rewindtape(i);                /* rewind tape */
  1266.     }
  1267.     goto D5;
  1268.   }
  1269.  
  1270. /*D3:*** Advance j ***/
  1271.   if (D [j] < D [j+1]) {
  1272.     ++j;
  1273.     goto D2;
  1274.   }
  1275.   else if (D [j] == 0)
  1276.     goto D4;
  1277.   else {
  1278.     j = 1;
  1279.     goto D2;
  1280.   }
  1281.  
  1282.  D4:/*** Up a level ***/
  1283.   ++l;
  1284.   a = A [1];
  1285.   for (j = 1; j <= P; ++j) {
  1286.     D [j] = a + A [j+1] - A [j];
  1287.     A [j] = a + A [j+1];
  1288.     }
  1289.   j = 1;
  1290.   goto D2;
  1291.  
  1292.  D5:/*** Merge ***/
  1293.   /*** this is an original algorithm version. It was modified, what results
  1294.        in saveing of rewriting TAPE [1] to output file
  1295.   if (l == 0) {
  1296.     *** write output from TAPE [1] ***
  1297.     return;                 *** end of merging ***
  1298.   }
  1299.   else
  1300.   ***************************************************************************/
  1301.   if (f_verbose)
  1302.     fprintf(stderr, "binsort -- merge level %d started\n", l);
  1303.   while (D [P] != 0 || (TAPE [P]).truns != 0) {
  1304.     for (j = 1; j <= P; ++j)
  1305.       if (!(D [j]))              /* all D [j] > 0 ? */
  1306.     break;
  1307.     if (j > P) {                 /* yes, all are greater */
  1308.       ++(D [T]);
  1309.       for (j = 1; j <= P; ++j)
  1310.     --(D [j]);
  1311.     }
  1312.     else                         /* no, at least one is not greater */
  1313.       mergeruns();               /* merge runs from tapes where D [j] == 0 */
  1314.   }
  1315.  
  1316.  /*D6:*** Down a level ***/
  1317.   --l;
  1318.   /*** This is algorithm modification mentioned above ***/
  1319.   if (l == 0)
  1320.     return;               /* end of merging */
  1321.   /******************************************************/
  1322.   /*** some small correction, rewind was moved several lines below ***
  1323.        rewindtape(P);
  1324.        rewindtape(T);
  1325.    ***                                                             ***/
  1326.   memcpy(&tmpTAPE, TAPE + T, sizeof(tmpTAPE));
  1327.   tmpD = D [T];
  1328.   for (i = T; i > 1; --i) {
  1329.     memcpy(TAPE + i, TAPE + i - 1, sizeof(tmpTAPE));
  1330.     D [i] = D [i-1];
  1331.   }
  1332.   memcpy(TAPE + 1, &tmpTAPE, sizeof(tmpTAPE));
  1333.   D [1] = tmpD;
  1334.   rewindtape(1);
  1335.   rewindtape(T);
  1336.   goto D5;
  1337. }
  1338.  
  1339.  
  1340. static void
  1341. mergeruns()
  1342. {
  1343.   register int         j;
  1344.   int                  newrunlng;
  1345.   int                  nmergeruns;       /* # of actual merged runs */
  1346.   struct scratch_tape *tapes [P+1],      /* tapes taken into account */
  1347.                       *ctape;            /* current tape */
  1348.  
  1349.   nmergeruns = newrunlng = 0;
  1350.   for (j = 1; j <= P; ++j) {
  1351.     if (D [j])                 /* this is a dummy run, which is discarded */
  1352.       --(D [j]);
  1353.     else {                            /* this is a real run and is merged */
  1354.       ++nmergeruns;
  1355.       ctape = tapes [nmergeruns] = TAPE + j;
  1356.       --(ctape->truns);            /* we shell process onre run from here */
  1357.       if ((read(ctape->fd, &(ctape->runlng), sizeof(int))) != sizeof(int))
  1358.     ioerr();
  1359.       ctape->pbuf = ctape->buf + scrbufsize;  /* mark buffer as exhausted */
  1360.       advancerunrec(ctape);
  1361.       newrunlng += ctape->runlng;
  1362.     }
  1363.   }
  1364.  
  1365.   /*** This is algorithm modification mentioned above ***/
  1366.   if (l > 1) {
  1367.     if (write((TAPE [T]).fd, &newrunlng, sizeof(int)) != sizeof(int))
  1368.       ioerr();
  1369.   }
  1370.  
  1371.   switch (nmergeruns) {
  1372.   case 1: merge1(tapes [1]);
  1373.           break;
  1374.   case 2: merge2(tapes [1], tapes [2]);
  1375.           break;
  1376.   case 3: merge3(tapes [1], tapes [2], tapes [3]);
  1377.           break;
  1378.   }
  1379.   flushrunbuf();                                 /* flush new run */
  1380.   ++((TAPE [T]).truns);                        /* update # of runs */
  1381. }
  1382.  
  1383.  
  1384. static void
  1385. merge1(p1)
  1386. struct scratch_tape *p1;
  1387. {
  1388.   /*** Just copies records from tape p1 into outfp ***/
  1389.  
  1390.   while (TRUE) {
  1391.     putrunrec(p1->pbuf);
  1392.     /*** Look if current input is exhausted ***/
  1393.     if (--(p1->runlng))
  1394.       /*** NO, advance tape ***/
  1395.       advancerunrec(p1);
  1396.     else
  1397.       /*** YES, merge is finished ***/
  1398.       return;
  1399.     }
  1400. }
  1401.  
  1402.  
  1403. static void
  1404. merge2(p1, p2)
  1405. struct scratch_tape  *p1, *p2;
  1406. {
  1407.   /*** Merges TWO runs (batches) from tapes p1, p2 into outfp      ***
  1408.    *** The algorithm simply swaps between inputs, so that current  ***
  1409.    *** is lower than other and then current is written into output ***
  1410.    *** If one of the runs is exhausted, merge1 is called           ***/
  1411.  
  1412.   register struct scratch_tape *current, *other, *tmp;
  1413.  
  1414.  
  1415.   current = p1;
  1416.   other = p2;
  1417.  
  1418.   do {
  1419.     if (cmproutine(current->pbuf, other->pbuf) <= 0)
  1420.       /*** current is lower, no swap ***/;
  1421.     else {
  1422.       /*** current is greater, swap current and other ***/
  1423.       tmp = current;
  1424.       current = other;
  1425.       other = tmp;
  1426.     }
  1427.  
  1428.     /*** Write current, which is now lower than other ***/
  1429.     putrunrec(current->pbuf);
  1430.     /*** Look if current input is exhausted ***/
  1431.     if (--(current->runlng))
  1432.       /*** NO, advance tape ***/
  1433.       advancerunrec(current);
  1434.     else {
  1435.       /*** YES, "merge just rest of the other run ***/
  1436.       merge1(other);
  1437.       return;
  1438.     }
  1439.   } while (TRUE);
  1440. }
  1441.  
  1442.  
  1443. static void
  1444. merge3(p1, p2, p3)
  1445. struct scratch_tape *p1, *p2, *p3;
  1446. {
  1447.   /*** Merges THREE runs (batches) from tapes p1, p2, p3 into output ***
  1448.    *** Algorithm maintains current record, greater of the other two  ***
  1449.    *** and lower of other two. Necessary comparisons involve swaps,  ***
  1450.    *** so than at the end the current is LOWER than lower and that   ***
  1451.    *** is lower than greater. If input from one of the three tapes   ***
  1452.    *** is exhausted, merge2 routine is called                        ***/
  1453.  
  1454.  
  1455.   register struct scratch_tape *current, *greater, *lower, *tmp;
  1456.  
  1457.   current = p1;
  1458.   if (cmproutine(p2->pbuf, p3->pbuf) <= 0) {
  1459.     lower = p2;
  1460.     greater = p3;
  1461.   }
  1462.   else {
  1463.     lower = p3;
  1464.     greater = p2;
  1465.   }
  1466.   
  1467.   do {
  1468.     if (cmproutine(current->pbuf, lower->pbuf) <= 0)
  1469.       ;
  1470.     else {
  1471.       tmp = lower;
  1472.       if (cmproutine(current->pbuf, greater->pbuf) <= 0) {
  1473.     lower = current;
  1474.     current = tmp;
  1475.       }
  1476.       else {
  1477.     lower = greater;
  1478.     greater = current;
  1479.     current = tmp;
  1480.       }
  1481.     }
  1482.     putrunrec(current->pbuf);
  1483.     if (--(current->runlng))
  1484.       advancerunrec(current);
  1485.     else {
  1486.       merge2(lower, greater);
  1487.       return;
  1488.     }
  1489.   } while (TRUE);
  1490. }
  1491.  
  1492.  
  1493. static void
  1494. gettape(num)
  1495. int     num;
  1496. {
  1497.   char                   scrname [500];
  1498.   int                    fdes;
  1499.   struct scratch_tape   *ctape;
  1500.   struct stat statstr;
  1501.  
  1502.   ctape = TAPE + num;
  1503.   sprintf(scrname, "%s/binsort%07d%d", scrpath, getpid(), num); /* gen name */
  1504.   if ((fdes = open(scrname, O_RDWR | O_CREAT, S_IREAD|S_IWRITE)) < 0)
  1505.                             /* create scratch file */
  1506.     ioerr();
  1507.   (void)fstat(fdes, &statstr);                               /* file status */
  1508.   if (!(statstr.st_mode & S_IFREG)) {
  1509.     fprintf(stderr, "binsort -- scratch is not a regular file\n");
  1510.     my_exit(1);
  1511.   }
  1512.   unlink(scrname);                         /* delete after close !!! */
  1513.   ctape->fd = fdes;                        /* file descriptor */
  1514.   ctape->truns = ctape->runlng = 0;        /* no runs on tape */
  1515.   ctape->buf = ctape->pbuf = (char *)NULL;
  1516. }
  1517.  
  1518. static void
  1519. rewindtape(num)
  1520. int          num;
  1521. {
  1522.   struct scratch_tape   *ctape;
  1523.  
  1524.   ctape = TAPE + num;
  1525.   (void)lseek(ctape->fd, 0L, SEEK_SET);
  1526.   if (num == T)
  1527.     ctape->pbuf = ctape->buf;               /* tape for write is empty */
  1528.   else
  1529.     ctape->pbuf = ctape->buf + scrbufsize;  /* tape for read in empty */
  1530. }
  1531.  
  1532.  
  1533. static void
  1534. writerun(num, nrec)
  1535. int          num;
  1536. int          nrec;
  1537. {
  1538.   register int          *pb, *pd;
  1539.   register int           j;
  1540.   register char        **pprec;
  1541.   register int           i;
  1542.   int                    lng_in_int;
  1543.   struct scratch_tape   *ctape;
  1544.   unsigned               bytelength;
  1545. # define            DSKBLK      2048
  1546.   char                   iob [DSKBLK];
  1547.  
  1548.   ctape = TAPE + num;
  1549.   if (write(ctape->fd, &nrec, sizeof(nrec)) == -1)   /* run length */
  1550.     ioerr();
  1551.   if (sortmode == RECORD_MODE) {
  1552.     bytelength = actrecl * nrec;
  1553.     if (write(ctape->fd, workarea, bytelength) == -1)  /* run */
  1554.       ioerr();
  1555.   }
  1556.   else {
  1557.     lng_in_int = actrecl / sizeof(int);
  1558.     pb = (int *)iob;
  1559.     for (i = nrec, pprec = pointer_area; i; --i, ++pprec) {
  1560.       for (pd = (int *)(*pprec), j = lng_in_int; j; --j) {
  1561.     if (pb == (int *)(iob + DSKBLK)) {                /* full disk block */
  1562.       if (write(ctape->fd, (void *)iob, DSKBLK) == -1)
  1563.         ioerr();
  1564.       pb = (int *)iob;
  1565.     }
  1566.     *pb++ = *pd++;
  1567.       }
  1568.     }
  1569.     if ((char *)pb != iob)           /* last piece of information in buffer */
  1570.       if (write(ctape->fd, (void *)iob, ((char *)pb - iob)) == -1)
  1571.         ioerr();
  1572.   }
  1573. }
  1574. /*
  1575.       if (write(ctape->fd, *pprec, actrecl) == -1)
  1576.     ioerr();
  1577. */
  1578.  
  1579.  
  1580. static void
  1581. advancerunrec(ctape)
  1582. struct scratch_tape      *ctape;
  1583. {
  1584.   register int            bread;
  1585.  
  1586.   ctape->pbuf += actrecl;
  1587.   if (ctape->pbuf >= ctape->buf + scrbufsize) {
  1588.     bread = (scrbufinrec < ctape->runlng) ? scrbufinrec : ctape->runlng;
  1589.     bread *= actrecl;
  1590.     if (read(ctape->fd, ctape->buf, bread) != bread)
  1591.       ioerr();
  1592.     ctape->pbuf = ctape->buf;
  1593.   }
  1594. }
  1595.  
  1596.  
  1597. void
  1598. putrunrec(rec)
  1599. char        *rec;
  1600. {
  1601.   register struct scratch_tape      *ctape;
  1602.  
  1603.   ctape = TAPE + T;
  1604.  
  1605.   /*** This is algorithm modification mentioned above ***/
  1606.   if (l == 1) {
  1607.     if (fwrite(rec, sizeof(char), lrecl, stdout) != lrecl)
  1608.       ioerr();
  1609.   }
  1610.   else {
  1611.     if (ctape->pbuf == (ctape->buf + scrbufsize))
  1612.       flushrunbuf();
  1613.     memcpy(ctape->pbuf, rec, actrecl);
  1614.     ctape->pbuf += actrecl;
  1615.     }
  1616. }
  1617.  
  1618.  
  1619. static void
  1620. flushrunbuf()
  1621. {
  1622.   register struct scratch_tape      *ctape;
  1623.   int                                size;
  1624.  
  1625.   ctape = TAPE + T;
  1626.   if (size = ctape->pbuf - ctape->buf) {
  1627.     if (write(ctape->fd, ctape->buf, size) != size)
  1628.       ioerr();
  1629.     ctape->pbuf = ctape->buf;
  1630.   }
  1631. }
  1632.  
  1633.  
  1634.  
  1635.  
  1636.  
  1637. /**********************
  1638. static void
  1639. testprint()
  1640. {
  1641.   register int      j;
  1642.  
  1643.   for (j = 1; j <= T; ++j) {
  1644.     fprintf(stderr,
  1645.       "j %3d l %3d A %3d D %3d TAPE %3d truns %3d runlng %3d\n",
  1646.         j, l, A[j], D[j], (TAPE+j)->fd, (TAPE+j)->truns, (TAPE+j)->runlng);
  1647.   }
  1648. }
  1649. ************************/
  1650.