Home | History | Annotate | Download | only in MC 
      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 
     17 namespace mcld {
     18 
     19 //===----------------------------------------------------------------------===//
     20 // Category
     21 SymbolCategory::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
     37 SymbolCategory::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 
     58 SymbolCategory::~SymbolCategory() {
     59   Category* current = m_pFile;
     60   while (current != NULL) {
     61     Category* tmp = current;
     62     current = current->next;
     63     delete tmp;
     64   }
     65 }
     66 
     67 SymbolCategory& 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 
     89 SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol) {
     90   assert(pSymbol.resolveInfo() != NULL);
     91   return add(pSymbol, Category::categorize(*pSymbol.resolveInfo()));
     92 }
     93 
     94 SymbolCategory& SymbolCategory::forceLocal(LDSymbol& pSymbol) {
     95   return add(pSymbol, Category::Local);
     96 }
     97 
     98 SymbolCategory& 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 
    190 SymbolCategory& 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 
    198 SymbolCategory& 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 
    222 SymbolCategory& SymbolCategory::changeToDynamic(LDSymbol& pSymbol) {
    223   assert(pSymbol.resolveInfo() != NULL);
    224   return arrange(pSymbol,
    225                  Category::categorize(*pSymbol.resolveInfo()),
    226                  Category::LocalDyn);
    227 }
    228 
    229 size_t SymbolCategory::numOfSymbols() const {
    230   return m_OutputSymbols.size();
    231 }
    232 
    233 size_t SymbolCategory::numOfFiles() const {
    234   return m_pFile->size();
    235 }
    236 
    237 size_t SymbolCategory::numOfLocals() const {
    238   return m_pLocal->size();
    239 }
    240 
    241 size_t SymbolCategory::numOfLocalDyns() const {
    242   return m_pLocalDyn->size();
    243 }
    244 
    245 size_t SymbolCategory::numOfCommons() const {
    246   return m_pCommon->size();
    247 }
    248 
    249 size_t SymbolCategory::numOfDynamics() const {
    250   return m_pDynamic->size();
    251 }
    252 
    253 size_t SymbolCategory::numOfRegulars() const {
    254   return m_pRegular->size();
    255 }
    256 
    257 bool SymbolCategory::empty() const {
    258   return m_OutputSymbols.empty();
    259 }
    260 
    261 bool SymbolCategory::emptyFiles() const {
    262   return m_pFile->empty();
    263 }
    264 
    265 bool SymbolCategory::emptyLocals() const {
    266   return m_pLocal->empty();
    267 }
    268 
    269 bool SymbolCategory::emptyLocalDyns() const {
    270   return m_pLocalDyn->empty();
    271 }
    272 
    273 bool SymbolCategory::emptyCommons() const {
    274   return m_pCommon->empty();
    275 }
    276 
    277 bool SymbolCategory::emptyDynamics() const {
    278   return m_pDynamic->empty();
    279 }
    280 
    281 bool SymbolCategory::emptyRegulars() const {
    282   return m_pRegular->empty();
    283 }
    284 
    285 SymbolCategory::iterator SymbolCategory::begin() {
    286   return m_OutputSymbols.begin();
    287 }
    288 
    289 SymbolCategory::iterator SymbolCategory::end() {
    290   return m_OutputSymbols.end();
    291 }
    292 
    293 SymbolCategory::const_iterator SymbolCategory::begin() const {
    294   return m_OutputSymbols.begin();
    295 }
    296 
    297 SymbolCategory::const_iterator SymbolCategory::end() const {
    298   return m_OutputSymbols.end();
    299 }
    300 
    301 SymbolCategory::iterator SymbolCategory::fileBegin() {
    302   return m_OutputSymbols.begin();
    303 }
    304 
    305 SymbolCategory::iterator SymbolCategory::fileEnd() {
    306   iterator iter = fileBegin();
    307   iter += m_pFile->size();
    308   return iter;
    309 }
    310 
    311 SymbolCategory::const_iterator SymbolCategory::fileBegin() const {
    312   return m_OutputSymbols.begin();
    313 }
    314 
    315 SymbolCategory::const_iterator SymbolCategory::fileEnd() const {
    316   const_iterator iter = fileBegin();
    317   iter += m_pFile->size();
    318   return iter;
    319 }
    320 
    321 SymbolCategory::iterator SymbolCategory::localBegin() {
    322   return fileEnd();
    323 }
    324 
    325 SymbolCategory::iterator SymbolCategory::localEnd() {
    326   iterator iter = localBegin();
    327   iter += m_pLocal->size();
    328   return iter;
    329 }
    330 
    331 SymbolCategory::const_iterator SymbolCategory::localBegin() const {
    332   return fileEnd();
    333 }
    334 
    335 SymbolCategory::const_iterator SymbolCategory::localEnd() const {
    336   const_iterator iter = localBegin();
    337   iter += m_pLocal->size();
    338   return iter;
    339 }
    340 
    341 SymbolCategory::iterator SymbolCategory::localDynBegin() {
    342   return localEnd();
    343 }
    344 
    345 SymbolCategory::iterator SymbolCategory::localDynEnd() {
    346   iterator iter = localDynBegin();
    347   iter += m_pLocalDyn->size();
    348   return iter;
    349 }
    350 
    351 SymbolCategory::const_iterator SymbolCategory::localDynBegin() const {
    352   return localEnd();
    353 }
    354 
    355 SymbolCategory::const_iterator SymbolCategory::localDynEnd() const {
    356   const_iterator iter = localDynBegin();
    357   iter += m_pLocalDyn->size();
    358   return iter;
    359 }
    360 
    361 SymbolCategory::iterator SymbolCategory::commonBegin() {
    362   return localDynEnd();
    363 }
    364 
    365 SymbolCategory::iterator SymbolCategory::commonEnd() {
    366   iterator iter = commonBegin();
    367   iter += m_pCommon->size();
    368   return iter;
    369 }
    370 
    371 SymbolCategory::const_iterator SymbolCategory::commonBegin() const {
    372   return localDynEnd();
    373 }
    374 
    375 SymbolCategory::const_iterator SymbolCategory::commonEnd() const {
    376   const_iterator iter = commonBegin();
    377   iter += m_pCommon->size();
    378   return iter;
    379 }
    380 
    381 SymbolCategory::iterator SymbolCategory::dynamicBegin() {
    382   return commonEnd();
    383 }
    384 
    385 SymbolCategory::iterator SymbolCategory::dynamicEnd() {
    386   iterator iter = dynamicBegin();
    387   iter += m_pDynamic->size();
    388   return iter;
    389 }
    390 
    391 SymbolCategory::const_iterator SymbolCategory::dynamicBegin() const {
    392   return commonEnd();
    393 }
    394 
    395 SymbolCategory::const_iterator SymbolCategory::dynamicEnd() const {
    396   const_iterator iter = dynamicBegin();
    397   iter += m_pDynamic->size();
    398   return iter;
    399 }
    400 
    401 SymbolCategory::iterator SymbolCategory::regularBegin() {
    402   return dynamicEnd();
    403 }
    404 
    405 SymbolCategory::iterator SymbolCategory::regularEnd() {
    406   return m_OutputSymbols.end();
    407 }
    408 
    409 SymbolCategory::const_iterator SymbolCategory::regularBegin() const {
    410   return dynamicEnd();
    411 }
    412 
    413 SymbolCategory::const_iterator SymbolCategory::regularEnd() const {
    414   return m_OutputSymbols.end();
    415 }
    416 
    417 }  // namespace mcld
    418