1f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines//===- ListDigraph.cpp ----------------------------------------------------===// 2f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// 3f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// The MCLinker Project 4f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// 5f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// This file is distributed under the University of Illinois Open Source 6f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// License. See LICENSE.TXT for details. 7f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// 8f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines//===----------------------------------------------------------------------===// 9f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#include <mcld/ADT/GraphLite/ListDigraph.h> 10f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 11f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesusing namespace mcld::graph; 12f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 13f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines//===----------------------------------------------------------------------===// 14f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// ListDigraph::Node 15f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines//===----------------------------------------------------------------------===// 16f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen HinesListDigraph::Node::Node() 17f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines : prev(NULL), next(NULL), first_in(NULL), first_out(NULL) { 18f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 19f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 20f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines//===----------------------------------------------------------------------===// 21f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// ListDigraph::Arc 22f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines//===----------------------------------------------------------------------===// 23f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen HinesListDigraph::Arc::Arc() 24f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines : target(NULL), source(NULL), 25f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines prev_in(NULL), next_in(NULL), prev_out(NULL), next_out(NULL) { 26f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 27f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 28f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines//===----------------------------------------------------------------------===// 29f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines// ListDigraph 30f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines//===----------------------------------------------------------------------===// 31f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen HinesListDigraph::ListDigraph() 32f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines : m_pNodeHead(NULL), m_pFreeNodeHead(NULL), m_pFreeArcHead(NULL), 33f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_NodeList(32), m_ArcList(32) { 34f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 35f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 36f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 37f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen HinesListDigraph::Node* ListDigraph::addNode() 38f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 39f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 1. find an available free node 40f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines Node* result = NULL; 41f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL == m_pFreeNodeHead) { 42f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result = m_NodeList.allocate(); 43f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines new (result) Node(); 44f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 45f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines else { 46f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result = m_pFreeNodeHead; 47f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pFreeNodeHead = m_pFreeNodeHead->next; 48f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 49f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 50f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 2. set up linkages 51f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result->prev = NULL; 52f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result->next = m_pNodeHead; 53f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 54f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 3. reset head node 55f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != m_pNodeHead) { 56f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pNodeHead->prev = result; 57f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 58f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pNodeHead = result; 59f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 60f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines return result; 61f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 62f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 63f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 64f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen HinesListDigraph::Arc* ListDigraph::addArc(Node& pU, Node& pV) 65f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 66f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 1. find an available free arc 67f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines Arc* result = NULL; 68f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL == m_pFreeArcHead) { 69f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result = m_ArcList.allocate(); 70f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines new (result) Arc(); 71f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 72f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines else { 73f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result = m_pFreeArcHead; 74f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pFreeArcHead = m_pFreeArcHead->next_in; 75f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 76f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 77f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 2. set up arc 78f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result->source = &pU; 79f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result->target = &pV; 80f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 81f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 3. set up fan-out linked list 82f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result->next_out = pU.first_out; 83f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != pU.first_out) { 84f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pU.first_out->prev_out = result; 85f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 86f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pU.first_out = result; 87f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 88f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 4. set up fan-in linked list 89f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines result->next_in = pV.first_in; 90f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != pV.first_in) { 91f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pV.first_in->prev_in = result; 92f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 93f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pV.first_in = result; 94f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 95f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines return result; 96f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 97f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 98f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesvoid ListDigraph::erase(ListDigraph::Node& pNode) 99f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 100f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 1. connect previous node and next node. 101f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != pNode.next) { 102f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pNode.next->prev = pNode.prev; 103f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 104f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 105f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != pNode.prev) { 106f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pNode.prev->next = pNode.next; 107f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 108f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines else { // pNode.prev is NULL => pNode is the head 109f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pNodeHead = pNode.next; 110f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 111f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 112f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 2. remove all fan-in arcs 113f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines Arc* fan_in = pNode.first_in; 114f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines while(NULL != fan_in) { 115f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines Arc* next_in = fan_in->next_in; 116f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines erase(*fan_in); 117f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines fan_in = next_in; 118f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 119f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 120f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 3. remove all fan-out arcs 121f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines Arc* fan_out = pNode.first_out; 122f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines while(NULL != fan_out) { 123f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines Arc* next_out = fan_out->next_out; 124f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines erase(*fan_out); 125f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines fan_out = next_out; 126f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 127f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 128f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 4. put pNode in the free node list 129f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pNode.next = m_pFreeNodeHead; 130f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pNode.prev = NULL; 131f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != m_pFreeNodeHead) 132f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pFreeNodeHead->prev = &pNode; 133f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pFreeNodeHead = &pNode; 134f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 135f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 136f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 137f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesvoid ListDigraph::erase(ListDigraph::Arc& pArc) 138f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 139f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 1. remove from the fan-out list 140f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != pArc.prev_out) { 141f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pArc.prev_out->next_out = pArc.next_out; 142f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 143f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines else { // pArc.prev_out is NULL => pArc is the first_out of the source 144f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pArc.source->first_out = pArc.next_out; 145f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 146f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 147f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != pArc.next_out) { 148f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pArc.next_out->prev_out = pArc.prev_out; 149f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 150f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 151f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 2. remove from the fan-in list 152f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != pArc.prev_in) { 153f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pArc.prev_in->next_in = pArc.next_in; 154f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 155f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines else { 156f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pArc.target->first_in = pArc.next_in; 157f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 158f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 159f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (NULL != pArc.next_in) { 160f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pArc.next_in->prev_in = pArc.prev_in; 161f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 162f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 163f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // 3. put pArc in the free arc list 164f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines // Use fan-in links to chain the free list 165f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines pArc.next_in = m_pFreeArcHead; 166f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pFreeArcHead = &pArc; 167f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 168f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 169f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 170f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesvoid ListDigraph::clear() 171f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 172f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pNodeHead = NULL; 173f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pFreeNodeHead = NULL; 174f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_pFreeArcHead = NULL; 175f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_NodeList.clear(); 176f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines m_ArcList.clear(); 177f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 178f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 179