Category : Files from Magazines
Archive   : DDJ0989.ZIP
Filename : PCBOARD.LST

PC BOARD LAYOUT SYSTEM TO ACCOMPANY _AUTOROUTING WITH THE A*
ALGORITHM_ BY RANDY NEVIN, SEPTEMBER 1989, DDJ

[CELL.H]

/* the low-order bit indicates a hole */
#define HOLE 0x00000001L /* a conducting hole */

/* traces radiating outward from a hole to a side or corner */
#define HOLE_NORTH 0x00000002L /* upward */
#define HOLE_NORTHEAST 0x00000004L /* upward and right */
#define HOLE_EAST 0x00000008L /* to the right */
#define HOLE_SOUTHEAST 0x00000010L /* downward and right */
#define HOLE_SOUTH 0x00000020L /* downward */
#define HOLE_SOUTHWEST 0x00000040L /* downward and left */
#define HOLE_WEST 0x00000080L /* to the left */
#define HOLE_NORTHWEST 0x00000100L /* upward and left */

/* straight lines through the center */
#define LINE_HORIZONTAL 0x00000002L /* left-to-right line */
#define LINE_VERTICAL 0x00000004L /* top-to-bottom line */

/* lines cutting across a corner, connecting adjacent sides */
#define CORNER_NORTHEAST 0x00000008L /* upper right corner */
#define CORNER_SOUTHEAST 0x00000010L /* lower right corner */
#define CORNER_SOUTHWEST 0x00000020L /* lower left corner */
#define CORNER_NORTHWEST 0x00000040L /* upper left corner */

/* diagonal lines through the center */
#define DIAG_NEtoSW 0x00000080L /* northeast to southwest */
#define DIAG_SEtoNW 0x00000100L /* southeast to northwest */

/* 135 degree angle side-to-far-corner lines */
#define BENT_NtoSE 0x00000200L /* north to southeast */
#define BENT_NtoSW 0x00000400L /* north to southwest */
#define BENT_EtoSW 0x00000800L /* east to southwest */
#define BENT_EtoNW 0x00001000L /* east to northwest */
#define BENT_StoNW 0x00002000L /* south to northwest */
#define BENT_StoNE 0x00004000L /* south to northeast */
#define BENT_WtoNE 0x00008000L /* west to northeast */
#define BENT_WtoSE 0x00010000L /* west to southeast */

/* 90 degree corner-to-adjacent-corner lines */
#define ANGLE_NEtoSE 0x00020000L /* northeast to southeast */
#define ANGLE_SEtoSW 0x00040000L /* southeast to southwest */
#define ANGLE_SWtoNW 0x00080000L /* southwest to northwest */
#define ANGLE_NWtoNE 0x00100000L /* northwest to northeast */

/* 45 degree angle side-to-near-corner lines */
#define SHARP_NtoNE 0x00200000L /* north to northeast */
#define SHARP_EtoNE 0x00400000L /* east to northeast */
#define SHARP_EtoSE 0x00800000L /* east to southeast */
#define SHARP_StoSE 0x01000000L /* south to southeast */
#define SHARP_StoSW 0x02000000L /* south to southwest */
#define SHARP_WtoSW 0x04000000L /* west to southwest */
#define SHARP_WtoNW 0x08000000L /* west to northwest */
#define SHARP_NtoNW 0x10000000L /* north to northwest */

/* directions the cell can be reached from (point to previous cell) */
#define FROM_NORTH 1
#define FROM_NORTHEAST 2
#define FROM_EAST 3
#define FROM_SOUTHEAST 4
#define FROM_SOUTH 5
#define FROM_SOUTHWEST 6
#define FROM_WEST 7
#define FROM_NORTHWEST 8
#define FROM_OTHERSIDE 9

#define TOP 0
#define BOTTOM 1
#define EMPTY 0
#define ILLEGAL -1


[ALLOC.C]

#include
#include
#include

char far *Alloc( long );
void Nomem( void );

char far *Alloc ( x ) /* allocate x bytes of far memory */
long x;
{
union REGS regs;

regs.h.ah = 0x48; /* allocate memory dos call */
x = (x+15)>>4; /* get number of paragraphs to allocate */
regs.x.bx = (int)x;
intdos( ®s, ®s ); /* call dos; request memory */
if (regs.x.cflag) /* memory allocation error */
Nomem();
return( (char far *)((long)regs.x.ax<<16) ); /* make a far pointer */
}

void Nomem () { /* a memory allocation request has failed */
printf( "out of memory\n" );
exit( -1 );
}

[BOARD.C]

#include
#include
#include "cell.h"

#define LIMIT 0x10000 /* 64k */

/* board dimensions */
int Nrows = ILLEGAL;
int Ncols = ILLEGAL;

int InitBoardDone = 0; /* sanity check */

/* memory usage */
long Ltotal = 0; /* for board */
long Itotal = 0; /* for dist */
long Ctotal = 0; /* for dir */


/*
** memory is allocated in blocks of rows. as many rows as will fit in 64k are
** allocated in each block. blocks are linked together by pointers. the last
** block has a null 'next' pointer. if you want to route some *really* big
** boards (so big that 640k is not sufficient), you should change the
** algorithms below to test for Lotus-Intel-Microsoft expanded memory (LIM 3.2
** or 4.0) and use it if present. this would be a major enhancement, so if you
** do it i hope you will send it back to me so that it can be incorporated in
** future versions.
*/

struct lmem { /* a block of longs */
struct lmem far *next; /* ptr to next block */
long mem[1]; /* more than 1 is actually allocated */
};

struct imem { /* a block of ints */
struct imem far *next; /* ptr to next block */
int mem[1]; /* more than 1 is actually allocated */
};

struct cmem { /* a block of chars */
struct cmem far *next; /* ptr to next block */
char mem[1]; /* more than 1 is actually allocated */
};

struct lhead { /* header of blocks of longs */
int numrows; /* number of rows per block */
struct lmem far *side[2]; /* ptr to first block of each chain */
};

struct ihead { /* header of blocks of ints */
int numrows; /* number of rows per block */
struct imem far *side[2]; /* ptr to first block of each chain */
};

struct chead { /* header of blocks of chars */
int numrows; /* number of rows per block */
struct cmem far *side[2]; /* ptr to first block of each chain */
};

static struct lhead Board = { 0, {NULL,NULL} }; /* 2-sided board */
static struct ihead Dist = { 0, {NULL,NULL} }; /* path distance to cells */
static struct chead Dir = { 0, {NULL,NULL} }; /* pointers back to source */

extern int justboard;

extern char far *Alloc( long );

void InitBoard( void );
long GetCell( int, int, int );
void SetCell( int, int, int, long );
void OrCell( int, int, int, long );
int GetDist( int, int, int );
void SetDist( int, int, int, int );
int GetDir( int, int, int );
void SetDir( int, int, int, int );

void InitBoard () { /* initialize the data structures */
long lx, ly; /* for calculating block sizes */
struct lmem far * far *ltop; /* for building board chain */
struct lmem far * far *lbottom; /* for building board chain */
struct imem far * far *itop; /* for building dist chain */
struct imem far * far *ibottom; /* for building dist chain */
struct cmem far * far *ctop; /* for building dir chain */
struct cmem far * far *cbottom; /* for building dir chain */
int r, c, i, j, k; /* for calculating number of rows per block */

InitBoardDone = 1; /* we have been called */
/* allocate Board (longs) */
for (lx = (long)Ncols*sizeof(long), ly = 0, i = 0;
i < Nrows && ly <= LIMIT - sizeof(long far *); ly += lx, i++)
; /* calculate maximum number of rows per block */
Board.numrows = --i;
ltop = &(Board.side[TOP]);
lbottom = &(Board.side[BOTTOM]);
for (j = Nrows; j > 0; j -= i) {
k = (j > i) ? i : j;
ly = ((long)k * lx) + sizeof(long far *);
*ltop = (struct lmem far *)Alloc( ly );
*lbottom = (struct lmem far *)Alloc( ly );
Ltotal += 2*ly;
ltop = (struct lmem far * far *)(*ltop);
lbottom = (struct lmem far * far *)(*lbottom);
}
*ltop = *lbottom = NULL;
if (!justboard) {
/* allocate Dist (ints) */
for (lx = (long)Ncols*sizeof(int), ly = 0, i = 0;
i < Nrows && ly <= LIMIT - sizeof(int far *);
ly += lx, i++)
; /* calculate maximum number of rows per block */
Dist.numrows = --i;
itop = &(Dist.side[TOP]);
ibottom = &(Dist.side[BOTTOM]);
for (j = Nrows; j > 0; j -= i) {
k = (j > i) ? i : j;
ly = ((long)k * lx) + sizeof(int far *);
*itop = (struct imem far *)Alloc( ly );
*ibottom = (struct imem far *)Alloc( ly );
Itotal += 2*ly;
itop = (struct imem far * far *)(*itop);
ibottom = (struct imem far * far *)(*ibottom);
}
*itop = *ibottom = NULL;
/* allocate Dir (chars) */
for (lx = (long)Ncols*sizeof(char), ly = 0, i = 0;
i < Nrows && ly <= LIMIT - sizeof(char far *);
ly += lx, i++)
; /* calculate maximum number of rows per block */
Dir.numrows = --i;
ctop = &(Dir.side[TOP]);
cbottom = &(Dir.side[BOTTOM]);
for (j = Nrows; j > 0; j -= i) {
k = (j > i) ? i : j;
ly = ((long)k * lx) + sizeof(char far *);
*ctop = (struct cmem far *)Alloc( ly );
*cbottom = (struct cmem far *)Alloc( ly );
Ctotal += 2*ly;
ctop = (struct cmem far * far *)(*ctop);
cbottom = (struct cmem far * far *)(*cbottom);
}
*ctop = *cbottom = NULL;
}
/* initialize everything to empty */
for (r = 0; r < Nrows; r++) {
for (c = 0; c < Ncols; c++) {
SetCell( r, c, TOP, (long)EMPTY );
SetCell( r, c, BOTTOM, (long)EMPTY );
if (!justboard) {
SetDist( r, c, TOP, EMPTY );
SetDist( r, c, BOTTOM, EMPTY );
SetDir( r, c, TOP, EMPTY );
SetDir( r, c, BOTTOM, EMPTY );
}
}
}
}

