1 // -*- mode: C++; c-file-style: "cc-mode" -*-
2 //*************************************************************************
3 // DESCRIPTION: Verilator: Hash AST trees to find duplicates
4 //
5 // Code available from: https://verilator.org
6 //
7 //*************************************************************************
8 //
9 // Copyright 2005-2021 by Wilson Snyder. This program is free software; you
10 // can redistribute it and/or modify it under the terms of either the GNU
11 // Lesser General Public License Version 3 or the Perl Artistic License
12 // Version 2.0.
13 // SPDX-License-Identifier: LGPL-3.0-only OR Artistic-2.0
14 //
15 //*************************************************************************
16 //
17 //  Datastructure for finding duplicate AstNode trees via hashing
18 //
19 //*************************************************************************
20 
21 #ifndef VERILATOR_V3DUPFINDER_H_
22 #define VERILATOR_V3DUPFINDER_H_
23 #include "config_build.h"
24 #include "verilatedos.h"
25 
26 #include "V3Error.h"
27 #include "V3Ast.h"
28 #include "V3Hasher.h"
29 
30 #include <map>
31 
32 //============================================================================
33 
34 struct V3DupFinderUserSame {
35     // Functor for V3DupFinder::findDuplicate
36     virtual bool isSame(AstNode*, AstNode*) = 0;
37     V3DupFinderUserSame() = default;
38     virtual ~V3DupFinderUserSame() = default;
39 };
40 
41 // This really is just a multimap from 'node hash' to 'node pointer', with some minor extensions.
42 class V3DupFinder final : private std::multimap<V3Hash, AstNode*> {
43     using Super = std::multimap<V3Hash, AstNode*>;
44 
45     // MEMBERS
46     const V3Hasher m_hasher;
47 
48 public:
49     // CONSTRUCTORS
V3DupFinder()50     V3DupFinder(){};
51     ~V3DupFinder() = default;
52 
53     // METHODS
54     VL_DEBUG_FUNC;  // Declare debug()
55 
56     // Expose minimal set of superclass interface
57     using Super::begin;
58     using Super::cbegin;
59     using Super::cend;
60     using Super::clear;
61     using Super::const_iterator;
62     using Super::empty;
63     using Super::end;
64     using Super::erase;
65     using Super::iterator;
66 
67     // Insert node into data structure
insert(AstNode * nodep)68     iterator insert(AstNode* nodep) { return emplace(m_hasher(nodep), nodep); }
69 
70     // Return duplicate, if one was inserted, with optional user check for sameness
71     iterator findDuplicate(AstNode* nodep, V3DupFinderUserSame* checkp = nullptr);
72 
73     // Dump for debug
74     void dumpFile(const string& filename, bool tree);
75     void dumpFilePrefixed(const string& nameComment, bool tree = false);
76 };
77 
78 #endif  // Guard
79