# Kite - Detailed Router

Public Types | Public Member Functions | Static Public Attributes | List of all members
Track Class Referenceabstract

Structure managing one routing track. More...

Inheritance diagram for Track:
[legend]

## Public Types

enum

IndexState {
BeginIsTrackMin = 0x00000001,
BeginIsSegmentMin = 0x00000002,
BeginIsSegmentMax = 0x00000004,
EndIsTrackMax = 0x00000008,
EndIsSegmentMin = 0x00000010,
EndIsNextSegmentMin = 0x00000020,
EndIsSegmentMax = 0x00000040,
BeforeFirstElement = BeginIsTrackMin |EndIsSegmentMin,
InsideElement = BeginIsSegmentMin|EndIsSegmentMax,
OutsideElement = BeginIsSegmentMax|EndIsNextSegmentMin,
AfterLastElement = BeginIsSegmentMax|EndIsTrackMax,
EmptyTrack = BeginIsTrackMin |EndIsTrackMax,
BeginMask = BeginIsTrackMin |BeginIsSegmentMin|BeginIsSegmentMax,
EndMask = EndIsTrackMax |EndIsSegmentMin |EndIsNextSegmentMin|EndIsSegmentMax
}

## Public Member Functions

virtual bool | isHorizontal () const =0
virtual bool | isVertical () const =0
bool | isLocalAssigned () const
RoutingPlane * | getRoutingPlane () const
KiteEngine * | getKiteEngine () const
virtual unsigned int | getDirection () const =0
size_t | getIndex () const
unsigned int | getDepth () const
const Layer * | getLayer () const
const Layer * | getBlockageLayer () const
DbU::Unit | getAxis () const
DbU::Unit | getMin () const
DbU::Unit | getMax () const
Track * | getNextTrack () const
Track * | getPreviousTrack () const
size_t | getSize () const
virtual Point | getPosition (DbU::Unit coordinate) const =0
TrackElement * | getSegment (size_t index) const
TrackElement * | getSegment (DbU::Unit position) const
TrackElement * | getNext (size_t &index, Net *) const
TrackElement * | getPrevious (size_t &index, Net *) const
TrackElement * | getNextFixed (size_t &index) const
size_t | find (const TrackElement *) const
DbU::Unit | getSourcePosition (vector< TrackElement *>::iterator) const
DbU::Unit | getMinimalPosition (size_t index, unsigned int state) const
DbU::Unit | getMaximalPosition (size_t index, unsigned int state) const
Interval | getFreeInterval (DbU::Unit position, Net *net=NULL) const
Interval | getOccupiedInterval (size_t &begin) const
Interval | expandFreeInterval (size_t &begin, size_t &end, unsigned int state, Net *) const
void | getBeginIndex (DbU::Unit position, size_t &begin, unsigned int &state) const
void | getOverlapBounds (Interval, size_t &begin, size_t &end) const
TrackCost | getOverlapCost (Interval, Net *, size_t begin, size_t end, unsigned int flags) const
TrackCost | getOverlapCost (Interval, Net *, unsigned int flags) const
TrackCost | getOverlapCost (TrackElement *, unsigned int flags) const
void | getTerminalWeight (Interval, Net *, size_t &count, unsigned int &weight) const
DbU::Unit | getSourcePosition (size_t index) const
bool | check (unsigned int &overlaps, const char *message=NULL) const
void | invalidate ()
void | insert (TrackElement *)
void | insert (TrackMarker *)
void | setSegment (TrackElement *, size_t)
size_t | doRemoval ()
void | doReorder ()

## Static Public Attributes

static const size_t | npos = (size_t)-1

## Detailed Description

Structure managing one routing track.

# Track Purpose

We use an array of regularly spaced Track as a geometrical fast access structure. It allows to know whether an area is used or not. The whole area may be seen as a set of adjoining tiles of fixed width but variable length.

The figure (1.b) show, for an horizontal, track the relation between `y,min,max` and the occupied area of the plane. `min` and `max` must take into account segment extensions (`e`) and the minimal distance between two rectangles (`MD`) of the same layer. We assume that the width of the segment, augmented of all it's contraints is no greater than `TS` (in fact it's how `TS` must be calculated).

