KiCad PCB EDA Suite
CN_CONNECTIVITY_ALGO Class Reference

#include <connectivity_algo.h>

Classes

class  ITEM_MAP_ENTRY
 

Public Types

enum  CLUSTER_SEARCH_MODE { CSM_PROPAGATE , CSM_CONNECTIVITY_CHECK , CSM_RATSNEST }
 
using CLUSTERS = std::vector< std::shared_ptr< CN_CLUSTER > >
 

Public Member Functions

 CN_CONNECTIVITY_ALGO ()
 
 ~CN_CONNECTIVITY_ALGO ()
 
bool ItemExists (const BOARD_CONNECTED_ITEM *aItem) const
 
ITEM_MAP_ENTRYItemEntry (const BOARD_CONNECTED_ITEM *aItem)
 
bool IsNetDirty (int aNet) const
 
void ClearDirtyFlags ()
 
void GetDirtyClusters (CLUSTERS &aClusters) const
 
int NetCount () const
 
void Build (BOARD *aZoneLayer, PROGRESS_REPORTER *aReporter=nullptr)
 
void LocalBuild (const std::vector< BOARD_ITEM * > &aItems)
 
void Clear ()
 
bool Remove (BOARD_ITEM *aItem)
 
bool Add (BOARD_ITEM *aItem)
 
const CLUSTERS SearchClusters (CLUSTER_SEARCH_MODE aMode, const std::initializer_list< KICAD_T > &aTypes, int aSingleNet, CN_ITEM *rootItem=nullptr)
 
const CLUSTERS SearchClusters (CLUSTER_SEARCH_MODE aMode)
 
void PropagateNets (BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)
 Propagate nets from pads to other items in clusters. More...
 
void FindIsolatedCopperIslands (ZONE *aZone, PCB_LAYER_ID aLayer, std::vector< int > &aIslands)
 
void FindIsolatedCopperIslands (std::vector< CN_ZONE_ISOLATED_ISLAND_LIST > &aZones, bool aConnectivityAlreadyRebuilt)
 Find the copper islands that are not connected to a net. More...
 
const CLUSTERSGetClusters ()
 
const CN_LISTItemList () const
 
template<typename Func >
void ForEachAnchor (Func &&aFunc) const
 
template<typename Func >
void ForEachItem (Func &&aFunc) const
 
void MarkNetAsDirty (int aNet)
 
void SetProgressReporter (PROGRESS_REPORTER *aReporter)
 

Private Member Functions

void searchConnections ()
 
void propagateConnections (BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)
 
template<class Container , class BItem >
void add (Container &c, BItem brditem)
 
void markItemNetAsDirty (const BOARD_ITEM *aItem)
 

Private Attributes

CN_LIST m_itemList
 
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRYm_itemMap
 
std::vector< std::shared_ptr< CN_CLUSTER > > m_connClusters
 
std::vector< std::shared_ptr< CN_CLUSTER > > m_ratsnestClusters
 
std::vector< bool > m_dirtyNets
 
PROGRESS_REPORTERm_progressReporter = nullptr
 

Detailed Description

Definition at line 117 of file connectivity_algo.h.

Member Typedef Documentation

◆ CLUSTERS

using CN_CONNECTIVITY_ALGO::CLUSTERS = std::vector<std::shared_ptr<CN_CLUSTER> >

Definition at line 127 of file connectivity_algo.h.

Member Enumeration Documentation

◆ CLUSTER_SEARCH_MODE

Enumerator
CSM_PROPAGATE 
CSM_CONNECTIVITY_CHECK 
CSM_RATSNEST 

Definition at line 120 of file connectivity_algo.h.

Constructor & Destructor Documentation

◆ CN_CONNECTIVITY_ALGO()

CN_CONNECTIVITY_ALGO::CN_CONNECTIVITY_ALGO ( )
inline

Definition at line 157 of file connectivity_algo.h.

157{}

◆ ~CN_CONNECTIVITY_ALGO()

CN_CONNECTIVITY_ALGO::~CN_CONNECTIVITY_ALGO ( )
inline

Definition at line 158 of file connectivity_algo.h.

References Clear().

Member Function Documentation

◆ Add()

bool CN_CONNECTIVITY_ALGO::Add ( BOARD_ITEM aItem)

Definition at line 117 of file connectivity_algo.cpp.

