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< CN_CLUSTER_PTR >
 

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 *aBoard, PROGRESS_REPORTER *aReporter=nullptr)
 
void Build (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 KICAD_T aTypes[], int aSingleNet)
 
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)
 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
 
CLUSTERS m_connClusters
 
CLUSTERS m_ratsnestClusters
 
std::vector< bool > m_dirtyNets
 
PROGRESS_REPORTERm_progressReporter = nullptr
 

Detailed Description

Definition at line 123 of file connectivity_algo.h.

Member Typedef Documentation

◆ CLUSTERS

Definition at line 133 of file connectivity_algo.h.

Member Enumeration Documentation

◆ CLUSTER_SEARCH_MODE

Constructor & Destructor Documentation

◆ CN_CONNECTIVITY_ALGO()

CN_CONNECTIVITY_ALGO::CN_CONNECTIVITY_ALGO ( )
inline

Definition at line 165 of file connectivity_algo.h.

165 {}

◆ ~CN_CONNECTIVITY_ALGO()

CN_CONNECTIVITY_ALGO::~CN_CONNECTIVITY_ALGO ( )
inline

Definition at line 166 of file connectivity_algo.h.

166 { Clear(); }

References Clear().

Member Function Documentation

◆ Add()

bool CN_CONNECTIVITY_ALGO::Add ( BOARD_ITEM aItem)

Definition at line 116 of file connectivity_algo.cpp.

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

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(), and FindIsolatedCopperIslands().

◆ add()

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

Definition at line 274 of file connectivity_algo.h.

275  {
276  auto item = c.Add( brditem );
277 
278  m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
279  }
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap

References m_itemMap.

Referenced by Add().

◆ Build() [1/2]

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

Definition at line 432 of file connectivity_algo.cpp.

433 {
434  int delta = 200; // Number of additions between 2 calls to the progress bar
435  int ii = 0;
436  int size = 0;
437 
438  size += aBoard->Zones().size();
439  size += aBoard->Tracks().size();
440 
441  for( FOOTPRINT* footprint : aBoard->Footprints() )
442  size += footprint->Pads().size();
443 
444  size *= 2; // Our caller us gets the other half of the progress bar
445 
446  delta = std::max( delta, size / 10 );
447 
448  for( ZONE* zone : aBoard->Zones() )
449  {
450  Add( zone );
451  reportProgress( aReporter, ii++, size, delta );
452  }
453 
454  for( PCB_TRACK* tv : aBoard->Tracks() )
455  {
456  Add( tv );
457  reportProgress( aReporter, ii++, size, delta );
458  }
459 
460  for( FOOTPRINT* footprint : aBoard->Footprints() )
461  {
462  for( PAD* pad : footprint->Pads() )
463  {
464  Add( pad );
465  reportProgress( aReporter, ii++, size, delta );
466  }
467  }
468 }
ZONES & Zones()
Definition: board.h:240
bool Add(BOARD_ITEM *aItem)
FOOTPRINTS & Footprints()
Definition: board.h:234
Handle a list of polygons defining a copper zone.
Definition: zone.h:56
void reportProgress(PROGRESS_REPORTER *aReporter, int aCount, int aSize, int aDelta)
constexpr int delta
Definition: pad.h:57
TRACKS & Tracks()
Definition: board.h:231

References Add(), delta, BOARD::Footprints(), pad, reportProgress(), BOARD::Tracks(), and BOARD::Zones().

◆ Build() [2/2]

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

Definition at line 471 of file connectivity_algo.cpp.

472 {
473  for( auto item : aItems )
474  {
475  switch( item->Type() )
476  {
477  case PCB_TRACE_T:
478  case PCB_ARC_T:
479  case PCB_VIA_T:
480  case PCB_PAD_T:
481  Add( item );
482  break;
483 
484  case PCB_FOOTPRINT_T:
485  for( PAD* pad : static_cast<FOOTPRINT*>( item )->Pads() )
486  Add( pad );
487 
488  break;
489 
490  default:
491  break;
492  }
493  }
494 }
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:97
class PAD, a pad in a footprint
Definition: typeinfo.h:89
bool Add(BOARD_ITEM *aItem)
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
class FOOTPRINT, a footprint
Definition: typeinfo.h:88
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96
Definition: pad.h:57

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

