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

Member Typedef Documentation

◆ CLUSTERS

Definition at line 127 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 159 of file connectivity_algo.h.

159 {}

◆ ~CN_CONNECTIVITY_ALGO()

CN_CONNECTIVITY_ALGO::~CN_CONNECTIVITY_ALGO ( )
inline

Definition at line 160 of file connectivity_algo.h.

160 { 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  markItemNetAsDirty ( aItem );
122 
123  switch( aItem->Type() )
124  {
125  case PCB_NETINFO_T:
126  MarkNetAsDirty( static_cast<NETINFO_ITEM*>( aItem )->GetNetCode() );
127  break;
128 
129  case PCB_FOOTPRINT_T:
130  for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
131  {
132  if( m_itemMap.find( pad ) != m_itemMap.end() )
133  return false;
134 
135  add( m_itemList, pad );
136  }
137 
138  break;
139 
140  case PCB_PAD_T:
141  if( m_itemMap.find ( aItem ) != m_itemMap.end() )
142  return false;
143 
144  add( m_itemList, static_cast<PAD*>( aItem ) );
145  break;
146 
147  case PCB_TRACE_T:
148  if( m_itemMap.find( aItem ) != m_itemMap.end() )
149  return false;
150 
151  add( m_itemList, static_cast<PCB_TRACK*>( aItem ) );
152  break;
153 
154  case PCB_ARC_T:
155  if( m_itemMap.find( aItem ) != m_itemMap.end() )
156  return false;
157 
158  add( m_itemList, static_cast<PCB_ARC*>( aItem ) );
159  break;
160 
161  case PCB_VIA_T:
162  if( m_itemMap.find( aItem ) != m_itemMap.end() )
163  return false;
164 
165  add( m_itemList, static_cast<PCB_VIA*>( aItem ) );
166  break;
167 
168  case PCB_ZONE_T:
169  {
170  ZONE* zone = static_cast<ZONE*>( aItem );
171 
172  if( m_itemMap.find( aItem ) != m_itemMap.end() )
173  return false;
174 
175  m_itemMap[zone] = ITEM_MAP_ENTRY();
176 
177  for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
178  {
179  for( CN_ITEM* zitem : m_itemList.Add( zone, layer ) )
180  m_itemMap[zone].Link( zitem );
181  }
182  }
183  break;
184 
185  default:
186  return false;
187  }
188 
189  return true;
190 }
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:291
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:64
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:142
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:113

References add(), CN_LIST::Add(), ZONE::GetLayerSet(), 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 268 of file connectivity_algo.h.

269  {
270  auto item = c.Add( brditem );
271 
272  m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
273  }
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 419 of file connectivity_algo.cpp.

420 {
421  const int delta = 100; // Number of additions between 2 calls to the progress bar
422  int ii = 0;
423  int size = 0;
424 
425  size += aBoard->Zones().size();
426  size += aBoard->Tracks().size();
427 
428  for( FOOTPRINT* footprint : aBoard->Footprints() )
429  size += footprint->Pads().size();
430 
431  size *= 2; // Our caller us gets the other half of the progress bar
432 
433  for( ZONE* zone : aBoard->Zones() )
434  {
435  Add( zone );
436  reportProgress( aReporter, ii++, size, delta );
437  }
438 
439  for( PCB_TRACK* tv : aBoard->Tracks() )
440  {
441  Add( tv );
442  reportProgress( aReporter, ii++, size, delta );
443  }
444 
445  for( FOOTPRINT* footprint : aBoard->Footprints() )
446  {
447  for( PAD* pad : footprint->Pads() )
448  {
449  Add( pad );
450  reportProgress( aReporter, ii++, size, delta );
451  }
452  }
453 }
ZONES & Zones()
Definition: board.h:239
bool Add(BOARD_ITEM *aItem)
FOOTPRINTS & Footprints()
Definition: board.h:233
constexpr int delta
Handle a list of polygons defining a copper zone.
Definition: zone.h:56
void reportProgress(PROGRESS_REPORTER *aReporter, int aCount, int aSize, int aDelta)
Definition: pad.h:57
TRACKS & Tracks()
Definition: board.h:230

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

457 {
458  for( auto item : aItems )
459  {
460  switch( item->Type() )
461  {
462  case PCB_TRACE_T:
463  case PCB_ARC_T:
464  case PCB_VIA_T:
465  case PCB_PAD_T:
466  Add( item );
467  break;
468 
469  case PCB_FOOTPRINT_T:
470  for( PAD* pad : static_cast<FOOTPRINT*>( item )->Pads() )
471  Add( pad );
472 
473  break;
474 
475  default:
476  break;
477  }
478  }
479 }
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 812 of file connectivity_algo.cpp.