118{
119 if( !aItem->IsOnCopperLayer() )
120 return false;
121
122 switch( aItem->Type() )
123 {
124 case PCB_NETINFO_T:
125 MarkNetAsDirty( static_cast<NETINFO_ITEM*>( aItem )->GetNetCode() );
126 break;
127
128 case PCB_FOOTPRINT_T:
129 {
130 if( static_cast<FOOTPRINT*>( aItem )->GetAttributes() & FP_JUST_ADDED )
131 return false;
132
133 for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
134 {
135 if( m_itemMap.find( pad ) != m_itemMap.end() )
136 return false;
137
138 add( m_itemList, pad );
139 }
140
141 break;
142 }
143
144 case PCB_PAD_T:
145 {
146 if( FOOTPRINT* fp = dynamic_cast<FOOTPRINT*>( aItem->GetParentFootprint() ) )
147 {
148 if( fp->GetAttributes() & FP_JUST_ADDED )
149 return false;
150 }
151
152 if( m_itemMap.find( aItem ) != m_itemMap.end() )
153 return false;
154
155 add( m_itemList, static_cast<PAD*>( aItem ) );
156 break;
157 }
158
159 case PCB_TRACE_T:
160 if( m_itemMap.find( aItem ) != m_itemMap.end() )
161 return false;
162
163 add( m_itemList, static_cast<PCB_TRACK*>( aItem ) );
164 break;
165
166 case PCB_ARC_T:
167 if( m_itemMap.find( aItem ) != m_itemMap.end() )
168 return false;
169
170 add( m_itemList, static_cast<PCB_ARC*>( aItem ) );
171 break;
172
173 case PCB_VIA_T:
174 if( m_itemMap.find( aItem ) != m_itemMap.end() )
175 return false;
176
177 add( m_itemList, static_cast<PCB_VIA*>( aItem ) );
178 break;
179
180 case PCB_ZONE_T:
181 {
182 ZONE* zone = static_cast<ZONE*>( aItem );
183
184 if( m_itemMap.find( aItem ) != m_itemMap.end() )
185 return false;
186
187 m_itemMap[zone] = ITEM_MAP_ENTRY();
188
189 for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
190 {
191 for( CN_ITEM* zitem : m_itemList.Add( zone, layer ) )
192 m_itemMap[zone].Link( zitem );
193 }
194 }
195 break;
196
197 default:
198 return false;
199 }
200
201 markItemNetAsDirty( aItem );
202
203 return true;
204}
BOARD_ITEM_CONTAINER * GetParentFootprint() const
Definition: board_item.cpp:242
virtual bool IsOnCopperLayer() const
Definition: board_item.h:123
void add(Container &c, BItem brditem)
void MarkNetAsDirty(int aNet)
void markItemNetAsDirty(const BOARD_ITEM *aItem)
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
CN_ITEM * Add(PAD *pad)
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:97
LSEQ Seq(const PCB_LAYER_ID *aWishListSequence, unsigned aCount) const
Return an LSEQ from the union of this LSET and a desired sequence.
Definition: lset.cpp:411
Handle the data for a net.
Definition: netinfo.h:66
Definition: pad.h:59
Handle a list of polygons defining a copper zone.
Definition: zone.h:57
virtual LSET GetLayerSet() const override
Return a std::bitset of all layers on which the item physically resides.
Definition: zone.h:121
@ FP_JUST_ADDED
Definition: footprint.h:73
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:59
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:102
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition: typeinfo.h:112
@ PCB_FOOTPRINT_T
class FOOTPRINT, a footprint
Definition: typeinfo.h:86
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87
@ PCB_ARC_T
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:103
@ PCB_NETINFO_T
class NETINFO_ITEM, a description of a net
Definition: typeinfo.h:114
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:101

References add(), CN_LIST::Add(), FP_JUST_ADDED, ZONE::GetLayerSet(), BOARD_ITEM::GetParentFootprint(), BOARD_ITEM::IsOnCopperLayer(), m_itemList, m_itemMap, markItemNetAsDirty(), MarkNetAsDirty(), pad, PCB_ARC_T, PCB_FOOTPRINT_T, PCB_NETINFO_T, PCB_PAD_T, PCB_TRACE_T, PCB_VIA_T, PCB_ZONE_T, LSET::Seq(), and EDA_ITEM::Type().

Referenced by Build(), FindIsolatedCopperIslands(), and LocalBuild().

◆ add()

template<class Container , class BItem >
void CN_CONNECTIVITY_ALGO::add ( Container &  c,
BItem  brditem 
)
inlineprivate

Definition at line 268 of file connectivity_algo.h.

269 {
270 CN_ITEM* item = c.Add( brditem );
271
272 m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
273 }

References m_itemMap.

Referenced by Add().

◆ Build()

void CN_CONNECTIVITY_ALGO::Build ( BOARD aZoneLayer,
PROGRESS_REPORTER aReporter = nullptr 
)

Definition at line 413 of file connectivity_algo.cpp.