long GetCell( r, c, s ) /* fetch board cell */
int r, c, s;
{
struct lmem far *p;

p = Board.side[s];
while (r >= Board.numrows) {
p = p->next;
r -= Board.numrows;
}
return( p->mem[r*Ncols+c] );
}

void SetCell( r, c, s, x ) /* store board cell */
int r, c, s;
long x;
{
struct lmem far *p;

p = Board.side[s];
while (r >= Board.numrows) {
p = p->next;
r -= Board.numrows;
}
p->mem[r*Ncols+c] = x;
}

void OrCell( r, c, s, x ) /* augment board cell */
int r, c, s;
long x;
{
struct lmem far *p;

p = Board.side[s];
while (r >= Board.numrows) {
p = p->next;
r -= Board.numrows;
}
p->mem[r*Ncols+c] |= x;
}

int GetDist( r, c, s ) /* fetch distance cell */
int r, c, s;
{
struct imem far *p;

p = Dist.side[s];
while (r >= Dist.numrows) {
p = p->next;
r -= Dist.numrows;
}
return( p->mem[r*Ncols+c] );
}

void SetDist( r, c, s, x ) /* store distance cell */
int r, c, s, x;
{
struct imem far *p;

p = Dist.side[s];
while (r >= Dist.numrows) {
p = p->next;
r -= Dist.numrows;
}
p->mem[r*Ncols+c] = x;
}

int GetDir( r, c, s ) /* fetch direction cell */
int r, c, s;
{
struct cmem far *p;

p = Dir.side[s];
while (r >= Dir.numrows) {
p = p->next;
r -= Dir.numrows;
}
return( (int)(p->mem[r*Ncols+c]) );
}

void SetDir( r, c, s, x ) /* store direction cell */
int r, c, s, x;
{
struct cmem far *p;

p = Dir.side[s];
while (r >= Dir.numrows) {
p = p->next;
r -= Dir.numrows;
}
p->mem[r*Ncols+c] = (char)x;
}


[DIST.C]

#include
#include "cell.h"

int GetApxDist( int, int, int, int );
int CalcDist( int, int, int );

int GetApxDist ( r1, c1, r2, c2 ) /* calculate approximate distance */
int r1, c1, r2, c2;
{
register int d1, d2; /* row and column deltas */
int d0; /* temporary variable for swapping d1 and d2 */

/* NOTE: the -25 used below is because we are not going from the */
/* center of (r1,c1) to the center of (r2,c2), we are going from */
/* the edge of a hole at (r1,c1) to the edge of a hole at (r2,c2). */
/* holes are 25 mils in diameter (12.5 mils in radius), so we back */
/* off by 2 radii. */
if ((d1 = r1-r2) < 0) /* get absolute row delta */
d1 = -d1;
if ((d2 = c1-c2) < 0) /* get absolute column delta */
d2 = -d2;
if (!d1) /* in same row? */
return( (d2*50)-25 ); /* 50 mils per cell */
if (!d2) /* in same column? */
return( (d1*50)-25 ); /* 50 mils per cell */
if (d1 > d2) { /* get smaller into d1 */
d0 = d1;
d1 = d2;
d2 = d0;
}
d2 -= d1; /* get non-diagonal part of approximate "route" */
return( (d1*71)+(d2*50)-25 ); /* 71 mils diagonally per cell */
}

/* distance to go thru a cell */
static int dist[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
/* N, NE, E, SE, S, SW, W, NW, OT, OR */
/* N */ { 50, 60, 35, 60, 99, 60, 35, 60, 12, 12 },
/* NE */ { 60, 71, 60, 71, 60, 99, 60, 71, 23, 23 },
/* E */ { 35, 60, 50, 60, 35, 60, 99, 60, 12, 12 },
/* SE */ { 60, 71, 60, 71, 60, 71, 60, 99, 23, 23 },
/* S */ { 99, 60, 35, 60, 50, 60, 35, 60, 12, 12 },
/* SW */ { 60, 99, 60, 71, 60, 71, 60, 71, 23, 23 },
/* W */ { 35, 60, 99, 60, 35, 60, 50, 60, 12, 12 },
/* NW */ { 60, 71, 60, 99, 60, 71, 60, 71, 23, 23 },

/* OT */ { 12, 23, 12, 23, 12, 23, 12, 23, 99, 99 },
/* OR */ { 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 }
};

/* distance around (circular) segment of hole */
static int circ[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
/* N, NE, E, SE, S, SW, W, NW, OT, OR */
/* N */ { 39, 29, 20, 10, 0, 10, 20, 29, 99, 0 },
/* NE */ { 29, 39, 29, 20, 10, 0, 10, 20, 99, 0 },
/* E */ { 20, 29, 39, 29, 20, 10, 0, 10, 99, 0 },
/* SE */ { 10, 20, 29, 39, 29, 20, 10, 0, 99, 0 },
/* S */ { 0, 10, 20, 29, 39, 29, 20, 10, 99, 0 },
/* SW */ { 10, 0, 10, 20, 29, 39, 29, 20, 99, 0 },
/* W */ { 20, 10, 0, 10, 20, 29, 39, 29, 99, 0 },
/* NW */ { 29, 20, 10, 0, 10, 20, 29, 39, 99, 0 },

/* OT */ { 99, 99, 99, 99, 99, 99, 99, 99, 99, 0 },
/* OR */ { 99, 99, 99, 99, 99, 99, 99, 99, 99, 0 }
};

/* penalty for extraneous holes and corners, scaled by sharpness of turn */
static int penalty[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
/* N, NE, E, SE, S, SW, W, NW, OT, OR */
/* N */ { 0, 5, 10, 15, 20, 15, 10, 5, 50, 0 },
/* NE */ { 5, 0, 5, 10, 15, 20, 15, 10, 50, 0 },
/* E */ { 10, 5, 0, 5, 10, 15, 20, 15, 50, 0 },
/* SE */ { 15, 10, 5, 0, 5, 10, 15, 20, 50, 0 },
/* S */ { 20, 15, 10, 5, 0, 5, 10, 15, 50, 0 },
/* SW */ { 15, 20, 15, 10, 5, 0, 5, 10, 50, 0 },
/* W */ { 10, 15, 20, 15, 10, 5, 0, 5, 50, 0 },
/* NW */ { 5, 10, 15, 20, 15, 10, 5, 0, 50, 0 },

/* OT */ { 50, 50, 50, 50, 50, 50, 50, 50, 100, 0 },
/* OR */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};

/*
** x is the direction to enter the cell of interest.
** y is the direction to exit the cell of interest.
** z is the direction to really exit the cell, if y=FROM_OTHERSIDE.
**
** return the distance of the trace through the cell of interest.
** the calculation is driven by the tables above.
*/

int CalcDist ( x, y, z ) /* calculate distance of a trace through a cell */
int x, y, z;
{
int adjust;

adjust = 0; /* set if hole is encountered */
if (x == EMPTY)
x = 10;
if (y == EMPTY)
y = 10;
else if (y == FROM_OTHERSIDE) {
if (z == EMPTY)
z = 10;
adjust = circ[x-1][z-1] + penalty[x-1][z-1];
}
return( dist[x-1][y-1] + penalty[x-1][y-1] + adjust );
}


[IO.C]

#include
#include
#include
#include
#include
#include "cell.h"

/* board dimensions */
extern int Nrows;
extern int Ncols;

extern int InitBoardDone; /* sanity check */

/* memory usage */
extern long Ltotal; /* for board */
extern long Itotal; /* for dist */
extern long Ctotal; /* for dir */

