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 size_t pos = 0; 124 if (!current->empty()) { 125 // find the position of source 126 pos = current->begin; 127 while (pos != current->end) { 128 if (m_OutputSymbols[pos] == &pSymbol) 129 break; 130 ++pos; 131 } 132 } 133 // FIXME: Try to search the symbol explicitly, if symbol is not in the given 134 // source category. Or we need to add some logics like shouldForceLocal() in 135 // SymbolCategory::Category::categorize(). 136 if (current->end == pos || current->empty()) { 137 current = m_pFile; 138 do { 139 pos = current->begin; 140 while (pos != current->end) { 141 if (m_OutputSymbols[pos] == &pSymbol) { 142 distance = pTarget - current->type; 143 break; 144 } 145 ++pos; 146 } 147 if (pos != current->end) 148 break; 149 current = current->next; 150 } while (current != NULL); 151 assert(current != NULL); 152 } 153 154 // The distance is positive. It means we should bubble sort downward. 155 if (distance > 0) { 156 // downward 157 size_t rear; 158 do { 159 if (current->type == pTarget) { 160 break; 161 } 162 else { 163 assert(!current->isLast() && "target category is wrong."); 164 rear = current->end - 1; 165 std::swap(m_OutputSymbols[pos], m_OutputSymbols[rear]); 166 pos = rear; 167 current->next->begin--; 168 current->end--; 169 } 170 current = current->next; 171 } while(NULL != current); 172 173 return *this; 174 } // downward 175 176 // The distance is negative. It means we should bubble sort upward. 177 if (distance < 0) { 178 179 // upward 180 do { 181 if (current->type == pTarget) { 182 break; 183 } 184 else { 185 assert(!current->isFirst() && "target category is wrong."); 186 std::swap(m_OutputSymbols[current->begin], m_OutputSymbols[pos]); 187 pos = current->begin; 188 current->begin++; 189 current->prev->end++; 190 } 191 current = current->prev; 192 } while(NULL != current); 193 194 return *this; 195 } // upward 196 return *this; 197 } 198 199 SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol, 200 const ResolveInfo& pSourceInfo) 201 { 202 assert(NULL != pSymbol.resolveInfo()); 203 return arrange(pSymbol, 204 Category::categorize(pSourceInfo), 205 Category::categorize(*pSymbol.resolveInfo())); 206 } 207 208 SymbolCategory& SymbolCategory::changeCommonsToGlobal() 209 { 210 // Change Common to Dynamic/Regular 211 while (!emptyCommons()) { 212 size_t pos = m_pCommon->end - 1; 213 switch (Category::categorize(*(m_OutputSymbols[pos]->resolveInfo()))) { 214 case Category::Dynamic: 215 m_pCommon->end--; 216 m_pDynamic->begin--; 217 break; 218 case Category::Regular: 219 std::swap(m_OutputSymbols[pos], m_OutputSymbols[m_pDynamic->end - 1]); 220 m_pCommon->end--; 221 m_pDynamic->begin--; 222 m_pDynamic->end--; 223 m_pRegular->begin--; 224 break; 225 default: 226 assert(0); 227 break; 228 } 229 } 230 return *this; 231 } 232 233 SymbolCategory& SymbolCategory::changeToDynamic(LDSymbol& pSymbol) 234 { 235 assert(NULL != pSymbol.resolveInfo()); 236 return arrange(pSymbol, 237 Category::categorize(*pSymbol.resolveInfo()), 238 Category::LocalDyn); 239 } 240 241 size_t SymbolCategory::numOfSymbols() const 242 { 243 return m_OutputSymbols.size(); 244 } 245 246 size_t SymbolCategory::numOfFiles() const 247 { 248 return m_pFile->size(); 249 } 250 251 size_t SymbolCategory::numOfLocals() const 252 { 253 return m_pLocal->size(); 254 } 255 256 size_t SymbolCategory::numOfLocalDyns() const 257 { 258 return m_pLocalDyn->size(); 259 } 260 261 size_t SymbolCategory::numOfCommons() const 262 { 263 return m_pCommon->size(); 264 } 265 266 size_t SymbolCategory::numOfDynamics() const 267 { 268 return m_pDynamic->size(); 269 } 270 271 size_t SymbolCategory::numOfRegulars() const 272 { 273 return m_pRegular->size(); 274 } 275 276 bool SymbolCategory::empty() const 277 { 278 return m_OutputSymbols.empty(); 279 } 280 281 bool SymbolCategory::emptyFiles() const 282 { 283 return m_pFile->empty(); 284 } 285 286 bool SymbolCategory::emptyLocals() const 287 { 288 return m_pLocal->empty(); 289 } 290 291 bool SymbolCategory::emptyLocalDyns() const 292 { 293 return m_pLocalDyn->empty(); 294 } 295 296 bool SymbolCategory::emptyCommons() const 297 { 298 return m_pCommon->empty(); 299 } 300 301 bool SymbolCategory::emptyDynamics() const 302 { 303 return m_pDynamic->empty(); 304 } 305 306 bool SymbolCategory::emptyRegulars() const 307 { 308 return m_pRegular->empty(); 309 } 310 311 SymbolCategory::iterator SymbolCategory::begin() 312 { 313 return m_OutputSymbols.begin(); 314 } 315 316 SymbolCategory::iterator SymbolCategory::end() 317 { 318 return m_OutputSymbols.end(); 319 } 320 321 SymbolCategory::const_iterator SymbolCategory::begin() const 322 { 323 return m_OutputSymbols.begin(); 324 } 325 326 SymbolCategory::const_iterator SymbolCategory::end() const 327 { 328 return m_OutputSymbols.end(); 329 } 330 331 SymbolCategory::iterator SymbolCategory::fileBegin() 332 { 333 return m_OutputSymbols.begin(); 334 } 335 336 SymbolCategory::iterator SymbolCategory::fileEnd() 337 { 338 iterator iter = fileBegin(); 339 iter += m_pFile->size(); 340 return iter; 341 } 342 343 SymbolCategory::const_iterator SymbolCategory::fileBegin() const 344 { 345 return m_OutputSymbols.begin(); 346 } 347 348 SymbolCategory::const_iterator SymbolCategory::fileEnd() const 349 { 350 const_iterator iter = fileBegin(); 351 iter += m_pFile->size(); 352 return iter; 353 } 354 355 SymbolCategory::iterator SymbolCategory::localBegin() 356 { 357 return fileEnd(); 358 } 359 360 SymbolCategory::iterator SymbolCategory::localEnd() 361 { 362 iterator iter = localBegin(); 363 iter += m_pLocal->size(); 364 return iter; 365 } 366 367 SymbolCategory::const_iterator SymbolCategory::localBegin() const 368 { 369 return fileEnd(); 370 } 371 372 SymbolCategory::const_iterator SymbolCategory::localEnd() const 373 { 374 const_iterator iter = localBegin(); 375 iter += m_pLocal->size(); 376 return iter; 377 } 378 379 SymbolCategory::iterator SymbolCategory::localDynBegin() 380 { 381 return localEnd(); 382 } 383 384 SymbolCategory::iterator SymbolCategory::localDynEnd() 385 { 386 iterator iter = localDynBegin(); 387 iter += m_pLocalDyn->size(); 388 return iter; 389 } 390 391 SymbolCategory::const_iterator SymbolCategory::localDynBegin() const 392 { 393 return localEnd(); 394 } 395 396 SymbolCategory::const_iterator SymbolCategory::localDynEnd() const 397 { 398 const_iterator iter = localDynBegin(); 399 iter += m_pLocalDyn->size(); 400 return iter; 401 } 402 403 SymbolCategory::iterator SymbolCategory::commonBegin() 404 { 405 return localDynEnd(); 406 } 407 408 SymbolCategory::iterator SymbolCategory::commonEnd() 409 { 410 iterator iter = commonBegin(); 411 iter += m_pCommon->size(); 412 return iter; 413 } 414 415 SymbolCategory::const_iterator SymbolCategory::commonBegin() const 416 { 417 return localDynEnd(); 418 } 419 420 SymbolCategory::const_iterator SymbolCategory::commonEnd() const 421 { 422 const_iterator iter = commonBegin(); 423 iter += m_pCommon->size(); 424 return iter; 425 } 426 427 SymbolCategory::iterator SymbolCategory::dynamicBegin() 428 { 429 return commonEnd(); 430 } 431 432 SymbolCategory::iterator SymbolCategory::dynamicEnd() 433 { 434 iterator iter = dynamicBegin(); 435 iter += m_pDynamic->size(); 436 return iter; 437 } 438 439 SymbolCategory::const_iterator SymbolCategory::dynamicBegin() const 440 { 441 return commonEnd(); 442 } 443 444 SymbolCategory::const_iterator SymbolCategory::dynamicEnd() const 445 { 446 const_iterator iter = dynamicBegin(); 447 iter += m_pDynamic->size(); 448 return iter; 449 } 450 451 SymbolCategory::iterator SymbolCategory::regularBegin() 452 { 453 return commonEnd(); 454 } 455 456 SymbolCategory::iterator SymbolCategory::regularEnd() 457 { 458 return m_OutputSymbols.end(); 459 } 460 461 SymbolCategory::const_iterator SymbolCategory::regularBegin() const 462 { 463 return commonEnd(); 464 } 465 466 SymbolCategory::const_iterator SymbolCategory::regularEnd() const 467 { 468 return m_OutputSymbols.end(); 469 } 470 471