414{
415 // Generate CN_ZONE_LAYERs for each island on each layer of each zone
416 //
417 std::vector<CN_ZONE_LAYER*> zitems;
418
419 for( ZONE* zone : aBoard->Zones() )
420 {
421 if( zone->IsOnCopperLayer() )
422 {
423 m_itemMap[zone] = ITEM_MAP_ENTRY();
424 markItemNetAsDirty( zone );
425
426 for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
427 {
428 if( IsCopperLayer( layer ) )
429 {
430 for( int j = 0; j < zone->GetFilledPolysList( layer )->OutlineCount(); j++ )
431 zitems.push_back( new CN_ZONE_LAYER( zone, layer, j ) );
432 }
433 }
434 }
435 }
436
437 // Setup progress metrics
438 //
439 int progressDelta = 50;
440 double size = 0.0;
441
442 size += zitems.size(); // Once for building RTrees
443 size += zitems.size(); // Once for adding to connectivity
444 size += aBoard->Tracks().size();
445
446 for( FOOTPRINT* footprint : aBoard->Footprints() )
447 size += footprint->Pads().size();
448
449 size *= 1.5; // Our caller gets the other third of the progress bar
450
451 progressDelta = std::max( progressDelta, (int) size / 4 );
452
453 auto report =
454 [&]( int progress )
455 {
456 if( aReporter && ( progress % progressDelta ) == 0 )
457 {
458 aReporter->SetCurrentProgress( progress / size );
459 aReporter->KeepRefreshing( false );
460 }
461 };
462
463 // Generate RTrees for CN_ZONE_LAYER items (in parallel)
464 //
466 std::vector<std::future<size_t>> returns( zitems.size() );
467
468 auto cache_zones =
469 [aReporter]( CN_ZONE_LAYER* aZoneLayer ) -> size_t
470 {
471 if( aReporter && aReporter->IsCancelled() )
472 return 0;
473
474 aZoneLayer->BuildRTree();
475
476 if( aReporter )
477 aReporter->AdvanceProgress();
478
479 return 1;
480 };
481
482 for( size_t ii = 0; ii < zitems.size(); ++ii )
483 returns[ii] = tp.submit( cache_zones, zitems[ii] );
484
485 for( const std::future<size_t>& ret : returns )
486 {
487 std::future_status status = ret.wait_for( std::chrono::milliseconds( 250 ) );
488
489 while( status != std::future_status::ready )
490 {
491 if( aReporter )
492 aReporter->KeepRefreshing();
493
494 status = ret.wait_for( std::chrono::milliseconds( 250 ) );
495 }
496
497 }
498
499 // Add CN_ZONE_LAYERS, tracks, and pads to connectivity
500 //
501 int ii = zitems.size();
502
503 for( CN_ZONE_LAYER* zitem : zitems )
504 {
505 m_itemList.Add( zitem );
506 m_itemMap[ zitem->Parent() ].Link( zitem );
507 report( ++ii );
508 }
509
510 for( PCB_TRACK* tv : aBoard->Tracks() )
511 {
512 Add( tv );
513 report( ++ii );
514 }
515
516 for( FOOTPRINT* footprint : aBoard->Footprints() )
517 {
518 for( PAD* pad : footprint->Pads() )
519 {
520 Add( pad );
521 report( ++ii );
522 }
523 }
524
525 if( aReporter )
526 {
527 aReporter->SetCurrentProgress( (double) ii / (double) size );
528 aReporter->KeepRefreshing( false );
529 }
530}
bool Add(BOARD_ITEM *aItem)
virtual bool IsCancelled() const =0
virtual bool KeepRefreshing(bool aWait=false)=0
Update the UI (if any).
virtual void AdvanceProgress()=0
Increment the progress bar length (inside the current virtual zone).
virtual void SetCurrentProgress(double aProgress)=0
Set the progress value to aProgress (0..1).
bool IsCopperLayer(int aLayerId)
Tests whether a layer is a copper layer.
Definition: layer_ids.h:825
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
Definition: thread_pool.cpp:32
static thread_pool * tp
Definition: thread_pool.cpp:30
BS::thread_pool thread_pool
Definition: thread_pool.h:30

References Add(), CN_LIST::Add(), PROGRESS_REPORTER::AdvanceProgress(), BOARD::Footprints(), GetKiCadThreadPool(), PROGRESS_REPORTER::IsCancelled(), IsCopperLayer(), PROGRESS_REPORTER::KeepRefreshing(), m_itemList, m_itemMap, markItemNetAsDirty(), pad, PROGRESS_REPORTER::SetCurrentProgress(), tp, BOARD::Tracks(), and BOARD::Zones().

◆ Clear()

void CN_CONNECTIVITY_ALGO::Clear ( )

Definition at line 933 of file connectivity_algo.cpp.

934{
935 m_ratsnestClusters.clear();
936 m_connClusters.clear();
937 m_itemMap.clear();
939
940}
std::vector< std::shared_ptr< CN_CLUSTER > > m_connClusters
std::vector< std::shared_ptr< CN_CLUSTER > > m_ratsnestClusters

References CN_LIST::Clear(), m_connClusters, m_itemList, m_itemMap, and m_ratsnestClusters.

Referenced by ~CN_CONNECTIVITY_ALGO().

◆ ClearDirtyFlags()

