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