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

Class MemoryOpenHashTable

java.lang.Object
org.apache.druid.query.groupby.epinephelinae.collection.MemoryOpenHashTable
public class MemoryOpenHashTable extends Object
An open-addressed hash table with linear probing backed by WritableMemory. Does not offer a similar interface to Map because this is meant to be useful to lower-level, high-performance callers. There is no copying or serde of keys and values: callers access the backing memory of the table directly. This table will not grow itself. Callers must handle growing if required; the copyTo(org.apache.druid.query.groupby.epinephelinae.collection.MemoryOpenHashTable, org.apache.druid.query.groupby.epinephelinae.collection.MemoryOpenHashTable.BucketCopyHandler) method is provided to assist.

  • Constructor Details

    • MemoryOpenHashTable

      public MemoryOpenHashTable(org.apache.datasketches.memory.WritableMemory tableMemory, int numBuckets, int maxSize, int keySize, int valueSize)
      Create a new table.
      Parameters:
      tableMemory - backing memory for the table; must be exactly large enough to hold "numBuckets"
      numBuckets - number of buckets for the table
      maxSize - maximum number of elements for the table; must be less than numBuckets
      keySize - key size in bytes
      valueSize - value size in bytes

  • Method Details

    • memoryNeeded

      public static int memoryNeeded(int numBuckets, int bucketSize)
      Returns the amount of memory needed for a table. This is just a multiplication, which is easy enough to do on your own, but sometimes it's nice for clarity's sake to call a function with a name that indicates why the multiplication is happening.
      Parameters:
      numBuckets - number of buckets
      bucketSize - size per bucket (in bytes)
      Returns:
      size of table (in bytes)

    • bucketSize

      public static int bucketSize(int keySize, int valueSize)
      Returns the size of each bucket in a table.
      Parameters:
      keySize - size of keys (in bytes)
      valueSize - size of values (in bytes)
      Returns:
      size of buckets (in bytes)

    • clear

      public void clear()
      Clear the table, resetting size to zero.

    • copyTo

      public void copyTo(MemoryOpenHashTable other, @Nullable MemoryOpenHashTable.BucketCopyHandler copyHandler)
      Copy this table into another one. The other table must be large enough to hold all the copied buckets. The other table will be cleared before the copy takes place.
      Parameters:
      other - the other table
      copyHandler - a callback that is notified for each copied bucket

    • findBucket

      public int findBucket(int keyHash, org.apache.datasketches.memory.Memory keySpace, int keySpacePosition)
      Finds the bucket for a particular key.
      Parameters:
      keyHash - result of calling HashTableUtils.hashMemory(org.apache.datasketches.memory.Memory, long, int) on this key
      keySpace - memory containing the key
      keySpacePosition - position of the key within keySpace
      Returns:
      bucket number if currently occupied, or -bucket - 1 if not occupied (yet)

    • canInsertNewBucket

      public boolean canInsertNewBucket()
      Returns whether this table can accept a new bucket.

    • initBucket

      public void initBucket(int bucket, org.apache.datasketches.memory.Memory keySpace, int keySpacePosition)
      Initialize a bucket with a particular key. Do not call this method unless the bucket is currently unused and canInsertNewBucket() returns true.
      Parameters:
      bucket - bucket number
      keySpace - memory containing the key
      keySpacePosition - position of the key within keySpace

    • size

      public int size()
      Returns the number of elements currently in the table.

    • numBuckets

      public int numBuckets()
      Returns the number of buckets in this table. Note that not all of these can actually be used. The amount that can be used depends on the "maxSize" parameter provided during construction.

    • keySize

      public int keySize()
      Returns the size of keys, in bytes.

    • valueSize

      public int valueSize()
      Returns the size of values, in bytes.

    • bucketKeyOffset

      public int bucketKeyOffset()
      Returns the offset within each bucket where the key starts.

    • bucketValueOffset

      public int bucketValueOffset()
      Returns the offset within each bucket where the value starts.

    • bucketSize

      public int bucketSize()
      Returns the size in bytes of each bucket.

    • bucketMemoryPosition

      public int bucketMemoryPosition(int bucket)
      Returns the position within memory() where a particular bucket starts.

    • memory

      public org.apache.datasketches.memory.WritableMemory memory()
      Returns the memory backing this table.

    • bucketIterator

      public it.unimi.dsi.fastutil.ints.IntIterator bucketIterator()
      Iterates over all used buckets, returning bucket numbers for each one. The intent is that callers will pass the bucket numbers to bucketMemoryPosition(int) and then use bucketKeyOffset() and bucketValueOffset() to extract keys and values from the buckets as needed.