KiCad PCB EDA Suite
work.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
5  * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6  * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
7  *
8  * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
9  *
10  * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
11  *
12  * This program is free software; you can redistribute it and/or
13  * modify it under the terms of the GNU General Public License
14  * as published by the Free Software Foundation; either version 2
15  * of the License, or (at your option) any later version.
16  *
17  * This program is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20  * GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License
23  * along with this program; if not, you may find one here:
24  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
25  * or you may search the http://www.gnu.org website for the version 2 license,
26  * or you may write to the Free Software Foundation, Inc.,
27  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
28  */
29 
30 
36 #include <fctsys.h>
37 #include <common.h>
38 
39 #include <pcbnew.h>
40 #include <autorout.h>
41 #include <cell.h>
42 
43 
44 struct CWORK // a unit of work is a source-target to connect
45  // this is a ratsnest item in the routing matrix world
46 {
47  int m_FromRow; // source row
48  int m_FromCol; // source column
49  int m_ToRow; // target row
50  int m_ToCol; // target column
51  RATSNEST_ITEM* m_Ratsnest; // Corresponding ratsnest
52  int m_NetCode; // m_NetCode
53  int m_ApxDist; // approximate distance
54  int m_Cost; // cost for sort by length
55  int m_Priority; // route priority
56 
57  // the function that calculates the cost of this ratsnest:
58  void CalculateCost();
59 };
60 
61 
62 // the list of ratsnests
63 static std::vector <CWORK> WorkList;
64 static unsigned Current = 0;
65 
66 
67 // initialize the work list
68 void InitWork()
69 {
70  WorkList.clear();
71  Current = 0;
72 }
73 
74 
75 /* add a unit of work to the work list
76  * :
77  * 1 if OK
78  * 0 if memory allocation failed
79  */
80 
81 int SetWork( int r1, int c1,
82  int n_c,
83  int r2, int c2,
84  RATSNEST_ITEM* pt_ch, int pri )
85 {
86  CWORK item;
87  item.m_FromRow = r1;
88  item.m_FromCol = c1;
89  item.m_NetCode = n_c;
90  item.m_ToRow = r2;
91  item.m_ToCol = c2;
92  item.m_Ratsnest = pt_ch;
93  item.m_ApxDist = RoutingMatrix.GetApxDist( r1, c1, r2, c2 );
94  item.CalculateCost();
95  item.m_Priority = pri;
96  WorkList.push_back( item );
97  return 1;
98 }
99 
100 
101 /* fetch a unit of work from the work list */
102 void GetWork( int* r1, int* c1,
103  int* n_c,
104  int* r2, int* c2,
105  RATSNEST_ITEM** pt_ch )
106 {
107  if( Current < WorkList.size() )
108  {
109  *r1 = WorkList[Current].m_FromRow;
110  *c1 = WorkList[Current].m_FromCol;
111  *n_c = WorkList[Current].m_NetCode;
112  *r2 = WorkList[Current].m_ToRow;
113  *c2 = WorkList[Current].m_ToCol;
114  *pt_ch = WorkList[Current].m_Ratsnest;
115  Current++;
116  }
117  else /* none left */
118  {
119  *r1 = *c1 = *r2 = *c2 = ILLEGAL;
120  *n_c = 0;
121  *pt_ch = NULL;
122  }
123 }
124 
125 
126 // order the work items; shortest (low cost) first:
127 bool sort_by_cost( const CWORK& ref, const CWORK& item )
128 {
129  if( ref.m_Priority == item.m_Priority )
130  return ref.m_Cost < item.m_Cost;
131 
132  return ref.m_Priority >= item.m_Priority;
133 }
134 
135 void SortWork()
136 {
137  sort( WorkList.begin(), WorkList.end(), sort_by_cost );
138 }
139 
140 
141 /* Calculate the cost of a ratsnest:
142  * cost = (| dx | + | dy |) * disability
143  * disability = 1 if dx or dy = 0, max if | dx | # | dy |
144  */
146 {
147  int dx, dy, mx, my;
148  double incl = 1.0;
149 
150  dx = abs( m_ToCol - m_FromCol );
151  dy = abs( m_ToRow - m_FromRow );
152  mx = dx;
153  my = dy;
154 
155  if( mx < my )
156  {
157  mx = dy; my = dx;
158  }
159 
160  if( mx )
161  incl += (2 * (double) my / mx);
162 
163  m_Cost = (int) ( ( dx + dy ) * incl );
164 }
int m_FromRow
Definition: work.cpp:47
void SortWork()
Definition: work.cpp:135
int m_ApxDist
Definition: work.cpp:53
bool sort_by_cost(const CWORK &ref, const CWORK &item)
Definition: work.cpp:127
int m_Cost
Definition: work.cpp:54
void InitWork()
Definition: work.cpp:68
int m_ToRow
Definition: work.cpp:49
#define ILLEGAL
Definition: autorout.h:52
static unsigned Current
Definition: work.cpp:64
#define abs(a)
Definition: auxiliary.h:84
int m_ToCol
Definition: work.cpp:50
int GetApxDist(int r1, int c1, int r2, int c2)
Definition: dist.cpp:42
int m_FromCol
Definition: work.cpp:48
Definition: work.cpp:44
int m_Priority
Definition: work.cpp:55
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
static std::vector< CWORK > WorkList
Definition: work.cpp:63
void GetWork(int *r1, int *c1, int *n_c, int *r2, int *c2, RATSNEST_ITEM **pt_ch)
Definition: work.cpp:102
The common library.
int SetWork(int r1, int c1, int n_c, int r2, int c2, RATSNEST_ITEM *pt_ch, int pri)
Definition: work.cpp:81
void CalculateCost()
Definition: work.cpp:145
RATSNEST_ITEM * m_Ratsnest
Definition: work.cpp:51
int m_NetCode
Definition: work.cpp:52