[deliverable/tracecompass.git] / statesystem / org.eclipse.tracecompass.statesystem.core.tests / src / org / eclipse / tracecompass / statesystem / core / tests / backend / historytree / HistoryTreeTest.java

/*******************************************************************************
 * Copyright (c) 2015 École Polytechnique de Montréal
 *
 * All rights reserved. This program and the accompanying materials are
 * made available under the terms of the Eclipse Public License v1.0 which
 * accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *******************************************************************************/

package org.eclipse.tracecompass.statesystem.core.tests.backend.historytree;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.fail;

import java.io.File;
import java.io.IOException;
import java.nio.channels.ClosedChannelException;
import java.util.List;

import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig;
import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTInterval;
import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode;
import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HistoryTree;
import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue;
import org.eclipse.tracecompass.statesystem.core.tests.stubs.backend.HistoryTreeStub;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;

/**
 * Tests the history tree
 *
 * @author Geneviève Bastien
 */
public class HistoryTreeTest {

    /* Minimal allowed blocksize */
    private static final int BLOCK_SIZE = HistoryTree.TREE_HEADER_SIZE;
    /* The extra size used by long and double values */
    private static final int LONG_DOUBLE_SIZE = 8;
    /* The number of extra characters to store a string interval */
    private static final int STRING_PADDING = 2;

    /* String with 23 characters, interval in file will be 25 bytes long */
    private static final String TEST_STRING = "abcdefghifklmnopqrstuvw";
    private static final TmfStateValue STRING_VALUE = TmfStateValue.newValueString(TEST_STRING);
    private static final TmfStateValue LONG_VALUE = TmfStateValue.newValueLong(10L);
    private static final TmfStateValue INT_VALUE = TmfStateValue.newValueInt(1);

    private @Nullable File fTempFile;

    /**
     * Create the temporary file for this history tree
     */
    @Before
    public void setupTest() {
        try {
            fTempFile = File.createTempFile("tmpStateSystem", null);
        } catch (IOException e) {
            fail(e.getMessage());
        }
    }

    /**
     * Delete the temporary history tree file after the test
     */
    @After
    public void cleanup() {
        if (fTempFile != null) {
            fTempFile.delete();
        }
    }

    /**
     * Setup a history tree.
     *
     * @param maxChildren
     *            The max number of children per node in the tree (tree config
     *            option)
     */
    private HistoryTreeStub setupSmallTree(int maxChildren) {
        HistoryTreeStub ht = null;
        try {
            File newFile = fTempFile;
            assertNotNull(newFile);
            HTConfig config = new HTConfig(newFile,
                    BLOCK_SIZE,
                    maxChildren, /* Number of children */
                    1, /* Provider version */
                    1); /* Start time */
            ht = new HistoryTreeStub(config);

        } catch (IOException e) {
            fail(e.getMessage());
        }

        assertNotNull(ht);
        return ht;
    }

    /**
     * Setup a history tree with config MAX_CHILDREN = 3.
     */
    private HistoryTreeStub setupSmallTree() {
        return setupSmallTree(3);
    }

    private static long fillValues(HistoryTree ht, TmfStateValue value, int nbValues, long start) {
        for (int i = 0; i < nbValues; i++) {
            ht.insertInterval(new HTInterval(start + i, start + i + 1, 1, value));
        }
        return start + nbValues;
    }

    /**
     * Insert intervals in the tree to fill the current leaf node to capacity,
     * without exceeding it.
     *
     * This guarantees that the following insertion will create new nodes.
     *
     * @param ht
     *            The history tree in which to insert
     * @return Start time of the current leaf node. Future insertions should be
     *         greater than or equal to this to make sure the intervals go in
     *         the leaf node.
     */
    private static long fillNextLeafNode(HistoryTreeStub ht, long leafNodeStart) {
        int prevCount = ht.getNodeCount();
        int prevDepth = ht.getDepth();

        /* Fill the following leaf node */
        HTNode node = ht.getLatestLeaf();
        int nodeFreeSpace = node.getNodeFreeSpace();
        int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
        long ret = fillValues(ht, STRING_VALUE, nbIntervals, leafNodeStart);

        /* Make sure we haven't changed the depth or node count */
        assertEquals(prevCount, ht.getNodeCount());
        assertEquals(prevDepth, ht.getDepth());

        return ret;
    }