◆ Clear()

void CN_CONNECTIVITY_ALGO::Clear ( )

Definition at line 839 of file connectivity_algo.cpp.

840 {
841  m_ratsnestClusters.clear();
842  m_connClusters.clear();
843  m_itemMap.clear();
844  m_itemList.Clear();
845 
846 }
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap

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 186 of file connectivity_algo.h.

187  {
188  for( auto i = m_dirtyNets.begin(); i != m_dirtyNets.end(); ++i )
189  *i = false;
190  }
std::vector< bool > m_dirtyNets

References m_dirtyNets.

◆ FindIsolatedCopperIslands() [1/2]

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

Definition at line 575 of file connectivity_algo.cpp.

577 {
578  if( aZone->GetFilledPolysList( aLayer ).IsEmpty() )
579  return;
580 
581  aIslands.clear();
582 
583  Remove( aZone );
584  Add( aZone );
585 
587 
588  for( const auto& cluster : m_connClusters )
589  {
590  if( cluster->Contains( aZone ) && cluster->IsOrphaned() )
591  {
592  for( auto z : *cluster )
593  {
594  if( z->Parent() == aZone && z->Layer() == aLayer )
595  {
596  aIslands.push_back( static_cast<CN_ZONE_LAYER*>(z)->SubpolyIndex() );
597  }
598  }
599  }
600  }
601 
602  wxLogTrace( wxT( "CN" ), wxT( "Found %u isolated islands\n" ), (unsigned) aIslands.size() );
603 }
bool Remove(BOARD_ITEM *aItem)
bool IsEmpty() const
bool Add(BOARD_ITEM *aItem)
const SHAPE_POLY_SET & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition: zone.h:637
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet)

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

◆ FindIsolatedCopperIslands() [2/2]

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

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 605 of file connectivity_algo.cpp.

606 {
607  for( auto& z : aZones )
608  {
609  Remove( z.m_zone );
610  Add( z.m_zone );
611  }
612 
614 
615  for( CN_ZONE_ISOLATED_ISLAND_LIST& zone : aZones )
616  {
617  for( PCB_LAYER_ID layer : zone.m_zone->GetLayerSet().Seq() )
618  {
619  if( zone.m_zone->GetFilledPolysList( layer ).IsEmpty() )
620  continue;
621 
622  for( const CN_CLUSTER_PTR& cluster : m_connClusters )
623  {
624  if( cluster->Contains( zone.m_zone ) && cluster->IsOrphaned() )
625  {
626  for( CN_ITEM* z : *cluster )
627  {
628  if( z->Parent() == zone.m_zone && z->Layer() == layer )
629  {
630  zone.m_islands[layer].push_back(
631  static_cast<CN_ZONE_LAYER*>( z )->SubpolyIndex() );
632  }
633  }
634  }
635  }
636  }
637  }
638 }
bool Remove(BOARD_ITEM *aItem)
bool Add(BOARD_ITEM *aItem)
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet)
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:65
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
A structure used for calculating isolated islands on a given zone across all its layers.

References Add(), CSM_CONNECTIVITY_CHECK, m_connClusters, Remove(), and SearchClusters().

◆ ForEachAnchor()

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

Definition at line 248 of file connectivity_algo.h.

249  {
250  for( auto&& item : m_itemList )
251  {
252  for( auto&& anchor : item->Anchors() )
253  aFunc( *anchor );
254  }
255  }

References anchor, and m_itemList.

◆ ForEachItem()

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

Definition at line 258 of file connectivity_algo.h.

259  {
260  for( auto&& item : m_itemList )
261  aFunc( *item );
262  }

References m_itemList.

◆ GetClusters()

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

Definition at line 641 of file connectivity_algo.cpp.

642 {
644  return m_ratsnestClusters;
645 }
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet)

References CSM_RATSNEST, m_ratsnestClusters, and SearchClusters().

◆ GetDirtyClusters()

void CN_CONNECTIVITY_ALGO::GetDirtyClusters ( CLUSTERS aClusters) const
inline

