lib/ADT/GraphLite/ListDigraph.cpp

//===- 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();
}