projects
/
SXSI
/
libbp.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
5382b5f
)
Micro optimization for find_close
author
Kim Nguyễn
<kn@lri.fr>
Wed, 18 Apr 2012 15:45:21 +0000
(17:45 +0200)
committer
Kim Nguyễn
<kn@lri.fr>
Wed, 18 Apr 2012 15:45:21 +0000
(17:45 +0200)
Makefile
patch
|
blob
|
history
bp.h
patch
|
blob
|
history
diff --git
a/Makefile
b/Makefile
index
59e83a1
..
94027c1
100644
(file)
--- a/
Makefile
+++ b/
Makefile
@@
-1,7
+1,7
@@
POPCOUNT=$(shell grep -q popcnt /proc/cpuinfo && echo 1)
ifeq ($(POPCOUNT), 1)
POPCOUNT=$(shell grep -q popcnt /proc/cpuinfo && echo 1)
ifeq ($(POPCOUNT), 1)
- POPCOUNT_FLAG=-DHAS_NATIVE_POPCOUNT -mpopcnt
-mtune=corei7 -march=corei7
+ POPCOUNT_FLAG=-DHAS_NATIVE_POPCOUNT -mpopcnt
else
#POPCOUNT_FLAG=-DHAS_POPCOUNT_TABLE
POPCOUNT_FLAG=
else
#POPCOUNT_FLAG=-DHAS_POPCOUNT_TABLE
POPCOUNT_FLAG=
diff --git
a/bp.h
b/bp.h
index
6177b83
..
e0eb4c9
100644
(file)
--- a/
bp.h
+++ b/
bp.h
@@
-86,6
+86,14
@@
static inline int bp_root_node(bp *b)
return 0;
}
return 0;
}
+///////////////////////////////////////////
+// inspect(bp *b, int s)
+// returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
+///////////////////////////////////////////
+static inline int bp_inspect(bp *b, int s)
+{
+ return bp_getbit(b->B, s);
+}
///////////////////////////////////////////
// find_close(bp *b,int s)
///////////////////////////////////////////
// find_close(bp *b,int s)
@@
-93,7
+101,11
@@
static inline int bp_root_node(bp *b)
///////////////////////////////////////////
static inline int bp_find_close(bp *b,int s)
{
///////////////////////////////////////////
static inline int bp_find_close(bp *b,int s)
{
- return bp_fwd_excess(b, s, -1);
+ int s1 = s + 1;
+ if (bp_inspect(b, s1) == CP)
+ return s1;
+ else
+ return bp_fwd_excess(b, s, -1);
}
///////////////////////////////////////////
}
///////////////////////////////////////////
@@
-187,15
+199,6
@@
static inline int bp_preorder_select(bp *b,int s)
int bp_postorder_rank(bp *b,int s);
int bp_postorder_rank(bp *b,int s);
-///////////////////////////////////////////
-// inspect(bp *b, int s)
-// returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
-///////////////////////////////////////////
-static inline int bp_inspect(bp *b, int s)
-{
- return bp_getbit(b->B, s);
-}
-
static inline int bp_isleaf(bp *b, int s)
{
return (bp_inspect(b, s+1) == CP);
static inline int bp_isleaf(bp *b, int s)
{
return (bp_inspect(b, s+1) == CP);
@@
-218,7
+221,8
@@
static inline int bp_subtree_size(bp *b, int s)
static inline int bp_first_child(bp *b, int s)
{
static inline int bp_first_child(bp *b, int s)
{
- return (bp_inspect(b, s+1) == CP) ? -1 : s+1;
+ int s1 = s + 1;
+ return bp_inspect(b, s1) ? s1 : -1;
}
}
@@
-231,7
+235,7
@@
static inline int bp_next_sibling(bp *b, int s)
{
int t;
t = bp_find_close(b, s) + 1;
{
int t;
t = bp_find_close(b, s) + 1;
- return
(bp_inspect(b, t) == CP) ? -1 : t
;
+ return
bp_inspect(b, t) ? t : -1
;
}
}