//===- ListDigraph.cpp ----------------------------------------------------===//
//
// The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include <mcld/ADT/GraphLite/ListDigraph.h>
using namespace mcld::graph;
//===----------------------------------------------------------------------===//
// ListDigraph::Node
//===----------------------------------------------------------------------===//
ListDigraph::Node::Node()
: prev(NULL), next(NULL), first_in(NULL), first_out(NULL) {
}
//===----------------------------------------------------------------------===//
// ListDigraph::Arc
//===----------------------------------------------------------------------===//
ListDigraph::Arc::Arc()
: target(NULL), source(NULL),
prev_in(NULL), next_in(NULL), prev_out(NULL), next_out(NULL) {
}
//===----------------------------------------------------------------------===//
// ListDigraph
//===----------------------------------------------------------------------===//
ListDigraph::ListDigraph()
: m_pNodeHead(NULL), m_pFreeNodeHead(NULL), m_pFreeArcHead(NULL),
m_NodeList(32), m_ArcList(32) {
}
ListDigraph::Node* ListDigraph::addNode()
{
// 1. find an available free node
Node* result = NULL;
if (NULL == m_pFreeNodeHead) {
result = m_NodeList.allocate();
new (result) Node();
}
else {
result = m_pFreeNodeHead;
m_pFreeNodeHead = m_pFreeNodeHead->next;
}
// 2. set up linkages
result->prev = NULL;
result->next = m_pNodeHead;
// 3. reset head node
if (NULL != m_pNodeHead) {
m_pNodeHead->prev = result;
}
m_pNodeHead = result;
return result;
}
ListDigraph::Arc* ListDigraph::addArc(Node& pU, Node& pV)
{
// 1. find an available free arc
Arc* result = NULL;
if (NULL == m_pFreeArcHead) {
result = m_ArcList.allocate();
new (result) Arc();
}
else {
result = m_pFreeArcHead;
m_pFreeArcHead = m_pFreeArcHead->next_in;
}
// 2. set up arc
result->source = &pU;
result->target = &pV;
// 3. set up fan-out linked list
result->next_out = pU.first_out;
if (NULL != pU.first_out) {
pU.first_out->prev_out = result;
}
pU.first_out = result;
// 4. set up fan-in linked list
result->next_in = pV.first_in;
if (NULL != pV.first_in) {
pV.first_in->prev_in = result;
}
pV.first_in = result;
return result;
}
void ListDigraph::erase(ListDigraph::Node& pNode)
{
// 1. connect previous node and next node.
if (NULL != pNode.next) {
pNode.next->prev = pNode.prev;
}
if (NULL != pNode.prev) {
pNode.prev->next = pNode.next;
}
else { // pNode.prev is NULL => pNode is the head
m_pNodeHead = pNode.next;
}
// 2. remove all fan-in arcs
Arc* fan_in = pNode.first_in;
while(NULL != fan_in) {
Arc* next_in = fan_in->next_in;
erase(*fan_in);
fan_in = next_in;
}
// 3. remove all fan-out arcs
Arc* fan_out = pNode.first_out;
while(NULL != fan_out) {
Arc* next_out = fan_out->next_out;
erase(*fan_out);
fan_out = next_out;
}
// 4. put pNode in the free node list
pNode.next = m_pFreeNodeHead;
pNode.prev = NULL;
if (NULL != m_pFreeNodeHead)
m_pFreeNodeHead->prev = &pNode;
m_pFreeNodeHead = &pNode;
}
void ListDigraph::erase(ListDigraph::Arc& pArc)
{
// 1. remove from the fan-out list
if (NULL != pArc.prev_out) {
pArc.prev_out->next_out = pArc.next_out;
}
else { // pArc.prev_out is NULL => pArc is the first_out of the source
pArc.source->first_out = pArc.next_out;
}
if (NULL != pArc.next_out) {
pArc.next_out->prev_out = pArc.prev_out;
}
// 2. remove from the fan-in list
if (NULL != pArc.prev_in) {
pArc.prev_in->next_in = pArc.next_in;
}
else {
pArc.target->first_in = pArc.next_in;
}
if (NULL != pArc.next_in) {
pArc.next_in->prev_in = pArc.prev_in;
}
// 3. put pArc in the free arc list
// Use fan-in links to chain the free list
pArc.next_in = m_pFreeArcHead;
m_pFreeArcHead = &pArc;
}
void ListDigraph::clear()
{
m_pNodeHead = NULL;
m_pFreeNodeHead = NULL;
m_pFreeArcHead = NULL;
m_NodeList.clear();
m_ArcList.clear();
}