Bzip2HuffmanAllocator Class — netty Architecture

Source Code

codec-compression/src/main/java/io/netty/handler/codec/compression/Bzip2HuffmanAllocator.java lines 25–184

final class Bzip2HuffmanAllocator {
    /**
     * @param array The code length array
     * @param i The input position
     * @param nodesToMove The number of internal nodes to be relocated
     * @return The smallest {@code k} such that {@code nodesToMove <= k <= i} and
     *         {@code i <= (array[k] % array.length)}
     */
    private static int first(final int[] array, int i, final int nodesToMove) {
        final int length = array.length;
        final int limit = i;
        int k = array.length - 2;

        while (i >= nodesToMove && array[i] % length > limit) {
            k = i;
            i -= limit - i + 1;
        }
        i = Math.max(nodesToMove - 1, i);

        while (k > i + 1) {
            int temp = i + k >>> 1;
            if (array[temp] % length > limit) {
                k = temp;
            } else {
                i = temp;
            }
        }
        return k;
    }

    /**
     * Fills the code array with extended parent pointers.
     * @param array The code length array
     */
    private static void setExtendedParentPointers(final int[] array) {
        final int length = array.length;
        array[0] += array[1];

        for (int headNode = 0, tailNode = 1, topNode = 2; tailNode < length - 1; tailNode++) {
            int temp;
            if (topNode >= length || array[headNode] < array[topNode]) {
                temp = array[headNode];
                array[headNode++] = tailNode;
            } else {
                temp = array[topNode++];
            }

            if (topNode >= length || (headNode < tailNode && array[headNode] < array[topNode])) {
                temp += array[headNode];
                array[headNode++] = tailNode + length;
            } else {
                temp += array[topNode++];
            }
            array[tailNode] = temp;
        }
    }

    /**
     * Finds the number of nodes to relocate in order to achieve a given code length limit.
     * @param array The code length array
     * @param maximumLength The maximum bit length for the generated codes
     * @return The number of nodes to relocate
     */
    private static int findNodesToRelocate(final int[] array, final int maximumLength) {
        int currentNode = array.length - 2;
        for (int currentDepth = 1; currentDepth < maximumLength - 1 && currentNode > 1; currentDepth++) {
            currentNode =  first(array, currentNode - 1, 0);
        }
        return currentNode;
    }

    /**
     * A final allocation pass with no code length limit.
     * @param array The code length array
     */
    private static void allocateNodeLengths(final int[] array) {
        int firstNode = array.length - 2;
        int nextNode = array.length - 1;

        for (int currentDepth = 1, availableNodes = 2; availableNodes > 0; currentDepth++) {
            final int lastNode = firstNode;