1 | // Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com> |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | #ifndef QDUPLICATETRACKER_P_H |
4 | #define QDUPLICATETRACKER_P_H |
5 | |
6 | // |
7 | // W A R N I N G |
8 | // ------------- |
9 | // |
10 | // This file is not part of the Qt API. It exists purely as an |
11 | // implementation detail. This header file may change from version to |
12 | // version without notice, or even be removed. |
13 | // |
14 | // We mean it. |
15 | // |
16 | |
17 | #include <private/qglobal_p.h> |
18 | |
19 | #ifdef __cpp_lib_memory_resource |
20 | # include <unordered_set> |
21 | # include <memory_resource> |
22 | # include <qhash.h> // for the hashing helpers |
23 | #else |
24 | # include <qset.h> |
25 | #endif |
26 | |
27 | QT_BEGIN_NAMESPACE |
28 | |
29 | template <typename T, size_t Prealloc = 32> |
30 | class QDuplicateTracker { |
31 | #ifdef __cpp_lib_memory_resource |
32 | template <typename HT> |
33 | struct QHasher { |
34 | size_t storedSeed = QHashSeed::globalSeed(); |
35 | size_t operator()(const HT &t) const { |
36 | return QHashPrivate::calculateHash(t, storedSeed); |
37 | } |
38 | }; |
39 | |
40 | struct node_guesstimate { void *next; size_t hash; T value; }; |
41 | static constexpr size_t bufferSize(size_t N) { |
42 | return N * sizeof(void*) // bucket list |
43 | + N * sizeof(node_guesstimate); // nodes |
44 | } |
45 | |
46 | char buffer[bufferSize(N: Prealloc)]; |
47 | std::pmr::monotonic_buffer_resource res{buffer, sizeof buffer}; |
48 | using Set = std::pmr::unordered_set<T, QHasher<T>>; |
49 | Set set{Prealloc, &res}; |
50 | #else |
51 | class Set : public QSet<T> { |
52 | qsizetype setSize = 0; |
53 | public: |
54 | explicit Set(qsizetype n) : QSet<T>{} |
55 | { this->reserve(n); } |
56 | |
57 | auto insert(const T &e) { |
58 | auto it = QSet<T>::insert(e); |
59 | const auto n = this->size(); |
60 | return std::pair{it, std::exchange(setSize, n) != n}; |
61 | } |
62 | |
63 | auto insert(T &&e) { |
64 | auto it = QSet<T>::insert(std::move(e)); |
65 | const auto n = this->size(); |
66 | return std::pair{it, std::exchange(setSize, n) != n}; |
67 | } |
68 | }; |
69 | Set set{Prealloc}; |
70 | #endif |
71 | Q_DISABLE_COPY_MOVE(QDuplicateTracker) |
72 | public: |
73 | static constexpr inline bool uses_pmr = |
74 | #ifdef __cpp_lib_memory_resource |
75 | true |
76 | #else |
77 | false |
78 | #endif |
79 | ; |
80 | QDuplicateTracker() {} // don't `= default`, lest we value-initialize `buffer` |
81 | explicit QDuplicateTracker(qsizetype n) |
82 | #ifdef __cpp_lib_memory_resource |
83 | : set{size_t(n), &res} |
84 | #else |
85 | : set{n} |
86 | #endif |
87 | {} |
88 | Q_DECL_DEPRECATED_X("Pass the capacity to reserve() to the ctor instead." ) |
89 | void reserve(qsizetype n) { set.reserve(n); } |
90 | [[nodiscard]] bool hasSeen(const T &s) |
91 | { |
92 | return !set.insert(s).second; |
93 | } |
94 | [[nodiscard]] bool hasSeen(T &&s) |
95 | { |
96 | return !set.insert(std::move(s)).second; |
97 | } |
98 | // For when you want to know, but aren't *yet* sure you'll add it: |
99 | [[nodiscard]] bool contains(const T &s) const |
100 | { |
101 | return set.find(s) != set.end(); // TODO C++20: can use set.contains() |
102 | } |
103 | |
104 | template <typename C> |
105 | void appendTo(C &c) const & |
106 | { |
107 | for (const auto &e : set) |
108 | c.push_back(e); |
109 | } |
110 | |
111 | template <typename C> |
112 | void appendTo(C &c) && |
113 | { |
114 | if constexpr (uses_pmr) { |
115 | while (!set.empty()) |
116 | c.push_back(std::move(set.extract(set.begin()).value())); |
117 | } else { |
118 | return appendTo(c); // lvalue version |
119 | } |
120 | } |
121 | |
122 | void clear() |
123 | { |
124 | #ifdef __cpp_lib_memory_resource |
125 | // The birth defect of std::unordered_set is that both the nodes as |
126 | // well as the bucket array are allocated from the same allocator, so |
127 | // if we want to reclaim memory from the freed nodes, we also need to |
128 | // reclaim the memory for the bucket array. |
129 | |
130 | set = Set(); // release all memory in `res` (clear() doesn't, and swap() is UB!) |
131 | res.release(); // restore to initial state (buffer, sizeof buffer) |
132 | // m_b_r can't reuse buffers, anyway |
133 | // now that `res` is reset to the initial state, also reset `set`: |
134 | set = Set{Prealloc, &res}; |
135 | #else |
136 | set.clear(); |
137 | #endif // __cpp_lib_memory_resource |
138 | } |
139 | }; |
140 | |
141 | QT_END_NAMESPACE |
142 | |
143 | #endif /* QDUPLICATETRACKER_P_H */ |
144 | |