/*
** the following types of input lines are legal (spaces and tabs can separate
** tokens, and case is not significant):
**
** 1) a blank line (ignored)
** 2) ';' followed by anything (ignored)
** use semicolon to insert comments.
** 3) DIMENSION (row,column)
** this defines the number of rows and columns on the board, and must be
** given before any of the lines below. note that the user sees the board
** coordinate space as being 1-based, but internally it is 0-based.
** 4) HOLE (row,column)
** this defines a hole location.
** 5) CONNECT thing AND thing
** this declares that two holes are to be electrically connected. a thing
** can be (row,column), or name1.name2, where name1 is the name of a
** CHIPAT-defined chip, and name2 is the name of one of its pins, or a
** number, giving the pin number of the named chip. you can use '='
** instead of 'AND' if you want.
** 6) PRIORITY CONNECT thing AND thing
** same as above, except the order of connections will be preserved. the
** autorouter is free to reorder the non-PRIORITY CONNECTs, and in fact
** reorders them shortest first. if there are PRIORITY CONNECTs, they will
** all be routed before non-PRIORITY CONNECTs.
** 7) INCLUDE filename
** this causes the input to be temporarily taken from the given filename.
** when the given filename is completely processed (EOF encountered),
** control returns to the current file. INCLUDE statements may be nested
** (they may occur inside the given filename). complete and partial
** pathnames can be used (C:\TTL.INC, ..\TTL.INC, \TTL.INC, FOO\TTL.INC).
** 8) CHIP TYPE=type PINS=number HORIZONTAL=number VERTICAL=number
** this declares a chip type, which can be used to place chips on the
** board (see CHIPAT, below), but does not itself place anything on the
** board. TYPE gives the name that will be used in later CHIPAT
** statements. PINS declares the number of pins. HORIZONTAL gives the
** number of 50-mil units separating adjacent pins (along the long side of
** the chip). and VERTICAL gives the number of 50-mil units separating
** pins across from each other (across the skinny width of the chip).
** standard values for HORIZONTAL and VERTICAL are 2 and 6, respectively.
** all CHIP type names must be unique.
** 9) number=name
** this declares a pin name for the chip that is currently being defined.
** this statement must follow a CHIP statement. pins not defined will have
** no name, but you can still refer to them by number. each pin on a chip
** can be named at most once.
** 10) name=number
** same as above.
** 11) CHIPAT (row,column) NAME=name TYPE=type ORIENTATION=orientation
** this defines an instance of a chip, and places the appropriate holes on
** the board. (row,column) is the location of pin 1. NAME defines the name
** to be used in following CONNECT statements. TYPE declares the
** CHIPAT-defined type of the chip. ORIENTATION can have the values
** NORMAL, UP, DOWN, and UPSIDEDOWN. all CHIPAT names must be unique.
**
** NORMAL UP DOWN UPSIDEDOWN
**
** 6 5 4 +---+ +---+ 3 2 1
** +-*-*-*-+ 4 * * 3 1 * | * 6 +-*-*-*-+
** | -> | 5 * ^ * 2 2 * v * 5 | <- |
** +-*-*-*-+ 6 * | * 1 3 * * 4 +-*-*-*-+
** 1 2 3 +---+ +---+ 4 5 6
**
** usually the highest-numbered pin (pin N) is Vcc (power) and the pin
** farthest from it (pin N/2) is GND (ground).
*/

/* chip orientations (rotations) */
#define ORIENT_NORMAL 1
#define ORIENT_UP 2
#define ORIENT_DOWN 3
#define ORIENT_UPSIDEDOWN 4

/* input token types */
#define TOK_EOF 1 /* end of file, no more tokens */
#define TOK_NEWLINE 2 /* end of line */
#define TOK_NUMBER 3 /* number (digits) */
#define TOK_HOLE 4 /* "HOLE" */
#define TOK_ROWCOLUMN 5 /* "(row,column)" */
#define TOK_CONNECT 6 /* "CONNECT" */
#define TOK_EQUAL 7 /* "=" */
#define TOK_AND 8 /* "AND" */
#define TOK_ALPHANUM 9 /* name (letters, digits, ':','.','\') */
#define TOK_CHIP 10 /* "CHIP" */
#define TOK_NAME 11 /* "NAME" */
#define TOK_PINS 12 /* "PINS" */
#define TOK_HORIZONTAL 13 /* "HORIZONTAL" */
#define TOK_VERTICAL 14 /* "VERTICAL" */
#define TOK_INCLUDE 15 /* "INCLUDE" */
#define TOK_CHIPAT 16 /* "CHIPAT" */
#define TOK_TYPE 17 /* "TYPE" */
#define TOK_ORIENTATION 18 /* "ORIENTATION" */
#define TOK_NORMAL 19 /* "NORMAL" */
#define TOK_UP 20 /* "UP" */
#define TOK_DOWN 21 /* "DOWN" */
#define TOK_UPSIDEDOWN 22 /* "UPSIDEDOWN" */
#define TOK_DIMENSION 23 /* "DIMENSION" */
#define TOK_PRIORITY 24 /* "PRIORITY" */

struct reserved { /* reserved word input tokens */
char *tokenname;
int tokenvalue;
};

static struct reserved tokenmatch[] = { /* reserved word table */
{ "HOLE", TOK_HOLE }, { "CONNECT", TOK_CONNECT },
{ "AND", TOK_AND }, { "CHIP", TOK_CHIP },
{ "NAME", TOK_NAME }, { "PINS", TOK_PINS },
{ "HORIZONTAL", TOK_HORIZONTAL }, { "VERTICAL", TOK_VERTICAL },
{ "INCLUDE", TOK_INCLUDE }, { "CHIPAT", TOK_CHIPAT },
{ "TYPE", TOK_TYPE }, { "ORIENTATION", TOK_ORIENTATION },
{ "NORMAL", TOK_NORMAL }, { "UP", TOK_UP },
{ "DOWN", TOK_DOWN }, { "UPSIDEDOWN", TOK_UPSIDEDOWN },
{ "DIMENSION", TOK_DIMENSION }, { "PRIORITY", TOK_PRIORITY }
};

#define MAXTOK 80 /* maximum token length (including null) */

static int numres = sizeof(tokenmatch) / sizeof(tokenmatch[0]);
static char token[MAXTOK]; /* the current token is formed here */

struct pinassign { /* for assigning names to pins */
int index;
char far *name;
struct pinassign far *next;
};

struct template { /* for "CHIP" declarations */
char far *type;
int pins;
int horizontal;
int vertical;
struct pinassign far *pinlist;
struct template far *next;
};

struct instance { /* for "CHIPAT" definitions */
int row;
int column;
char far *name;
struct template far *type;
int orientation;
struct instance far *next;
};

static struct template far *chip = NULL; /* list of CHIPs */
static struct instance far *chipat = NULL; /* list of CHIPATs */

extern void InitBoard( void );
extern long GetCell( int, int, int );
extern void SetCell( int, int, int, long );
extern void InitWork( void );
extern void SetWork( int, int, char far *, int, int, char far *, int );
extern void SortWork( void );
extern void Nomem( void );

void Initialize( FILE * );
static void initfile( FILE * );
static void initchip( struct instance far * );
static void locate( char *, int *, int * );
static int gettoken( FILE * );
static char far *fcopy( char * );
static int same( char far *, char far * );
void Report( FILE * );

void Initialize ( fin ) /* get hole coordinates and connections */
FILE *fin;
{
printf( "enter Initialize()\n" );
InitWork(); /* clear work list */
initfile( fin ); /* read input file(s) */
SortWork(); /* arrange to do shortest ones first */
printf( " %ld bytes used for board\n", Ltotal );
printf( " %ld bytes used for dist\n", Itotal );
printf( " %ld bytes used for dir\n", Ctotal );
printf( "leave Initialize()\n" );
}

/* some useful macros (common code sequences) */

#define SkipRest { while ((tok = gettoken( fin )) != TOK_EOF \
&& tok != TOK_NEWLINE) ; }

#define SkipTokRest { while (tok != TOK_EOF && tok != TOK_NEWLINE) \
tok = gettoken( fin ); } \
continue;

#define CheckInit { if (!InitBoardDone) { \
printf( "error: need dimensions first\n" ); \
SkipRest; \
continue; } }