void CN_CONNECTIVITY_ALGO::ClearDirtyFlags ( )
inline

Definition at line 178 of file connectivity_algo.h.

179 {
180 for( size_t ii = 0; ii < m_dirtyNets.size(); ii++ )
181 m_dirtyNets[ii] = false;
182 }
std::vector< bool > m_dirtyNets

References m_dirtyNets.

◆ FindIsolatedCopperIslands() [1/2]

void CN_CONNECTIVITY_ALGO::FindIsolatedCopperIslands ( std::vector< CN_ZONE_ISOLATED_ISLAND_LIST > &  aZones,
bool  aConnectivityAlreadyRebuilt 
)

Find the copper islands that are not connected to a net.

These are added to the m_islands vector. N.B. This must be called after aZones has been refreshed.

Parameters
aZones is the set of zones to search for islands.

Definition at line 662 of file connectivity_algo.cpp.

664{
665 int progressDelta = 50;
666 int ii = 0;
667
668 progressDelta = std::max( progressDelta, (int) aZones.size() / 4 );
669
670 if( !aConnectivityAlreadyRebuilt )
671 {
672 for( CN_ZONE_ISOLATED_ISLAND_LIST& z : aZones )
673 {
674 Remove( z.m_zone );
675 Add( z.m_zone );
676 ii++;
677
678 if( m_progressReporter && ( ii % progressDelta ) == 0 )
679 {
680 m_progressReporter->SetCurrentProgress( (double) ii / (double) aZones.size() );
682 }
683
685 return;
686 }
687 }
688
690
691 for( CN_ZONE_ISOLATED_ISLAND_LIST& zone : aZones )
692 {
693 for( PCB_LAYER_ID layer : zone.m_zone->GetLayerSet().Seq() )
694 {
695 if( zone.m_zone->GetFilledPolysList( layer )->IsEmpty() )
696 continue;
697
698 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
699 {
700 if( cluster->Contains( zone.m_zone ) && cluster->IsOrphaned() )
701 {
702 for( CN_ITEM* z : *cluster )
703 {
704 if( z->Parent() == zone.m_zone && z->Layer() == layer )
705 {
706 zone.m_islands[layer].push_back(
707 static_cast<CN_ZONE_LAYER*>( z )->SubpolyIndex() );
708 }
709 }
710 }
711 }
712 }
713 }
714}
bool Remove(BOARD_ITEM *aItem)
PROGRESS_REPORTER * m_progressReporter
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const std::initializer_list< KICAD_T > &aTypes, int aSingleNet, CN_ITEM *rootItem=nullptr)
A structure used for calculating isolated islands on a given zone across all its layers.

References Add(), CSM_CONNECTIVITY_CHECK, PROGRESS_REPORTER::IsCancelled(), PROGRESS_REPORTER::KeepRefreshing(), m_connClusters, m_progressReporter, Remove(), SearchClusters(), and PROGRESS_REPORTER::SetCurrentProgress().

◆ FindIsolatedCopperIslands() [2/2]

void CN_CONNECTIVITY_ALGO::FindIsolatedCopperIslands ( ZONE aZone,
PCB_LAYER_ID  aLayer,
std::vector< int > &  aIslands 
)

Definition at line 634 of file connectivity_algo.cpp.

636{
637 if( aZone->GetFilledPolysList( aLayer )->IsEmpty() )
638 return;
639
640 aIslands.clear();
641
642 Remove( aZone );
643 Add( aZone );
644
646
647 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
648 {
649 if( cluster->Contains( aZone ) && cluster->IsOrphaned() )
650 {
651 for( CN_ITEM* z : *cluster )
652 {
653 if( z->Parent() == aZone && z->Layer() == aLayer )
654 aIslands.push_back( static_cast<CN_ZONE_LAYER*>(z)->SubpolyIndex() );
655 }
656 }
657 }
658
659 wxLogTrace( wxT( "CN" ), wxT( "Found %u isolated islands\n" ), (unsigned) aIslands.size() );
660}
const std::shared_ptr< SHAPE_POLY_SET > & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition: zone.h:601

References Add(), CSM_CONNECTIVITY_CHECK, ZONE::GetFilledPolysList(), m_connClusters, Remove(), and SearchClusters().

◆ ForEachAnchor()

template<typename Func >
void CN_CONNECTIVITY_ALGO::ForEachAnchor ( Func &&  aFunc) const
inline

Definition at line 242 of file connectivity_algo.h.

243 {
244 for( CN_ITEM* item : m_itemList )
245 {
246 for( std::shared_ptr<CN_ANCHOR>& anchor : item->Anchors() )
247 aFunc( *anchor );
248 }
249 }

References anchor, and m_itemList.

◆ ForEachItem()

template<typename Func >
void CN_CONNECTIVITY_ALGO::ForEachItem ( Func &&  aFunc) const
inline

Definition at line 252 of file connectivity_algo.h.

