Tor  0.4.7.0-alpha-dev
digestset.c
Go to the documentation of this file.
1 /* Copyright (c) 2018-2021, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
4 /**
5  * \file digestset.c
6  * \brief Implementation for a set of digests
7  **/
8 
9 #include "orconfig.h"
12 #include "lib/defs/digest_sizes.h"
14 #include "ext/siphash.h"
15 
16 /* Wrap our hash function to have the signature that the bloom filter
17  * needs. */
18 static uint64_t
19 bloomfilt_digest_hash(const struct sipkey *key,
20  const void *item)
21 {
22  return siphash24(item, DIGEST_LEN, key);
23 }
24 
25 /**
26  * Allocate and return an digestset, suitable for holding up to
27  * <b>max_guess</b> distinct values.
28  */
29 digestset_t *
30 digestset_new(int max_guess)
31 {
32  uint8_t k[BLOOMFILT_KEY_LEN];
33  crypto_rand((void*)k, sizeof(k));
34  return bloomfilt_new(max_guess, bloomfilt_digest_hash, k);
35 }
36 
37 /**
38  * Add <b>digest</b> to <b>set</b>.
39  *
40  * All future queries for <b>digest</b> in set will return true. Removing
41  * items is not possible.
42  */
43 void
44 digestset_add(digestset_t *set, const char *digest)
45 {
46  bloomfilt_add(set, digest);
47 }
48 
49 /**
50  * Return true if <b>digest</b> is a member of <b>set</b>. (And probably,
51  * return false if <b>digest</b> is not a member of set.)
52  */
53 int
54 digestset_probably_contains(const digestset_t *set,
55  const char *digest)
56 {
57  return bloomfilt_probably_contains(set, digest);
58 }
void bloomfilt_add(bloomfilt_t *set, const void *item)
Definition: bloomfilt.c:38
int bloomfilt_probably_contains(const bloomfilt_t *set, const void *item)
Definition: bloomfilt.c:54
bloomfilt_t * bloomfilt_new(int max_elements, bloomfilt_hash_fn hashfn, const uint8_t *random_key)
Definition: bloomfilt.c:78
Header for bloomfilt.c.
#define BLOOMFILT_KEY_LEN
Definition: bloomfilt.h:26
void crypto_rand(char *to, size_t n)
Definition: crypto_rand.c:477
Common functions for using (pseudo-)random number generators.
Definitions for common sizes of cryptographic digests.
#define DIGEST_LEN
Definition: digest_sizes.h:20
void digestset_add(digestset_t *set, const char *digest)
Definition: digestset.c:44
int digestset_probably_contains(const digestset_t *set, const char *digest)
Definition: digestset.c:54
digestset_t * digestset_new(int max_guess)
Definition: digestset.c:30
Types to handle sets of digests, based on bloom filters.
Definition: siphash.h:6