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 #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 bit* bit_create(IV len) {
  19         if(len < 1){
  20                 croak("Length less than 1");
  21                 return 0;
  22         }
  23         len++;
  24         bit *ret;
  25         Newx(ret, 1, bit);
  26         ret->n = len;
  27         Newxz(ret->t, len, IV);
  28         return ret;
  29 }
  30
  31 void bit_free(bit *b) {
  32         Safefree(b->t);
  33         Safefree(b);
  34 }
  35
  36 IV bit_query(bit *b, IV idx) {
  37         CHECK_INDEX(idx, 0, b->n - 1, 0);
  38         IV ret = 0;
  39         while(idx)
  40                 ret += b->t[idx], idx -= idx & -idx;
  41         return ret;
  42 }
  43
  44 void bit_update(bit *b, IV idx, IV value) {
  45         CHECK_INDEX(idx, 0, b->n - 1, );
  46         while(idx < b->n)
  47                 b->t[idx] += value, idx += idx & -idx;
  48 }
  49
  50 void bit_clear(bit *b) {
  51         Zero(b->t, b->n, IV);
  52 }
  53
  54 typedef struct {
  55         IV n, m;
  56         IV* t;
  57 } bit2d;
  58
  59 bit2d* bit2d_create(IV n, IV m) {
  60         if(n < 1 || m < 1){
  61                 croak("A dimension is less than 1");
  62                 return 0;
  63         }
  64         n++, m++;
  65         bit2d *ret;
  66         Newx(ret, 1, bit2d);
  67         ret->n = n;
  68         ret->m = m;
  69         Newxz(ret->t, n * m, IV);
  70         return ret;
  71 }
  72
  73 void bit2d_free(bit2d *b) {
  74         Safefree(b->t);
  75         Safefree(b);
  76 }
  77
  78 IV bit2d_query(bit2d *b, IV i1, IV i2) {
  79         CHECK_INDEX(i1, 1, b->n - 1, 0);
  80         CHECK_INDEX(i2, 1, b->m - 1, 0);
  81         if(i1 > b->n || i1 < 1) {
  82                 croak("Index 1 not in range [1," IVdf "]", b->n);
  83                 return 0;
  84         }
  85         if(i2 > b->m || i2 < 1) {
  86                 croak("Index 2 not in range [1," IVdf "]", b->m);
  87                 return 0;
  88         }
  89         IV ret = 0, i2c = i2;
  90         while(i1) {
  91                 i2 = i2c;
  92                 while(i2)
  93                         ret += b->t[i1 * b->m + i2], i2 -= i2 & -i2;
  94                 i1 -= i1 & -i1;
  95         }
  96         return ret;
  97 }
  98
  99 void bit2d_update(bit2d *b, IV i1, IV i2, IV value) {
 100         CHECK_INDEX(i1, 1, b->n - 1, );
 101         CHECK_INDEX(i2, 1, b->m - 1, );
 102         IV i2c = i2;
 103         while(i1 < b->n) {
 104                 i2 = i2c;
 105                 while(i2 < b->m)
 106                         b->t[i1 * b->m + i2] += value, i2 += i2 & -i2;
 107                 i1 += i1 & -i1;
 108         }
 109 }
 110
 111 void bit2d_clear(bit2d *b) {
 112         Zero(b->t, b->n * b->m, IV);
 113 }
 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);