| //===- SymbolCategory.cpp -------------------------------------------------===// |
| // |
| // The MCLinker Project |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| #include <mcld/MC/SymbolCategory.h> |
| #include <mcld/LD/LDSymbol.h> |
| #include <mcld/LD/ResolveInfo.h> |
| #include <algorithm> |
| #include <cassert> |
| |
| using namespace mcld; |
| |
| //===----------------------------------------------------------------------===// |
| // Category |
| SymbolCategory::Category::Type |
| SymbolCategory::Category::categorize(const ResolveInfo& pInfo) |
| { |
| if (ResolveInfo::File == pInfo.type()) |
| return Category::File; |
| if (ResolveInfo::Local == pInfo.binding()) |
| return Category::Local; |
| if (ResolveInfo::Common == pInfo.desc()) |
| return Category::Common; |
| if (ResolveInfo::Default == pInfo.visibility() || |
| ResolveInfo::Protected == pInfo.visibility()) |
| return Category::Dynamic; |
| return Category::Regular; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // SymbolCategory |
| SymbolCategory::SymbolCategory() |
| { |
| m_pFile = new Category(Category::File); |
| m_pLocal = new Category(Category::Local); |
| m_pLocalDyn = new Category(Category::LocalDyn); |
| m_pCommon = new Category(Category::Common); |
| m_pDynamic = new Category(Category::Dynamic); |
| m_pRegular = new Category(Category::Regular); |
| |
| m_pFile->next = m_pLocal; |
| m_pLocal->next = m_pLocalDyn; |
| m_pLocalDyn->next = m_pCommon; |
| m_pCommon->next = m_pDynamic; |
| m_pDynamic->next = m_pRegular; |
| |
| m_pRegular->prev = m_pDynamic; |
| m_pDynamic->prev = m_pCommon; |
| m_pCommon->prev = m_pLocalDyn; |
| m_pLocalDyn->prev = m_pLocal; |
| m_pLocal->prev = m_pFile; |
| } |
| |
| SymbolCategory::~SymbolCategory() |
| { |
| Category* current = m_pFile; |
| while (NULL != current) { |
| Category* tmp = current; |
| current = current->next; |
| delete tmp; |
| } |
| } |
| |
| SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol, Category::Type pTarget) |
| { |
| Category* current = m_pRegular; |
| m_OutputSymbols.push_back(&pSymbol); |
| |
| // use non-stable bubble sort to arrange the order of symbols. |
| while (NULL != current) { |
| if (current->type == pTarget) { |
| current->end++; |
| break; |
| } |
| else { |
| if (!current->empty()) { |
| std::swap(m_OutputSymbols[current->begin], |
| m_OutputSymbols[current->end]); |
| } |
| current->end++; |
| current->begin++; |
| current = current->prev; |
| } |
| } |
| return *this; |
| } |
| |
| SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol) |
| { |
| assert(NULL != pSymbol.resolveInfo()); |
| return add(pSymbol, Category::categorize(*pSymbol.resolveInfo())); |
| } |
| |
| SymbolCategory& SymbolCategory::forceLocal(LDSymbol& pSymbol) |
| { |
| return add(pSymbol, Category::Local); |
| } |
| |
| SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol, |
| Category::Type pSource, |
| Category::Type pTarget) |
| { |
| int distance = pTarget - pSource; |
| if (0 == distance) { |
| // in the same category, do not need to re-arrange |
| return *this; |
| } |
| |
| // source and target are not in the same category |
| // find the category of source |
| Category* current = m_pFile; |
| while(NULL != current) { |
| if (pSource == current->type) |
| break; |
| current = current->next; |
| } |
| |
| assert(NULL != current); |
| size_t pos = 0; |
| if (!current->empty()) { |
| // find the position of source |
| pos = current->begin; |
| while (pos != current->end) { |
| if (m_OutputSymbols[pos] == &pSymbol) |
| break; |
| ++pos; |
| } |
| } |
| // FIXME: Try to search the symbol explicitly, if symbol is not in the given |
| // source category. Or we need to add some logics like shouldForceLocal() in |
| // SymbolCategory::Category::categorize(). |
| if (current->end == pos || current->empty()) { |
| current = m_pFile; |
| do { |
| pos = current->begin; |
| while (pos != current->end) { |
| if (m_OutputSymbols[pos] == &pSymbol) { |
| distance = pTarget - current->type; |
| break; |
| } |
| ++pos; |
| } |
| if (pos != current->end) |
| break; |
| current = current->next; |
| } while (current != NULL); |
| assert(current != NULL); |
| } |
| |
| // The distance is positive. It means we should bubble sort downward. |
| if (distance > 0) { |
| // downward |
| size_t rear; |
| do { |
| if (current->type == pTarget) { |
| break; |
| } |
| else { |
| assert(!current->isLast() && "target category is wrong."); |
| rear = current->end - 1; |
| std::swap(m_OutputSymbols[pos], m_OutputSymbols[rear]); |
| pos = rear; |
| current->next->begin--; |
| current->end--; |
| } |
| current = current->next; |
| } while(NULL != current); |
| |
| return *this; |
| } // downward |
| |
| // The distance is negative. It means we should bubble sort upward. |
| if (distance < 0) { |
| |
| // upward |
| do { |
| if (current->type == pTarget) { |
| break; |
| } |
| else { |
| assert(!current->isFirst() && "target category is wrong."); |
| std::swap(m_OutputSymbols[current->begin], m_OutputSymbols[pos]); |
| pos = current->begin; |
| current->begin++; |
| current->prev->end++; |
| } |
| current = current->prev; |
| } while(NULL != current); |
| |
| return *this; |
| } // upward |
| return *this; |
| } |
| |
| SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol, |
| const ResolveInfo& pSourceInfo) |
| { |
| assert(NULL != pSymbol.resolveInfo()); |
| return arrange(pSymbol, |
| Category::categorize(pSourceInfo), |
| Category::categorize(*pSymbol.resolveInfo())); |
| } |
| |
| SymbolCategory& SymbolCategory::changeCommonsToGlobal() |
| { |
| // Change Common to Dynamic/Regular |
| while (!emptyCommons()) { |
| size_t pos = m_pCommon->end - 1; |
| switch (Category::categorize(*(m_OutputSymbols[pos]->resolveInfo()))) { |
| case Category::Dynamic: |
| m_pCommon->end--; |
| m_pDynamic->begin--; |
| break; |
| case Category::Regular: |
| std::swap(m_OutputSymbols[pos], m_OutputSymbols[m_pDynamic->end - 1]); |
| m_pCommon->end--; |
| m_pDynamic->begin--; |
| m_pDynamic->end--; |
| m_pRegular->begin--; |
| break; |
| default: |
| assert(0); |
| break; |
| } |
| } |
| return *this; |
| } |
| |
| SymbolCategory& SymbolCategory::changeToDynamic(LDSymbol& pSymbol) |
| { |
| assert(NULL != pSymbol.resolveInfo()); |
| return arrange(pSymbol, |
| Category::categorize(*pSymbol.resolveInfo()), |
| Category::LocalDyn); |
| } |
| |
| size_t SymbolCategory::numOfSymbols() const |
| { |
| return m_OutputSymbols.size(); |
| } |
| |
| size_t SymbolCategory::numOfFiles() const |
| { |
| return m_pFile->size(); |
| } |
| |
| size_t SymbolCategory::numOfLocals() const |
| { |
| return m_pLocal->size(); |
| } |
| |
| size_t SymbolCategory::numOfLocalDyns() const |
| { |
| return m_pLocalDyn->size(); |
| } |
| |
| size_t SymbolCategory::numOfCommons() const |
| { |
| return m_pCommon->size(); |
| } |
| |
| size_t SymbolCategory::numOfDynamics() const |
| { |
| return m_pDynamic->size(); |
| } |
| |
| size_t SymbolCategory::numOfRegulars() const |
| { |
| return m_pRegular->size(); |
| } |
| |
| bool SymbolCategory::empty() const |
| { |
| return m_OutputSymbols.empty(); |
| } |
| |
| bool SymbolCategory::emptyFiles() const |
| { |
| return m_pFile->empty(); |
| } |
| |
| bool SymbolCategory::emptyLocals() const |
| { |
| return m_pLocal->empty(); |
| } |
| |
| bool SymbolCategory::emptyLocalDyns() const |
| { |
| return m_pLocalDyn->empty(); |
| } |
| |
| bool SymbolCategory::emptyCommons() const |
| { |
| return m_pCommon->empty(); |
| } |
| |
| bool SymbolCategory::emptyDynamics() const |
| { |
| return m_pDynamic->empty(); |
| } |
| |
| bool SymbolCategory::emptyRegulars() const |
| { |
| return m_pRegular->empty(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::begin() |
| { |
| return m_OutputSymbols.begin(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::end() |
| { |
| return m_OutputSymbols.end(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::begin() const |
| { |
| return m_OutputSymbols.begin(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::end() const |
| { |
| return m_OutputSymbols.end(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::fileBegin() |
| { |
| return m_OutputSymbols.begin(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::fileEnd() |
| { |
| iterator iter = fileBegin(); |
| iter += m_pFile->size(); |
| return iter; |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::fileBegin() const |
| { |
| return m_OutputSymbols.begin(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::fileEnd() const |
| { |
| const_iterator iter = fileBegin(); |
| iter += m_pFile->size(); |
| return iter; |
| } |
| |
| SymbolCategory::iterator SymbolCategory::localBegin() |
| { |
| return fileEnd(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::localEnd() |
| { |
| iterator iter = localBegin(); |
| iter += m_pLocal->size(); |
| return iter; |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::localBegin() const |
| { |
| return fileEnd(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::localEnd() const |
| { |
| const_iterator iter = localBegin(); |
| iter += m_pLocal->size(); |
| return iter; |
| } |
| |
| SymbolCategory::iterator SymbolCategory::localDynBegin() |
| { |
| return localEnd(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::localDynEnd() |
| { |
| iterator iter = localDynBegin(); |
| iter += m_pLocalDyn->size(); |
| return iter; |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::localDynBegin() const |
| { |
| return localEnd(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::localDynEnd() const |
| { |
| const_iterator iter = localDynBegin(); |
| iter += m_pLocalDyn->size(); |
| return iter; |
| } |
| |
| SymbolCategory::iterator SymbolCategory::commonBegin() |
| { |
| return localDynEnd(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::commonEnd() |
| { |
| iterator iter = commonBegin(); |
| iter += m_pCommon->size(); |
| return iter; |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::commonBegin() const |
| { |
| return localDynEnd(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::commonEnd() const |
| { |
| const_iterator iter = commonBegin(); |
| iter += m_pCommon->size(); |
| return iter; |
| } |
| |
| SymbolCategory::iterator SymbolCategory::dynamicBegin() |
| { |
| return commonEnd(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::dynamicEnd() |
| { |
| iterator iter = dynamicBegin(); |
| iter += m_pDynamic->size(); |
| return iter; |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::dynamicBegin() const |
| { |
| return commonEnd(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::dynamicEnd() const |
| { |
| const_iterator iter = dynamicBegin(); |
| iter += m_pDynamic->size(); |
| return iter; |
| } |
| |
| SymbolCategory::iterator SymbolCategory::regularBegin() |
| { |
| return commonEnd(); |
| } |
| |
| SymbolCategory::iterator SymbolCategory::regularEnd() |
| { |
| return m_OutputSymbols.end(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::regularBegin() const |
| { |
| return commonEnd(); |
| } |
| |
| SymbolCategory::const_iterator SymbolCategory::regularEnd() const |
| { |
| return m_OutputSymbols.end(); |
| } |
| |