home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / ddjmag / ddj8909.arc / PCBOARD.LST < prev    next >
File List  |  1989-07-27  |  66KB  |  2,172 lines
  1. PC BOARD LAYOUT SYSTEM TO ACCOMPANY _AUTOROUTING WITH THE A*
  2. ALGORITHM_ BY RANDY NEVIN, SEPTEMBER 1989, DDJ
  3.  
  4. [CELL.H]
  5.  
  6. /* the low-order bit indicates a hole */
  7. #define HOLE            0x00000001L    /* a conducting hole */
  8.  
  9. /* traces radiating outward from a hole to a side or corner */
  10. #define HOLE_NORTH        0x00000002L    /* upward        */
  11. #define HOLE_NORTHEAST        0x00000004L    /* upward and right    */
  12. #define HOLE_EAST        0x00000008L    /* to the right        */
  13. #define HOLE_SOUTHEAST        0x00000010L    /* downward and right    */
  14. #define HOLE_SOUTH        0x00000020L    /* downward        */
  15. #define HOLE_SOUTHWEST        0x00000040L    /* downward and left    */
  16. #define HOLE_WEST        0x00000080L    /* to the left        */
  17. #define HOLE_NORTHWEST        0x00000100L    /* upward and left    */
  18.  
  19. /* straight lines through the center */
  20. #define LINE_HORIZONTAL        0x00000002L    /* left-to-right line    */
  21. #define LINE_VERTICAL        0x00000004L    /* top-to-bottom line    */
  22.  
  23. /* lines cutting across a corner, connecting adjacent sides */
  24. #define CORNER_NORTHEAST    0x00000008L    /* upper right corner    */
  25. #define CORNER_SOUTHEAST    0x00000010L    /* lower right corner    */
  26. #define CORNER_SOUTHWEST    0x00000020L    /* lower left corner    */
  27. #define CORNER_NORTHWEST    0x00000040L    /* upper left corner    */
  28.  
  29. /* diagonal lines through the center */
  30. #define DIAG_NEtoSW        0x00000080L    /* northeast to southwest */
  31. #define DIAG_SEtoNW        0x00000100L    /* southeast to northwest */
  32.  
  33. /* 135 degree angle side-to-far-corner lines */
  34. #define BENT_NtoSE        0x00000200L    /* north to southeast    */
  35. #define BENT_NtoSW        0x00000400L    /* north to southwest    */
  36. #define BENT_EtoSW        0x00000800L    /* east to southwest    */
  37. #define BENT_EtoNW        0x00001000L    /* east to northwest    */
  38. #define BENT_StoNW        0x00002000L    /* south to northwest    */
  39. #define BENT_StoNE        0x00004000L    /* south to northeast    */
  40. #define BENT_WtoNE        0x00008000L    /* west to northeast    */
  41. #define BENT_WtoSE        0x00010000L    /* west to southeast    */
  42.  
  43. /* 90 degree corner-to-adjacent-corner lines */
  44. #define ANGLE_NEtoSE        0x00020000L    /* northeast to southeast */
  45. #define ANGLE_SEtoSW        0x00040000L    /* southeast to southwest */
  46. #define ANGLE_SWtoNW        0x00080000L    /* southwest to northwest */
  47. #define ANGLE_NWtoNE        0x00100000L    /* northwest to northeast */
  48.  
  49. /* 45 degree angle side-to-near-corner lines */
  50. #define SHARP_NtoNE        0x00200000L    /* north to northeast    */
  51. #define SHARP_EtoNE        0x00400000L    /* east to northeast    */
  52. #define SHARP_EtoSE        0x00800000L    /* east to southeast    */
  53. #define SHARP_StoSE        0x01000000L    /* south to southeast    */
  54. #define SHARP_StoSW        0x02000000L    /* south to southwest    */
  55. #define SHARP_WtoSW        0x04000000L    /* west to southwest    */
  56. #define SHARP_WtoNW        0x08000000L    /* west to northwest    */
  57. #define SHARP_NtoNW        0x10000000L    /* north to northwest    */
  58.  
  59. /* directions the cell can be reached from (point to previous cell) */
  60. #define FROM_NORTH        1
  61. #define FROM_NORTHEAST        2
  62. #define FROM_EAST        3
  63. #define FROM_SOUTHEAST        4
  64. #define FROM_SOUTH        5
  65. #define FROM_SOUTHWEST        6
  66. #define FROM_WEST        7
  67. #define FROM_NORTHWEST        8
  68. #define FROM_OTHERSIDE        9
  69.  
  70. #define    TOP    0
  71. #define BOTTOM    1
  72. #define EMPTY    0
  73. #define ILLEGAL    -1
  74.  
  75.  
  76. [ALLOC.C]
  77.  
  78. #include <stdio.h>
  79. #include <stdlib.h>
  80. #include <dos.h>
  81.  
  82. char far *Alloc( long );
  83. void Nomem( void );
  84.  
  85. char far *Alloc ( x ) /* allocate x bytes of far memory */
  86.     long x;
  87.     {
  88.     union REGS regs;
  89.  
  90.     regs.h.ah = 0x48; /* allocate memory dos call */
  91.     x = (x+15)>>4; /* get number of paragraphs to allocate */
  92.     regs.x.bx = (int)x;
  93.     intdos( ®s, ®s ); /* call dos; request memory */
  94.     if (regs.x.cflag) /* memory allocation error */
  95.         Nomem();
  96.     return( (char far *)((long)regs.x.ax<<16) ); /* make a far pointer */
  97.     }
  98.  
  99. void Nomem () { /* a memory allocation request has failed */
  100.     printf( "out of memory\n" );
  101.     exit( -1 );
  102.     }
  103.  
  104. [BOARD.C]
  105.  
  106. #include <stdio.h>
  107. #include <stdlib.h>
  108. #include "cell.h"
  109.  
  110. #define LIMIT    0x10000        /* 64k */
  111.  
  112. /* board dimensions */
  113. int Nrows = ILLEGAL;
  114. int Ncols = ILLEGAL;
  115.  
  116. int InitBoardDone = 0; /* sanity check */
  117.  
  118. /* memory usage */
  119. long Ltotal = 0; /* for board */
  120. long Itotal = 0; /* for dist */
  121. long Ctotal = 0; /* for dir */
  122.  
  123. /*
  124. ** memory is allocated in blocks of rows. as many rows as will fit in 64k are
  125. ** allocated in each block. blocks are linked together by pointers. the last
  126. ** block has a null 'next' pointer. if you want to route some *really* big
  127. ** boards (so big that 640k is not sufficient), you should change the
  128. ** algorithms below to test for Lotus-Intel-Microsoft expanded memory (LIM 3.2
  129. ** or 4.0) and use it if present. this would be a major enhancement, so if you
  130. ** do it i hope you will send it back to me so that it can be incorporated in
  131. ** future versions.
  132. */
  133.  
  134. struct lmem { /* a block of longs */
  135.     struct lmem far *next;     /* ptr to next block */
  136.     long         mem[1]; /* more than 1 is actually allocated */
  137.     };
  138.  
  139. struct imem { /* a block of ints */
  140.     struct imem far *next;     /* ptr to next block */
  141.     int         mem[1]; /* more than 1 is actually allocated */
  142.     };
  143.  
  144. struct cmem { /* a block of chars */
  145.     struct cmem far *next;     /* ptr to next block */
  146.     char         mem[1]; /* more than 1 is actually allocated */
  147.     };
  148.  
  149. struct lhead { /* header of blocks of longs */
  150.     int         numrows; /* number of rows per block */
  151.     struct lmem far *side[2]; /* ptr to first block of each chain */
  152.     };
  153.  
  154. struct ihead { /* header of blocks of ints */
  155.     int         numrows; /* number of rows per block */
  156.     struct imem far *side[2]; /* ptr to first block of each chain */
  157.     };
  158.  
  159. struct chead { /* header of blocks of chars */
  160.     int         numrows; /* number of rows per block */
  161.     struct cmem far *side[2]; /* ptr to first block of each chain */
  162.     };
  163.  
  164. static struct lhead Board = { 0, {NULL,NULL} }; /* 2-sided board */
  165. static struct ihead Dist = { 0, {NULL,NULL} }; /* path distance to cells */
  166. static struct chead Dir = { 0, {NULL,NULL} }; /* pointers back to source */
  167.  
  168. extern int justboard;
  169.  
  170. extern char far *Alloc( long );
  171.  
  172. void InitBoard( void );
  173. long GetCell( int, int, int );
  174. void SetCell( int, int, int, long );
  175. void OrCell( int, int, int, long );
  176. int GetDist( int, int, int );
  177. void SetDist( int, int, int, int );
  178. int GetDir( int, int, int );
  179. void SetDir( int, int, int, int );
  180.  
  181. void InitBoard () { /* initialize the data structures */
  182.     long lx, ly; /* for calculating block sizes */
  183.     struct lmem far * far *ltop;     /* for building board chain */
  184.     struct lmem far * far *lbottom;     /* for building board chain */
  185.     struct imem far * far *itop;     /* for building dist chain */
  186.     struct imem far * far *ibottom;     /* for building dist chain */
  187.     struct cmem far * far *ctop;     /* for building dir chain */
  188.     struct cmem far * far *cbottom;     /* for building dir chain */
  189.     int r, c, i, j, k; /* for calculating number of rows per block */
  190.  
  191.     InitBoardDone = 1; /* we have been called */
  192. /* allocate Board (longs) */
  193.     for (lx = (long)Ncols*sizeof(long), ly = 0, i = 0;
  194.         i < Nrows && ly <= LIMIT - sizeof(long far *); ly += lx, i++)
  195.         ; /* calculate maximum number of rows per block */
  196.     Board.numrows = --i;
  197.     ltop = &(Board.side[TOP]);
  198.     lbottom = &(Board.side[BOTTOM]);
  199.     for (j = Nrows; j > 0; j -= i) {
  200.         k = (j > i) ? i : j;
  201.         ly = ((long)k * lx) + sizeof(long far *);
  202.         *ltop = (struct lmem far *)Alloc( ly );
  203.         *lbottom = (struct lmem far *)Alloc( ly );
  204.         Ltotal += 2*ly;
  205.         ltop = (struct lmem far * far *)(*ltop);
  206.         lbottom = (struct lmem far * far *)(*lbottom);
  207.         }
  208.     *ltop = *lbottom = NULL;
  209.     if (!justboard) {
  210. /* allocate Dist (ints) */
  211.         for (lx = (long)Ncols*sizeof(int), ly = 0, i = 0;
  212.             i < Nrows && ly <= LIMIT - sizeof(int far *);
  213.             ly += lx, i++)
  214.             ; /* calculate maximum number of rows per block */
  215.         Dist.numrows = --i;
  216.         itop = &(Dist.side[TOP]);
  217.         ibottom = &(Dist.side[BOTTOM]);
  218.         for (j = Nrows; j > 0; j -= i) {
  219.             k = (j > i) ? i : j;
  220.             ly = ((long)k * lx) + sizeof(int far *);
  221.             *itop = (struct imem far *)Alloc( ly );
  222.             *ibottom = (struct imem far *)Alloc( ly );
  223.             Itotal += 2*ly;
  224.             itop = (struct imem far * far *)(*itop);
  225.             ibottom = (struct imem far * far *)(*ibottom);
  226.             }
  227.         *itop = *ibottom = NULL;
  228. /* allocate Dir (chars) */
  229.         for (lx = (long)Ncols*sizeof(char), ly = 0, i = 0;
  230.             i < Nrows && ly <= LIMIT - sizeof(char far *);
  231.             ly += lx, i++)
  232.             ; /* calculate maximum number of rows per block */
  233.         Dir.numrows = --i;
  234.         ctop = &(Dir.side[TOP]);
  235.         cbottom = &(Dir.side[BOTTOM]);
  236.         for (j = Nrows; j > 0; j -= i) {
  237.             k = (j > i) ? i : j;
  238.             ly = ((long)k * lx) + sizeof(char far *);
  239.             *ctop = (struct cmem far *)Alloc( ly );
  240.             *cbottom = (struct cmem far *)Alloc( ly );
  241.             Ctotal += 2*ly;
  242.             ctop = (struct cmem far * far *)(*ctop);
  243.             cbottom = (struct cmem far * far *)(*cbottom);
  244.             }
  245.         *ctop = *cbottom = NULL;
  246.         }
  247. /* initialize everything to empty */
  248.     for (r = 0; r < Nrows; r++) {
  249.         for (c = 0; c < Ncols; c++) {
  250.             SetCell( r, c, TOP, (long)EMPTY );
  251.             SetCell( r, c, BOTTOM, (long)EMPTY );
  252.             if (!justboard) {
  253.                 SetDist( r, c, TOP, EMPTY );
  254.                 SetDist( r, c, BOTTOM, EMPTY );
  255.                 SetDir( r, c, TOP, EMPTY );
  256.                 SetDir( r, c, BOTTOM, EMPTY );
  257.                 }
  258.             }
  259.         }
  260.     }
  261.  
  262. long GetCell( r, c, s ) /* fetch board cell */
  263.     int r, c, s;
  264.     {
  265.     struct lmem far *p;
  266.  
  267.     p = Board.side[s];
  268.     while (r >= Board.numrows) {
  269.         p = p->next;
  270.         r -= Board.numrows;
  271.         }
  272.     return( p->mem[r*Ncols+c] );
  273.     }
  274.  
  275. void SetCell( r, c, s, x ) /* store board cell */
  276.     int r, c, s;
  277.     long x;
  278.     {
  279.     struct lmem far *p;
  280.  
  281.     p = Board.side[s];
  282.     while (r >= Board.numrows) {
  283.         p = p->next;
  284.         r -= Board.numrows;
  285.         }
  286.     p->mem[r*Ncols+c] = x;
  287.     }
  288.  
  289. void OrCell( r, c, s, x ) /* augment board cell */
  290.     int r, c, s;
  291.     long x;
  292.     {
  293.     struct lmem far *p;
  294.  
  295.     p = Board.side[s];
  296.     while (r >= Board.numrows) {
  297.         p = p->next;
  298.         r -= Board.numrows;
  299.         }
  300.     p->mem[r*Ncols+c] |= x;
  301.     }
  302.  
  303. int GetDist( r, c, s ) /* fetch distance cell */
  304.     int r, c, s;
  305.     {
  306.     struct imem far *p;
  307.  
  308.     p = Dist.side[s];
  309.     while (r >= Dist.numrows) {
  310.         p = p->next;
  311.         r -= Dist.numrows;
  312.         }
  313.     return( p->mem[r*Ncols+c] );
  314.     }
  315.  
  316. void SetDist( r, c, s, x ) /* store distance cell */
  317.     int r, c, s, x;
  318.     {
  319.     struct imem far *p;
  320.  
  321.     p = Dist.side[s];
  322.     while (r >= Dist.numrows) {
  323.         p = p->next;
  324.         r -= Dist.numrows;
  325.         }
  326.     p->mem[r*Ncols+c] = x;
  327.     }
  328.  
  329. int GetDir( r, c, s ) /* fetch direction cell */
  330.     int r, c, s;
  331.     {
  332.     struct cmem far *p;
  333.  
  334.     p = Dir.side[s];
  335.     while (r >= Dir.numrows) {
  336.         p = p->next;
  337.         r -= Dir.numrows;
  338.         }
  339.     return( (int)(p->mem[r*Ncols+c]) );
  340.     }
  341.  
  342. void SetDir( r, c, s, x ) /* store direction cell */
  343.     int r, c, s, x;
  344.     {
  345.     struct cmem far *p;
  346.  
  347.     p = Dir.side[s];
  348.     while (r >= Dir.numrows) {
  349.         p = p->next;
  350.         r -= Dir.numrows;
  351.         }
  352.     p->mem[r*Ncols+c] = (char)x;
  353.     }
  354.  
  355.  
  356. [DIST.C]
  357.  
  358. #include <stdio.h>
  359. #include "cell.h"
  360.  
  361. int GetApxDist( int, int, int, int );
  362. int CalcDist( int, int, int );
  363.  
  364. int GetApxDist ( r1, c1, r2, c2 ) /* calculate approximate distance */
  365.     int r1, c1, r2, c2;
  366.     {
  367.     register int d1, d2; /* row and column deltas */
  368.     int d0; /* temporary variable for swapping d1 and d2 */
  369.  
  370.     /* NOTE: the -25 used below is because we are not going from the   */
  371.     /* center of (r1,c1) to the center of (r2,c2), we are going from   */
  372.     /* the edge of a hole at (r1,c1) to the edge of a hole at (r2,c2). */
  373.     /* holes are 25 mils in diameter (12.5 mils in radius), so we back */
  374.     /* off by 2 radii.                           */
  375.     if ((d1 = r1-r2) < 0) /* get absolute row delta */
  376.         d1 = -d1;
  377.     if ((d2 = c1-c2) < 0) /* get absolute column delta */
  378.         d2 = -d2;
  379.     if (!d1) /* in same row? */
  380.         return( (d2*50)-25 ); /* 50 mils per cell */
  381.     if (!d2) /* in same column? */
  382.         return( (d1*50)-25 ); /* 50 mils per cell */
  383.     if (d1 > d2) { /* get smaller into d1 */
  384.         d0 = d1;
  385.         d1 = d2;
  386.         d2 = d0;
  387.         }
  388.     d2 -= d1; /* get non-diagonal part of approximate "route" */
  389.     return( (d1*71)+(d2*50)-25 ); /* 71 mils diagonally per cell */
  390.     }
  391.  
  392. /* distance to go thru a cell */
  393. static int dist[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  394.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  395. /* N  */ { 50, 60, 35, 60, 99, 60, 35, 60,   12, 12 },
  396. /* NE */ { 60, 71, 60, 71, 60, 99, 60, 71,   23, 23 },
  397. /* E  */ { 35, 60, 50, 60, 35, 60, 99, 60,   12, 12 },
  398. /* SE */ { 60, 71, 60, 71, 60, 71, 60, 99,   23, 23 },
  399. /* S  */ { 99, 60, 35, 60, 50, 60, 35, 60,   12, 12 },
  400. /* SW */ { 60, 99, 60, 71, 60, 71, 60, 71,   23, 23 },
  401. /* W  */ { 35, 60, 99, 60, 35, 60, 50, 60,   12, 12 },
  402. /* NW */ { 60, 71, 60, 99, 60, 71, 60, 71,   23, 23 },
  403.  
  404. /* OT */ { 12, 23, 12, 23, 12, 23, 12, 23,   99, 99 },
  405. /* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 99 }
  406.     };
  407.  
  408. /* distance around (circular) segment of hole */
  409. static int circ[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  410.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  411. /* N  */ { 39, 29, 20, 10,  0, 10, 20, 29,   99, 0 },
  412. /* NE */ { 29, 39, 29, 20, 10,  0, 10, 20,   99, 0 },
  413. /* E  */ { 20, 29, 39, 29, 20, 10,  0, 10,   99, 0 },
  414. /* SE */ { 10, 20, 29, 39, 29, 20, 10,  0,   99, 0 },
  415. /* S  */ {  0, 10, 20, 29, 39, 29, 20, 10,   99, 0 },
  416. /* SW */ { 10,  0, 10, 20, 29, 39, 29, 20,   99, 0 },
  417. /* W  */ { 20, 10,  0, 10, 20, 29, 39, 29,   99, 0 },
  418. /* NW */ { 29, 20, 10,  0, 10, 20, 29, 39,   99, 0 },
  419.  
  420. /* OT */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 0 },
  421. /* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 0 }
  422.     };
  423.  
  424. /* penalty for extraneous holes and corners, scaled by sharpness of turn */
  425. static int penalty[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  426.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  427. /* N  */ {  0,  5, 10, 15, 20, 15, 10,  5,   50, 0 },
  428. /* NE */ {  5,  0,  5, 10, 15, 20, 15, 10,   50, 0 },
  429. /* E  */ { 10,  5,  0,  5, 10, 15, 20, 15,   50, 0 },
  430. /* SE */ { 15, 10,  5,  0,  5, 10, 15, 20,   50, 0 },
  431. /* S  */ { 20, 15, 10,  5,  0,  5, 10, 15,   50, 0 },
  432. /* SW */ { 15, 20, 15, 10,  5,  0,  5, 10,   50, 0 },
  433. /* W  */ { 10, 15, 20, 15, 10,  5,  0,  5,   50, 0 },
  434. /* NW */ {  5, 10, 15, 20, 15, 10,  5,  0,   50, 0 },
  435.  
  436. /* OT */ { 50, 50, 50, 50, 50, 50, 50, 50,  100, 0 },
  437. /* OR */ {  0,  0,  0,  0,  0,  0,  0,  0,    0, 0 }
  438.     };
  439.  
  440. /*
  441. ** x is the direction to enter the cell of interest.
  442. ** y is the direction to exit the cell of interest.
  443. ** z is the direction to really exit the cell, if y=FROM_OTHERSIDE.
  444. **
  445. ** return the distance of the trace through the cell of interest.
  446. ** the calculation is driven by the tables above.
  447. */
  448.  
  449. int CalcDist ( x, y, z ) /* calculate distance of a trace through a cell */
  450.     int x, y, z;
  451.     {
  452.     int adjust;
  453.  
  454.     adjust = 0; /* set if hole is encountered */
  455.     if (x == EMPTY)
  456.         x = 10;
  457.     if (y == EMPTY)
  458.         y = 10;
  459.     else if (y == FROM_OTHERSIDE) {
  460.         if (z == EMPTY)
  461.             z = 10;
  462.         adjust = circ[x-1][z-1] + penalty[x-1][z-1];
  463.         }
  464.     return( dist[x-1][y-1] + penalty[x-1][y-1] + adjust );
  465.     }
  466.  
  467.  
  468. [IO.C]
  469.  
  470. #include <stdio.h>
  471. #include <stdlib.h>
  472. #include <string.h>
  473. #include <malloc.h>
  474. #include <ctype.h>
  475. #include "cell.h"
  476.  
  477. /* board dimensions */
  478. extern int Nrows;
  479. extern int Ncols;
  480.  
  481. extern int InitBoardDone; /* sanity check */
  482.  
  483. /* memory usage */
  484. extern long Ltotal; /* for board */
  485. extern long Itotal; /* for dist */
  486. extern long Ctotal; /* for dir */
  487.  
  488. /*
  489. ** the following types of input lines are legal (spaces and tabs can separate
  490. ** tokens, and case is not significant):
  491. **
  492. **  1) a blank line (ignored)
  493. **  2) ';' followed by anything (ignored)
  494. **     use semicolon to insert comments.
  495. **  3) DIMENSION (row,column)
  496. **     this defines the number of rows and columns on the board, and must be
  497. **     given before any of the lines below. note that the user sees the board
  498. **     coordinate space as being 1-based, but internally it is 0-based.
  499. **  4) HOLE (row,column)
  500. **     this defines a hole location.
  501. **  5) CONNECT thing AND thing
  502. **     this declares that two holes are to be electrically connected. a thing
  503. **     can be (row,column), or name1.name2, where name1 is the name of a
  504. **     CHIPAT-defined chip, and name2 is the name of one of its pins, or a
  505. **     number, giving the pin number of the named chip. you can use '='
  506. **     instead of 'AND' if you want.
  507. **  6) PRIORITY CONNECT thing AND thing
  508. **     same as above, except the order of connections will be preserved. the
  509. **     autorouter is free to reorder the non-PRIORITY CONNECTs, and in fact
  510. **     reorders them shortest first. if there are PRIORITY CONNECTs, they will
  511. **     all be routed before non-PRIORITY CONNECTs.
  512. **  7) INCLUDE filename
  513. **     this causes the input to be temporarily taken from the given filename.
  514. **     when the given filename is completely processed (EOF encountered),
  515. **     control returns to the current file. INCLUDE statements may be nested
  516. **     (they may occur inside the given filename). complete and partial
  517. **     pathnames can be used (C:\TTL.INC, ..\TTL.INC, \TTL.INC, FOO\TTL.INC).
  518. **  8) CHIP TYPE=type PINS=number HORIZONTAL=number VERTICAL=number
  519. **     this declares a chip type, which can be used to place chips on the
  520. **     board (see CHIPAT, below), but does not itself place anything on the
  521. **     board. TYPE gives the name that will be used in later CHIPAT
  522. **     statements. PINS declares the number of pins. HORIZONTAL gives the
  523. **     number of 50-mil units separating adjacent pins (along the long side of
  524. **     the chip). and VERTICAL gives the number of 50-mil units separating
  525. **     pins across from each other (across the skinny width of the chip).
  526. **     standard values for HORIZONTAL and VERTICAL are 2 and 6, respectively.
  527. **     all CHIP type names must be unique.
  528. **  9) number=name
  529. **     this declares a pin name for the chip that is currently being defined.
  530. **     this statement must follow a CHIP statement. pins not defined will have
  531. **     no name, but you can still refer to them by number. each pin on a chip
  532. **     can be named at most once.
  533. ** 10) name=number
  534. **     same as above.
  535. ** 11) CHIPAT (row,column) NAME=name TYPE=type ORIENTATION=orientation
  536. **     this defines an instance of a chip, and places the appropriate holes on
  537. **     the board. (row,column) is the location of pin 1. NAME defines the name
  538. **     to be used in following CONNECT statements. TYPE declares the
  539. **     CHIPAT-defined type of the chip. ORIENTATION can have the values
  540. **     NORMAL, UP, DOWN, and UPSIDEDOWN. all CHIPAT names must be unique.
  541. **
  542. **      NORMAL           UP           DOWN        UPSIDEDOWN
  543. **
  544. **       6 5 4          +---+         +---+          3 2 1
  545. **     +-*-*-*-+      4 *   * 3     1 * | * 6      +-*-*-*-+
  546. **     |  ->   |      5 * ^ * 2     2 * v * 5      |   <-  |
  547. **     +-*-*-*-+      6 * | * 1     3 *   * 4      +-*-*-*-+
  548. **       1 2 3          +---+         +---+          4 5 6
  549. **
  550. **     usually the highest-numbered pin (pin N) is Vcc (power) and the pin
  551. **     farthest from it (pin N/2) is GND (ground).
  552. */
  553.  
  554. /* chip orientations (rotations) */
  555. #define ORIENT_NORMAL        1
  556. #define ORIENT_UP        2
  557. #define ORIENT_DOWN        3
  558. #define ORIENT_UPSIDEDOWN    4
  559.  
  560. /* input token types */
  561. #define TOK_EOF        1    /* end of file, no more tokens        */
  562. #define TOK_NEWLINE    2    /* end of line                */
  563. #define TOK_NUMBER    3    /* number (digits)            */
  564. #define TOK_HOLE    4    /* "HOLE"                */
  565. #define TOK_ROWCOLUMN    5    /* "(row,column)"            */
  566. #define TOK_CONNECT    6    /* "CONNECT"                */
  567. #define TOK_EQUAL    7    /* "="                    */
  568. #define TOK_AND        8    /* "AND"                */
  569. #define TOK_ALPHANUM    9    /* name (letters, digits, ':','.','\')    */
  570. #define TOK_CHIP    10    /* "CHIP"                */
  571. #define TOK_NAME    11    /* "NAME"                */
  572. #define TOK_PINS    12    /* "PINS"                */
  573. #define TOK_HORIZONTAL    13    /* "HORIZONTAL"                */
  574. #define TOK_VERTICAL    14    /* "VERTICAL"                */
  575. #define TOK_INCLUDE    15    /* "INCLUDE"                */
  576. #define TOK_CHIPAT    16    /* "CHIPAT"                */
  577. #define TOK_TYPE    17    /* "TYPE"                */
  578. #define TOK_ORIENTATION    18    /* "ORIENTATION"            */
  579. #define TOK_NORMAL    19    /* "NORMAL"                */
  580. #define TOK_UP        20    /* "UP"                    */
  581. #define TOK_DOWN    21    /* "DOWN"                */
  582. #define TOK_UPSIDEDOWN    22    /* "UPSIDEDOWN"                */
  583. #define TOK_DIMENSION    23    /* "DIMENSION"                */
  584. #define TOK_PRIORITY    24    /* "PRIORITY"                */
  585.  
  586. struct reserved { /* reserved word input tokens */
  587.     char *tokenname;
  588.     int tokenvalue;
  589.     };
  590.  
  591. static struct reserved tokenmatch[] = { /* reserved word table */
  592.   { "HOLE",       TOK_HOLE       },  { "CONNECT",     TOK_CONNECT     },
  593.   { "AND",        TOK_AND        },  { "CHIP",        TOK_CHIP        },
  594.   { "NAME",       TOK_NAME       },  { "PINS",        TOK_PINS        },
  595.   { "HORIZONTAL", TOK_HORIZONTAL },  { "VERTICAL",    TOK_VERTICAL    },
  596.   { "INCLUDE",    TOK_INCLUDE    },  { "CHIPAT",      TOK_CHIPAT      },
  597.   { "TYPE",       TOK_TYPE       },  { "ORIENTATION", TOK_ORIENTATION },
  598.   { "NORMAL",     TOK_NORMAL     },  { "UP",          TOK_UP          },
  599.   { "DOWN",       TOK_DOWN       },  { "UPSIDEDOWN",  TOK_UPSIDEDOWN  },
  600.   { "DIMENSION",  TOK_DIMENSION  },  { "PRIORITY",    TOK_PRIORITY    }
  601.  };
  602.  
  603. #define MAXTOK    80    /* maximum token length (including null) */
  604.  
  605. static int numres = sizeof(tokenmatch) / sizeof(tokenmatch[0]);
  606. static char token[MAXTOK]; /* the current token is formed here */
  607.  
  608. struct pinassign { /* for assigning names to pins */
  609.     int            index;
  610.     char far        *name;
  611.     struct pinassign far    *next;
  612.     };
  613.  
  614. struct template { /* for "CHIP" declarations */
  615.     char far        *type;
  616.     int            pins;
  617.     int            horizontal;
  618.     int            vertical;
  619.     struct pinassign far    *pinlist;
  620.     struct template far    *next;
  621.     };
  622.  
  623. struct instance { /* for "CHIPAT" definitions */
  624.     int            row;
  625.     int            column;
  626.     char far        *name;
  627.     struct template far    *type;
  628.     int            orientation;
  629.     struct instance far    *next;
  630.     };
  631.  
  632. static struct template far *chip = NULL; /* list of CHIPs */
  633. static struct instance far *chipat = NULL; /* list of CHIPATs */
  634.  
  635. extern void InitBoard( void );
  636. extern long GetCell( int, int, int );
  637. extern void SetCell( int, int, int, long );
  638. extern void InitWork( void );
  639. extern void SetWork( int, int, char far *, int, int, char far *, int );
  640. extern void SortWork( void );
  641. extern void Nomem( void );
  642.  
  643. void Initialize( FILE * );
  644. static void initfile( FILE * );
  645. static void initchip( struct instance far * );
  646. static void locate( char *, int *, int * );
  647. static int gettoken( FILE * );
  648. static char far *fcopy( char * );
  649. static int same( char far *, char far * );
  650. void Report( FILE * );
  651.  
  652. void Initialize ( fin ) /* get hole coordinates and connections */
  653.     FILE *fin;
  654.     {
  655.     printf( "enter Initialize()\n" );
  656.     InitWork(); /* clear work list */
  657.     initfile( fin ); /* read input file(s) */
  658.     SortWork(); /* arrange to do shortest ones first */
  659.     printf( "  %ld bytes used for board\n", Ltotal );
  660.     printf( "  %ld bytes used for dist\n", Itotal );
  661.     printf( "  %ld bytes used for dir\n", Ctotal );
  662.     printf( "leave Initialize()\n" );
  663.     }
  664.  
  665. /* some useful macros (common code sequences) */
  666.  
  667. #define SkipRest    { while ((tok = gettoken( fin )) != TOK_EOF \
  668.                 && tok != TOK_NEWLINE) ; }
  669.  
  670. #define SkipTokRest    { while (tok != TOK_EOF && tok != TOK_NEWLINE) \
  671.                 tok = gettoken( fin ); } \
  672.             continue;
  673.  
  674. #define CheckInit    { if (!InitBoardDone) { \
  675.                 printf( "error: need dimensions first\n" ); \
  676.                 SkipRest; \
  677.                 continue; } }
  678.  
  679. static void initfile ( fin ) /* read and process input file(s) */
  680.     FILE *fin;
  681.     {
  682.     int tok, r1, c1, r2, c2, i;
  683.     char far *p;
  684.     char far *n1;
  685.     char far *n2;
  686.     long cell;
  687.     struct template far *p1;
  688.     struct pinassign far *p2;
  689.     struct pinassign far *p22;
  690.     struct instance far *p3;
  691.     FILE *fnew;
  692.  
  693.     while ((tok = gettoken( fin )) != TOK_EOF) {
  694.         if (tok == TOK_DIMENSION) {
  695.             if (InitBoardDone) { /* can only do it once */
  696.                 printf( "error: redundant dimensions\n" );
  697.                 SkipRest;
  698.                 continue;
  699.                 }
  700.             if ((tok = gettoken( fin )) != TOK_ROWCOLUMN) {
  701.                 printf( "expect (row,column)\n" );
  702.                 SkipTokRest;
  703.                 }
  704.             sscanf( token, "(%d,%d)", &Nrows, &Ncols );
  705.             if (Nrows <= 0 || Ncols <= 0)
  706.                 printf( "dimension error\n" );
  707.             else /* allocate memory for data structures */
  708.                 InitBoard();
  709.             }
  710.         else if (tok == TOK_HOLE) {
  711.             CheckInit; /* must get dimensions first */
  712.             if ((tok = gettoken( fin )) != TOK_ROWCOLUMN) {
  713.                 printf( "expect (row,column)\n" );
  714.                 SkipTokRest;
  715.                 }
  716.             sscanf( token, "(%d,%d)", &r1, &c1 );
  717.             if (r1 <= 0 || r1 > Nrows || c1 <= 0 || c1 > Ncols)
  718.                 printf( "out of range\n" );
  719.             else { /* position the hole on the board */
  720.                 /* should check for neighbor holes (error) */
  721.                 SetCell( r1-1, c1-1, TOP, HOLE );
  722.                 SetCell( r1-1, c1-1, BOTTOM, HOLE );
  723.                 }
  724.             }
  725.         else if (tok == TOK_CONNECT) {
  726.             CheckInit; /* must get dimensions first */
  727.             if ((tok = gettoken( fin )) == TOK_ROWCOLUMN)
  728.                 sscanf( token, "(%d,%d)", &r1, &c1 );
  729.             else if (tok == TOK_ALPHANUM)
  730.                 locate( token, &r1, &c1 );
  731.             else {
  732.                 printf( "expect (row,column) or name\n" );
  733.                 SkipTokRest;
  734.                 }
  735.             n1 = fcopy( token );
  736.             if ((tok = gettoken( fin )) != TOK_EQUAL
  737.                 && tok != TOK_AND) {
  738.                 printf( "expect = or AND\n" );
  739.                 SkipTokRest;
  740.                 }
  741.             if ((tok = gettoken( fin )) == TOK_ROWCOLUMN)
  742.                 sscanf( token, "(%d,%d)", &r2, &c2 );
  743.             else if (tok == TOK_ALPHANUM)
  744.                 locate( token, &r2, &c2 );
  745.             else {
  746.                 printf( "expect (row,column) or name\n" );
  747.                 SkipTokRest;
  748.                 }
  749.             n2 = fcopy( token );
  750.             if (r1 <= 0 || r1 > Nrows || r2 <= 0 || r2 > Nrows
  751.                 || c1 <= 0 || c1 > Ncols
  752.                 || c2 <= 0 || c2 > Ncols) {
  753.                 printf( "out of range\n" );
  754.                 _ffree( n1 );
  755.                 _ffree( n2 );
  756.                 }
  757.             else {
  758.                 cell = GetCell( r1-1, c1-1, TOP );
  759.                 if (!(cell & HOLE)) {
  760.                     printf( "error: no source hole\n" );
  761.                     _ffree( n1 );
  762.                     _ffree( n2 );
  763.                     SkipRest;
  764.                     continue;
  765.                     }
  766.                 cell = GetCell( r2-1, c2-1, TOP );
  767.                 if (!(cell & HOLE)) {
  768.                     printf( "error: no target hole\n" );
  769.                     _ffree( n1 );
  770.                     _ffree( n2 );
  771.                     SkipRest;
  772.                     continue;
  773.                     }
  774.                 SetWork( r1-1, c1-1, n1, r2-1, c2-1, n2, 0 );
  775.                 }
  776.             }
  777.         else if (tok == TOK_PRIORITY) {
  778.             CheckInit; /* must get dimensions first */
  779.             if ((tok = gettoken( fin )) != TOK_CONNECT) {
  780.                 printf( "expect CONNECT\n" );
  781.                 SkipTokRest;
  782.                 }
  783.             if ((tok = gettoken( fin )) == TOK_ROWCOLUMN)
  784.                 sscanf( token, "(%d,%d)", &r1, &c1 );
  785.             else if (tok == TOK_ALPHANUM)
  786.                 locate( token, &r1, &c1 );
  787.             else {
  788.                 printf( "expect (row,column) or name\n" );
  789.                 SkipTokRest;
  790.                 }
  791.             n1 = fcopy( token );
  792.             if ((tok = gettoken( fin )) != TOK_EQUAL
  793.                 && tok != TOK_AND) {
  794.                 printf( "expect = or AND\n" );
  795.                 SkipTokRest;
  796.                 }
  797.             if ((tok = gettoken( fin )) == TOK_ROWCOLUMN)
  798.                 sscanf( token, "(%d,%d)", &r2, &c2 );
  799.             else if (tok == TOK_ALPHANUM)
  800.                 locate( token, &r2, &c2 );
  801.             else {
  802.                 printf( "expect (row,column) or name\n" );
  803.                 SkipTokRest;
  804.                 }
  805.             n2 = fcopy( token );
  806.             if (r1 <= 0 || r1 > Nrows || r2 <= 0 || r2 > Nrows
  807.                 || c1 <= 0 || c1 > Ncols
  808.                 || c2 <= 0 || c2 > Ncols) {
  809.                 printf( "out of range\n" );
  810.                 _ffree( n1 );
  811.                 _ffree( n2 );
  812.                 }
  813.             else {
  814.                 cell = GetCell( r1-1, c1-1, TOP );
  815.                 if (!(cell & HOLE)) {
  816.                     printf( "error: no source hole\n" );
  817.                     _ffree( n1 );
  818.                     _ffree( n2 );
  819.                     SkipRest;
  820.                     continue;
  821.                     }
  822.                 cell = GetCell( r2-1, c2-1, TOP );
  823.                 if (!(cell & HOLE)) {
  824.                     printf( "error: no target hole\n" );
  825.                     _ffree( n1 );
  826.                     _ffree( n2 );
  827.                     SkipRest;
  828.                     continue;
  829.                     }
  830.                 SetWork( r1-1, c1-1, n1, r2-1, c2-1, n2, 1 );
  831.                 }
  832.             }
  833.         else if (tok == TOK_INCLUDE) {
  834.             CheckInit; /* must get dimensions first */
  835.             if ((tok = gettoken( fin )) != TOK_ALPHANUM) {
  836.                 printf( "expect name for INCLUDE\n" );
  837.                 SkipTokRest;
  838.                 }
  839.             if (!(fnew = fopen( token, "r" ))) {
  840.                 printf( "can't open INCLUDE file %s\n",
  841.                     token );
  842.                 SkipRest;
  843.                 continue;
  844.                 }
  845.             if ((tok = gettoken( fin )) != TOK_EOF
  846.                 && tok != TOK_NEWLINE) {
  847.                 printf( "extra chars on INCLUDE line\n" );
  848.                 SkipRest;
  849.                 }
  850.             initfile( fnew ); /* recurse */
  851.             if (fclose( fnew ))
  852.                 printf( "error closing INCLUDE file\n" );
  853.             continue; /* already ate the NEWLINE, if any */
  854.             }
  855.         else if (tok == TOK_CHIP) {
  856.             CheckInit; /* must get dimensions first */
  857.             if ((tok = gettoken( fin )) != TOK_TYPE
  858.                 || (tok = gettoken( fin )) != TOK_EQUAL
  859.                 || (tok = gettoken( fin )) != TOK_ALPHANUM) {
  860.                 printf( "expect TYPE=type\n" );
  861.                 SkipTokRest;
  862.                 }
  863.             if (!(p1 = (struct template far *)
  864.                 _fmalloc( sizeof(struct template) )))
  865.                 Nomem();
  866.             p1->type = fcopy( token );
  867.             if ((tok = gettoken( fin )) != TOK_PINS
  868.                 || (tok = gettoken( fin )) != TOK_EQUAL
  869.                 || (tok = gettoken( fin )) != TOK_NUMBER) {
  870.                 printf( "expect PINS=number\n" );
  871.                 _ffree( p1->type );
  872.                 _ffree( p1 );
  873.                 SkipTokRest;
  874.                 }
  875.             sscanf( token, "%d", &i );
  876.             p1->pins = i;
  877.             if ((p1->pins = i) < 0 || (i & 1))
  878.                 printf( "PINS negative or odd\n" );
  879.             if ((tok = gettoken( fin )) != TOK_HORIZONTAL
  880.                 || (tok = gettoken( fin )) != TOK_EQUAL
  881.                 || (tok = gettoken( fin )) != TOK_NUMBER) {
  882.                 printf( "expect HORIZONTAL=number\n" );
  883.                 _ffree( p1->type );
  884.                 _ffree( p1 );
  885.                 SkipTokRest;
  886.                 }
  887.             sscanf( token, "%d", &i );
  888.             if ((p1->horizontal = i) <= 0)
  889.                 printf( "HORIZONTAL nonpositive\n" );
  890.             if ((tok = gettoken( fin )) != TOK_VERTICAL
  891.                 || (tok = gettoken( fin )) != TOK_EQUAL
  892.                 || (tok = gettoken( fin )) != TOK_NUMBER) {
  893.                 printf( "expect VERTICAL=number\n" );
  894.                 _ffree( p1->type );
  895.                 _ffree( p1 );
  896.                 SkipTokRest;
  897.                 }
  898.             sscanf( token, "%d", &i );
  899.             if ((p1->vertical = i) < 0)
  900.                 printf( "VERTICAL nonpositive\n" );
  901.             p1->pinlist = NULL;
  902.             p1->next = chip;
  903.             chip = p1;
  904.             }
  905.         else if (tok == TOK_NUMBER) {
  906.             CheckInit; /* must get dimensions first */
  907.             if (!chip) {
  908.                 printf( "no template\n" );
  909.                 SkipRest;
  910.                 continue;
  911.                 }
  912.             sscanf( token, "%d", &i );
  913.             if ((tok = gettoken( fin )) != TOK_EQUAL
  914.                 || (tok = gettoken( fin )) != TOK_ALPHANUM) {
  915.                 printf( "expect number=name\n" );
  916.                 SkipTokRest;
  917.                 }
  918.             if (!(p2 = (struct pinassign far *)
  919.                 _fmalloc( sizeof(struct pinassign) )))
  920.                 Nomem();
  921.             p2->name = fcopy( token );
  922.             p2->index = i;
  923.             /* check uniqueness of name and index */
  924.             for (p22 = chip->pinlist; p22; p22 = p22->next)
  925.                 if (p22->index == i
  926.                     || same( p22->name, p )) {
  927.                     printf( "warning: repeated pin\n" );
  928.                     break;
  929.                     }
  930.             p2->next = chip->pinlist;
  931.             chip->pinlist = p2;
  932.             }
  933.         else if (tok == TOK_ALPHANUM) {
  934.             CheckInit; /* must get dimensions first */
  935.             if (!chip) {
  936.                 printf( "no template\n" );
  937.                 SkipRest;
  938.                 continue;
  939.                 }
  940.             p = fcopy( token );
  941.             if ((tok = gettoken( fin )) != TOK_EQUAL
  942.                 || (tok = gettoken( fin )) != TOK_NUMBER) {
  943.                 printf( "expect name=number\n" );
  944.                 _ffree( p );
  945.                 SkipTokRest;
  946.                 }
  947.             sscanf( token, "%d", &i );
  948.             if (!(p2 = (struct pinassign far *)
  949.                 _fmalloc( sizeof(struct pinassign) )))
  950.                 Nomem();
  951.             p2->name = p;
  952.             p2->index = i;
  953.             /* check uniqueness of name and index */
  954.             for (p22 = chip->pinlist; p22; p22 = p22->next)
  955.                 if (p22->index == i
  956.                     || same( p22->name, p )) {
  957.                     printf( "warning: repeated pin\n" );
  958.                     break;
  959.                     }
  960.             p2->next = chip->pinlist;
  961.             chip->pinlist = p2;
  962.             }
  963.         else if (tok == TOK_CHIPAT) {
  964.             CheckInit; /* must get dimensions first */
  965.             if ((tok = gettoken( fin )) != TOK_ROWCOLUMN) {
  966.                 printf( "expect (row,column)\n" );
  967.                 SkipTokRest;
  968.                 }
  969.             sscanf( token, "(%d,%d)", &r1, &c1 );
  970.             if ((tok = gettoken( fin )) != TOK_NAME
  971.                 || (tok = gettoken( fin )) != TOK_EQUAL
  972.                 || (tok = gettoken( fin )) != TOK_ALPHANUM) {
  973.                 printf( "expect NAME=name\n" );
  974.                 SkipTokRest;
  975.                 }
  976.             if (!(p3 = (struct instance far *)
  977.                 _fmalloc( sizeof(struct instance) )))
  978.                 Nomem();
  979.             p3->name = fcopy( token );
  980.             p3->row = r1;
  981.             p3->column = c1;
  982.             if ((tok = gettoken( fin )) != TOK_TYPE
  983.                 || (tok = gettoken( fin )) != TOK_EQUAL
  984.                 || (tok = gettoken( fin )) != TOK_ALPHANUM) {
  985.                 printf( "expect TYPE=type\n" );
  986.                 _ffree( p3->name );
  987.                 _ffree( p3 );
  988.                 SkipTokRest;
  989.                 }
  990.             for (p3->type = chip; p3->type;
  991.                 p3->type = p3->type->next)
  992.                 if (same( token, p3->type->type ))
  993.                     break;
  994.             if (!(p3->type)) {
  995.                 printf( "couldn't find chip type\n" );
  996.                 _ffree( p3->name );
  997.                 _ffree( p3 );
  998.                 SkipTokRest;
  999.                 }
  1000.             if ((tok = gettoken( fin )) != TOK_ORIENTATION
  1001.                 || (tok = gettoken( fin )) != TOK_EQUAL
  1002.                 || ((tok = gettoken( fin )) != TOK_NORMAL
  1003.                 && tok != TOK_UP && tok != TOK_DOWN
  1004.                 && tok != TOK_UPSIDEDOWN)) {
  1005.                 printf( "expect ORIENTATION=orientation\n" );
  1006.                 _ffree( p3->name );
  1007.                 _ffree( p3 );
  1008.                 SkipTokRest;
  1009.                 }
  1010.             switch (tok) {
  1011.             case TOK_NORMAL:
  1012.                 p3->orientation = ORIENT_NORMAL;    break;
  1013.             case TOK_UP:
  1014.                 p3->orientation = ORIENT_UP;        break;
  1015.             case TOK_DOWN:
  1016.                 p3->orientation = ORIENT_DOWN;        break;
  1017.             case TOK_UPSIDEDOWN:
  1018.                 p3->orientation = ORIENT_UPSIDEDOWN;    break;
  1019.             default:
  1020.                 printf( "internal error\n" );
  1021.                 exit( -1 );
  1022.                 break;
  1023.                 }
  1024.             p3->next = chipat;
  1025.             chipat = p3;
  1026.             initchip( p3 );
  1027.             }
  1028.         else if (tok == TOK_NEWLINE)
  1029.             continue;
  1030.         else /* something unexpected */
  1031.             printf( "syntax error: unexpected input\n" );
  1032.         if ((tok = gettoken( fin )) != TOK_EOF && tok != TOK_NEWLINE) {
  1033.             printf( "syntax error: expected end of line\n" );
  1034.             SkipRest;
  1035.             }
  1036.         }
  1037.     }
  1038.  
  1039. static void initchip ( p ) /* initialize a chip definition (create holes) */
  1040.     struct instance far *p;
  1041.     {
  1042.     int r, c, pin;
  1043.     struct template far *t;
  1044.  
  1045.     pin = 1;
  1046.     r = p->row;
  1047.     c = p->column;
  1048.     t = p->type;
  1049.     /* should check for neighboring holes (warning if so) */
  1050.     switch (p->orientation) {
  1051.     case ORIENT_NORMAL:
  1052.         while (pin <= t->pins / 2) {
  1053.             SetCell( r-1, c-1, TOP, HOLE );
  1054.             SetCell( r-1, c-1, BOTTOM, HOLE );
  1055.             pin++;
  1056.             c += t->horizontal;
  1057.             }
  1058.         c -= t->horizontal;
  1059.         r += t->vertical;
  1060.         while (pin <= t->pins) {
  1061.             SetCell( r-1, c-1, TOP, HOLE );
  1062.             SetCell( r-1, c-1, BOTTOM, HOLE );
  1063.             pin++;
  1064.             c -= t->horizontal;
  1065.             }
  1066.         break;
  1067.     case ORIENT_UP:
  1068.         while (pin <= t->pins / 2) {
  1069.             SetCell( r-1, c-1, TOP, HOLE );
  1070.             SetCell( r-1, c-1, BOTTOM, HOLE );
  1071.             pin++;
  1072.             r += t->horizontal;
  1073.             }
  1074.         r -= t->horizontal;
  1075.         c -= t->vertical;
  1076.         while (pin <= t->pins) {
  1077.             SetCell( r-1, c-1, TOP, HOLE );
  1078.             SetCell( r-1, c-1, BOTTOM, HOLE );
  1079.             pin++;
  1080.             r -= t->horizontal;
  1081.             }
  1082.         break;
  1083.     case ORIENT_DOWN:
  1084.         while (pin <= t->pins / 2) {
  1085.             SetCell( r-1, c-1, TOP, HOLE );
  1086.             SetCell( r-1, c-1, BOTTOM, HOLE );
  1087.             pin++;
  1088.             r -= t->horizontal;
  1089.             }
  1090.         r += t->horizontal;
  1091.         c += t->vertical;
  1092.         while (pin <= t->pins) {
  1093.             SetCell( r-1, c-1, TOP, HOLE );
  1094.             SetCell( r-1, c-1, BOTTOM, HOLE );
  1095.             pin++;
  1096.             r += t->horizontal;
  1097.             }
  1098.         break;
  1099.     case ORIENT_UPSIDEDOWN:
  1100.         while (pin <= t->pins / 2) {
  1101.             SetCell( r-1, c-1, TOP, HOLE );
  1102.             SetCell( r-1, c-1, BOTTOM, HOLE );
  1103.             pin++;
  1104.             c -= t->horizontal;
  1105.             }
  1106.         c += t->horizontal;
  1107.         r -= t->vertical;
  1108.         while (pin <= t->pins) {
  1109.             SetCell( r-1, c-1, TOP, HOLE );
  1110.             SetCell( r-1, c-1, BOTTOM, HOLE );
  1111.             pin++;
  1112.             c += t->horizontal;
  1113.             }
  1114.         break;
  1115.     default:
  1116.         printf( "internal error: unexpected orientation\n" );
  1117.         exit( -1 );
  1118.         break;
  1119.         }
  1120.     }
  1121.  
  1122. static void locate ( p, r, c ) /* find location of name1.{name2,number} */
  1123.     char *p;
  1124.     int *r, *c;
  1125.     {
  1126.     char *q;
  1127.     int i;
  1128.     struct instance far *s;
  1129.     struct pinassign far *t;
  1130.  
  1131.     if (!(q = strchr( p, '.' ))) {
  1132.         printf( "expect name1.{name2,number}\n" );
  1133.         return;
  1134.         }
  1135.     *q++ = 0; /* separate into two parts & point at second part */
  1136.     for (s = chipat; s; s = s->next) /* find proper chip */
  1137.         if (same( p, s->name ))
  1138.             break;
  1139.     if (!s || !(s->type)) {
  1140.         printf( "can't find chip or chip type\n" );
  1141.         return;
  1142.         }
  1143.     if (isdigit( *q )) { /* get pin number */
  1144.         i = atoi( q );
  1145.         if (i <= 0 || i > s->type->pins) {
  1146.             printf( "pin out of range\n" );
  1147.             return;
  1148.             }
  1149.         }
  1150.     else { /* get index of named pin via the template */
  1151.         for (t = s->type->pinlist; t; t = t->next)
  1152.             if (same( q, t->name ))
  1153.                 break;
  1154.         if (!t) {
  1155.             printf( "can't find pin\n" );
  1156.             return;
  1157.             }
  1158.         i = t->index;
  1159.         }
  1160.     *r = s->row;
  1161.     *c = s->column;
  1162.     switch (s->orientation) {
  1163.     case ORIENT_NORMAL:
  1164.         if (i <= s->type->pins / 2)
  1165.             *c += (i-1) * s->type->horizontal;
  1166.         else {
  1167.             *r += s->type->vertical;
  1168.             *c += (s->type->pins - i) * s->type->horizontal;
  1169.             }
  1170.         break;
  1171.     case ORIENT_UP:
  1172.         if (i <= s->type->pins / 2)
  1173.             *r += (i-1) * s->type->horizontal;
  1174.         else {
  1175.             *c -= s->type->vertical;
  1176.             *r += (s->type->pins - i) * s->type->horizontal;
  1177.             }
  1178.         break;
  1179.     case ORIENT_DOWN:
  1180.         if (i <= s->type->pins / 2)
  1181.             *r -= (i-1) * s->type->horizontal;
  1182.         else {
  1183.             *c += s->type->vertical;
  1184.             *r -= (s->type->pins - i) * s->type->horizontal;
  1185.             }
  1186.         break;
  1187.     case ORIENT_UPSIDEDOWN:
  1188.         if (i <= s->type->pins / 2)
  1189.             *c -= (i-1) * s->type->horizontal;
  1190.         else {
  1191.             *r -= s->type->vertical;
  1192.             *c -= (s->type->pins - i) * s->type->horizontal;
  1193.             }
  1194.         break;
  1195.     default:
  1196.         printf( "internal error: unexpected orientation\n" );
  1197.         exit( -1 );
  1198.         break;
  1199.         }
  1200.     *--q = '.'; /* put back the separator */
  1201.     }
  1202.  
  1203. static int gettoken ( fin ) /* get next token into token[], return value */
  1204.     FILE *fin;
  1205.     {
  1206.     int ch, i;
  1207.  
  1208.     /* burn whitespace */
  1209.     while ((ch = getc( fin )) == ' ' || ch == '\t') ;
  1210.     if (ch == EOF)
  1211.         return( TOK_EOF );
  1212.     else if (ch == '\n')
  1213.         return( TOK_NEWLINE );
  1214.     else if (ch == ';') { /* comment; burn to end of line */
  1215.         while ((ch = getc( fin )) != EOF && ch != '\n') ;
  1216.         return( (ch == '\n') ? TOK_NEWLINE : TOK_EOF );
  1217.         }
  1218.     else if (ch == '=')
  1219.         return( TOK_EQUAL );
  1220.     else if (isdigit( ch )) { /* a number; move it to the buffer */
  1221.         i = 0;
  1222.         do {
  1223.             if (i < MAXTOK-1)
  1224.                 token[i++] = (char)ch;
  1225.             ch = getc( fin );
  1226.             } while (isdigit( ch ));
  1227.         token[i] = 0;
  1228.         if (ch != EOF)
  1229.             ungetc( ch, fin );
  1230.         return( TOK_NUMBER );
  1231.         }
  1232.     else if (isalpha( ch ) || ch == '.' || ch == '\\') {
  1233.         /* a name; move it to the buffer */
  1234.         i = 0;
  1235.         do {
  1236.             if (i < MAXTOK-1)
  1237.                 token[i++] = (char)ch;
  1238.             ch = getc( fin );
  1239.             } while (isalnum( ch ) || ch == ':' || ch == '.'
  1240.                 || ch == '\\');
  1241.         token[i] = 0;
  1242.         if (ch != EOF)
  1243.             ungetc( ch, fin );
  1244.         /* try to identify it as a reserved word */
  1245.         for (i = 0; i < numres; i++) /* search table */
  1246.             if (!stricmp( tokenmatch[i].tokenname, token ))
  1247.                 return( tokenmatch[i].tokenvalue );
  1248.         /* it's not a reserved word; just return it */
  1249.         strupr( token );
  1250.         return( TOK_ALPHANUM );
  1251.         }
  1252.     else if (ch == '(') { /* "(row,column)", move it to the buffer */
  1253.         token[0] = (char)ch;
  1254.         i = 1;
  1255.         while ((ch = getc( fin )) == ' ' || ch == '\t') ;
  1256.         if (!isdigit( ch )) {
  1257.             printf( "syntax error: expected digit\n" );
  1258.             exit( -1 );
  1259.             }
  1260.         do {
  1261.             if (i < MAXTOK-1)
  1262.                 token[i++] = (char)ch;
  1263.             ch = getc( fin );
  1264.             } while (isdigit( ch ));
  1265.         while (ch == ' ' || ch == '\t')
  1266.             ch = getc( fin );
  1267.         if (ch != ',') {
  1268.             printf( "syntax error: expected comma\n" );
  1269.             exit( -1 );
  1270.             }
  1271.         if (i < MAXTOK-1)
  1272.             token[i++] = (char)ch;
  1273.         while ((ch = getc( fin )) == ' ' || ch == '\t') ;
  1274.         if (!isdigit( ch )) {
  1275.             printf( "syntax error: expected digit\n" );
  1276.             exit( -1 );
  1277.             }
  1278.         do {
  1279.             if (i < MAXTOK-1)
  1280.                 token[i++] = (char)ch;
  1281.             ch = getc( fin );
  1282.             } while (isdigit( ch ));
  1283.         while (ch == ' ' || ch == '\t')
  1284.             ch = getc( fin );
  1285.         if (ch != ')') {
  1286.             printf( "syntax error: expected right paren\n" );
  1287.             exit( -1 );
  1288.             }
  1289.         if (i < MAXTOK-1)
  1290.             token[i++] = (char)ch;
  1291.         token[i] = 0;
  1292.         return( TOK_ROWCOLUMN );
  1293.         }
  1294.     else {
  1295.         printf( "syntax error: unrecognized token\n" );
  1296.         exit( -1 );
  1297.         }
  1298.     }
  1299.  
  1300. static char far *fcopy ( p ) /* return ptr to far string copy */
  1301.     char *p;
  1302.     {
  1303.     char far *q;
  1304.     char far *r;
  1305.  
  1306.     if (!(q = r = _fmalloc( strlen( p ) + 1 )))
  1307.         Nomem();
  1308.     while (*r++ = *p++) ; /* copy string */
  1309.     return( q );
  1310.     }
  1311.  
  1312. static int same ( p, q ) /* return 1 if far strings are identical, else 0 */
  1313.     char far *p;
  1314.     char far *q;
  1315.     {
  1316.     while (*p && *p == *q) { /* compare bytes until mismatch or end */
  1317.         p++;
  1318.         q++;
  1319.         }
  1320.     return( (*p || *q) ? 0 : 1 );
  1321.     }
  1322.  
  1323. void Report ( fout ) /* output routed board */
  1324.     FILE *fout;
  1325.     {
  1326.     int r, c;
  1327.     char b;
  1328.     long x;
  1329.  
  1330.     printf( "enter Report()\n" );
  1331.     /* output dimensions first */
  1332.     b = (char)Nrows;    putc( b, fout );
  1333.     b = (char)(Nrows>>8);    putc( b, fout );
  1334.     b = (char)Ncols;    putc( b, fout );
  1335.     b = (char)(Ncols>>8);    putc( b, fout );
  1336.     /* now do rows and columns */
  1337.     for (r = 0; r < Nrows; r++)
  1338.         for (c = 0; c < Ncols; c++) {
  1339.             x = GetCell( r, c, TOP ); /* first do frontside */
  1340.             b = (char)x;        putc( b, fout );
  1341.             b = (char)(x>>8);    putc( b, fout );
  1342.             b = (char)(x>>16);    putc( b, fout );
  1343.             b = (char)(x>>24);    putc( b, fout );
  1344.             x = GetCell( r, c, BOTTOM ); /* then do backside */
  1345.             b = (char)x;        putc( b, fout );
  1346.             b = (char)(x>>8);    putc( b, fout );
  1347.             b = (char)(x>>16);    putc( b, fout );
  1348.             b = (char)(x>>24);    putc( b, fout );
  1349.             }
  1350.     printf( "leave Report()\n" );
  1351.     }
  1352.  
  1353.  
  1354. [PCBROUTE.C]
  1355.  
  1356. /*
  1357. ** printed circuit board autorouter, Copyright (C) Randy Nevin 1989.
  1358. **
  1359. ** you may give this software to anyone, make as many copies as you like, and
  1360. ** post it on public computer bulletin boards and file servers. you may not
  1361. ** sell it or charge any fee for distribution (except for media and postage),
  1362. ** remove this comment or the copyright notice from the code, or claim that
  1363. ** you wrote this code or anything derived from it. you may modify the code as
  1364. ** much as you want (please document clearly with comments, and maintain the
  1365. ** coding style), but programs which are derived from this one are subject to
  1366. ** the conditions stated here. i am providing this code so that people can
  1367. ** learn from it, so if you distribute it, please include source code, not
  1368. ** just executables. contact me to report bugs or suggest enhancements; i do
  1369. ** not guarantee support, but i will make an effort in good faith to help you,
  1370. ** and i want to act as a central clearing house for future versions. you
  1371. ** should contact me before undertaking a significant development effort, to
  1372. ** avoid reinventing the wheel. if you come up with an enhancement you
  1373. ** consider particularly useful, i would appreciate being informed so that it
  1374. ** can be incorporated in future versions. my address is: Randy Nevin,
  1375. ** 1731 211th PL NE, Redmond, WA 98053. this code is available directly from
  1376. ** the author; just send a floppy and a self-addressed floppy mailer with
  1377. ** sufficient postage.
  1378. **
  1379. ** HISTORY
  1380. ** (name        date        description)
  1381. ** ----------------------------------------------------
  1382. ** randy nevin        2/1/89        initial version
  1383. ** randy nevin        2/4/89        made retrace table driven, instead of
  1384. **                    doubly-nested switch statements.
  1385. ** randy nevin        2/4/89        changed dir from int to char (cut
  1386. **                    storage for it in half).
  1387. ** randy nevin        2/8/89        changed SetQueue and ReSetQueue to
  1388. **                    give priority to goal nodes.
  1389. ** randy nevin        2/11/89        don't output incremental search
  1390. **                    results if stdout is redirected.
  1391. ** randy nevin        2/11/89        released version 1.00
  1392. */
  1393.  
  1394. #include <stdio.h>
  1395. #include <stdlib.h>
  1396. #include <io.h>
  1397. #include <time.h>
  1398. #include <string.h>
  1399. #include "cell.h"
  1400.  
  1401. /*
  1402. ** if you run out of memory while routing large boards, there are two things
  1403. ** you can do: (1) go into your config.sys file and disable everything you
  1404. ** don't need. getting rid of things like ansi.sys, ramdisks, disk caches, and
  1405. ** other terminate and stay resident (tsr) programs can free a lot of memory.
  1406. ** (2) link the router, inspect the .map file, relink with the /CPARMAXALLOC:n
  1407. ** switch, where n is calculated to allow for a near heap of about 5k. read
  1408. ** the linker documentation before you do thiions 
  1409.             sspinlikipR HOthe route.map file
  1410. ** says the program needs 81EFh bytes. to this i add 1400h (5k) for a near
  1411. ** heap to get 95EFh bytes or 95Fh paragraphs, which is 2399 decimal.
  1412. */
  1413.  
  1414. int justboard = 0; /* need all data structures, not just the board */
  1415.  
  1416. extern void Initialize( FILE * );
  1417. extern void Solve( void );
  1418. extern void Report( FILE * );
  1419.  
  1420. void main( int, char *[] );
  1421.  
  1422. void main ( argc, argv ) /* input board, route traces, output routed board */
  1423.     int argc;
  1424.     char *argv[];
  1425.     {
  1426.     char *self, *p;
  1427.     FILE *fin, *fout;
  1428.     long start, stop;
  1429.  
  1430.     printf( "Copyright (C) Randy Nevin, 1989. Version 1.00\n" );
  1431.     printf( "See source code for rights granted.\n\n" );
  1432.     start = time( NULL );
  1433.     self = argv[0];
  1434.     /* get rid of initial part of path */
  1435.     if ((p = strrchr( self, '\\' )) || (p = strrchr( self, ':' )))
  1436.         self = ++p;
  1437.     if (argc != 3) { /* need infile and outfile */
  1438.         printf( "usage: %s infile outfile\n", self );
  1439.         exit( -1 );
  1440.         }
  1441.     if (!(fin = fopen( argv[1], "r" ))) {
  1442.         printf( "can't open %s\n", argv[1] );
  1443.         exit( -1 );
  1444.         }
  1445.     if (!(fout = fopen( argv[2], "wb" ))) {
  1446.         printf( "can't open %s\n", argv[2] );
  1447.         exit( -1 );
  1448.         }
  1449.     Initialize( fin );
  1450.     Solve();
  1451.     Report( fout );
  1452.     stop = time( NULL ) - start;
  1453.     printf( "time = %ld second%s\n", stop, (stop == 1) ? "" : "s" );
  1454.     exit( 0 );
  1455.     }
  1456.  
  1457.  
  1458. [QUEUE.C]
  1459.  
  1460. #include <stdio.h>
  1461. #include <stdlib.h>
  1462. #include <malloc.h>
  1463. #include "cell.h"
  1464.  
  1465. struct queue { /* search queue structure */
  1466.     int Row;    /* current row                    */
  1467.     int Col;    /* current column                */
  1468.     int Side;    /* 0=top, 1=bottom                */
  1469.     int Dist;    /* path distance to this cell so far        */
  1470.     int ApxDist;    /* approximate distance to target from here    */
  1471.     struct queue far *Next;
  1472.     };
  1473.  
  1474. /* search statistics */
  1475. long OpenNodes = 0; /* total number of nodes opened */
  1476. long ClosNodes = 0; /* total number of nodes closed */
  1477. long MoveNodes = 0; /* total number of nodes moved */
  1478. long MaxNodes = 0; /* maximum number of nodes opened at one time */
  1479.  
  1480. static long qlen = 0; /* current queue length */
  1481.  
  1482. static struct queue far *Head = NULL;
  1483. static struct queue far *Tail = NULL;
  1484. static struct queue far *Save = NULL; /* hold empty queue structs */
  1485.  
  1486. extern void Nomem( void );
  1487.  
  1488. void InitQueue( void );
  1489. void GetQueue( int *, int *, int *, int *, int * );
  1490. void SetQueue( int, int, int, int, int, int, int );
  1491. void ReSetQueue( int, int, int, int, int, int, int );
  1492.  
  1493. void InitQueue () { /* initialize the search queue */
  1494.     struct queue far *p;
  1495.  
  1496.     while (p = Head) {
  1497.         Head = p->Next;
  1498.         p->Next = Save;
  1499.         Save = p;
  1500.         }
  1501.     Tail = NULL;
  1502.     OpenNodes = ClosNodes = MoveNodes = MaxNodes = qlen = 0;
  1503.     }
  1504.  
  1505. void GetQueue ( r, c, s, d, a ) /* get search queue item from list */
  1506.     int *r, *c, *s, *d, *a;
  1507.     {
  1508.     struct queue far *p;
  1509.  
  1510.     if (p = Head) { /* return first item in list */
  1511.         *r = p->Row;
  1512.         *c = p->Col;
  1513.         *s = p->Side;
  1514.         *d = p->Dist;
  1515.         *a = p->ApxDist;
  1516.         if (!(Head = p->Next))
  1517.             Tail = NULL;
  1518.         /* put node on free list */
  1519.         p->Next = Save;
  1520.         Save = p;
  1521.         ClosNodes++;
  1522.         qlen--;
  1523.         }
  1524.     else /* empty list */
  1525.         *r = *c = *s = *d = *a = ILLEGAL;
  1526.     }
  1527.  
  1528. void SetQueue ( r, c, s, d, a, r2, c2 ) /* add a search node to the list */
  1529.     int r, c, s, d, a, r2, c2;
  1530.     {
  1531.     struct queue far *p;
  1532.     struct queue far *q;
  1533.     struct queue far *t;
  1534.     register int i;
  1535.     int j;
  1536.  
  1537.     if (p = Save) /* try free list first */
  1538.         Save = p->Next;
  1539.     else if (!(p = (struct queue far *)_fmalloc( sizeof(struct queue) )))
  1540.         Nomem();
  1541.     p->Row = r;
  1542.     p->Col = c;
  1543.     p->Side = s;
  1544.     i = (p->Dist = d) + (p->ApxDist = a);
  1545.     p->Next = NULL;
  1546.     if (q = Head) { /* insert in proper position in list */
  1547.         if (q->Dist + q->ApxDist > i) { /* insert at head */
  1548.             p->Next = q;
  1549.             Head = p;
  1550.             }
  1551.         else { /* search for proper position */
  1552.             for (t = q, q = q->Next;
  1553.                 q && i > (j = q->Dist + q->ApxDist);
  1554.                 t = q, q = q->Next)
  1555.                 ;
  1556.             if (q && i == j && q->Row == r2 && q->Col == c2) {
  1557.                 /* insert after q, which is a goal node */
  1558.                 if (!(p->Next = q->Next))
  1559.                     Tail = p;
  1560.                 q->Next = p;
  1561.                 }
  1562.             else { /* insert in front of q */
  1563.                 if (!(p->Next = q))
  1564.                     Tail = p;
  1565.                 t->Next = p;
  1566.                 }
  1567.             }
  1568.         }
  1569.     else /* empty search list */
  1570.         Head = Tail = p;
  1571.     OpenNodes++;
  1572.     if (++qlen > MaxNodes)
  1573.         MaxNodes = qlen;
  1574.     }
  1575.  
  1576. void ReSetQueue ( r, c, s, d, a, r2, c2 ) /* reposition node in list */
  1577.     register int r, c;
  1578.     int s, d, a, r2, c2;
  1579.     {
  1580.     struct queue far *p;
  1581.     struct queue far *q;
  1582.  
  1583.     /* first, see if it is already in the list */
  1584.     for (q = NULL, p = Head; p; q = p, p = p->Next) {
  1585.         if (p->Row == r && p->Col == c && p->Side == s) {
  1586.             /* old one to remove */
  1587.             if (q) {
  1588.                 if (!(q->Next = p->Next))
  1589.                     Tail = q;
  1590.                 }
  1591.             else if (!(Head = p->Next))
  1592.                 Tail = NULL;
  1593.             p->Next = Save;
  1594.             Save = p;
  1595.             OpenNodes--;
  1596.             MoveNodes++;
  1597.             qlen--;
  1598.             break;
  1599.             }
  1600.         }
  1601.     /* if it was there, it's gone now; insert it at the proper position */
  1602.     SetQueue( r, c, s, d, a, r2, c2 );
  1603.     }
  1604.  
  1605.  
  1606.  
  1607. [SOLVE.C]
  1608.  
  1609. #include <stdio.h>
  1610. #include <stdlib.h>
  1611. #include <fcntl.h>
  1612. #include <io.h>
  1613. #include "cell.h"
  1614.  
  1615. /*
  1616. ** visit neighboring cells like this (where [9] is on the other side):
  1617. **
  1618. **    +---+---+---+
  1619. **    | 1 | 2 | 3 |
  1620. **    +---+---+---+
  1621. **    | 4 |[9]| 5 |
  1622. **    +---+---+---+
  1623. **    | 6 | 7 | 8 |
  1624. **    +---+---+---+
  1625. */
  1626.  
  1627. static int delta[8][2] = { /* for visiting neighbors on the same side */
  1628.      {  1, -1 }, /* northwest    */
  1629.      {  1,  0 }, /* north        */
  1630.      {  1,  1 }, /* northeast    */
  1631.      {  0, -1 }, /* west        */
  1632.      {  0,  1 }, /* east        */
  1633.      { -1, -1 }, /* southwest    */
  1634.      { -1,  0 }, /* south        */
  1635.      { -1,  1 }  /* southeast    */
  1636.     };
  1637.  
  1638. static int ndir[8] = { /* for building paths back to source */
  1639.      FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
  1640.      FROM_EAST,                  FROM_WEST,
  1641.      FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
  1642.     };
  1643.  
  1644. /* blocking masks for neighboring cells */
  1645. #define BLOCK_NORTHEAST        ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
  1646.                 | ANGLE_NEtoSE | ANGLE_NWtoNE \
  1647.                 | SHARP_NtoNE | SHARP_EtoNE )
  1648. #define BLOCK_SOUTHEAST        ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  1649.                 | ANGLE_NEtoSE | ANGLE_SEtoSW \
  1650.                 | SHARP_EtoSE | SHARP_StoSE )
  1651. #define BLOCK_SOUTHWEST        ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  1652.                 | ANGLE_SEtoSW | ANGLE_SWtoNW \
  1653.                 | SHARP_StoSW | SHARP_WtoSW )
  1654. #define BLOCK_NORTHWEST        ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  1655.                 | ANGLE_SWtoNW | ANGLE_NWtoNE \
  1656.                 | SHARP_WtoNW | SHARP_NtoNW )
  1657.  
  1658. struct block {
  1659.     int r1, c1;
  1660.     long b1, h1;
  1661.     int r2, c2;
  1662.     long b2, h2;
  1663.     };
  1664.  
  1665. static struct block blocking[8] = { /* blocking masks */
  1666.      {  0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  1667.         1,  0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
  1668.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  1669.      {  1,  0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  1670.         0,  1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  1671.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  1672.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  1673.      {  0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  1674.        -1,  0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  1675.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  1676.      { -1,  0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  1677.         0,  1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
  1678.     };
  1679.  
  1680. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  1681.      { 1, 1, 1, 1, 1, 1, 1, 1 },
  1682.      { 0, 0, 0, 0, 1, 0, 1, 0 },
  1683.      { 0, 0, 0, 1, 0, 0, 1, 0 },
  1684.      { 0, 1, 0, 0, 1, 0, 0, 0 },
  1685.      { 0, 1, 0, 1, 0, 0, 0, 0 }
  1686.     };
  1687.  
  1688. static long newmask[5][8] = { /* patterns to mask out in neighbor cells */
  1689.      { 0, 0, 0, 0, 0, 0, 0, 0 },
  1690.      { 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
  1691.         CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  1692.      { 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
  1693.         CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  1694.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
  1695.         CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
  1696.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
  1697.         CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
  1698.     };
  1699.  
  1700. static char fmt[] =
  1701.   "  open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";
  1702.  
  1703. /* board dimensions */
  1704. extern int Nrows;
  1705. extern int Ncols;
  1706.  
  1707. /* measures of progress */
  1708. int Ntotal = 0;
  1709. int Ncurrent = 0;
  1710.  
  1711. /* search statistics */
  1712. extern long OpenNodes; /* total number of nodes opened */
  1713. extern long ClosNodes; /* total number of nodes closed */
  1714. extern long MoveNodes; /* total number of nodes moved */
  1715. extern long MaxNodes; /* maximum number of nodes opened at one time */
  1716.  
  1717. extern void GetWork( int *, int *, char far * far *, int *, int *,
  1718.     char far * far * );
  1719. extern void InitQueue( void );
  1720. extern void GetQueue( int *, int *, int *, int *, int * );
  1721. extern void SetQueue( int, int, int, int, int, int, int );
  1722. extern void ReSetQueue( int, int, int, int, int, int, int );
  1723. extern long GetCell( int, int, int );
  1724. extern void SetCell( int, int, int, long );
  1725. extern void OrCell( int, int, int, long );
  1726. extern int GetDir( int, int, int );
  1727. extern void SetDir( int, int, int, int );
  1728. extern int GetDist( int, int, int );
  1729. extern void SetDist( int, int, int, int );
  1730. extern int GetApxDist( int, int, int, int );
  1731. extern int CalcDist( int, int, int );
  1732.  
  1733. void Solve( void );
  1734. void Retrace( int, int, int, int, int );
  1735.  
  1736. void Solve () { /* route all traces */
  1737.     int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
  1738.     register int i;
  1739.     char far *n1;
  1740.     char far *n2;
  1741.     long curcell, newcell, buddy, lastopen, lastclos, lastmove;
  1742.     int newdist, olddir, success, self, echo;
  1743.  
  1744.     printf( "enter Solve()\n" );
  1745.     echo = isatty( fileno(stdout) ) ? 1 : 0;
  1746.     /* go until no more work to do */
  1747.     for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
  1748.             GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
  1749.         Ncurrent++;
  1750.         printf( "routing %Fs=%Fs, %d of %d\n", n1, n2, Ncurrent,
  1751.             Ntotal );
  1752.         if (r1 == r2 && c1 == c2) /* trivial case; already routed */
  1753.             continue;
  1754.         success = 0;
  1755.         lastopen = lastclos = lastmove = 0;
  1756.         InitQueue(); /* initialize the search queue */
  1757.         a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
  1758.         SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  1759.         SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  1760.         /* search until success or we exhaust all possibilities */
  1761.         for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  1762.             GetQueue( &r, &c, &s, &d, &a )) {
  1763.             if (r == r2 && c == c2) { /* success! */
  1764.                 Retrace( r1, c1, r2, c2, s ); /* lay traces */
  1765.                 success++;
  1766.                 break;
  1767.                 }
  1768.             /* report every 100 new nodes or so */
  1769.             if (echo && (OpenNodes - lastopen > 100
  1770.                 || ClosNodes - lastclos > 100
  1771.                 || MoveNodes - lastmove > 100)) {
  1772.                 lastopen = (OpenNodes/100)*100;
  1773.                 lastclos = (ClosNodes/100)*100;
  1774.                 lastmove = (MoveNodes/100)*100;
  1775.                 printf( fmt, OpenNodes, ClosNodes,
  1776.                     MoveNodes, MaxNodes,
  1777.                     (ClosNodes*50)/(Nrows*Ncols) );
  1778.                 putchar( '\r' );
  1779.                 }
  1780.             curcell = GetCell( r, c, s );
  1781.             if (curcell & CORNER_NORTHWEST)
  1782.                 self = 1;
  1783.             else if (curcell & CORNER_NORTHEAST)
  1784.                 self = 2;
  1785.             else if (curcell & CORNER_SOUTHWEST)
  1786.                 self = 3;
  1787.             else if (curcell & CORNER_SOUTHEAST)
  1788.                 self = 4;
  1789.             else
  1790.                 self = 0;
  1791.             for (i = 0; i < 8; i++) { /* consider neighbors */
  1792.                 if (!selfok[self][i]) /* check self-block */
  1793.                     continue;
  1794.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  1795.                     || (nc = c+delta[i][1]) < 0
  1796.                     || nc >= Ncols) /* off the edge? */
  1797.                     continue;
  1798.                 newcell = GetCell( nr, nc, s );
  1799.                 /* check for non-target hole */
  1800.                 if (newcell & HOLE) {
  1801.                     if (nr != r2 || nc != c2)
  1802.                         continue;
  1803.                     }
  1804.                 else {
  1805.                     newcell &= ~(newmask[self][i]);
  1806.                     if (newcell) /* check for traces */
  1807.                         continue;
  1808.                     }
  1809.                 /* check blocking on corner neighbors */
  1810.                 if (delta[i][0] && delta[i][1]) {
  1811.                     /* check first buddy */
  1812.                     buddy = GetCell( r+blocking[i].r1,
  1813.                         c+blocking[i].c1, s );
  1814.                     if (buddy & HOLE) {
  1815.                         if (buddy & (blocking[i].h1))
  1816.                             continue;
  1817.                         }
  1818.                     else if (buddy & (blocking[i].b1))
  1819.                         continue;
  1820.                     /* check second buddy */
  1821.                     buddy = GetCell( r+blocking[i].r2,
  1822.                         c+blocking[i].c2, s );
  1823.                     if (buddy & HOLE) {
  1824.                         if (buddy & (blocking[i].h2))
  1825.                             continue;
  1826.                         }
  1827.                     else if (buddy & (blocking[i].b2))
  1828.                         continue;
  1829.                     }
  1830.                 olddir = GetDir( r, c, s );
  1831.                 newdist = d+CalcDist( ndir[i], olddir,
  1832.                     (olddir == FROM_OTHERSIDE)
  1833.                     ? GetDir( r, c, 1-s ) : 0 );
  1834.                 /* if not visited yet, add it to queue */
  1835.                 if (!GetDir( nr, nc, s )) {
  1836.                     SetDir( nr, nc, s, ndir[i] );
  1837.                     SetDist( nr, nc, s, newdist );
  1838.                     SetQueue( nr, nc, s, newdist,
  1839.                         GetApxDist( nr, nc, r2, c2 ),
  1840.                         r2, c2 );
  1841.                     }
  1842.                 /* we might have found a better path */
  1843.                 else if (newdist < GetDist( nr, nc, s )) {
  1844.                     SetDir( nr, nc, s, ndir[i] );
  1845.                     SetDist( nr, nc, s, newdist );
  1846.                     ReSetQueue( nr, nc, s, newdist,
  1847.                         GetApxDist( nr, nc, r2, c2 ),
  1848.                         r2, c2 );
  1849.                     }
  1850.                 }
  1851.             /* consider other side of board */
  1852.             /* check for holes or traces on other side */
  1853.             if (newcell = GetCell( r, c, 1-s ))
  1854.                 continue;
  1855.             skip = 0;
  1856.             /* check for nearby holes */
  1857.             for (i = 0; i < 8; i++) {
  1858.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  1859.                     || (nc = c+delta[i][1]) < 0
  1860.                     || nc >= Ncols) /* off the edge? */
  1861.                     continue;
  1862.                 if (GetCell( nr, nc, s ) & HOLE) {
  1863.                     skip = 1; /* neighboring hole */
  1864.                     break;
  1865.                     }
  1866.                 }
  1867.             if (skip) /* neighboring hole? */
  1868.                 continue; /* yes, can't drill one here */
  1869.             olddir = GetDir( r, c, s );
  1870.             newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
  1871.                 (olddir == FROM_OTHERSIDE)
  1872.                 ? GetDir( r, c, 1-s ) : 0 );
  1873.             /* if not visited yet, add it to queue */
  1874.             if (!GetDir( r, c, 1-s )) {
  1875.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  1876.                 SetDist( r, c, 1-s, newdist );
  1877.                 SetQueue( r, c, 1-s, newdist, a, r2, c2 );
  1878.                 }
  1879.             /* we might have found a better path */
  1880.             else if (newdist < GetDist( r, c, 1-s )) {
  1881.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  1882.                 SetDist( r, c, 1-s, newdist );
  1883.                 ReSetQueue( r, c, 1-s, newdist, a, r2, c2 );
  1884.                 }
  1885.             }
  1886.         printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
  1887.             (ClosNodes*50)/(Nrows*Ncols) );
  1888.         putchar( '\n' );
  1889.         if (!success)
  1890.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  1891.         /* clear direction flags */
  1892.         for (r = 0; r < Nrows; r++) {
  1893.             for (c = 0; c < Ncols; c++) {
  1894.                 SetDir( r, c, TOP, EMPTY );
  1895.                 SetDir( r, c, BOTTOM, EMPTY );
  1896.                 }
  1897.             }
  1898.         }
  1899.     printf( "leave Solve()\n" );
  1900.     }
  1901.  
  1902. static long bit[8][9] = { /* OT=Otherside */
  1903.      /* N, NE, E, SE, S, SW, W, NW, OT */
  1904. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
  1905.        SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
  1906. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
  1907.        0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
  1908. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  1909.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
  1910. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
  1911.        ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
  1912. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
  1913.        BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
  1914. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
  1915.        BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
  1916. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
  1917.        BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
  1918. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  1919.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
  1920.     };
  1921.  
  1922. void Retrace ( rr1, cc1, rr2, cc2, s )
  1923.     /* work from target back to source, actually laying the traces */
  1924.     int rr1, cc1, rr2, cc2, s; /* start on side s */
  1925.     {
  1926.     int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  1927.     register int x, y;
  1928.     long b;
  1929.  
  1930.     r1 = rr2;
  1931.     c1 = cc2;
  1932.     s1 = s;
  1933.     r0 = c0 = s0 = ILLEGAL;
  1934.     do {
  1935.         /* find where we came from to get here */
  1936.         switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  1937.         case FROM_NORTH:    r2++;        break;
  1938.         case FROM_EAST:            c2++;    break;
  1939.         case FROM_SOUTH:    r2--;        break;
  1940.         case FROM_WEST:            c2--;    break;
  1941.         case FROM_NORTHEAST:    r2++;    c2++;    break;
  1942.         case FROM_SOUTHEAST:    r2--;    c2++;    break;
  1943.         case FROM_SOUTHWEST:    r2--;    c2--;    break;
  1944.         case FROM_NORTHWEST:    r2++;    c2--;    break;
  1945.         case FROM_OTHERSIDE:    s2 = 1-s2;    break;
  1946.         default:
  1947.             printf( "internal error: no way back\n" );
  1948.             exit( -1 );
  1949.             break;
  1950.             }
  1951.         if (r0 != ILLEGAL)
  1952.             y = GetDir( r0, c0, s0 );
  1953.         /* see if target or hole */
  1954.         if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  1955.             switch (x) {
  1956.             case FROM_NORTH:
  1957.                 OrCell( r1, c1, s1, HOLE_NORTH );    break;
  1958.             case FROM_EAST:
  1959.                 OrCell( r1, c1, s1, HOLE_EAST );    break;
  1960.             case FROM_SOUTH:
  1961.                 OrCell( r1, c1, s1, HOLE_SOUTH );    break;
  1962.             case FROM_WEST:
  1963.                 OrCell( r1, c1, s1, HOLE_WEST );    break;
  1964.             case FROM_NORTHEAST:
  1965.                 OrCell( r1, c1, s1, HOLE_NORTHEAST );    break;
  1966.             case FROM_SOUTHEAST:
  1967.                 OrCell( r1, c1, s1, HOLE_SOUTHEAST );    break;
  1968.             case FROM_SOUTHWEST:
  1969.                 OrCell( r1, c1, s1, HOLE_SOUTHWEST );    break;
  1970.             case FROM_NORTHWEST:
  1971.                 OrCell( r1, c1, s1, HOLE_NORTHWEST );    break;
  1972.             case FROM_OTHERSIDE:
  1973.             default:
  1974.                 printf( "internal error\n" );
  1975.                 exit( -1 );
  1976.                 break;
  1977.                 }
  1978.             }
  1979.         else {
  1980.             if ((y == FROM_NORTH || y == FROM_NORTHEAST
  1981.                 || y == FROM_EAST || y == FROM_SOUTHEAST
  1982.                 || y == FROM_SOUTH || y == FROM_SOUTHWEST
  1983.                 || y == FROM_WEST || y == FROM_NORTHWEST)
  1984.                 && (x == FROM_NORTH || x == FROM_NORTHEAST
  1985.                 || x == FROM_EAST || x == FROM_SOUTHEAST
  1986.                 || x == FROM_SOUTH || x == FROM_SOUTHWEST
  1987.                 || x == FROM_WEST || x == FROM_NORTHWEST
  1988.                 || x == FROM_OTHERSIDE)
  1989.                 && (b = bit[y-1][x-1])) {
  1990.                 OrCell( r1, c1, s1, b );
  1991.                 if (b & HOLE)
  1992.                     OrCell( r2, c2, s2, HOLE );
  1993.                 }
  1994.             else {
  1995.                 printf( "internal error\n" );
  1996.                 exit( -1 );
  1997.                 }
  1998.             }
  1999.         if (r2 == rr1 && c2 == cc1) { /* see if source */
  2000.             switch (x) {
  2001.             case FROM_NORTH:
  2002.                 OrCell( r2, c2, s2, HOLE_SOUTH );    break;
  2003.             case FROM_EAST:
  2004.                 OrCell( r2, c2, s2, HOLE_WEST );    break;
  2005.             case FROM_SOUTH:
  2006.                 OrCell( r2, c2, s2, HOLE_NORTH );    break;
  2007.             case FROM_WEST:
  2008.                 OrCell( r2, c2, s2, HOLE_EAST );    break;
  2009.             case FROM_NORTHEAST:
  2010.                 OrCell( r2, c2, s2, HOLE_SOUTHWEST );    break;
  2011.             case FROM_SOUTHEAST:
  2012.                 OrCell( r2, c2, s2, HOLE_NORTHWEST );    break;
  2013.             case FROM_SOUTHWEST:
  2014.                 OrCell( r2, c2, s2, HOLE_NORTHEAST );    break;
  2015.             case FROM_NORTHWEST:
  2016.                 OrCell( r2, c2, s2, HOLE_SOUTHEAST );    break;
  2017.             case FROM_OTHERSIDE:
  2018.             default:
  2019.                 printf( "internal error\n" );
  2020.                 exit( -1 );
  2021.                 break;
  2022.                 }
  2023.             }
  2024.         /* move to next cell */
  2025.         r0 = r1; c0 = c1; s0 = s1;
  2026.         r1 = r2; c1 = c2; s1 = s2;
  2027.         } while (!(r2 == rr1 && c2 == cc1));
  2028.     }
  2029.  
  2030.  
  2031. [WORK.C]
  2032.  
  2033. #include <stdio.h>
  2034. #include <stdlib.h>
  2035. #include <malloc.h>
  2036. #include "cell.h"
  2037.  
  2038. struct work { /* a unit of work is a hole-pair to connect */
  2039.     int FromRow;        /* source row        */
  2040.     int FromCol;        /* source column    */
  2041.     char far *FromName;    /* source name        */
  2042.     int ToRow;        /* target row        */
  2043.     int ToCol;        /* target column    */
  2044.     char far *ToName;    /* target name        */
  2045.     int ApxDist;        /* approximate distance    */
  2046.     int Priority;        /* 0=no, 1=yes        */
  2047.     struct work far *Next;
  2048.     };
  2049.  
  2050. /* pointers to the first and last item of work to do */
  2051. static struct work far *Head = NULL;
  2052. static struct work far *Tail = NULL;
  2053.  
  2054. extern int Ntotal;
  2055.  
  2056. extern int GetApxDist( int, int, int, int );
  2057. extern void Nomem( void );
  2058.  
  2059. void InitWork( void );
  2060. void SetWork( int, int, char far *, int, int, char far *, int );
  2061. void GetWork( int *, int *, char far * far *, int *, int *, char far * far * );
  2062. void SortWork( void );
  2063.  
  2064. void InitWork () { /* initialize the work list */
  2065.     struct work far *p;
  2066.  
  2067.     while (p = Head) {
  2068.         Head = p->Next;
  2069.         _ffree( p );
  2070.         }
  2071.     Tail = NULL;
  2072.     }
  2073.  
  2074. void SetWork ( r1, c1, n1, r2, c2, n2, pri )
  2075.     /* add a unit of work to the work list */
  2076.     int r1, c1, r2, c2, pri;
  2077.     char far *n1;
  2078.     char far *n2;
  2079.     {
  2080.     struct work far *p;
  2081.  
  2082.     if (p = (struct work far *)_fmalloc( sizeof(struct work) )) {
  2083.         p->FromRow = r1;
  2084.         p->FromCol = c1;
  2085.         p->FromName = n1;
  2086.         p->ToRow = r2;
  2087.         p->ToCol = c2;
  2088.         p->ToName = n2;
  2089.         p->ApxDist = GetApxDist( r1, c1, r2, c2 );
  2090.         p->Priority = pri;
  2091.         p->Next = NULL;
  2092.         if (Head) /* attach at end */
  2093.             Tail->Next = p;
  2094.         else /* first in list */
  2095.             Head = p;
  2096.         Tail = p;
  2097.         Ntotal++;
  2098.         }
  2099.     else /* can't get any more memory */
  2100.         Nomem();
  2101.     }
  2102.  
  2103. void GetWork ( r1, c1, n1, r2, c2, n2 )
  2104.     /* fetch a unit of work from the work list */
  2105.     int *r1, *c1, *r2, *c2;
  2106.     char far * far *n1;
  2107.     char far * far *n2;
  2108.     {
  2109.     struct work far *p;
  2110.  
  2111.     if (p = Head) {
  2112.         *r1 = p->FromRow;
  2113.         *c1 = p->FromCol;
  2114.         *n1 = p->FromName;
  2115.         *r2 = p->ToRow;
  2116.         *c2 = p->ToCol;
  2117.         *n2 = p->ToName;
  2118.         if (!(Head = p->Next))
  2119.             Tail = NULL;
  2120.         _ffree( p );
  2121.         }
  2122.     else { /* none left */
  2123.         *r1 = *c1 = *r2 = *c2 = ILLEGAL;
  2124.         *n1 = *n2 = NULL;
  2125.         }
  2126.     }
  2127.  
  2128. void SortWork () { /* order the work items; shortest first */
  2129.     struct work far *p;
  2130.     struct work far *q0; /* put PRIORITY CONNECTs in q0 */
  2131.     struct work far *q1; /* sort other CONNECTs in q1 */
  2132.     struct work far *r;
  2133.  
  2134.     q0 = q1 = NULL;
  2135.     while (p = Head) { /* prioritize each work item */
  2136.         Head = Head->Next;
  2137.         if (p->Priority) {
  2138.             if (!(r = q0)) {
  2139.                 p->Next = q0;
  2140.                 q0 = p;
  2141.                 }
  2142.             else {
  2143.                 while (r->Next)
  2144.                     r = r->Next;
  2145.                 p->Next = r->Next;
  2146.                 r->Next = p;
  2147.                 }
  2148.             }
  2149.         else if (!(r = q1) || p->ApxDist < q1->ApxDist) {
  2150.             p->Next = q1;
  2151.             q1 = p;
  2152.             }
  2153.         else { /* find proper position in list */
  2154.             while (r->Next && p->ApxDist >= r->ApxDist)
  2155.                 r = r->Next;
  2156.             p->Next = r->Next;
  2157.             r->Next = p;
  2158.             }
  2159.         }
  2160.     if (p = q0) {
  2161.         while (q0->Next)
  2162.             q0 = q0->Next;
  2163.         q0->Next = q1;
  2164.         }
  2165.     else
  2166.         p = q1;
  2167.     /* reposition Head and Tail */
  2168.     for (Tail = Head = p; Tail && Tail->Next; Tail = Tail->Next)
  2169.         ;
  2170.     }
  2171.  
  2172.