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)
 Propagates 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)
 Finds 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 185 of file connectivity_algo.h.

185 {}

◆ ~CN_CONNECTIVITY_ALGO()

CN_CONNECTIVITY_ALGO::~CN_CONNECTIVITY_ALGO ( )
inline

Definition at line 186 of file connectivity_algo.h.

186 { Clear(); }

References Clear().

Member Function Documentation

◆ add()

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

Definition at line 175 of file connectivity_algo.h.

176  {
177  auto item = c.Add( brditem );
178 
179  m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item );
180  }
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap

References m_itemMap.

Referenced by Add().

◆ Add()

bool CN_CONNECTIVITY_ALGO::Add ( BOARD_ITEM aItem)

Definition at line 114 of file connectivity_algo.cpp.

115 {
116  if( !aItem->IsOnCopperLayer() )
117  return false;
118 
119  markItemNetAsDirty ( aItem );
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  for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
129  {
130  if( m_itemMap.find( pad ) != m_itemMap.end() )
131  return false;
132 
133  add( m_itemList, pad );
134  }
135 
136  break;
137 
138  case PCB_PAD_T:
139  if( m_itemMap.find ( aItem ) != m_itemMap.end() )
140  return false;
141 
142  add( m_itemList, static_cast<PAD*>( aItem ) );
143  break;
144 
145  case PCB_TRACE_T:
146  if( m_itemMap.find( aItem ) != m_itemMap.end() )
147  return false;
148 
149  add( m_itemList, static_cast<TRACK*>( aItem ) );
150  break;
151 
152  case PCB_ARC_T:
153  if( m_itemMap.find( aItem ) != m_itemMap.end() )
154  return false;
155 
156  add( m_itemList, static_cast<ARC*>( aItem ) );
157  break;
158 
159  case PCB_VIA_T:
160  if( m_itemMap.find( aItem ) != m_itemMap.end() )
161  return false;
162 
163  add( m_itemList, static_cast<VIA*>( aItem ) );
164  break;
165 
166  case PCB_ZONE_T:
167  {
168  ZONE* zone = static_cast<ZONE*>( aItem );
169 
170  if( m_itemMap.find( aItem ) != m_itemMap.end() )
171  return false;
172 
173  m_itemMap[zone] = ITEM_MAP_ENTRY();
174 
175  for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
176  {
177  for( CN_ITEM* zitem : m_itemList.Add( zone, layer ) )
178  m_itemMap[zone].Link( zitem );
179  }
180  }
181  break;
182 
183  default:
184  return false;
185  }
186 
187  return true;
188 }
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 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 TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
PCB_LAYER_ID
A quick note on layer IDs:
void markItemNetAsDirty(const BOARD_ITEM *aItem)
Handle a list of polygons defining a copper zone.
Definition: zone.h:57
class ZONE, a copper pour area
Definition: typeinfo.h:105
class FOOTPRINT, a footprint
Definition: typeinfo.h:88
class NETINFO_ITEM, a description of a net
Definition: typeinfo.h:107
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96
Definition: pad.h:60
virtual bool IsOnCopperLayer() const
Definition: board_item.h:144
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:163

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().

◆ Build() [1/2]

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

Definition at line 417 of file connectivity_algo.cpp.

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

References Add(), 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 454 of file connectivity_algo.cpp.

455 {
456  for( auto item : aItems )
457  {
458  switch( item->Type() )
459  {
460  case PCB_TRACE_T:
461  case PCB_ARC_T:
462  case PCB_VIA_T:
463  case PCB_PAD_T:
464  Add( item );
465  break;
466 
467  case PCB_FOOTPRINT_T:
468  for( PAD* pad : static_cast<FOOTPRINT*>( item )->Pads() )
469  Add( pad );
470 
471  break;
472 
473  default:
474  break;
475  }
476  }
477 }
class 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 TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
class FOOTPRINT, a footprint
Definition: typeinfo.h:88
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96
Definition: pad.h:60

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

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

207  {
208  for( auto i = m_dirtyNets.begin(); i != m_dirtyNets.end(); ++i )
209  *i = false;
210  }
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 549 of file connectivity_algo.cpp.

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

Finds 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 The set of zones to search for islands

Definition at line 579 of file connectivity_algo.cpp.

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

267  {
268  for( auto&& item : m_itemList )
269  {
270  for( auto&& anchor : item->Anchors() )
271  aFunc( *anchor );
272  }
273  }

References anchor, and m_itemList.

◆ ForEachItem()

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

Definition at line 276 of file connectivity_algo.h.

277  {
278  for( auto&& item : m_itemList )
279  aFunc( *item );
280  }

References m_itemList.

◆ GetClusters()

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

Definition at line 615 of file connectivity_algo.cpp.

616 {
618  return m_ratsnestClusters;
619 }
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 212 of file connectivity_algo.h.

213  {
214  for( const auto& cl : m_ratsnestClusters )
215  {
216  int net = cl->OriginNet();
217 
218  if( net >= 0 && m_dirtyNets[net] )
219  aClusters.push_back( cl );
220  }
221  }
std::vector< bool > m_dirtyNets

