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 15 using namespace mcld; 16 17 //===----------------------------------------------------------------------===// 18 // Category 19 SymbolCategory::Category::Type 20 SymbolCategory::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 36 SymbolCategory::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 58 SymbolCategory::~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 68 SymbolCategory& 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 92 SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol) 93 { 94 assert(NULL != pSymbol.resolveInfo()); 95 return add(pSymbol, Category::categorize(*pSymbol.resolveInfo())); 96 } 97 98 SymbolCategory& SymbolCategory::forceLocal(LDSymbol& pSymbol) 99 { 100 return add(pSymbol, Category::Local); 101 } 102 103 SymbolCategory& 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 182 SymbolCategory& 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 191 SymbolCategory& 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 216 SymbolCategory& SymbolCategory::changeToDynamic(LDSymbol& pSymbol) 217 { 218 assert(NULL != pSymbol.resolveInfo()); 219 return arrange(pSymbol, 220 Category::categorize(*pSymbol.resolveInfo()), 221 Category::LocalDyn); 222 } 223 224 size_t SymbolCategory::numOfSymbols() const 225 { 226 return m_OutputSymbols.size(); 227 } 228 229 size_t SymbolCategory::numOfFiles() const 230 { 231 return m_pFile->size(); 232 } 233 234 size_t SymbolCategory::numOfLocals() const 235 { 236 return m_pLocal->size(); 237 } 238 239 size_t SymbolCategory::numOfLocalDyns() const 240 { 241 return m_pLocalDyn->size(); 242 } 243 244 size_t SymbolCategory::numOfCommons() const 245 { 246 return m_pCommon->size(); 247 } 248 249 size_t SymbolCategory::numOfDynamics() const 250 { 251 return m_pDynamic->size(); 252 } 253 254 size_t SymbolCategory::numOfRegulars() const 255 { 256 return m_pRegular->size(); 257 } 258 259 bool SymbolCategory::empty() const 260 { 261 return m_OutputSymbols.empty(); 262 } 263 264 bool SymbolCategory::emptyFiles() const 265 { 266 return m_pFile->empty(); 267 } 268 269 bool SymbolCategory::emptyLocals() const 270 { 271 return m_pLocal->empty(); 272 } 273 274 bool SymbolCategory::emptyLocalDyns() const 275 { 276 return m_pLocalDyn->empty(); 277 } 278 279 bool SymbolCategory::emptyCommons() const 280 { 281 return m_pCommon->empty(); 282 } 283 284 bool SymbolCategory::emptyDynamics() const 285 { 286 return m_pDynamic->empty(); 287 } 288 289 bool SymbolCategory::emptyRegulars() const 290 { 291 return m_pRegular->empty(); 292 } 293 294 SymbolCategory::iterator SymbolCategory::begin() 295 { 296 return m_OutputSymbols.begin(); 297 } 298 299 SymbolCategory::iterator SymbolCategory::end() 300 { 301 return m_OutputSymbols.end(); 302 } 303 304 SymbolCategory::const_iterator SymbolCategory::begin() const 305 { 306 return m_OutputSymbols.begin(); 307 } 308 309 SymbolCategory::const_iterator SymbolCategory::end() const 310 { 311 return m_OutputSymbols.end(); 312 } 313 314 SymbolCategory::iterator SymbolCategory::fileBegin() 315 { 316 return m_OutputSymbols.begin(); 317 } 318 319 SymbolCategory::iterator SymbolCategory::fileEnd() 320 { 321 iterator iter = fileBegin(); 322 iter += m_pFile->size(); 323 return iter; 324 } 325 326 SymbolCategory::const_iterator SymbolCategory::fileBegin() const 327 { 328 return m_OutputSymbols.begin(); 329 } 330 331 SymbolCategory::const_iterator SymbolCategory::fileEnd() const 332 { 333 const_iterator iter = fileBegin(); 334 iter += m_pFile->size(); 335 return iter; 336 } 337 338 SymbolCategory::iterator SymbolCategory::localBegin() 339 { 340 return fileEnd(); 341 } 342 343 SymbolCategory::iterator SymbolCategory::localEnd() 344 { 345 iterator iter = localBegin(); 346 iter += m_pLocal->size(); 347 return iter; 348 } 349 350 SymbolCategory::const_iterator SymbolCategory::localBegin() const 351 { 352 return fileEnd(); 353 } 354 355 SymbolCategory::const_iterator SymbolCategory::localEnd() const 356 { 357 const_iterator iter = localBegin(); 358 iter += m_pLocal->size(); 359 return iter; 360 } 361 362 SymbolCategory::iterator SymbolCategory::localDynBegin() 363 { 364 return localEnd(); 365 } 366 367 SymbolCategory::iterator SymbolCategory::localDynEnd() 368 { 369 iterator iter = localDynBegin(); 370 iter += m_pLocalDyn->size(); 371 return iter; 372 } 373 374 SymbolCategory::const_iterator SymbolCategory::localDynBegin() const 375 { 376 return localEnd(); 377 } 378 379 SymbolCategory::const_iterator SymbolCategory::localDynEnd() const 380 { 381 const_iterator iter = localDynBegin(); 382 iter += m_pLocalDyn->size(); 383 return iter; 384 } 385 386 SymbolCategory::iterator SymbolCategory::commonBegin() 387 { 388 return localDynEnd(); 389 } 390 391 SymbolCategory::iterator SymbolCategory::commonEnd() 392 { 393 iterator iter = commonBegin(); 394 iter += m_pCommon->size(); 395 return iter; 396 } 397 398 SymbolCategory::const_iterator SymbolCategory::commonBegin() const 399 { 400 return localDynEnd(); 401 } 402 403 SymbolCategory::const_iterator SymbolCategory::commonEnd() const 404 { 405 const_iterator iter = commonBegin(); 406 iter += m_pCommon->size(); 407 return iter; 408 } 409 410 SymbolCategory::iterator SymbolCategory::dynamicBegin() 411 { 412 return commonEnd(); 413 } 414 415 SymbolCategory::iterator SymbolCategory::dynamicEnd() 416 { 417 iterator iter = dynamicBegin(); 418 iter += m_pDynamic->size(); 419 return iter; 420 } 421 422 SymbolCategory::const_iterator SymbolCategory::dynamicBegin() const 423 { 424 return commonEnd(); 425 } 426 427 SymbolCategory::const_iterator SymbolCategory::dynamicEnd() const 428 { 429 const_iterator iter = dynamicBegin(); 430 iter += m_pDynamic->size(); 431 return iter; 432 } 433 434 SymbolCategory::iterator SymbolCategory::regularBegin() 435 { 436 return commonEnd(); 437 } 438 439 SymbolCategory::iterator SymbolCategory::regularEnd() 440 { 441 return m_OutputSymbols.end(); 442 } 443 444 SymbolCategory::const_iterator SymbolCategory::regularBegin() const 445 { 446 return commonEnd(); 447 } 448 449 SymbolCategory::const_iterator SymbolCategory::regularEnd() const 450 { 451 return m_OutputSymbols.end(); 452 } 453 454
