# Kite - Detailed Router

SegmentFsm.h
1 // -*- C++ -*-
2 //
3 // This file is part of the Coriolis Software.
4 // Copyright (c) UPMC 2008-2018, All Rights Reserved
5 //
6 // +-----------------------------------------------------------------+
7 // | C O R I O L I S |
8 // | K i t e - D e t a i l e d R o u t e r |
9 // | |
10 // | Author : Jean-Paul CHAPUT |
11 // | E-mail : Jean-Paul.Chaput@asim.lip6.fr |
12 // | =============================================================== |
13 // | C++ Header : "./kite/SegmentFsm.h" |
14 // +-----------------------------------------------------------------+
15
16
17 #ifndef KITE_SEGMENT_FSM_H
18 #define KITE_SEGMENT_FSM_H
19
20 #include "kite/TrackCost.h"
21
22 namespace Kite {
23
24 class TrackElement;
25 class DataNegociate;
26 class RoutingEvent;
27 class RoutingEventQueue;
28 class RoutingEventHistory;
29
30
31 // -------------------------------------------------------------------
32 // Class : "SegmentAction".
33
34 class SegmentAction {
35 public:
36 enum Type { Self = (1<< 0)
37 , Other = (1<< 1)
38 , Perpandicular = (1<< 2)
39 , Insert = (1<< 3)
40 , Ripup = (1<< 4)
41 , RipedByLocal = (1<< 5)
42 , ResetRipup = (1<< 6)
43 , ToRipupLimit = (1<< 7)
44 , MoveToAxis = (1<< 8)
45 , AxisHint = (1<< 9)
46 , PackingMode = (1<<10)
47 , ToState = (1<<11)
48 , EventLevel1 = (1<<12)
49 , EventLevel2 = (1<<13)
50 , EventLevel3 = (1<<14)
51 , EventLevel4 = (1<<15)
52 , EventLevel5 = (1<<16)
53 , SelfInsert = Self |Insert
54 , SelfRipup = Self |Ripup
55 , SelfRipupPerpand = Self |Ripup|Perpandicular
56 , SelfRipupPerpandWithAxisHint = Self |Ripup|Perpandicular|EventLevel4|AxisHint
57 , OtherRipup = Other|Ripup
58 , OtherRipupPerpandAndPushAside = Other|Ripup|Perpandicular|EventLevel3|AxisHint
59 , OtherRipupPerpandAndPacking = Other|Ripup|Perpandicular|EventLevel4|PackingMode
60 };
61 public:
62 SegmentAction ( TrackElement*
63 , unsigned int type
64 , DbU::Unit axisHint=0
65 , unsigned int toState =0
66 );
67 inline TrackElement* getSegment () const;
68 inline unsigned int getType () const;
69 inline void setAxisHint ( DbU::Unit );
70 inline unsigned int setFlag ( unsigned int );
71 bool doAction ( RoutingEventQueue& );
72 private:
73 TrackElement* _segment;
74 unsigned int _type;
75 DbU::Unit _axisHint;
76 unsigned int _toState;
77 };
78
79
80 inline TrackElement* SegmentAction::getSegment () const { return _segment; }
81 inline unsigned int SegmentAction::getType () const { return _type; }
82 inline void SegmentAction::setAxisHint ( DbU::Unit axis ) { _axisHint = axis; }
83 inline unsigned int SegmentAction::setFlag ( unsigned int flag ) { _type |= flag; return _type; }
84
85
86 // -------------------------------------------------------------------
87 // Class : "SegmentFsm".
88
89 class SegmentFsm {
90
91 public:
92 enum State { MissingData = (1<<0)
93 , EmptyTrackList = (1<<1)
94 , Inserted = (1<<2)
95 , Self = (1<<3)
96 , Other = (1<<4)
97 , Ripup = (1<<5)
98 , MaximumSlack = (1<<6)
99 , SelfInserted = Self | Inserted
100 , OtherRipup = Other | Ripup
101 , SelfMaximumSlack = Self | MaximumSlack
102 };
103 enum SlackenFlags { NoRecursive = (1<<0)
104 , NoTransition = (1<<1)
105 };
106
107 public:
108 SegmentFsm ( RoutingEvent*
109 , RoutingEventQueue&
110 , RoutingEventHistory&
111 );
112 inline bool isFullBlocked () const;
113 inline RoutingEvent* getEvent () const;
114 inline RoutingEventQueue& getQueue () const;
115 inline RoutingEventHistory& getHistory () const;
116 inline unsigned int getState () const;
117 inline DataNegociate* getData ();
118 inline Interval& getConstraint ();
119 inline Interval& getOptimal ();
120 inline vector<TrackCost>& getCosts ();
121 inline TrackCost& getCost ( size_t );
122 inline Track* getTrack ( size_t );
123 inline size_t getBegin ( size_t );
124 inline size_t getEnd ( size_t );
125 inline vector<SegmentAction>& getActions ();
126 inline void setState ( unsigned int );
127 void addAction ( TrackElement*
128 , unsigned int type
129 , DbU::Unit axisHint=0
130 , unsigned int toState =0
131 );
132 void doActions ();
133 inline void clearActions ();
134 bool insertInTrack ( size_t );
135 bool conflictSolveByHistory ();
136 bool conflictSolveByPlaceds ();
137 bool solveTerminalVsGlobal ();
138 bool desaturate ();
139 bool slackenTopology ( unsigned int flags=0 );
140 bool solveFullBlockages ();
141 private:
142 bool _slackenStrap ( TrackElement*&
143 , DataNegociate*&
144 , unsigned int flags );
145 bool _slackenLocal ( TrackElement*&
146 , DataNegociate*&
147 , unsigned int flags );
148 bool _slackenGlobal ( TrackElement*&
149 , DataNegociate*&
150 , unsigned int flags );
151 private:
152 RoutingEvent* _event;
153 RoutingEventQueue& _queue;
154 RoutingEventHistory& _history;
155 unsigned int _state;
156 DataNegociate* _data;
157 Interval _constraint;
158 Interval _optimal;
159 vector<TrackCost> _costs;
160 vector<SegmentAction> _actions;
161 bool _fullBlocked;
162 };
163
164
165 inline bool SegmentFsm::isFullBlocked () const { return _fullBlocked and _costs.size(); }
166 inline RoutingEvent* SegmentFsm::getEvent () const { return _event; }
167 inline RoutingEventQueue& SegmentFsm::getQueue () const { return _queue; }
168 inline RoutingEventHistory& SegmentFsm::getHistory () const { return _history; }
169 inline unsigned int SegmentFsm::getState () const { return _state; }
170 inline DataNegociate* SegmentFsm::getData () { return _data; }
171 inline Interval& SegmentFsm::getConstraint () { return _constraint; }
172 inline Interval& SegmentFsm::getOptimal () { return _optimal; }
173 inline vector<TrackCost>& SegmentFsm::getCosts () { return _costs; }
174 inline TrackCost& SegmentFsm::getCost ( size_t i ) { return _costs[i]; }
175 inline Track* SegmentFsm::getTrack ( size_t i ) { return _costs[i].getTrack(); }
176 inline size_t SegmentFsm::getBegin ( size_t i ) { return _costs[i].getBegin(); }
177 inline size_t SegmentFsm::getEnd ( size_t i ) { return _costs[i].getEnd(); }
178 inline vector<SegmentAction>& SegmentFsm::getActions () { return _actions; }
179 inline void SegmentFsm::setState ( unsigned int state ) { _state = state; }
180 inline void SegmentFsm::clearActions () { _actions.clear(); }
181
182
183 } // Kite namespace.
184
185 #endif // KITE_SEGMENT_FSM_H
Kite::RoutingEvent
Atomic Placement Request for a TrackSegment.
Definition: RoutingEvent.h:55
Kite::SegmentFsm::doActions
void doActions()
Definition: SegmentFsm.cpp:583
Kite::SegmentAction::OtherRipupPerpandAndPushAside
Definition: SegmentFsm.h:58
Kite::SegmentAction::RipedByLocal
Definition: SegmentFsm.h:41
Kite::SegmentAction::SelfRipup
Definition: SegmentFsm.h:54
Kite::SegmentFsm::getState
unsigned int getState() const
Definition: SegmentFsm.h:169
Kite::SegmentAction::OtherRipup
Definition: SegmentFsm.h:57
Kite::SegmentAction::getSegment
TrackElement * getSegment() const
Definition: SegmentFsm.h:80
Kite::SegmentAction::Ripup
Definition: SegmentFsm.h:40
Kite::SegmentFsm::SelfInserted
Definition: SegmentFsm.h:99
Kite::SegmentFsm::insertInTrack
bool insertInTrack(size_t)
Definition: SegmentFsm.cpp:612
Kite::SegmentFsm::getData
DataNegociate * getData()
Definition: SegmentFsm.h:170
Kite::SegmentFsm
Pseudo-decorator to process a RoutingEvent.
Definition: SegmentFsm.h:89
Kite::SegmentFsm::getQueue
RoutingEventQueue & getQueue() const
Definition: SegmentFsm.h:167
Kite::SegmentAction::setFlag
unsigned int setFlag(unsigned int)
Definition: SegmentFsm.h:83
Hurricane::DbU::Unit
std::int64_t Unit
Kite::SegmentAction::Type
Type
Definition: SegmentFsm.h:36
Kite::SegmentFsm::desaturate
bool desaturate()
Definition: SegmentFsm.cpp:939
Kite::SegmentFsm::MaximumSlack
Definition: SegmentFsm.h:98
Kite::SegmentAction::SelfInsert
Definition: SegmentFsm.h:53
Kite::SegmentFsm::EmptyTrackList
Definition: SegmentFsm.h:93
Kite::SegmentAction::setAxisHint
void setAxisHint(DbU::Unit)
Definition: SegmentFsm.h:82
Kite::SegmentFsm::Self
Definition: SegmentFsm.h:95
Kite::SegmentFsm::slackenTopology
bool slackenTopology(unsigned int flags=0)
Definition: SegmentFsm.cpp:1205
Kite::SegmentFsm::SelfMaximumSlack
Definition: SegmentFsm.h:101
Kite::Track
Structure managing one routing track.
Definition: Track.h:42
Hurricane::Interval
Kite::SegmentFsm::State
State
Definition: SegmentFsm.h:92
Kite::SegmentFsm::getCost
TrackCost & getCost(size_t)
Definition: SegmentFsm.h:174
Kite::SegmentFsm::getEvent
RoutingEvent * getEvent() const
Definition: SegmentFsm.h:166
Kite::SegmentAction::AxisHint
Definition: SegmentFsm.h:45
Kite::SegmentFsm::getActions
vector< SegmentAction > & getActions()
Definition: SegmentFsm.h:178
Kite::SegmentAction::SegmentAction
SegmentAction(TrackElement *, unsigned int type, DbU::Unit axisHint=0, unsigned int toState=0)
Definition: SegmentFsm.cpp:349
Kite::SegmentAction::OtherRipupPerpandAndPacking
Definition: SegmentFsm.h:59
Kite::SegmentAction::getType
unsigned int getType() const
Definition: SegmentFsm.h:81
Kite::SegmentAction::SelfRipupPerpandWithAxisHint
Definition: SegmentFsm.h:56
Kite::SegmentAction::EventLevel3
Definition: SegmentFsm.h:50
Kite::SegmentFsm::getOptimal
Interval & getOptimal()
Definition: SegmentFsm.h:172
Kite::SegmentAction::EventLevel5
Definition: SegmentFsm.h:52
Kite::SegmentAction::EventLevel4
Definition: SegmentFsm.h:51
Kite::SegmentFsm::Ripup
Definition: SegmentFsm.h:97
Kite::SegmentFsm::OtherRipup
Definition: SegmentFsm.h:100
Kite::SegmentFsm::getTrack
Track * getTrack(size_t)
Definition: SegmentFsm.h:175
Kite::SegmentAction::doAction
bool doAction(RoutingEventQueue &)
Definition: SegmentFsm.cpp:361
Kite::RoutingEventHistory
History of RoutingEvent.
Definition: RoutingEventHistory.h:35
Kite::SegmentFsm::clearActions
void clearActions()
Definition: SegmentFsm.h:180
Kite::SegmentFsm::solveFullBlockages
bool solveFullBlockages()
Definition: SegmentFsm.cpp:893
Kite::SegmentAction::Perpandicular
Definition: SegmentFsm.h:38
Kite::TrackElement
Abstract Class for all Elements inserted inside a Track.
Definition: TrackElement.h:100
Kite::SegmentAction::EventLevel1
Definition: SegmentFsm.h:48
Kite::SegmentFsm::conflictSolveByHistory
bool conflictSolveByHistory()
Definition: SegmentFsm.cpp:633
Kite::SegmentFsm::setState
void setState(unsigned int)
Definition: SegmentFsm.h:179
Kite::SegmentAction::Self
Definition: SegmentFsm.h:36
Kite::SegmentFsm::Other
Definition: SegmentFsm.h:96
Kite::SegmentFsm::SegmentFsm
SegmentFsm(RoutingEvent *, RoutingEventQueue &, RoutingEventHistory &)
Definition: SegmentFsm.cpp:442
Kite::SegmentAction::EventLevel2
Definition: SegmentFsm.h:49
Kite::SegmentFsm::getHistory
RoutingEventHistory & getHistory() const
Definition: SegmentFsm.h:168
Kite::RoutingEventQueue
The priority Queue of RoutingEvent.
Definition: RoutingEventQueue.h:35
Kite::SegmentFsm::isFullBlocked
bool isFullBlocked() const
Definition: SegmentFsm.h:165
Kite::SegmentAction
Store request for an event to be generated on a TrackElement.
Definition: SegmentFsm.h:34
Kite
The namespace dedicated to Kite.
Definition: Constants.h:22
Kite::SegmentFsm::conflictSolveByPlaceds
bool conflictSolveByPlaceds()
Definition: SegmentFsm.cpp:718
Kite::SegmentFsm::Inserted
Definition: SegmentFsm.h:94
Kite::SegmentAction::Other
Definition: SegmentFsm.h:37
Kite::SegmentFsm::MissingData
Definition: SegmentFsm.h:92
Kite::SegmentFsm::getCosts
vector< TrackCost > & getCosts()
Definition: SegmentFsm.h:173
Kite::SegmentAction::ToRipupLimit
Definition: SegmentFsm.h:43
Kite::DataNegociate
Algorimthmic datas associated the TrackSegment.
Definition: DataNegociate.h:50
Kite::SegmentAction::ResetRipup
Definition: SegmentFsm.h:42
Kite::SegmentAction::SelfRipupPerpand
Definition: SegmentFsm.h:55
Kite::SegmentFsm::getConstraint
Interval & getConstraint()
Definition: SegmentFsm.h:171
Kite::SegmentFsm::getEnd
size_t getEnd(size_t)
Definition: SegmentFsm.h:177
Kite::SegmentAction::Insert
Definition: SegmentFsm.h:39
Kite::SegmentFsm::addAction
void addAction(TrackElement *, unsigned int type, DbU::Unit axisHint=0, unsigned int toState=0)
Definition: SegmentFsm.cpp:571
Kite::SegmentAction::ToState
Definition: SegmentFsm.h:47
Kite::SegmentAction::PackingMode
Definition: SegmentFsm.h:46
Kite::SegmentFsm::getBegin
size_t getBegin(size_t)
Definition: SegmentFsm.h:176