static void initfile ( fin ) /* read and process input file(s) */
FILE *fin;
{
int tok, r1, c1, r2, c2, i;
char far *p;
char far *n1;
char far *n2;
long cell;
struct template far *p1;
struct pinassign far *p2;
struct pinassign far *p22;
struct instance far *p3;
FILE *fnew;

while ((tok = gettoken( fin )) != TOK_EOF) {
if (tok == TOK_DIMENSION) {
if (InitBoardDone) { /* can only do it once */
printf( "error: redundant dimensions\n" );
SkipRest;
continue;
}
if ((tok = gettoken( fin )) != TOK_ROWCOLUMN) {
printf( "expect (row,column)\n" );
SkipTokRest;
}
sscanf( token, "(%d,%d)", &Nrows, &Ncols );
if (Nrows <= 0 || Ncols <= 0)
printf( "dimension error\n" );
else /* allocate memory for data structures */
InitBoard();
}
else if (tok == TOK_HOLE) {
CheckInit; /* must get dimensions first */
if ((tok = gettoken( fin )) != TOK_ROWCOLUMN) {
printf( "expect (row,column)\n" );
SkipTokRest;
}
sscanf( token, "(%d,%d)", &r1, &c1 );
if (r1 <= 0 || r1 > Nrows || c1 <= 0 || c1 > Ncols)
printf( "out of range\n" );
else { /* position the hole on the board */
/* should check for neighbor holes (error) */
SetCell( r1-1, c1-1, TOP, HOLE );
SetCell( r1-1, c1-1, BOTTOM, HOLE );
}
}
else if (tok == TOK_CONNECT) {
CheckInit; /* must get dimensions first */
if ((tok = gettoken( fin )) == TOK_ROWCOLUMN)
sscanf( token, "(%d,%d)", &r1, &c1 );
else if (tok == TOK_ALPHANUM)
locate( token, &r1, &c1 );
else {
printf( "expect (row,column) or name\n" );
SkipTokRest;
}
n1 = fcopy( token );
if ((tok = gettoken( fin )) != TOK_EQUAL
&& tok != TOK_AND) {
printf( "expect = or AND\n" );
SkipTokRest;
}
if ((tok = gettoken( fin )) == TOK_ROWCOLUMN)
sscanf( token, "(%d,%d)", &r2, &c2 );
else if (tok == TOK_ALPHANUM)
locate( token, &r2, &c2 );
else {
printf( "expect (row,column) or name\n" );
SkipTokRest;
}
n2 = fcopy( token );
if (r1 <= 0 || r1 > Nrows || r2 <= 0 || r2 > Nrows
|| c1 <= 0 || c1 > Ncols
|| c2 <= 0 || c2 > Ncols) {
printf( "out of range\n" );
_ffree( n1 );
_ffree( n2 );
}
else {
cell = GetCell( r1-1, c1-1, TOP );
if (!(cell & HOLE)) {
printf( "error: no source hole\n" );
_ffree( n1 );
_ffree( n2 );
SkipRest;
continue;
}
cell = GetCell( r2-1, c2-1, TOP );
if (!(cell & HOLE)) {
printf( "error: no target hole\n" );
_ffree( n1 );
_ffree( n2 );
SkipRest;
continue;
}
SetWork( r1-1, c1-1, n1, r2-1, c2-1, n2, 0 );
}
}
else if (tok == TOK_PRIORITY) {
CheckInit; /* must get dimensions first */
if ((tok = gettoken( fin )) != TOK_CONNECT) {
printf( "expect CONNECT\n" );
SkipTokRest;
}
if ((tok = gettoken( fin )) == TOK_ROWCOLUMN)
sscanf( token, "(%d,%d)", &r1, &c1 );
else if (tok == TOK_ALPHANUM)
locate( token, &r1, &c1 );
else {
printf( "expect (row,column) or name\n" );
SkipTokRest;
}
n1 = fcopy( token );
if ((tok = gettoken( fin )) != TOK_EQUAL
&& tok != TOK_AND) {
printf( "expect = or AND\n" );
SkipTokRest;
}
if ((tok = gettoken( fin )) == TOK_ROWCOLUMN)
sscanf( token, "(%d,%d)", &r2, &c2 );
else if (tok == TOK_ALPHANUM)
locate( token, &r2, &c2 );
else {
printf( "expect (row,column) or name\n" );
SkipTokRest;
}
n2 = fcopy( token );
if (r1 <= 0 || r1 > Nrows || r2 <= 0 || r2 > Nrows
|| c1 <= 0 || c1 > Ncols
|| c2 <= 0 || c2 > Ncols) {
printf( "out of range\n" );
_ffree( n1 );
_ffree( n2 );
}
else {
cell = GetCell( r1-1, c1-1, TOP );
if (!(cell & HOLE)) {
printf( "error: no source hole\n" );
_ffree( n1 );
_ffree( n2 );
SkipRest;
continue;
}
cell = GetCell( r2-1, c2-1, TOP );
if (!(cell & HOLE)) {
printf( "error: no target hole\n" );
_ffree( n1 );
_ffree( n2 );
SkipRest;
continue;
}
SetWork( r1-1, c1-1, n1, r2-1, c2-1, n2, 1 );
}
}
else if (tok == TOK_INCLUDE) {
CheckInit; /* must get dimensions first */
if ((tok = gettoken( fin )) != TOK_ALPHANUM) {
printf( "expect name for INCLUDE\n" );
SkipTokRest;
}
if (!(fnew = fopen( token, "r" ))) {
printf( "can't open INCLUDE file %s\n",
token );
SkipRest;
continue;
}
if ((tok = gettoken( fin )) != TOK_EOF
&& tok != TOK_NEWLINE) {
printf( "extra chars on INCLUDE line\n" );
SkipRest;
}
initfile( fnew ); /* recurse */
if (fclose( fnew ))
printf( "error closing INCLUDE file\n" );
continue; /* already ate the NEWLINE, if any */
}
else if (tok == TOK_CHIP) {
CheckInit; /* must get dimensions first */
if ((tok = gettoken( fin )) != TOK_TYPE
|| (tok = gettoken( fin )) != TOK_EQUAL
|| (tok = gettoken( fin )) != TOK_ALPHANUM) {
printf( "expect TYPE=type\n" );
SkipTokRest;
}
if (!(p1 = (struct template far *)
_fmalloc( sizeof(struct template) )))
Nomem();
p1->type = fcopy( token );
if ((tok = gettoken( fin )) != TOK_PINS
|| (tok = gettoken( fin )) != TOK_EQUAL
|| (tok = gettoken( fin )) != TOK_NUMBER) {
printf( "expect PINS=number\n" );
_ffree( p1->type );
_ffree( p1 );
SkipTokRest;
}
sscanf( token, "%d", &i );
p1->pins = i;
if ((p1->pins = i) < 0 || (i & 1))
printf( "PINS negative or odd\n" );
if ((tok = gettoken( fin )) != TOK_HORIZONTAL
|| (tok = gettoken( fin )) != TOK_EQUAL
|| (tok = gettoken( fin )) != TOK_NUMBER) {
printf( "expect HORIZONTAL=number\n" );
_ffree( p1->type );
_ffree( p1 );
SkipTokRest;
}
sscanf( token, "%d", &i );
if ((p1->horizontal = i) <= 0)
printf( "HORIZONTAL nonpositive\n" );
if ((tok = gettoken( fin )) != TOK_VERTICAL
|| (tok = gettoken( fin )) != TOK_EQUAL
|| (tok = gettoken( fin )) != TOK_NUMBER) {
printf( "expect VERTICAL=number\n" );
_ffree( p1->type );
_ffree( p1 );
SkipTokRest;
}
sscanf( token, "%d", &i );
if ((p1->vertical = i) < 0)
printf( "VERTICAL nonpositive\n" );
p1->pinlist = NULL;
p1->next = chip;
chip = p1;
}
else if (tok == TOK_NUMBER) {
CheckInit; /* must get dimensions first */
if (!chip) {
printf( "no template\n" );
SkipRest;
continue;
}
sscanf( token, "%d", &i );
if ((tok = gettoken( fin )) != TOK_EQUAL
|| (tok = gettoken( fin )) != TOK_ALPHANUM) {
printf( "expect number=name\n" );
SkipTokRest;
}
if (!(p2 = (struct pinassign far *)
_fmalloc( sizeof(struct pinassign) )))
Nomem();
p2->name = fcopy( token );
p2->index = i;
/* check uniqueness of name and index */
for (p22 = chip->pinlist; p22; p22 = p22->next)
if (p22->index == i
|| same( p22->name, p )) {
printf( "warning: repeated pin\n" );
break;
}
p2->next = chip->pinlist;
chip->pinlist = p2;
}
else if (tok == TOK_ALPHANUM) {
CheckInit; /* must get dimensions first */
if (!chip) {
printf( "no template\n" );
SkipRest;
continue;
}
p = fcopy( token );
if ((tok = gettoken( fin )) != TOK_EQUAL
|| (tok = gettoken( fin )) != TOK_NUMBER) {
printf( "expect name=number\n" );

_ffree( p );
SkipTokRest;
}
sscanf( token, "%d", &i );
if (!(p2 = (struct pinassign far *)
_fmalloc( sizeof(struct pinassign) )))
Nomem();
p2->name = p;
p2->index = i;
/* check uniqueness of name and index */
for (p22 = chip->pinlist; p22; p22 = p22->next)
if (p22->index == i
|| same( p22->name, p )) {
printf( "warning: repeated pin\n" );
break;
}
p2->next = chip->pinlist;
chip->pinlist = p2;
}
else if (tok == TOK_CHIPAT) {
CheckInit; /* must get dimensions first */
if ((tok = gettoken( fin )) != TOK_ROWCOLUMN) {
printf( "expect (row,column)\n" );
SkipTokRest;
}
sscanf( token, "(%d,%d)", &r1, &c1 );
if ((tok = gettoken( fin )) != TOK_NAME
|| (tok = gettoken( fin )) != TOK_EQUAL
|| (tok = gettoken( fin )) != TOK_ALPHANUM) {
printf( "expect NAME=name\n" );
SkipTokRest;
}
if (!(p3 = (struct instance far *)
_fmalloc( sizeof(struct instance) )))
Nomem();
p3->name = fcopy( token );
p3->row = r1;
p3->column = c1;
if ((tok = gettoken( fin )) != TOK_TYPE
|| (tok = gettoken( fin )) != TOK_EQUAL
|| (tok = gettoken( fin )) != TOK_ALPHANUM) {
printf( "expect TYPE=type\n" );
_ffree( p3->name );
_ffree( p3 );
SkipTokRest;
}
for (p3->type = chip; p3->type;
p3->type = p3->type->next)
if (same( token, p3->type->type ))
break;
if (!(p3->type)) {
printf( "couldn't find chip type\n" );
_ffree( p3->name );
_ffree( p3 );
SkipTokRest;
}
if ((tok = gettoken( fin )) != TOK_ORIENTATION
|| (tok = gettoken( fin )) != TOK_EQUAL
|| ((tok = gettoken( fin )) != TOK_NORMAL
&& tok != TOK_UP && tok != TOK_DOWN
&& tok != TOK_UPSIDEDOWN)) {
printf( "expect ORIENTATION=orientation\n" );
_ffree( p3->name );
_ffree( p3 );
SkipTokRest;
}
switch (tok) {
case TOK_NORMAL:
p3->orientation = ORIENT_NORMAL; break;
case TOK_UP:
p3->orientation = ORIENT_UP; break;
case TOK_DOWN:
p3->orientation = ORIENT_DOWN; break;
case TOK_UPSIDEDOWN:
p3->orientation = ORIENT_UPSIDEDOWN; break;
default:
printf( "internal error\n" );
exit( -1 );
break;
}
p3->next = chipat;
chipat = p3;
initchip( p3 );
}
else if (tok == TOK_NEWLINE)
continue;
else /* something unexpected */
printf( "syntax error: unexpected input\n" );
if ((tok = gettoken( fin )) != TOK_EOF && tok != TOK_NEWLINE) {
printf( "syntax error: expected end of line\n" );
SkipRest;
}
}
}

