Package org.apache.druid.query.groupby.epinephelinae

Class ByteBufferHashTable

java.lang.Object
org.apache.druid.query.groupby.epinephelinae.ByteBufferHashTable
public class ByteBufferHashTable extends Object
A fixed-width, open-addressing hash table that lives inside a caller-provided byte buffer.

The table uses a contiguous slice of the input ByteBuffer as its backing store. Each bucket holds at most one entry, and occupies bucketSizeWithHash number of bytes. Collisions are resolved by continuously probing the next bucket to find an empty bucket to slot the new entry. The current table view tableBuffer is maintained as a ByteBuffer slice that moves and grows within the arena as the table expands.

  • Field Details

    • maxSizeForTesting

      protected final int maxSizeForTesting

    • HASH_SIZE

      protected static final int HASH_SIZE
      See Also:

    • maxLoadFactor

      protected final float maxLoadFactor

    • initialBuckets

      protected final int initialBuckets

    • buffer

      protected final ByteBuffer buffer

    • bucketSizeWithHash

      protected final int bucketSizeWithHash

    • tableArenaSize

      protected final int tableArenaSize

    • keySize

      protected final int keySize

    • tableStart

      protected int tableStart

    • tableBuffer

      protected ByteBuffer tableBuffer

    • size

      protected int size

    • regrowthThreshold

      protected int regrowthThreshold

    • maxBuckets

      protected int maxBuckets

    • growthCount

      protected int growthCount

    • bucketUpdateHandler

      @Nullable protected ByteBufferHashTable.BucketUpdateHandler bucketUpdateHandler

    • maxMergeBufferUsedBytes

      protected long maxMergeBufferUsedBytes

  • Constructor Details

    • ByteBufferHashTable

      public ByteBufferHashTable(float maxLoadFactor, int initialBuckets, int bucketSizeWithHash, ByteBuffer buffer, int keySize, int maxSizeForTesting, @Nullable ByteBufferHashTable.BucketUpdateHandler bucketUpdateHandler)

  • Method Details

    • calculateTableArenaSizeWithPerBucketAdditionalSize

      public static int calculateTableArenaSizeWithPerBucketAdditionalSize(int bufferCapacity, int bucketSize, int perBucketAdditionalSize)

    • calculateTableArenaSizeWithFixedAdditionalSize

      public static int calculateTableArenaSizeWithFixedAdditionalSize(int bufferCapacity, int bucketSize, int fixedAdditionalSize)

    • reset

      public void reset()

    • adjustTableWhenFull

      public void adjustTableWhenFull()

    • initializeNewBucketKey

      protected void initializeNewBucketKey(int bucket, ByteBuffer keyBuffer, int keyHash)

    • findBucketWithAutoGrowth

      protected int findBucketWithAutoGrowth(ByteBuffer keyBuffer, int keyHash, Runnable preTableGrowthRunnable)
      Find a bucket for a key, attempting to grow the table with adjustTableWhenFull() if possible.
      Parameters:
      keyBuffer - buffer containing the key
      keyHash - hash of the key
      preTableGrowthRunnable - runnable that executes before the table grows
      Returns:
      bucket number of the found bucket or -1 if a bucket could not be allocated after resizing.

    • findBucket

      protected int findBucket(boolean allowNewBucket, int buckets, ByteBuffer targetTableBuffer, ByteBuffer keyBuffer, int keyHash)
      Finds the bucket into which we should insert a key.
      Parameters:
      keyBuffer - key, must have exactly keySize bytes remaining. Will not be modified.
      targetTableBuffer - Need selectable buffer, since when resizing hash table, findBucket() is used on the newly allocated table buffer
      Returns:
      bucket index for this key, or -1 if no bucket is available due to being full

    • canAllowNewBucket

      protected boolean canAllowNewBucket()

    • getOffsetForBucket

      protected int getOffsetForBucket(int bucket)

    • maxSizeForBuckets

      protected int maxSizeForBuckets(int buckets)

    • isBucketUsed

      protected boolean isBucketUsed(int bucket)

    • isOffsetUsed

      protected boolean isOffsetUsed(int bucketOffset)

    • getTableBuffer

      public ByteBuffer getTableBuffer()

    • getSize

      public int getSize()

    • getRegrowthThreshold

      public int getRegrowthThreshold()

    • getMaxBuckets

      public int getMaxBuckets()

    • getGrowthCount

      public int getGrowthCount()

    • updateMaxMergeBufferUsedBytes

      protected void updateMaxMergeBufferUsedBytes()
      To maintain an accurate tracking of the maximum bytes used per query, this function is to be called immediately whenever either of size or bucketSizeWithHash is changed.

    • getMaxMergeBufferUsedBytes

      public long getMaxMergeBufferUsedBytes()