    /**
     * Test that nodes are filled
     *
     * It fills nodes with sequential intervals from one attribute only, so that
     * leafs should be filled.
     */
    @Test
    public void testSequentialFill() {
        HistoryTreeStub ht = setupSmallTree();

        HTNode node = ht.getLatestLeaf();
        assertEquals(0, node.getNodeUsagePercent());

        /* Add null intervals up to ~10% */
        int nodeFreeSpace = node.getNodeFreeSpace();
        int nbIntervals = nodeFreeSpace / 10 / HTInterval.DATA_ENTRY_SIZE;
        long start = fillValues(ht, TmfStateValue.nullValue(), nbIntervals, 1);
        assertEquals(nodeFreeSpace - nbIntervals * HTInterval.DATA_ENTRY_SIZE, node.getNodeFreeSpace());

        /* Add integer intervals up to ~20% */
        nodeFreeSpace = node.getNodeFreeSpace();
        nbIntervals = nodeFreeSpace / 10 / HTInterval.DATA_ENTRY_SIZE;
        start = fillValues(ht, INT_VALUE, nbIntervals, start);
        assertEquals(nodeFreeSpace - nbIntervals * HTInterval.DATA_ENTRY_SIZE, node.getNodeFreeSpace());

        /* Add long intervals up to ~30% */
        nodeFreeSpace = node.getNodeFreeSpace();
        nbIntervals = nodeFreeSpace / 10 / (HTInterval.DATA_ENTRY_SIZE + LONG_DOUBLE_SIZE);
        start = fillValues(ht, LONG_VALUE, nbIntervals, start);
        assertEquals(nodeFreeSpace - nbIntervals * (HTInterval.DATA_ENTRY_SIZE + LONG_DOUBLE_SIZE), node.getNodeFreeSpace());

        /* Add string intervals up to ~40% */
        nodeFreeSpace = node.getNodeFreeSpace();
        nbIntervals = nodeFreeSpace / 10 / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
        start = fillValues(ht, STRING_VALUE, nbIntervals, start);
        assertEquals(nodeFreeSpace - nbIntervals * (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING), node.getNodeFreeSpace());

    }

    /**
     * Test the addition of new nodes to the tree and make sure the tree is
     * built with the right structure
     */
    @Test
    public void testDepth() {
        HistoryTreeStub ht = setupSmallTree();

        /* Fill a first node */
        HTNode node = ht.getLatestLeaf();
        int nodeFreeSpace = node.getNodeFreeSpace();
        int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
        long start = fillValues(ht, STRING_VALUE, nbIntervals, 1);

        /* Add intervals that should add a sibling to the node */
        assertEquals(1, ht.getNodeCount());
        assertEquals(1, ht.getDepth());
        start = fillValues(ht, STRING_VALUE, 1, start);
        assertEquals(3, ht.getNodeCount());
        assertEquals(2, ht.getDepth());

        /* Fill the latest leaf node (2nd child) */
        node = ht.getLatestLeaf();
        nodeFreeSpace = node.getNodeFreeSpace();
        nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
        start = fillValues(ht, STRING_VALUE, nbIntervals, start);

        /*
         * Add an interval that should add another sibling to the previous nodes
         */
        start = fillValues(ht, STRING_VALUE, 1, start);
        assertEquals(4, ht.getNodeCount());
        assertEquals(2, ht.getDepth());

        /* Fill the latest leaf node (3rd and last child) */
        node = ht.getLatestLeaf();
        nodeFreeSpace = node.getNodeFreeSpace();
        nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
        start = fillValues(ht, STRING_VALUE, nbIntervals, start);

        /* The new node created here should generate a new branch */
        start = fillValues(ht, STRING_VALUE, 1, start);
        assertEquals(7, ht.getNodeCount());
        assertEquals(3, ht.getDepth());
    }

