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 Summary

  Fields
  Modifier and Type
  Field
  Description
  `static final int`
  `BLOCK_SIZE`
  The size of blocks used internally to store array values

- ## Constructor Summary

  Constructors
  Modifier
  Constructor
  Description
  ``
  `SemisparseByteArray()`
  `protected`
  `SemisparseByteArray(Map<Long,byte[]> blocks, ULongSpan.MutableULongSpanSet defined)`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `void`
  `clear()`
  Clear the array
  `int`
  `contiguousAvailableAfter(long loc)`
  Check how many contiguous bytes are available starting at the given address
  `SemisparseByteArray`
  `fork()`
  `void`
  `getData(long loc, byte[] data)`
  Copy a range of data from the semisparse array into the given byte array
  `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
  `ULongSpan.ULongSpanSet`
  `getInitialized(long a, long b)`
  Enumerate the initialized ranges within the given range
  `ULongSpan.ULongSpanSet`
  `getUninitialized(long a, long b)`
  Enumerate the uninitialized ranges within the given range
  `boolean`
  `isInitialized(long a)`
  Check if an index is initialized
  `boolean`
  `isInitialized(long a, long b)`
  Check if a range is completely initialized
  `void`
  `putAll(SemisparseByteArray from)`
  Copy the contents on another semisparse array into this one
  `void`
  `putData(long loc, byte[] data)`
  Initialize or modify a range of the array by copying from a given array
  `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

  ### Methods inherited from class java.lang.Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- ## Field Details

  - ### BLOCK_SIZE

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

- ## Constructor Details

  - ### SemisparseByteArray

    public SemisparseByteArray()

  - ### SemisparseByteArray

    protected SemisparseByteArray(Map<Long,byte[]> blocks, ULongSpan.MutableULongSpanSet defined)

- ## 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(long, byte[], int, int)`

  - ### 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(long, byte[], int, int)`

  - ### 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