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 (C) 2019-2023 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
89 std::shared_ptr<const CN_ANCHOR> GetSourceNode() const { return m_source; }
90 std::shared_ptr<const CN_ANCHOR> GetTargetNode() const { return m_target; }
91
92 void SetSourceNode( const std::shared_ptr<const CN_ANCHOR>& aNode ) { m_source = aNode; }
93 void SetTargetNode( const std::shared_ptr<const CN_ANCHOR>& aNode ) { m_target = aNode; }
94
96 {
97 if( m_source && !m_source->Valid() )
98 m_source.reset();
99
100 if( m_target && !m_target->Valid() )
101 m_target.reset();
102 }
103
104 void SetWeight( unsigned weight ) { m_weight = weight; }
105 unsigned GetWeight() const { return m_weight; }
106
107 void SetVisible( bool aVisible ) { m_visible = aVisible; }
108 bool IsVisible() const { return m_visible; }
109
110 const VECTOR2I GetSourcePos() const { return m_source->Pos(); }
111 const VECTOR2I GetTargetPos() const { return m_target->Pos(); }
112 unsigned GetLength() const
113 {
114 return ( m_target->Pos() - m_source->Pos() ).EuclideanNorm();
115 }
116
117private:
118 std::shared_ptr<const CN_ANCHOR> m_source;
119 std::shared_ptr<const CN_ANCHOR> m_target;
120 unsigned m_weight;
122};
123
124
126{
127public:
129 {
133 };
134
135 using CLUSTERS = std::vector<std::shared_ptr<CN_CLUSTER>>;
136
137 /*
138 * Holds a list of CN_ITEMs for a given BOARD_CONNECTED_ITEM. For most items (pads, tracks,
139 * etc.) the list will have a single CN_ITEM, but for ZONEs it will have one item for each
140 * distinct outline on each layer.
141 */
143 {
144 public:
145 ITEM_MAP_ENTRY( CN_ITEM* aItem = nullptr )
146 {
147 if( aItem )
148 m_items.push_back( aItem );
149 }
150
152 {
153 for( CN_ITEM* item : m_items )
154 item->SetValid( false );
155 }
156
157 void Link( CN_ITEM* aItem )
158 {
159 m_items.push_back( aItem );
160 }
161
162 const std::list<CN_ITEM*>& GetItems() const
163 {
164 return m_items;
165 }
166
167 std::list<CN_ITEM*> m_items;
168 };
169
170 CN_CONNECTIVITY_ALGO( CONNECTIVITY_DATA* aParentConnectivityData ) :
171 m_parentConnectivityData( aParentConnectivityData ),
172 m_isLocal( false )
173 {}
174
176 {
177 Clear();
178 }
179
180 bool ItemExists( const BOARD_CONNECTED_ITEM* aItem ) const
181 {
182 return m_itemMap.find( aItem ) != m_itemMap.end();
183 }
184
186 {
187 return m_itemMap[ aItem ];
188 }
189
190 bool IsNetDirty( int aNet ) const
191 {
192 if( aNet < 0 )
193 return false;
194
195 return m_dirtyNets[ aNet ];
196 }
197
199 {
200 for( size_t ii = 0; ii < m_dirtyNets.size(); ii++ )
201 m_dirtyNets[ii] = false;
202 }
203
204 void GetDirtyClusters( CLUSTERS& aClusters ) const
205 {
206 for( const std::shared_ptr<CN_CLUSTER>& cl : m_ratsnestClusters )
207 {
208 int net = cl->OriginNet();
209
210 if( net >= 0 && m_dirtyNets[net] )
211 aClusters.push_back( cl );
212 }
213 }
214
215 int NetCount() const
216 {
217 return m_dirtyNets.size();
218 }
219
220 void Build( BOARD* aBoard, PROGRESS_REPORTER* aReporter = nullptr );
221 void LocalBuild( std::shared_ptr<CONNECTIVITY_DATA> aGlobalConnectivity,
222 const std::vector<BOARD_ITEM*>& aLocalItems );
223
224 void Clear();
225
226 bool Remove( BOARD_ITEM* aItem );
227 bool Add( BOARD_ITEM* aItem );
228
230 const std::initializer_list<KICAD_T>& aTypes,
231 int aSingleNet, CN_ITEM* rootItem = nullptr );
233
238 void PropagateNets( BOARD_COMMIT* aCommit = nullptr );
239
243 void FillIsolatedIslandsMap( std::map<ZONE*, std::map<PCB_LAYER_ID, ISOLATED_ISLANDS>>& aMap,
244 bool aConnectivityAlreadyRebuilt );
245
246 const CLUSTERS& GetClusters();
247
248 const CN_LIST& ItemList() const
249 {
250 return m_itemList;
251 }
252
253 template <typename Func>
254 void ForEachAnchor( Func&& aFunc ) const
255 {
256 for( CN_ITEM* item : m_itemList )
257 {
258 for( std::shared_ptr<CN_ANCHOR>& anchor : item->Anchors() )
259 aFunc( *anchor );
260 }
261 }
262
263 template <typename Func>
264 void ForEachItem( Func&& aFunc ) const
265 {
266 for( CN_ITEM* item : m_itemList )
267 aFunc( *item );
268 }
269
270 void MarkNetAsDirty( int aNet );
271 void RemoveInvalidRefs();
272
273 void SetProgressReporter( PROGRESS_REPORTER* aReporter );
274
275private:
276 void searchConnections();
277
278 void propagateConnections( BOARD_COMMIT* aCommit = nullptr );
279
280 template <class Container, class BItem>
281 void add( Container& c, BItem brditem )
282 {
283 CN_ITEM* item = c.Add( brditem );
284
285 m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
286 }
287
288 void markItemNetAsDirty( const BOARD_ITEM* aItem );
289
290private:
293 std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> m_itemMap;
294
295 std::vector<std::shared_ptr<CN_CLUSTER>> m_connClusters;
296 std::vector<std::shared_ptr<CN_CLUSTER>> m_ratsnestClusters;
297 std::vector<bool> m_dirtyNets;
298
300 std::shared_ptr<CONNECTIVITY_DATA> m_globalConnectivityData;
301
303};
304
305
307{
308public:
309 CN_VISITOR( CN_ITEM* aItem ) :
310 m_item( aItem )
311 {}
312
313 bool operator()( CN_ITEM* aCandidate );
314
315protected:
316 void checkZoneItemConnection( CN_ZONE_LAYER* aZoneLayer, CN_ITEM* aItem );
317
318 void checkZoneZoneConnection( CN_ZONE_LAYER* aZoneLayerA, CN_ZONE_LAYER* aZoneLayerB );
319
320protected:
322};
323
324#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:77
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:276
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
void LocalBuild(std::shared_ptr< CONNECTIVITY_DATA > aGlobalConnectivity, const std::vector< BOARD_ITEM * > &aLocalItems)
ITEM_MAP_ENTRY & ItemEntry(const BOARD_CONNECTED_ITEM *aItem)
void GetDirtyClusters(CLUSTERS &aClusters) const
void propagateConnections(BOARD_COMMIT *aCommit=nullptr)
const CLUSTERS & GetClusters()
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const std::initializer_list< KICAD_T > &aTypes, int aSingleNet, CN_ITEM *rootItem=nullptr)
void MarkNetAsDirty(int aNet)
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
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:72