home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 1 / ARM_CLUB_CD.iso / contents / education / a / autopcb / !AutoPCB / c / WORK < prev   
Text File  |  1991-03-23  |  5KB  |  143 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #include "heap.h"
  5.  
  6. #include "cell.h"
  7.  
  8. #define far
  9.  
  10. struct work { /* a unit of work is a hole-pair to connect */
  11.         int FromRow;            /* source row           */
  12.         int FromCol;            /* source column        */
  13.         char far *FromName;     /* source name          */
  14.         int ToRow;              /* target row           */
  15.         int ToCol;              /* target column        */
  16.         char far *ToName;       /* target name          */
  17.         int ApxDist;            /* approximate distance */
  18.         int Priority;           /* 0=no, 1=yes          */
  19.         struct work far *Next;
  20.         };
  21.  
  22. /* pointers to the first and last item of work to do */
  23. static struct work far *Head = NULL;
  24. static struct work far *Tail = NULL;
  25.  
  26. extern int Ntotal;
  27.  
  28. extern int GetApxDist( int, int, int, int );
  29. extern void Nomem( void );
  30.  
  31. void InitWork( void );
  32. void SetWork( int, int, char far *, int, int, char far *, int );
  33. void GetWork( int *, int *, char far * far *, int *, int *, char far * far * );
  34. void SortWork( void );
  35.  
  36. void InitWork () { /* initialize the work list */
  37.         struct work far *p;
  38.  
  39.         while (p = Head) {
  40.                 Head = p->Next;
  41.                 heap_free( p );
  42.                 }
  43.         Tail = NULL;
  44.         }
  45.  
  46. void SetWork ( r1, c1, n1, r2, c2, n2, pri )
  47.         /* add a unit of work to the work list */
  48.         int r1, c1, r2, c2, pri;
  49.         char far *n1;
  50.         char far *n2;
  51.         {
  52.         struct work far *p;
  53.  
  54.         if (p = (struct work far *)heap_alloc( sizeof(struct work) )) {
  55.                 p->FromRow = r1;
  56.                 p->FromCol = c1;
  57.                 p->FromName = n1;
  58.                 p->ToRow = r2;
  59.                 p->ToCol = c2;
  60.                 p->ToName = n2;
  61.                 p->ApxDist = GetApxDist( r1, c1, r2, c2 );
  62.                 p->Priority = pri;
  63.                 p->Next = NULL;
  64.                 if (Head) /* attach at end */
  65.                         Tail->Next = p;
  66.                 else /* first in list */
  67.                         Head = p;
  68.                 Tail = p;
  69.                 Ntotal++;
  70.                 }
  71.         else /* can't get any more memory */
  72.                 Nomem();
  73.         }
  74.  
  75. void GetWork ( r1, c1, n1, r2, c2, n2 )
  76.         /* fetch a unit of work from the work list */
  77.         int *r1, *c1, *r2, *c2;
  78.         char far * far *n1;
  79.         char far * far *n2;
  80.         {
  81.         struct work far *p;
  82.  
  83.         if (p = Head) {
  84.                 *r1 = p->FromRow;
  85.                 *c1 = p->FromCol;
  86.                 *n1 = p->FromName;
  87.                 *r2 = p->ToRow;
  88.                 *c2 = p->ToCol;
  89.                 *n2 = p->ToName;
  90.                 if (!(Head = p->Next))
  91.                         Tail = NULL;
  92.                 heap_free( p );
  93.                 }
  94.         else { /* none left */
  95.                 *r1 = *c1 = *r2 = *c2 = ILLEGAL;
  96.                 *n1 = *n2 = NULL;
  97.                 }
  98.         }
  99.  
  100. void SortWork () { /* order the work items; shortest first */
  101.         struct work far *p;
  102.         struct work far *q0; /* put PRIORITY CONNECTs in q0 */
  103.         struct work far *q1; /* sort other CONNECTs in q1 */
  104.         struct work far *r;
  105.  
  106.         q0 = q1 = NULL;
  107.         while (p = Head) { /* prioritize each work item */
  108.                 Head = Head->Next;
  109.                 if (p->Priority) {
  110.                         if (!(r = q0)) {
  111.                                 p->Next = q0;
  112.                                 q0 = p;
  113.                                 }
  114.                         else {
  115.                                 while (r->Next)
  116.                                         r = r->Next;
  117.                                 p->Next = r->Next;
  118.                                 r->Next = p;
  119.                                 }
  120.                         }
  121.                 else if (!(r = q1) || p->ApxDist < q1->ApxDist) {
  122.                         p->Next = q1;
  123.                         q1 = p;
  124.                         }
  125.                 else { /* find proper position in list */
  126.                         while (r->Next && p->ApxDist >= r->ApxDist)
  127.                                 r = r->Next;
  128.                         p->Next = r->Next;
  129.                         r->Next = p;
  130.                         }
  131.                 }
  132.         if (p = q0) {
  133.                 while (q0->Next)
  134.                         q0 = q0->Next;
  135.                 q0->Next = q1;
  136.                 }
  137.         else
  138.                 p = q1;
  139.         /* reposition Head and Tail */
  140.         for (Tail = Head = p; Tail && Tail->Next; Tail = Tail->Next)
  141.                 ;
  142.         }
  143.