| /* |
| * 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. |
| */ |
| package org.apache.cassandra.io.tries; |
| |
| import java.io.IOException; |
| |
| import org.junit.Test; |
| |
| import org.apache.cassandra.io.util.DataOutputBuffer; |
| import org.apache.cassandra.io.util.Rebufferer; |
| import org.apache.cassandra.io.util.TailOverridingRebufferer; |
| |
| import static org.junit.Assert.assertEquals; |
| |
| public class TrieBuilderTest extends AbstractTrieTestBase |
| { |
| @Test |
| public void testPartialBuildRecalculationBug() throws IOException |
| { |
| DataOutputBuffer buf = new DataOutputBufferPaged(); |
| IncrementalTrieWriter<Integer> builder = newTrieWriter(serializer, buf); |
| long count = 0; |
| |
| count += addUntilBytesWritten(buf, builder, "a", 1); // Make a node whose children are written |
| long reset = count; |
| count += addUntilBytesWritten(buf, builder, "c", 64 * 1024); // Finalize it and write long enough to grow its pointer size |
| |
| dump = true; |
| IncrementalTrieWriter.PartialTail tail = builder.makePartialRoot(); |
| // The line above hit an assertion as that node's parent had a pre-calculated branch size which was no longer |
| // correct, and we didn't bother to reset it. |
| dump = false; |
| |
| // Check that partial representation has the right content. |
| Rebufferer source = new ByteBufRebufferer(buf.asNewBuffer()); |
| source = new TailOverridingRebufferer(source, tail.cutoff(), tail.tail()); |
| verifyContent(count, source, tail.root(), reset); |
| |
| long reset2 = count; |
| |
| // Also check the completed trie. |
| count += addUntilBytesWritten(buf, builder, "e", 16 * 1024); |
| dump = true; |
| long root = builder.complete(); |
| // The line above hit another size assertion as the size of a node's branch growing caused it to need to switch |
| // format, but we didn't bother to recalculate its size. |
| dump = false; |
| |
| source = new ByteBufRebufferer(buf.asNewBuffer()); |
| verifyContent(count, source, root, reset, reset2); |
| } |
| |
| public void verifyContent(long count, Rebufferer source, long root, long... resets) |
| { |
| ValueIterator<?> iter = new ValueIterator<>(source, root); |
| long found = 0; |
| long ofs = 0; |
| int rpos = 0; |
| long pos; |
| while ((pos = iter.nextPayloadedNode()) != -1) |
| { |
| iter.go(pos); |
| assertEquals(valueFor(found - ofs), iter.payloadFlags()); |
| ++found; |
| if (rpos < resets.length && found >= resets[rpos]) |
| { |
| ofs = resets[rpos]; |
| ++rpos; |
| } |
| } |
| assertEquals(count, found); |
| } |
| |
| private long addUntilBytesWritten(DataOutputBuffer buf, |
| IncrementalTrieWriter<Integer> builder, |
| String prefix, |
| long howMany) throws IOException |
| { |
| long pos = buf.position(); |
| long idx = 0; |
| while (pos + howMany > buf.position()) |
| { |
| builder.add(source(String.format("%s%8s", prefix, toBase(idx))), valueFor(idx)); |
| logger.info("Adding {} : {}", String.format("%s%8s", prefix, toBase(idx)), valueFor(idx)); |
| ++idx; |
| } |
| logger.info(String.format("%s%8s", prefix, toBase(idx - 1))); |
| return idx; |
| } |
| } |