Definition at line 192 of file connectivity_algo.h.

193  {
194  for( const auto& cl : m_ratsnestClusters )
195  {
196  int net = cl->OriginNet();
197 
198  if( net >= 0 && m_dirtyNets[net] )
199  aClusters.push_back( cl );
200  }
201  }
std::vector< bool > m_dirtyNets

References m_dirtyNets, and m_ratsnestClusters.

◆ IsNetDirty()

bool CN_CONNECTIVITY_ALGO::IsNetDirty ( int  aNet) const
inline

Definition at line 178 of file connectivity_algo.h.

179  {
180  if( aNet < 0 )
181  return false;
182 
183  return m_dirtyNets[ aNet ];
184  }
std::vector< bool > m_dirtyNets

References m_dirtyNets.

◆ ItemEntry()

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

Definition at line 173 of file connectivity_algo.h.

174  {
175  return m_itemMap[ aItem ];
176  }
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap

References m_itemMap.

◆ ItemExists()

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

Definition at line 168 of file connectivity_algo.h.

169  {
170  return m_itemMap.find( aItem ) != m_itemMap.end();
171  }
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap

References m_itemMap.

◆ ItemList()

const CN_LIST& CN_CONNECTIVITY_ALGO::ItemList ( ) const
inline

Definition at line 242 of file connectivity_algo.h.

243  {
244  return m_itemList;
245  }

References m_itemList.

◆ markItemNetAsDirty()

void CN_CONNECTIVITY_ALGO::markItemNetAsDirty ( const BOARD_ITEM aItem)
private

Definition at line 96 of file connectivity_algo.cpp.

97 {
98  if( aItem->IsConnected() )
99  {
100  auto citem = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
101  MarkNetAsDirty( citem->GetNetCode() );
102  }
103  else
104  {
105  if( aItem->Type() == PCB_FOOTPRINT_T )
106  {
107  const FOOTPRINT* footprint = static_cast<const FOOTPRINT*>( aItem );
108 
109  for( PAD* pad : footprint->Pads() )
110  MarkNetAsDirty( pad->GetNetCode() );
111  }
112  }
113 }
void MarkNetAsDirty(int aNet)
PADS & Pads()
Definition: footprint.h:169
class FOOTPRINT, a footprint
Definition: typeinfo.h:88
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:103
Definition: pad.h:57
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:112

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

Referenced by Add(), and Remove().

◆ MarkNetAsDirty()

void CN_CONNECTIVITY_ALGO::MarkNetAsDirty ( int  aNet)

Definition at line 648 of file connectivity_algo.cpp.

649 {
650  if( aNet < 0 )
651  return;
652 
653  if( (int) m_dirtyNets.size() <= aNet )
654  {
655  int lastNet = m_dirtyNets.size() - 1;
656 
657  if( lastNet < 0 )
658  lastNet = 0;
659 
660  m_dirtyNets.resize( aNet + 1 );
661 
662  for( int i = lastNet; i < aNet + 1; i++ )
663  m_dirtyNets[i] = true;
664  }
665 
666  m_dirtyNets[aNet] = true;
667 }
std::vector< bool > m_dirtyNets

References m_dirtyNets.

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

◆ NetCount()

int CN_CONNECTIVITY_ALGO::NetCount ( ) const
inline

Definition at line 203 of file connectivity_algo.h.

204  {
205  return m_dirtyNets.size();
206  }
std::vector< bool > m_dirtyNets

References m_dirtyNets.

◆ propagateConnections()

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

Definition at line 497 of file connectivity_algo.cpp.

