Class BitVectorRepository

java.lang.Object
com.ibm.wala.util.intset.BitVectorRepository
public class BitVectorRepository extends Object
A repository for shared bit vectors as described by Heintze.

Points-to sets that cross their sparse-to-dense threshold delegate their dense part here via findOrCreateSharedSubset(BitVectorIntSet): the repository keeps one canonical representative per distinct bit pattern and hands it back on later lookups, so equal sets share a single backing array instead of each holding its own copy. Representatives are held by WeakReference so the repository never pins memory; entries whose representative has been collected are pruned opportunistically during lookups.

Representatives are bucketed by cardinality. Lookups scan the queried cardinality first, then successively smaller cardinalities down to 5 elements below it. In the exact-size bucket, a subset match of equal cardinality is necessarily bit-for-bit equality, so each entry's cached fingerprint(int[]) rejects non-matching candidates with a single long comparison before the word-by-word BitVector.isSubset confirmation runs. Strictly smaller buckets keep the exact exhaustive subset scan; no scalar prefilter is sound there because a strict subset's fingerprint need not match the queried set's.

The repository is a process-wide singleton guarded by synchronized on the lookup, and lookups never mutate caller-visible state. The representative chosen for a given query is deterministic (bucket insertion order), which keeps downstream iteration order stable.

  • Constructor Details

    • BitVectorRepository

      public BitVectorRepository()

  • Method Details

    • findOrCreateSharedSubset

      public static BitVectorIntSet findOrCreateSharedSubset(BitVectorIntSet value)
      Returns:
      the BitVector in this repository which is the canonical shared subset representative of value; the result will have the same bits as value, except it may exclude up to SUBSET_DELTA bits.
      Throws:
      IllegalArgumentException - if value is null