For the whole track array, see RoutingPlane.

Fig 1: Track Area

# Track Implementation

A Track is implemented with a sorted vector of TrackElement. TrackElements from differents nets must not overlap. The sorting order is defined as follow:

- TrackElements are sorted by increasing source (min) positions.
- In case of overlap (i.e. belongs to the same net), if they share the same source position, then they are sorted by decreasing length. This way, the longest one will be the first encountered when walking through the Track in increasing index order.

Figure 2.b shows the details of the Track [1] of figure 1.a. Net <d> show an exemple of overlapping.

Fig 2: Track Structure

In addition to the TrackSegments, the Track also manage additionnal informations through a second vector of TrackMarkers. TrackMarker are currently used only to hints at how strongly a terminal is dependant on that portion of Track to be accessed.

## Indexes vs. Iterators

Numerical indexes have been prefered over iterators because they can be used more easily by objects other the Track itself for referencing. So internal managment follow the same rule, handling indexes or reference to indexes.

## Update Mechanism

When a TrackElement is normaly inserted in a Track, a two way link is established. The Track has an entry in it's vector refering to TrackElement, and conversely, the TrackElement has it's `track` field pointing to it's owning Track.

TrackElement Removal

To remove a TrackElement from a Track, we break one of those two links: the TrackElement cease to refer to the owning Track, marking him for removal which will occurs at the next track revalidation (Track::doRemoval()). In figure 3, the TrackElement belonging to net <b> is marked for removal.

Fig 3: TrackElement Removal

TrackElement Insertion

When a TrackElement is inserted into a Track, the two way link is immediatly created (but the TrackElement is not yet at it's final place in the Track's vector). Before inserting a TrackElement we check that it's been already detached (`track` field to `NULL`).

It is at that step that the TrackElement axis is actually updated through a call to TrackElement::setAxis().

Revalidation Sequence

After a Track has been modificated either the Track element vector or the MarkerElement vector (or both) has been invalidateds. Revalidation take place in three steps:

- Track::doRemoval(), remove all TrackElement marked for removal.
- Track::insert(), insert the TrackElement into their new Track.
- Track::doReorder(), sort the TrackElement of the vector, that is, put the newly inserted elements at their right place.

Each step must be done for all Tracks before proceeding to the next. This way a TrackElement `track` field doesn't get set before it has been actually removed from it's previous Track.

## Main Operations on Tracks

Helper Function: Track::getBeginIndex()

Return in `begin` the index of the TrackElement whose minimum is immediately below the requested `position` on the Track axis. The second returned parameter `state` is a set of flags to tell how the `begin` index has to be interpreted.

Helper Function: Track::getOccupiedInterval()

Returns the complete interval of a set of overlapping TrackElement from the same net.

## Member Enumeration Documentation

## ◆ IndexState

enum IndexState

Indicates how to compute the bounds of the interval enclosing a given `position` on track axis.

Note
  According to position, the interval can be a free interval or a used interval.

Enumerator
BeginIsTrackMin | (implies `begin=0`) there is no TrackElement before `position`
BeginIsSegmentMin | The `begin` segment starts before `position` and ends after.
BeginIsSegmentMax | The `begin` segment starts and ends before `position`.
EndIsTrackMax | There is no TrackElement after `position`.
EndIsSegmentMin | The `begin` segment starts before `position`.
EndIsNextSegmentMin | The `begin` segment starts and ends before `position`. So the maximum is given by the `minimum` of the next TrackElement.
EndIsSegmentMax | The `begin` segment starts before `position` and ends after.
BeforeFirstElement | the `position` is before the first TrackElement.
InsideElement | the `position` is inside a TrackElement.
OutsideElement | the `position` is in free zone between two TrackElements.
AfterLastElement | the position is after the end of the last element.
EmptyTrack | the track is still empty.
BeginMask | To extract the begin part from a combination of flags.
EndMask | To extract the end part from a combination of flags.

## Member Function Documentation

## ◆ isHorizontal()

bool isHorizontal | ( |  | ) | const

pure virtual

Returns: true if the Track in horizontal direction.

Implemented in HorizontalTrack, and VerticalTrack.

