projects
/
SXSI
/
XMLTree.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Backport changes from the grammar branch
[SXSI/XMLTree.git]
/
libcds
/
src
/
static_bitsequence
/
sdarray.cpp
diff --git
a/libcds/src/static_bitsequence/sdarray.cpp
b/libcds/src/static_bitsequence/sdarray.cpp
index
2294a0c
..
4fe52b2
100644
(file)
--- a/
libcds/src/static_bitsequence/sdarray.cpp
+++ b/
libcds/src/static_bitsequence/sdarray.cpp
@@
-1,6
+1,7
@@
#include <sdarray.h>
#include <sdarray.h>
-
+using std::min;
+using std::max;
#if 0
typedef unsigned int qword;
#define logD 4
#if 0
typedef unsigned int qword;
#define logD 4
@@
-157,6
+158,34
@@
static const unsigned int _popCount[] = {
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
+static inline unsigned int
+_fast_popcount2(int x)
+{
+ uint m1 = 0x55555555;
+ uint m2 = 0x33333333;
+ uint m4 = 0x0f0f0f0f;
+ x -= (x >> 1) & m1;
+ x = (x & m2) + ((x >> 2) & m2);
+ x = (x + (x >> 4)) & m4;
+ x += x >> 8;
+ return (x + (x >> 16)) & 0x3f;
+}
+
+static inline unsigned int
+_fast_popcount3(int x)
+{
+ uint m1 = 0x55555555;
+ uint m2 = 0xc30c30c3;
+ x -= (x >> 1) & m1;
+ x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2);
+ x += x >> 6;
+ return (x + (x >> 12) + (x >> 24)) & 0x3f;
+}
+
+static inline unsigned int
+_fast_popcount(int x) {
+ return _popCount[x];
+}
static unsigned int __selecttbl[8*256];
static int built = 0;
static unsigned int __selecttbl[8*256];
static int built = 0;
@@
-395,11
+424,13
@@
int selectd2_select(selectd2 *select, int i,int f) {
if (f == 1) {
rr = p & (8-1);
if (f == 1) {
rr = p & (8-1);
- r -= _popCount[*q >> (8-1-rr)];
+ //r -= _popCount[*q >> (8-1-rr)];
+ r -= _fast_popcount(*q >> (8-1-rr));
//p = p - rr;
while (1) {
//p = p - rr;
while (1) {
- rr = _popCount[*q];
+ //rr = _popCount[*q];
+ rr = _fast_popcount(*q);
if (r + rr >= i) break;
r += rr;
//p += 8;
if (r + rr >= i) break;
r += rr;
//p += 8;
@@
-410,11
+441,13
@@
int selectd2_select(selectd2 *select, int i,int f) {
}
else {
rr = p & (8-1);
}
else {
rr = p & (8-1);
- r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+ //r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+ r -= _fast_popcount((*q ^ 0xff) >> (8-1-rr));
//p = p - rr;
while (1) {
//p = p - rr;
while (1) {
- rr = _popCount[*q ^ 0xff];
+ //rr = _popCount[*q ^ 0xff];
+ rr = _fast_popcount(*q ^ 0xff);
if (r + rr >= i) break;
r += rr;
//p += 8;
if (r + rr >= i) break;
r += rr;
//p += 8;
@@
-471,11
+504,13
@@
int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
if (f == 1) {
rr = p & (8-1);
if (f == 1) {
rr = p & (8-1);
- r -= _popCount[*q >> (8-1-rr)];
+ //r -= _popCount[*q >> (8-1-rr)];
+ r -= _fast_popcount(*q >> (8-1-rr));
//p = p - rr;
while (1) {
//p = p - rr;
while (1) {
- rr = _popCount[*q];
+ //rr = _popCount[*q];
+ rr = _fast_popcount(*q);
if (r + rr >= i) break;
r += rr;
//p += 8;
if (r + rr >= i) break;
r += rr;
//p += 8;
@@
-487,7
+522,8
@@
int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
if ((i>>logL) == ((i+1)>>logL)) {
i++;
while (1) {
if ((i>>logL) == ((i+1)>>logL)) {
i++;
while (1) {
- rr = _popCount[*q];
+ //rr = _popCount[*q];
+ r = _fast_popcount(*q);
if (r + rr >= i) break;
r += rr;
q++;
if (r + rr >= i) break;
r += rr;
q++;
@@
-502,11
+538,13
@@
int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
}
else {
rr = p & (8-1);
}
else {
rr = p & (8-1);
- r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+ //r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+ r -= _fast_popcount((*q ^ 0xff) >> (8-1-rr));
//p = p - rr;
while (1) {
//p = p - rr;
while (1) {
- rr = _popCount[*q ^ 0xff];
+ //rr = _popCount[*q ^ 0xff];
+ rr = _fast_popcount(*q ^ 0xff);
if (r + rr >= i) break;
r += rr;
//p += 8;
if (r + rr >= i) break;
r += rr;
//p += 8;
@@
-518,7
+556,8
@@
int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
if ((i>>logL) == ((i+1)>>logL)) {
i++;
while (1) {
if ((i>>logL) == ((i+1)>>logL)) {
i++;
while (1) {
- rr = _popCount[*q ^ 0xff];
+ //rr = _popCount[*q ^ 0xff];
+ rr = _fast_popcount(*q ^ 0xff);
if (r + rr >= i) break;
r += rr;
q++;
if (r + rr >= i) break;
r += rr;
q++;