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