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

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

420 {
421  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  delta = std::max( delta, size / 50 );
434 
435  for( ZONE* zone : aBoard->Zones() )
436  {
437  Add( zone );
438  reportProgress( aReporter, ii++, size, delta );
439  }
440 
441  for( PCB_TRACK* tv : aBoard->Tracks() )
442  {
443  Add( tv );
444  reportProgress( aReporter, ii++, size, delta );
445  }
446 
447  for( FOOTPRINT* footprint : aBoard->Footprints() )
448  {
449  for( PAD* pad : footprint->Pads() )
450  {
451  Add( pad );
452  reportProgress( aReporter, ii++, size, delta );
453  }
454  }
455 }
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 458 of file connectivity_algo.cpp.

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

815 {
816  m_ratsnestClusters.clear();
817  m_connClusters.clear();
818  m_itemMap.clear();
819  m_itemList.Clear();
820 
821 }
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 553 of file connectivity_algo.cpp.

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

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

620 {
622  return m_ratsnestClusters;
623 }
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:168
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 626 of file connectivity_algo.cpp.

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

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

547 {
549  propagateConnections( aCommit, aMode );
550 }
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 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
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 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)
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 small class to help profiling.
Definition: profile.h:45
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 823 of file connectivity_algo.cpp.

824 {
825  m_progressReporter = aReporter;
826 }
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: