Use std::unordered_set (hash set) instead of std::set (tree set) in blockfilter interface, as suggested by @ryanofsky in #12254. This may result in a very minor speedup, but I haven’t measured.
This moves CSipHasher to it’s own file crypto/siphash.h, so that it can be used in the libbitcoin_util library without including hash.{h,cpp}. I’m open to other suggestions on solving this issue if people would prefer to leave CSipHasher where it is.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
357+ uint64_t m_k0, m_k1;
358+
359+public:
360+ ByteVectorHash();
361+ size_t operator()(const std::vector<unsigned char>& input) const;
362+};
util.h is the best place for a generic utility data structure such as this, it’s more for assorted operating system functions
support/bytevectorhash.h ?
unless there’s a strong need to group this with other things
0@@ -0,0 +1,47 @@
1+// Copyright (c) 2016-2018 The Bitcoin Core developers
0@@ -0,0 +1,18 @@
1+// Copyright (c) 2018 The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#include <crypto/siphash.h>
6+#include <support/bytevectorhash.h>
7+#include <random.h>
0src/support/bytevectorhash.cpp:6:1: warning: #includes are not sorted properly [llvm-include-order]
20+ v[0] = 0x736f6d6570736575ULL ^ k0;
21+ v[1] = 0x646f72616e646f6dULL ^ k1;
22+ v[2] = 0x6c7967656e657261ULL ^ k0;
23+ v[3] = 0x7465646279746573ULL ^ k1;
24+ count = 0;
25+ tmp = 0;
count and tmp using default member initializers or in the member initializer list of the constructor?
0@@ -0,0 +1,23 @@
1+// Copyright (c) 2018 The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#ifndef BITCOIN_SUPPORT_BYTEVECTORHASH_H
6+#define BITCOIN_SUPPORT_BYTEVECTORHASH_H
7+
8+/**
9+ * Implementation of Hash named requirement for a byte vector. This may be used the hash function in
10+ * std::unordered_set or std::unordered_map over std::vector<unsigned char>. Internally, a random
11+ * instance of SipHash-2-4 is used.
12+ */
13+class ByteVectorHash
14+{
15+private:
private.
class is private.
14@@ -15,6 +15,7 @@
15
16 #include <amount.h>
17 #include <coins.h>
18+#include <crypto/siphash.h>
5@@ -6,6 +6,7 @@
6 #include <util.h>
7
8 #include <chainparamsbase.h>
9+#include <crypto/siphash.h>
0@@ -0,0 +1,23 @@
1+// Copyright (c) 2018 The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#ifndef BITCOIN_SUPPORT_BYTEVECTORHASH_H
6+#define BITCOIN_SUPPORT_BYTEVECTORHASH_H
7+
8+/**
<stdint.h> and <vector>.
8+/**
9+ * Implementation of Hash named requirement for a byte vector. This may be used the hash function in
10+ * std::unordered_set or std::unordered_map over std::vector<unsigned char>. Internally, a random
11+ * instance of SipHash-2-4 is used.
12+ */
13+class ByteVectorHash
@jimpo can you improve PR description of the advantages of this change (beside linking @ryanofsky suggestion)?
Do you have numbers to support this change?
Left some nits.
5+#ifndef BITCOIN_SUPPORT_BYTEVECTORHASH_H
6+#define BITCOIN_SUPPORT_BYTEVECTORHASH_H
7+
8+/**
9+ * Implementation of Hash named requirement for a byte vector. This may be used the hash function in
10+ * std::unordered_set or std::unordered_map over std::vector<unsigned char>. Internally, a random
In commit “blockfilter: Use unordered_set instead of set in blockfilter.” (f4608359e4e643c6e197df822e03226146e37a49)
The way this is written makes it seem like this whole class is tied to std::vector<unsigned char>, when actually only the call operator is. I guess my concern that if someone wants to reuse this hash function on a similar type like Span<char>, prevector, or std::string, the naming and comments here will lead them to copy/paste/rename this whole class instead of doing something simpler like overloading the call operator or adding a Span conversion.
I’d suggest:
operator() overloads for new types could be added here in the future.ByteVectorHash to something like RandomizedSipHash to avoid tying it to std::vector.std::vector with Span.
random and crypto/siphash. Perhaps others have a different understanding, as I don’t think it was ever written down somewhere what it was for, but I would just put it in src/.
final specifier, and tweaking includes.
This is a move-only commit with the exception of changes to includes.