From 3a0a1f68fff444c0f3826861774cb0647d4b7e61 Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Wed, 26 Mar 2014 21:21:53 +0000 Subject: [PATCH] Simplify PBQP graph removeAdjEdgeId implementation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204857 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/PBQP/Graph.h | 22 ++++++++++------------ 1 file changed, 10 insertions(+), 12 deletions(-) diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index 030197f174f..e414c225518 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -67,16 +67,16 @@ namespace PBQP { return Idx; } - // If a swap is performed, returns the new EdgeId that must be - // updated, otherwise returns invalidEdgeId(). - EdgeId removeAdjEdgeId(AdjEdgeIdx Idx) { - EdgeId EIdToUpdate = Graph::invalidEdgeId(); - if (Idx < AdjEdgeIds.size() - 1) { - std::swap(AdjEdgeIds[Idx], AdjEdgeIds.back()); - EIdToUpdate = AdjEdgeIds[Idx]; - } + void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) { + // Swap-and-pop for fast removal. + // 1) Update the adj index of the edge currently at back(). + // 2) Swap Edge at Idx with back(). + // 3) pop_back() + // If Idx == size() - 1 then the updateAdjEdgeIdx and swap are + // redundant, but both operations are cheap. + G.getEdge(AdjEdgeIds.back()).updateAdjEdgeIdx(ThisNId, Idx); + std::swap(AdjEdgeIds[Idx], AdjEdgeIds.back()); AdjEdgeIds.pop_back(); - return EIdToUpdate; } const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; } @@ -138,9 +138,7 @@ namespace PBQP { assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() && "Edge not connected to NIds[NIdx]."); NodeEntry &N = G.getNode(NIds[NIdx]); - EdgeId EIdToUpdate = N.removeAdjEdgeId(ThisEdgeAdjIdxs[NIdx]); - if (EIdToUpdate != Graph::invalidEdgeId()) - G.getEdge(EIdToUpdate).updateAdjEdgeIdx(NIds[NIdx], ThisEdgeAdjIdxs[NIdx]); + N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]); ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx(); } -- 2.34.1