1 //===- Core/SymbolTable.h - Main Symbol Table -----------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLD_CORE_SYMBOL_TABLE_H 10 #define LLD_CORE_SYMBOL_TABLE_H 11 12 #include "lld/Common/LLVM.h" 13 #include "llvm/ADT/DenseSet.h" 14 #include "llvm/Support/DJB.h" 15 #include <cstring> 16 #include <map> 17 #include <vector> 18 19 namespace lld { 20 21 class AbsoluteAtom; 22 class Atom; 23 class DefinedAtom; 24 class LinkingContext; 25 class ResolverOptions; 26 class SharedLibraryAtom; 27 class UndefinedAtom; 28 29 /// The SymbolTable class is responsible for coalescing atoms. 30 /// 31 /// All atoms coalescable by-name or by-content should be added. 32 /// The method replacement() can be used to find the replacement atom 33 /// if an atom has been coalesced away. 34 class SymbolTable { 35 public: 36 /// add atom to symbol table 37 bool add(const DefinedAtom &); 38 39 /// add atom to symbol table 40 bool add(const UndefinedAtom &); 41 42 /// add atom to symbol table 43 bool add(const SharedLibraryAtom &); 44 45 /// add atom to symbol table 46 bool add(const AbsoluteAtom &); 47 48 /// returns atom in symbol table for specified name (or nullptr) 49 const Atom *findByName(StringRef sym); 50 51 /// returns vector of remaining UndefinedAtoms 52 std::vector<const UndefinedAtom *> undefines(); 53 54 /// if atom has been coalesced away, return replacement, else return atom 55 const Atom *replacement(const Atom *); 56 57 /// if atom has been coalesced away, return true 58 bool isCoalescedAway(const Atom *); 59 60 private: 61 typedef llvm::DenseMap<const Atom *, const Atom *> AtomToAtom; 62 63 struct StringRefMappingInfo { getEmptyKeyStringRefMappingInfo64 static StringRef getEmptyKey() { return StringRef(); } getTombstoneKeyStringRefMappingInfo65 static StringRef getTombstoneKey() { return StringRef(" ", 1); } getHashValueStringRefMappingInfo66 static unsigned getHashValue(StringRef const val) { 67 return llvm::djbHash(val, 0); 68 } isEqualStringRefMappingInfo69 static bool isEqual(StringRef const lhs, StringRef const rhs) { 70 return lhs.equals(rhs); 71 } 72 }; 73 typedef llvm::DenseMap<StringRef, const Atom *, 74 StringRefMappingInfo> NameToAtom; 75 76 struct AtomMappingInfo { getEmptyKeyAtomMappingInfo77 static const DefinedAtom * getEmptyKey() { return nullptr; } getTombstoneKeyAtomMappingInfo78 static const DefinedAtom * getTombstoneKey() { return (DefinedAtom*)(-1); } 79 static unsigned getHashValue(const DefinedAtom * const Val); 80 static bool isEqual(const DefinedAtom * const LHS, 81 const DefinedAtom * const RHS); 82 }; 83 typedef llvm::DenseSet<const DefinedAtom*, AtomMappingInfo> AtomContentSet; 84 85 bool addByName(const Atom &); 86 bool addByContent(const DefinedAtom &); 87 88 AtomToAtom _replacedAtoms; 89 NameToAtom _nameTable; 90 AtomContentSet _contentTable; 91 }; 92 93 } // namespace lld 94 95 #endif // LLD_CORE_SYMBOL_TABLE_H 96