static void initchip ( p ) /* initialize a chip definition (create holes) */
struct instance far *p;
{
int r, c, pin;
struct template far *t;

pin = 1;
r = p->row;
c = p->column;
t = p->type;
/* should check for neighboring holes (warning if so) */
switch (p->orientation) {
case ORIENT_NORMAL:
while (pin <= t->pins / 2) {
SetCell( r-1, c-1, TOP, HOLE );
SetCell( r-1, c-1, BOTTOM, HOLE );
pin++;
c += t->horizontal;
}
c -= t->horizontal;
r += t->vertical;
while (pin <= t->pins) {
SetCell( r-1, c-1, TOP, HOLE );
SetCell( r-1, c-1, BOTTOM, HOLE );
pin++;
c -= t->horizontal;
}
break;
case ORIENT_UP:
while (pin <= t->pins / 2) {
SetCell( r-1, c-1, TOP, HOLE );
SetCell( r-1, c-1, BOTTOM, HOLE );
pin++;
r += t->horizontal;
}
r -= t->horizontal;
c -= t->vertical;
while (pin <= t->pins) {
SetCell( r-1, c-1, TOP, HOLE );
SetCell( r-1, c-1, BOTTOM, HOLE );
pin++;
r -= t->horizontal;
}
break;
case ORIENT_DOWN:
while (pin <= t->pins / 2) {
SetCell( r-1, c-1, TOP, HOLE );
SetCell( r-1, c-1, BOTTOM, HOLE );
pin++;
r -= t->horizontal;
}
r += t->horizontal;
c += t->vertical;
while (pin <= t->pins) {
SetCell( r-1, c-1, TOP, HOLE );
SetCell( r-1, c-1, BOTTOM, HOLE );
pin++;
r += t->horizontal;
}
break;
case ORIENT_UPSIDEDOWN:
while (pin <= t->pins / 2) {
SetCell( r-1, c-1, TOP, HOLE );
SetCell( r-1, c-1, BOTTOM, HOLE );
pin++;
c -= t->horizontal;
}
c += t->horizontal;
r -= t->vertical;
while (pin <= t->pins) {
SetCell( r-1, c-1, TOP, HOLE );
SetCell( r-1, c-1, BOTTOM, HOLE );
pin++;
c += t->horizontal;
}
break;
default:
printf( "internal error: unexpected orientation\n" );
exit( -1 );
break;
}
}

static void locate ( p, r, c ) /* find location of name1.{name2,number} */
char *p;
int *r, *c;
{
char *q;
int i;
struct instance far *s;
struct pinassign far *t;

if (!(q = strchr( p, '.' ))) {
printf( "expect name1.{name2,number}\n" );
return;
}
*q++ = 0; /* separate into two parts & point at second part */
for (s = chipat; s; s = s->next) /* find proper chip */
if (same( p, s->name ))
break;
if (!s || !(s->type)) {
printf( "can't find chip or chip type\n" );
return;
}
if (isdigit( *q )) { /* get pin number */
i = atoi( q );
if (i <= 0 || i > s->type->pins) {
printf( "pin out of range\n" );
return;
}
}
else { /* get index of named pin via the template */
for (t = s->type->pinlist; t; t = t->next)
if (same( q, t->name ))
break;
if (!t) {
printf( "can't find pin\n" );
return;
}
i = t->index;
}
*r = s->row;
*c = s->column;
switch (s->orientation) {
case ORIENT_NORMAL:
if (i <= s->type->pins / 2)
*c += (i-1) * s->type->horizontal;
else {
*r += s->type->vertical;
*c += (s->type->pins - i) * s->type->horizontal;
}
break;
case ORIENT_UP:
if (i <= s->type->pins / 2)
*r += (i-1) * s->type->horizontal;
else {
*c -= s->type->vertical;
*r += (s->type->pins - i) * s->type->horizontal;
}
break;
case ORIENT_DOWN:
if (i <= s->type->pins / 2)
*r -= (i-1) * s->type->horizontal;
else {
*c += s->type->vertical;
*r -= (s->type->pins - i) * s->type->horizontal;
}
break;
case ORIENT_UPSIDEDOWN:
if (i <= s->type->pins / 2)
*c -= (i-1) * s->type->horizontal;
else {
*r -= s->type->vertical;
*c -= (s->type->pins - i) * s->type->horizontal;
}
break;
default:
printf( "internal error: unexpected orientation\n" );
exit( -1 );
break;
}
*--q = '.'; /* put back the separator */
}

static int gettoken ( fin ) /* get next token into token[], return value */
FILE *fin;
{
int ch, i;

/* burn whitespace */
while ((ch = getc( fin )) == ' ' || ch == '\t') ;
if (ch == EOF)
return( TOK_EOF );
else if (ch == '\n')
return( TOK_NEWLINE );
else if (ch == ';') { /* comment; burn to end of line */
while ((ch = getc( fin )) != EOF && ch != '\n') ;
return( (ch == '\n') ? TOK_NEWLINE : TOK_EOF );
}
else if (ch == '=')
return( TOK_EQUAL );
else if (isdigit( ch )) { /* a number; move it to the buffer */
i = 0;
do {
if (i < MAXTOK-1)
token[i++] = (char)ch;
ch = getc( fin );
} while (isdigit( ch ));
token[i] = 0;
if (ch != EOF)
ungetc( ch, fin );
return( TOK_NUMBER );
}
else if (isalpha( ch ) || ch == '.' || ch == '\\') {
/* a name; move it to the buffer */
i = 0;
do {
if (i < MAXTOK-1)
token[i++] = (char)ch;
ch = getc( fin );
} while (isalnum( ch ) || ch == ':' || ch == '.'
|| ch == '\\');
token[i] = 0;
if (ch != EOF)
ungetc( ch, fin );
/* try to identify it as a reserved word */
for (i = 0; i < numres; i++) /* search table */
if (!stricmp( tokenmatch[i].tokenname, token ))
return( tokenmatch[i].tokenvalue );
/* it's not a reserved word; just return it */
strupr( token );
return( TOK_ALPHANUM );
}
else if (ch == '(') { /* "(row,column)", move it to the buffer */
token[0] = (char)ch;
i = 1;
while ((ch = getc( fin )) == ' ' || ch == '\t') ;
if (!isdigit( ch )) {
printf( "syntax error: expected digit\n" );
exit( -1 );
}
do {
if (i < MAXTOK-1)
token[i++] = (char)ch;
ch = getc( fin );
} while (isdigit( ch ));
while (ch == ' ' || ch == '\t')
ch = getc( fin );
if (ch != ',') {
printf( "syntax error: expected comma\n" );
exit( -1 );
}
if (i < MAXTOK-1)
token[i++] = (char)ch;
while ((ch = getc( fin )) == ' ' || ch == '\t') ;
if (!isdigit( ch )) {
printf( "syntax error: expected digit\n" );
exit( -1 );
}
do {
if (i < MAXTOK-1)
token[i++] = (char)ch;
ch = getc( fin );
} while (isdigit( ch ));
while (ch == ' ' || ch == '\t')
ch = getc( fin );
if (ch != ')') {
printf( "syntax error: expected right paren\n" );
exit( -1 );
}
if (i < MAXTOK-1)
token[i++] = (char)ch;
token[i] = 0;
return( TOK_ROWCOLUMN );
}
else {
printf( "syntax error: unrecognized token\n" );
exit( -1 );
}
}

