Program Listing for File HSPrefixTree.h

↰ Return to documentation for file (src/sta/HSPrefixTree.h)

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

#include "HSGraphClock.h"
#include "HSStaBase.h"
#include "HSTimingEdge.h"

using std::vector;

namespace HSFullTiming {

class HSPartitionFlow;
class HSTimingEdge;
class HSTimingLocalData;

// prefix node
struct pfxtNode {
  int nodeId;
  int clkId;
  float slack;
  int hop;
  int fromEdgeId;
  int toEdgeId;
  int parentId;
  bool poped;
};

class HSPrefixTree {
 public:
  HSPrefixTree(int k, const HSPartitionFlow *pFlow,
               const HSTimingLocalData *oneLocal);
  ~HSPrefixTree();

  // 初始化堆，把所有与时钟相连的起始边作为偏离边对应的前缀树节点压入堆中，然后把slack最小的节点弹出，把它的偏离结果再压入堆中
  void initHeap();
  // 向堆中加入一个节点
  void pushPfxtNode(pfxtNode node);
  // 从堆顶弹出slack最小的节点
  pfxtNode *popPfxtNode();
  // 对一个前缀树节点进行偏移，并把偏移出的节点都压入堆中
  void spur(pfxtNode *node);
  // 重新建堆
  void reBuildHeap();
  // 导出一条路径
  void dumpOnePath(pfxtNode *node);
  // 提取前K条路径
  void extractTopkPaths();
  // 打印前K条路径到控制台
  void printTopkPaths();
  // 用于获取一个nodeId;
  long long getNodeId();
  // 给出id，让它返回对应pfxtNode
  pfxtNode getNodeById(long long nodeId);
  // 给出id，让它返回对应的slackData
  slackData &getSlackData(int clkId, int edgeId);
  // 获取提取的前K条路径
  vector<HSStaBase::timingpath> &getTopkPaths();

 private:
  // Top K
  const int k;
  // 用堆存储前缀树节点的指针
  vector<pfxtNode *> minHeap;
  // 存储前缀树节点
  vector<pfxtNode> pfxtNodes;
  // 存储导出的timingpath
  vector<HSStaBase::timingpath> topkPaths;
  // 用于通过NodeId访问node
  map<long long, int> id2index;
  // 用于访问电路图中边的连接关系
  const HSPartitionFlow *pFlow;
  // 用于访问slackData
  const vector<HSTimingEdge *> &m_timingEdgeAll;
  // 用于访问oneLocal
  const HSTimingLocalData *oneLocal;
  // 节点计数，用于设置nodeId
  long long nodeCount = 0;
  // 用于给定预分配的空间大小
  int numReserve;
};
}  // namespace HSFullTiming