Ushuffle.xs

filter: Statementstmt 95.6% 66 / 69 Branchbran 74.0% 40 / 54 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 86.1% 106 / 123 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
↑ Summary ushufflelib/ushuffle.c »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
k = SvOK(sv) ? SvIV(sv) : 0; 143873 2 143875
77 143875 ▶ if (k < 1)
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
name = SvOK(class) ? SvPV_nolen(class) : NULL; 2716 1 2717
165 2719 ▶ if (!name || !*name)
Branch: 2 branches
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
RETVAL = 1; 0 0 0
228 OUTPUT:
229 RETVAL
↑ Summary ushufflelib/ushuffle.c »