static char far *fcopy ( p ) /* return ptr to far string copy */
char *p;
{
char far *q;
char far *r;

if (!(q = r = _fmalloc( strlen( p ) + 1 )))
Nomem();
while (*r++ = *p++) ; /* copy string */
return( q );
}

static int same ( p, q ) /* return 1 if far strings are identical, else 0 */
char far *p;
char far *q;
{
while (*p && *p == *q) { /* compare bytes until mismatch or end */
p++;
q++;
}
return( (*p || *q) ? 0 : 1 );
}

void Report ( fout ) /* output routed board */
FILE *fout;
{
int r, c;
char b;
long x;

printf( "enter Report()\n" );
/* output dimensions first */
b = (char)Nrows; putc( b, fout );
b = (char)(Nrows>>8); putc( b, fout );
b = (char)Ncols; putc( b, fout );
b = (char)(Ncols>>8); putc( b, fout );
/* now do rows and columns */
for (r = 0; r < Nrows; r++)
for (c = 0; c < Ncols; c++) {
x = GetCell( r, c, TOP ); /* first do frontside */
b = (char)x; putc( b, fout );
b = (char)(x>>8); putc( b, fout );
b = (char)(x>>16); putc( b, fout );
b = (char)(x>>24); putc( b, fout );
x = GetCell( r, c, BOTTOM ); /* then do backside */
b = (char)x; putc( b, fout );
b = (char)(x>>8); putc( b, fout );
b = (char)(x>>16); putc( b, fout );
b = (char)(x>>24); putc( b, fout );
}
printf( "leave Report()\n" );
}


[PCBROUTE.C]

/*
** printed circuit board autorouter, Copyright (C) Randy Nevin 1989.
**
** you may give this software to anyone, make as many copies as you like, and
** post it on public computer bulletin boards and file servers. you may not
** sell it or charge any fee for distribution (except for media and postage),
** remove this comment or the copyright notice from the code, or claim that
** you wrote this code or anything derived from it. you may modify the code as
** much as you want (please document clearly with comments, and maintain the
** coding style), but programs which are derived from this one are subject to
** the conditions stated here. i am providing this code so that people can
** learn from it, so if you distribute it, please include source code, not
** just executables. contact me to report bugs or suggest enhancements; i do
** not guarantee support, but i will make an effort in good faith to help you,
** and i want to act as a central clearing house for future versions. you
** should contact me before undertaking a significant development effort, to
** avoid reinventing the wheel. if you come up with an enhancement you
** consider particularly useful, i would appreciate being informed so that it
** can be incorporated in future versions. my address is: Randy Nevin,
** 1731 211th PL NE, Redmond, WA 98053. this code is available directly from
** the author; just send a floppy and a self-addressed floppy mailer with
** sufficient postage.
**
** HISTORY
** (name date description)
** ----------------------------------------------------
** randy nevin 2/1/89 initial version
** randy nevin 2/4/89 made retrace table driven, instead of
** doubly-nested switch statements.
** randy nevin 2/4/89 changed dir from int to char (cut
** storage for it in half).
** randy nevin 2/8/89 changed SetQueue and ReSetQueue to
** give priority to goal nodes.
** randy nevin 2/11/89 don't output incremental search
** results if stdout is redirected.
** randy nevin 2/11/89 released version 1.00
*/

#include
#include
#include
#include
#include
#include "cell.h"

/*
** if you run out of memory while routing large boards, there are two things
** you can do: (1) go into your config.sys file and disable everything you
** don't need. getting rid of things like ansi.sys, ramdisks, disk caches, and
** other terminate and stay resident (tsr) programs can free a lot of memory.
** (2) link the router, inspect the .map file, relink with the /CPARMAXALLOC:n
** switch, where n is calculated to allow for a near heap of about 5k. read
** the linker documentation before you do thiions
sspinlikipR HOthe route.map file
** says the program needs 81EFh bytes. to this i add 1400h (5k) for a near
** heap to get 95EFh bytes or 95Fh paragraphs, which is 2399 decimal.
*/

int justboard = 0; /* need all data structures, not just the board */


extern void Initialize( FILE * );
extern void Solve( void );
extern void Report( FILE * );

void main( int, char *[] );

void main ( argc, argv ) /* input board, route traces, output routed board */
int argc;
char *argv[];
{
char *self, *p;
FILE *fin, *fout;
long start, stop;

printf( "Copyright (C) Randy Nevin, 1989. Version 1.00\n" );
printf( "See source code for rights granted.\n\n" );
start = time( NULL );
self = argv[0];
/* get rid of initial part of path */
if ((p = strrchr( self, '\\' )) || (p = strrchr( self, ':' )))
self = ++p;
if (argc != 3) { /* need infile and outfile */
printf( "usage: %s infile outfile\n", self );
exit( -1 );
}
if (!(fin = fopen( argv[1], "r" ))) {
printf( "can't open %s\n", argv[1] );
exit( -1 );
}
if (!(fout = fopen( argv[2], "wb" ))) {
printf( "can't open %s\n", argv[2] );
exit( -1 );
}
Initialize( fin );
Solve();
Report( fout );
stop = time( NULL ) - start;
printf( "time = %ld second%s\n", stop, (stop == 1) ? "" : "s" );
exit( 0 );
}


[QUEUE.C]

#include
#include
#include
#include "cell.h"

struct queue { /* search queue structure */
int Row; /* current row */
int Col; /* current column */
int Side; /* 0=top, 1=bottom */
int Dist; /* path distance to this cell so far */
int ApxDist; /* approximate distance to target from here */
struct queue far *Next;
};

/* search statistics */
long OpenNodes = 0; /* total number of nodes opened */
long ClosNodes = 0; /* total number of nodes closed */
long MoveNodes = 0; /* total number of nodes moved */
long MaxNodes = 0; /* maximum number of nodes opened at one time */

static long qlen = 0; /* current queue length */

static struct queue far *Head = NULL;
static struct queue far *Tail = NULL;
static struct queue far *Save = NULL; /* hold empty queue structs */

extern void Nomem( void );

void InitQueue( void );
void GetQueue( int *, int *, int *, int *, int * );
void SetQueue( int, int, int, int, int, int, int );
void ReSetQueue( int, int, int, int, int, int, int );

void InitQueue () { /* initialize the search queue */
struct queue far *p;

while (p = Head) {
Head = p->Next;
p->Next = Save;
Save = p;
}
Tail = NULL;
OpenNodes = ClosNodes = MoveNodes = MaxNodes = qlen = 0;
}

void GetQueue ( r, c, s, d, a ) /* get search queue item from list */
int *r, *c, *s, *d, *a;
{
struct queue far *p;

if (p = Head) { /* return first item in list */
*r = p->Row;
*c = p->Col;
*s = p->Side;
*d = p->Dist;
*a = p->ApxDist;
if (!(Head = p->Next))
Tail = NULL;
/* put node on free list */
p->Next = Save;
Save = p;
ClosNodes++;
qlen--;
}
else /* empty list */
*r = *c = *s = *d = *a = ILLEGAL;
}

void SetQueue ( r, c, s, d, a, r2, c2 ) /* add a search node to the list */
int r, c, s, d, a, r2, c2;
{
struct queue far *p;
struct queue far *q;
struct queue far *t;
register int i;
int j;

if (p = Save) /* try free list first */
Save = p->Next;
else if (!(p = (struct queue far *)_fmalloc( sizeof(struct queue) )))
Nomem();
p->Row = r;
p->Col = c;
p->Side = s;
i = (p->Dist = d) + (p->ApxDist = a);
p->Next = NULL;
if (q = Head) { /* insert in proper position in list */
if (q->Dist + q->ApxDist > i) { /* insert at head */
p->Next = q;
Head = p;
}
else { /* search for proper position */
for (t = q, q = q->Next;
q && i > (j = q->Dist + q->ApxDist);
t = q, q = q->Next)
;
if (q && i == j && q->Row == r2 && q->Col == c2) {
/* insert after q, which is a goal node */
if (!(p->Next = q->Next))
Tail = p;
q->Next = p;
}
else { /* insert in front of q */
if (!(p->Next = q))
Tail = p;
t->Next = p;
}
}
}
else /* empty search list */
Head = Tail = p;
OpenNodes++;
if (++qlen > MaxNodes)
MaxNodes = qlen;
}

