XS.xs

filter: Statementstmt 89.0% 57 / 64 Branchbran 68.9% 40 / 58 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 79.5% 97 / 122 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Algorithm/BIT2D/XS.pm ↑ Summary blib/lib/Algorithm/BIT/XS.pm »
1 #define PERL_NO_GET_CONTEXT
2 #include "EXTERN.h"
3 #include "perl.h"
4 #include "XSUB.h"
5  
6 #include "ppport.h"
7  
8 #define CHECK_INDEX(idx, min, max, ret) if(idx < min || idx > max) { \
9 croak("Index not in range [" IVdf "," IVdf "]", (IV)(min), (IV)(max)); \
10 return ret; \
11 }
12  
13 typedef struct {
14 IV n;
15 IV* t;
16 } bit;
17  
18 1 bit* bit_create(IV len) {
19 1 ▶ if(len < 1){
Branch: 1 branch
BranchTrueFalseTotal
if(len < 1){ 0 1 1
20 0 croak("Length less than 1");
21 return 0;
22 }
23 1 len++;
24 bit *ret;
25 1 Newx(ret, 1, bit);
26 1 ret->n = len;
27 1 ▶ Newxz(ret->t, len, IV);
Branch: 1 branch
BranchTrueFalseTotal
Newxz(ret->t, len, IV); 0 1 1
28 1 return ret;
29 }
30  
31 1 void bit_free(bit *b) {
32 1 Safefree(b->t);
33 1 Safefree(b);
34 1 }
35  
36 20 IV bit_query(bit *b, IV idx) {
37 20 ▶ CHECK_INDEX(idx, 0, b->n - 1, 0);
Branch: 2 branches
BranchTrueFalseTotal
CHECK_INDEX(idx, 0, b->n - 1, 0); 20 0 20
CHECK_INDEX(idx, 0, b->n - 1, 0); 1 19 20
38 19 IV ret = 0;
39 57 ▶ while(idx)
Branch: 1 branch
BranchTrueFalseTotal
while(idx) 38 19 57
40 38 ret += b->t[idx], idx -= idx & -idx;
41 19 return ret;
42 }
43  
44 7 void bit_update(bit *b, IV idx, IV value) {
45 7 ▶ CHECK_INDEX(idx, 0, b->n - 1, );
Branch: 2 branches
BranchTrueFalseTotal
CHECK_INDEX(idx, 0, b->n - 1, ); 7 0 7
CHECK_INDEX(idx, 0, b->n - 1, ); 1 6 7
46 26 ▶ while(idx < b->n)
Branch: 1 branch
BranchTrueFalseTotal
while(idx < b->n) 20 6 26
47 20 b->t[idx] += value, idx += idx & -idx;
48 }
49  
50 1 void bit_clear(bit *b) {
51 1 ▶ Zero(b->t, b->n, IV);
Branch: 1 branch
BranchTrueFalseTotal
Zero(b->t, b->n, IV); 0 1 1
52 1 }
53  
54 typedef struct {
55 IV n, m;
56 IV* t;
57 } bit2d;
58  
59 1 bit2d* bit2d_create(IV n, IV m) {
60 1 ▶ if(n < 1 || m < 1){
Branch: 2 branches
BranchTrueFalseTotal
if(n < 1 || m < 1){ 1 0 1
if(n < 1 || m < 1){ 0 1 1
61 0 croak("A dimension is less than 1");
62 return 0;
63 }
64 1 n++, m++;
65 bit2d *ret;
66 1 Newx(ret, 1, bit2d);
67 1 ret->n = n;
68 1 ret->m = m;
69 1 ▶ Newxz(ret->t, n * m, IV);
Branch: 1 branch
BranchTrueFalseTotal
Newxz(ret->t, n * m, IV); 0 1 1
70 1 return ret;
71 }
72  
73 1 void bit2d_free(bit2d *b) {
74 1 Safefree(b->t);
75 1 Safefree(b);
76 1 }
77  
78 5 IV bit2d_query(bit2d *b, IV i1, IV i2) {
79 5 ▶ CHECK_INDEX(i1, 1, b->n - 1, 0);
Branch: 2 branches
BranchTrueFalseTotal
CHECK_INDEX(i1, 1, b->n - 1, 0); 5 0 5
CHECK_INDEX(i1, 1, b->n - 1, 0); 1 4 5
80 4 ▶ CHECK_INDEX(i2, 1, b->m - 1, 0);
Branch: 2 branches
BranchTrueFalseTotal
CHECK_INDEX(i2, 1, b->m - 1, 0); 4 0 4
CHECK_INDEX(i2, 1, b->m - 1, 0); 1 3 4
81 3 ▶ if(i1 > b->n || i1 < 1) {
Branch: 2 branches
BranchTrueFalseTotal
if(i1 > b->n || i1 < 1) { 3 0 3
if(i1 > b->n || i1 < 1) { 0 3 3
82 0 croak("Index 1 not in range [1," IVdf "]", b->n);
83 return 0;
84 }
85 3 ▶ if(i2 > b->m || i2 < 1) {
Branch: 2 branches
BranchTrueFalseTotal
if(i2 > b->m || i2 < 1) { 3 0 3
if(i2 > b->m || i2 < 1) { 0 3 3
86 0 croak("Index 2 not in range [1," IVdf "]", b->m);
87 return 0;
88 }
89 3 IV ret = 0, i2c = i2;
90 9 ▶ while(i1) {
Branch: 1 branch
BranchTrueFalseTotal
while(i1) { 6 3 9
91 6 i2 = i2c;
92 16 ▶ while(i2)
Branch: 1 branch
BranchTrueFalseTotal
while(i2) 10 6 16
93 10 ret += b->t[i1 * b->m + i2], i2 -= i2 & -i2;
94 6 i1 -= i1 & -i1;
95 }
96 3 return ret;
97 }
98  
99 4 void bit2d_update(bit2d *b, IV i1, IV i2, IV value) {
100 4 ▶ CHECK_INDEX(i1, 1, b->n - 1, );
Branch: 2 branches
BranchTrueFalseTotal
CHECK_INDEX(i1, 1, b->n - 1, ); 4 0 4
CHECK_INDEX(i1, 1, b->n - 1, ); 1 3 4
101 3 ▶ CHECK_INDEX(i2, 1, b->m - 1, );
Branch: 2 branches
BranchTrueFalseTotal
CHECK_INDEX(i2, 1, b->m - 1, ); 3 0 3
CHECK_INDEX(i2, 1, b->m - 1, ); 1 2 3
102 2 IV i2c = i2;
103 7 ▶ while(i1 < b->n) {
Branch: 1 branch
BranchTrueFalseTotal
while(i1 < b->n) { 5 2 7
104 5 i2 = i2c;
105 16 ▶ while(i2 < b->m)
Branch: 1 branch
BranchTrueFalseTotal
while(i2 < b->m) 11 5 16
106 11 b->t[i1 * b->m + i2] += value, i2 += i2 & -i2;
107 5 i1 += i1 & -i1;
108 }
109 }
110  
111 0 void bit2d_clear(bit2d *b) {
112 0 ▶ Zero(b->t, b->n * b->m, IV);
Branch: 1 branch
BranchTrueFalseTotal
Zero(b->t, b->n * b->m, IV); 0 0 0
113 0 }
114  
115 typedef bit *Algorithm__BIT__XS;
116 typedef bit2d *Algorithm__BIT2D__XS;
117  
118 MODULE = Algorithm::BIT::XS PACKAGE = Algorithm::BIT::XS PREFIX = bit_
119  
120 PROTOTYPES: ENABLE
121  
122 Algorithm::BIT::XS bit_create(IV len);
123  
124 void bit_free(Algorithm::BIT::XS b);
125 ALIAS:
126 DESTROY = 1
127  
128 IV bit_query(Algorithm::BIT::XS b, IV idx);
129  
130 void bit_update(Algorithm::BIT::XS b, IV idx, IV value);
131  
132 void bit_clear(Algorithm::BIT::XS b);
133  
134 MODULE = Algorithm::BIT::XS PACKAGE = Algorithm::BIT2D::XS PREFIX = bit2d_
135  
136 PROTOTYPES: ENABLE
137  
138 Algorithm::BIT2D::XS bit2d_create(IV n, IV m);
139  
140 void bit2d_free(Algorithm::BIT2D::XS b);
141 ALIAS:
142 DESTROY = 1
143  
144 IV bit2d_query(Algorithm::BIT2D::XS b, IV i1, IV i2);
145  
146 void bit2d_update(Algorithm::BIT2D::XS b, IV i1, IV i2, IV value);
147  
148 void bit2d_clear(Algorithm::BIT2D::XS b);
« blib/lib/Algorithm/BIT2D/XS.pm ↑ Summary blib/lib/Algorithm/BIT/XS.pm »