Referenced by TrackFixedSegment::isHorizontal().

## ◆ isVertical()

bool isVertical | ( |  | ) | const

pure virtual

Returns: true if the Track in vertical direction.

Implemented in HorizontalTrack, and VerticalTrack.

Referenced by TrackFixedSegment::isVertical().

## ◆ isLocalAssigned()

bool isLocalAssigned | ( |  | ) | const

inline

Returns: true is the Track should be preferentially used for local routing.

## ◆ getRoutingPlane()

RoutingPlane * getRoutingPlane | ( |  | ) | const

inline

Returns: The RoutingPlane owning this Track.

Referenced by Track::getNextTrack(), and Track::getPreviousTrack().

## ◆ getKiteEngine()

KiteEngine * getKiteEngine | ( |  | ) | const

Returns: The KiteEngine owning this Track.

## ◆ getDirection()

unsigned int getDirection | ( |  | ) | const

pure virtual

Returns: The direction of the Track, either Katabatic::KbHorizontal or Katabatic::KbVertical.

Implemented in HorizontalTrack, and VerticalTrack.

Referenced by TrackFixedSegment::getDirection().

## ◆ getIndex()

RoutingPlane * getIndex | ( |  | ) | const

inline

Returns: The index of this Track in the RoutingPlane Track vector.

Referenced by Track::check(), Track::getNextTrack(), and Track::getPreviousTrack().

## ◆ getDepth()

unsigned int getDepth | ( |  | ) | const

Returns: The depth (as given by the RoutingGauge) of the Track's layer.

## ◆ getLayer()

Layer * getLayer | ( |  | ) | const

Returns: The `Layer` of the Track.

Referenced by Track::insert().

## ◆ getBlockageLayer()

Layer * getBlockageLayer | ( |  | ) | const

Returns: The associated blockage `Layer` to the Track's layer.

Referenced by Track::insert().

## ◆ getAxis()

DbU::Unit getAxis | ( |  | ) | const

inline

Returns: The Axis of the Track.

Referenced by Track::check(), NegociateWindow::createTrackSegment(), TrackFixedSegment::getAxis(), VerticalTrack::getPosition(), HorizontalTrack::getPosition(), Track::insert(), RoutingEvent::revalidate(), Manipulator::ripupPerpandiculars(), and SegmentFsm::SegmentFsm().

## ◆ getMin()

DbU::Unit getMin | ( |  | ) | const

inline

Returns: The minimal allowed coordinate of the Track.

Referenced by Manipulator::minimize().

## ◆ getMax()

DbU::Unit getMax | ( |  | ) | const

inline

Returns: The maximal allowed coordinate of the Track.

## ◆ getNextTrack()

Track * getNextTrack | ( |  | ) | const

Returns: The next Track in the `RoutingPlane` vector. That is the one with the axis immediatly superior.

Referenced by NegociateWindow::createTrackSegment(), RoutingEvent::revalidate(), and Manipulator::ripupPerpandiculars().

## ◆ getPreviousTrack()

Track * getPreviousTrack | ( |  | ) | const

Returns: The previous Track in the `RoutingPlane` vector. That is the one with the axis immediatly inferior.

Referenced by NegociateWindow::createTrackSegment().

## ◆ getSize()

size_t getSize | ( |  | ) | const

inline

Returns: The total number of TrackSegment in the Track.

Referenced by Track::getMaximalPosition(), and Track::getSegment().

## ◆ getPosition()

Point getPosition | ( | DbU::Unit | position | ) | const

pure virtual

Returns: the point at ``(position,getAxis()) for horizontal Track at or ``(getAxis(),position) for vertical Track.

Implemented in HorizontalTrack, and VerticalTrack.

## ◆ getSegment() [1/2]

TrackSegment * getSegment | ( | size_t | index | ) | const

Parameters

  index | The index of the TrackSegment.

Returns
  The TrackSegment at index. The result will be `NULL` in the follwing cases :
  - index is outside the sorted zone.
  - index points to a hole in the Track.
  - index is equal to Track::npos.

