You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by ma...@apache.org on 2009/09/23 11:23:39 UTC
svn commit: r818014 - in /lucene/lucy/trunk: core/Lucy/Object/
core/Lucy/Test/Object/ core/Lucy/Util/ perl/lib/Lucy/ perl/lib/Lucy/Object/
perl/t/core/
Author: marvin
Date: Wed Sep 23 09:23:38 2009
New Revision: 818014
URL: http://svn.apache.org/viewvc?rev=818014&view=rev
Log:
Commit LUCY-52, adding BitVector.
Added:
lucene/lucy/trunk/core/Lucy/Object/BitVector.bp (with props)
lucene/lucy/trunk/core/Lucy/Object/BitVector.c (with props)
lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.bp (with props)
lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.c (with props)
lucene/lucy/trunk/perl/lib/Lucy/Object/BitVector.pm (with props)
lucene/lucy/trunk/perl/t/core/013-bit_vector.t (with props)
Modified:
lucene/lucy/trunk/core/Lucy/Util/ToolSet.h
lucene/lucy/trunk/perl/lib/Lucy/Test.pm
Added: lucene/lucy/trunk/core/Lucy/Object/BitVector.bp
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Object/BitVector.bp?rev=818014&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Object/BitVector.bp (added)
+++ lucene/lucy/trunk/core/Lucy/Object/BitVector.bp Wed Sep 23 09:23:38 2009
@@ -0,0 +1,156 @@
+parcel Lucy;
+
+/** An array of bits.
+ *
+ * BitVector is a growable array of bits. All bits are initially zero.
+ */
+
+class Lucy::Object::BitVector cnick BitVec
+ extends Lucy::Object::Obj {
+
+ u32_t cap;
+ u8_t *bits;
+
+ inert incremented BitVector*
+ new(u32_t capacity = 0);
+
+ /**
+ * @param capacity The number of bits that the initial array should be
+ * able to hold.
+ */
+ public inert BitVector*
+ init(BitVector *self, u32_t capacity = 0);
+
+ /** Return true if the bit at <code>tick</code> has been set, false if it
+ * hasn't (regardless of whether it lies within the bounds of the
+ * object's capacity).
+ *
+ * @param tick The requested bit.
+ */
+ public bool_t
+ Get(BitVector *self, u32_t tick);
+
+ /** Set the bit at <code>tick</code> to 1.
+ *
+ * @param tick The bit to be set.
+ */
+ public void
+ Set(BitVector *self, u32_t tick);
+
+ /** Accessor for the BitVector's underlying bit array.
+ */
+ u8_t*
+ Get_Raw_Bits(BitVector *self);
+
+ /** Accessor for capacity.
+ */
+ u32_t
+ Get_Capacity(BitVector *self);
+
+ /** Returns the next set bit equal to or greater than <code>tick</code>,
+ * or -1 if no such bit exists.
+ */
+ public 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.
+ */
+ public void
+ Clear(BitVector *self, u32_t tick);
+
+ /** Clear all bits.
+ */
+ public void
+ Clear_All(BitVector *self);
+
+ /** If the BitVector does not already have enough room to hold the
+ * indicated number of bits, allocate more memory so that it can.
+ *
+ * @param capacity Least number of bits the BitVector should accomodate.
+ */
+ public void
+ Grow(BitVector *self, u32_t capacity);
+
+ /** Modify the contents of this BitVector so that it has the same bits set
+ * as <code>other</code>.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ Mimic(BitVector *self, Obj *other);
+
+ /** Modify the BitVector so that only bits which remain set are those
+ * which 1) were already set in this BitVector, and 2) were also set in
+ * the other BitVector.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ And(BitVector *self, const BitVector *other);
+
+ /** Modify the BitVector, setting all bits which are set in the other
+ * BitVector if they were not already set.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ Or(BitVector *self, const BitVector *other);
+
+ /** Modify the BitVector, performing an XOR operation against the other.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ Xor(BitVector *self, const BitVector *other);
+
+ /** Modify the BitVector, clearing all bits which are set in the other.
+ *
+ * @param other Another BitVector.
+ */
+ public void
+ And_Not(BitVector *self, const BitVector *other);
+
+ /** Invert the value of a bit.
+ *
+ * @param tick The bit to invert.
+ */
+ public void
+ Flip(BitVector *self, u32_t tick);
+
+ /** Invert each bit within a contiguous block.
+ *
+ * @param offset Lower bound.
+ * @param length The number of bits to flip.
+ */
+ public void
+ Flip_Block(BitVector *self, u32_t offset, u32_t length);
+
+ /** Return a count of the number of set bits.
+ */
+ public u32_t
+ Count(BitVector *self);
+
+ public void
+ Destroy(BitVector *self);
+
+ public incremented BitVector*
+ Clone(BitVector *self);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Object/BitVector.bp
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Object/BitVector.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Object/BitVector.c?rev=818014&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Object/BitVector.c (added)
+++ lucene/lucy/trunk/core/Lucy/Object/BitVector.c Wed Sep 23 09:23:38 2009
@@ -0,0 +1,388 @@
+#define C_LUCY_BITVECTOR
+#include "Lucy/Util/ToolSet.h"
+
+#include <math.h>
+
+#include "Lucy/Object/BitVector.h"
+
+#define BITVEC_GROW(self, num) \
+ do { \
+ if (num >= self->cap) \
+ BitVec_Grow(self, num); \
+ } while (0)
+
+/* Shared subroutine for performing both OR and XOR ops.
+ */
+#define DO_OR 1
+#define DO_XOR 2
+static void
+S_do_or_or_xor(BitVector *self, const BitVector *other, int operation);
+
+/* 1 bit per byte. Use bitwise and to see if a bit is set.
+ */
+
+/* Clear a bit. Caller must ensure that tick is within capacity.
+ */
+#define CLEAR(self, tick) \
+ self->bits[ (tick >> 3) ] &= ~(lucy_NumUtil_u1masks[tick & 0x7])
+
+/* Number of 1 bits given a u8 value.
+ */
+static const u32_t BYTE_COUNTS[256] = {
+ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 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
+};
+
+
+BitVector*
+BitVec_new(u32_t capacity)
+{
+ BitVector *self = (BitVector*)VTable_Make_Obj(BITVECTOR);
+ return BitVec_init(self, capacity);
+}
+
+BitVector*
+BitVec_init(BitVector *self, u32_t capacity)
+{
+ const u32_t byte_size = (u32_t)ceil(capacity / 8.0);
+
+ /* Derive. */
+ self->bits = capacity ? (u8_t*)CALLOCATE(byte_size, sizeof(u8_t)) : NULL;
+
+ /* Assign. */
+ self->cap = byte_size * 8;
+
+ return self;
+}
+
+void
+BitVec_destroy(BitVector* self)
+{
+ FREEMEM(self->bits);
+ SUPER_DESTROY(self, BITVECTOR);
+}
+
+BitVector*
+BitVec_clone(BitVector *self)
+{
+ BitVector *evil_twin = BitVec_new(self->cap);
+ u32_t byte_size = (u32_t)ceil(self->cap / 8.0);
+
+ /* Forbid inheritance. */
+ if (Obj_Get_VTable(self) != BITVECTOR) {
+ THROW(ERR, "Attempt by %o to inherit BitVec_Clone",
+ Obj_Get_Class_Name(self));
+ }
+
+ memcpy(evil_twin->bits, self->bits, byte_size * sizeof(u8_t));
+
+ return evil_twin;
+}
+
+u8_t*
+BitVec_get_raw_bits(BitVector *self) { return self->bits; }
+u32_t
+BitVec_get_capacity(BitVector *self) { return self->cap; }
+
+void
+BitVec_mimic(BitVector *self, Obj *other)
+{
+ BitVector *evil_twin = (BitVector*)ASSERT_IS_A(other, BITVECTOR);
+ const u32_t my_byte_size = (u32_t)ceil(self->cap / 8.0);
+ const u32_t evil_twin_byte_size = (u32_t)ceil(evil_twin->cap / 8.0);
+ if (my_byte_size > evil_twin_byte_size) {
+ u32_t space = my_byte_size - evil_twin_byte_size;
+ memset(self->bits + evil_twin_byte_size, 0, space);
+ }
+ else {
+ BitVec_Grow(self, evil_twin->cap);
+ }
+ memcpy(self->bits, evil_twin->bits, evil_twin_byte_size);
+}
+
+void
+BitVec_grow(BitVector *self, u32_t new_max)
+{
+ if (new_max >= self->cap) {
+ const size_t old_byte_cap = (size_t)ceil(self->cap / 8.0);
+ const size_t new_byte_cap = (size_t)ceil((new_max + 1) / 8.0);
+ const size_t num_new_bytes = new_byte_cap - old_byte_cap;
+
+ self->bits = (u8_t*)REALLOCATE(self->bits, new_byte_cap);
+ memset(self->bits + old_byte_cap, 0, num_new_bytes);
+ self->cap = new_byte_cap * 8;
+ }
+}
+
+void
+BitVec_set(BitVector *self, u32_t tick)
+{
+ BITVEC_GROW(self, tick);
+ NumUtil_u1set(self->bits, tick);
+}
+
+void
+BitVec_clear(BitVector *self, u32_t tick)
+{
+ if (tick >= self->cap)
+ return;
+ CLEAR(self, tick);
+}
+
+void
+BitVec_clear_all(BitVector *self)
+{
+ const size_t byte_size = (size_t)ceil(self->cap / 8.0);
+ memset(self->bits, 0, byte_size);
+}
+
+bool_t
+BitVec_get(BitVector *self, u32_t tick)
+{
+ if (tick >= self->cap)
+ return false;
+ return NumUtil_u1get(self->bits, tick);
+}
+
+static i32_t
+S_first_bit_in_nonzero_byte(u8_t num)
+{
+ i32_t first_bit = 0;
+ if ((num & 0xF) == 0) { first_bit += 4; num >>= 4; }
+ if ((num & 0x3) == 0) { first_bit += 2; num >>= 2; }
+ if ((num & 0x1) == 0) { first_bit += 1; }
+ return first_bit;
+}
+
+i32_t
+BitVec_next_set_bit(BitVector *self, u32_t tick)
+{
+ size_t byte_size = (size_t)ceil(self->cap / 8.0);
+ u8_t *const limit = self->bits + byte_size;
+ u8_t *ptr = self->bits + (tick >> 3);
+
+ if (ptr >= limit) {
+ return -1;
+ }
+ else if (*ptr != 0) {
+ /* Special case the first byte. */
+ const i32_t base = (ptr - self->bits) * 8;
+ const i32_t min_sub_tick = tick & 0x7;
+ unsigned int byte = *ptr >> min_sub_tick;
+ if (byte) {
+ const i32_t candidate = base + min_sub_tick +
+ S_first_bit_in_nonzero_byte(byte);
+ return candidate < (i32_t)self->cap ? candidate : -1;
+ }
+ }
+
+ for (ptr++ ; ptr < limit; ptr++) {
+ if (*ptr != 0) {
+ /* There's a non-zero bit in this byte. */
+ const i32_t base = (ptr - self->bits) * 8;
+ const i32_t candidate = base + S_first_bit_in_nonzero_byte(*ptr);
+ return candidate < (i32_t)self->cap ? candidate : -1;
+ }
+ }
+
+ return -1;
+}
+
+void
+BitVec_and(BitVector *self, const BitVector *other)
+{
+ u8_t *bits_a = self->bits;
+ u8_t *bits_b = other->bits;
+ const u32_t min_cap = self->cap < other->cap
+ ? self->cap
+ : other->cap;
+ const size_t byte_size = (size_t)ceil(min_cap / 8.0);
+ u8_t *const limit = bits_a + byte_size;
+
+ /* Intersection. */
+ while (bits_a < limit) {
+ *bits_a &= *bits_b;
+ bits_a++, bits_b++;
+ }
+
+ /* Set all remaining to zero. */
+ if (self->cap > min_cap) {
+ const size_t self_byte_size = (size_t)ceil(self->cap / 8.0);
+ memset(bits_a, 0, self_byte_size - byte_size);
+ }
+}
+
+void
+BitVec_or(BitVector *self, const BitVector *other)
+{
+ S_do_or_or_xor(self, other, DO_OR);
+}
+
+void
+BitVec_xor(BitVector *self, const BitVector *other)
+{
+ S_do_or_or_xor(self, other, DO_XOR);
+}
+
+static void
+S_do_or_or_xor(BitVector *self, const BitVector *other, int operation)
+{
+ u8_t *bits_a, *bits_b;
+ u32_t max_cap, min_cap;
+ u8_t *limit;
+ double byte_size;
+
+ /* Sort out what the minimum and maximum caps are. */
+ if (self->cap < other->cap) {
+ max_cap = other->cap;
+ min_cap = self->cap;
+ }
+ else {
+ max_cap = self->cap;
+ min_cap = other->cap;
+ }
+
+ /* Grow self if smaller than other, then calc pointers. */
+ BITVEC_GROW(self, max_cap);
+ bits_a = self->bits;
+ bits_b = other->bits;
+ byte_size = ceil(min_cap / 8.0);
+ limit = self->bits + (size_t)byte_size;
+
+ /* Perform union of common bits. */
+ if (operation == DO_OR) {
+ while (bits_a < limit) {
+ *bits_a |= *bits_b;
+ bits_a++, bits_b++;
+ }
+ }
+ else if (operation == DO_XOR) {
+ while (bits_a < limit) {
+ *bits_a ^= *bits_b;
+ bits_a++, bits_b++;
+ }
+ }
+ else {
+ THROW(ERR, "Unrecognized operation: %i32", (i32_t)operation);
+ }
+
+ /* Copy remaining bits if other is bigger than self. */
+ if (other->cap > min_cap) {
+ const double other_byte_size = ceil(other->cap / 8.0);
+ const size_t bytes_to_copy = (size_t)(other_byte_size - byte_size);
+ memcpy(bits_a, bits_b, bytes_to_copy);
+ }
+}
+
+void
+BitVec_and_not(BitVector *self, const BitVector *other)
+{
+ u8_t *bits_a = self->bits;
+ u8_t *bits_b = other->bits;
+ const u32_t min_cap = self->cap < other->cap
+ ? self->cap
+ : other->cap;
+ const size_t byte_size = (size_t)ceil(min_cap / 8.0);
+ u8_t *const limit = bits_a + byte_size;
+
+ /* Clear bits set in other. */
+ while (bits_a < limit) {
+ *bits_a &= ~(*bits_b);
+ bits_a++, bits_b++;
+ }
+}
+
+void
+BitVec_flip(BitVector *self, u32_t tick)
+{
+ BITVEC_GROW(self, tick);
+ NumUtil_u1flip(self->bits, tick);
+}
+
+void
+BitVec_flip_block(BitVector *self, u32_t offset, u32_t length)
+{
+ u32_t first = offset;
+ u32_t last = offset + length - 1;
+
+ /* Bail if there's nothing to flip. */
+ if (!length) { return; }
+
+ BITVEC_GROW(self, last);
+
+ /* Flip partial bytes. */
+ while (last % 8 != 0 && last > first) {
+ NumUtil_u1flip(self->bits, last);
+ last--;
+ }
+ while (first % 8 != 0 && first < last) {
+ NumUtil_u1flip(self->bits, first);
+ first++;
+ }
+
+ /* Are first and last equal? */
+ if (first == last) {
+ /* There's only one bit left to flip. */
+ NumUtil_u1flip(self->bits, last);
+ }
+ /* They must be multiples of 8, then. */
+ else {
+ const u32_t start_tick = first >> 3;
+ const u32_t limit_tick = last >> 3;
+ u8_t *bits = self->bits + start_tick;
+ u8_t *limit = self->bits + limit_tick;
+
+ /* Last actually belongs to the following byte (e.g. 8, in byte 2). */
+ NumUtil_u1flip(self->bits, last);
+
+ /* Flip whole bytes. */
+ for ( ; bits < limit; bits++) {
+ *bits = ~(*bits);
+ }
+ }
+}
+
+u32_t
+BitVec_count(BitVector *self)
+{
+ u32_t count = 0;
+ const size_t byte_size = (size_t)ceil(self->cap / 8.0);
+ u8_t *ptr = self->bits;
+ u8_t *const limit = ptr + byte_size;
+
+ for( ; ptr < limit; ptr++) {
+ count += BYTE_COUNTS[*ptr];
+ }
+
+ return count;
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Object/BitVector.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.bp
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.bp?rev=818014&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.bp (added)
+++ lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.bp Wed Sep 23 09:23:38 2009
@@ -0,0 +1,22 @@
+parcel Lucy;
+
+inert class Lucy::Test::Object::TestBitVector {
+ inert void
+ run_tests();
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.bp
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.c?rev=818014&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.c (added)
+++ lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.c Wed Sep 23 09:23:38 2009
@@ -0,0 +1,429 @@
+#define C_LUCY_TESTBITVECTOR
+#include "Lucy/Util/ToolSet.h"
+
+#include "Lucy/Test.h"
+#include "Lucy/Test/Object/TestBitVector.h"
+
+static void
+test_Set_and_Get(TestBatch *batch)
+{
+ unsigned i, max;
+ const u32_t three = 3;
+ const u32_t seventeen = 17;
+ BitVector *bit_vec = BitVec_new(8);
+
+ BitVec_Set(bit_vec, three);
+ ASSERT_TRUE(batch, BitVec_Get_Capacity(bit_vec) < seventeen,
+ "set below cap");
+ BitVec_Set(bit_vec, seventeen);
+ ASSERT_TRUE(batch, BitVec_Get_Capacity(bit_vec) > seventeen,
+ "set above cap causes BitVector to grow");
+
+ for (i = 0, max = BitVec_Get_Capacity(bit_vec); i < max; i++) {
+ if (i == three || i == seventeen) {
+ ASSERT_TRUE(batch, BitVec_Get(bit_vec, i), "set/get %d", i);
+ }
+ else {
+ ASSERT_FALSE(batch, BitVec_Get(bit_vec, i), "get %d", i);
+ }
+ }
+ ASSERT_FALSE(batch, BitVec_Get(bit_vec, i), "out of range get");
+
+ DECREF(bit_vec);
+}
+
+static void
+test_Flip(TestBatch *batch)
+{
+ BitVector *bit_vec = BitVec_new(0);
+ int i;
+
+ for (i = 0; i <= 20; i++) { BitVec_Flip(bit_vec, i); }
+ for (i = 0; i <= 20; i++) {
+ ASSERT_TRUE(batch, BitVec_Get(bit_vec, i), "flip on %d", i);
+ }
+ ASSERT_FALSE(batch, BitVec_Get(bit_vec, i), "no flip %d", i);
+ for (i = 0; i <= 20; i++) { BitVec_Flip(bit_vec, i); }
+ for (i = 0; i <= 20; i++) {
+ ASSERT_FALSE(batch, BitVec_Get(bit_vec, i), "flip off %d", i);
+ }
+ ASSERT_FALSE(batch, BitVec_Get(bit_vec, i), "still no flip %d", i);
+
+ DECREF(bit_vec);
+}
+
+static void
+test_Flip_Block_ascending(TestBatch *batch)
+{
+ BitVector *bit_vec = BitVec_new(0);
+ int i;
+
+ for (i = 0; i <= 20; i++) {
+ BitVec_Flip_Block(bit_vec, i, 21 - i);
+ }
+
+ for (i = 0; i <= 20; i++) {
+ if (i % 2 == 0) {
+ ASSERT_TRUE(batch, BitVec_Get(bit_vec, i),
+ "Flip_Block ascending %d", i);
+ }
+ else {
+ ASSERT_FALSE(batch, BitVec_Get(bit_vec, i),
+ "Flip_Block ascending %d", i);
+ }
+ }
+
+ DECREF(bit_vec);
+}
+
+static void
+test_Flip_Block_descending(TestBatch *batch)
+{
+ BitVector *bit_vec = BitVec_new(0);
+ int i;
+
+ for (i = 19; i >= 0; i--) {
+ BitVec_Flip_Block(bit_vec, 1, i);
+ }
+
+ for (i = 0; i <= 20; i++) {
+ if (i % 2) {
+ ASSERT_TRUE(batch, BitVec_Get(bit_vec, i),
+ "Flip_Block descending %d", i);
+ }
+ else {
+ ASSERT_FALSE(batch, BitVec_Get(bit_vec, i),
+ "Flip_Block descending %d", i);
+ }
+ }
+
+ DECREF(bit_vec);
+}
+
+static void
+test_Flip_Block_bulk(TestBatch *batch)
+{
+ i32_t offset;
+
+ for (offset = 0; offset <= 17; offset++) {
+ i32_t len;
+ for (len = 0; len <= 17; len++) {
+ int i;
+ int upper = offset + len - 1;
+ BitVector *bit_vec = BitVec_new(0);
+
+ BitVec_Flip_Block(bit_vec, offset, len);
+ for (i = 0; i <= 17; i++) {
+ if (i >= offset && i <= upper) {
+ if (!BitVec_Get(bit_vec, i)) { break; }
+ }
+ else {
+ if (BitVec_Get(bit_vec, i)) { break; }
+ }
+ }
+ ASSERT_INT_EQ(batch, i, 18, "Flip_Block(%d, %d)", offset, len);
+
+ DECREF(bit_vec);
+ }
+ }
+}
+
+static void
+test_Mimic(TestBatch *batch)
+{
+ int foo;
+
+ for (foo = 0; foo <= 17; foo++) {
+ int bar;
+ for (bar = 0; bar <= 17; bar++) {
+ int i;
+ BitVector *foo_vec = BitVec_new(0);
+ BitVector *bar_vec = BitVec_new(0);
+
+ BitVec_Set(foo_vec, foo);
+ BitVec_Set(bar_vec, bar);
+ BitVec_Mimic(foo_vec, (Obj*)bar_vec);
+
+ for (i = 0; i <= 17; i++) {
+ if (BitVec_Get(foo_vec, i) && i != bar) { break; }
+ }
+ ASSERT_INT_EQ(batch, i, 18, "Mimic(%d, %d)", foo, bar);
+
+ DECREF(foo_vec);
+ DECREF(bar_vec);
+ }
+ }
+}
+
+static BitVector*
+S_create_set(int set_num)
+{
+ int i;
+ int nums_1[] = { 1, 2, 3, 10, 20, 30, 0 };
+ int nums_2[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10,
+ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 0 };
+ int *nums = set_num == 1 ? nums_1 : nums_2;
+ BitVector *bit_vec = BitVec_new(31);
+ for (i = 0; nums[i] != 0; i++) {
+ BitVec_Set(bit_vec, nums[i]);
+ }
+ return bit_vec;
+}
+
+#define OP_OR 1
+#define OP_XOR 2
+#define OP_AND 3
+#define OP_AND_NOT 4
+static int
+S_verify_logical_op(BitVector *bit_vec, BitVector *set_1, BitVector *set_2,
+ int op)
+{
+ int i;
+
+ for (i = 0; i < 50; i++) {
+ bool_t wanted;
+
+ switch(op) {
+ case OP_OR:
+ wanted = BitVec_Get(set_1, i) || BitVec_Get(set_2, i);
+ break;
+ case OP_XOR:
+ wanted = (!BitVec_Get(set_1, i)) != (!BitVec_Get(set_2, i));
+ break;
+ case OP_AND:
+ wanted = BitVec_Get(set_1, i) && BitVec_Get(set_2, i);
+ break;
+ case OP_AND_NOT:
+ wanted = BitVec_Get(set_1, i) && (!BitVec_Get(set_2, i));
+ break;
+ default:
+ wanted = false;
+ THROW(ERR, "unknown op: %d", op);
+ }
+
+ if (BitVec_Get(bit_vec, i) != wanted) { break; }
+ }
+
+ return i;
+}
+
+static void
+test_Or(TestBatch *batch)
+{
+ BitVector *smaller = S_create_set(1);
+ BitVector *larger = S_create_set(2);
+ BitVector *set_1 = S_create_set(1);
+ BitVector *set_2 = S_create_set(2);
+
+ BitVec_Or(smaller, set_2);
+ ASSERT_INT_EQ(batch, S_verify_logical_op(smaller, set_1, set_2, OP_OR),
+ 50, "OR with self smaller than other");
+ BitVec_Or(larger, set_1);
+ ASSERT_INT_EQ(batch, S_verify_logical_op(larger, set_1, set_2, OP_OR),
+ 50, "OR with other smaller than self");
+
+ DECREF(smaller);
+ DECREF(larger);
+ DECREF(set_1);
+ DECREF(set_2);
+}
+
+static void
+test_Xor(TestBatch *batch)
+{
+ BitVector *smaller = S_create_set(1);
+ BitVector *larger = S_create_set(2);
+ BitVector *set_1 = S_create_set(1);
+ BitVector *set_2 = S_create_set(2);
+
+ BitVec_Xor(smaller, set_2);
+ ASSERT_INT_EQ(batch, S_verify_logical_op(smaller, set_1, set_2, OP_XOR),
+ 50, "XOR with self smaller than other");
+ BitVec_Xor(larger, set_1);
+ ASSERT_INT_EQ(batch, S_verify_logical_op(larger, set_1, set_2, OP_XOR),
+ 50, "XOR with other smaller than self");
+
+ DECREF(smaller);
+ DECREF(larger);
+ DECREF(set_1);
+ DECREF(set_2);
+}
+
+static void
+test_And(TestBatch *batch)
+{
+ BitVector *smaller = S_create_set(1);
+ BitVector *larger = S_create_set(2);
+ BitVector *set_1 = S_create_set(1);
+ BitVector *set_2 = S_create_set(2);
+
+ BitVec_And(smaller, set_2);
+ ASSERT_INT_EQ(batch, S_verify_logical_op(smaller, set_1, set_2, OP_AND),
+ 50, "AND with self smaller than other");
+ BitVec_And(larger, set_1);
+ ASSERT_INT_EQ(batch, S_verify_logical_op(larger, set_1, set_2, OP_AND),
+ 50, "AND with other smaller than self");
+
+ DECREF(smaller);
+ DECREF(larger);
+ DECREF(set_1);
+ DECREF(set_2);
+}
+
+static void
+test_And_Not(TestBatch *batch)
+{
+ BitVector *smaller = S_create_set(1);
+ BitVector *larger = S_create_set(2);
+ BitVector *set_1 = S_create_set(1);
+ BitVector *set_2 = S_create_set(2);
+
+ BitVec_And_Not(smaller, set_2);
+ ASSERT_INT_EQ(batch,
+ S_verify_logical_op(smaller, set_1, set_2, OP_AND_NOT),
+ 50, "AND_NOT with self smaller than other");
+ BitVec_And_Not(larger, set_1);
+ ASSERT_INT_EQ(batch,
+ S_verify_logical_op(larger, set_2, set_1, OP_AND_NOT),
+ 50, "AND_NOT with other smaller than self");
+
+ DECREF(smaller);
+ DECREF(larger);
+ DECREF(set_1);
+ DECREF(set_2);
+}
+
+static void
+test_Count(TestBatch *batch)
+{
+ int i;
+ int shuffled[64];
+ BitVector *bit_vec = BitVec_new(64);
+
+ for (i = 0; i < 64; i++) { shuffled[i] = i; }
+ for (i = 0; i < 64; i++) {
+ int shuffle_pos = rand() % 64;
+ int temp = shuffled[shuffle_pos];
+ shuffled[shuffle_pos] = shuffled[i];
+ shuffled[i] = temp;
+ }
+ for (i = 0; i < 64; i++) {
+ BitVec_Set(bit_vec, shuffled[i]);
+ if (BitVec_Count(bit_vec) != (u32_t)(i + 1)) { break; }
+ }
+ ASSERT_INT_EQ(batch, i, 64, "Count() returns the right number of bits");
+
+ DECREF(bit_vec);
+}
+
+static void
+test_Next_Set_Bit(TestBatch *batch)
+{
+ int i;
+
+ for (i = 24; i <= 33; i++) {
+ int probe;
+ BitVector *bit_vec = BitVec_new(64);
+ BitVec_Set(bit_vec, i);
+ ASSERT_INT_EQ(batch, BitVec_Next_Set_Bit(bit_vec, 0), i,
+ "Next_Set_Bit for 0 is %d", i);
+ ASSERT_INT_EQ(batch, BitVec_Next_Set_Bit(bit_vec, 0), i,
+ "Next_Set_Bit for 1 is %d", i);
+ for (probe = 15; probe <= i; probe++) {
+ ASSERT_INT_EQ(batch, BitVec_Next_Set_Bit(bit_vec, probe), i,
+ "Next_Set_Bit for %d is %d", probe, i);
+ }
+ for (probe = i + 1; probe <= i + 9; probe++) {
+ ASSERT_INT_EQ(batch, BitVec_Next_Set_Bit(bit_vec, probe), -1,
+ "no Next_Set_Bit for %d when max is %d", probe, i );
+ }
+ DECREF(bit_vec);
+ }
+}
+
+static void
+test_Clear_All(TestBatch *batch)
+{
+ BitVector *bit_vec = BitVec_new(64);
+ BitVec_Flip_Block(bit_vec, 0, 63);
+ BitVec_Clear_All(bit_vec);
+ ASSERT_INT_EQ(batch, BitVec_Next_Set_Bit(bit_vec, 0), -1, "Clear_All");
+ DECREF(bit_vec);
+}
+
+static void
+test_Clone(TestBatch *batch)
+{
+ int i;
+ BitVector *self = BitVec_new(30);
+ BitVector *evil_twin;
+
+ BitVec_Set(self, 2);
+ BitVec_Set(self, 3);
+ BitVec_Set(self, 10);
+ BitVec_Set(self, 20);
+
+ evil_twin = BitVec_Clone(self);
+ for (i = 0; i < 50; i++) {
+ if (BitVec_Get(self, i) != BitVec_Get(evil_twin, i)) { break; }
+ }
+ ASSERT_INT_EQ(batch, i, 50, "Clone");
+ ASSERT_INT_EQ(batch, BitVec_Count(evil_twin), 4, "clone Count");
+
+ DECREF(self);
+ DECREF(evil_twin);
+}
+
+/* Valgrind only - detect off-by-one error. */
+static void
+test_off_by_one_error()
+{
+ int cap;
+ for (cap = 5; cap <= 24; cap++) {
+ BitVector *bit_vec = BitVec_new(cap);
+ BitVec_Set(bit_vec, cap - 2);
+ DECREF(bit_vec);
+ }
+}
+
+void
+TestBitVector_run_tests()
+{
+ TestBatch *batch = Test_new_batch("TestInStream", 1028, NULL);
+
+ PLAN(batch);
+
+ test_Set_and_Get(batch);
+ test_Flip(batch);
+ test_Flip_Block_ascending(batch);
+ test_Flip_Block_descending(batch);
+ test_Flip_Block_bulk(batch);
+ test_Mimic(batch);
+ test_Or(batch);
+ test_Xor(batch);
+ test_And(batch);
+ test_And_Not(batch);
+ test_Count(batch);
+ test_Next_Set_Bit(batch);
+ test_Clear_All(batch);
+ test_Clone(batch);
+ test_off_by_one_error();
+
+ batch->destroy(batch);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/core/Lucy/Test/Object/TestBitVector.c
------------------------------------------------------------------------------
svn:eol-style = native
Modified: lucene/lucy/trunk/core/Lucy/Util/ToolSet.h
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Util/ToolSet.h?rev=818014&r1=818013&r2=818014&view=diff
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Util/ToolSet.h (original)
+++ lucene/lucy/trunk/core/Lucy/Util/ToolSet.h Wed Sep 23 09:23:38 2009
@@ -19,7 +19,7 @@
#include <stdlib.h>
#include <string.h>
#include "Lucy/Object/Obj.h"
-/* #include "Lucy/Object/BitVector.h" */
+#include "Lucy/Object/BitVector.h"
/* #include "Lucy/Object/ByteBuf.h" */
#include "Lucy/Object/CharBuf.h"
#include "Lucy/Object/Err.h"
Added: lucene/lucy/trunk/perl/lib/Lucy/Object/BitVector.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/lib/Lucy/Object/BitVector.pm?rev=818014&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/lib/Lucy/Object/BitVector.pm (added)
+++ lucene/lucy/trunk/perl/lib/Lucy/Object/BitVector.pm Wed Sep 23 09:23:38 2009
@@ -0,0 +1,82 @@
+use Lucy;
+
+1;
+
+__END__
+
+__BINDING__
+
+my $synopsis = <<'END_SYNOPSIS';
+ my $bit_vec = Lucy::Object::BitVector->new( capacity => 8 );
+ my $other = Lucy::Object::BitVector->new( capacity => 8 );
+ $bit_vec->set($_) for ( 0, 2, 4, 6 );
+ $other->set($_) for ( 1, 3, 5, 7 );
+ $bit_vec->or($other);
+END_SYNOPSIS
+my $constructor = <<'END_CONSTRUCTOR';
+ my $bit_vec = Lucy::Object::BitVector->new(
+ capacity => $doc_max + 1, # default 0,
+ );
+END_CONSTRUCTOR
+
+Boilerplater::Binding::Perl::Class->register(
+ parcel => "Lucy",
+ class_name => "Lucy::Object::BitVector",
+ bind_methods => [
+ qw( Get
+ Set
+ Clear
+ Clear_All
+ And
+ Or
+ And_Not
+ Xor
+ Flip
+ Flip_Block
+ Next_Set_Bit
+ Grow
+ Count
+ Get_Capacity
+ )
+ ],
+ bind_constructors => ["new"],
+ make_pod => {
+ synopsis => $synopsis,
+ constructor => { sample => $constructor },
+ methods => [
+ qw( get
+ set
+ clear
+ clear_all
+ and
+ or
+ and_not
+ xor
+ flip
+ flip_block
+ next_set_bit
+ grow
+ count
+ )
+ ],
+ }
+);
+
+__COPYRIGHT__
+
+ /**
+ * Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ * implied. See the License for the specific language governing
+ * permissions and limitations under the License.
+ */
+
Propchange: lucene/lucy/trunk/perl/lib/Lucy/Object/BitVector.pm
------------------------------------------------------------------------------
svn:eol-style = native
Modified: lucene/lucy/trunk/perl/lib/Lucy/Test.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/lib/Lucy/Test.pm?rev=818014&r1=818013&r2=818014&view=diff
==============================================================================
--- lucene/lucy/trunk/perl/lib/Lucy/Test.pm (original)
+++ lucene/lucy/trunk/perl/lib/Lucy/Test.pm Wed Sep 23 09:23:38 2009
@@ -18,6 +18,9 @@
if (strEQ(package, "TestObj")) {
lucy_TestObj_run_tests();
}
+ else if (strEQ(package, "TestBitVector")) {
+ lucy_TestBitVector_run_tests();
+ }
else if (strEQ(package, "TestCharBuf")) {
lucy_TestCB_run_tests();
}
Added: lucene/lucy/trunk/perl/t/core/013-bit_vector.t
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/t/core/013-bit_vector.t?rev=818014&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/t/core/013-bit_vector.t (added)
+++ lucene/lucy/trunk/perl/t/core/013-bit_vector.t Wed Sep 23 09:23:38 2009
@@ -0,0 +1,6 @@
+use strict;
+use warnings;
+
+use Lucy::Test;
+Lucy::Test::run_tests("TestBitVector");
+
Propchange: lucene/lucy/trunk/perl/t/core/013-bit_vector.t
------------------------------------------------------------------------------
svn:eol-style = native