| 1 |
|
| #define PERL_NO_GET_CONTEXT |
| 2 |
|
| #include "EXTERN.h" |
| 3 |
|
| #include "perl.h" |
| 4 |
|
| #include "XSUB.h" |
| 5 |
|
| |
| 6 |
|
| #include <limits.h> |
| 7 |
|
| #include <stdlib.h> |
| 8 |
|
| #include <string.h> |
| 9 |
|
| #include <sys/time.h> |
| 10 |
|
| |
| 11 |
|
| #include "ushufflelib/ushuffle.h" |
| 12 |
|
| |
| 13 |
|
| /* |
| 14 |
|
| * The uShuffle library keeps the k-let graph of a single sequence in |
| 15 |
|
| * file-level statics. Every Shuffler therefore owns a copy of its sequence, |
| 16 |
|
| * and loaded_id records whose graph the library currently holds, so that the |
| 17 |
|
| * graph is rebuilt when another Shuffler or a plain shuffle() call has |
| 18 |
|
| * replaced it in the meantime. Ids start at 1 and are never reused; 0 means |
| 19 |
|
| * "no Shuffler". |
| 20 |
|
| * |
| 21 |
|
| * The same statics, and the random number generator, are shared by all |
| 22 |
|
| * interpreter threads of the process. LIBRARY_LOCK serializes every use of |
| 23 |
|
| * them. Nothing that can croak may run while the lock is held. |
| 24 |
|
| */ |
| 25 |
|
| |
| 26 |
|
| typedef struct { |
| 27 |
|
| char *seq; |
| 28 |
|
| int len; |
| 29 |
|
| int k; |
| 30 |
|
| UV id; |
| 31 |
|
| } shuffler; |
| 32 |
|
| |
| 33 |
|
| typedef shuffler *Ushuffle__Shuffler; |
| 34 |
|
| |
| 35 |
|
| static UV next_id = 1; |
| 36 |
|
| static UV loaded_id = 0; |
| 37 |
|
| static int booted = 0; |
| 38 |
|
| |
| 39 |
|
| #ifdef USE_ITHREADS |
| 40 |
|
| static perl_mutex library_mutex; |
| 41 |
|
| #define LIBRARY_LOCK_INIT MUTEX_INIT(&library_mutex) |
| 42 |
|
| #define LIBRARY_LOCK MUTEX_LOCK(&library_mutex) |
| 43 |
|
| #define LIBRARY_UNLOCK MUTEX_UNLOCK(&library_mutex) |
| 44 |
|
| #else |
| 45 |
|
| #define LIBRARY_LOCK_INIT NOOP |
| 46 |
|
| #define LIBRARY_LOCK NOOP |
| 47 |
|
| #define LIBRARY_UNLOCK NOOP |
| 48 |
|
| #endif |
| 49 |
|
| |
| 50 |
|
| /* a tied or otherwise magical argument is fetched exactly once */ |
| 51 |
287730 |
| static SV *fetched(pTHX_ SV *sv) { |
| 52 |
287730 |
▶ | return SvGMAGICAL(sv) ? sv_2mortal(newSVsv(sv)) : sv; |
Branch: 1 branch
| Branch | True | False | Total |
| return SvGMAGICAL(sv) ? sv_2mortal(newSVsv(sv)) : sv; |
13 |
287717 |
287730 |
|
| 53 |
|
| } |
| 54 |
|
| |
| 55 |
143855 |
| static const char *checked_sequence(pTHX_ SV *sv, int *len) { |
| 56 |
|
| const char *s; |
| 57 |
|
| STRLEN n; |
| 58 |
|
| |
| 59 |
143855 |
| sv = fetched(aTHX_ sv); |
| 60 |
143855 |
▶ | if (!SvOK(sv)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (!SvOK(sv)) |
6 |
143849 |
143855 |
|
| 61 |
6 |
| croak("Ushuffle: sequence is undefined"); |
| 62 |
143845 |
| s = SvPVbyte(sv, n); |
| 63 |
143845 |
▶ | if (n > (STRLEN) INT_MAX) |
Branch: 1 branch
| Branch | True | False | Total |
| if (n > (STRLEN) INT_MAX) |
0 |
143845 |
143845 |
|
| 64 |
0 |
| croak("Ushuffle: sequence is too long"); |
| 65 |
|
| /* the library compares k-lets with strncmp */ |
| 66 |
143845 |
▶ | if (memchr(s, '\0', n)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (memchr(s, '\0', n)) |
8 |
143837 |
143845 |
|
| 67 |
8 |
| croak("Ushuffle: sequence contains a NUL byte"); |
| 68 |
143837 |
| *len = (int) n; |
| 69 |
143837 |
| return s; |
| 70 |
|
| } |
| 71 |
|
| |
| 72 |
143875 |
| static int checked_k(pTHX_ SV *sv) { |
| 73 |
|
| IV k; |
| 74 |
|
| |
| 75 |
143875 |
| sv = fetched(aTHX_ sv); |
| 76 |
143875 |
▶ | k = SvOK(sv) ? SvIV(sv) : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| k = SvOK(sv) ? SvIV(sv) : 0; |
143873 |
2 |
143875 |
|
| 77 |
143875 |
▶ | if (k < 1) |
Branch: 1 branch
| Branch | True | False | Total |
| if (k < 1) |
20 |
143855 |
143875 |
|
| 78 |
20 |
| croak("Ushuffle: k must be a positive integer"); |
| 79 |
143855 |
▶ | return k > INT_MAX ? INT_MAX : (int) k; |
Branch: 1 branch
| Branch | True | False | Total |
| return k > INT_MAX ? INT_MAX : (int) k; |
143851 |
4 |
143855 |
|
| 80 |
|
| } |
| 81 |
|
| |
| 82 |
|
| /* |
| 83 |
|
| * One shuffle of seq. id is that of the Shuffler owning seq, whose graph is |
| 84 |
|
| * reused if the library still holds it, or 0 for a sequence without one. |
| 85 |
|
| */ |
| 86 |
283068 |
| static SV *next_shuffle(pTHX_ const char *seq, int len, int k, UV id) { |
| 87 |
|
| SV *t; |
| 88 |
|
| |
| 89 |
283068 |
▶ | if (len == 0) |
Branch: 1 branch
| Branch | True | False | Total |
| if (len == 0) |
62 |
283006 |
283068 |
|
| 90 |
62 |
| return newSVpvn("", 0); |
| 91 |
283006 |
| t = newSV(len); |
| 92 |
283006 |
| SvPOK_only(t); |
| 93 |
|
| LIBRARY_LOCK; |
| 94 |
283006 |
▶ | if (id == 0 || loaded_id != id) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (id == 0 || loaded_id != id) { |
141868 |
141138 |
283006 |
| if (id == 0 || loaded_id != id) { |
22637 |
119231 |
141868 |
|
| 95 |
163775 |
| shuffle1(seq, len, k); |
| 96 |
163775 |
| loaded_id = id; |
| 97 |
|
| } |
| 98 |
283006 |
| shuffle2(SvPVX(t)); |
| 99 |
|
| LIBRARY_UNLOCK; |
| 100 |
283006 |
| SvPVX(t)[len] = '\0'; |
| 101 |
283006 |
| SvCUR_set(t, len); |
| 102 |
283006 |
| return t; |
| 103 |
|
| } |
| 104 |
|
| |
| 105 |
17 |
| static void seed_from_clock(pTHX) { |
| 106 |
|
| struct timeval tv; |
| 107 |
|
| |
| 108 |
17 |
| gettimeofday(&tv, NULL); |
| 109 |
34 |
| srandom((unsigned int) ((unsigned long) tv.tv_sec |
| 110 |
17 |
| ^ ((unsigned long) tv.tv_usec << 12) |
| 111 |
17 |
| ^ ((unsigned long) PerlProc_getpid() << 16))); |
| 112 |
17 |
| } |
| 113 |
|
| |
| 114 |
|
| MODULE = Ushuffle PACKAGE = Ushuffle |
| 115 |
|
| |
| 116 |
|
| PROTOTYPES: DISABLE |
| 117 |
|
| |
| 118 |
|
| BOOT: |
| 119 |
|
| /* runs again in a thread that loads the module its parent had not loaded */ |
| 120 |
17 |
▶ | if (!booted) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!booted) { |
17 |
0 |
17 |
|
| 121 |
|
| LIBRARY_LOCK_INIT; |
| 122 |
17 |
| seed_from_clock(aTHX); |
| 123 |
17 |
| booted = 1; |
| 124 |
|
| } |
| 125 |
|
| |
| 126 |
|
| SV * |
| 127 |
|
| shuffle(sequence, k) |
| 128 |
|
| SV *sequence |
| 129 |
|
| SV *k |
| 130 |
|
| PREINIT: |
| 131 |
|
| const char *s; |
| 132 |
|
| int len, let; |
| 133 |
|
| CODE: |
| 134 |
141158 |
| let = checked_k(aTHX_ k); |
| 135 |
141148 |
| s = checked_sequence(aTHX_ sequence, &len); |
| 136 |
141139 |
| RETVAL = next_shuffle(aTHX_ s, len, let, 0); |
| 137 |
|
| OUTPUT: |
| 138 |
|
| RETVAL |
| 139 |
|
| |
| 140 |
|
| void |
| 141 |
|
| set_seed(seed) |
| 142 |
|
| UV seed |
| 143 |
|
| CODE: |
| 144 |
|
| LIBRARY_LOCK; |
| 145 |
77 |
| srandom((unsigned int) seed); |
| 146 |
|
| LIBRARY_UNLOCK; |
| 147 |
|
| |
| 148 |
|
| MODULE = Ushuffle PACKAGE = Ushuffle::Shuffler |
| 149 |
|
| |
| 150 |
|
| SV * |
| 151 |
|
| new(class, sequence, k) |
| 152 |
|
| SV *class |
| 153 |
|
| SV *sequence |
| 154 |
|
| SV *k |
| 155 |
|
| PREINIT: |
| 156 |
|
| shuffler *self; |
| 157 |
|
| const char *name, *s; |
| 158 |
|
| int len, let; |
| 159 |
|
| CODE: |
| 160 |
|
| /* called on an object, new makes another object of the same class */ |
| 161 |
2719 |
▶ | if (SvROK(class) && SvOBJECT(SvRV(class))) |
Branch: 2 branches
| Branch | True | False | Total |
| if (SvROK(class) && SvOBJECT(SvRV(class))) |
2 |
2717 |
2719 |
| if (SvROK(class) && SvOBJECT(SvRV(class))) |
2 |
0 |
2 |
|
| 162 |
2 |
▶ | name = HvNAME(SvSTASH(SvRV(class))); |
Branch: 6 branches
| Branch | True | False | Total |
| name = HvNAME(SvSTASH(SvRV(class))); |
2 |
0 |
2 |
| name = HvNAME(SvSTASH(SvRV(class))); |
2 |
0 |
2 |
| name = HvNAME(SvSTASH(SvRV(class))); |
0 |
2 |
2 |
| name = HvNAME(SvSTASH(SvRV(class))); |
0 |
0 |
0 |
| name = HvNAME(SvSTASH(SvRV(class))); |
2 |
0 |
2 |
| name = HvNAME(SvSTASH(SvRV(class))); |
0 |
2 |
2 |
|
| 163 |
|
| else |
| 164 |
5433 |
▶ | name = SvOK(class) ? SvPV_nolen(class) : NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| name = SvOK(class) ? SvPV_nolen(class) : NULL; |
2716 |
1 |
2717 |
|
| 165 |
2719 |
▶ | if (!name || !*name) |
Branch: 2 branches
| Branch | True | False | Total |
| if (!name || !*name) |
2718 |
1 |
2719 |
| if (!name || !*name) |
1 |
2717 |
2718 |
|
| 166 |
2 |
| croak("Ushuffle::Shuffler::new: class name expected"); |
| 167 |
2717 |
| let = checked_k(aTHX_ k); |
| 168 |
2707 |
| s = checked_sequence(aTHX_ sequence, &len); |
| 169 |
2698 |
| Newx(self, 1, shuffler); |
| 170 |
2698 |
| self->seq = savepvn(s, len); |
| 171 |
2698 |
| self->len = len; |
| 172 |
2698 |
| self->k = let; |
| 173 |
|
| LIBRARY_LOCK; |
| 174 |
2698 |
| self->id = next_id++; |
| 175 |
|
| LIBRARY_UNLOCK; |
| 176 |
2698 |
| RETVAL = sv_setref_pv(newSV(0), name, (void *) self); |
| 177 |
|
| OUTPUT: |
| 178 |
|
| RETVAL |
| 179 |
|
| |
| 180 |
|
| SV * |
| 181 |
|
| shuffle(self) |
| 182 |
|
| Ushuffle::Shuffler self |
| 183 |
|
| CODE: |
| 184 |
141929 |
| RETVAL = next_shuffle(aTHX_ self->seq, self->len, self->k, self->id); |
| 185 |
|
| OUTPUT: |
| 186 |
|
| RETVAL |
| 187 |
|
| |
| 188 |
|
| SV * |
| 189 |
|
| sequence(self) |
| 190 |
|
| Ushuffle::Shuffler self |
| 191 |
|
| CODE: |
| 192 |
5269 |
| RETVAL = newSVpvn(self->seq, self->len); |
| 193 |
|
| OUTPUT: |
| 194 |
|
| RETVAL |
| 195 |
|
| |
| 196 |
|
| int |
| 197 |
|
| k(self) |
| 198 |
|
| Ushuffle::Shuffler self |
| 199 |
|
| CODE: |
| 200 |
5244 |
▶ | RETVAL = self->k; |
Branch: 1 branch
| Branch | True | False | Total |
| RETVAL = self->k; |
5235 |
9 |
5244 |
|
| 201 |
|
| OUTPUT: |
| 202 |
|
| RETVAL |
| 203 |
|
| |
| 204 |
|
| void |
| 205 |
|
| DESTROY(object) |
| 206 |
|
| SV *object |
| 207 |
|
| PREINIT: |
| 208 |
|
| SV *referent; |
| 209 |
|
| shuffler *self; |
| 210 |
|
| CODE: |
| 211 |
|
| /* tolerant, since it also runs during global destruction; the pointer |
| 212 |
|
| * is zeroed so that an explicit DESTROY call cannot free twice */ |
| 213 |
2700 |
▶ | if (!SvROK(object) || !sv_derived_from(object, "Ushuffle::Shuffler")) |
Branch: 2 branches
| Branch | True | False | Total |
| if (!SvROK(object) || !sv_derived_from(object, "Ushuffle::Shuffler")) |
2700 |
0 |
2700 |
| if (!SvROK(object) || !sv_derived_from(object, "Ushuffle::Shuffler")) |
0 |
2700 |
2700 |
|
| 214 |
0 |
| XSRETURN_EMPTY; |
| 215 |
2700 |
| referent = SvRV(object); |
| 216 |
2700 |
| self = INT2PTR(shuffler *, SvIV(referent)); |
| 217 |
2700 |
▶ | if (self) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (self) { |
2698 |
2 |
2700 |
|
| 218 |
2698 |
| Safefree(self->seq); |
| 219 |
2698 |
| Safefree(self); |
| 220 |
2698 |
| sv_setiv(referent, 0); |
| 221 |
|
| } |
| 222 |
|
| |
| 223 |
|
| int |
| 224 |
|
| CLONE_SKIP(...) |
| 225 |
|
| CODE: |
| 226 |
|
| /* a Shuffler is a bare pointer; cloning it into a thread would free it twice */ |
| 227 |
0 |
▶ | RETVAL = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| RETVAL = 1; |
0 |
0 |
0 |
|
| 228 |
|
| OUTPUT: |
| 229 |
|
| RETVAL |