cassandra-trunk/src/java/org/apache/cassandra/io/tries/TrieNode.java
/*
 * 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.DataOutput;
import java.io.IOException;
import java.nio.ByteBuffer;

import org.apache.cassandra.io.util.DataOutputPlus;
import org.apache.cassandra.io.util.SizedInts;

/**
 * Trie node types and manipulation mechanisms. The main purpose of this is to allow for handling tries directly as
 * they are on disk without any serialization, and to enable the creation of such files.
 * <p>
 * The serialization methods take as argument a generic {@code SerializationNode} and provide a method {@code typeFor}
 * for choosing a suitable type to represent it, which can then be used to calculate size and write the node.
 * <p>
 * To read a file containing trie nodes, one would use {@code at} to identify the node type and then the various
 * read methods to retrieve the data. They all take a buffer (usually memory-mapped) containing the data, and a position
 * in it that identifies the node.
 * <p>
 * These node types do not specify any treatment of payloads. They are only concerned with providing 4 bits of
 * space for {@code payloadFlags}, and a way of calculating the position after the node. Users of this class by convention
 * use non-zero payloadFlags to indicate a payload exists, write it (possibly in flag-dependent format) at serialization
 * time after the node itself is written, and read it using the {@code payloadPosition} value.
 * <p>
 * To improve efficiency, multiple node types depending on the number of transitions are provided:
 * -- payload only, which has no outgoing transitions
 * -- single outgoing transition
 * -- sparse, which provides a list of transition bytes with corresponding targets
 * -- dense, where the transitions span a range of values and having the list (and the search in it) can be avoided
 * <p>
 * For each of the transition-carrying types we also have "in-page" versions where transition targets are the 4, 8 or 12
 * lowest bits of the position within the same page. To save one further byte, the single in-page versions using 4 or 12
 * bits cannot carry a payload.
 * <p>
 * This class is effectively an enumeration; abstract class permits instances to extend each other and reuse code.
 * <p>
 * See {@code org/apache/cassandra/io/sstable/format/bti/BtiFormat.md} for a description of the mechanisms of writing
 * and reading an on-disk trie.
 */
@SuppressWarnings({ "SameParameterValue" })
public abstract class TrieNode
{
    /** Value used to indicate a branch (e.g. for transition and lastTransition) does not exist. */
    public static int NONE = -1;

    // Consumption (read) methods

    /**
     * Returns the type of node stored at this position. It can then be used to call the methods below.
     */
    public static TrieNode at(ByteBuffer src, int position)
    {
        return Types.values[(src.get(position) >> 4) & 0xF];
    }

    /**
     * Returns the 4 payload flag bits. Node types that cannot carry a payload return 0.
     */
    public int payloadFlags(ByteBuffer src, int position)
    {
        return src.get(position) & 0x0F;
    }

    /**
     * Return the position just after the node, where the payload is usually stored.
     */
    abstract public int payloadPosition(ByteBuffer src, int position);

    /**
     * Returns search index for the given byte in the node. If exact match is present, this is >= 0, otherwise as in
     * binary search.
     */
    abstract public int search(ByteBuffer src, int position, int transitionByte);       // returns as binarySearch

    /**
     * Returns the upper childIndex limit. Calling transition with values 0...transitionRange - 1 is valid.
     */
    abstract public int transitionRange(ByteBuffer src, int position);

    /**
     * Returns the byte value for this child index, or Integer.MAX_VALUE if there are no transitions with this index or
     * higher to permit listing the children without needing to call transitionRange.
     *
     * @param childIndex must be >= 0, though it is allowed to pass a value greater than {@code transitionRange - 1}
     */
    abstract public int transitionByte(ByteBuffer src, int position, int childIndex);

    /**
     * Returns the delta between the position of this node and the position of the target of the specified transition.
     * This is always a negative number. Dense nodes use 0 to specify "no transition".
     *
     * @param childIndex must be >= 0 and < {@link #transitionRange(ByteBuffer, int)} - note that this is not validated
     *                   and behaviour of this method is undefined for values outside of that range
     */
    abstract long transitionDelta(ByteBuffer src, int position, int childIndex);