Referenced by SegmentFsm::conflictSolveByPlaceds(), NegociateWindow::createTrackSegment(), SegmentFsm::desaturate(), Manipulator::forceOverLocals(), Manipulator::forceToTrack(), Track::getSegment(), Manipulator::insertInTrack(), Manipulator::makeDogleg(), Manipulator::minimize(), and Manipulator::shrinkToTrack().

## ◆ getSegment() [2/2]

TrackSegment * getSegment | ( | DbU::Unit | position | ) | const

Parameters

  position | The position where to search.

Returns
  The TrackSegment whose starting point is immediatly inferior to position.

## ◆ getNext()

TrackSegment * getNext | ( | size_t & | index,
|  | Net * | net
| ) |  | const

Parameters

  index | Index of the starting TrackSegment.
  net | A `Net` to ignore.

Returns
  The next TrackSegment (`NULL` if not found).

Find, starting from TrackSegment at index the next TrackSegment ignoring TrackSegment from net. index is modified to point on the returned TrackSegment. If there's no next TrackSegment (`NULL`) then index is set to Track::npos.

Referenced by Track::expandFreeInterval(), TrackFixedSegment::getNext(), TrackSegment::getNext(), TrackElement::getNext(), and Track::getNextFixed().

## ◆ getPrevious()

TrackSegment * getPrevious | ( | size_t & | index,
|  | Net * | net
| ) |  | const

Parameters

  index | Index of the starting TrackSegment.
  net | A `Net` to ignore.

Returns
  The previous TrackSegment (`NULL` if not found).

find, starting from TrackSegment at index the previous TrackSegment ignoring TrackSegment from net. index is modified to point on the returned TrackSegment. If there's no previous TrackSegment (`NULL`) then index is set to Track::npos.

Referenced by Track::expandFreeInterval(), TrackFixedSegment::getPrevious(), TrackSegment::getPrevious(), and TrackElement::getPrevious().

## ◆ getNextFixed()

TrackSegment * getNextFixed | ( | size_t & | index | ) | const

Parameters

  index | Index of the starting TrackSegment.

Returns
  The first previous Fixed TrackSegment.

find, starting from TrackSegment at index the first previous with a Fixed attribute set. index is modified to point on the returned TrackSegment. If there's no previous TrackSegment (`NULL`) then index is set to Track::npos.

## ◆ find()

size_t find | ( | const TrackElement * | element | ) | const

Returns: the index of element inside the Track. If the element do not belongs to the Track, return Track::npos.

## ◆ getSourcePosition() [1/2]

DbU::Unit getSourcePosition | ( | vector< TrackElement *>::iterator | it | ) | const

Returns: The source position of TrackSegment pointed by iterator it. If it is equal to `end()` , returns zero.

## ◆ getMinimalPosition()

DbU::Unit getMinimalPosition | ( | size_t | index,
|  | unsigned int | state
| ) |  | const

Returns: Extract the minimal position from the interval at `index` in accordance to `state` hinting.

See also: Track::IndexState.

## ◆ getMaximalPosition()

DbU::Unit getMaximalPosition | ( | size_t | index,
|  | unsigned int | state
| ) |  | const

Returns: Extract the maximal position from the interval at `index` in accordance to `state` hinting.

See also: Track::IndexState.

Referenced by Track::expandFreeInterval().

## ◆ getFreeInterval()

Interval getFreeInterval | ( | DbU::Unit | position,
|  | Net * | net = `NULL`
| ) |  | const

Parameters

  position | where fo find a free interval.
  net | for which net to find the free interval. Returns: The longuest free interval enclosing position (may be empty).

## ◆ getOccupiedInterval()

Interval getOccupiedInterval | ( | size_t & | begin | ) | const

Parameters

  begin | index of one of the TrackElement set. May be modificated. Returns: the whole interval used by a set of overlaping TrackSegment.

As TrackElement from a same net can overlap, the interval of one of them do not give the full extend of the Track occupation at this point. This function looks for all overlaping segments and returns the merged interval. Additionnaly it sets `begin` to the index of the lowest TrackElement of the set.

Fig 4: Track::getOccuppiedInterval()

Referenced by Track::expandFreeInterval(), Track::getBeginIndex(), and Track::getOverlapBounds().

## ◆ expandFreeInterval()

