Commit | Line | Data |
---|---|---|
0e4f7002 MG |
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 | typedef struct { | |
9 | IV n; | |
10 | IV* t; | |
11 | } bit; | |
12 | ||
13 | bit* bit_create(IV len) { | |
14 | if(len < 1){ | |
15 | croak("Length less than 1"); | |
16 | return 0; | |
17 | } | |
18 | len++; | |
19 | bit *ret; | |
20 | Newx(ret, 1, bit); | |
21 | ret->n = len; | |
22 | Newxz(ret->t, len, IV); | |
23 | return ret; | |
24 | } | |
25 | ||
26 | void bit_free(bit *b) { | |
27 | Safefree(b->t); | |
28 | Safefree(b); | |
29 | } | |
30 | ||
31 | IV bit_query(bit *b, IV idx) { | |
32 | if(idx > b->n || idx < 1){ | |
33 | croak("Index not in range [1," IVdf "]", b->n); | |
34 | return 0; | |
35 | } | |
36 | IV ret = 0; | |
37 | while(idx) | |
38 | ret += b->t[idx], idx -= idx & -idx; | |
39 | return ret; | |
40 | } | |
41 | ||
42 | void bit_update(bit *b, IV idx, IV value) { | |
43 | if(idx > b->n || idx < 1){ | |
44 | croak("Index not in range [1," IVdf "]", b->n); | |
45 | return; | |
46 | } | |
47 | while(idx < b->n) | |
48 | b->t[idx] += value, idx += idx & -idx; | |
49 | } | |
50 | ||
51 | void bit_clear(bit *b) { | |
52 | Zero(b->t, b->n, IV); | |
53 | } | |
54 | ||
55 | typedef bit *Algorithm__BIT__XS; | |
56 | ||
57 | MODULE = Algorithm::BIT::XS PACKAGE = Algorithm::BIT::XS PREFIX = bit_ | |
58 | ||
59 | PROTOTYPES: ENABLE | |
60 | ||
61 | Algorithm::BIT::XS bit_create(IV len); | |
62 | ||
63 | void bit_free(Algorithm::BIT::XS b); | |
64 | ||
65 | IV bit_query(Algorithm::BIT::XS b, IV idx); | |
66 | ||
67 | void bit_update(Algorithm::BIT::XS b, IV idx, IV value); | |
68 | ||
69 | void bit_clear(Algorithm::BIT::XS b); |