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