Interval expandFreeInterval | ( | size_t & | begin,
|  | size_t & | end,
|  | unsigned int | state,
|  | Net * | net
| ) |  | const

Parameters

  begin | the lowest used TrackSegment.
  end | the highest used TrackSegment.
  state | tells how to interpret the `begin` & `end` indexes.
  net | the for wich we seek place. Returns: The longuest free interval between ``]begin,end[ .

Starting from the initial `[begin,end]` interval, expand the interval to encompass all free space or segments belonging to `net`. `state` may be used to compute the interval bounds from `begin` and `end` instead of directly using the returned `interval`.

Note
  ``]begin,end[ must define a free interval between two TrackSegment.

Referenced by Track::getFreeInterval().

## ◆ getBeginIndex()

void getBeginIndex | ( | DbU::Unit | position,
|  | size_t & | begin,
|  | unsigned int & | state
| ) |  | const

Parameters

  position | The position where to search.
  begin | Index of the immediatly inferior TrackElement.
  state | how to interpret the returned `begin`.

Return in `begin` the index of the TrackElement whose minimum is immediately below the requested `position` on the Track axis. The second returned parameter `state` is a set of flags to tell how the `begin` index has to be interpreted.

Flags for the `state` are:

- Track::BeginIsTrackMin : (implies `begin=0`) there is no TrackElement before `position`.
- Track::EndIsSegmentMin : The `begin` segment starts before `position`.
- Track::BeginIsSegmentMin : The `begin` segment starts before `position` and ends after.
- Track::EndIsSegmentMax : The `begin` segment starts before `position` and ends after.
- Track::BeginIsSegmentMax : The `begin` segment starts and ends before `position`.
- Track::EndIsNextSegmentMin : The `begin` segment starts and ends before `position`. So the maximum is given by the `minimum` of the next TrackElement.
- Track::EndIsTrackMax : There is no TrackElement after `position`.

Based on the previous flags, we build the `state` parameter:

- Track::BeforeFirstElement : the `position` is before the first TrackElement.
- Track::InsideElement : the `position` is inside a TrackElement.
- Track::OutsideElement : the `position` is in free zone between two TrackElements.
- Track::AfterLastElement : the position is after the end of the last element.
- Track::EmptyTrack : the track is still empty.

To separate flags relevant to begin and end informations, two masks are provideds:

- Track::BeginMask
- Track::EndMask

Fig 3: Track::getBeginIndex()

Reminder for myself: The Track::getBeginIndex() function relies on the STL `lower_bound()` function. `lower_bound()` finds the TrackElement immediately superior to `position` (shown on Figure 3 by the `LB` label in white on black).

The relation between the returned `begin` index and the position is given through the `state` parameter.

Referenced by Track::getFreeInterval(), Track::getOverlapBounds(), and Track::getSegment().

## ◆ getOverlapBounds()

void getOverlapBounds | ( | Interval | interval,
|  | size_t & | begin,
|  | size_t & | end
| ) |  | const

Parameters

  interval | the overlaping interval.
  begin | where to store the starting bound.
  end | where to store the ending bound.

find the range of TrackSegment intersecting interval. Note that when the interval lower bound crosses a set of overlaping intervals from the same `Net`, the interval at begin will crosses the lower bound but some following of the same `Net` may not.

Referenced by NegociateWindow::createTrackSegment(), and Track::getOverlapCost().

## ◆ getOverlapCost() [1/3]

TrackCost getOverlapCost | ( | Interval | interval,
|  | Net * | net,
|  | size_t | begin,
|  | size_t | end,
|  | unsigned int | flags
| ) |  | const

Parameters

  interval | the overlaping interval.
  net | a Net to ignore (null cost).
  begin | the starting bound.
  end | the ending bound.
  flags | passed to the overlap cost function.

Returns
  The cost of the overlap.

Compute the cost of the overlap of interval with the range ``[begin,end] of TrackSegment. Any TrackSegment belonging to net will be ignored.

Referenced by Track::getOverlapCost().

## ◆ getOverlapCost() [2/3]

TrackCost getOverlapCost | ( | Interval | interval,
|  | Net * | net,
|  | unsigned int | flags
| ) |  | const

Parameters

  interval | the overlaping interval.
  net | a Net to ignore (null cost).
  flags | passed to the overlap cost function.

Compute the overlap cost of interval with TrackSegment from the current Track, ignoring thoses belonging to net.

## ◆ getOverlapCost() [3/3]

TrackCost getOverlapCost | ( | TrackElement * | segment,
|  | unsigned int | flags
| ) |  | const

Parameters

  segment | under which to compute overlap cost.
  flags | passed to the overlap cost function.

Compute the overlap cost of `segment` with TrackSegment from the current Track (interval and net are deduced from `segment`).

## ◆ getTerminalWeight()

void getTerminalWeight | ( | Interval | interval,
|  | Net * | net,
|  | size_t & | count,
|  | unsigned int & | weight
| ) |  | const

Parameters

  interval | under which to compute terminal weight.
  net | a net to be ignored.
  count | incremented of the number of track markers under the `interval`.
  weight | incremented of the sum of the weight of the track markers under the `interval`.

Compute and return the sum of the weight of the track markers (see TrackMarker) under `interval` ignoring `net` (that is, for `net`).

Remark: The referenced variables `count` and `weight` are not reset to
  zero by this function. It is of the caller's responsability.

## ◆ getSourcePosition() [2/2]

DbU::Unit getSourcePosition | ( | size_t | index | ) | const

Returns: The source position of TrackSegment at index index. If index is equal to Track::npos, returns zero.

## ◆ check()

bool check | ( | unsigned int & | overlaps,
|  | const char * | message = `NULL`
| ) |  | const

Parameters

  overlaps | The number of overlaping segments.
  message | An iformative message, only printed if an error occurs.

Returns
  true if the Track contains no incoherencies.

Perform a complete Track check. Looks for the following incoherencies :

- TrackSegment do not refers this Track.
- TrackSegment is detached (TrackSegment::getTrack() is `NULL`).
- TrackSegment is hollow, this one is very unlikely as hollow TrackSegment are only created for the `lower_bound()`.
- `NULL` pointers (should never occurs, nevertheless...)
- Two consecutive TrackSegment from different `Net` must not overlap.
- For TrackSegment starting from the same position, the longuest must be first.

## ◆ invalidate()

void invalidate | ( |  | ) |

Inconditionnaly invalidate the Track, regardless if it has been modificated. The Track will be forced to be revalidated on closure of the current session.

## ◆ insert() [1/2]

void insert | ( | TrackElement * | segment | ) |

Adds segment to the Track. Must only be used inside a Session. They must appears after Track::doRemoval() and before Track::doReorder().

See also: Kite::Session.

## ◆ insert() [2/2]

void insert | ( | TrackMarker * | marker | ) |

Adds marker to the Track. Must only be used inside a Session.

See also: Kite::Session.

## ◆ setSegment()

void setSegment | ( | TrackElement * | element,
|  | size_t | index
| ) |  |

Directly affect the Track entry at position `index` to `element` (use with great care).

See also: Kite::Session.

Referenced by TrackSegment::swapTrack().

## ◆ doRemoval()

size_t doRemoval | ( |  | ) |

Returns: The number of removeds TrackSegment.

Suppress all the TrackSegment that have been withdraw from the Track. TrackSegment must be withdraw trough the TrackSegment::detach() method which sets their owning Track to `NULL` (the removal criterion). It uses the STL remove_if algorithm that put all the to be removed elements at the end of the vector.

See also: Kite::Session.

## ◆ doReorder()

void doReorder | ( |  | ) |

(Re)sort the TrackElement of the vector. Must be called after:

- Track::doRemoval() so no detached TrackSegment are presents.
- All calls to Track::insert(), as the newly inserted elements are put at the back of the vector.

See also: Kite::Session.

## Member Data Documentation

## ◆ npos

npos = (size_t)-1

static

A special index value (greatest integer) meaning that an index is invalid.

Referenced by Track::expandFreeInterval(), Track::find(), Track::getNext(), Track::getOccupiedInterval(), Track::getOverlapBounds(), Track::getOverlapCost(), Track::getPrevious(), Track::getSegment(), and Track::getSourcePosition().

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

- Track.h
- Track.cpp
- Track.dox