Mailing List Archive

Author: creamyg
Date: 2008-07-29 10:16:41 -0700 (Tue, 29 Jul 2008)
New Revision: 3661

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:
Expose BitVector as a public class. Change Flip_Range() to Flip_Block(),
because an offset and a range are less ambiguous than a "from" bit (inclusive)
and a "to" big (exclusive). Rename vars named "num" to "tick" for consistency
with the rest of the library when describing an index into an array.


Modified: trunk/c_src/KinoSearch/Util/BitVector.bp
===================================================================
--- trunk/c_src/KinoSearch/Util/BitVector.bp 2008-07-28 20:24:29 UTC (rev 3660)
+++ trunk/c_src/KinoSearch/Util/BitVector.bp 2008-07-29 17:16:41 UTC (rev 3661)
@@ -12,13 +12,13 @@
u8_t *bits;
u32_t count;

+ static incremented BitVector*
+ new(u32_t capacity = 0);
+
/**
* @param capacity The number of bits that the initial array should be
* able to hold.
*/
- static incremented BitVector*
- new(u32_t capacity = 0);
-
static BitVector*
init(BitVector *self, u32_t capacity = 0);

@@ -26,24 +26,24 @@
* hasn't. (Regardless of whether it lies within the bounds of the
* object's capacity).
*
- * @param num The requested bit.
+ * @param tick The requested bit.
*/
bool_t
- Get(const BitVector *self, u32_t num);
+ Get(const BitVector *self, u32_t tick);

/** Set the indicated bit at to 1.
*
- * @param num The bit to be set.
+ * @param tick The bit to be set.
*/
void
- Set(BitVector *self, u32_t num);
+ Set(BitVector *self, u32_t tick);

/** Clear the indicated bit. (i.e. set it to 0).
*
- * @param num The bit to be cleared.
+ * @param tick The bit to be cleared.
*/
void
- Clear(BitVector *self, u32_t num);
+ Clear(BitVector *self, u32_t tick);

/** Clear all bits.
*/
@@ -91,20 +91,18 @@

/** Invert the value of a bit.
*
- * @param num The bit to invert.
+ * @param tick The bit to invert.
*/
void
- Flip(BitVector *self, u32_t num);
+ Flip(BitVector *self, u32_t tick);

- /** Invert the values in the BitVector from the lower bound, inclusive, to
- * the upper bound, exclusive. If the bounds are the same, no change will
- * occur.
+ /** Invert each bit within a contiguous block.
*
- * @param from Lower bound.
- * @param to Upper bound.
+ * @param offset Lower bound.
+ * @param length The number of bits to flip.
*/
void
- Flip_Range(BitVector *self, u32_t from, u32_t to);
+ Flip_Block(BitVector *self, u32_t offset, u32_t length);

/** Return a count of the number of set bits.
*/

Modified: trunk/c_src/KinoSearch/Util/BitVector.c
===================================================================
--- trunk/c_src/KinoSearch/Util/BitVector.c 2008-07-28 20:24:29 UTC (rev 3660)
+++ trunk/c_src/KinoSearch/Util/BitVector.c 2008-07-29 17:16:41 UTC (rev 3661)
@@ -24,9 +24,9 @@
0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
};

-/* Clear a bit. Caller must ensure that num is within capacity.
+/* Clear a bit. Caller must ensure that tick is within capacity.
*/
-#define CLEAR(self, num) self->bits[ (num >> 3) ] &= ~(bitmasks[num & 0x7])
+#define CLEAR(self, tick) self->bits[ (tick >> 3) ] &= ~(bitmasks[tick & 0x7])

/* Number of 1 bits given a u8 value.
*/
@@ -108,18 +108,18 @@
}

void
-BitVec_set(BitVector *self, u32_t num)
+BitVec_set(BitVector *self, u32_t tick)
{
- BITVEC_GROW(self, num);
- self->bits[ (num >> 3) ] |= bitmasks[num & 0x7];
+ BITVEC_GROW(self, tick);
+ self->bits[ (tick >> 3) ] |= bitmasks[tick & 0x7];
}

void
-BitVec_clear(BitVector *self, u32_t num)
+BitVec_clear(BitVector *self, u32_t tick)
{
- if (num >= self->cap)
+ if (tick >= self->cap)
return;
- CLEAR(self, num);
+ CLEAR(self, tick);
}

void
@@ -130,11 +130,11 @@
}

bool_t
-BitVec_get(const BitVector *self, u32_t num)
+BitVec_get(const BitVector *self, u32_t tick)
{
- if (num >= self->cap)
+ if (tick >= self->cap)
return false;
- return (self->bits[ (num >> 3) ] & bitmasks[num & 0x7]) == 0
+ return (self->bits[ (tick >> 3) ] & bitmasks[tick & 0x7]) == 0
? false
: true;
}
@@ -244,31 +244,31 @@
}

