KiCad PCB EDA Suite
Loading...
Searching...
No Matches
connectivity_algo.h
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) 2013-2017 CERN
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Maciej Suminski <[email protected]>
8 * @author Tomasz Wlostowski <[email protected]>
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, you may find one here:
22 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23 * or you may search the http://www.gnu.org website for the version 2 license,
24 * or you may write to the Free Software Foundation, Inc.,
25 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26 */
27
28// #define CONNECTIVITY_DEBUG
29
30#ifndef __CONNECTIVITY_ALGO_H
31#define __CONNECTIVITY_ALGO_H
32
33#include <board.h>
34#include <pad.h>
35#include <footprint.h>
36#include <zone.h>
37
39
40#include <memory>
41#include <algorithm>
42#include <functional>
43#include <vector>
44#include <deque>
45
49
50class CN_RATSNEST_NODES;
51class BOARD;
53class BOARD_ITEM;
54class ZONE;
56
57
63{
64public:
66 m_weight( 0 ),
67 m_visible( true )
68 {}
69
70 CN_EDGE( const std::shared_ptr<CN_ANCHOR>& aSource, const std::shared_ptr<CN_ANCHOR>& aTarget,
71 unsigned aWeight = 0 ) :
72 m_source( aSource ),
73 m_target( aTarget ),
74 m_weight( aWeight ),
75 m_visible( true )
76 {}
77
84 bool operator<( CN_EDGE aOther ) const
85 {
86 return m_weight < aOther.m_weight;
87 }
88
101 bool StableSortCompare( const CN_EDGE& aOther ) const
102 {
103 const VECTOR2I& thisPos = GetSourcePos();
104 const VECTOR2I& otherPos = aOther.GetSourcePos();
105
106 // First compare by source node position
107 if( thisPos.x != otherPos.x )
108 return thisPos.x < otherPos.x;
109
110 if( thisPos.y != otherPos.y )
111 return thisPos.y < otherPos.y;
112
113 // Then compare by weight
114 if( m_weight != aOther.m_weight )
115 return m_weight < aOther.m_weight;
116
117 // Then by visibility
118 if( m_visible != aOther.m_visible )
119 return m_visible && !aOther.m_visible;
120
121 // If everything is equal, return false for stable ordering
122 return false;
123 }
124
125 std::shared_ptr<const CN_ANCHOR> GetSourceNode() const { return m_source; }
126 std::shared_ptr<const CN_ANCHOR> GetTargetNode() const { return m_target; }
127
128 void SetSourceNode( const std::shared_ptr<const CN_ANCHOR>& aNode ) { m_source = aNode; }
129 void SetTargetNode( const std::shared_ptr<const CN_ANCHOR>& aNode ) { m_target = aNode; }
130
132 {
133 if( m_source && !m_source->Valid() )
134 m_source.reset();
135
136 if( m_target && !m_target->Valid() )
137 m_target.reset();
138 }
139
140 void SetWeight( unsigned weight ) { m_weight = weight; }
141 unsigned GetWeight() const { return m_weight; }
142
143 void SetVisible( bool aVisible ) { m_visible = aVisible; }
144 bool IsVisible() const { return m_visible; }
145
146 const VECTOR2I GetSourcePos() const { return m_source->Pos(); }
147 const VECTOR2I GetTargetPos() const { return m_target->Pos(); }
148 unsigned GetLength() const
149 {
150 return ( m_target->Pos() - m_source->Pos() ).EuclideanNorm();
151 }
152
153private:
154 std::shared_ptr<const CN_ANCHOR> m_source;
155 std::shared_ptr<const CN_ANCHOR> m_target;
156 unsigned m_weight;
158};
159
160
162{
163public:
165 {
169 };
170
171 using CLUSTERS = std::vector<std::shared_ptr<CN_CLUSTER>>;
172
173 /*
174 * Holds a list of CN_ITEMs for a given BOARD_CONNECTED_ITEM. For most items (pads, tracks,
175 * etc.) the list will have a single CN_ITEM, but for ZONEs it will have one item for each
176 * distinct outline on each layer.
177 */
179 {
180 public:
181 ITEM_MAP_ENTRY( CN_ITEM* aItem = nullptr )
182 {
183 if( aItem )
184 m_items.push_back( aItem );
185 }
186
188 {
189 for( CN_ITEM* item : m_items )
190 item->SetValid( false );
191 }
192
193 void Link( CN_ITEM* aItem )
194 {
195 m_items.push_back( aItem );
196 }
197
198 const std::list<CN_ITEM*>& GetItems() const
199 {
200 return m_items;
201 }
202
203 std::list<CN_ITEM*> m_items;
204 };
205
206 CN_CONNECTIVITY_ALGO( CONNECTIVITY_DATA* aParentConnectivityData ) :
207 m_parentConnectivityData( aParentConnectivityData ),
208 m_isLocal( false )
209 {}
210
212 {
213 Clear();
214 }
215
216 bool ItemExists( const BOARD_CONNECTED_ITEM* aItem ) const
217 {
218 return m_itemMap.find( aItem ) != m_itemMap.end();
219 }
220
222 {
223 return m_itemMap[ aItem ];
224 }
225
226 bool IsNetDirty( int aNet ) const
227 {
228 if( aNet < 0 )
229 return false;
230
231 return m_dirtyNets[ aNet ];
232 }
233
235 {
236 for( size_t ii = 0; ii < m_dirtyNets.size(); ii++ )
237 m_dirtyNets[ii] = false;
238 }
239
240 void GetDirtyClusters( CLUSTERS& aClusters ) const
241 {
242 for( const std::shared_ptr<CN_CLUSTER>& cl : m_ratsnestClusters )
243 {
244 int net = cl->OriginNet();
245
246 if( net >= 0 && m_dirtyNets[net] )
247 aClusters.push_back( cl );
248 }
249 }
250
251 int NetCount() const
252 {
253 return m_dirtyNets.size();
254 }
255
256 void Build( BOARD* aBoard, PROGRESS_REPORTER* aReporter = nullptr );
257 void LocalBuild( const std::shared_ptr<CONNECTIVITY_DATA>& aGlobalConnectivity,
258 const std::vector<BOARD_ITEM*>& aLocalItems );
259
260 void Clear();
261
262 bool Remove( BOARD_ITEM* aItem );
263 bool Add( BOARD_ITEM* aItem );
264
265 const CLUSTERS SearchClusters( CLUSTER_SEARCH_MODE aMode, bool aExcludeZones, int aSingleNet );
267
272 void PropagateNets( BOARD_COMMIT* aCommit = nullptr );
273
277 void FillIsolatedIslandsMap( std::map<ZONE*, std::map<PCB_LAYER_ID, ISOLATED_ISLANDS>>& aMap,
278 bool aConnectivityAlreadyRebuilt );
279
280 const CLUSTERS& GetClusters();
281
282 const CN_LIST& ItemList() const
283 {
284 return m_itemList;
285 }
286
287 template <typename Func>
288 void ForEachAnchor( Func&& aFunc ) const
289 {
290 for( CN_ITEM* item : m_itemList )
291 {
292 for( std::shared_ptr<CN_ANCHOR>& anchor : item->Anchors() )
293 aFunc( *anchor );
294 }
295 }
296
297 template <typename Func>
298 void ForEachItem( Func&& aFunc ) const
299 {
300 for( CN_ITEM* item : m_itemList )
301 aFunc( *item );
302 }
303
304 void MarkNetAsDirty( int aNet );
305 void RemoveInvalidRefs();
306
307 void SetProgressReporter( PROGRESS_REPORTER* aReporter );
308
309private:
310 void searchConnections();
311
312 void propagateConnections( BOARD_COMMIT* aCommit = nullptr );
313
314 template <class Container, class BItem>
315 void add( Container& c, BItem brditem )
316 {
317 CN_ITEM* item = c.Add( brditem );
318
319 m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
320 }
321
322 void markItemNetAsDirty( const BOARD_ITEM* aItem );
323
324 void updateJumperPads();
325
326private:
329 std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> m_itemMap;
330
331 std::vector<std::shared_ptr<CN_CLUSTER>> m_connClusters;
332 std::vector<std::shared_ptr<CN_CLUSTER>> m_ratsnestClusters;
333 std::vector<bool> m_dirtyNets;
334
336 std::shared_ptr<CONNECTIVITY_DATA> m_globalConnectivityData;
337
338 std::mutex m_mutex;
339
341};
342
343
345{
346public:
347 CN_VISITOR( CN_ITEM* aItem ) :
348 m_item( aItem )
349 {}
350
351 bool operator()( CN_ITEM* aCandidate );
352
353protected:
354 void checkZoneItemConnection( CN_ZONE_LAYER* aZoneLayer, CN_ITEM* aItem );
355
356 void checkZoneZoneConnection( CN_ZONE_LAYER* aZoneLayerA, CN_ZONE_LAYER* aZoneLayerB );
357
358protected:
360};
361
362#endif
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:79
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:317
ITEM_MAP_ENTRY(CN_ITEM *aItem=nullptr)
const std::list< CN_ITEM * > & GetItems() const
void MarkItemsAsInvalid()
std::list< CN_ITEM * > m_items
void Link(CN_ITEM *aItem)
void FillIsolatedIslandsMap(std::map< ZONE *, std::map< PCB_LAYER_ID, ISOLATED_ISLANDS > > &aMap, bool aConnectivityAlreadyRebuilt)
Fill in the isolated islands map with copper islands that are not connected to a net.
bool Remove(BOARD_ITEM *aItem)
bool ItemExists(const BOARD_CONNECTED_ITEM *aItem) const
void ForEachItem(Func &&aFunc) const
CN_CONNECTIVITY_ALGO(CONNECTIVITY_DATA *aParentConnectivityData)
CONNECTIVITY_DATA * m_parentConnectivityData
void add(Container &c, BItem brditem)
PROGRESS_REPORTER * m_progressReporter
std::vector< std::shared_ptr< CN_CLUSTER > > m_connClusters
ITEM_MAP_ENTRY & ItemEntry(const BOARD_CONNECTED_ITEM *aItem)
void GetDirtyClusters(CLUSTERS &aClusters) const
void propagateConnections(BOARD_COMMIT *aCommit=nullptr)
const CLUSTERS & GetClusters()
void LocalBuild(const std::shared_ptr< CONNECTIVITY_DATA > &aGlobalConnectivity, const std::vector< BOARD_ITEM * > &aLocalItems)
void MarkNetAsDirty(int aNet)
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, bool aExcludeZones, int aSingleNet)
void markItemNetAsDirty(const BOARD_ITEM *aItem)
std::vector< std::shared_ptr< CN_CLUSTER > > m_ratsnestClusters
void ForEachAnchor(Func &&aFunc) const
void PropagateNets(BOARD_COMMIT *aCommit=nullptr)
Propagate nets from pads to other items in clusters.
std::shared_ptr< CONNECTIVITY_DATA > m_globalConnectivityData
const CN_LIST & ItemList() const
bool IsNetDirty(int aNet) const
std::vector< bool > m_dirtyNets
std::vector< std::shared_ptr< CN_CLUSTER > > CLUSTERS
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
void Build(BOARD *aBoard, PROGRESS_REPORTER *aReporter=nullptr)
bool Add(BOARD_ITEM *aItem)
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
std::shared_ptr< const CN_ANCHOR > GetSourceNode() const
std::shared_ptr< const CN_ANCHOR > m_target
bool StableSortCompare(const CN_EDGE &aOther) const
Comparison operator for std::stable_sort.
void SetTargetNode(const std::shared_ptr< const CN_ANCHOR > &aNode)
void SetWeight(unsigned weight)
void RemoveInvalidRefs()
void SetSourceNode(const std::shared_ptr< const CN_ANCHOR > &aNode)
void SetVisible(bool aVisible)
unsigned GetWeight() const
std::shared_ptr< const CN_ANCHOR > GetTargetNode() const
unsigned m_weight
const VECTOR2I GetTargetPos() const
unsigned GetLength() const
std::shared_ptr< const CN_ANCHOR > m_source
CN_EDGE(const std::shared_ptr< CN_ANCHOR > &aSource, const std::shared_ptr< CN_ANCHOR > &aTarget, unsigned aWeight=0)
const VECTOR2I GetSourcePos() const
bool IsVisible() const
bool operator<(CN_EDGE aOther) const
This sort operator provides a sort-by-weight for the ratsnest operation.
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
CN_VISITOR(CN_ITEM *aItem)
void checkZoneItemConnection(CN_ZONE_LAYER *aZoneLayer, CN_ITEM *aItem)
CN_ITEM * m_item
The item we are looking for connections to.
void checkZoneZoneConnection(CN_ZONE_LAYER *aZoneLayerA, CN_ZONE_LAYER *aZoneLayerB)
bool operator()(CN_ITEM *aCandidate)
A progress reporter interface for use in multi-threaded environments.
Handle a list of polygons defining a copper zone.
Definition: zone.h:74