void ReSetQueue ( r, c, s, d, a, r2, c2 ) /* reposition node in list */
register int r, c;
int s, d, a, r2, c2;
{
struct queue far *p;
struct queue far *q;

/* first, see if it is already in the list */
for (q = NULL, p = Head; p; q = p, p = p->Next) {
if (p->Row == r && p->Col == c && p->Side == s) {
/* old one to remove */
if (q) {
if (!(q->Next = p->Next))
Tail = q;
}
else if (!(Head = p->Next))
Tail = NULL;
p->Next = Save;
Save = p;
OpenNodes--;
MoveNodes++;
qlen--;
break;
}
}
/* if it was there, it's gone now; insert it at the proper position */
SetQueue( r, c, s, d, a, r2, c2 );
}



[SOLVE.C]

#include
#include
#include
#include
#include "cell.h"

/*
** visit neighboring cells like this (where [9] is on the other side):
**
** +---+---+---+
** | 1 | 2 | 3 |
** +---+---+---+
** | 4 |[9]| 5 |
** +---+---+---+
** | 6 | 7 | 8 |
** +---+---+---+
*/

static int delta[8][2] = { /* for visiting neighbors on the same side */
{ 1, -1 }, /* northwest */
{ 1, 0 }, /* north */
{ 1, 1 }, /* northeast */
{ 0, -1 }, /* west */
{ 0, 1 }, /* east */
{ -1, -1 }, /* southwest */
{ -1, 0 }, /* south */
{ -1, 1 } /* southeast */
};

static int ndir[8] = { /* for building paths back to source */
FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
FROM_EAST, FROM_WEST,
FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
};

/* blocking masks for neighboring cells */
#define BLOCK_NORTHEAST ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
| ANGLE_NEtoSE | ANGLE_NWtoNE \
| SHARP_NtoNE | SHARP_EtoNE )
#define BLOCK_SOUTHEAST ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
| ANGLE_NEtoSE | ANGLE_SEtoSW \
| SHARP_EtoSE | SHARP_StoSE )
#define BLOCK_SOUTHWEST ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
| ANGLE_SEtoSW | ANGLE_SWtoNW \
| SHARP_StoSW | SHARP_WtoSW )
#define BLOCK_NORTHWEST ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
| ANGLE_SWtoNW | ANGLE_NWtoNE \
| SHARP_WtoNW | SHARP_NtoNW )

struct block {
int r1, c1;
long b1, h1;
int r2, c2;
long b2, h2;
};

static struct block blocking[8] = { /* blocking masks */
{ 0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
1, 0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
0, 1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
-1, 0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ -1, 0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
0, 1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
};

static int selfok[5][8] = { /* mask for self-blocking corner effects */
{ 1, 1, 1, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 0, 1, 0 },
{ 0, 1, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 0, 0, 0 }
};

static long newmask[5][8] = { /* patterns to mask out in neighbor cells */
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
{ 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
{ 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
{ 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
};

static char fmt[] =
" open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";

/* board dimensions */
extern int Nrows;
extern int Ncols;

/* measures of progress */
int Ntotal = 0;
int Ncurrent = 0;

/* search statistics */
extern long OpenNodes; /* total number of nodes opened */
extern long ClosNodes; /* total number of nodes closed */
extern long MoveNodes; /* total number of nodes moved */
extern long MaxNodes; /* maximum number of nodes opened at one time */

extern void GetWork( int *, int *, char far * far *, int *, int *,
char far * far * );
extern void InitQueue( void );
extern void GetQueue( int *, int *, int *, int *, int * );
extern void SetQueue( int, int, int, int, int, int, int );
extern void ReSetQueue( int, int, int, int, int, int, int );
extern long GetCell( int, int, int );
extern void SetCell( int, int, int, long );
extern void OrCell( int, int, int, long );
extern int GetDir( int, int, int );
extern void SetDir( int, int, int, int );
extern int GetDist( int, int, int );
extern void SetDist( int, int, int, int );
extern int GetApxDist( int, int, int, int );
extern int CalcDist( int, int, int );

void Solve( void );
void Retrace( int, int, int, int, int );

void Solve () { /* route all traces */
int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
register int i;
char far *n1;
char far *n2;
long curcell, newcell, buddy, lastopen, lastclos, lastmove;
int newdist, olddir, success, self, echo;

printf( "enter Solve()\n" );
echo = isatty( fileno(stdout) ) ? 1 : 0;
/* go until no more work to do */
for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
Ncurrent++;
printf( "routing %Fs=%Fs, %d of %d\n", n1, n2, Ncurrent,
Ntotal );
if (r1 == r2 && c1 == c2) /* trivial case; already routed */
continue;
success = 0;
lastopen = lastclos = lastmove = 0;
InitQueue(); /* initialize the search queue */
a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
SetQueue( r1, c1, TOP, 0, a, r2, c2 );
SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
/* search until success or we exhaust all possibilities */
for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
GetQueue( &r, &c, &s, &d, &a )) {
if (r == r2 && c == c2) { /* success! */
Retrace( r1, c1, r2, c2, s ); /* lay traces */
success++;
break;
}
/* report every 100 new nodes or so */
if (echo && (OpenNodes - lastopen > 100
|| ClosNodes - lastclos > 100
|| MoveNodes - lastmove > 100)) {
lastopen = (OpenNodes/100)*100;
lastclos = (ClosNodes/100)*100;
lastmove = (MoveNodes/100)*100;
printf( fmt, OpenNodes, ClosNodes,
MoveNodes, MaxNodes,
(ClosNodes*50)/(Nrows*Ncols) );
putchar( '\r' );
}
curcell = GetCell( r, c, s );
if (curcell & CORNER_NORTHWEST)
self = 1;
else if (curcell & CORNER_NORTHEAST)
self = 2;
else if (curcell & CORNER_SOUTHWEST)
self = 3;
else if (curcell & CORNER_SOUTHEAST)
self = 4;
else
self = 0;
for (i = 0; i < 8; i++) { /* consider neighbors */
if (!selfok[self][i]) /* check self-block */
continue;
if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
|| (nc = c+delta[i][1]) < 0
|| nc >= Ncols) /* off the edge? */
continue;
newcell = GetCell( nr, nc, s );
/* check for non-target hole */
if (newcell & HOLE) {
if (nr != r2 || nc != c2)
continue;
}
else {
newcell &= ~(newmask[self][i]);
if (newcell) /* check for traces */
continue;
}
/* check blocking on corner neighbors */
if (delta[i][0] && delta[i][1]) {
/* check first buddy */
buddy = GetCell( r+blocking[i].r1,
c+blocking[i].c1, s );
if (buddy & HOLE) {
if (buddy & (blocking[i].h1))
continue;
}
else if (buddy & (blocking[i].b1))
continue;
/* check second buddy */
buddy = GetCell( r+blocking[i].r2,
c+blocking[i].c2, s );
if (buddy & HOLE) {
if (buddy & (blocking[i].h2))
continue;
}
else if (buddy & (blocking[i].b2))
continue;
}
olddir = GetDir( r, c, s );
newdist = d+CalcDist( ndir[i], olddir,
(olddir == FROM_OTHERSIDE)
? GetDir( r, c, 1-s ) : 0 );
/* if not visited yet, add it to queue */
if (!GetDir( nr, nc, s )) {
SetDir( nr, nc, s, ndir[i] );
SetDist( nr, nc, s, newdist );
SetQueue( nr, nc, s, newdist,
GetApxDist( nr, nc, r2, c2 ),
r2, c2 );
}
/* we might have found a better path */
else if (newdist < GetDist( nr, nc, s )) {
SetDir( nr, nc, s, ndir[i] );
SetDist( nr, nc, s, newdist );
ReSetQueue( nr, nc, s, newdist,
GetApxDist( nr, nc, r2, c2 ),
r2, c2 );
}
}
/* consider other side of board */
/* check for holes or traces on other side */
if (newcell = GetCell( r, c, 1-s ))
continue;
skip = 0;
/* check for nearby holes */
for (i = 0; i < 8; i++) {
if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
|| (nc = c+delta[i][1]) < 0
|| nc >= Ncols) /* off the edge? */
continue;
if (GetCell( nr, nc, s ) & HOLE) {
skip = 1; /* neighboring hole */
break;
}
}
if (skip) /* neighboring hole? */
continue; /* yes, can't drill one here */
olddir = GetDir( r, c, s );
newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
(olddir == FROM_OTHERSIDE)
? GetDir( r, c, 1-s ) : 0 );
/* if not visited yet, add it to queue */
if (!GetDir( r, c, 1-s )) {
SetDir( r, c, 1-s, FROM_OTHERSIDE );
SetDist( r, c, 1-s, newdist );
SetQueue( r, c, 1-s, newdist, a, r2, c2 );
}
/* we might have found a better path */
else if (newdist < GetDist( r, c, 1-s )) {
SetDir( r, c, 1-s, FROM_OTHERSIDE );
SetDist( r, c, 1-s, newdist );
ReSetQueue( r, c, 1-s, newdist, a, r2, c2 );
}
}
printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
(ClosNodes*50)/(Nrows*Ncols) );
putchar( '\n' );
if (!success)
printf( "\t*!* UNSUCCESSFUL *!*\n" );
/* clear direction flags */
for (r = 0; r < Nrows; r++) {
for (c = 0; c < Ncols; c++) {
SetDir( r, c, TOP, EMPTY );
SetDir( r, c, BOTTOM, EMPTY );
}
}
}
printf( "leave Solve()\n" );
}