    /**
     * Make sure the node sequence numbers and parent pointers are set correctly
     * when new nodes are created.
     *
     * <p>
     * We are building a tree whose node sequence numbers will look like this at
     * the end:
     * </p>
     *
     * <pre>
     *     3
     *    / \
     *   1   4
     *  / \   \
     * 0   2   5
     * </pre>
     *
     * <p>
     * However while building, the parent pointers may be different.
     * </p>
     *
     * @throws ClosedChannelException
     *             If the test fails
     */
    @Test
    public void testNodeSequenceNumbers() throws ClosedChannelException {
        /* Represents the start time of the current leaf node */
        long start = 1;

        HistoryTreeStub ht = setupSmallTree(2);
        start = fillNextLeafNode(ht, start);

        List<HTNode> branch = ht.getLatestBranch();
        assertEquals(1, branch.size());
        assertEquals( 0, branch.get(0).getSequenceNumber());
        assertEquals(-1, branch.get(0).getParentSequenceNumber());

        /* Create a new branch */
        start = fillValues(ht, STRING_VALUE, 1, start);
        start = fillNextLeafNode(ht, start);
        assertEquals(3, ht.getNodeCount());
        assertEquals(2, ht.getDepth());

        /* Make sure the first node's parent was updated */
        HTNode node = ht.readNode(0);
        assertEquals(0, node.getSequenceNumber());
        assertEquals(1, node.getParentSequenceNumber());

        /* Make sure the new branch is alright */
        branch = ht.getLatestBranch();
        assertEquals(2, branch.size());
        assertEquals( 1, branch.get(0).getSequenceNumber());
        assertEquals(-1, branch.get(0).getParentSequenceNumber());
        assertEquals( 2, branch.get(1).getSequenceNumber());
        assertEquals( 1, branch.get(1).getParentSequenceNumber());

        /* Create a third branch */
        start = fillValues(ht, STRING_VALUE, 1, start);
        start = fillNextLeafNode(ht, start);
        assertEquals(6, ht.getNodeCount());
        assertEquals(3, ht.getDepth());

        /* Make sure all previous nodes are still correct */
        node = ht.readNode(0);
        assertEquals(0, node.getSequenceNumber());
        assertEquals(1, node.getParentSequenceNumber());
        node = ht.readNode(1);
        assertEquals(1, node.getSequenceNumber());
        assertEquals(3, node.getParentSequenceNumber());
        node = ht.readNode(2);
        assertEquals(2, node.getSequenceNumber());
        assertEquals(1, node.getParentSequenceNumber());

        /* Verify the contents of the new latest branch */
        branch = ht.getLatestBranch();
        assertEquals(3, branch.size());
        assertEquals( 3, branch.get(0).getSequenceNumber());
        assertEquals(-1, branch.get(0).getParentSequenceNumber());
        assertEquals( 4, branch.get(1).getSequenceNumber());
        assertEquals( 3, branch.get(1).getParentSequenceNumber());
        assertEquals( 5, branch.get(2).getSequenceNumber());
        assertEquals( 4, branch.get(2).getParentSequenceNumber());
    }
}
Commit	Line	Data
f3476b68 GB	1	/*******************************************************************************
	2	* Copyright (c) 2015 École Polytechnique de Montréal
	3	*
	4	* All rights reserved. This program and the accompanying materials are
	5	* made available under the terms of the Eclipse Public License v1.0 which
	6	* accompanies this distribution, and is available at
	7	* http://www.eclipse.org/legal/epl-v10.html
	8	*******************************************************************************/
	9
51004941	10	package org.eclipse.tracecompass.statesystem.core.tests.backend.historytree;
f3476b68 GB	11
	12	import static org.junit.Assert.assertEquals;
	13	import static org.junit.Assert.assertNotNull;
	14	import static org.junit.Assert.fail;
	15
	16	import java.io.File;
	17	import java.io.IOException;
b2ca67ca PT	18	import java.nio.channels.ClosedChannelException;
b2ca67ca PT	19	import java.util.List;
f3476b68	20
51004941	21	import org.eclipse.jdt.annotation.Nullable;
f3476b68 GB	22	import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig;
	23	import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTInterval;
	24	import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode;
	25	import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HistoryTree;
	26	import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue;
