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 14 using namespace mcld; 15 16 //===----------------------------------------------------------------------===// 17 // Category 18 SymbolCategory::Category::Type 19 SymbolCategory::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 34 SymbolCategory::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 53 SymbolCategory::~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 63 SymbolCategory& 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 91 SymbolCategory& 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 105 SymbolCategory& 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 184 SymbolCategory& 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 206 size_t SymbolCategory::numOfSymbols() const 207 { 208 return m_OutputSymbols.size(); 209 } 210 211 size_t SymbolCategory::numOfLocals() const 212 { 213 return (m_pFile->size() + m_pLocal->size()); 214 } 215 216 size_t SymbolCategory::numOfCommons() const 217 { 218 return m_pCommon->size(); 219 } 220 221 size_t SymbolCategory::numOfRegulars() const 222 { 223 return (m_pWeak->size() + m_pGlobal->size()); 224 } 225 226 bool SymbolCategory::empty() const 227 { 228 return (emptyLocals() && 229 emptyCommons() && 230 emptyRegulars()); 231 } 232 233 bool SymbolCategory::emptyLocals() const 234 { 235 return (m_pFile->empty() && m_pLocal->empty()); 236 } 237 238 bool SymbolCategory::emptyCommons() const 239 { 240 return m_pCommon->empty(); 241 } 242 243 bool SymbolCategory::emptyRegulars() const 244 { 245 return (m_pWeak->empty() && m_pGlobal->empty()); 246 } 247 248 SymbolCategory::iterator SymbolCategory::begin() 249 { 250 return m_OutputSymbols.begin(); 251 } 252 253 SymbolCategory::iterator SymbolCategory::end() 254 { 255 return m_OutputSymbols.end(); 256 } 257 258 SymbolCategory::const_iterator SymbolCategory::begin() const 259 { 260 return m_OutputSymbols.begin(); 261 } 262 263 SymbolCategory::const_iterator SymbolCategory::end() const 264 { 265 return m_OutputSymbols.end(); 266 } 267 268 SymbolCategory::iterator SymbolCategory::localBegin() 269 { 270 return m_OutputSymbols.begin(); 271 } 272 273 SymbolCategory::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 281 SymbolCategory::const_iterator SymbolCategory::localBegin() const 282 { 283 return m_OutputSymbols.begin(); 284 } 285 286 SymbolCategory::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 294 SymbolCategory::iterator SymbolCategory::commonBegin() 295 { 296 return localEnd(); 297 } 298 299 SymbolCategory::iterator SymbolCategory::commonEnd() 300 { 301 iterator iter = localEnd(); 302 iter += m_pCommon->size(); 303 return iter; 304 } 305 306 SymbolCategory::const_iterator SymbolCategory::commonBegin() const 307 { 308 return localEnd(); 309 } 310 311 SymbolCategory::const_iterator SymbolCategory::commonEnd() const 312 { 313 const_iterator iter = localEnd(); 314 iter += m_pCommon->size(); 315 return iter; 316 } 317 318 SymbolCategory::iterator SymbolCategory::regularBegin() 319 { 320 return commonEnd(); 321 } 322 323 SymbolCategory::iterator SymbolCategory::regularEnd() 324 { 325 return m_OutputSymbols.end(); 326 } 327 328 SymbolCategory::const_iterator SymbolCategory::regularBegin() const 329 { 330 return commonEnd(); 331 } 332 333 SymbolCategory::const_iterator SymbolCategory::regularEnd() const 334 { 335 return m_OutputSymbols.end(); 336 } 337 338