813 {
814  m_ratsnestClusters.clear();
815  m_connClusters.clear();
816  m_itemMap.clear();
817  m_itemList.Clear();
818 
819 }
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 180 of file connectivity_algo.h.

181  {
182  for( auto i = m_dirtyNets.begin(); i != m_dirtyNets.end(); ++i )
183  *i = false;
184  }
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 551 of file connectivity_algo.cpp.

553 {
554  if( aZone->GetFilledPolysList( aLayer ).IsEmpty() )
555  return;
556 
557  aIslands.clear();
558 
559  Remove( aZone );
560  Add( aZone );
561 
563 
564  for( const auto& cluster : m_connClusters )
565  {
566  if( cluster->Contains( aZone ) && cluster->IsOrphaned() )
567  {
568  for( auto z : *cluster )
569  {
570  if( z->Parent() == aZone && z->Layer() == aLayer )
571  {
572  aIslands.push_back( static_cast<CN_ZONE_LAYER*>(z)->SubpolyIndex() );
573  }
574  }
575  }
576  }
577 
578  wxLogTrace( "CN", "Found %u isolated islands\n", (unsigned)aIslands.size() );
579 }
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:635
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 581 of file connectivity_algo.cpp.

582 {
583  for( auto& z : aZones )
584  {
585  Remove( z.m_zone );
586  Add( z.m_zone );
587  }
588 
590 
591  for( CN_ZONE_ISOLATED_ISLAND_LIST& zone : aZones )
592  {
593  for( PCB_LAYER_ID layer : zone.m_zone->GetLayerSet().Seq() )
594  {
595  if( zone.m_zone->GetFilledPolysList( layer ).IsEmpty() )
596  continue;
597 
598  for( const CN_CLUSTER_PTR& cluster : m_connClusters )
599  {
600  if( cluster->Contains( zone.m_zone ) && cluster->IsOrphaned() )
601  {
602  for( CN_ITEM* z : *cluster )
603  {
604  if( z->Parent() == zone.m_zone && z->Layer() == layer )
605  {
606  zone.m_islands[layer].push_back(
607  static_cast<CN_ZONE_LAYER*>( z )->SubpolyIndex() );
608  }
609  }
610  }
611  }
612  }
613  }
614 }
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:64
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 242 of file connectivity_algo.h.