void
-BitVec_flip(BitVector *self, u32_t num)
+BitVec_flip(BitVector *self, u32_t tick)
{
- const u32_t tick = num >> 3;
- const u8_t single_bit_mask = bitmasks[ (num % 8) ];
+ const u32_t byte_offset = tick >> 3;
+ const u8_t single_bit_mask = bitmasks[ (tick % 8) ];
u8_t byte;

- BITVEC_GROW(self, num);
- byte = self->bits[tick];
+ BITVEC_GROW(self, tick);
+ byte = self->bits[byte_offset];

if ((byte & single_bit_mask) == single_bit_mask) /* bit is set */
byte &= ~single_bit_mask; /* turn off one bit */
else
byte |= single_bit_mask; /* turn on one bit */

- self->bits[tick] = byte;
+ self->bits[byte_offset] = byte;
}

void
-BitVec_flip_range(BitVector *self, u32_t from_bit, u32_t to_bit)
+BitVec_flip_block(BitVector *self, u32_t offset, u32_t length)
{
- u32_t first = from_bit;
- u32_t last = to_bit - 1;
+ u32_t first = offset;
+ u32_t last = offset + length - 1;

/* Proceed only if we have bits to flip. */
- if (from_bit == to_bit)
+ if (!length)
return;

BITVEC_GROW(self, last);

Modified: trunk/perl/lib/KinoSearch/Util/BitVector.pm
===================================================================
--- trunk/perl/lib/KinoSearch/Util/BitVector.pm 2008-07-28 20:24:29 UTC (rev 3660)
+++ trunk/perl/lib/KinoSearch/Util/BitVector.pm 2008-07-29 17:16:41 UTC (rev 3661)
@@ -6,13 +6,35 @@

__AUTO_XS__

+my $synopsis = <<'END_SYNOPSIS';
+ my $bit_vec = KinoSearch::Util::BitVector->new( capacity => 8 );
+ my $other = KinoSearch::Util::BitVector->new( capacity => 8 );
+ $bit_vec->set($_) for ( 0, 2, 4, 6 );
+ $other->set($_) for ( 1, 3, 5, 7 );
+ $bit_vec->or($other);
+ print "$_\n" for @{ $bit_vec->to_array }; # prints 0 through 7.
+END_SYNOPSIS
+my $constructor = <<'END_CONSTRUCTOR';
+ my $bit_vec = KinoSearch::Util::BitVector->new(
+ capacity => $max_docs + 1, # default 0,
+ );
+END_CONSTRUCTOR
+
{ "KinoSearch::Util::BitVector" => {
bind_methods => [.
qw( get set clear clear_all grow count and or
- and_not xor flip flip_range to_array )
+ and_not xor flip flip_block to_array )
],
make_getters => [qw( cap count )],
make_constructors => ["new"],
+ make_pod => {
+ synopsis => $synopsis,
+ constructor => { sample => $constructor },
+ methods => [.
+ qw( get set clear clear_all grow count and or
+ and_not xor flip flip_block to_array )
+ ],
+ }
},
}


Modified: trunk/perl/t/013-bit_vector.t
===================================================================
--- trunk/perl/t/013-bit_vector.t 2008-07-28 20:24:29 UTC (rev 3660)
+++ trunk/perl/t/013-bit_vector.t 2008-07-29 17:16:41 UTC (rev 3661)
@@ -30,32 +30,32 @@

$bit_vec = KinoSearch::Util::BitVector->new;
for ( 0 .. 20 ) {
- $bit_vec->flip_range( from => $_, to => 21 );
+ $bit_vec->flip_block( offset => $_, length => 21 - $_ );
}
is_deeply(
$bit_vec->to_arrayref,
[. 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 ],
- 'flip range ascending'
+ 'flip_block ascending'
);

$bit_vec = KinoSearch::Util::BitVector->new;
-for ( reverse 1 .. 20 ) {
- $bit_vec->flip_range( from => 1, to => $_ );
+for ( reverse 0 .. 19 ) {
+ $bit_vec->flip_block( offset => 1, length => $_ );
}
is_deeply(
$bit_vec->to_arrayref,
[. 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],
- 'flip range descending'
+ 'flip_block descending'
);

-for my $lower ( 0 .. 17 ) {
- for my $amount ( 0 .. 17 ) {
- my $upper = $lower + $amount;
+for my $offset ( 0 .. 17 ) {
+ for my $length ( 0 .. 17 ) {
$bit_vec = KinoSearch::Util::BitVector->new;
- $bit_vec->flip_range( from => $lower, to => $upper );
- my $expected = $lower == $upper ? [] : [ $lower .. $upper - 1 ];
+ $bit_vec->flip_block( offset => $offset, length => $length );
+ my $upper = $offset + $length - 1;
+ my $expected = $length ? [ $offset .. $upper ] : [];
is_deeply( $bit_vec->to_arrayref, $expected,
- "flip range $lower .. $upper" );
+ "flip_block offset=$offset, length=$length" );
}
}



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