253 {
254 for( CN_ITEM* item : m_itemList )
255 aFunc( *item );
256 }

References m_itemList.

◆ GetClusters()

const CN_CONNECTIVITY_ALGO::CLUSTERS & CN_CONNECTIVITY_ALGO::GetClusters ( )

Definition at line 717 of file connectivity_algo.cpp.

References CSM_RATSNEST, m_ratsnestClusters, and SearchClusters().

◆ GetDirtyClusters()

void CN_CONNECTIVITY_ALGO::GetDirtyClusters ( CLUSTERS aClusters) const
inline

Definition at line 184 of file connectivity_algo.h.

185 {
186 for( const std::shared_ptr<CN_CLUSTER>& cl : m_ratsnestClusters )
187 {
188 int net = cl->OriginNet();
189
190 if( net >= 0 && m_dirtyNets[net] )
191 aClusters.push_back( cl );
192 }
193 }

References m_dirtyNets, and m_ratsnestClusters.

◆ IsNetDirty()

bool CN_CONNECTIVITY_ALGO::IsNetDirty ( int  aNet) const
inline

Definition at line 170 of file connectivity_algo.h.

171 {
172 if( aNet < 0 )
173 return false;
174
175 return m_dirtyNets[ aNet ];
176 }

References m_dirtyNets.

◆ ItemEntry()

ITEM_MAP_ENTRY & CN_CONNECTIVITY_ALGO::ItemEntry ( const BOARD_CONNECTED_ITEM aItem)
inline

Definition at line 165 of file connectivity_algo.h.

166 {
167 return m_itemMap[ aItem ];
168 }

References m_itemMap.

◆ ItemExists()

bool CN_CONNECTIVITY_ALGO::ItemExists ( const BOARD_CONNECTED_ITEM aItem) const
inline

Definition at line 160 of file connectivity_algo.h.

161 {
162 return m_itemMap.find( aItem ) != m_itemMap.end();
163 }

References m_itemMap.

◆ ItemList()

const CN_LIST & CN_CONNECTIVITY_ALGO::ItemList ( ) const
inline

Definition at line 236 of file connectivity_algo.h.

237 {
238 return m_itemList;
239 }

References m_itemList.

◆ LocalBuild()

void CN_CONNECTIVITY_ALGO::LocalBuild ( const std::vector< BOARD_ITEM * > &  aItems)

Definition at line 533 of file connectivity_algo.cpp.

534{
535 for( BOARD_ITEM* item : aItems )
536 {
537 switch( item->Type() )
538 {
539 case PCB_TRACE_T:
540 case PCB_ARC_T:
541 case PCB_VIA_T:
542 case PCB_PAD_T:
543 case PCB_FOOTPRINT_T:
544 Add( item );
545 break;
546
547 default:
548 break;
549 }
550 }
551}
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:58

References Add(), PCB_ARC_T, PCB_FOOTPRINT_T, PCB_PAD_T, PCB_TRACE_T, and PCB_VIA_T.

◆ markItemNetAsDirty()

void CN_CONNECTIVITY_ALGO::markItemNetAsDirty ( const BOARD_ITEM aItem)
private

Definition at line 97 of file connectivity_algo.cpp.

98{
99 if( aItem->IsConnected() )
100 {
101 const BOARD_CONNECTED_ITEM* citem = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
102 MarkNetAsDirty( citem->GetNetCode() );
103 }
104 else
105 {
106 if( aItem->Type() == PCB_FOOTPRINT_T )
107 {
108 const FOOTPRINT* footprint = static_cast<const FOOTPRINT*>( aItem );
109
110 for( PAD* pad : footprint->Pads() )
111 MarkNetAsDirty( pad->GetNetCode() );
112 }
113 }
114}
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:115
PADS & Pads()
Definition: footprint.h:170

References BOARD_CONNECTED_ITEM::GetNetCode(), BOARD_ITEM::IsConnected(), MarkNetAsDirty(), pad, FOOTPRINT::Pads(), PCB_FOOTPRINT_T, and EDA_ITEM::Type().

Referenced by Add(), Build(), and Remove().

◆ MarkNetAsDirty()

void CN_CONNECTIVITY_ALGO::MarkNetAsDirty ( int  aNet)

Definition at line 724 of file connectivity_algo.cpp.

725{
726 if( aNet < 0 )
727 return;
728
729 if( (int) m_dirtyNets.size() <= aNet )
730 {
731 int lastNet = m_dirtyNets.size() - 1;
732
733 if( lastNet < 0 )
734 lastNet = 0;
735
736 m_dirtyNets.resize( aNet + 1 );
737
738 for( int i = lastNet; i < aNet + 1; i++ )
739 m_dirtyNets[i] = true;
740 }
741
742 m_dirtyNets[aNet] = true;
743}

References m_dirtyNets.

Referenced by Add(), markItemNetAsDirty(), and propagateConnections().

◆ NetCount()