    /**
     * Returns position of node to transition to for the given search index. Argument must be positive. May return NONE
     * if a transition with that index does not exist (DENSE nodes).
     * Position is the offset of the node within the ByteBuffer. positionLong is its global placement, which is the
     * base for any offset calculations.
     *
     * @param positionLong although it seems to be obvious, this argument must be "real", that is, each child must have
     *                     the calculated absolute position >= 0, otherwise the behaviour of this method is undefined
     * @param childIndex   must be >= 0 and < {@link #transitionRange(ByteBuffer, int)} - note that this is not validated
     *                     and behaviour of this method is undefined for values outside of that range
     */
    public long transition(ByteBuffer src, int position, long positionLong, int childIndex)
    {
        // note: this is not valid for dense nodes
        return positionLong + transitionDelta(src, position, childIndex);
    }

    /**
     * Returns the highest transition for this node, or NONE if none exist (PAYLOAD_ONLY nodes).
     */
    public long lastTransition(ByteBuffer src, int position, long positionLong)
    {
        return transition(src, position, positionLong, transitionRange(src, position) - 1);
    }

    /**
     * Returns a transition that is higher than the index returned by {@code search}. This may not exist (if the
     * argument was higher than the last transition byte), in which case this returns the given {@code defaultValue}.
     */
    abstract public long greaterTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue);

    /**
     * Returns a transition that is lower than the index returned by {@code search}. Returns {@code defaultValue} for
     * {@code searchIndex} equals 0 or -1 as lesser transition for those indexes does not exist.
     */
    abstract public long lesserTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue);

    // Construction (serialization) methods

    /**
     * Returns a node type that is suitable to store the node.
     */
    public static TrieNode typeFor(SerializationNode<?> node, long nodePosition)
    {
        int c = node.childCount();
        if (c == 0)
            return Types.PAYLOAD_ONLY;

        int bitsPerPointerIndex = 0;
        long delta = node.maxPositionDelta(nodePosition);
        assert delta < 0;
        while (!Types.singles[bitsPerPointerIndex].fits(-delta))
            ++bitsPerPointerIndex;

        if (c == 1)
        {
            if (node.payload() != null && Types.singles[bitsPerPointerIndex].bytesPerPointer == FRACTIONAL_BYTES)
                ++bitsPerPointerIndex; // next index will permit payload

            return Types.singles[bitsPerPointerIndex];
        }

        TrieNode sparse = Types.sparses[bitsPerPointerIndex];
        TrieNode dense = Types.denses[bitsPerPointerIndex];
        return (sparse.sizeofNode(node) < dense.sizeofNode(node)) ? sparse : dense;
    }

    /**
     * Returns the size needed to serialize this node.
     */
    abstract public int sizeofNode(SerializationNode<?> node);

    /**
     * Serializes the node. All transition target positions must already have been defined. {@code payloadBits} must
     * be four bits.
     */
    abstract public void serialize(DataOutputPlus out, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException;

    // Implementations

    final int bytesPerPointer;
    static final int FRACTIONAL_BYTES = 0;

    TrieNode(int ordinal, int bytesPerPointer)
    {
        this.ordinal = ordinal;
        this.bytesPerPointer = bytesPerPointer;
    }

    final int ordinal;

    static private class PayloadOnly extends TrieNode
    {
        // byte flags
        // var payload
        PayloadOnly(int ordinal)
        {
            super(ordinal, FRACTIONAL_BYTES);
        }

        @Override
        public int payloadPosition(ByteBuffer src, int position)
        {
            return position + 1;
        }

        @Override
        public int search(ByteBuffer src, int position, int transitionByte)
        {
            return -1;
        }

        @Override
        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            return 0;
        }

        @Override
        public long transition(ByteBuffer src, int position, long positionLong, int childIndex)
        {
            return NONE;
        }

        @Override
        public long lastTransition(ByteBuffer src, int position, long positionLong)
        {
            return NONE;
        }

        @Override
        public long greaterTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
        {
            return defaultValue;
        }

        @Override
        public long lesserTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
        {
            return defaultValue;
        }

        @Override
        public int transitionByte(ByteBuffer src, int position, int childIndex)
        {
            return Integer.MAX_VALUE;
        }

        @Override
        public int transitionRange(ByteBuffer src, int position)
        {
            return 0;
        }

        public int sizeofNode(SerializationNode<?> node)
        {
            return 1;
        }

        @Override
        public void serialize(DataOutputPlus dest, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
        {
            dest.writeByte((ordinal << 4) + (payloadBits & 0x0F));
        }
    }

    static private class Single extends TrieNode
    {
        // byte flags
        // byte transition
        // bytesPerPointer bytes transition target
        // var payload

        Single(int ordinal, int bytesPerPointer)
        {
            super(ordinal, bytesPerPointer);
        }

        @Override
        public int payloadPosition(ByteBuffer src, int position)
        {
            return position + 2 + bytesPerPointer;
        }

        @Override
        public int search(ByteBuffer src, int position, int transitionByte)
        {
            int c = src.get(position + 1) & 0xFF;
            if (transitionByte == c)
                return 0;
            return transitionByte < c ? -1 : -2;
        }

        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            return -readBytes(src, position + 2);
        }

        @Override
        public long lastTransition(ByteBuffer src, int position, long positionLong)
        {
            return transition(src, position, positionLong, 0);
        }

        @Override
        public long greaterTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
        {
            return (searchIndex == -1) ? transition(src, position, positionLong, 0) : defaultValue;
        }

        @Override
        public long lesserTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
        {
            return searchIndex == 0 || searchIndex == -1 ? defaultValue : transition(src, position, positionLong, 0);
        }

        @Override
        public int transitionByte(ByteBuffer src, int position, int childIndex)
        {
            return childIndex == 0 ? src.get(position + 1) & 0xFF : Integer.MAX_VALUE;
        }

        @Override
        public int transitionRange(ByteBuffer src, int position)
        {
            return 1;
        }

        public int sizeofNode(SerializationNode<?> node)
        {
            return 2 + bytesPerPointer;
        }

        @Override
        public void serialize(DataOutputPlus dest, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
        {
            int childCount = node.childCount();
            assert childCount == 1;
            dest.writeByte((ordinal << 4) + (payloadBits & 0x0F));

            dest.writeByte(node.transition(0));
            writeBytes(dest, -node.serializedPositionDelta(0, nodePosition));
        }
    }

    static private class SingleNoPayload4 extends Single
    {
        // 4-bit type ordinal
        // 4-bit target delta
        // byte transition
        // no payload!
        SingleNoPayload4(int ordinal)
        {
            super(ordinal, FRACTIONAL_BYTES);
        }

        @Override
        public int payloadFlags(ByteBuffer src, int position)
        {
            return 0;
        }

        // Although we don't have a payload position, provide one for calculating the size of the node.
        @Override
        public int payloadPosition(ByteBuffer src, int position)
        {
            return position + 2;
        }

        @Override
        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            return -(src.get(position) & 0xF);
        }

        @Override
        boolean fits(long delta)
        {
            return 0 <= delta && delta <= 0xF;
        }

        @Override
        public void serialize(DataOutputPlus dest, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
        {
            assert payloadBits == 0;
            int childCount = node.childCount();
            assert childCount == 1;
            long pd = -node.serializedPositionDelta(0, nodePosition);
            assert pd > 0 && pd < 0x10;
            dest.writeByte((ordinal << 4) + (int) (pd & 0x0F));
            dest.writeByte(node.transition(0));
        }

        @Override
        public int sizeofNode(SerializationNode<?> node)
        {
            return 2;
        }
    }

    static private class SingleNoPayload12 extends Single
    {
        // 4-bit type ordinal
        // 12-bit target delta
        // byte transition
        // no payload!
        SingleNoPayload12(int ordinal)
        {
            super(ordinal, FRACTIONAL_BYTES);
        }

        @Override
        public int payloadFlags(ByteBuffer src, int position)
        {
            return 0;
        }

        // Although we don't have a payload position, provide one for calculating the size of the node.
        @Override
        public int payloadPosition(ByteBuffer src, int position)
        {
            return position + 3;
        }

        @Override
        public int search(ByteBuffer src, int position, int transitionByte)
        {
            int c = src.get(position + 2) & 0xFF;
            if (transitionByte == c)
                return 0;
            return transitionByte < c ? -1 : -2;
        }

        @Override
        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            return -(src.getShort(position) & 0xFFF);
        }

        @Override
        public int transitionByte(ByteBuffer src, int position, int childIndex)
        {
            return childIndex == 0 ? src.get(position + 2) & 0xFF : Integer.MAX_VALUE;
        }

        @Override
        boolean fits(long delta)
        {
            return 0 <= delta && delta <= 0xFFF;
        }

        @Override
        public void serialize(DataOutputPlus dest, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
        {
            assert payloadBits == 0;
            int childCount = node.childCount();
            assert childCount == 1;
            long pd = -node.serializedPositionDelta(0, nodePosition);
            assert pd > 0 && pd < 0x1000;
            dest.writeByte((ordinal << 4) + (int) ((pd >> 8) & 0x0F));
            dest.writeByte((byte) pd);
            dest.writeByte(node.transition(0));
        }

        @Override
        public int sizeofNode(SerializationNode<?> node)
        {
            return 3;
        }
    }

    static private class Sparse extends TrieNode
    {
        // byte flags
        // byte count (<= 255)
        // count bytes transitions
        // count ints transition targets
        // var payload

        Sparse(int ordinal, int bytesPerPointer)
        {
            super(ordinal, bytesPerPointer);
        }

        @Override
        public int transitionRange(ByteBuffer src, int position)
        {
            return src.get(position + 1) & 0xFF;
        }

        @Override
        public int payloadPosition(ByteBuffer src, int position)
        {
            int count = transitionRange(src, position);
            return position + 2 + (bytesPerPointer + 1) * count;
        }

        @Override
        public int search(ByteBuffer src, int position, int key)
        {
            int l = -1; // known < key
            int r = transitionRange(src, position);   // known > key
            position += 2;

            while (l + 1 < r)
            {
                int m = (l + r + 1) / 2;
                int childTransition = src.get(position + m) & 0xFF;
                int cmp = Integer.compare(key, childTransition);
                if (cmp < 0)
                    r = m;
                else if (cmp > 0)
                    l = m;
                else
                    return m;
            }

            return -r - 1;
        }

        @Override
        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            assert childIndex >= 0;
            int range = transitionRange(src, position);
            assert childIndex < range;
            return -readBytes(src, position + 2 + range + bytesPerPointer * childIndex);
        }

        @Override
        public long greaterTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
        {
            if (searchIndex < 0)
                searchIndex = -1 - searchIndex;
            else
                ++searchIndex;
            if (searchIndex >= transitionRange(src, position))
                return defaultValue;
            return transition(src, position, positionLong, searchIndex);
        }

        public long lesserTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
        {
            if (searchIndex == 0 || searchIndex == -1)
                return defaultValue;
            if (searchIndex < 0)
                searchIndex = -2 - searchIndex;
            else
                --searchIndex;
            return transition(src, position, positionLong, searchIndex);
        }

        @Override
        public int transitionByte(ByteBuffer src, int position, int childIndex)
        {
            return childIndex < transitionRange(src, position) ? src.get(position + 2 + childIndex) & 0xFF : Integer.MAX_VALUE;
        }

        @Override
        public int sizeofNode(SerializationNode<?> node)
        {
            return 2 + node.childCount() * (1 + bytesPerPointer);
        }

        @Override
        public void serialize(DataOutputPlus dest, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
        {
            int childCount = node.childCount();
            assert childCount > 0;
            assert childCount < 256;
            dest.writeByte((ordinal << 4) + (payloadBits & 0x0F));
            dest.writeByte(childCount);

            for (int i = 0; i < childCount; ++i)
                dest.writeByte(node.transition(i));
            for (int i = 0; i < childCount; ++i)
                writeBytes(dest, -node.serializedPositionDelta(i, nodePosition));
        }
    }

    static private class Sparse12 extends Sparse
    {
        // byte flags
        // byte count (<= 255)
        // count bytes transitions
        // count 12-bits transition targets
        // var payload
        Sparse12(int ordinal)
        {
            super(ordinal, FRACTIONAL_BYTES);
        }

        @Override
        public int payloadPosition(ByteBuffer src, int position)
        {
            int count = transitionRange(src, position);
            return position + 2 + (5 * count + 1) / 2;
        }

        @Override
        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            return -read12Bits(src, position + 2 + transitionRange(src, position), childIndex);
        }

        @Override
        public int sizeofNode(SerializationNode<?> node)
        {
            return 2 + (node.childCount() * 5 + 1) / 2;
        }

        @Override
        public void serialize(DataOutputPlus dest, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
        {
            int childCount = node.childCount();
            assert childCount < 256;
            dest.writeByte((ordinal << 4) + (payloadBits & 0x0F));
            dest.writeByte(childCount);

            for (int i = 0; i < childCount; ++i)
                dest.writeByte(node.transition(i));
            int i;
            for (i = 0; i + 2 <= childCount; i += 2)
            {
                int p0 = (int) -node.serializedPositionDelta(i, nodePosition);
                int p1 = (int) -node.serializedPositionDelta(i + 1, nodePosition);
                assert p0 > 0 && p0 < (1 << 12);
                assert p1 > 0 && p1 < (1 << 12);
                dest.writeByte(p0 >> 4);
                dest.writeByte((p0 << 4) | (p1 >> 8));
                dest.writeByte(p1);
            }
            if (i < childCount)
            {
                long pd = -node.serializedPositionDelta(i, nodePosition);
                assert pd > 0 && pd < (1 << 12);
                dest.writeShort((short) (pd << 4));
            }
        }

        @Override
        boolean fits(long delta)
        {
            return 0 <= delta && delta <= 0xFFF;
        }
    }

    static private class Dense extends TrieNode
    {
        // byte flags
        // byte start
        // byte length-1
        // length ints transition targets (-1 for not present)
        // var payload

        static final int NULL_VALUE = 0;

        Dense(int ordinal, int bytesPerPointer)
        {
            super(ordinal, bytesPerPointer);
        }

        @Override
        public int transitionRange(ByteBuffer src, int position)
        {
            return 1 + (src.get(position + 2) & 0xFF);
        }

        @Override
        public int payloadPosition(ByteBuffer src, int position)
        {
            return position + 3 + transitionRange(src, position) * bytesPerPointer;
        }

        @Override
        public int search(ByteBuffer src, int position, int transitionByte)
        {
            int l = src.get(position + 1) & 0xFF;
            int i = transitionByte - l;
            if (i < 0)
                return -1;
            int len = transitionRange(src, position);
            if (i >= len)
                return -len - 1;
            long t = transition(src, position, 0L, i);
            return t != -1 ? i : -i - 1;
        }

        @Override
        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            return -readBytes(src, position + 3 + childIndex * bytesPerPointer);
        }

        @Override
        public long transition(ByteBuffer src, int position, long positionLong, int childIndex)
        {
            long v = transitionDelta(src, position, childIndex);
            return v != NULL_VALUE ? v + positionLong : NONE;
        }

        @Override
        public long greaterTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
        {
            if (searchIndex < 0)
                searchIndex = -1 - searchIndex;
            else
                ++searchIndex;
            int len = transitionRange(src, position);
            for (; searchIndex < len; ++searchIndex)
            {
                long t = transition(src, position, positionLong, searchIndex);
                if (t != NONE)
                    return t;
            }
            return defaultValue;
        }

        @Override
        public long lesserTransition(ByteBuffer src, int position, long positionLong, int searchIndex, long defaultValue)
        {
            if (searchIndex == 0 || searchIndex == -1)
                return defaultValue;

            if (searchIndex < 0)
                searchIndex = -2 - searchIndex;
            else
                --searchIndex;
            for (; searchIndex >= 0; --searchIndex)
            {
                long t = transition(src, position, positionLong, searchIndex);
                if (t != -1)
                    return t;
            }
            assert false : "transition must always exist at 0, and we should not be called for less of that";
            return defaultValue;
        }

        @Override
        public int transitionByte(ByteBuffer src, int position, int childIndex)
        {
            if (childIndex >= transitionRange(src, position))
                return Integer.MAX_VALUE;
            int l = src.get(position + 1) & 0xFF;
            return l + childIndex;
        }

        @Override
        public int sizeofNode(SerializationNode<?> node)
        {
            int l = node.transition(0);
            int r = node.transition(node.childCount() - 1);
            return 3 + (r - l + 1) * bytesPerPointer;
        }

        @Override
        public void serialize(DataOutputPlus dest, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
        {
            int childCount = node.childCount();
            dest.writeByte((ordinal << 4) + (payloadBits & 0x0F));
            int l = node.transition(0);
            int r = node.transition(childCount - 1);
            assert 0 <= l && l <= r && r <= 255;
            dest.writeByte(l);
            dest.writeByte(r - l);      // r is included, i.e. this is len - 1

            for (int i = 0; i < childCount; ++i)
            {
                int next = node.transition(i);
                while (l < next)
                {
                    writeBytes(dest, NULL_VALUE);
                    ++l;
                }
                writeBytes(dest, -node.serializedPositionDelta(i, nodePosition));
                ++l;
            }
        }
    }

    static private class Dense12 extends Dense
    {
        // byte flags
        // byte start
        // byte length-1
        // length 12-bits transition targets (-1 for not present)
        // var payload

        Dense12(int ordinal)
        {
            super(ordinal, FRACTIONAL_BYTES);
        }

        @Override
        public int payloadPosition(ByteBuffer src, int position)
        {
            return position + 3 + (transitionRange(src, position) * 3 + 1) / 2;
        }

        @Override
        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            return -read12Bits(src, position + 3, childIndex);
        }

        @Override
        public int sizeofNode(SerializationNode<?> node)
        {
            int l = node.transition(0);
            int r = node.transition(node.childCount() - 1);
            return 3 + ((r - l + 1) * 3 + 1) / 2;
        }

        @Override
        public void serialize(DataOutputPlus dest, SerializationNode<?> node, int payloadBits, long nodePosition) throws IOException
        {
            int childCount = node.childCount();
            dest.writeByte((ordinal << 4) + (payloadBits & 0x0F));
            int l = node.transition(0);
            int r = node.transition(childCount - 1);
            assert 0 <= l && l <= r && r <= 255;
            dest.writeByte(l);
            dest.writeByte(r - l);      // r is included, i.e. this is len - 1

            int carry = 0;
            int start = l;
            for (int i = 0; i < childCount; ++i)
            {
                int next = node.transition(i);
                while (l < next)
                {
                    carry = write12Bits(dest, NULL_VALUE, l - start, carry);
                    ++l;
                }
                long pd = node.serializedPositionDelta(i, nodePosition);
                carry = write12Bits(dest, (int) -pd, l - start, carry);
                ++l;
            }
            if (((l - start) & 1) == 1)
                dest.writeByte(carry);
        }

        @Override
        boolean fits(long delta)
        {
            return 0 <= delta && delta <= 0xFFF;
        }
    }

    static private class LongDense extends Dense
    {
        // byte flags
        // byte start
        // byte length-1
        // length long transition targets (-1 for not present)
        // var payload
        LongDense(int ordinal)
        {
            super(ordinal, 8);
        }

        @Override
        public long transitionDelta(ByteBuffer src, int position, int childIndex)
        {
            return -src.getLong(position + 3 + childIndex * 8);
        }

        @Override
        public void writeBytes(DataOutputPlus dest, long ofs) throws IOException
        {
            dest.writeLong(ofs);
        }

        @Override
        boolean fits(long delta)
        {
            return true;
        }
    }


    static int read12Bits(ByteBuffer src, int base, int searchIndex)
    {
        int word = src.getShort(base + (3 * searchIndex) / 2);
        if ((searchIndex & 1) == 0)
            word = (word >> 4);
        return word & 0xFFF;
    }

    static int write12Bits(DataOutput dest, int value, int index, int carry) throws IOException
    {
        assert 0 <= value && value <= 0xFFF;
        if ((index & 1) == 0)
        {
            dest.writeByte(value >> 4);
            return value << 4;
        }
        else
        {
            dest.writeByte(carry | (value >> 8));
            dest.writeByte(value);
            return 0;
        }
    }

    long readBytes(ByteBuffer src, int position)
    {
        return SizedInts.readUnsigned(src, position, bytesPerPointer);
    }

    void writeBytes(DataOutputPlus dest, long ofs) throws IOException
    {
        assert fits(ofs);
        SizedInts.write(dest, ofs, bytesPerPointer);
    }

    boolean fits(long delta)
    {
        return 0 <= delta && delta < (1L << (bytesPerPointer * 8));
    }

    @Override
    public String toString()
    {
        String res = getClass().getSimpleName();
        if (bytesPerPointer >= 1)
            res += (bytesPerPointer * 8);
        return res;
    }

    static class Types
    {
        static final TrieNode PAYLOAD_ONLY = new PayloadOnly(0);
        static final TrieNode SINGLE_NOPAYLOAD_4 = new SingleNoPayload4(1);
        static final TrieNode SINGLE_8 = new Single(2, 1);
        static final TrieNode SINGLE_NOPAYLOAD_12 = new SingleNoPayload12(3);
        static final TrieNode SINGLE_16 = new Single(4, 2);
        static final TrieNode SPARSE_8 = new Sparse(5, 1);
        static final TrieNode SPARSE_12 = new Sparse12(6);
        static final TrieNode SPARSE_16 = new Sparse(7, 2);
        static final TrieNode SPARSE_24 = new Sparse(8, 3);
        static final TrieNode SPARSE_40 = new Sparse(9, 5);
        static final TrieNode DENSE_12 = new Dense12(10);
        static final TrieNode DENSE_16 = new Dense(11, 2);
        static final TrieNode DENSE_24 = new Dense(12, 3);
        static final TrieNode DENSE_32 = new Dense(13, 4);
        static final TrieNode DENSE_40 = new Dense(14, 5);
        static final TrieNode LONG_DENSE = new LongDense(15);

        // The position of each type in this list must match its ordinal value. Checked by the static block below.
        static final TrieNode[] values = new TrieNode[]{ PAYLOAD_ONLY,
                                                         SINGLE_NOPAYLOAD_4, SINGLE_8, SINGLE_NOPAYLOAD_12, SINGLE_16,
                                                         SPARSE_8, SPARSE_12, SPARSE_16, SPARSE_24, SPARSE_40,
                                                         DENSE_12, DENSE_16, DENSE_24, DENSE_32, DENSE_40,
                                                         LONG_DENSE }; // Catch-all

        // We can't fit all types * all sizes in 4 bits, so we use a selection. When we don't have a matching instance
        // we just use something more general that can do its job.
        // The arrays below must have corresponding types for all sizes specified by the singles row.
        // Note: 12 bit sizes are important, because that size will fit any pointer within a page-packed branch.
        static final TrieNode[] singles = new TrieNode[]{ SINGLE_NOPAYLOAD_4, SINGLE_8, SINGLE_NOPAYLOAD_12, SINGLE_16, DENSE_24, DENSE_32, DENSE_40, LONG_DENSE };
        static final TrieNode[] sparses = new TrieNode[]{ SPARSE_8, SPARSE_8, SPARSE_12, SPARSE_16, SPARSE_24, SPARSE_40, SPARSE_40, LONG_DENSE };
        static final TrieNode[] denses = new TrieNode[]{ DENSE_12, DENSE_12, DENSE_12, DENSE_16, DENSE_24, DENSE_32, DENSE_40, LONG_DENSE };

        static
        {
            //noinspection ConstantConditions
            assert sparses.length == singles.length && denses.length == singles.length && values.length <= 16;
            for (int i = 0; i < values.length; ++i)
                assert values[i].ordinal == i;
        }
    }
}
