gianm commented on a change in pull request #9308: Add MemoryOpenHashTable, a table similar to ByteBufferHashTable. URL: https://github.com/apache/druid/pull/9308#discussion_r374974801
########## File path: processing/src/main/java/org/apache/druid/query/groupby/epinephelinae/collection/MemoryOpenHashTable.java ########## @@ -0,0 +1,433 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.druid.query.groupby.epinephelinae.collection; + +import it.unimi.dsi.fastutil.ints.IntIterator; +import org.apache.datasketches.memory.Memory; +import org.apache.datasketches.memory.WritableMemory; +import org.apache.druid.java.util.common.ISE; +import org.apache.druid.query.groupby.epinephelinae.Groupers; + +import javax.annotation.Nullable; +import java.nio.ByteBuffer; +import java.nio.ByteOrder; +import java.util.NoSuchElementException; + +/** + * An open-addressed hash table with linear probing backed by {@link WritableMemory}. Does not offer a similar + * interface to {@link java.util.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 {@link #copyTo} method is provided + * to assist. + */ +public class MemoryOpenHashTable +{ + private static final byte USED_BYTE = 1; + private static final int USED_BYTE_SIZE = Byte.BYTES; + + private final WritableMemory tableMemory; + private final int keySize; + private final int valueSize; + private final int bucketSize; + + // Maximum number of elements in the table (based on numBuckets and maxLoadFactor). + private final int maxSize; + + // Number of available/used buckets in the table. Always a power of two. + private final int numBuckets; + + // Mask that clips a number to [0, numBuckets). Used when searching through buckets. + private final int bucketMask; + + // Number of elements in the table right now. + private int size; + + /** + * Create a new table. + * + * @param tableMemory backing memory for the table; must be exactly large enough to hold "numBuckets" + * @param numBuckets number of buckets for the table + * @param maxSize maximum number of elements for the table; must be less than numBuckets + * @param keySize key size in bytes + * @param valueSize value size in bytes + */ + public MemoryOpenHashTable( + final WritableMemory tableMemory, + final int numBuckets, + final int maxSize, + final int keySize, + final int valueSize + ) + { + this.tableMemory = tableMemory; + this.numBuckets = numBuckets; + this.bucketMask = numBuckets - 1; + this.maxSize = maxSize; + this.keySize = keySize; + this.valueSize = valueSize; + this.bucketSize = bucketSize(keySize, valueSize); + + // Our main user today (HashVectorGrouper) needs the tableMemory to be backed by a big-endian ByteBuffer that is Review comment: Ah, this should probably say "VectorGrouper implementations". I'll change it. ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
