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 2011/02/25 03:05:59 UTC
[lucy-commits] svn commit: r1074378 - in /incubator/lucy/trunk:
core/Lucy/Index/PolyReader.c core/Lucy/Test/Index/TestPolyReader.c
core/Lucy/Test/Index/TestPolyReader.cfh perl/lib/Lucy/Test.pm
perl/t/core/225-polyreader.t
Author: marvin
Date: Fri Feb 25 02:05:58 2011
New Revision: 1074378
URL: http://svn.apache.org/viewvc?rev=1074378&view=rev
Log:
Fix a latent binary search bug in PolyReader_sub_tick that could theoretically
result in the wrong document being returned in a search. In practice, the bug
was hidden because the default merge algo could not produce the conditions
necessary to trigger the glitch.
Added:
incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.c
incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.cfh
incubator/lucy/trunk/perl/t/core/225-polyreader.t
Modified:
incubator/lucy/trunk/core/Lucy/Index/PolyReader.c
incubator/lucy/trunk/perl/lib/Lucy/Test.pm
Modified: incubator/lucy/trunk/core/Lucy/Index/PolyReader.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/core/Lucy/Index/PolyReader.c?rev=1074378&r1=1074377&r2=1074378&view=diff
==============================================================================
--- incubator/lucy/trunk/core/Lucy/Index/PolyReader.c (original)
+++ incubator/lucy/trunk/core/Lucy/Index/PolyReader.c Fri Feb 25 02:05:58 2011
@@ -485,28 +485,37 @@ PolyReader_get_seg_readers(PolyReader *s
uint32_t
PolyReader_sub_tick(I32Array *offsets, int32_t doc_id)
{
- uint32_t lo = 0;
- uint32_t hi_tick = I32Arr_Get_Size(offsets) - 1;
- uint32_t hi = hi_tick;
+ int32_t size = I32Arr_Get_Size(offsets);
+ if (size == 0) {
+ return 0;
+ }
- while (hi >= lo) {
- uint32_t mid = lo + ((hi - lo) / 2);
- int32_t mid_start = I32Arr_Get(offsets, mid) + 1;
- if (doc_id < mid_start) {
- hi = mid - 1;
- }
- else if (doc_id > mid_start) {
- lo = mid + 1;
+ int32_t lo = -1;
+ int32_t hi = size;
+ while (hi - lo > 1) {
+ int32_t mid = lo + ((hi - lo) / 2);
+ int32_t offset = I32Arr_Get(offsets, mid);
+ if (doc_id <= offset) {
+ hi = mid;
+ }
+ else {
+ lo = mid;
+ }
+ }
+ if (hi == size) {
+ hi--;
+ }
+
+ while (hi > 0) {
+ int32_t offset = I32Arr_Get(offsets, hi);
+ if (doc_id <= offset) {
+ hi--;
}
else {
- while ( mid < hi_tick
- && I32Arr_Get(offsets, mid + 1) == mid_start
- ) {
- mid++;
- }
- return mid;
+ break;
}
}
+
return hi;
}
Added: incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.c
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.c?rev=1074378&view=auto
==============================================================================
--- incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.c (added)
+++ incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.c Fri Feb 25 02:05:58 2011
@@ -0,0 +1,51 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.
+ */
+
+#define C_LUCY_TESTPOLYREADER
+#include "Lucy/Util/ToolSet.h"
+
+#include "Lucy/Test.h"
+#include "Lucy/Test/Index/TestPolyReader.h"
+#include "Lucy/Index/PolyReader.h"
+
+static void
+test_sub_tick(TestBatch *batch)
+{
+ size_t num_segs = 255;
+ int32_t *ints = (int32_t*)MALLOCATE(num_segs * sizeof(int32_t));
+ size_t i;
+ for (i = 0; i < num_segs; i++) {
+ ints[i] = i;
+ }
+ I32Array *offsets = I32Arr_new(ints, num_segs);
+ for (i = 1; i < num_segs; i++) {
+ if (PolyReader_sub_tick(offsets, i) != i - 1) { break; }
+ }
+ TEST_INT_EQ(batch, i, num_segs, "got all sub_tick() calls right");
+ DECREF(offsets);
+}
+
+void
+TestPolyReader_run_tests()
+{
+ TestBatch *batch = TestBatch_new(1);
+ TestBatch_Plan(batch);
+
+ test_sub_tick(batch);
+
+ DECREF(batch);
+}
+
Added: incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.cfh
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.cfh?rev=1074378&view=auto
==============================================================================
--- incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.cfh (added)
+++ incubator/lucy/trunk/core/Lucy/Test/Index/TestPolyReader.cfh Fri Feb 25 02:05:58 2011
@@ -0,0 +1,23 @@
+/* Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.
+ */
+
+parcel Lucy;
+
+inert class Lucy::Test::Index::TestPolyReader {
+ inert void
+ run_tests();
+}
+
Modified: incubator/lucy/trunk/perl/lib/Lucy/Test.pm
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/perl/lib/Lucy/Test.pm?rev=1074378&r1=1074377&r2=1074378&view=diff
==============================================================================
--- incubator/lucy/trunk/perl/lib/Lucy/Test.pm (original)
+++ incubator/lucy/trunk/perl/lib/Lucy/Test.pm Fri Feb 25 02:05:58 2011
@@ -97,6 +97,9 @@ PPCODE:
else if (strEQ(package, "TestIndexManager")) {
lucy_TestIxManager_run_tests();
}
+ else if (strEQ(package, "TestPolyReader")) {
+ lucy_TestPolyReader_run_tests();
+ }
else if (strEQ(package, "TestPostingListWriter")) {
lucy_TestPListWriter_run_tests();
}
Added: incubator/lucy/trunk/perl/t/core/225-polyreader.t
URL: http://svn.apache.org/viewvc/incubator/lucy/trunk/perl/t/core/225-polyreader.t?rev=1074378&view=auto
==============================================================================
--- incubator/lucy/trunk/perl/t/core/225-polyreader.t (added)
+++ incubator/lucy/trunk/perl/t/core/225-polyreader.t Fri Feb 25 02:05:58 2011
@@ -0,0 +1,21 @@
+# Licensed to the Apache Software Foundation (ASF) under one or more
+# contributor license agreements. See the NOTICE file distributed with
+# this work for additional information regarding copyright ownership.
+# The ASF licenses this file to You 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.
+
+use strict;
+use warnings;
+
+use Lucy::Test;
+Lucy::Test::run_tests("TestPolyReader");
+