1//===- SymbolCategory.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/MC/SymbolCategory.h>
10#include <mcld/LD/LDSymbol.h>
11#include <mcld/LD/ResolveInfo.h>
12#include <algorithm>
13
14using namespace mcld;
15
16//===----------------------------------------------------------------------===//
17// Category
18SymbolCategory::Category::Type
19SymbolCategory::Category::categorize(const ResolveInfo& pInfo)
20{
21  if (ResolveInfo::File == pInfo.type())
22    return Category::File;
23  if (ResolveInfo::Local == pInfo.binding())
24    return Category::Local;
25  if (ResolveInfo::Common == pInfo.desc())
26    return Category::Common;
27  if (ResolveInfo::Weak == pInfo.binding())
28    return Category::Weak;
29  return Category::Global;
30}
31
32//===----------------------------------------------------------------------===//
33// SymbolCategory
34SymbolCategory::SymbolCategory()
35{
36  m_pFile   = new Category(Category::File);
37  m_pLocal  = new Category(Category::Local);
38  m_pCommon = new Category(Category::Common);
39  m_pWeak   = new Category(Category::Weak);
40  m_pGlobal = new Category(Category::Global);
41
42  m_pFile->next   = m_pLocal;
43  m_pLocal->next  = m_pCommon;
44  m_pCommon->next = m_pWeak;
45  m_pWeak->next   = m_pGlobal;
46
47  m_pGlobal->prev = m_pWeak;
48  m_pWeak->prev   = m_pCommon;
49  m_pCommon->prev = m_pLocal;
50  m_pLocal->prev   = m_pFile;
51}
52
53SymbolCategory::~SymbolCategory()
54{
55  Category* current = m_pFile;
56  while (NULL != current) {
57    Category* tmp = current;
58    current = current->next;
59    delete tmp;
60  }
61}
62
63SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol)
64{
65  m_OutputSymbols.push_back(&pSymbol);
66
67  assert(NULL != pSymbol.resolveInfo());
68  Category::Type target = Category::categorize(*pSymbol.resolveInfo());
69
70  Category* current = m_pGlobal;
71
72  // use non-stable bubble sort to arrange the order of symbols.
73  while (NULL != current) {
74    if (current->type == target) {
75      current->end++;
76      break;
77    }
78    else {
79      if (!current->empty()) {
80        std::swap(m_OutputSymbols[current->begin],
81                  m_OutputSymbols[current->end]);
82      }
83      current->end++;
84      current->begin++;
85      current = current->prev;
86    }
87  }
88  return *this;
89}
90
91SymbolCategory& SymbolCategory::forceLocal(LDSymbol& pSymbol)
92{
93  m_OutputSymbols.insert(localEnd(), &pSymbol);
94  m_pLocal->end++;
95  m_pCommon->begin++;
96  m_pCommon->end++;
97  m_pWeak->begin++;
98  m_pWeak->end++;
99  m_pGlobal->begin++;
100  m_pGlobal->end++;
101
102  return *this;
103}
104
105SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol, const ResolveInfo& pSourceInfo)
106{
107  assert(NULL != pSymbol.resolveInfo());
108  Category::Type source = Category::categorize(pSourceInfo);
109  Category::Type target = Category::categorize(*pSymbol.resolveInfo());
110
111  int distance = target - source;
112  if (0 == distance) {
113    // in the same category, do not need to re-arrange
114    return *this;
115  }
116
117  // source and target are not in the same category
118  // find the category of source
119  Category* current = m_pFile;
120  while(NULL != current) {
121    if (source == current->type)
122      break;
123    current = current->next;
124  }
125
126  assert(NULL != current);
127  assert(!current->empty());
128
129  // find the position of source
130  size_t pos = current->begin;
131  while (pos != current->end) {
132    if (m_OutputSymbols[pos] == &pSymbol)
133      break;
134    ++pos;
135  }
136
137  assert(current->end != pos);
138
139  // The distance is positive. It means we should bubble sort downward.
140  if (distance > 0) {
141    // downward
142    size_t rear;
143    do {
144      if (current->type == target) {
145        break;
146      }
147      else {
148        assert(!current->isLast() && "target category is wrong.");
149        rear = current->end - 1;
150        std::swap(m_OutputSymbols[pos], m_OutputSymbols[rear]);
151        pos = rear;
152        current->next->begin--;
153        current->end--;
154      }
155      current = current->next;
156    } while(NULL != current);
157
158    return *this;
159  } // downward
160
161  // The distance is negative. It means we should bubble sort upward.
162  if (distance < 0) {
163
164    // upward
165    do {
166      if (current->type == target) {
167        break;
168      }
169      else {
170        assert(!current->isFirst() && "target category is wrong.");
171        std::swap(m_OutputSymbols[current->begin], m_OutputSymbols[pos]);
172        pos = current->begin;
173        current->begin++;
174        current->prev->end++;
175      }
176      current = current->prev;
177    } while(NULL != current);
178
179    return *this;
180  } // upward
181  return *this;
182}
183
184SymbolCategory& SymbolCategory::changeCommonsToGlobal()
185{
186  if (emptyCommons())
187    return *this;
188
189  size_t com_rear = m_pCommon->end - 1;
190  size_t com_front = m_pCommon->begin;
191  size_t weak_rear = m_pWeak->end - 1;
192  size_t weak_size = m_pWeak->end - m_pWeak->begin;
193  for (size_t sym = com_rear; sym >= com_front; --sym) {
194    std::swap(m_OutputSymbols[weak_rear], m_OutputSymbols[sym]);
195    --weak_rear;
196  }
197
198  m_pWeak->begin = m_pCommon->begin;
199  m_pWeak->end = m_pCommon->begin + weak_size;
200  m_pGlobal->begin = m_pWeak->end;
201  m_pCommon->begin = m_pCommon->end = m_pWeak->begin;
202
203  return *this;
204}
205
206size_t SymbolCategory::numOfSymbols() const
207{
208  return m_OutputSymbols.size();
209}
210
211size_t SymbolCategory::numOfLocals() const
212{
213  return (m_pFile->size() + m_pLocal->size());
214}
215
216size_t SymbolCategory::numOfCommons() const
217{
218  return m_pCommon->size();
219}
220
221size_t SymbolCategory::numOfRegulars() const
222{
223  return (m_pWeak->size() + m_pGlobal->size());
224}
225
226bool SymbolCategory::empty() const
227{
228  return (emptyLocals() &&
229          emptyCommons() &&
230          emptyRegulars());
231}
232
233bool SymbolCategory::emptyLocals() const
234{
235  return (m_pFile->empty() && m_pLocal->empty());
236}
237
238bool SymbolCategory::emptyCommons() const
239{
240  return m_pCommon->empty();
241}
242
243bool SymbolCategory::emptyRegulars() const
244{
245  return (m_pWeak->empty() && m_pGlobal->empty());
246}
247
248SymbolCategory::iterator SymbolCategory::begin()
249{
250  return m_OutputSymbols.begin();
251}
252
253SymbolCategory::iterator SymbolCategory::end()
254{
255  return m_OutputSymbols.end();
256}
257
258SymbolCategory::const_iterator SymbolCategory::begin() const
259{
260  return m_OutputSymbols.begin();
261}
262
263SymbolCategory::const_iterator SymbolCategory::end() const
264{
265  return m_OutputSymbols.end();
266}
267
268SymbolCategory::iterator SymbolCategory::localBegin()
269{
270  return m_OutputSymbols.begin();
271}
272
273SymbolCategory::iterator SymbolCategory::localEnd()
274{
275  iterator iter = m_OutputSymbols.begin();
276  iter += m_pFile->size();
277  iter += m_pLocal->size();
278  return iter;
279}
280
281SymbolCategory::const_iterator SymbolCategory::localBegin() const
282{
283  return m_OutputSymbols.begin();
284}
285
286SymbolCategory::const_iterator SymbolCategory::localEnd() const
287{
288  const_iterator iter = m_OutputSymbols.begin();
289  iter += m_pFile->size();
290  iter += m_pLocal->size();
291  return iter;
292}
293
294SymbolCategory::iterator SymbolCategory::commonBegin()
295{
296  return localEnd();
297}
298
299SymbolCategory::iterator SymbolCategory::commonEnd()
300{
301  iterator iter = localEnd();
302  iter += m_pCommon->size();
303  return iter;
304}
305
306SymbolCategory::const_iterator SymbolCategory::commonBegin() const
307{
308  return localEnd();
309}
310
311SymbolCategory::const_iterator SymbolCategory::commonEnd() const
312{
313  const_iterator iter = localEnd();
314  iter += m_pCommon->size();
315  return iter;
316}
317
318SymbolCategory::iterator SymbolCategory::regularBegin()
319{
320  return commonEnd();
321}
322
323SymbolCategory::iterator SymbolCategory::regularEnd()
324{
325  return m_OutputSymbols.end();
326}
327
328SymbolCategory::const_iterator SymbolCategory::regularBegin() const
329{
330  return commonEnd();
331}
332
333SymbolCategory::const_iterator SymbolCategory::regularEnd() const
334{
335  return m_OutputSymbols.end();
336}
337
338