================
@@ -38,22 +38,59 @@ namespace llvm {
// Immutable AVL-Tree Definition.
//===----------------------------------------------------------------------===//
-template <typename ImutInfo> class ImutAVLFactory;
+template <typename ImutInfo, bool Canonicalize = true> class ImutAVLFactory;
template <typename ImutInfo> class ImutIntervalAVLFactory;
-template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
+template <typename ImutInfo, bool Canonicalize = true>
+class ImutAVLTreeInOrderIterator;
+
+namespace ImutAVLDetail {
+/// The intrusive doubly-linked chain of same-digest trees in the factory's
+/// canonicalization cache. Held as an (empty) base so that, when
canonicalization
+/// is disabled, the empty base optimization removes it entirely. Kept separate
+/// from the cached digest below so that the two pointers pack without the tail
+/// padding that grouping a trailing 32-bit field with them would introduce.
+template <typename Tree, bool Canonicalize> struct CanonicalLinks {
+ Tree *Prev = nullptr;
+ Tree *Next = nullptr;
+};
+template <typename Tree> struct CanonicalLinks<Tree, false> {};
+
+/// The cached structural digest, used only for canonicalization. Stored as an
+/// LLVM_NO_UNIQUE_ADDRESS member so it occupies no space when disabled and
packs
+/// alongside the adjacent 32-bit fields when enabled.
+template <bool Canonicalize> struct CanonicalDigest {
+ uint32_t Digest = 0;
+};
+template <> struct CanonicalDigest<false> {};
-template <typename ImutInfo >
-class ImutAVLTree {
+/// The factory-side canonicalization cache: digest -> tree chain. Empty when
+/// canonicalization is disabled.
+template <typename Tree, bool Canonicalize> struct CanonicalCache {
+ DenseMap<unsigned, Tree *> Cache;
+};
+template <typename Tree> struct CanonicalCache<Tree, false> {};
+} // namespace ImutAVLDetail
+
+template <typename ImutInfo, bool Canonicalize = true>
+class ImutAVLTree
+ : private ImutAVLDetail::CanonicalLinks<
+ ImutAVLTree<ImutInfo, Canonicalize>, Canonicalize> {
----------------
Xazax-hun wrote:
Unfortunately, we cannot in the list of base classes. But the using in the
updated the body of the class.
https://github.com/llvm/llvm-project/pull/209300
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