498 {
499  bool skipConflicts = ( aMode == PROPAGATE_MODE::SKIP_CONFLICTS );
500 
501  wxLogTrace( wxT( "CN" ), wxT( "propagateConnections: propagate skip conflicts? %d" ),
502  skipConflicts );
503 
504  for( const auto& cluster : m_connClusters )
505  {
506  if( skipConflicts && cluster->IsConflicting() )
507  {
508  wxLogTrace( wxT( "CN" ), wxT( "Conflicting nets in cluster %p; skipping update" ),
509  cluster.get() );
510  }
511  else if( cluster->IsOrphaned() )
512  {
513  wxLogTrace( wxT( "CN" ), wxT( "Skipping orphaned cluster %p [net: %s]" ),
514  cluster.get(),
515  (const char*) cluster->OriginNetName().c_str() );
516  }
517  else if( cluster->HasValidNet() )
518  {
519  if( cluster->IsConflicting() )
520  {
521  wxLogTrace( wxT( "CN" ), wxT( "Conflicting nets in cluster %p; chose %d (%s)" ),
522  cluster.get(),
523  cluster->OriginNet(),
524  cluster->OriginNetName() );
525  }
526 
527  // normal cluster: just propagate from the pads
528  int n_changed = 0;
529 
530  for( auto item : *cluster )
531  {
532  if( item->CanChangeNet() )
533  {
534  if( item->Valid() && item->Parent()->GetNetCode() != cluster->OriginNet() )
535  {
536  MarkNetAsDirty( item->Parent()->GetNetCode() );
537  MarkNetAsDirty( cluster->OriginNet() );
538 
539  if( aCommit )
540  aCommit->Modify( item->Parent() );
541 
542  item->Parent()->SetNetCode( cluster->OriginNet() );
543  n_changed++;
544  }
545  }
546  }
547 
548  if( n_changed )
549  {
550  wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : net : %d %s" ),
551  cluster.get(),
552  cluster->OriginNet(),
553  (const char*) cluster->OriginNetName().c_str() );
554  }
555  else
556  wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : nothing to propagate" ),
557  cluster.get() );
558  }
559  else
560  {
561  wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : connected to unused net" ),
562  cluster.get() );
563  }
564  }
565 }
COMMIT & Modify(EDA_ITEM *aItem)
Create an undo entry for an item that has been already modified.
Definition: commit.h:103
void MarkNetAsDirty(int aNet)

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 568 of file connectivity_algo.cpp.

569 {
571  propagateConnections( aCommit, aMode );
572 }
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet)
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 44 of file connectivity_algo.cpp.

45 {
46  markItemNetAsDirty( aItem );
47 
48  switch( aItem->Type() )
49  {
50  case PCB_FOOTPRINT_T:
51  for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
52  {
53  m_itemMap[pad].MarkItemsAsInvalid();
54  m_itemMap.erase( pad );
55  }
56 
57  m_itemList.SetDirty( true );
58  break;
59 
60  case PCB_PAD_T:
61  m_itemMap[aItem].MarkItemsAsInvalid();
62  m_itemMap.erase( aItem );
63  m_itemList.SetDirty( true );
64  break;
65 
66  case PCB_TRACE_T:
67  case PCB_ARC_T:
68  m_itemMap[aItem].MarkItemsAsInvalid();
69  m_itemMap.erase( aItem );
70  m_itemList.SetDirty( true );
71  break;
72 
73  case PCB_VIA_T:
74  m_itemMap[aItem].MarkItemsAsInvalid();
75  m_itemMap.erase( aItem );
76  m_itemList.SetDirty( true );
77  break;
78 
79  case PCB_ZONE_T:
80  m_itemMap[aItem].MarkItemsAsInvalid();
81  m_itemMap.erase ( aItem );
82  m_itemList.SetDirty( true );
83  break;
84 
85  default:
86  return false;
87  }
88 
89  // Once we delete an item, it may connect between lists, so mark both as potentially invalid
90  m_itemList.SetHasInvalid( true );
91 
92  return true;
93 }
void SetHasInvalid(bool aInvalid=true)
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:97
class PAD, a pad in a footprint
Definition: typeinfo.h:89
void SetDirty(bool aDirty=true)
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
void markItemNetAsDirty(const BOARD_ITEM *aItem)
class ZONE, a copper pour area
Definition: typeinfo.h:105
class FOOTPRINT, a footprint
Definition: typeinfo.h:88
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96
Definition: pad.h:57
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:112

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,
const KICAD_T  aTypes[],
int  aSingleNet 
)

Definition at line 318 of file connectivity_algo.cpp.

