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
11#include "mcld/LD/LDSymbol.h"
12#include "mcld/LD/ResolveInfo.h"
13
14#include <algorithm>
15#include <cassert>
16
17namespace mcld {
18
19//===----------------------------------------------------------------------===//
20// Category
21SymbolCategory::Category::Type SymbolCategory::Category::categorize(
22    const ResolveInfo& pInfo) {
23  if (ResolveInfo::File == pInfo.type())
24    return Category::File;
25  if (ResolveInfo::Local == pInfo.binding())
26    return Category::Local;
27  if (ResolveInfo::Common == pInfo.desc())
28    return Category::Common;
29  if (ResolveInfo::Default == pInfo.visibility() ||
30      ResolveInfo::Protected == pInfo.visibility())
31    return Category::Dynamic;
32  return Category::Regular;
33}
34
35//===----------------------------------------------------------------------===//
36// SymbolCategory
37SymbolCategory::SymbolCategory() {
38  m_pFile = new Category(Category::File);
39  m_pLocal = new Category(Category::Local);
40  m_pLocalDyn = new Category(Category::LocalDyn);
41  m_pCommon = new Category(Category::Common);
42  m_pDynamic = new Category(Category::Dynamic);
43  m_pRegular = new Category(Category::Regular);
44
45  m_pFile->next = m_pLocal;
46  m_pLocal->next = m_pLocalDyn;
47  m_pLocalDyn->next = m_pCommon;
48  m_pCommon->next = m_pDynamic;
49  m_pDynamic->next = m_pRegular;
50
51  m_pRegular->prev = m_pDynamic;
52  m_pDynamic->prev = m_pCommon;
53  m_pCommon->prev = m_pLocalDyn;
54  m_pLocalDyn->prev = m_pLocal;
55  m_pLocal->prev = m_pFile;
56}
57
58SymbolCategory::~SymbolCategory() {
59  Category* current = m_pFile;
60  while (current != NULL) {
61    Category* tmp = current;
62    current = current->next;
63    delete tmp;
64  }
65}
66
67SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol, Category::Type pTarget) {
68  Category* current = m_pRegular;
69  m_OutputSymbols.push_back(&pSymbol);
70
71  // use non-stable bubble sort to arrange the order of symbols.
72  while (current != NULL) {
73    if (current->type == pTarget) {
74      current->end++;
75      break;
76    } else {
77      if (!current->empty()) {
78        std::swap(m_OutputSymbols[current->begin],
79                  m_OutputSymbols[current->end]);
80      }
81      current->end++;
82      current->begin++;
83      current = current->prev;
84    }
85  }
86  return *this;
87}
88
89SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol) {
90  assert(pSymbol.resolveInfo() != NULL);
91  return add(pSymbol, Category::categorize(*pSymbol.resolveInfo()));
92}
93
94SymbolCategory& SymbolCategory::forceLocal(LDSymbol& pSymbol) {
95  return add(pSymbol, Category::Local);
96}
97
98SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol,
99                                        Category::Type pSource,
100                                        Category::Type pTarget) {
101  int distance = pTarget - pSource;
102  if (distance == 0) {
103    // in the same category, do not need to re-arrange
104    return *this;
105  }
106
107  // source and target are not in the same category
108  // find the category of source
109  Category* current = m_pFile;
110  while (current != NULL) {
111    if (pSource == current->type)
112      break;
113    current = current->next;
114  }
115
116  assert(current != NULL);
117  size_t pos = 0;
118  if (!current->empty()) {
119    // find the position of source
120    pos = current->begin;
121    while (pos != current->end) {
122      if (m_OutputSymbols[pos] == &pSymbol)
123        break;
124      ++pos;
125    }
126  }
127  // FIXME: Try to search the symbol explicitly, if symbol is not in the given
128  // source category. Or we need to add some logics like shouldForceLocal() in
129  // SymbolCategory::Category::categorize().
130  if (current->end == pos || current->empty()) {
131    current = m_pFile;
132    do {
133      pos = current->begin;
134      while (pos != current->end) {
135        if (m_OutputSymbols[pos] == &pSymbol) {
136          distance = pTarget - current->type;
137          break;
138        }
139        ++pos;
140      }
141      if (pos != current->end)
142        break;
143      current = current->next;
144    } while (current != NULL);
145    assert(current != NULL);
146  }
147
148  // The distance is positive. It means we should bubble sort downward.
149  if (distance > 0) {
150    // downward
151    size_t rear;
152    do {
153      if (current->type == pTarget) {
154        break;
155      } else {
156        assert(!current->isLast() && "target category is wrong.");
157        rear = current->end - 1;
158        std::swap(m_OutputSymbols[pos], m_OutputSymbols[rear]);
159        pos = rear;
160        current->next->begin--;
161        current->end--;
162      }
163      current = current->next;
164    } while (current != NULL);
165
166    return *this;
167  }  // downward
168
169  // The distance is negative. It means we should bubble sort upward.
170  if (distance < 0) {
171    // upward
172    do {
173      if (current->type == pTarget) {
174        break;
175      } else {
176        assert(!current->isFirst() && "target category is wrong.");
177        std::swap(m_OutputSymbols[current->begin], m_OutputSymbols[pos]);
178        pos = current->begin;
179        current->begin++;
180        current->prev->end++;
181      }
182      current = current->prev;
183    } while (current != NULL);
184
185    return *this;
186  }  // upward
187  return *this;
188}
189
190SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol,
191                                        const ResolveInfo& pSourceInfo) {
192  assert(pSymbol.resolveInfo() != NULL);
193  return arrange(pSymbol,
194                 Category::categorize(pSourceInfo),
195                 Category::categorize(*pSymbol.resolveInfo()));
196}
197
198SymbolCategory& SymbolCategory::changeCommonsToGlobal() {
199  // Change Common to Dynamic/Regular
200  while (!emptyCommons()) {
201    size_t pos = m_pCommon->end - 1;
202    switch (Category::categorize(*(m_OutputSymbols[pos]->resolveInfo()))) {
203      case Category::Dynamic:
204        m_pCommon->end--;
205        m_pDynamic->begin--;
206        break;
207      case Category::Regular:
208        std::swap(m_OutputSymbols[pos], m_OutputSymbols[m_pDynamic->end - 1]);
209        m_pCommon->end--;
210        m_pDynamic->begin--;
211        m_pDynamic->end--;
212        m_pRegular->begin--;
213        break;
214      default:
215        assert(0);
216        break;
217    }
218  }
219  return *this;
220}
221
222SymbolCategory& SymbolCategory::changeToDynamic(LDSymbol& pSymbol) {
223  assert(pSymbol.resolveInfo() != NULL);
224  return arrange(pSymbol,
225                 Category::categorize(*pSymbol.resolveInfo()),
226                 Category::LocalDyn);
227}
228
229size_t SymbolCategory::numOfSymbols() const {
230  return m_OutputSymbols.size();
231}
232
233size_t SymbolCategory::numOfFiles() const {
234  return m_pFile->size();
235}
236
237size_t SymbolCategory::numOfLocals() const {
238  return m_pLocal->size();
239}
240
241size_t SymbolCategory::numOfLocalDyns() const {
242  return m_pLocalDyn->size();
243}
244
245size_t SymbolCategory::numOfCommons() const {
246  return m_pCommon->size();
247}
248
249size_t SymbolCategory::numOfDynamics() const {
250  return m_pDynamic->size();
251}
252
253size_t SymbolCategory::numOfRegulars() const {
254  return m_pRegular->size();
255}
256
257bool SymbolCategory::empty() const {
258  return m_OutputSymbols.empty();
259}
260
261bool SymbolCategory::emptyFiles() const {
262  return m_pFile->empty();
263}
264
265bool SymbolCategory::emptyLocals() const {
266  return m_pLocal->empty();
267}
268
269bool SymbolCategory::emptyLocalDyns() const {
270  return m_pLocalDyn->empty();
271}
272
273bool SymbolCategory::emptyCommons() const {
274  return m_pCommon->empty();
275}
276
277bool SymbolCategory::emptyDynamics() const {
278  return m_pDynamic->empty();
279}
280
281bool SymbolCategory::emptyRegulars() const {
282  return m_pRegular->empty();
283}
284
285SymbolCategory::iterator SymbolCategory::begin() {
286  return m_OutputSymbols.begin();
287}
288
289SymbolCategory::iterator SymbolCategory::end() {
290  return m_OutputSymbols.end();
291}
292
293SymbolCategory::const_iterator SymbolCategory::begin() const {
294  return m_OutputSymbols.begin();
295}
296
297SymbolCategory::const_iterator SymbolCategory::end() const {
298  return m_OutputSymbols.end();
299}
300
301SymbolCategory::iterator SymbolCategory::fileBegin() {
302  return m_OutputSymbols.begin();
303}
304
305SymbolCategory::iterator SymbolCategory::fileEnd() {
306  iterator iter = fileBegin();
307  iter += m_pFile->size();
308  return iter;
309}
310
311SymbolCategory::const_iterator SymbolCategory::fileBegin() const {
312  return m_OutputSymbols.begin();
313}
314
315SymbolCategory::const_iterator SymbolCategory::fileEnd() const {
316  const_iterator iter = fileBegin();
317  iter += m_pFile->size();
318  return iter;
319}
320
321SymbolCategory::iterator SymbolCategory::localBegin() {
322  return fileEnd();
323}
324
325SymbolCategory::iterator SymbolCategory::localEnd() {
326  iterator iter = localBegin();
327  iter += m_pLocal->size();
328  return iter;
329}
330
331SymbolCategory::const_iterator SymbolCategory::localBegin() const {
332  return fileEnd();
333}
334
335SymbolCategory::const_iterator SymbolCategory::localEnd() const {
336  const_iterator iter = localBegin();
337  iter += m_pLocal->size();
338  return iter;
339}
340
341SymbolCategory::iterator SymbolCategory::localDynBegin() {
342  return localEnd();
343}
344
345SymbolCategory::iterator SymbolCategory::localDynEnd() {
346  iterator iter = localDynBegin();
347  iter += m_pLocalDyn->size();
348  return iter;
349}
350
351SymbolCategory::const_iterator SymbolCategory::localDynBegin() const {
352  return localEnd();
353}
354
355SymbolCategory::const_iterator SymbolCategory::localDynEnd() const {
356  const_iterator iter = localDynBegin();
357  iter += m_pLocalDyn->size();
358  return iter;
359}
360
361SymbolCategory::iterator SymbolCategory::commonBegin() {
362  return localDynEnd();
363}
364
365SymbolCategory::iterator SymbolCategory::commonEnd() {
366  iterator iter = commonBegin();
367  iter += m_pCommon->size();
368  return iter;
369}
370
371SymbolCategory::const_iterator SymbolCategory::commonBegin() const {
372  return localDynEnd();
373}
374
375SymbolCategory::const_iterator SymbolCategory::commonEnd() const {
376  const_iterator iter = commonBegin();
377  iter += m_pCommon->size();
378  return iter;
379}
380
381SymbolCategory::iterator SymbolCategory::dynamicBegin() {
382  return commonEnd();
383}
384
385SymbolCategory::iterator SymbolCategory::dynamicEnd() {
386  iterator iter = dynamicBegin();
387  iter += m_pDynamic->size();
388  return iter;
389}
390
391SymbolCategory::const_iterator SymbolCategory::dynamicBegin() const {
392  return commonEnd();
393}
394
395SymbolCategory::const_iterator SymbolCategory::dynamicEnd() const {
396  const_iterator iter = dynamicBegin();
397  iter += m_pDynamic->size();
398  return iter;
399}
400
401SymbolCategory::iterator SymbolCategory::regularBegin() {
402  return dynamicEnd();
403}
404
405SymbolCategory::iterator SymbolCategory::regularEnd() {
406  return m_OutputSymbols.end();
407}
408
409SymbolCategory::const_iterator SymbolCategory::regularBegin() const {
410  return dynamicEnd();
411}
412
413SymbolCategory::const_iterator SymbolCategory::regularEnd() const {
414  return m_OutputSymbols.end();
415}
416
417}  // namespace mcld
418