Class SparseBitSet

src/main/java/pascal/taie/util/collection/SparseBitSet.java:38–1450

Sparse bit set. This implementation groups bits into blocks, and it could avoid allocating words to represent continuous zero bits when possible. This design saves memory and improves efficiency of set iterations. This implementation uses core design and some code from https://github.com/brettwo

 * and improve the readability.
 */
public class SparseBitSet extends AbstractBitSet
        implements Serializable {

    // TODO: unify level1/2/3 and table/area/block
    // Currently:
    // w1/level1 = table
    // w2/level2 = area
    // w3/level3 = block

    //==============================================================================
    //  The critical parameters. These are set up so that the compiler may
    //  pre-compute all the values as compile-time constants.
    //==============================================================================

    /**
     * The number of bits in a positive integer, and the size of permitted index
     * of a bit in the bit set.
     */
    private static final int INDEX_SIZE = Integer.SIZE - 1;

    /**
     * LEVEL3 is the number of bits of the level3 address.
     */
    private static final int LEVEL3 = 5; // Do not change!

    /**
     * LEVEL2 is the number of bits of the level2 address.
     */
    private static final int LEVEL2 = 5; // Do not change!

    /**
     * LEVEL1 is the number of bits of the level1 address.
     */
    private static final int LEVEL1 = INDEX_SIZE - LEVEL2 - LEVEL3 - ADDRESS_BITS_PER_WORD;

    /**
     * MAX_LENGTH1 is the maximum number of entries in the level1 set array.
     */
    private static final int MAX_LENGTH1 = 1 << LEVEL1;

    /**
     * LENGTH2 is the number of entries in the any level2 area.
     */
    private static final int LENGTH2 = 1 << LEVEL2;

    /**
     * LENGTH3 is the number of entries in the any level3 block.
     */
    private static final int LENGTH3 = 1 << LEVEL3;

    /**
     * The shift to create the word index. (I.e., move it to the right end)
     */
    static final int SHIFT3 = ADDRESS_BITS_PER_WORD;

    /**
     * MASK3 is the mask to extract the LEVEL3 address from a word index
     * (after shifting by SHIFT3).