321 {
322  bool withinAnyNet = ( aMode != CSM_PROPAGATE );
323 
324  std::deque<CN_ITEM*> Q;
325  std::set<CN_ITEM*> item_set;
326 
327  CLUSTERS clusters;
328 
329  if( m_itemList.IsDirty() )
331 
332  auto addToSearchList =
333  [&item_set, withinAnyNet, aSingleNet, aTypes]( CN_ITEM *aItem )
334  {
335  if( withinAnyNet && aItem->Net() <= 0 )
336  return;
337 
338  if( !aItem->Valid() )
339  return;
340 
341  if( aSingleNet >=0 && aItem->Net() != aSingleNet )
342  return;
343 
344  bool found = false;
345 
346  for( int i = 0; aTypes[i] != EOT; i++ )
347  {
348  if( aItem->Parent()->Type() == aTypes[i] )
349  {
350  found = true;
351  break;
352  }
353  }
354 
355  if( !found )
356  return;
357 
358  aItem->SetVisited( false );
359 
360  item_set.insert( aItem );
361  };
362 
363  std::for_each( m_itemList.begin(), m_itemList.end(), addToSearchList );
364 
366  return CLUSTERS();
367 
368  while( !item_set.empty() )
369  {
370  CN_CLUSTER_PTR cluster = std::make_shared<CN_CLUSTER>();
371  CN_ITEM* root;
372  auto it = item_set.begin();
373 
374  while( it != item_set.end() && (*it)->Visited() )
375  it = item_set.erase( item_set.begin() );
376 
377  if( it == item_set.end() )
378  break;
379 
380  root = *it;
381  root->SetVisited( true );
382 
383  Q.clear();
384  Q.push_back( root );
385 
386  while( Q.size() )
387  {
388  CN_ITEM* current = Q.front();
389 
390  Q.pop_front();
391  cluster->Add( current );
392 
393  for( auto n : current->ConnectedItems() )
394  {
395  if( withinAnyNet && n->Net() != root->Net() )
396  continue;
397 
398  if( !n->Visited() && n->Valid() )
399  {
400  n->SetVisited( true );
401  Q.push_back( n );
402  }
403  }
404  }
405 
406  clusters.push_back( cluster );
407  }
408 
410  return CLUSTERS();
411 
412  std::sort( clusters.begin(), clusters.end(),
413  []( CN_CLUSTER_PTR a, CN_CLUSTER_PTR b )
414  {
415  return a->OriginNet() < b->OriginNet();
416  } );
417 
418  return clusters;
419 }
const CONNECTED_ITEMS & ConnectedItems() const
void SetVisited(bool aVisited)
bool IsDirty() const
int Net() const
allow parallel connection threads
search types array terminator (End Of Types)
Definition: typeinfo.h:81
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
virtual bool IsCancelled() const =0
std::vector< CN_CLUSTER_PTR > CLUSTERS
PROGRESS_REPORTER * m_progressReporter

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

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

◆ SearchClusters() [2/2]

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

Definition at line 304 of file connectivity_algo.cpp.

305 {
306  constexpr KICAD_T types[] = { PCB_TRACE_T, PCB_ARC_T, PCB_PAD_T, PCB_VIA_T, PCB_ZONE_T,
307  PCB_FOOTPRINT_T, EOT };
308  constexpr KICAD_T no_zones[] = { PCB_TRACE_T, PCB_ARC_T, PCB_PAD_T, PCB_VIA_T,
309  PCB_FOOTPRINT_T, EOT };
310 
311  if( aMode == CSM_PROPAGATE )
312  return SearchClusters( aMode, no_zones, -1 );
313  else
314  return SearchClusters( aMode, types, -1 );
315 }
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:97
class PAD, a pad in a footprint
Definition: typeinfo.h:89
search types array terminator (End Of Types)
Definition: typeinfo.h:81
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:77
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], int aSingleNet)
class ZONE, a copper pour area
Definition: typeinfo.h:105
class FOOTPRINT, a footprint
Definition: typeinfo.h:88
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96

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

◆ searchConnections()

void CN_CONNECTIVITY_ALGO::searchConnections ( )
private

Definition at line 206 of file connectivity_algo.cpp.

