[algorithm-bit-xs.git] / XS.xs

#define PERL_NO_GET_CONTEXT
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include "ppport.h"

#define CHECK_INDEX(idx, min, max, ret) if(idx < min || idx > max) {	\
		croak("Index not in range [" IVdf "," IVdf "]", (IV)(min), (IV)(max)); \
		return ret;														\
	}

typedef struct {
	IV n;
	IV* t;
} bit;

bit* bit_create(IV len) {
	if(len < 1){
		croak("Length less than 1");
		return 0;
	}
	len++;
	bit *ret;
	Newx(ret, 1, bit);
	ret->n = len;
	Newxz(ret->t, len, IV);
	return ret;
}

void bit_free(bit *b) {
	Safefree(b->t);
	Safefree(b);
}

IV bit_query(bit *b, IV idx) {
	CHECK_INDEX(idx, 0, b->n - 1, 0);
	IV ret = 0;
	while(idx)
		ret += b->t[idx], idx -= idx & -idx;
	return ret;
}

void bit_update(bit *b, IV idx, IV value) {
	CHECK_INDEX(idx, 0, b->n - 1, );
	while(idx < b->n)
		b->t[idx] += value, idx += idx & -idx;
}

void bit_clear(bit *b) {
	Zero(b->t, b->n, IV);
}

typedef struct {
	IV n, m;
	IV* t;
} bit2d;

bit2d* bit2d_create(IV n, IV m) {
	if(n < 1 || m < 1){
		croak("A dimension is less than 1");
		return 0;
	}
	n++, m++;
	bit2d *ret;
	Newx(ret, 1, bit2d);
	ret->n = n;
	ret->m = m;
	Newxz(ret->t, n * m, IV);
	return ret;
}

void bit2d_free(bit2d *b) {
	Safefree(b->t);
	Safefree(b);
}

IV bit2d_query(bit2d *b, IV i1, IV i2) {
	CHECK_INDEX(i1, 1, b->n - 1, 0);
	CHECK_INDEX(i2, 1, b->m - 1, 0);
	if(i1 > b->n || i1 < 1) {
		croak("Index 1 not in range [1," IVdf "]", b->n);
		return 0;
	}
	if(i2 > b->m || i2 < 1) {
		croak("Index 2 not in range [1," IVdf "]", b->m);
		return 0;
	}
	IV ret = 0, i2c = i2;
	while(i1) {
		i2 = i2c;
		while(i2)
			ret += b->t[i1 * b->m + i2], i2 -= i2 & -i2;
		i1 -= i1 & -i1;
	}
	return ret;
}

void bit2d_update(bit2d *b, IV i1, IV i2, IV value) {
	CHECK_INDEX(i1, 1, b->n - 1, );
	CHECK_INDEX(i2, 1, b->m - 1, );
	IV i2c = i2;
	while(i1 < b->n) {
		i2 = i2c;
		while(i2 < b->m)
			b->t[i1 * b->m + i2] += value, i2 += i2 & -i2;
		i1 += i1 & -i1;
	}
}

void bit2d_clear(bit2d *b) {
	Zero(b->t, b->n * b->m, IV);
}

typedef bit *Algorithm__BIT__XS;
typedef bit2d *Algorithm__BIT2D__XS;

MODULE = Algorithm::BIT::XS		PACKAGE = Algorithm::BIT::XS		PREFIX = bit_

PROTOTYPES: ENABLE

Algorithm::BIT::XS bit_create(IV len);

void bit_free(Algorithm::BIT::XS b);
ALIAS:
    DESTROY = 1

IV bit_query(Algorithm::BIT::XS b, IV idx);

void bit_update(Algorithm::BIT::XS b, IV idx, IV value);

void bit_clear(Algorithm::BIT::XS b);

MODULE = Algorithm::BIT::XS		PACKAGE = Algorithm::BIT2D::XS		PREFIX = bit2d_

PROTOTYPES: ENABLE

Algorithm::BIT2D::XS bit2d_create(IV n, IV m);

void bit2d_free(Algorithm::BIT2D::XS b);
ALIAS:
    DESTROY = 1

IV bit2d_query(Algorithm::BIT2D::XS b, IV i1, IV i2);

void bit2d_update(Algorithm::BIT2D::XS b, IV i1, IV i2, IV value);

void bit2d_clear(Algorithm::BIT2D::XS b);
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
02b65a50 MG	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
0e4f7002 MG	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) {
02b65a50	37	CHECK_INDEX(idx, 0, b->n - 1, 0);
0e4f7002 MG	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) {
02b65a50	45	CHECK_INDEX(idx, 0, b->n - 1, );
0e4f7002 MG	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
0c7cf8e9 MG	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) {
02b65a50 MG	79	CHECK_INDEX(i1, 1, b->n - 1, 0);
02b65a50 MG	80	CHECK_INDEX(i2, 1, b->m - 1, 0);
0c7cf8e9 MG	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)
926e0865	93	ret += b->t[i1 * b->m + i2], i2 -= i2 & -i2;
0c7cf8e9 MG	94	i1 -= i1 & -i1;
	95	}
	96	return ret;
	97	}
	98
	99	void bit2d_update(bit2d *b, IV i1, IV i2, IV value) {
02b65a50 MG	100	CHECK_INDEX(i1, 1, b->n - 1, );
02b65a50 MG	101	CHECK_INDEX(i2, 1, b->m - 1, );
0c7cf8e9 MG	102	IV i2c = i2;
	103	while(i1 < b->n) {
	104	i2 = i2c;
	105	while(i2 < b->m)
926e0865	106	b->t[i1 * b->m + i2] += value, i2 += i2 & -i2;
0c7cf8e9 MG	107	i1 += i1 & -i1;
	108	}
	109	}
	110
	111	void bit2d_clear(bit2d *b) {
	112	Zero(b->t, b->n * b->m, IV);
	113	}
	114
0e4f7002	115	typedef bit *Algorithm__BIT__XS;
0c7cf8e9	116	typedef bit2d *Algorithm__BIT2D__XS;
0e4f7002 MG	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);
2b47d13c MG	125	ALIAS:
2b47d13c MG	126	DESTROY = 1
0e4f7002 MG	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);
0c7cf8e9 MG	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);
2b47d13c MG	141	ALIAS:
2b47d13c MG	142	DESTROY = 1
0c7cf8e9 MG	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);