| 1 |
|
| # HAMT::Set. The trie is the map's with entries that carry no value, so |
| 2 |
|
| # membership, add and remove are the map's lookup, put and delete; what is a |
| 3 |
|
| # set's own is the algebra. |
| 4 |
|
| |
| 5 |
|
| MODULE = HAMT PACKAGE = HAMT::Set |
| 6 |
|
| |
| 7 |
|
| void |
| 8 |
|
| new(klass, ...) |
| 9 |
|
| SV *klass |
| 10 |
|
| PREINIT: |
| 11 |
|
| hamt_map *m; |
| 12 |
|
| SV *obj; |
| 13 |
|
| I32 i; |
| 14 |
|
| CODE: |
| 15 |
2848 |
| obj = hamt_handle_new(aTHX_ &hamt_set_vtbl, hamt_class_stash(aTHX_ klass), |
| 16 |
|
| NULL, 0, &m, "HAMT::Set::new"); |
| 17 |
398530 |
▶ | for (i = 1; i < items; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 1; i < items; i++) |
395682 |
2848 |
398530 |
|
| 18 |
395682 |
| hamt_xs_put(aTHX_ m, ST(i), NULL, "HAMT::Set::new"); |
| 19 |
2848 |
| ST(0) = obj; |
| 20 |
2848 |
| XSRETURN(1); |
| 21 |
|
| |
| 22 |
|
| void |
| 23 |
|
| add(self, ...) |
| 24 |
|
| SV *self |
| 25 |
|
| PREINIT: |
| 26 |
|
| hamt_map *m, *n; |
| 27 |
|
| hamt_node *was; |
| 28 |
|
| SV *obj; |
| 29 |
|
| I32 i; |
| 30 |
|
| CODE: |
| 31 |
732 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::add", "set"); |
| 32 |
732 |
| was = m->root; |
| 33 |
732 |
▶ | if (GIMME_V == G_VOID) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (GIMME_V == G_VOID) { |
3 |
729 |
732 |
|
| 34 |
3 |
| hamt_void_warn(aTHX_ "HAMT::Set::add"); |
| 35 |
3 |
| XSRETURN_EMPTY; |
| 36 |
|
| } |
| 37 |
729 |
| obj = hamt_handle_new(aTHX_ &hamt_set_vtbl, SvSTASH(SvRV(self)), |
| 38 |
|
| m->root, m->count, &n, "HAMT::Set::add"); |
| 39 |
1461 |
▶ | for (i = 1; i < items; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 1; i < items; i++) |
732 |
729 |
1461 |
|
| 40 |
732 |
| hamt_xs_put(aTHX_ n, ST(i), NULL, "HAMT::Set::add"); |
| 41 |
729 |
▶ | if (n->root != was) ST(0) = obj; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n->root != was) ST(0) = obj; |
467 |
262 |
729 |
|
| 42 |
729 |
| XSRETURN(1); |
| 43 |
|
| |
| 44 |
|
| void |
| 45 |
|
| remove(self, ...) |
| 46 |
|
| SV *self |
| 47 |
|
| PREINIT: |
| 48 |
|
| hamt_map *m, *n; |
| 49 |
|
| hamt_node *was; |
| 50 |
|
| SV *obj; |
| 51 |
|
| I32 i; |
| 52 |
|
| CODE: |
| 53 |
720 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::remove", "set"); |
| 54 |
720 |
| was = m->root; |
| 55 |
720 |
▶ | if (GIMME_V == G_VOID) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (GIMME_V == G_VOID) { |
1 |
719 |
720 |
|
| 56 |
1 |
| hamt_void_warn(aTHX_ "HAMT::Set::remove"); |
| 57 |
1 |
| XSRETURN_EMPTY; |
| 58 |
|
| } |
| 59 |
719 |
| obj = hamt_handle_new(aTHX_ &hamt_set_vtbl, SvSTASH(SvRV(self)), |
| 60 |
|
| m->root, m->count, &n, "HAMT::Set::remove"); |
| 61 |
1443 |
▶ | for (i = 1; i < items; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 1; i < items; i++) |
724 |
719 |
1443 |
|
| 62 |
724 |
| hamt_xs_del(aTHX_ n, ST(i), "HAMT::Set::remove"); |
| 63 |
719 |
▶ | if (n->root != was) ST(0) = obj; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n->root != was) ST(0) = obj; |
253 |
466 |
719 |
|
| 64 |
719 |
| XSRETURN(1); |
| 65 |
|
| |
| 66 |
|
| void |
| 67 |
|
| has(self, member) |
| 68 |
|
| SV *self |
| 69 |
|
| SV *member |
| 70 |
|
| PREINIT: |
| 71 |
|
| hamt_map *m; |
| 72 |
|
| hamt_key k; |
| 73 |
|
| CODE: |
| 74 |
139 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::has", "set"); |
| 75 |
138 |
| hamt_key_from_sv(aTHX_ member, &k); |
| 76 |
138 |
▶ | ST(0) = boolSV(hamt_map_find(m->root, k.p, (size_t)k.len, k.utf8, k.hash) != NULL); |
Branch: 1 branch
| Branch | True | False | Total |
| ST(0) = boolSV(hamt_map_find(m->root, k.p, (size_t)k.len, k.utf8, k.hash) != NULL); |
73 |
65 |
138 |
|
| 77 |
138 |
| XSRETURN(1); |
| 78 |
|
| |
| 79 |
|
| void |
| 80 |
|
| count(self) |
| 81 |
|
| SV *self |
| 82 |
|
| PREINIT: |
| 83 |
|
| hamt_map *m; |
| 84 |
|
| CODE: |
| 85 |
4995 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::count", "set"); |
| 86 |
4992 |
| ST(0) = sv_2mortal(newSVuv((UV)m->count)); |
| 87 |
4992 |
| XSRETURN(1); |
| 88 |
|
| |
| 89 |
|
| void |
| 90 |
|
| members(self) |
| 91 |
|
| SV *self |
| 92 |
|
| PREINIT: |
| 93 |
|
| hamt_map *m; |
| 94 |
|
| hamt_iter it; |
| 95 |
|
| hamt_entry *e; |
| 96 |
|
| PPCODE: |
| 97 |
8268 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::members", "set"); |
| 98 |
8268 |
▶ | if (GIMME_V == G_VOID) XSRETURN_EMPTY; |
Branch: 1 branch
| Branch | True | False | Total |
| if (GIMME_V == G_VOID) XSRETURN_EMPTY; |
1 |
8267 |
8268 |
|
| 99 |
8267 |
▶ | if (GIMME_V == G_SCALAR) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (GIMME_V == G_SCALAR) { |
1 |
8266 |
8267 |
|
| 100 |
1 |
| PUSHs(sv_2mortal(newSVuv((UV)m->count))); |
| 101 |
1 |
| XSRETURN(1); |
| 102 |
|
| } |
| 103 |
8266 |
▶ | if (m->count > ((size_t)-1 >> 2)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (m->count > ((size_t)-1 >> 2)) |
0 |
8266 |
8266 |
|
| 104 |
0 |
| croak("HAMT::Set::members: too many members for one list"); |
| 105 |
8266 |
▶ | EXTEND(SP, (SSize_t)m->count); |
Branch: 2 branches
| Branch | True | False | Total |
| EXTEND(SP, (SSize_t)m->count); |
8266 |
0 |
8266 |
| EXTEND(SP, (SSize_t)m->count); |
0 |
8266 |
8266 |
|
| 106 |
8266 |
| hamt_iter_init(&it, m->root); |
| 107 |
1042419 |
▶ | while ((e = hamt_iter_next(&it))) |
Branch: 1 branch
| Branch | True | False | Total |
| while ((e = hamt_iter_next(&it))) |
1034153 |
8266 |
1042419 |
|
| 108 |
1034153 |
| PUSHs(sv_2mortal(hamt_key_to_sv(aTHX_ e))); |
| 109 |
|
| |
| 110 |
|
| void |
| 111 |
|
| each(self, code) |
| 112 |
|
| SV *self |
| 113 |
|
| SV *code |
| 114 |
|
| PREINIT: |
| 115 |
|
| hamt_map *m; |
| 116 |
|
| hamt_node *root; |
| 117 |
|
| hamt_iter it; |
| 118 |
|
| hamt_entry *e; |
| 119 |
8 |
| SV *keysv = NULL, *err = NULL; |
| 120 |
|
| int how; |
| 121 |
|
| CODE: |
| 122 |
8 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::each", "set"); |
| 123 |
8 |
| hamt_xs_need_code(aTHX_ code, "HAMT::Set::each"); |
| 124 |
7 |
| root = m->root; |
| 125 |
7 |
| ENTER; |
| 126 |
7 |
| SAVETMPS; |
| 127 |
7 |
| hamt_xs_hold_root(aTHX_ root); |
| 128 |
7 |
| hamt_xs_walk_enter(aTHX); |
| 129 |
7 |
| hamt_iter_init(&it, root); |
| 130 |
915 |
▶ | while ((e = hamt_iter_next(&it))) { |
Branch: 1 branch
| Branch | True | False | Total |
| while ((e = hamt_iter_next(&it))) { |
911 |
4 |
915 |
|
| 131 |
911 |
| keysv = hamt_xs_scratch(aTHX_ keysv); |
| 132 |
911 |
| sv_setpvn(keysv, e->key, (STRLEN)e->klen); |
| 133 |
911 |
▶ | if (e->utf8) SvUTF8_on(keysv); else SvUTF8_off(keysv); |
Branch: 1 branch
| Branch | True | False | Total |
| if (e->utf8) SvUTF8_on(keysv); else SvUTF8_off(keysv); |
0 |
911 |
911 |
|
| 134 |
911 |
| how = hamt_xs_call(aTHX_ code, &keysv, 1, NULL); |
| 135 |
911 |
▶ | if (how == HAMT_XS_LAST || (err = hamt_xs_call_err(aTHX_ how, 1))) break; |
Branch: 2 branches
| Branch | True | False | Total |
| if (how == HAMT_XS_LAST || (err = hamt_xs_call_err(aTHX_ how, 1))) break; |
910 |
1 |
911 |
| if (how == HAMT_XS_LAST || (err = hamt_xs_call_err(aTHX_ how, 1))) break; |
908 |
2 |
910 |
|
| 136 |
|
| } |
| 137 |
7 |
| hamt_xs_call_leave(aTHX); |
| 138 |
7 |
▶ | FREETMPS; |
Branch: 1 branch
| Branch | True | False | Total |
| FREETMPS; |
7 |
0 |
7 |
|
| 139 |
7 |
| LEAVE; |
| 140 |
7 |
▶ | if (err) hamt_xs_rethrow(aTHX_ err); |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) hamt_xs_rethrow(aTHX_ err); |
2 |
5 |
7 |
|
| 141 |
5 |
| XSRETURN(1); |
| 142 |
|
| |
| 143 |
|
| # union, intersect and difference share a body. None of them runs Perl, so |
| 144 |
|
| # nothing needs holding across the walk; each returns the receiver itself |
| 145 |
|
| # when the result is the receiver, and union returns the other set when the |
| 146 |
|
| # result is that and it is of the receiver's class. |
| 147 |
|
| void |
| 148 |
|
| union(self, other) |
| 149 |
|
| SV *self |
| 150 |
|
| SV *other |
| 151 |
|
| ALIAS: |
| 152 |
|
| intersect = 1 |
| 153 |
|
| difference = 2 |
| 154 |
|
| PREINIT: |
| 155 |
|
| hamt_map *m, *o, *n; |
| 156 |
|
| hamt_node *r; |
| 157 |
5020 |
| size_t count = 0; |
| 158 |
5020 |
| int err = 0; |
| 159 |
|
| HV *stash; |
| 160 |
|
| static const char *const name[3] = { |
| 161 |
|
| "HAMT::Set::union", "HAMT::Set::intersect", "HAMT::Set::difference" |
| 162 |
|
| }; |
| 163 |
|
| CODE: |
| 164 |
5020 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, name[ix], "set"); |
| 165 |
5020 |
| o = hamt_handle(aTHX_ other, &hamt_set_vtbl, name[ix], "set"); |
| 166 |
5017 |
▶ | if (GIMME_V == G_VOID) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (GIMME_V == G_VOID) { |
4 |
5013 |
5017 |
|
| 167 |
4 |
| hamt_void_warn(aTHX_ name[ix]); |
| 168 |
4 |
| XSRETURN_EMPTY; |
| 169 |
|
| } |
| 170 |
5013 |
| stash = SvSTASH(SvRV(self)); |
| 171 |
5013 |
▶ | if (ix == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (ix == 0) { |
1675 |
3338 |
5013 |
|
| 172 |
|
| hamt_merge_ctx c; |
| 173 |
1675 |
| c.cx = HAMT_CX; |
| 174 |
1675 |
| c.resolve = NULL; |
| 175 |
1675 |
| c.ud = NULL; |
| 176 |
1675 |
| r = hamt_map_merge(&c, m->root, o->root); |
| 177 |
1675 |
| err = c.err; |
| 178 |
1675 |
| count = m->count + c.added; |
| 179 |
|
| } |
| 180 |
|
| else { |
| 181 |
|
| hamt_set_ctx c; |
| 182 |
3338 |
| c.cx = HAMT_CX; |
| 183 |
1672 |
| r = ix == 1 ? hamt_set_intersect(&c, m->root, o->root, m->count, o->count, &count) |
| 184 |
3338 |
▶ | : hamt_set_subtract(&c, m->root, o->root, m->count, o->count, &count); |
Branch: 1 branch
| Branch | True | False | Total |
| : hamt_set_subtract(&c, m->root, o->root, m->count, o->count, &count); |
1672 |
1666 |
3338 |
|
| 185 |
3338 |
| err = c.err; |
| 186 |
|
| } |
| 187 |
5013 |
▶ | if (err) croak("%s: out of memory", name[ix]); |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) croak("%s: out of memory", name[ix]); |
0 |
5013 |
5013 |
|
| 188 |
|
| |
| 189 |
5013 |
▶ | if (r == m->root) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (r == m->root) { |
1197 |
3816 |
5013 |
|
| 190 |
1197 |
▶ | if (r) hamt_node_release(HAMT_CX, r); |
Branch: 1 branch
| Branch | True | False | Total |
| if (r) hamt_node_release(HAMT_CX, r); |
1196 |
1 |
1197 |
|
| 191 |
1197 |
| XSRETURN(1); |
| 192 |
|
| } |
| 193 |
3816 |
▶ | if (ix == 0 && r == o->root && SvSTASH(SvRV(other)) == stash) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (ix == 0 && r == o->root && SvSTASH(SvRV(other)) == stash) { |
1412 |
2404 |
3816 |
| if (ix == 0 && r == o->root && SvSTASH(SvRV(other)) == stash) { |
195 |
1217 |
1412 |
| if (ix == 0 && r == o->root && SvSTASH(SvRV(other)) == stash) { |
194 |
1 |
195 |
|
| 194 |
194 |
▶ | if (r) hamt_node_release(HAMT_CX, r); |
Branch: 1 branch
| Branch | True | False | Total |
| if (r) hamt_node_release(HAMT_CX, r); |
194 |
0 |
194 |
|
| 195 |
194 |
| ST(0) = other; |
| 196 |
194 |
| XSRETURN(1); |
| 197 |
|
| } |
| 198 |
|
| /* The new handle takes a reference of its own; the one the walk |
| 199 |
|
| * returned is released whether or not making the handle works. */ |
| 200 |
3622 |
| ENTER; |
| 201 |
3622 |
▶ | if (r) SAVEDESTRUCTOR_X(hamt_xs_root_unref, r); |
Branch: 1 branch
| Branch | True | False | Total |
| if (r) SAVEDESTRUCTOR_X(hamt_xs_root_unref, r); |
2689 |
933 |
3622 |
|
| 202 |
3622 |
| ST(0) = hamt_handle_new(aTHX_ &hamt_set_vtbl, stash, r, count, &n, name[ix]); |
| 203 |
3622 |
| LEAVE; |
| 204 |
3622 |
| XSRETURN(1); |
| 205 |
|
| |
| 206 |
|
| void |
| 207 |
|
| is_subset(self, other) |
| 208 |
|
| SV *self |
| 209 |
|
| SV *other |
| 210 |
|
| ALIAS: |
| 211 |
|
| is_disjoint = 1 |
| 212 |
|
| PREINIT: |
| 213 |
|
| hamt_map *m, *o; |
| 214 |
|
| size_t visits; |
| 215 |
|
| static const char *const name[2] = { "HAMT::Set::is_subset", "HAMT::Set::is_disjoint" }; |
| 216 |
|
| CODE: |
| 217 |
3320 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, name[ix], "set"); |
| 218 |
3320 |
| o = hamt_handle(aTHX_ other, &hamt_set_vtbl, name[ix], "set"); |
| 219 |
3318 |
▶ | ST(0) = boolSV(ix == 0 |
Branch: 2 branches
| Branch | True | False | Total |
| ST(0) = boolSV(ix == 0 |
1659 |
1659 |
3318 |
| ST(0) = boolSV(ix == 0 |
942 |
2376 |
3318 |
|
| 220 |
|
| ? hamt_set_subset(m->root, o->root, m->count, o->count, &visits) |
| 221 |
|
| : hamt_set_disjoint(m->root, o->root, &visits)); |
| 222 |
3318 |
| XSRETURN(1); |
| 223 |
|
| |
| 224 |
|
| void |
| 225 |
|
| equals(self, other) |
| 226 |
|
| SV *self |
| 227 |
|
| SV *other |
| 228 |
|
| PREINIT: |
| 229 |
|
| hamt_map *m, *o; |
| 230 |
|
| hamt_eq_ctx c; |
| 231 |
|
| CODE: |
| 232 |
1670 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::equals", "set"); |
| 233 |
1670 |
| o = hamt_handle_try(aTHX_ other, &hamt_set_vtbl); |
| 234 |
1670 |
▶ | if (!o || o->count != m->count) XSRETURN_NO; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!o || o->count != m->count) XSRETURN_NO; |
1666 |
4 |
1670 |
| if (!o || o->count != m->count) XSRETURN_NO; |
1426 |
240 |
1666 |
|
| 235 |
240 |
| c.cx = HAMT_CX; |
| 236 |
240 |
| c.eq = NULL; |
| 237 |
240 |
| c.ud = NULL; |
| 238 |
240 |
| c.visits = 0; |
| 239 |
240 |
▶ | ST(0) = boolSV(hamt_node_equal(&c, m->root, o->root) > 0); |
Branch: 1 branch
| Branch | True | False | Total |
| ST(0) = boolSV(hamt_node_equal(&c, m->root, o->root) > 0); |
188 |
52 |
240 |
|
| 240 |
240 |
| XSRETURN(1); |
| 241 |
|
| |
| 242 |
|
| void |
| 243 |
|
| transient(self) |
| 244 |
|
| SV *self |
| 245 |
|
| PREINIT: |
| 246 |
|
| hamt_map *m; |
| 247 |
|
| CODE: |
| 248 |
6 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::transient", "set"); |
| 249 |
12 |
| ST(0) = hamt_txn_new(aTHX_ &hamt_set_txn_vtbl, "HAMT::Set::Transient", |
| 250 |
6 |
| SvSTASH(SvRV(self)), m->root, m->count, |
| 251 |
|
| "HAMT::Set::transient"); |
| 252 |
6 |
| XSRETURN(1); |
| 253 |
|
| |
| 254 |
|
| void |
| 255 |
|
| _check(self) |
| 256 |
|
| SV *self |
| 257 |
|
| PREINIT: |
| 258 |
|
| hamt_map *m; |
| 259 |
|
| CODE: |
| 260 |
4958 |
| m = hamt_handle(aTHX_ self, &hamt_set_vtbl, "HAMT::Set::_check", "set"); |
| 261 |
4958 |
| ST(0) = sv_2mortal(newSViv((IV)hamt_map_check(m->root, m->count))); |
| 262 |
4958 |
| XSRETURN(1); |
| 263 |
|
| |
| 264 |
|
| void |
| 265 |
|
| CLONE_SKIP(...) |
| 266 |
|
| CODE: |
| 267 |
0 |
| ST(0) = &PL_sv_yes; |
| 268 |
0 |
| XSRETURN(1); |