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 14using namespace mcld; 15 16//===----------------------------------------------------------------------===// 17// Category 18SymbolCategory::Category::Type 19SymbolCategory::Category::categorize(const ResolveInfo& pInfo) 20{ 21 if (ResolveInfo::File == pInfo.type()) 22 return Category::File; 23 if (ResolveInfo::Local == pInfo.binding()) 24 return Category::Local; 25 if (ResolveInfo::Common == pInfo.desc()) 26 return Category::Common; 27 if (ResolveInfo::Weak == pInfo.binding()) 28 return Category::Weak; 29 return Category::Global; 30} 31 32//===----------------------------------------------------------------------===// 33// SymbolCategory 34SymbolCategory::SymbolCategory() 35{ 36 m_pFile = new Category(Category::File); 37 m_pLocal = new Category(Category::Local); 38 m_pCommon = new Category(Category::Common); 39 m_pWeak = new Category(Category::Weak); 40 m_pGlobal = new Category(Category::Global); 41 42 m_pFile->next = m_pLocal; 43 m_pLocal->next = m_pCommon; 44 m_pCommon->next = m_pWeak; 45 m_pWeak->next = m_pGlobal; 46 47 m_pGlobal->prev = m_pWeak; 48 m_pWeak->prev = m_pCommon; 49 m_pCommon->prev = m_pLocal; 50 m_pLocal->prev = m_pFile; 51} 52 53SymbolCategory::~SymbolCategory() 54{ 55 Category* current = m_pFile; 56 while (NULL != current) { 57 Category* tmp = current; 58 current = current->next; 59 delete tmp; 60 } 61} 62 63SymbolCategory& SymbolCategory::add(LDSymbol& pSymbol) 64{ 65 m_OutputSymbols.push_back(&pSymbol); 66 67 assert(NULL != pSymbol.resolveInfo()); 68 Category::Type target = Category::categorize(*pSymbol.resolveInfo()); 69 70 Category* current = m_pGlobal; 71 72 // use non-stable bubble sort to arrange the order of symbols. 73 while (NULL != current) { 74 if (current->type == target) { 75 current->end++; 76 break; 77 } 78 else { 79 if (!current->empty()) { 80 std::swap(m_OutputSymbols[current->begin], 81 m_OutputSymbols[current->end]); 82 } 83 current->end++; 84 current->begin++; 85 current = current->prev; 86 } 87 } 88 return *this; 89} 90 91SymbolCategory& SymbolCategory::forceLocal(LDSymbol& pSymbol) 92{ 93 m_OutputSymbols.insert(localEnd(), &pSymbol); 94 m_pLocal->end++; 95 m_pCommon->begin++; 96 m_pCommon->end++; 97 m_pWeak->begin++; 98 m_pWeak->end++; 99 m_pGlobal->begin++; 100 m_pGlobal->end++; 101 102 return *this; 103} 104 105SymbolCategory& SymbolCategory::arrange(LDSymbol& pSymbol, const ResolveInfo& pSourceInfo) 106{ 107 assert(NULL != pSymbol.resolveInfo()); 108 Category::Type source = Category::categorize(pSourceInfo); 109 Category::Type target = Category::categorize(*pSymbol.resolveInfo()); 110 111 int distance = target - source; 112 if (0 == distance) { 113 // in the same category, do not need to re-arrange 114 return *this; 115 } 116 117 // source and target are not in the same category 118 // find the category of source 119 Category* current = m_pFile; 120 while(NULL != current) { 121 if (source == current->type) 122 break; 123 current = current->next; 124 } 125 126 assert(NULL != current); 127 assert(!current->empty()); 128 129 // find the position of source 130 size_t pos = current->begin; 131 while (pos != current->end) { 132 if (m_OutputSymbols[pos] == &pSymbol) 133 break; 134 ++pos; 135 } 136 137 assert(current->end != pos); 138 139 // The distance is positive. It means we should bubble sort downward. 140 if (distance > 0) { 141 // downward 142 size_t rear; 143 do { 144 if (current->type == target) { 145 break; 146 } 147 else { 148 assert(!current->isLast() && "target category is wrong."); 149 rear = current->end - 1; 150 std::swap(m_OutputSymbols[pos], m_OutputSymbols[rear]); 151 pos = rear; 152 current->next->begin--; 153 current->end--; 154 } 155 current = current->next; 156 } while(NULL != current); 157 158 return *this; 159 } // downward 160 161 // The distance is negative. It means we should bubble sort upward. 162 if (distance < 0) { 163 164 // upward 165 do { 166 if (current->type == target) { 167 break; 168 } 169 else { 170 assert(!current->isFirst() && "target category is wrong."); 171 std::swap(m_OutputSymbols[current->begin], m_OutputSymbols[pos]); 172 pos = current->begin; 173 current->begin++; 174 current->prev->end++; 175 } 176 current = current->prev; 177 } while(NULL != current); 178 179 return *this; 180 } // upward 181 return *this; 182} 183 184SymbolCategory& SymbolCategory::changeCommonsToGlobal() 185{ 186 if (emptyCommons()) 187 return *this; 188 189 size_t com_rear = m_pCommon->end - 1; 190 size_t com_front = m_pCommon->begin; 191 size_t weak_rear = m_pWeak->end - 1; 192 size_t weak_size = m_pWeak->end - m_pWeak->begin; 193 for (size_t sym = com_rear; sym >= com_front; --sym) { 194 std::swap(m_OutputSymbols[weak_rear], m_OutputSymbols[sym]); 195 --weak_rear; 196 } 197 198 m_pWeak->begin = m_pCommon->begin; 199 m_pWeak->end = m_pCommon->begin + weak_size; 200 m_pGlobal->begin = m_pWeak->end; 201 m_pCommon->begin = m_pCommon->end = m_pWeak->begin; 202 203 return *this; 204} 205 206size_t SymbolCategory::numOfSymbols() const 207{ 208 return m_OutputSymbols.size(); 209} 210 211size_t SymbolCategory::numOfLocals() const 212{ 213 return (m_pFile->size() + m_pLocal->size()); 214} 215 216size_t SymbolCategory::numOfCommons() const 217{ 218 return m_pCommon->size(); 219} 220 221size_t SymbolCategory::numOfRegulars() const 222{ 223 return (m_pWeak->size() + m_pGlobal->size()); 224} 225 226bool SymbolCategory::empty() const 227{ 228 return (emptyLocals() && 229 emptyCommons() && 230 emptyRegulars()); 231} 232 233bool SymbolCategory::emptyLocals() const 234{ 235 return (m_pFile->empty() && m_pLocal->empty()); 236} 237 238bool SymbolCategory::emptyCommons() const 239{ 240 return m_pCommon->empty(); 241} 242 243bool SymbolCategory::emptyRegulars() const 244{ 245 return (m_pWeak->empty() && m_pGlobal->empty()); 246} 247 248SymbolCategory::iterator SymbolCategory::begin() 249{ 250 return m_OutputSymbols.begin(); 251} 252 253SymbolCategory::iterator SymbolCategory::end() 254{ 255 return m_OutputSymbols.end(); 256} 257 258SymbolCategory::const_iterator SymbolCategory::begin() const 259{ 260 return m_OutputSymbols.begin(); 261} 262 263SymbolCategory::const_iterator SymbolCategory::end() const 264{ 265 return m_OutputSymbols.end(); 266} 267 268SymbolCategory::iterator SymbolCategory::localBegin() 269{ 270 return m_OutputSymbols.begin(); 271} 272 273SymbolCategory::iterator SymbolCategory::localEnd() 274{ 275 iterator iter = m_OutputSymbols.begin(); 276 iter += m_pFile->size(); 277 iter += m_pLocal->size(); 278 return iter; 279} 280 281SymbolCategory::const_iterator SymbolCategory::localBegin() const 282{ 283 return m_OutputSymbols.begin(); 284} 285 286SymbolCategory::const_iterator SymbolCategory::localEnd() const 287{ 288 const_iterator iter = m_OutputSymbols.begin(); 289 iter += m_pFile->size(); 290 iter += m_pLocal->size(); 291 return iter; 292} 293 294SymbolCategory::iterator SymbolCategory::commonBegin() 295{ 296 return localEnd(); 297} 298 299SymbolCategory::iterator SymbolCategory::commonEnd() 300{ 301 iterator iter = localEnd(); 302 iter += m_pCommon->size(); 303 return iter; 304} 305 306SymbolCategory::const_iterator SymbolCategory::commonBegin() const 307{ 308 return localEnd(); 309} 310 311SymbolCategory::const_iterator SymbolCategory::commonEnd() const 312{ 313 const_iterator iter = localEnd(); 314 iter += m_pCommon->size(); 315 return iter; 316} 317 318SymbolCategory::iterator SymbolCategory::regularBegin() 319{ 320 return commonEnd(); 321} 322 323SymbolCategory::iterator SymbolCategory::regularEnd() 324{ 325 return m_OutputSymbols.end(); 326} 327 328SymbolCategory::const_iterator SymbolCategory::regularBegin() const 329{ 330 return commonEnd(); 331} 332 333SymbolCategory::const_iterator SymbolCategory::regularEnd() const 334{ 335 return m_OutputSymbols.end(); 336} 337 338