XS.xs

   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 struct {
  56         IV n, m;
  57         IV* t;
  58 } bit2d;
  59
  60 bit2d* bit2d_create(IV n, IV m) {
  61         if(n < 1 || m < 1){
  62                 croak("A dimension is less than 1");
  63                 return 0;
  64         }
  65         n++, m++;
  66         bit2d *ret;
  67         Newx(ret, 1, bit2d);
  68         ret->n = n;
  69         ret->m = m;
  70         Newxz(ret->t, n * m, IV);
  71         return ret;
  72 }
  73
  74 void bit2d_free(bit2d *b) {
  75         Safefree(b->t);
  76         Safefree(b);
  77 }
  78
  79 IV bit2d_query(bit2d *b, IV i1, IV i2) {
  80         if(i1 > b->n || i1 < 1) {
  81                 croak("Index 1 not in range [1," IVdf "]", b->n);
  82                 return 0;
  83         }
  84         if(i2 > b->m || i2 < 1) {
  85                 croak("Index 2 not in range [1," IVdf "]", b->m);
  86                 return 0;
  87         }
  88         IV ret = 0, i2c = i2;
  89         while(i1) {
  90                 i2 = i2c;
  91                 while(i2)
  92                         ret += b->t[i1 * b->m + i2], i2 -= i2 & -i2;
  93                 i1 -= i1 & -i1;
  94         }
  95         return ret;
  96 }
  97
  98 void bit2d_update(bit2d *b, IV i1, IV i2, IV value) {
  99         if(i1 > b->n || i1 < 1) {
 100                 croak("Index 1 not in range [1," IVdf "]", b->n);
 101                 return;
 102         }
 103         if(i2 > b->m || i2 < 1) {
 104                 croak("Index 2 not in range [1," IVdf "]", b->m);
 105                 return;
 106         }
 107         IV i2c = i2;
 108         while(i1 < b->n) {
 109                 i2 = i2c;
 110                 while(i2 < b->m)
 111                         b->t[i1 * b->m + i2] += value, i2 += i2 & -i2;
 112                 i1 += i1 & -i1;
 113         }
 114 }
 115
 116 void bit2d_clear(bit2d *b) {
 117         Zero(b->t, b->n * b->m, IV);
 118 }
 119
 120 typedef bit *Algorithm__BIT__XS;
 121 typedef bit2d *Algorithm__BIT2D__XS;
 122
 123 MODULE = Algorithm::BIT::XS             PACKAGE = Algorithm::BIT::XS            PREFIX = bit_
 124
 125 PROTOTYPES: ENABLE
 126
 127 Algorithm::BIT::XS bit_create(IV len);
 128
 129 void bit_free(Algorithm::BIT::XS b);
 130
 131 IV bit_query(Algorithm::BIT::XS b, IV idx);
 132
 133 void bit_update(Algorithm::BIT::XS b, IV idx, IV value);
 134
 135 void bit_clear(Algorithm::BIT::XS b);
 136
 137 MODULE = Algorithm::BIT::XS             PACKAGE = Algorithm::BIT2D::XS          PREFIX = bit2d_
 138
 139 PROTOTYPES: ENABLE
 140
 141 Algorithm::BIT2D::XS bit2d_create(IV n, IV m);
 142
 143 void bit2d_free(Algorithm::BIT2D::XS b);
 144
 145 IV bit2d_query(Algorithm::BIT2D::XS b, IV i1, IV i2);
 146
 147 void bit2d_update(Algorithm::BIT2D::XS b, IV i1, IV i2, IV value);
 148
 149 void bit2d_clear(Algorithm::BIT2D::XS b);