207 {
208 #ifdef PROFILE
209  PROF_COUNTER garbage_collection( "garbage-collection" );
210 #endif
211  std::vector<CN_ITEM*> garbage;
212  garbage.reserve( 1024 );
213 
214  m_itemList.RemoveInvalidItems( garbage );
215 
216  for( auto item : garbage )
217  delete item;
218 
219 #ifdef PROFILE
220  garbage_collection.Show();
221  PROF_COUNTER search_basic( "search-basic" );
222 #endif
223 
224  std::vector<CN_ITEM*> dirtyItems;
225  std::copy_if( m_itemList.begin(), m_itemList.end(), std::back_inserter( dirtyItems ),
226  [] ( CN_ITEM* aItem )
227  {
228  return aItem->Dirty();
229  } );
230 
231  if( m_progressReporter )
232  {
233  m_progressReporter->SetMaxProgress( dirtyItems.size() );
234 
236  return;
237  }
238 
239  if( m_itemList.IsDirty() )
240  {
241  size_t parallelThreadCount = std::min<size_t>( std::thread::hardware_concurrency(),
242  ( dirtyItems.size() + 7 ) / 8 );
243 
244  std::atomic<size_t> nextItem( 0 );
245  std::vector<std::future<size_t>> returns( parallelThreadCount );
246 
247  auto conn_lambda =
248  [&nextItem, &dirtyItems]( CN_LIST* aItemList,
249  PROGRESS_REPORTER* aReporter) -> size_t
250  {
251  for( size_t i = nextItem++; i < dirtyItems.size(); i = nextItem++ )
252  {
253  CN_VISITOR visitor( dirtyItems[i] );
254  aItemList->FindNearby( dirtyItems[i], visitor );
255 
256  if( aReporter )
257  {
258  if( aReporter->IsCancelled() )
259  break;
260  else
261  aReporter->AdvanceProgress();
262  }
263  }
264 
265  return 1;
266  };
267 
268  if( parallelThreadCount <= 1 )
269  conn_lambda( &m_itemList, m_progressReporter );
270  else
271  {
272  for( size_t ii = 0; ii < parallelThreadCount; ++ii )
273  {
274  returns[ii] = std::async( std::launch::async, conn_lambda, &m_itemList,
276  }
277 
278  for( size_t ii = 0; ii < parallelThreadCount; ++ii )
279  {
280  // Here we balance returns with a 100ms timeout to allow UI updating
281  std::future_status status;
282  do
283  {
284  if( m_progressReporter )
286 
287  status = returns[ii].wait_for( std::chrono::milliseconds( 100 ) );
288  } while( status != std::future_status::ready );
289  }
290  }
291 
292  if( m_progressReporter )
294  }
295 
296 #ifdef PROFILE
297  search_basic.Show();
298 #endif
299 
301 }
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
virtual void SetMaxProgress(int aMaxProgress)=0
Fix the value that gives the 100 percent progress bar length (inside the current virtual zone).
A progress reporter interface for use in multi-threaded environments.
void ClearDirtyFlags()
bool IsDirty() const
A thread-safe event counter.
Definition: profile.h:225
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
virtual bool KeepRefreshing(bool aWait=false)=0
Update the UI (if any).
PROGRESS_REPORTER * m_progressReporter

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

Referenced by SearchClusters().

◆ SetProgressReporter()

void CN_CONNECTIVITY_ALGO::SetProgressReporter ( PROGRESS_REPORTER aReporter)

Definition at line 848 of file connectivity_algo.cpp.

849 {
850  m_progressReporter = aReporter;
851 }
PROGRESS_REPORTER * m_progressReporter

References m_progressReporter.

Member Data Documentation

◆ m_connClusters

CLUSTERS 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 285 of file connectivity_algo.h.

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

◆ m_progressReporter

PROGRESS_REPORTER* CN_CONNECTIVITY_ALGO::m_progressReporter = nullptr
private

Definition at line 291 of file connectivity_algo.h.

Referenced by SearchClusters(), searchConnections(), and SetProgressReporter().

◆ m_ratsnestClusters

CLUSTERS CN_CONNECTIVITY_ALGO::m_ratsnestClusters
private

Definition at line 288 of file connectivity_algo.h.

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


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