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 19namespace lld { 20 21class AbsoluteAtom; 22class Atom; 23class DefinedAtom; 24class LinkingContext; 25class ResolverOptions; 26class SharedLibraryAtom; 27class 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. 34class SymbolTable { 35public: 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 60private: 61 typedef llvm::DenseMap<const Atom *, const Atom *> AtomToAtom; 62 63 struct StringRefMappingInfo { 64 static StringRef getEmptyKey() { return StringRef(); } 65 static StringRef getTombstoneKey() { return StringRef(" ", 1); } 66 static unsigned getHashValue(StringRef const val) { 67 return llvm::djbHash(val, 0); 68 } 69 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 { 77 static const DefinedAtom * getEmptyKey() { return nullptr; } 78 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