References m_dirtyNets, and m_ratsnestClusters.

◆ IsNetDirty()

bool CN_CONNECTIVITY_ALGO::IsNetDirty ( int  aNet) const
inline

Definition at line 198 of file connectivity_algo.h.

199  {
200  if( aNet < 0 )
201  return false;
202 
203  return m_dirtyNets[ aNet ];
204  }
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 193 of file connectivity_algo.h.

194  {
195  return m_itemMap[ aItem ];
196  }
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 188 of file connectivity_algo.h.

189  {
190  return m_itemMap.find( aItem ) != m_itemMap.end();
191  }
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 260 of file connectivity_algo.h.

261  {
262  return m_itemList;
263  }

References m_itemList.

◆ markItemNetAsDirty()

void CN_CONNECTIVITY_ALGO::markItemNetAsDirty ( const BOARD_ITEM aItem)
private

Definition at line 94 of file connectivity_algo.cpp.

95 {
96  if( aItem->IsConnected() )
97  {
98  auto citem = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
99  MarkNetAsDirty( citem->GetNetCode() );
100  }
101  else
102  {
103  if( aItem->Type() == PCB_FOOTPRINT_T )
104  {
105  const FOOTPRINT* footprint = static_cast<const FOOTPRINT*>( aItem );
106 
107  for( PAD* pad : footprint->Pads() )
108  MarkNetAsDirty( pad->GetNetCode() );
109  }
110  }
111 }
void MarkNetAsDirty(int aNet)
PADS & Pads()
Definition: footprint.h:164
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:136
Definition: pad.h:60
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:163

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

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

224  {
225  return m_dirtyNets.size();
226  }
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 480 of file connectivity_algo.cpp.

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

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

543 {
545  propagateConnections( aCommit, aMode );
546 }
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 42 of file connectivity_algo.cpp.

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

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

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

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

192 {
193 #ifdef PROFILE
194  PROF_COUNTER garbage_collection( "garbage-collection" );
195 #endif
196  std::vector<CN_ITEM*> garbage;
197  garbage.reserve( 1024 );
198 
199  m_itemList.RemoveInvalidItems( garbage );
200 
201  for( auto item : garbage )
202  delete item;
203 
204 #ifdef PROFILE
205  garbage_collection.Show();
206  PROF_COUNTER search_basic( "search-basic" );
207 #endif
208 
209  std::vector<CN_ITEM*> dirtyItems;
210  std::copy_if( m_itemList.begin(), m_itemList.end(), std::back_inserter( dirtyItems ),
211  [] ( CN_ITEM* aItem )
212  {
213  return aItem->Dirty();
214  } );
215 
216  if( m_progressReporter )
217  {
218  m_progressReporter->SetMaxProgress( dirtyItems.size() );
219 
221  return;
222  }
223 
224  if( m_itemList.IsDirty() )
225  {
226  size_t parallelThreadCount = std::min<size_t>( std::thread::hardware_concurrency(),
227  ( dirtyItems.size() + 7 ) / 8 );
228 
229  std::atomic<size_t> nextItem( 0 );
230  std::vector<std::future<size_t>> returns( parallelThreadCount );
231 
232  auto conn_lambda =
233  [&nextItem, &dirtyItems]( CN_LIST* aItemList,
234  PROGRESS_REPORTER* aReporter) -> size_t
235  {
236  for( size_t i = nextItem++; i < dirtyItems.size(); i = nextItem++ )
237  {
238  CN_VISITOR visitor( dirtyItems[i] );
239  aItemList->FindNearby( dirtyItems[i], visitor );
240 
241  if( aReporter )
242  {
243  if( aReporter->IsCancelled() )
244  break;
245  else
246  aReporter->AdvanceProgress();
247  }
248  }
249 
250  return 1;
251  };
252 
253  if( parallelThreadCount <= 1 )
254  conn_lambda( &m_itemList, m_progressReporter );
255  else
256  {
257  for( size_t ii = 0; ii < parallelThreadCount; ++ii )
258  {
259  returns[ii] = std::async( std::launch::async, conn_lambda, &m_itemList,
261  }
262 
263  for( size_t ii = 0; ii < parallelThreadCount; ++ii )
264  {
265  // Here we balance returns with a 100ms timeout to allow UI updating
266  std::future_status status;
267  do
268  {
269  if( m_progressReporter )
271 
272  status = returns[ii].wait_for( std::chrono::milliseconds( 100 ) );
273  } while( status != std::future_status::ready );
274  }
275  }
276 
277  if( m_progressReporter )
279  }
280 
281 #ifdef PROFILE
282  search_basic.Show();
283 #endif
284 
286 }
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 thar gives the 100 precent 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 819 of file connectivity_algo.cpp.

820 {
821  m_progressReporter = aReporter;
822 }
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 162 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 167 of file connectivity_algo.h.

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

◆ m_ratsnestClusters

CLUSTERS CN_CONNECTIVITY_ALGO::m_ratsnestClusters
private

Definition at line 165 of file connectivity_algo.h.

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


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