int CN_CONNECTIVITY_ALGO::NetCount ( ) const
inline

Definition at line 195 of file connectivity_algo.h.

196 {
197 return m_dirtyNets.size();
198 }

References m_dirtyNets.

◆ propagateConnections()

void CN_CONNECTIVITY_ALGO::propagateConnections ( BOARD_COMMIT aCommit = nullptr,
PROPAGATE_MODE  aMode = PROPAGATE_MODE::SKIP_CONFLICTS 
)
private

Definition at line 554 of file connectivity_algo.cpp.

555{
556 bool skipConflicts = ( aMode == PROPAGATE_MODE::SKIP_CONFLICTS );
557
558 wxLogTrace( wxT( "CN" ), wxT( "propagateConnections: propagate skip conflicts? %d" ),
559 skipConflicts );
560
561 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
562 {
563 if( skipConflicts && cluster->IsConflicting() )
564 {
565 wxLogTrace( wxT( "CN" ), wxT( "Conflicting nets in cluster %p; skipping update" ),
566 cluster.get() );
567 }
568 else if( cluster->IsOrphaned() )
569 {
570 wxLogTrace( wxT( "CN" ), wxT( "Skipping orphaned cluster %p [net: %s]" ),
571 cluster.get(),
572 (const char*) cluster->OriginNetName().c_str() );
573 }
574 else if( cluster->HasValidNet() )
575 {
576 if( cluster->IsConflicting() )
577 {
578 wxLogTrace( wxT( "CN" ), wxT( "Conflicting nets in cluster %p; chose %d (%s)" ),
579 cluster.get(),
580 cluster->OriginNet(),
581 cluster->OriginNetName() );
582 }
583
584 // normal cluster: just propagate from the pads
585 int n_changed = 0;
586
587 for( CN_ITEM* item : *cluster )
588 {
589 if( item->CanChangeNet() )
590 {
591 if( item->Valid() && item->Parent()->GetNetCode() != cluster->OriginNet() )
592 {
593 MarkNetAsDirty( item->Parent()->GetNetCode() );
594 MarkNetAsDirty( cluster->OriginNet() );
595
596 if( aCommit )
597 aCommit->Modify( item->Parent() );
598
599 item->Parent()->SetNetCode( cluster->OriginNet() );
600 n_changed++;
601 }
602 }
603 }
604
605 if( n_changed )
606 {
607 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : net : %d %s" ),
608 cluster.get(),
609 cluster->OriginNet(),
610 (const char*) cluster->OriginNetName().c_str() );
611 }
612 else
613 {
614 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : nothing to propagate" ),
615 cluster.get() );
616 }
617 }
618 else
619 {
620 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : connected to unused net" ),
621 cluster.get() );
622 }
623 }
624}
COMMIT & Modify(EDA_ITEM *aItem)
Create an undo entry for an item that has been already modified.
Definition: commit.h:103

References m_connClusters, MarkNetAsDirty(), COMMIT::Modify(), and SKIP_CONFLICTS.

Referenced by PropagateNets().

◆ PropagateNets()

void CN_CONNECTIVITY_ALGO::PropagateNets ( BOARD_COMMIT aCommit = nullptr,
PROPAGATE_MODE  aMode = PROPAGATE_MODE::SKIP_CONFLICTS 
)

Propagate nets from pads to other items in clusters.

Parameters
aCommitis used to store undo information for items modified by the call.
aModecontrols how clusters with conflicting nets are resolved.

Definition at line 627 of file connectivity_algo.cpp.

628{
630 propagateConnections( aCommit, aMode );
631}
void propagateConnections(BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)

References CSM_PROPAGATE, m_connClusters, propagateConnections(), and SearchClusters().

◆ Remove()

bool CN_CONNECTIVITY_ALGO::Remove ( BOARD_ITEM aItem)

Definition at line 45 of file connectivity_algo.cpp.

46{
47 markItemNetAsDirty( aItem );
48
49 switch( aItem->Type() )
50 {
51 case PCB_FOOTPRINT_T:
52 for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
53 {
54 m_itemMap[pad].MarkItemsAsInvalid();
55 m_itemMap.erase( pad );
56 }
57
58 m_itemList.SetDirty( true );
59 break;
60
61 case PCB_PAD_T:
62 m_itemMap[aItem].MarkItemsAsInvalid();
63 m_itemMap.erase( aItem );
64 m_itemList.SetDirty( true );
65 break;
66
67 case PCB_TRACE_T:
68 case PCB_ARC_T:
69 m_itemMap[aItem].MarkItemsAsInvalid();
70 m_itemMap.erase( aItem );
71 m_itemList.SetDirty( true );
72 break;
73
74 case PCB_VIA_T:
75 m_itemMap[aItem].MarkItemsAsInvalid();
76 m_itemMap.erase( aItem );
77 m_itemList.SetDirty( true );
78 break;
79
80 case PCB_ZONE_T:
81 m_itemMap[aItem].MarkItemsAsInvalid();
82 m_itemMap.erase ( aItem );
83 m_itemList.SetDirty( true );
84 break;
85
86 default:
87 return false;
88 }
89
90 // Once we delete an item, it may connect between lists, so mark both as potentially invalid
92
93 return true;
94}
void SetDirty(bool aDirty=true)
void SetHasInvalid(bool aInvalid=true)

