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