Bitcoin Core  22.99.0
P2P Digital Currency
minisketch.h
Go to the documentation of this file.
1 #ifndef _MINISKETCH_H_
2 #define _MINISKETCH_H_ 1
3 
4 #include <stdint.h>
5 #include <stdlib.h>
6 
7 #ifdef _MSC_VER
8 # include <compat.h>
9 #else
10 # include <unistd.h>
11 #endif
12 
13 #ifndef MINISKETCH_API
14 # if defined(_WIN32)
15 # ifdef MINISKETCH_BUILD
16 # define MINISKETCH_API __declspec(dllexport)
17 # else
18 # define MINISKETCH_API
19 # endif
20 # elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(MINISKETCH_BUILD)
21 # define MINISKETCH_API __attribute__ ((visibility ("default")))
22 # else
23 # define MINISKETCH_API
24 # endif
25 #endif
26 
27 #ifdef __cplusplus
28 # if __cplusplus >= 201103L
29 # include <memory>
30 # include <vector>
31 # include <cassert>
32 # if __cplusplus >= 201703L
33 # include <optional>
34 # endif // __cplusplus >= 201703L
35 # endif // __cplusplus >= 201103L
36 extern "C" {
37 #endif // __cplusplus
38 
40 typedef struct minisketch minisketch;
41 
43 MINISKETCH_API int minisketch_bits_supported(uint32_t bits);
44 
55 
60 MINISKETCH_API int minisketch_implementation_supported(uint32_t bits, uint32_t implementation);
61 
71 MINISKETCH_API minisketch* minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity);
72 
74 MINISKETCH_API uint32_t minisketch_bits(const minisketch* sketch);
75 
77 MINISKETCH_API size_t minisketch_capacity(const minisketch* sketch);
78 
81 
93 MINISKETCH_API void minisketch_set_seed(minisketch* sketch, uint64_t seed);
94 
100 
106 
109 
111 MINISKETCH_API void minisketch_serialize(const minisketch* sketch, unsigned char* output);
112 
114 MINISKETCH_API void minisketch_deserialize(minisketch* sketch, const unsigned char* input);
115 
129 MINISKETCH_API void minisketch_add_uint64(minisketch* sketch, uint64_t element);
130 
147 MINISKETCH_API size_t minisketch_merge(minisketch* sketch, const minisketch* other_sketch);
148 
156 MINISKETCH_API ssize_t minisketch_decode(const minisketch* sketch, size_t max_elements, uint64_t* output);
157 
170 MINISKETCH_API size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits);
171 
188 MINISKETCH_API size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits);
189 
190 #ifdef __cplusplus
191 }
192 
193 #if __cplusplus >= 201103L
194 
195 class Minisketch
196 {
197  struct Deleter
198  {
199  void operator()(minisketch* ptr) const
200  {
201  minisketch_destroy(ptr);
202  }
203  };
204 
205  std::unique_ptr<minisketch, Deleter> m_minisketch;
206 
207 public:
209  static bool BitsSupported(uint32_t bits) noexcept { return minisketch_bits_supported(bits); }
210 
212  static uint32_t MaxImplementation() noexcept { return minisketch_implementation_max(); }
213 
218  static bool ImplementationSupported(uint32_t bits, uint32_t implementation) noexcept { return minisketch_implementation_supported(bits, implementation); }
219 
225  static size_t ComputeCapacity(uint32_t bits, size_t max_elements, uint32_t fpbits) noexcept { return minisketch_compute_capacity(bits, max_elements, fpbits); }
226 
228  static size_t ComputeMaxElements(uint32_t bits, size_t capacity, uint32_t fpbits) noexcept { return minisketch_compute_max_elements(bits, capacity, fpbits); }
229 
231  Minisketch(const Minisketch& sketch) noexcept
232  {
233  if (sketch.m_minisketch) {
234  m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_clone(sketch.m_minisketch.get()));
235  }
236  }
237 
239  Minisketch& operator=(const Minisketch& sketch) noexcept
240  {
241  if (sketch.m_minisketch) {
242  m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_clone(sketch.m_minisketch.get()));
243  }
244  return *this;
245  }
246 
248  explicit operator bool() const noexcept { return bool{m_minisketch}; }
249 
251  Minisketch() noexcept = default;
252 
254  Minisketch(Minisketch&&) noexcept = default;
255 
257  Minisketch& operator=(Minisketch&&) noexcept = default;
258 
265  Minisketch(uint32_t bits, uint32_t implementation, size_t capacity) noexcept
266  {
267  m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_create(bits, implementation, capacity));
268  }
269 
272  static Minisketch CreateFP(uint32_t bits, uint32_t implementation, size_t max_elements, uint32_t fpbits) noexcept
273  {
274  return Minisketch(bits, implementation, ComputeCapacity(bits, max_elements, fpbits));
275  }
276 
278  uint32_t GetBits() const noexcept { return minisketch_bits(m_minisketch.get()); }
279 
281  size_t GetCapacity() const noexcept { return minisketch_capacity(m_minisketch.get()); }
282 
284  uint32_t GetImplementation() const noexcept { return minisketch_implementation(m_minisketch.get()); }
285 
287  Minisketch& SetSeed(uint64_t seed) noexcept
288  {
289  minisketch_set_seed(m_minisketch.get(), seed);
290  return *this;
291  }
292 
295  Minisketch& Add(uint64_t element) noexcept
296  {
297  minisketch_add_uint64(m_minisketch.get(), element);
298  return *this;
299  }
300 
303  Minisketch& Merge(const Minisketch& sketch) noexcept
304  {
305  minisketch_merge(m_minisketch.get(), sketch.m_minisketch.get());
306  return *this;
307  }
308 
311  bool Decode(std::vector<uint64_t>& result) const
312  {
313  ssize_t ret = minisketch_decode(m_minisketch.get(), result.size(), result.data());
314  if (ret == -1) return false;
315  result.resize(ret);
316  return true;
317  }
318 
320  size_t GetSerializedSize() const noexcept { return minisketch_serialized_size(m_minisketch.get()); }
321 
323  std::vector<unsigned char> Serialize() const
324  {
325  std::vector<unsigned char> result(GetSerializedSize());
326  minisketch_serialize(m_minisketch.get(), result.data());
327  return result;
328  }
329 
332  template<typename T>
333  Minisketch& Deserialize(
334  const T& obj,
335  typename std::enable_if<
336  std::is_convertible<typename std::remove_pointer<decltype(obj.data())>::type (*)[], const unsigned char (*)[]>::value &&
337  std::is_convertible<decltype(obj.size()), std::size_t>::value,
338  std::nullptr_t
339  >::type = nullptr) noexcept
340  {
341  assert(GetSerializedSize() == obj.size());
342  minisketch_deserialize(m_minisketch.get(), obj.data());
343  return *this;
344  }
345 
346 #if __cplusplus >= 201703L
347 
348  std::optional<std::vector<uint64_t>> Decode(size_t max_elements) const
349  {
350  std::vector<uint64_t> result(max_elements);
351  ssize_t ret = minisketch_decode(m_minisketch.get(), max_elements, result.data());
352  if (ret == -1) return {};
353  result.resize(ret);
354  return result;
355  }
356 
358  std::optional<std::vector<uint64_t>> DecodeFP(uint32_t fpbits) const
359  {
360  return Decode(ComputeMaxElements(GetBits(), GetCapacity(), fpbits));
361  }
362 #endif // __cplusplus >= 201703L
363 };
364 #endif // __cplusplus >= 201103L
365 #endif // __cplusplus
366 
367 #endif // _MINISKETCH_H_
assert
assert(!tx.IsCoinBase())
minisketch_create
MINISKETCH_API minisketch * minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity)
Construct a sketch for a given element size, implementation and capacity.
Definition: minisketch.cpp:380
minisketch_merge
MINISKETCH_API size_t minisketch_merge(minisketch *sketch, const minisketch *other_sketch)
Merge the elements of another sketch into this sketch.
Definition: minisketch.cpp:460
bech32::Decode
DecodeResult Decode(const std::string &str)
Decode a Bech32 or Bech32m string.
Definition: bech32.cpp:480
minisketch_serialized_size
MINISKETCH_API size_t minisketch_serialized_size(const minisketch *sketch)
Compute the size in bytes for serializing a given sketch.
Definition: minisketch.cpp:434
MINISKETCH_API
#define MINISKETCH_API
Definition: minisketch.h:23
Merge
FlatSigningProvider Merge(const FlatSigningProvider &a, const FlatSigningProvider &b)
Definition: signingprovider.cpp:67
minisketch_deserialize
MINISKETCH_API void minisketch_deserialize(minisketch *sketch, const unsigned char *input)
Deserialize a sketch from bytes.
Definition: minisketch.cpp:448
minisketch_bits_supported
MINISKETCH_API int minisketch_bits_supported(uint32_t bits)
Determine whether support for elements of bits bits was compiled in.
Definition: minisketch.cpp:165
minisketch_destroy
MINISKETCH_API void minisketch_destroy(minisketch *sketch)
Destroy a sketch.
Definition: minisketch.cpp:426
minisketch_implementation
MINISKETCH_API uint32_t minisketch_implementation(const minisketch *sketch)
Get the implementation of a sketch.
Definition: minisketch.cpp:410
minisketch_decode
MINISKETCH_API ssize_t minisketch_decode(const minisketch *sketch, size_t max_elements, uint64_t *output)
Decode a sketch.
Definition: minisketch.cpp:470
minisketch_serialize
MINISKETCH_API void minisketch_serialize(const minisketch *sketch, unsigned char *output)
Serialize a sketch to bytes.
Definition: minisketch.cpp:442
compat.h
minisketch
struct minisketch minisketch
Opaque type for decoded sketches.
Definition: minisketch.h:40
minisketch_compute_capacity
MINISKETCH_API size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits)
Compute the capacity needed to achieve a certain rate of false positives.
Definition: minisketch.cpp:482
minisketch_implementation_max
MINISKETCH_API uint32_t minisketch_implementation_max(void)
Determine the maximum number of implementations available.
Definition: minisketch.cpp:358
minisketch_set_seed
MINISKETCH_API void minisketch_set_seed(minisketch *sketch, uint64_t seed)
Set the seed for randomizing algorithm choices to a fixed value.
Definition: minisketch.cpp:476
minisketch_compute_max_elements
MINISKETCH_API size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits)
Compute what max_elements can be decoded for a certain rate of false positives.
Definition: minisketch.cpp:486
ByteUnit::T
@ T
minisketch_bits
MINISKETCH_API uint32_t minisketch_bits(const minisketch *sketch)
Get the element size of a sketch in bits.
Definition: minisketch.cpp:398
minisketch_add_uint64
MINISKETCH_API void minisketch_add_uint64(minisketch *sketch, uint64_t element)
Add an element to a sketch.
Definition: minisketch.cpp:454
minisketch_clone
MINISKETCH_API minisketch * minisketch_clone(const minisketch *sketch)
Clone a sketch.
Definition: minisketch.cpp:416
Serialize
void Serialize(Stream &s, char a)
Definition: serialize.h:199
minisketch_capacity
MINISKETCH_API size_t minisketch_capacity(const minisketch *sketch)
Get the capacity of a sketch.
Definition: minisketch.cpp:404
minisketch_implementation_supported
MINISKETCH_API int minisketch_implementation_supported(uint32_t bits, uint32_t implementation)
Determine if the a combination of bits and implementation number is available.
Definition: minisketch.cpp:366