Mailing List Archive

Author: creamyg
Date: 2008-08-25 20:52:45 -0700 (Mon, 25 Aug 2008)
New Revision: 3764

Modified:
trunk/c_src/KinoSearch/Util/BitVector.bp
trunk/c_src/KinoSearch/Util/BitVector.c
trunk/perl/lib/KinoSearch/Util/BitVector.pm
trunk/perl/t/013-bit_vector.t
Log:
Add BitVec_Next_Set_Bit().


Modified: trunk/c_src/KinoSearch/Util/BitVector.bp
===================================================================
--- trunk/c_src/KinoSearch/Util/BitVector.bp 2008-08-26 03:52:02 UTC (rev 3763)
+++ trunk/c_src/KinoSearch/Util/BitVector.bp 2008-08-26 03:52:45 UTC (rev 3764)
@@ -38,6 +38,12 @@
public void
Set(BitVector *self, u32_t tick);

+ /** Returns the next set bit equal to or greater than the supplied tick,
+ * or -1 if no such bit exists.
+ */
+ i32_t
+ Next_Set_Bit(BitVector *self, u32_t tick);
+
/** Clear the indicated bit. (i.e. set it to 0).
*
* @param tick The bit to be cleared.

Modified: trunk/c_src/KinoSearch/Util/BitVector.c
===================================================================
--- trunk/c_src/KinoSearch/Util/BitVector.c 2008-08-26 03:52:02 UTC (rev 3763)
+++ trunk/c_src/KinoSearch/Util/BitVector.c 2008-08-26 03:52:45 UTC (rev 3764)
@@ -154,6 +154,32 @@
: true;
}

+i32_t
+BitVec_next_set_bit(BitVector *self, u32_t tick)
+{
+ size_t byte_size = ceil(self->cap / 8.0);
+ u8_t *const limit = self->bits + byte_size;
+ u8_t *ptr = self->bits + (tick >> 3);
+
+ for ( ; ptr < limit; ptr++) {
+ if (*ptr != 0) {
+ /* There's a non-zero bit in this byte. */
+ const i32_t base = (ptr - self->bits) * 8;
+ u32_t i;
+ for (i = 0; i < 8; i++) {
+ const i32_t candidate = base + i;
+ if (BitVec_Get(self, candidate)) {
+ if (candidate >= (i32_t)tick && candidate < (i32_t)self->cap) {
+ return candidate;
+ }
+ }
+ }
+ }
+ }
+
+ return -1;
+}
+
void
BitVec_and(BitVector *self, const BitVector *other)
{

Modified: trunk/perl/lib/KinoSearch/Util/BitVector.pm
===================================================================
--- trunk/perl/lib/KinoSearch/Util/BitVector.pm 2008-08-26 03:52:02 UTC (rev 3763)
+++ trunk/perl/lib/KinoSearch/Util/BitVector.pm 2008-08-26 03:52:45 UTC (rev 3764)
@@ -22,8 +22,21 @@

{ "KinoSearch::Util::BitVector" => {
bind_methods => [.
- qw( Get Set Clear Clear_All Grow Count Copy And Or
- And_Not Xor Flip Flip_Block To_Array )
+ qw( Get
+ Set
+ Clear
+ Clear_All
+ And
+ Or
+ And_Not
+ Xor
+ Flip
+ Flip_Block
+ Next_Set_Bit
+ To_Array
+ Grow
+ Count
+ Copy )
],
make_getters => [qw( cap count )],
make_constructors => ["new"],
@@ -31,8 +44,21 @@
synopsis => $synopsis,
constructor => { sample => $constructor },
methods => [.
- qw( get set clear clear_all grow count copy and or
- and_not xor flip flip_block to_array )
+ qw( get
+ set
+ clear
+ clear_all
+ and
+ or
+ and_not
+ xor
+ flip
+ flip_block
+ next_set_bit
+ to_array
+ grow
+ count
+ copy )
],
}
},

Modified: trunk/perl/t/013-bit_vector.t
===================================================================
--- trunk/perl/t/013-bit_vector.t 2008-08-26 03:52:02 UTC (rev 3763)
+++ trunk/perl/t/013-bit_vector.t 2008-08-26 03:52:45 UTC (rev 3764)
@@ -1,7 +1,7 @@
use strict;
use warnings;

-use Test::More tests => 666;
+use Test::More tests => 921;
use List::Util qw( shuffle );

use KinoSearch::Util::BitVector;
@@ -177,6 +177,19 @@
$bit_vec->clear_all;
is_deeply( $bit_vec->to_arrayref, [], "clear_all" );

+for my $set ( 24 .. 33 ) {
+ $bit_vec = KinoSearch::Util::BitVector->new;
+ $bit_vec->set($set);
+ for my $val ( 0, 1, 15 .. $set ) {
+ is( $bit_vec->next_set_bit($val),
+ $set, "Next_Set_Bit for $val is $set" );
+ }
+ for my $val ( $set + 1 .. $set + 9 ) {
+ is( $bit_vec->next_set_bit($val),
+ -1, "no Next_set_Bit for $val when max is $set" );
+ }
+}
+
# Valgrind only - detect off-by-one error.
for my $cap ( 5 .. 24 ) {
$bit_vec = KinoSearch::Util::BitVector->new( capacity => $cap );


_______________________________________________
kinosearch-commits mailing list
kinosearch-commits@rectangular.com
http://www.rectangular.com/mailman/listinfo/kinosearch-commits