xs/bloom.xs

filter: Statementstmt 95.3% 62 / 65 Branchbran 58.0% 29 / 50 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 79.1% 91 / 115 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/sa/sa_cuckoo.h ↑ Summary xs/ring.xs »
1 # Shared::Arena::Bloom - a set that answers "no" exactly and "yes" probably.
2  
3 MODULE = Shared::Arena PACKAGE = Shared::Arena PREFIX = sar_
4  
5 # $arena->bloom($name, capacity => N, fp_rate => 0.01)
6 #
7 # Sized from what you expect to put in it and the false-positive rate you will
8 # accept, because those are the numbers a caller actually has. `bits` and
9 # `hashes` are there for a caller who has already done the arithmetic.
10 SV *
11 sar_bloom(self, name, ...)
12 SV *self
13 SV *name
14 PREINIT:
15 sa_region *arena;
16 sa_reg *e;
17 sa_bloom *b;
18 const char *nm;
19 STRLEN nlen;
20 13 UV capacity = 10000, bits = 0, hashes = 0;
21 13 double fp = 0.01;
22 13 uint64_t nbits = 0;
23 13 uint32_t k = 0;
24 13 int err = SA_E_OK;
25 I32 i;
26 SV *obj;
27 CODE:
28 13 arena = SA_SELF(sa_region, self);
29 13 ▶ if (!arena || !arena->map.base)
Branch: 2 branches
BranchTrueFalseTotal
if (!arena || !arena->map.base) 13 0 13
if (!arena || !arena->map.base) 0 13 13
30 0 croak("Shared::Arena: this region is released");
31 13 nm = SvPV(name, nlen);
32 34 ▶ for (i = 2; i + 1 < items; i += 2) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 2; i + 1 < items; i += 2) { 21 13 34
33 21 const char *o = SvPV_nolen(ST(i));
34 21 ▶ if (strEQ(o, "capacity")) capacity = SvUV(ST(i + 1));
Branch: 1 branch
BranchTrueFalseTotal
if (strEQ(o, "capacity")) capacity = SvUV(ST(i + 1)); 12 9 21
35 9 ▶ else if (strEQ(o, "fp_rate")) fp = SvNV(ST(i + 1));
Branch: 1 branch
BranchTrueFalseTotal
else if (strEQ(o, "fp_rate")) fp = SvNV(ST(i + 1)); 7 2 9
36 2 ▶ else if (strEQ(o, "bits")) bits = SvUV(ST(i + 1));
Branch: 1 branch
BranchTrueFalseTotal
else if (strEQ(o, "bits")) bits = SvUV(ST(i + 1)); 1 1 2
37 1 ▶ else if (strEQ(o, "hashes")) hashes = SvUV(ST(i + 1));
Branch: 1 branch
BranchTrueFalseTotal
else if (strEQ(o, "hashes")) hashes = SvUV(ST(i + 1)); 1 0 1
38 }
39 13 ▶ if (bits) {
Branch: 1 branch
BranchTrueFalseTotal
if (bits) { 1 12 13
40 1 nbits = sa_bloom_words((uint64_t)bits) * 64u;
41 1 ▶ k = hashes ? (uint32_t)hashes : 5;
Branch: 1 branch
BranchTrueFalseTotal
k = hashes ? (uint32_t)hashes : 5; 1 0 1
42 1 ▶ if (k > SA_BLOOM_MAX_K) k = SA_BLOOM_MAX_K;
Branch: 1 branch
BranchTrueFalseTotal
if (k > SA_BLOOM_MAX_K) k = SA_BLOOM_MAX_K; 0 1 1
43 }
44 else {
45 12 sa_bloom_size((uint64_t)capacity, fp, &nbits, &k);
46 12 ▶ if (hashes) {
Branch: 1 branch
BranchTrueFalseTotal
if (hashes) { 0 12 12
47 0 k = (uint32_t)hashes;
48 0 ▶ if (k > SA_BLOOM_MAX_K) k = SA_BLOOM_MAX_K;
Branch: 1 branch
BranchTrueFalseTotal
if (k > SA_BLOOM_MAX_K) k = SA_BLOOM_MAX_K; 0 0 0
49 }
50 }
51  
52 13 e = sa_carve(arena, nm, (size_t)nlen, sa_bloom_bytes(nbits),
53 SA_T_BLOOM, &err);
54 13 ▶ if (!e) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err));
Branch: 1 branch
BranchTrueFalseTotal
if (!e) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err)); 0 13 13
55  
56 13 b = sa_bloom_bind(arena, e, nbits, k, &err);
57 13 ▶ if (!b) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err));
Branch: 1 branch
BranchTrueFalseTotal
if (!b) croak("Shared::Arena: the filter '%s' %s", nm, sa_strerror(err)); 0 13 13
58 13 b->hdr->capacity = (uint64_t)capacity;
59  
60 13 obj = newSV(0);
61 13 sv_setref_pv(obj, "Shared::Arena::Bloom", (void *)b);
62 13 sv_magicext(SvRV(obj), SvRV(self), PERL_MAGIC_ext, NULL, NULL, 0);
63 13 SvREFCNT_inc(SvRV(self));
64 13 RETVAL = obj;
65 OUTPUT:
66 RETVAL
67  
68 MODULE = Shared::Arena PACKAGE = Shared::Arena::Bloom PREFIX = sab_
69  
70 # 1 when the key had already been added, 0 when this call added it.
71 #
72 # The answer is per BIT and not per key: two processes adding the same key at
73 # the same instant may both be told it was new. Harmless for a filter; not good
74 # enough to do a job exactly once.
75 int
76 sab_add(self, key)
77 SV *self
78 SV *key
79 PREINIT:
80 sa_bloom *b;
81 const char *k;
82 STRLEN klen;
83 CODE:
84 2 b = SA_SELF(sa_bloom, self);
85 2 ▶ if (!b) croak("Shared::Arena::Bloom: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!b) croak("Shared::Arena::Bloom: this filter is released"); 0 2 2
86 2 k = SvPV(key, klen);
87 2 RETVAL = sa_bloom_add(b, k, (uint32_t)klen);
88 OUTPUT:
89 RETVAL
90  
91 # A false answer is exact. A true one is probably right.
92 int
93 sab_check(self, key)
94 SV *self
95 SV *key
96 PREINIT:
97 sa_bloom *b;
98 const char *k;
99 STRLEN klen;
100 CODE:
101 2 b = SA_SELF(sa_bloom, self);
102 2 ▶ if (!b) croak("Shared::Arena::Bloom: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!b) croak("Shared::Arena::Bloom: this filter is released"); 0 2 2
103 2 k = SvPV(key, klen);
104 2 RETVAL = sa_bloom_check(b, k, (uint32_t)klen);
105 OUTPUT:
106 RETVAL
107  
108 void
109 sab_reset(self)
110 SV *self
111 PREINIT:
112 sa_bloom *b;
113 CODE:
114 1 b = SA_SELF(sa_bloom, self);
115 1 ▶ if (!b) croak("Shared::Arena::Bloom: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!b) croak("Shared::Arena::Bloom: this filter is released"); 0 1 1
116 1 sa_bloom_reset(b);
117  
118 UV
119 sab_bits(self)
120 SV *self
121 PREINIT:
122 sa_bloom *b;
123 CODE:
124 5 b = SA_SELF(sa_bloom, self);
125 5 ▶ if (!b) croak("Shared::Arena::Bloom: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!b) croak("Shared::Arena::Bloom: this filter is released"); 0 5 5
126 5 ▶ RETVAL = (UV)b->nbits;
Branch: 1 branch
BranchTrueFalseTotal
RETVAL = (UV)b->nbits; 0 5 5
127 OUTPUT:
128 RETVAL
129  
130 UV
131 sab_hashes(self)
132 SV *self
133 PREINIT:
134 sa_bloom *b;
135 CODE:
136 5 b = SA_SELF(sa_bloom, self);
137 5 ▶ if (!b) croak("Shared::Arena::Bloom: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!b) croak("Shared::Arena::Bloom: this filter is released"); 0 5 5
138 5 ▶ RETVAL = (UV)b->nhash;
Branch: 1 branch
BranchTrueFalseTotal
RETVAL = (UV)b->nhash; 0 5 5
139 OUTPUT:
140 RETVAL
141  
142 # bits / hashes / set / added / seen / estimated / capacity / fill
143 #
144 # `fill` is the fraction of bits set, and it is the number that says whether the
145 # filter is still delivering the rate it was sized for. Counting the set bits
146 # walks the whole array, so this belongs on a status page and not in a loop.
147 void
148 sab_stats(self)
149 SV *self
150 PREINIT:
151 sa_bloom *b;
152 uint64_t set;
153 PPCODE:
154 5 b = SA_SELF(sa_bloom, self);
155 5 ▶ if (!b) croak("Shared::Arena::Bloom: this filter is released");
Branch: 1 branch
BranchTrueFalseTotal
if (!b) croak("Shared::Arena::Bloom: this filter is released"); 0 5 5
156 5 set = sa_bloom_popcount(b);
157 5 ▶ EXTEND(SP, 16);
Branch: 1 branch
BranchTrueFalseTotal
EXTEND(SP, 16); 0 5 5
158 5 mPUSHp("bits", 4); mPUSHu((UV)b->nbits);
159 5 mPUSHp("hashes", 6); mPUSHu((UV)b->nhash);
160 5 mPUSHp("set", 3); mPUSHu((UV)set);
161 5 mPUSHp("added", 5); mPUSHu((UV)sa_at_load64_acq(&b->hdr->added));
162 5 mPUSHp("seen", 4); mPUSHu((UV)sa_at_load64_acq(&b->hdr->seen));
163 5 mPUSHp("estimated", 9); mPUSHu((UV)sa_bloom_estimate(b));
164 5 mPUSHp("capacity", 8); mPUSHu((UV)b->hdr->capacity);
165 5 mPUSHp("fill", 4);
166 5 ▶ mPUSHn(b->nbits ? (double)set / (double)b->nbits : 0.0);
Branch: 1 branch
BranchTrueFalseTotal
mPUSHn(b->nbits ? (double)set / (double)b->nbits : 0.0); 5 0 5
167  
168 void
169 sab_DESTROY(self)
170 SV *self
171 PREINIT:
172 sa_bloom *b;
173 CODE:
174 13 b = SA_SELF(sa_bloom, self);
175 13 ▶ if (b) { sa_bloom_free(b); sv_setiv(SvRV(self), 0); }
Branch: 1 branch
BranchTrueFalseTotal
if (b) { sa_bloom_free(b); sv_setiv(SvRV(self), 0); } 13 0 13
« include/sa/sa_cuckoo.h ↑ Summary xs/ring.xs »