References m_itemList, m_itemMap, markItemNetAsDirty(), pad, PCB_ARC_T, PCB_FOOTPRINT_T, PCB_PAD_T, PCB_TRACE_T, PCB_VIA_T, PCB_ZONE_T, CN_LIST::SetDirty(), CN_LIST::SetHasInvalid(), and EDA_ITEM::Type().

Referenced by FindIsolatedCopperIslands().

◆ SearchClusters() [1/2]

const CN_CONNECTIVITY_ALGO::CLUSTERS CN_CONNECTIVITY_ALGO::SearchClusters ( CLUSTER_SEARCH_MODE  aMode)

Definition at line 291 of file connectivity_algo.cpp.

292{
293 if( aMode == CSM_PROPAGATE )
294 {
295 return SearchClusters( aMode,
297 -1 );
298 }
299 else
300 {
301 return SearchClusters( aMode,
303 -1 );
304 }
305}

References CSM_PROPAGATE, PCB_ARC_T, PCB_FOOTPRINT_T, PCB_PAD_T, PCB_TRACE_T, PCB_VIA_T, PCB_ZONE_T, and SearchClusters().

◆ SearchClusters() [2/2]

const CN_CONNECTIVITY_ALGO::CLUSTERS CN_CONNECTIVITY_ALGO::SearchClusters ( CLUSTER_SEARCH_MODE  aMode,
const std::initializer_list< KICAD_T > &  aTypes,
int  aSingleNet,
CN_ITEM rootItem = nullptr 
)

Definition at line 309 of file connectivity_algo.cpp.

312{
313 bool withinAnyNet = ( aMode != CSM_PROPAGATE );
314
315 std::deque<CN_ITEM*> Q;
316 std::set<CN_ITEM*> item_set;
317
318 CLUSTERS clusters;
319
320 if( m_itemList.IsDirty() )
322
323 auto addToSearchList =
324 [&item_set, withinAnyNet, aSingleNet, &aTypes, rootItem ]( CN_ITEM *aItem )
325 {
326 if( withinAnyNet && aItem->Net() <= 0 )
327 return;
328
329 if( !aItem->Valid() )
330 return;
331
332 if( aSingleNet >=0 && aItem->Net() != aSingleNet )
333 return;
334
335 bool found = false;
336
337 for( KICAD_T type : aTypes )
338 {
339 if( aItem->Parent()->Type() == type )
340 {
341 found = true;
342 break;
343 }
344 }
345
346 if( !found && aItem != rootItem )
347 return;
348
349 aItem->SetVisited( false );
350
351 item_set.insert( aItem );
352 };
353
354 std::for_each( m_itemList.begin(), m_itemList.end(), addToSearchList );
355
357 return CLUSTERS();
358
359 while( !item_set.empty() )
360 {
361 std::shared_ptr<CN_CLUSTER> cluster = std::make_shared<CN_CLUSTER>();
362 CN_ITEM* root;
363 auto it = item_set.begin();
364
365 while( it != item_set.end() && (*it)->Visited() )
366 it = item_set.erase( item_set.begin() );
367
368 if( it == item_set.end() )
369 break;
370
371 root = *it;
372 root->SetVisited( true );
373
374 Q.clear();
375 Q.push_back( root );
376
377 while( Q.size() )
378 {
379 CN_ITEM* current = Q.front();
380
381 Q.pop_front();
382 cluster->Add( current );
383
384 for( CN_ITEM* n : current->ConnectedItems() )
385 {
386 if( withinAnyNet && n->Net() != root->Net() )
387 continue;
388
389 if( !n->Visited() && n->Valid() )
390 {
391 n->SetVisited( true );
392 Q.push_back( n );
393 }
394 }
395 }
396
397 clusters.push_back( cluster );
398 }
399
401 return CLUSTERS();
402
403 std::sort( clusters.begin(), clusters.end(),
404 []( const std::shared_ptr<CN_CLUSTER>& a, const std::shared_ptr<CN_CLUSTER>& b )
405 {
406 return a->OriginNet() < b->OriginNet();
407 } );
408
409 return clusters;
410}
std::vector< std::shared_ptr< CN_CLUSTER > > CLUSTERS
const std::vector< CN_ITEM * > & ConnectedItems() const
int Net() const
allow parallel connection threads
void SetVisited(bool aVisited)
bool IsDirty() const
#define Q()
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:78

