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