Package ghidra.generic.util.datastruct

Class SemisparseByteArray

java.lang.Object
ghidra.generic.util.datastruct.SemisparseByteArray
public class SemisparseByteArray extends Object
A sparse byte array characterized by contiguous dense regions

Notionally, the array is 2 to the power 64 bytes in size. Only the initialized values are actually stored. Uninitialized indices are assumed to have the value 0. Naturally, this implementation works best when the array is largely uninitialized. For efficient use, isolated initialized values should be avoided. Rather, an entire range should be initialized at the same time.

On a number line, the initialized indices of a semisparse array might be depicted: 

 -----   --------- - ------         ---

In contrast, the same for a sparse array might be depicted: 

 -    --  -  - -    ---     --     -         -

This implementation is well-suited for memory caches where the memory is accessed by reading ranges instead of individual bytes. Because consecutive reads and writes tend to occur in a common locality, caches using a semisparse array may perform well.

This implementation is also thread-safe. Any thread needing exclusive access for multiple reads and/or writes, e.g., to implement a compare-and-set operation, must apply additional synchronization.

  • Field Details

    • BLOCK_SIZE

      public static final int BLOCK_SIZE
      The size of blocks used internally to store array values
      See Also:

  • Constructor Details

  • Method Details

    • fork

      public SemisparseByteArray fork()

    • clear

      public void clear()
      Clear the array

      All indices will be uninitialized after this call, just as it was immediately after construction

    • getData

      public void getData(long loc, byte[] data)
      Copy a range of data from the semisparse array into the given byte array
      Parameters:
      loc - the index to begin copying data out
      data - the array to copy data into
      See Also:

    • getData

      public void getData(long loc, byte[] data, int offset, int length)
      Copy a range of data from the semisparse array into a portion of the given byte array

      Copies length bytes of data from the semisparse array starting at index loc into data starting at index offset. All initialized portions within the requested region are copied. The uninitialized portions may be treated as zeroes or not copied at all. Typically, the destination array has been initialized to zero by the caller, such that all uninitialized portions are zero. To avoid fetching uninitialized data, use contiguousAvailableAfter(long) as an upper bound on the length.

      Parameters:
      loc - the index to begin copying data out
      data - the array to copy data into
      offset - the offset into the destination array
      length - the length of data to read

    • getInitialized

      public ULongSpan.ULongSpanSet getInitialized(long a, long b)
      Enumerate the initialized ranges within the given range

      The given range is interpreted as closed, i.e., [a, b].

      Parameters:
      a - the lower-bound, inclusive, of the range
      b - the upper-bound, inclusive, of the range
      Returns:
      the set of initialized ranges

    • isInitialized

      public boolean isInitialized(long a, long b)
      Check if a range is completely initialized

      The given range is interpreted as closed, i.e., [a, b].

      Parameters:
      a - the lower-bound, inclusive, of the range
      b - the upper-bound, inclusive, of the range
      Returns:
      true if all indices in the range are initialized, false otherwise

    • isInitialized

      public boolean isInitialized(long a)
      Check if an index is initialized
      Parameters:
      a - the index to check
      Returns:
      true if the index is initialized, false otherwise

    • getUninitialized

      public ULongSpan.ULongSpanSet getUninitialized(long a, long b)
      Enumerate the uninitialized ranges within the given range

      The given range is interpreted as closed, i.e., [a, b].

      Parameters:
      a - the lower-bound, inclusive, of the range
      b - the upper-bound, inclusive, of the range
      Returns:
      the set of uninitialized ranges

    • putData

      public void putData(long loc, byte[] data)
      Initialize or modify a range of the array by copying from a given array
      Parameters:
      loc - the index of the semisparse array to begin copying into
      data - the data to copy
      See Also:

    • putData

      public void putData(long loc, byte[] data, int offset, int length)
      Initialize or modify a range of the array by copying a portion from a given array
      Parameters:
      loc - the index of the semisparse array to begin copying into
      data - the source array to copy from
      offset - the offset of the source array to begin copying from
      length - the length of data to copy

    • putAll

      public void putAll(SemisparseByteArray from)
      Copy the contents on another semisparse array into this one
      Parameters:
      from - the source array

    • contiguousAvailableAfter

      public int contiguousAvailableAfter(long loc)
      Check how many contiguous bytes are available starting at the given address
      Parameters:
      loc - the starting offset
      Returns:
      the number of contiguous defined bytes following