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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
#ifndef QF_H
#define QF_H
#include <inttypes.h>
#include <pthread.h>
#include <stdbool.h>
#ifdef __cplusplus
extern "C" {
#endif
struct __attribute__ ((__packed__)) qfblock;
typedef struct qfblock qfblock;
uint64_t shift_into_b2(uint64_t a, uint64_t b, int bstart, int bend, int amount);
typedef struct {
uint64_t total_time_single;
uint64_t total_time_spinning;
uint64_t locks_taken;
uint64_t locks_acquired_single_attempt;
} wait_time_data;
typedef struct quotient_filter_mem {
int fd;
volatile int metadata_lock;
volatile int *locks;
wait_time_data *wait_times;
} quotient_filter_mem;
typedef quotient_filter_mem qfmem;
typedef struct quotient_filter_metadata {
uint64_t size;
uint32_t seed;
uint64_t nslots;
uint64_t xnslots;
uint64_t key_bits;
uint64_t value_bits;
uint64_t key_remainder_bits;
uint64_t bits_per_slot;
uint64_t range;
uint64_t nblocks;
uint64_t nelts;
uint64_t ndistinct_elts;
uint64_t noccupied_slots;
uint64_t num_locks;
} quotient_filter_metadata;
typedef quotient_filter_metadata qfmetadata;
typedef struct quotient_filter {
qfmem *mem;
qfmetadata *metadata;
qfblock *blocks;
} quotient_filter;
typedef quotient_filter QF;
typedef struct {
uint64_t start_index;
uint16_t length;
} cluster_data;
typedef struct quotient_filter_iterator {
QF *qf;
uint64_t run;
uint64_t current;
uint64_t cur_start_index;
uint16_t cur_length;
uint32_t num_clusters;
cluster_data *c_info;
} quotient_filter_iterator;
typedef quotient_filter_iterator QFi;
void qf_init(QF *qf, uint64_t nslots, uint64_t key_bits, uint64_t value_bits, uint32_t seed);
void qf_reset(QF *qf);
void qf_destroy(QF *qf);
void qf_copy(QF *dest, QF *src);
/* Increment the counter for this key/value pair by count. */
bool qf_insert(QF *qf, uint64_t key, uint64_t value, uint64_t count,
bool lock, bool spin);
/* Remove count instances of this key/value combination. */
void qf_remove(QF *qf, uint64_t key, uint64_t value, uint64_t count);
/* Remove all instances of this key/value pair. */
void qf_delete_key_value(QF *qf, uint64_t key, uint64_t value);
/* Remove all instances of this key. */
void qf_delete_key(QF *qf, uint64_t key);
/* Replace the association (key, oldvalue, count) with the association
(key, newvalue, count). If there is already an association (key,
newvalue, count'), then the two associations will be merged and
their counters will be summed, resulting in association (key,
newvalue, count' + count). */
void qf_replace(QF *qf, uint64_t key, uint64_t oldvalue, uint64_t newvalue);
/* Lookup the value associated with key. Returns the count of that
key/value pair in the QF. If it returns 0, then, the key is not
present in the QF. Only returns the first value associated with key
in the QF. If you want to see others, use an iterator. */
uint64_t qf_query(const QF *qf, uint64_t key, uint64_t *value);
/* Return the number of times key has been inserted, with any value,
into qf. */
uint64_t qf_count_key(const QF *qf, uint64_t key);
/* Return the number of times key has been inserted, with the given
value, into qf. */
uint64_t qf_count_key_value(const QF *qf, uint64_t key, uint64_t value, bool lock);
/* Initialize an iterator */
bool qf_iterator(QF *qf, QFi *qfi, uint64_t position);
/* Returns 0 if the iterator is still valid (i.e. has not reached the
end of the QF. */
int qfi_get(QFi *qfi, uint64_t *key, uint64_t *value, uint64_t *count);
/* Advance to next entry. Returns whether or not another entry is
found. */
int qfi_next(QFi *qfi);
/* Check to see if the if the end of the QF */
int qfi_end(QFi *qfi);
/* For debugging */
void qf_dump(const QF *);
/* write data structure of to the disk */
void qf_serialize(const QF *qf, const char *filename);
/* read data structure off the disk */
void qf_deserialize(QF *qf, const char *filename);
/* mmap the QF from disk. */
void qf_read(QF *qf, const char *path);
/* merge two QFs into the third one. */
void qf_merge(QF *qfa, QF *qfb, QF *qfc);
/* merge multiple QFs into the final QF one. */
void qf_multi_merge(QF *qf_arr[], int nqf, QF *qfr);
/* find cosine similarity between two QFs. */
uint64_t qf_inner_product(QF *qfa, QF *qfb);
/* magnitude of a QF. */
uint64_t qf_magnitude(QF *qf);
#ifdef __cplusplus
}
#endif
#endif /* QF_H */
|
