line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
/* |
2
|
|
|
|
|
|
|
Copyright (c) 2008 Edwin Pratomo |
3
|
|
|
|
|
|
|
|
4
|
|
|
|
|
|
|
You may distribute under the terms of either the GNU General Public |
5
|
|
|
|
|
|
|
License or the Artistic License, as specified in the Perl README file, |
6
|
|
|
|
|
|
|
with the exception that it cannot be placed on a CD-ROM or similar media |
7
|
|
|
|
|
|
|
for commercial distribution without the prior approval of the author. |
8
|
|
|
|
|
|
|
|
9
|
|
|
|
|
|
|
*/ |
10
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
#include "coollex.h" |
12
|
|
|
|
|
|
|
|
13
|
5
|
|
|
|
|
|
COMBINATION* init_combination(IV n, IV r, AV *av) { |
14
|
5
|
|
|
|
|
|
COMBINATION *c = NULL; |
15
|
|
|
|
|
|
|
int i; |
16
|
5
|
|
|
|
|
|
unsigned char *b = NULL; |
17
|
5
|
|
|
|
|
|
SV *aryref = newRV_inc((SV*) av); |
18
|
|
|
|
|
|
|
|
19
|
|
|
|
|
|
|
/* init bitstring */ |
20
|
5
|
|
|
|
|
|
b = (unsigned char*)safecalloc(n, sizeof(unsigned char)); |
21
|
5
|
50
|
|
|
|
|
if (b == NULL) |
22
|
0
|
|
|
|
|
|
return NULL; |
23
|
|
|
|
|
|
|
|
24
|
15
|
100
|
|
|
|
|
for (i = 0; i < r; i++) |
25
|
10
|
|
|
|
|
|
b[i] = 1; |
26
|
|
|
|
|
|
|
|
27
|
5
|
|
|
|
|
|
c = (COMBINATION*)safemalloc(sizeof(COMBINATION)); |
28
|
5
|
50
|
|
|
|
|
if (c == NULL) { |
29
|
0
|
|
|
|
|
|
safefree(b); |
30
|
0
|
|
|
|
|
|
return NULL; |
31
|
|
|
|
|
|
|
} |
32
|
5
|
|
|
|
|
|
c->n = n; |
33
|
5
|
|
|
|
|
|
c->r = r; |
34
|
5
|
|
|
|
|
|
c->aryref = aryref; |
35
|
5
|
|
|
|
|
|
c->b = b; |
36
|
5
|
|
|
|
|
|
c->state = 0; |
37
|
5
|
|
|
|
|
|
c->x = 1; |
38
|
5
|
|
|
|
|
|
c->y = 0; |
39
|
5
|
|
|
|
|
|
return c; |
40
|
|
|
|
|
|
|
} |
41
|
|
|
|
|
|
|
|
42
|
3
|
|
|
|
|
|
void free_combination(COMBINATION *c) { |
43
|
3
|
|
|
|
|
|
safefree(c->b); |
44
|
3
|
|
|
|
|
|
SvREFCNT_dec(c->aryref); |
45
|
3
|
|
|
|
|
|
safefree(c); |
46
|
3
|
|
|
|
|
|
} |
47
|
|
|
|
|
|
|
|
48
|
|
|
|
|
|
|
/* coollex algorithm */ |
49
|
26
|
|
|
|
|
|
bool coollex(COMBINATION *c) { |
50
|
26
|
|
|
|
|
|
bool is_done = FALSE; |
51
|
|
|
|
|
|
|
|
52
|
26
|
|
|
|
|
|
switch (c->state) { |
53
|
|
|
|
|
|
|
case 0: /* state 0: initialized */ |
54
|
5
|
|
|
|
|
|
c->state = 1; |
55
|
5
|
|
|
|
|
|
break; |
56
|
|
|
|
|
|
|
case 1: /* state 1: first shift */ |
57
|
4
|
|
|
|
|
|
c->b[c->r] =1; |
58
|
4
|
|
|
|
|
|
c->b[0] = 0; |
59
|
4
|
|
|
|
|
|
c->state = 2; |
60
|
4
|
|
|
|
|
|
break; |
61
|
|
|
|
|
|
|
default: /* subsequent shifts */ |
62
|
|
|
|
|
|
|
{ |
63
|
17
|
100
|
|
|
|
|
while (c->x < c->n - 1) { |
64
|
13
|
|
|
|
|
|
c->b[c->x++] = 0; |
65
|
13
|
|
|
|
|
|
c->b[c->y++] = 1; |
66
|
13
|
100
|
|
|
|
|
if (c->b[c->x] == 0) { |
67
|
6
|
|
|
|
|
|
c->b[c->x] = 1, c->b[0] = 0; |
68
|
6
|
100
|
|
|
|
|
if (c->y > 1) c->x = 1; |
69
|
6
|
|
|
|
|
|
c->y = 0; |
70
|
|
|
|
|
|
|
} |
71
|
13
|
|
|
|
|
|
return is_done; |
72
|
|
|
|
|
|
|
} |
73
|
4
|
|
|
|
|
|
is_done = TRUE; |
74
|
|
|
|
|
|
|
} |
75
|
|
|
|
|
|
|
} |
76
|
13
|
|
|
|
|
|
return is_done; |
77
|
|
|
|
|
|
|
} |
78
|
|
|
|
|
|
|
|
79
|
26
|
|
|
|
|
|
void coollex_visit(COMBINATION *c, SV **p_items) { |
80
|
26
|
|
|
|
|
|
int i, r = 0; |
81
|
|
|
|
|
|
|
SV **p, **svp; |
82
|
26
|
|
|
|
|
|
AV *av = (AV*)SvRV(c->aryref); |
83
|
126
|
100
|
|
|
|
|
for (i = 0, p = p_items; i < c->n; i++) { |
84
|
100
|
100
|
|
|
|
|
if (c->b[i]) { /* the bitstring matters */ |
85
|
52
|
|
|
|
|
|
r++; |
86
|
|
|
|
|
|
|
/* tell GC to take care of this */ |
87
|
52
|
100
|
|
|
|
|
if (SvOK(*p)) { |
|
|
50
|
|
|
|
|
|
|
|
50
|
|
|
|
|
|
88
|
46
|
|
|
|
|
|
SvREFCNT_dec(*p); |
89
|
|
|
|
|
|
|
} |
90
|
52
|
|
|
|
|
|
svp = av_fetch(av, i, FALSE); |
91
|
52
|
50
|
|
|
|
|
*p = (svp) ? SvREFCNT_inc(*svp) : &PL_sv_undef; |
92
|
52
|
|
|
|
|
|
p++; |
93
|
|
|
|
|
|
|
} |
94
|
|
|
|
|
|
|
} |
95
|
|
|
|
|
|
|
assert(r == c->r); |
96
|
26
|
|
|
|
|
|
} |
97
|
|
|
|
|
|
|
|