243  {
244  for( auto&& item : m_itemList )
245  {
246  for( auto&& 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( auto&& item : m_itemList )
255  aFunc( *item );
256  }

References m_itemList.

◆ GetClusters()

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

Definition at line 617 of file connectivity_algo.cpp.

618 {
620  return m_ratsnestClusters;
621 }
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 186 of file connectivity_algo.h.

187  {
188  for( const auto& cl : m_ratsnestClusters )
189  {
190  int net = cl->OriginNet();
191 
192  if( net >= 0 && m_dirtyNets[net] )
193  aClusters.push_back( cl );
194  }
195  }
std::vector< bool > m_dirtyNets

References m_dirtyNets, and m_ratsnestClusters.

◆ IsNetDirty()

bool CN_CONNECTIVITY_ALGO::IsNetDirty ( int  aNet) const
inline

Definition at line 172 of file connectivity_algo.h.

173  {
174  if( aNet < 0 )
175  return false;
176 
177  return m_dirtyNets[ aNet ];
178  }
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 167 of file connectivity_algo.h.

168  {
169  return m_itemMap[ aItem ];
170  }
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 162 of file connectivity_algo.h.

163  {
164  return m_itemMap.find( aItem ) != m_itemMap.end();
165  }
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 236 of file connectivity_algo.h.

237  {
238  return m_itemList;
239  }

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:159
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:134
Definition: pad.h:57
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:113

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

625 {
626  if( aNet < 0 )
627  return;
628 
629  if( (int) m_dirtyNets.size() <= aNet )
630  {
631  int lastNet = m_dirtyNets.size() - 1;
632 
633  if( lastNet < 0 )
634  lastNet = 0;
635 
636  m_dirtyNets.resize( aNet + 1 );
637 
638  for( int i = lastNet; i < aNet + 1; i++ )
639  m_dirtyNets[i] = true;
640  }
641 
642  m_dirtyNets[aNet] = true;
643 }
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 197 of file connectivity_algo.h.

198  {
199  return m_dirtyNets.size();
200  }
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 482 of file connectivity_algo.cpp.

483 {
484  bool skipConflicts = ( aMode == PROPAGATE_MODE::SKIP_CONFLICTS );
485 
486  wxLogTrace( "CN", "propagateConnections: propagate skip conflicts? %d", skipConflicts );
487 
488  for( const auto& cluster : m_connClusters )
489  {
490  if( skipConflicts && cluster->IsConflicting() )
491  {
492  wxLogTrace( "CN", "Conflicting nets in cluster %p; skipping update", cluster.get() );
493  }
494  else if( cluster->IsOrphaned() )
495  {
496  wxLogTrace( "CN", "Skipping orphaned cluster %p [net: %s]", cluster.get(),
497  (const char*) cluster->OriginNetName().c_str() );
498  }
499  else if( cluster->HasValidNet() )
500  {
501  if( cluster->IsConflicting() )
502  {
503  wxLogTrace( "CN", "Conflicting nets in cluster %p; chose %d (%s)", cluster.get(),
504  cluster->OriginNet(), cluster->OriginNetName() );
505  }
506 
507  // normal cluster: just propagate from the pads
508  int n_changed = 0;
509 
510  for( auto item : *cluster )
511  {
512  if( item->CanChangeNet() )
513  {
514  if( item->Valid() && item->Parent()->GetNetCode() != cluster->OriginNet() )
515  {
516  MarkNetAsDirty( item->Parent()->GetNetCode() );
517  MarkNetAsDirty( cluster->OriginNet() );
518 
519  if( aCommit )
520  aCommit->Modify( item->Parent() );
521 
522  item->Parent()->SetNetCode( cluster->OriginNet() );
523  n_changed++;
524  }
525  }
526  }
527 
528  if( n_changed )
529  {
530  wxLogTrace( "CN", "Cluster %p : net : %d %s", cluster.get(),
531  cluster->OriginNet(), (const char*) cluster->OriginNetName().c_str() );
532  }
533  else
534  wxLogTrace( "CN", "Cluster %p : nothing to propagate", cluster.get() );
535  }
536  else
537  {
538  wxLogTrace( "CN", "Cluster %p : connected to unused net", cluster.get() );
539  }
540  }
541 }
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 544 of file connectivity_algo.cpp.

545 {
547  propagateConnections( aCommit, aMode );
548 }
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:113

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

308 {
309  bool withinAnyNet = ( aMode != CSM_PROPAGATE );
310 
311  std::deque<CN_ITEM*> Q;
312  std::set<CN_ITEM*> item_set;
313 
314  CLUSTERS clusters;
315 
316  if( m_itemList.IsDirty() )
318 
319  auto addToSearchList =
320  [&item_set, withinAnyNet, aSingleNet, aTypes]( CN_ITEM *aItem )
321  {
322  if( withinAnyNet && aItem->Net() <= 0 )
323  return;
324 
325  if( !aItem->Valid() )
326  return;
327 
328  if( aSingleNet >=0 && aItem->Net() != aSingleNet )
329  return;
330 
331  bool found = false;
332 
333  for( int i = 0; aTypes[i] != EOT; i++ )
334  {
335  if( aItem->Parent()->Type() == aTypes[i] )
336  {
337  found = true;
338  break;
339  }
340  }
341 
342  if( !found )
343  return;
344 
345  aItem->SetVisited( false );
346 
347  item_set.insert( aItem );
348  };
349 
350  std::for_each( m_itemList.begin(), m_itemList.end(), addToSearchList );
351 
353  return CLUSTERS();
354 
355  while( !item_set.empty() )
356  {
357  CN_CLUSTER_PTR cluster = std::make_shared<CN_CLUSTER>();
358  CN_ITEM* root;
359  auto it = item_set.begin();
360 
361  while( it != item_set.end() && (*it)->Visited() )
362  it = item_set.erase( item_set.begin() );
363 
364  if( it == item_set.end() )
365  break;
366 
367  root = *it;
368  root->SetVisited( true );
369 
370  Q.clear();
371  Q.push_back( root );
372 
373  while( Q.size() )
374  {
375  CN_ITEM* current = Q.front();
376 
377  Q.pop_front();
378  cluster->Add( current );
379 
380  for( auto n : current->ConnectedItems() )
381  {
382  if( withinAnyNet && n->Net() != root->Net() )
383  continue;
384 
385  if( !n->Visited() && n->Valid() )
386  {
387  n->SetVisited( true );
388  Q.push_back( n );
389  }
390  }
391  }
392 
393  clusters.push_back( cluster );
394  }
395 
397  return CLUSTERS();
398 
399  std::sort( clusters.begin(), clusters.end(),
400  []( CN_CLUSTER_PTR a, CN_CLUSTER_PTR b )
401  {
402  return a->OriginNet() < b->OriginNet();
403  } );
404 
405  return clusters;
406 }
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
bool IsCancelled() const
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
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 291 of file connectivity_algo.cpp.

292 {
293  constexpr KICAD_T types[] = { PCB_TRACE_T, PCB_ARC_T, PCB_PAD_T, PCB_VIA_T, PCB_ZONE_T,
294  PCB_FOOTPRINT_T, EOT };
295  constexpr KICAD_T no_zones[] = { PCB_TRACE_T, PCB_ARC_T, PCB_PAD_T, PCB_VIA_T,
296  PCB_FOOTPRINT_T, EOT };
297 
298  if( aMode == CSM_PROPAGATE )
299  return SearchClusters( aMode, no_zones, -1 );
300  else
301  return SearchClusters( aMode, types, -1 );
302 }
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 193 of file connectivity_algo.cpp.

194 {
195 #ifdef PROFILE
196  PROF_COUNTER garbage_collection( "garbage-collection" );
197 #endif
198  std::vector<CN_ITEM*> garbage;
199  garbage.reserve( 1024 );
200 
201  m_itemList.RemoveInvalidItems( garbage );
202 
203  for( auto item : garbage )
204  delete item;
205 
206 #ifdef PROFILE
207  garbage_collection.Show();
208  PROF_COUNTER search_basic( "search-basic" );
209 #endif
210 
211  std::vector<CN_ITEM*> dirtyItems;
212  std::copy_if( m_itemList.begin(), m_itemList.end(), std::back_inserter( dirtyItems ),
213  [] ( CN_ITEM* aItem )
214  {
215  return aItem->Dirty();
216  } );
217 
218  if( m_progressReporter )
219  {
220  m_progressReporter->SetMaxProgress( dirtyItems.size() );
221 
223  return;
224  }
225 
226  if( m_itemList.IsDirty() )
227  {
228  size_t parallelThreadCount = std::min<size_t>( std::thread::hardware_concurrency(),
229  ( dirtyItems.size() + 7 ) / 8 );
230 
231  std::atomic<size_t> nextItem( 0 );
232  std::vector<std::future<size_t>> returns( parallelThreadCount );
233 
234  auto conn_lambda =
235  [&nextItem, &dirtyItems]( CN_LIST* aItemList,
236  PROGRESS_REPORTER* aReporter) -> size_t
237  {
238  for( size_t i = nextItem++; i < dirtyItems.size(); i = nextItem++ )
239  {
240  CN_VISITOR visitor( dirtyItems[i] );
241  aItemList->FindNearby( dirtyItems[i], visitor );
242 
243  if( aReporter )
244  {
245  if( aReporter->IsCancelled() )
246  break;
247  else
248  aReporter->AdvanceProgress();
249  }
250  }
251 
252  return 1;
253  };
254 
255  if( parallelThreadCount <= 1 )
256  conn_lambda( &m_itemList, m_progressReporter );
257  else
258  {
259  for( size_t ii = 0; ii < parallelThreadCount; ++ii )
260  {
261  returns[ii] = std::async( std::launch::async, conn_lambda, &m_itemList,
263  }
264 
265  for( size_t ii = 0; ii < parallelThreadCount; ++ii )
266  {
267  // Here we balance returns with a 100ms timeout to allow UI updating
268  std::future_status status;
269  do
270  {
271  if( m_progressReporter )
273 
274  status = returns[ii].wait_for( std::chrono::milliseconds( 100 ) );
275  } while( status != std::future_status::ready );
276  }
277  }
278 
279  if( m_progressReporter )
281  }
282 
283 #ifdef PROFILE
284  search_basic.Show();
285 #endif
286 
288 }
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
A progress reporter for use in multi-threaded environments.
void ClearDirtyFlags()
bool IsDirty() const
A small class to help profiling.
Definition: profile.h:45
bool KeepRefreshing(bool aWait=false)
Update the UI dialog.
void SetMaxProgress(int aMaxProgress)
Fix the value that gives the 100 percent progress bar length (inside the current virtual zone).
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 821 of file connectivity_algo.cpp.

822 {
823  m_progressReporter = aReporter;
824 }
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 279 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 284 of file connectivity_algo.h.

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

◆ m_ratsnestClusters

CLUSTERS 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: