Bitcoin Core  24.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 <BaseTsd.h>
9  typedef SSIZE_T ssize_t;
10 #else
11 # include <unistd.h>
12 #endif
13 
14 #ifndef MINISKETCH_API
15 # if defined(_WIN32)
16 # ifdef MINISKETCH_BUILD
17 # define MINISKETCH_API __declspec(dllexport)
18 # else
19 # define MINISKETCH_API
20 # endif
21 # elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(MINISKETCH_BUILD)
22 # define MINISKETCH_API __attribute__ ((visibility ("default")))
23 # else
24 # define MINISKETCH_API
25 # endif
26 #endif
27 
28 #ifdef __cplusplus
29 # if __cplusplus >= 201103L
30 # include <memory>
31 # include <vector>
32 # include <cassert>
33 # if __cplusplus >= 201703L
34 # include <optional>
35 # endif // __cplusplus >= 201703L
36 # endif // __cplusplus >= 201103L
37 extern "C" {
38 #endif // __cplusplus
39 
41 typedef struct minisketch minisketch;
42 
44 MINISKETCH_API int minisketch_bits_supported(uint32_t bits);
45 
56 
61 MINISKETCH_API int minisketch_implementation_supported(uint32_t bits, uint32_t implementation);
62 
72 MINISKETCH_API minisketch* minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity);
73 
75 MINISKETCH_API uint32_t minisketch_bits(const minisketch* sketch);
76 
78 MINISKETCH_API size_t minisketch_capacity(const minisketch* sketch);
79 
82 
94 MINISKETCH_API void minisketch_set_seed(minisketch* sketch, uint64_t seed);
95 
101 
107 
110 
112 MINISKETCH_API void minisketch_serialize(const minisketch* sketch, unsigned char* output);
113 
115 MINISKETCH_API void minisketch_deserialize(minisketch* sketch, const unsigned char* input);
116 
130 MINISKETCH_API void minisketch_add_uint64(minisketch* sketch, uint64_t element);
131 
148 MINISKETCH_API size_t minisketch_merge(minisketch* sketch, const minisketch* other_sketch);
149 
157 MINISKETCH_API ssize_t minisketch_decode(const minisketch* sketch, size_t max_elements, uint64_t* output);
158 
171 MINISKETCH_API size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits);
172 
189 MINISKETCH_API size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits);
190 
191 #ifdef __cplusplus
192 }
193 
194 #if __cplusplus >= 201103L
196 class Minisketch
197 {
198  struct Deleter
199  {
200  void operator()(minisketch* ptr) const
201  {
202  minisketch_destroy(ptr);
203  }
204  };
205 
206  std::unique_ptr<minisketch, Deleter> m_minisketch;
207 
208 public:
210  static bool BitsSupported(uint32_t bits) noexcept { return minisketch_bits_supported(bits); }
211 
213  static uint32_t MaxImplementation() noexcept { return minisketch_implementation_max(); }
214 
219  static bool ImplementationSupported(uint32_t bits, uint32_t implementation) noexcept { return minisketch_implementation_supported(bits, implementation); }
220 
226  static size_t ComputeCapacity(uint32_t bits, size_t max_elements, uint32_t fpbits) noexcept { return minisketch_compute_capacity(bits, max_elements, fpbits); }
227 
229  static size_t ComputeMaxElements(uint32_t bits, size_t capacity, uint32_t fpbits) noexcept { return minisketch_compute_max_elements(bits, capacity, fpbits); }
230 
232  Minisketch(const Minisketch& sketch) noexcept
233  {
234  if (sketch.m_minisketch) {
235  m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_clone(sketch.m_minisketch.get()));
236  }
237  }
238 
240  Minisketch& operator=(const Minisketch& sketch) noexcept
241  {
242  if (sketch.m_minisketch) {
243  m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_clone(sketch.m_minisketch.get()));
244  }
245  return *this;
246  }
247 
249  explicit operator bool() const noexcept { return bool{m_minisketch}; }
250 
252  Minisketch() noexcept = default;
253 
255  Minisketch(Minisketch&&) noexcept = default;
256 
258  Minisketch& operator=(Minisketch&&) noexcept = default;
259 
266  Minisketch(uint32_t bits, uint32_t implementation, size_t capacity) noexcept
267  {
268  m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_create(bits, implementation, capacity));
269  }
270 
273  static Minisketch CreateFP(uint32_t bits, uint32_t implementation, size_t max_elements, uint32_t fpbits) noexcept
274  {
275  return Minisketch(bits, implementation, ComputeCapacity(bits, max_elements, fpbits));
276  }
277 
279  uint32_t GetBits() const noexcept { return minisketch_bits(m_minisketch.get()); }
280 
282  size_t GetCapacity() const noexcept { return minisketch_capacity(m_minisketch.get()); }
283 
285  uint32_t GetImplementation() const noexcept { return minisketch_implementation(m_minisketch.get()); }
286 
288  Minisketch& SetSeed(uint64_t seed) noexcept
289  {
290  minisketch_set_seed(m_minisketch.get(), seed);
291  return *this;
292  }
293 
296  Minisketch& Add(uint64_t element) noexcept
297  {
298  minisketch_add_uint64(m_minisketch.get(), element);
299  return *this;
300  }
301 
304  Minisketch& Merge(const Minisketch& sketch) noexcept
305  {
306  minisketch_merge(m_minisketch.get(), sketch.m_minisketch.get());
307  return *this;
308  }
309 
312  bool Decode(std::vector<uint64_t>& result) const
313  {
314  ssize_t ret = minisketch_decode(m_minisketch.get(), result.size(), result.data());
315  if (ret == -1) return false;
316  result.resize(ret);
317  return true;
318  }
319 
321  size_t GetSerializedSize() const noexcept { return minisketch_serialized_size(m_minisketch.get()); }
322 
324  std::vector<unsigned char> Serialize() const
325  {
326  std::vector<unsigned char> result(GetSerializedSize());
327  minisketch_serialize(m_minisketch.get(), result.data());
328  return result;
329  }
330 
333  template<typename T>
334  Minisketch& Deserialize(
335  const T& obj,
336  typename std::enable_if<
337  std::is_convertible<typename std::remove_pointer<decltype(obj.data())>::type (*)[], const unsigned char (*)[]>::value &&
338  std::is_convertible<decltype(obj.size()), std::size_t>::value,
339  std::nullptr_t
340  >::type = nullptr) noexcept
341  {
342  assert(GetSerializedSize() == obj.size());
343  minisketch_deserialize(m_minisketch.get(), obj.data());
344  return *this;
345  }
346 
347 #if __cplusplus >= 201703L
349  std::optional<std::vector<uint64_t>> Decode(size_t max_elements) const
350  {
351  std::vector<uint64_t> result(max_elements);
352  ssize_t ret = minisketch_decode(m_minisketch.get(), max_elements, result.data());
353  if (ret == -1) return {};
354  result.resize(ret);
355  return result;
356  }
357 
359  std::optional<std::vector<uint64_t>> DecodeFP(uint32_t fpbits) const
360  {
361  return Decode(ComputeMaxElements(GetBits(), GetCapacity(), fpbits));
362  }
363 #endif // __cplusplus >= 201703L
364 };
365 #endif // __cplusplus >= 201103L
366 #endif // __cplusplus
367 
368 #endif // _MINISKETCH_H_
int ret
MINISKETCH_API void minisketch_serialize(const minisketch *sketch, unsigned char *output)
Serialize a sketch to bytes.
Definition: minisketch.cpp:440
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:378
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:474
MINISKETCH_API uint32_t minisketch_implementation(const minisketch *sketch)
Get the implementation of a sketch.
Definition: minisketch.cpp:408
MINISKETCH_API size_t minisketch_capacity(const minisketch *sketch)
Get the capacity of a sketch.
Definition: minisketch.cpp:402
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:480
MINISKETCH_API ssize_t minisketch_decode(const minisketch *sketch, size_t max_elements, uint64_t *output)
Decode a sketch.
Definition: minisketch.cpp:468
MINISKETCH_API int minisketch_bits_supported(uint32_t bits)
Determine whether support for elements of bits bits was compiled in.
Definition: minisketch.cpp:163
MINISKETCH_API size_t minisketch_merge(minisketch *sketch, const minisketch *other_sketch)
Merge the elements of another sketch into this sketch.
Definition: minisketch.cpp:458
MINISKETCH_API size_t minisketch_serialized_size(const minisketch *sketch)
Compute the size in bytes for serializing a given sketch.
Definition: minisketch.cpp:432
#define MINISKETCH_API
Definition: minisketch.h:24
MINISKETCH_API uint32_t minisketch_implementation_max(void)
Determine the maximum number of implementations available.
Definition: minisketch.cpp:356
MINISKETCH_API void minisketch_add_uint64(minisketch *sketch, uint64_t element)
Add an element to a sketch.
Definition: minisketch.cpp:452
MINISKETCH_API uint32_t minisketch_bits(const minisketch *sketch)
Get the element size of a sketch in bits.
Definition: minisketch.cpp:396
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:484
MINISKETCH_API void minisketch_deserialize(minisketch *sketch, const unsigned char *input)
Deserialize a sketch from bytes.
Definition: minisketch.cpp:446
MINISKETCH_API void minisketch_destroy(minisketch *sketch)
Destroy a sketch.
Definition: minisketch.cpp:424
struct minisketch minisketch
Opaque type for decoded sketches.
Definition: minisketch.h:41
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:364
MINISKETCH_API minisketch * minisketch_clone(const minisketch *sketch)
Clone a sketch.
Definition: minisketch.cpp:414
DecodeResult Decode(const std::string &str)
Decode a Bech32 or Bech32m string.
Definition: bech32.cpp:373
void Serialize(Stream &, char)=delete
assert(!tx.IsCoinBase())