5eb1b4b0	27	import org.eclipse.tracecompass.statesystem.core.tests.stubs.backend.HistoryTreeStub;
f3476b68 GB	28	import org.junit.After;
	29	import org.junit.Before;
	30	import org.junit.Test;
	31
	32	/**
	33	* Tests the history tree
	34	*
	35	* @author Geneviève Bastien
	36	*/
	37	public class HistoryTreeTest {
	38
	39	/* Minimal allowed blocksize */
	40	private static final int BLOCK_SIZE = HistoryTree.TREE_HEADER_SIZE;
	41	/* The extra size used by long and double values */
	42	private static final int LONG_DOUBLE_SIZE = 8;
	43	/* The number of extra characters to store a string interval */
	44	private static final int STRING_PADDING = 2;
	45
	46	/* String with 23 characters, interval in file will be 25 bytes long */
	47	private static final String TEST_STRING = "abcdefghifklmnopqrstuvw";
51004941 GB	48	private static final TmfStateValue STRING_VALUE = TmfStateValue.newValueString(TEST_STRING);
	49	private static final TmfStateValue LONG_VALUE = TmfStateValue.newValueLong(10L);
	50	private static final TmfStateValue INT_VALUE = TmfStateValue.newValueInt(1);
f3476b68	51
51004941	52	private @Nullable File fTempFile;
f3476b68 GB	53
	54	/**
	55	* Create the temporary file for this history tree
	56	*/
	57	@Before
	58	public void setupTest() {
	59	try {
	60	fTempFile = File.createTempFile("tmpStateSystem", null);
	61	} catch (IOException e) {
	62	fail(e.getMessage());
	63	}
	64	}
	65
	66	/**
	67	* Delete the temporary history tree file after the test
	68	*/
	69	@After
	70	public void cleanup() {
51004941 GB	71	if (fTempFile != null) {
	72	fTempFile.delete();
	73	}
f3476b68 GB	74	}
f3476b68 GB	75
b2ca67ca PT	76	/**
	77	* Setup a history tree.
	78	*
	79	* @param maxChildren
	80	* The max number of children per node in the tree (tree config
	81	* option)
	82	*/
	83	private HistoryTreeStub setupSmallTree(int maxChildren) {
f3476b68 GB	84	HistoryTreeStub ht = null;
	85	try {
	86	File newFile = fTempFile;
	87	assertNotNull(newFile);
	88	HTConfig config = new HTConfig(newFile,
	89	BLOCK_SIZE,
b2ca67ca	90	maxChildren, /* Number of children */
f3476b68 GB	91	1, /* Provider version */
	92	1); /* Start time */
	93	ht = new HistoryTreeStub(config);
	94
	95	} catch (IOException e) {
	96	fail(e.getMessage());
	97	}
	98
	99	assertNotNull(ht);
	100	return ht;
	101	}
	102
b2ca67ca PT	103	/**
	104	* Setup a history tree with config MAX_CHILDREN = 3.
	105	*/
	106	private HistoryTreeStub setupSmallTree() {
	107	return setupSmallTree(3);
	108	}
	109
51004941	110	private static long fillValues(HistoryTree ht, TmfStateValue value, int nbValues, long start) {
f3476b68 GB	111	for (int i = 0; i < nbValues; i++) {
	112	ht.insertInterval(new HTInterval(start + i, start + i + 1, 1, value));
	113	}
	114	return start + nbValues;
	115	}
	116
b2ca67ca PT	117	/**
	118	* Insert intervals in the tree to fill the current leaf node to capacity,
	119	* without exceeding it.
	120	*
	121	* This guarantees that the following insertion will create new nodes.
	122	*
	123	* @param ht
	124	* The history tree in which to insert
	125	* @return Start time of the current leaf node. Future insertions should be
	126	* greater than or equal to this to make sure the intervals go in
	127	* the leaf node.
	128	*/
	129	private static long fillNextLeafNode(HistoryTreeStub ht, long leafNodeStart) {
	130	int prevCount = ht.getNodeCount();
	131	int prevDepth = ht.getDepth();
	132
	133	/* Fill the following leaf node */
	134	HTNode node = ht.getLatestLeaf();
	135	int nodeFreeSpace = node.getNodeFreeSpace();
	136	int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
	137	long ret = fillValues(ht, STRING_VALUE, nbIntervals, leafNodeStart);
	138
	139	/* Make sure we haven't changed the depth or node count */
	140	assertEquals(prevCount, ht.getNodeCount());
	141	assertEquals(prevDepth, ht.getDepth());
	142
	143	return ret;
	144	}
	145
f3476b68 GB	146	/**
	147	* Test that nodes are filled
	148	*
	149	* It fills nodes with sequential intervals from one attribute only, so that
	150	* leafs should be filled.
	151	*/
	152	@Test
	153	public void testSequentialFill() {
	154	HistoryTreeStub ht = setupSmallTree();
	155
	156	HTNode node = ht.getLatestLeaf();
	157	assertEquals(0, node.getNodeUsagePercent());
	158
	159	/* Add null intervals up to ~10% */
	160	int nodeFreeSpace = node.getNodeFreeSpace();
	161	int nbIntervals = nodeFreeSpace / 10 / HTInterval.DATA_ENTRY_SIZE;
	162	long start = fillValues(ht, TmfStateValue.nullValue(), nbIntervals, 1);
	163	assertEquals(nodeFreeSpace - nbIntervals * HTInterval.DATA_ENTRY_SIZE, node.getNodeFreeSpace());
	164
	165	/* Add integer intervals up to ~20% */
	166	nodeFreeSpace = node.getNodeFreeSpace();
	167	nbIntervals = nodeFreeSpace / 10 / HTInterval.DATA_ENTRY_SIZE;
	168	start = fillValues(ht, INT_VALUE, nbIntervals, start);
	169	assertEquals(nodeFreeSpace - nbIntervals * HTInterval.DATA_ENTRY_SIZE, node.getNodeFreeSpace());
	170
	171	/* Add long intervals up to ~30% */
	172	nodeFreeSpace = node.getNodeFreeSpace();
	173	nbIntervals = nodeFreeSpace / 10 / (HTInterval.DATA_ENTRY_SIZE + LONG_DOUBLE_SIZE);
	174	start = fillValues(ht, LONG_VALUE, nbIntervals, start);
	175	assertEquals(nodeFreeSpace - nbIntervals * (HTInterval.DATA_ENTRY_SIZE + LONG_DOUBLE_SIZE), node.getNodeFreeSpace());
	176
	177	/* Add string intervals up to ~40% */
	178	nodeFreeSpace = node.getNodeFreeSpace();
	179	nbIntervals = nodeFreeSpace / 10 / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
	180	start = fillValues(ht, STRING_VALUE, nbIntervals, start);
	181	assertEquals(nodeFreeSpace - nbIntervals * (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING), node.getNodeFreeSpace());
	182
	183	}
	184
7c247a0f GB	185	/**
	186	* Test the addition of new nodes to the tree and make sure the tree is
	187	* built with the right structure
	188	*/
	189	@Test
	190	public void testDepth() {
	191	HistoryTreeStub ht = setupSmallTree();
	192
	193	/* Fill a first node */
	194	HTNode node = ht.getLatestLeaf();
	195	int nodeFreeSpace = node.getNodeFreeSpace();
	196	int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
	197	long start = fillValues(ht, STRING_VALUE, nbIntervals, 1);
	198
	199	/* Add intervals that should add a sibling to the node */
	200	assertEquals(1, ht.getNodeCount());
	201	assertEquals(1, ht.getDepth());
	202	start = fillValues(ht, STRING_VALUE, 1, start);
	203	assertEquals(3, ht.getNodeCount());
	204	assertEquals(2, ht.getDepth());
	205
	206	/* Fill the latest leaf node (2nd child) */
	207	node = ht.getLatestLeaf();
	208	nodeFreeSpace = node.getNodeFreeSpace();
	209	nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
	210	start = fillValues(ht, STRING_VALUE, nbIntervals, start);
	211
	212	/*
	213	* Add an interval that should add another sibling to the previous nodes
	214	*/
	215	start = fillValues(ht, STRING_VALUE, 1, start);
	216	assertEquals(4, ht.getNodeCount());
	217	assertEquals(2, ht.getDepth());
	218
	219	/* Fill the latest leaf node (3rd and last child) */
	220	node = ht.getLatestLeaf();
	221	nodeFreeSpace = node.getNodeFreeSpace();
	222	nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING);
	223	start = fillValues(ht, STRING_VALUE, nbIntervals, start);
	224
	225	/* The new node created here should generate a new branch */
	226	start = fillValues(ht, STRING_VALUE, 1, start);
	227	assertEquals(7, ht.getNodeCount());
	228	assertEquals(3, ht.getDepth());
	229	}