static long bit[8][9] = { /* OT=Otherside */
/* N, NE, E, SE, S, SW, W, NW, OT */
/* N */ { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
/* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
/* E */ { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
/* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
/* S */ { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
/* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
/* W */ { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
/* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
};

void Retrace ( rr1, cc1, rr2, cc2, s )
/* work from target back to source, actually laying the traces */
int rr1, cc1, rr2, cc2, s; /* start on side s */
{
int r0, c0, s0, r1, c1, s1, r2, c2, s2;
register int x, y;
long b;

r1 = rr2;
c1 = cc2;
s1 = s;
r0 = c0 = s0 = ILLEGAL;
do {
/* find where we came from to get here */
switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
case FROM_NORTH: r2++; break;
case FROM_EAST: c2++; break;
case FROM_SOUTH: r2--; break;
case FROM_WEST: c2--; break;
case FROM_NORTHEAST: r2++; c2++; break;
case FROM_SOUTHEAST: r2--; c2++; break;
case FROM_SOUTHWEST: r2--; c2--; break;
case FROM_NORTHWEST: r2++; c2--; break;
case FROM_OTHERSIDE: s2 = 1-s2; break;
default:
printf( "internal error: no way back\n" );
exit( -1 );
break;
}
if (r0 != ILLEGAL)
y = GetDir( r0, c0, s0 );
/* see if target or hole */
if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
switch (x) {
case FROM_NORTH:
OrCell( r1, c1, s1, HOLE_NORTH ); break;
case FROM_EAST:
OrCell( r1, c1, s1, HOLE_EAST ); break;
case FROM_SOUTH:
OrCell( r1, c1, s1, HOLE_SOUTH ); break;
case FROM_WEST:
OrCell( r1, c1, s1, HOLE_WEST ); break;
case FROM_NORTHEAST:
OrCell( r1, c1, s1, HOLE_NORTHEAST ); break;
case FROM_SOUTHEAST:
OrCell( r1, c1, s1, HOLE_SOUTHEAST ); break;
case FROM_SOUTHWEST:
OrCell( r1, c1, s1, HOLE_SOUTHWEST ); break;
case FROM_NORTHWEST:
OrCell( r1, c1, s1, HOLE_NORTHWEST ); break;
case FROM_OTHERSIDE:
default:
printf( "internal error\n" );
exit( -1 );
break;
}
}
else {
if ((y == FROM_NORTH || y == FROM_NORTHEAST
|| y == FROM_EAST || y == FROM_SOUTHEAST
|| y == FROM_SOUTH || y == FROM_SOUTHWEST
|| y == FROM_WEST || y == FROM_NORTHWEST)
&& (x == FROM_NORTH || x == FROM_NORTHEAST
|| x == FROM_EAST || x == FROM_SOUTHEAST
|| x == FROM_SOUTH || x == FROM_SOUTHWEST
|| x == FROM_WEST || x == FROM_NORTHWEST
|| x == FROM_OTHERSIDE)
&& (b = bit[y-1][x-1])) {
OrCell( r1, c1, s1, b );
if (b & HOLE)
OrCell( r2, c2, s2, HOLE );
}
else {
printf( "internal error\n" );
exit( -1 );
}
}
if (r2 == rr1 && c2 == cc1) { /* see if source */
switch (x) {
case FROM_NORTH:
OrCell( r2, c2, s2, HOLE_SOUTH ); break;
case FROM_EAST:
OrCell( r2, c2, s2, HOLE_WEST ); break;
case FROM_SOUTH:
OrCell( r2, c2, s2, HOLE_NORTH ); break;
case FROM_WEST:
OrCell( r2, c2, s2, HOLE_EAST ); break;
case FROM_NORTHEAST:
OrCell( r2, c2, s2, HOLE_SOUTHWEST ); break;
case FROM_SOUTHEAST:
OrCell( r2, c2, s2, HOLE_NORTHWEST ); break;
case FROM_SOUTHWEST:
OrCell( r2, c2, s2, HOLE_NORTHEAST ); break;
case FROM_NORTHWEST:
OrCell( r2, c2, s2, HOLE_SOUTHEAST ); break;
case FROM_OTHERSIDE:
default:
printf( "internal error\n" );
exit( -1 );
break;
}
}
/* move to next cell */
r0 = r1; c0 = c1; s0 = s1;
r1 = r2; c1 = c2; s1 = s2;
} while (!(r2 == rr1 && c2 == cc1));
}


[WORK.C]

#include
#include
#include
#include "cell.h"

struct work { /* a unit of work is a hole-pair to connect */
int FromRow; /* source row */
int FromCol; /* source column */
char far *FromName; /* source name */
int ToRow; /* target row */
int ToCol; /* target column */
char far *ToName; /* target name */
int ApxDist; /* approximate distance */
int Priority; /* 0=no, 1=yes */
struct work far *Next;
};

/* pointers to the first and last item of work to do */
static struct work far *Head = NULL;
static struct work far *Tail = NULL;

extern int Ntotal;

extern int GetApxDist( int, int, int, int );
extern void Nomem( void );

void InitWork( void );
void SetWork( int, int, char far *, int, int, char far *, int );
void GetWork( int *, int *, char far * far *, int *, int *, char far * far * );
void SortWork( void );

void InitWork () { /* initialize the work list */
struct work far *p;

while (p = Head) {
Head = p->Next;
_ffree( p );
}
Tail = NULL;
}


void SetWork ( r1, c1, n1, r2, c2, n2, pri )
/* add a unit of work to the work list */
int r1, c1, r2, c2, pri;
char far *n1;
char far *n2;
{
struct work far *p;

if (p = (struct work far *)_fmalloc( sizeof(struct work) )) {
p->FromRow = r1;
p->FromCol = c1;
p->FromName = n1;
p->ToRow = r2;
p->ToCol = c2;
p->ToName = n2;
p->ApxDist = GetApxDist( r1, c1, r2, c2 );
p->Priority = pri;
p->Next = NULL;
if (Head) /* attach at end */
Tail->Next = p;
else /* first in list */
Head = p;
Tail = p;
Ntotal++;
}
else /* can't get any more memory */
Nomem();
}

void GetWork ( r1, c1, n1, r2, c2, n2 )
/* fetch a unit of work from the work list */
int *r1, *c1, *r2, *c2;
char far * far *n1;
char far * far *n2;
{
struct work far *p;

if (p = Head) {
*r1 = p->FromRow;
*c1 = p->FromCol;
*n1 = p->FromName;
*r2 = p->ToRow;
*c2 = p->ToCol;
*n2 = p->ToName;
if (!(Head = p->Next))
Tail = NULL;
_ffree( p );
}
else { /* none left */
*r1 = *c1 = *r2 = *c2 = ILLEGAL;
*n1 = *n2 = NULL;
}
}

void SortWork () { /* order the work items; shortest first */
struct work far *p;
struct work far *q0; /* put PRIORITY CONNECTs in q0 */
struct work far *q1; /* sort other CONNECTs in q1 */
struct work far *r;

q0 = q1 = NULL;
while (p = Head) { /* prioritize each work item */
Head = Head->Next;
if (p->Priority) {
if (!(r = q0)) {
p->Next = q0;
q0 = p;
}
else {
while (r->Next)
r = r->Next;
p->Next = r->Next;
r->Next = p;
}
}
else if (!(r = q1) || p->ApxDist < q1->ApxDist) {
p->Next = q1;
q1 = p;
}
else { /* find proper position in list */
while (r->Next && p->ApxDist >= r->ApxDist)
r = r->Next;
p->Next = r->Next;
r->Next = p;
}
}
if (p = q0) {
while (q0->Next)
q0 = q0->Next;
q0->Next = q1;
}
else
p = q1;
/* reposition Head and Tail */
for (Tail = Head = p; Tail && Tail->Next; Tail = Tail->Next)
;
}