-
Notifications
You must be signed in to change notification settings - Fork 46
/
duplicatetracker.h
133 lines (115 loc) · 3.67 KB
/
duplicatetracker.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/*
This file is part of KDToolBox.
SPDX-FileCopyrightText: 2021 Klarälvdalens Datakonsult AB, a KDAB Group company <info@kdab.com>
Author: Marc Mutz <marc.mutz@kdab.com>
SPDX-License-Identifier: MIT
*/
#pragma once
#include <algorithm> // for std::max
#include <cstddef> // for std::max_align_t
#include <unordered_set>
#ifdef __has_include
#if __has_include(<memory_resource>) && __cplusplus > 201402L
#include <memory_resource>
#endif
#endif
namespace KDToolBox
{
namespace detail
{
template<std::size_t N>
struct alignas(std::max_align_t) Storage
{
char m_buffer[N];
};
template<typename T, typename Hash, typename Equal>
class DuplicateTrackerBaseBase
{
protected:
#ifdef __cpp_lib_memory_resource
std::pmr::monotonic_buffer_resource m_res;
std::pmr::unordered_set<T, Hash, Equal> m_set;
#else
std::unordered_set<T, Hash, Equal> m_set;
#endif
#ifdef __cpp_lib_memory_resource
explicit DuplicateTrackerBaseBase(char *buffer, std::size_t bufferSize, std::size_t N, const Hash &h,
const Equal &e)
: m_res(buffer, bufferSize)
, m_set(N, h, e, &m_res)
{
}
#else
explicit DuplicateTrackerBaseBase(std::size_t N, const Hash &h, const Equal &e)
: m_set(N, h, e)
{
}
#endif
DuplicateTrackerBaseBase(const DuplicateTrackerBaseBase &) = delete;
DuplicateTrackerBaseBase(DuplicateTrackerBaseBase &&) = delete;
DuplicateTrackerBaseBase &operator=(const DuplicateTrackerBaseBase &) = delete;
DuplicateTrackerBaseBase &operator=(DuplicateTrackerBaseBase &&) = delete;
~DuplicateTrackerBaseBase() = default;
void reserve(std::size_t n) { m_set.reserve(n); }
bool hasSeen(const T &t) { return !m_set.insert(t).second; }
bool hasSeen(T &&t) { return !m_set.insert(std::move(t)).second; }
bool contains(const T &t) const { return m_set.find(t) != m_set.end(); }
const decltype(m_set) &set() const noexcept { return m_set; }
decltype(m_set) &set() noexcept { return m_set; }
};
template<typename T>
struct node_guesstimate
{
void *next;
std::size_t hash;
T value;
};
template<typename T>
constexpr std::size_t calc_memory(std::size_t numNodes) noexcept
{
return sizeof(node_guesstimate<T>) * numNodes // nodes
+ sizeof(void *) * numNodes; // bucket list
}
template<typename T, std::size_t Prealloc, typename Hash, typename Equal>
class DuplicateTrackerBase :
#ifdef __cpp_lib_memory_resource
Storage<calc_memory<T>(Prealloc)>,
#endif
DuplicateTrackerBaseBase<T, Hash, Equal>
{
protected:
using Base = detail::DuplicateTrackerBaseBase<T, Hash, Equal>;
explicit DuplicateTrackerBase(std::size_t numBuckets, const Hash &h, const Equal &e)
#ifdef __cpp_lib_memory_resource
: Base(this->m_buffer, sizeof(this->m_buffer), std::max(numBuckets, Prealloc), h, e){}
#else
: Base(std::max(numBuckets, Prealloc), h, e)
{
}
#endif
~DuplicateTrackerBase() = default;
using Base::contains;
using Base::hasSeen;
using Base::reserve;
using Base::set;
};
} // namespace detail
template<typename T, std::size_t Prealloc = 64, typename Hash = std::hash<T>, typename Equal = std::equal_to<T>>
class DuplicateTracker : detail::DuplicateTrackerBase<T, Prealloc, Hash, Equal>
{
using Base = detail::DuplicateTrackerBase<T, Prealloc, Hash, Equal>;
public:
DuplicateTracker()
: DuplicateTracker(Prealloc, Hash(), Equal())
{
}
explicit DuplicateTracker(std::size_t numBuckets, const Hash &h = Hash(), const Equal &e = Equal())
: Base(numBuckets, h, e)
{
}
using Base::contains;
using Base::hasSeen;
using Base::reserve;
using Base::set;
};
} // namespace KDToolBox