b2ca67ca PT	230
	231	/**
	232	* Make sure the node sequence numbers and parent pointers are set correctly
	233	* when new nodes are created.
	234	*
	235	* <p>
	236	* We are building a tree whose node sequence numbers will look like this at
	237	* the end:
	238	* </p>
	239	*
	240	* <pre>
	241	* 3
	242	* / \
	243	* 1 4
	244	* / \ \
	245	* 0 2 5
	246	* </pre>
	247	*
	248	* <p>
	249	* However while building, the parent pointers may be different.
	250	* </p>
	251	*
	252	* @throws ClosedChannelException
	253	* If the test fails
	254	*/
	255	@Test
	256	public void testNodeSequenceNumbers() throws ClosedChannelException {
	257	/* Represents the start time of the current leaf node */
	258	long start = 1;
	259
	260	HistoryTreeStub ht = setupSmallTree(2);
	261	start = fillNextLeafNode(ht, start);
	262
	263	List<HTNode> branch = ht.getLatestBranch();
	264	assertEquals(1, branch.size());
	265	assertEquals( 0, branch.get(0).getSequenceNumber());
	266	assertEquals(-1, branch.get(0).getParentSequenceNumber());
	267
	268	/* Create a new branch */
	269	start = fillValues(ht, STRING_VALUE, 1, start);
	270	start = fillNextLeafNode(ht, start);
	271	assertEquals(3, ht.getNodeCount());
	272	assertEquals(2, ht.getDepth());
	273
	274	/* Make sure the first node's parent was updated */
	275	HTNode node = ht.readNode(0);
	276	assertEquals(0, node.getSequenceNumber());
	277	assertEquals(1, node.getParentSequenceNumber());
	278
	279	/* Make sure the new branch is alright */
	280	branch = ht.getLatestBranch();
	281	assertEquals(2, branch.size());
	282	assertEquals( 1, branch.get(0).getSequenceNumber());
	283	assertEquals(-1, branch.get(0).getParentSequenceNumber());
	284	assertEquals( 2, branch.get(1).getSequenceNumber());
	285	assertEquals( 1, branch.get(1).getParentSequenceNumber());
	286
	287	/* Create a third branch */
	288	start = fillValues(ht, STRING_VALUE, 1, start);
	289	start = fillNextLeafNode(ht, start);
	290	assertEquals(6, ht.getNodeCount());
	291	assertEquals(3, ht.getDepth());
	292
	293	/* Make sure all previous nodes are still correct */
294	node = ht.readNode(0);
295	assertEquals(0, node.getSequenceNumber());
296	assertEquals(1, node.getParentSequenceNumber());
297	node = ht.readNode(1);
298	assertEquals(1, node.getSequenceNumber());
299	assertEquals(3, node.getParentSequenceNumber());
300	node = ht.readNode(2);
301	assertEquals(2, node.getSequenceNumber());
302	assertEquals(1, node.getParentSequenceNumber());
303
304	/* Verify the contents of the new latest branch */
305	branch = ht.getLatestBranch();
306	assertEquals(3, branch.size());
307	assertEquals( 3, branch.get(0).getSequenceNumber());
308	assertEquals(-1, branch.get(0).getParentSequenceNumber());
309	assertEquals( 4, branch.get(1).getSequenceNumber());
310	assertEquals( 3, branch.get(1).getParentSequenceNumber());
311	assertEquals( 5, branch.get(2).getSequenceNumber());
312	assertEquals( 4, branch.get(2).getParentSequenceNumber());
313	}
f3476b68	314	}