References CN_LIST::begin(), CN_ITEM::ConnectedItems(), CSM_PROPAGATE, CN_LIST::end(), PROGRESS_REPORTER::IsCancelled(), CN_LIST::IsDirty(), m_itemList, m_progressReporter, CN_ITEM::Net(), Q, searchConnections(), and CN_ITEM::SetVisited().

Referenced by FindIsolatedCopperIslands(), GetClusters(), PropagateNets(), and SearchClusters().

◆ searchConnections()

void CN_CONNECTIVITY_ALGO::searchConnections ( )
private

Definition at line 207 of file connectivity_algo.cpp.

208{
209#ifdef PROFILE
210 PROF_TIMER garbage_collection( "garbage-collection" );
211#endif
212 std::vector<CN_ITEM*> garbage;
213 garbage.reserve( 1024 );
214
216
217 for( CN_ITEM* item : garbage )
218 delete item;
219
220#ifdef PROFILE
221 garbage_collection.Show();
222 PROF_TIMER search_basic( "search-basic" );
223#endif
224
226 std::vector<CN_ITEM*> dirtyItems;
227 std::copy_if( m_itemList.begin(), m_itemList.end(), std::back_inserter( dirtyItems ),
228 [] ( CN_ITEM* aItem )
229 {
230 return aItem->Dirty();
231 } );
232
234 {
235 m_progressReporter->SetMaxProgress( dirtyItems.size() );
236
238 return;
239 }
240
241 if( m_itemList.IsDirty() )
242 {
243
244 std::vector<std::future<size_t>> returns( dirtyItems.size() );
245
246 auto conn_lambda =
247 [&dirtyItems]( size_t aItem, CN_LIST* aItemList,
248 PROGRESS_REPORTER* aReporter) -> size_t
249 {
250 if( aReporter && aReporter->IsCancelled() )
251 return 0;
252
253 CN_VISITOR visitor( dirtyItems[aItem] );
254 aItemList->FindNearby( dirtyItems[aItem], visitor );
255
256 if( aReporter )
257 aReporter->AdvanceProgress();
258
259 return 1;
260 };
261
262 for( size_t ii = 0; ii < dirtyItems.size(); ++ii )
263 returns[ii] = tp.submit( conn_lambda, ii, &m_itemList, m_progressReporter );
264
265 for( const std::future<size_t>& ret : returns )
266 {
267 // Here we balance returns with a 250ms timeout to allow UI updating
268 std::future_status status = ret.wait_for( std::chrono::milliseconds( 250 ) );
269
270 while( status != std::future_status::ready )
271 {
274
275 status = ret.wait_for( std::chrono::milliseconds( 250 ) );
276 }
277 }
278
281 }
282
283#ifdef PROFILE
284 search_basic.Show();
285#endif
286
288}
void ClearDirtyFlags()
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
A small class to help profiling.
Definition: profile.h:47
A progress reporter interface for use in multi-threaded environments.
virtual void SetMaxProgress(int aMaxProgress)=0
Fix the value that gives the 100 percent progress bar length (inside the current virtual zone).

References CN_LIST::begin(), CN_LIST::ClearDirtyFlags(), CN_LIST::end(), GetKiCadThreadPool(), CN_LIST::IsDirty(), PROGRESS_REPORTER::KeepRefreshing(), m_itemList, m_progressReporter, CN_LIST::RemoveInvalidItems(), PROGRESS_REPORTER::SetMaxProgress(), PROF_TIMER::Show(), and tp.

Referenced by SearchClusters().

◆ SetProgressReporter()

void CN_CONNECTIVITY_ALGO::SetProgressReporter ( PROGRESS_REPORTER aReporter)

Definition at line 942 of file connectivity_algo.cpp.

943{
944 m_progressReporter = aReporter;
945}

References m_progressReporter.

Member Data Documentation

◆ m_connClusters

std::vector<std::shared_ptr<CN_CLUSTER> > CN_CONNECTIVITY_ALGO::m_connClusters
private

◆ m_dirtyNets

std::vector<bool> CN_CONNECTIVITY_ALGO::m_dirtyNets
private

◆ m_itemList

CN_LIST CN_CONNECTIVITY_ALGO::m_itemList
private

◆ m_itemMap

std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> CN_CONNECTIVITY_ALGO::m_itemMap
private

Definition at line 279 of file connectivity_algo.h.

Referenced by Add(), add(), Build(), Clear(), ItemEntry(), ItemExists(), and Remove().

◆ m_progressReporter

PROGRESS_REPORTER* CN_CONNECTIVITY_ALGO::m_progressReporter = nullptr
private

◆ m_ratsnestClusters

std::vector<std::shared_ptr<CN_CLUSTER> > CN_CONNECTIVITY_ALGO::m_ratsnestClusters
private

Definition at line 282 of file connectivity_algo.h.

Referenced by Clear(), GetClusters(), and GetDirtyClusters().


The documentation for this class was generated from the following files: