Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Licensed 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 com.facebook.presto.operator;
 
 
 import java.util.List;
 
 import static com.facebook.presto.operator.SyntheticAddress.decodePosition;
 import static com.facebook.presto.operator.SyntheticAddress.decodeSliceIndex;
 import static com.facebook.presto.operator.SyntheticAddress.encodeSyntheticAddress;
 import static com.facebook.presto.spi.type.BigintType.BIGINT;
 import static com.facebook.presto.sql.gen.JoinCompiler.PagesHashStrategyFactory;
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static io.airlift.slice.SizeOf.sizeOf;
 import static it.unimi.dsi.fastutil.HashCommon.arraySize;
 import static it.unimi.dsi.fastutil.HashCommon.maxFill;
 
 // This implementation assumes arrays used in the hash are always a power of 2
 public class GroupByHash
 {
     private static final JoinCompiler JOIN_COMPILER = new JoinCompiler();
 
     private static final float FILL_RATIO = 0.75f;
     private final List<Typetypes;
     private final int[] channels;
 
     private final PagesHashStrategy hashStrategy;
     private final List<ObjectArrayList<Block>> channelBuilders;
     private final HashGenerator hashGenerator;
     private final Optional<IntegerprecomputedHashChannel;
     private PageBuilder currentPageBuilder;
 
     private long completedPagesMemorySize;
 
     private int maxFill;
     private int mask;
     private long[] key;
     private int[] value;
 
     private final LongBigArray groupAddress;
 
     private int nextGroupId;
 
     public GroupByHash(List<? extends TypehashTypesint[] hashChannelsOptional<IntegerinputHashChannelint expectedSize)
     {
         checkNotNull(hashTypes"hashTypes is null");
         checkArgument(hashTypes.size() == hashChannels.length"hashTypes and hashChannels have different sizes");
         checkNotNull(inputHashChannel"inputHashChannel is null");
         checkArgument(expectedSize > 0, "expectedSize must be greater than zero");
 
         this. = inputHashChannel.isPresent() ? ImmutableList.copyOf(Iterables.concat(hashTypes, ImmutableList.of())) : ImmutableList.copyOf(hashTypes);
         this. = checkNotNull(hashChannels"hashChannels is null").clone();
         this. = inputHashChannel.isPresent() ? new PrecomputedHashGenerator(inputHashChannel.get()) : new InterpretedHashGenerator(ImmutableList.copyOf(hashTypes), hashChannels);
 
         // For each hashed channel, create an appendable list to hold the blocks (builders).  As we
         // add new values we append them to the existing block builder until it fills up and then
         // we add a new block builder to each list.
         ImmutableList.Builder<IntegeroutputChannels = ImmutableList.builder();
         ImmutableList.Builder<ObjectArrayList<Block>> channelBuilders = ImmutableList.builder();
         for (int i = 0; i < hashChannels.lengthi++) {
             outputChannels.add(i);
             channelBuilders.add(ObjectArrayList.wrap(new Block[1024], 0));
         }
         if (inputHashChannel.isPresent()) {
             this. = Optional.of(hashChannels.length);
             channelBuilders.add(ObjectArrayList.wrap(new Block[1024], 0));
         }
         else {
             this. = Optional.empty();
         }
         this. = channelBuilders.build();
         PagesHashStrategyFactory pagesHashStrategyFactory = .compilePagesHashStrategyFactory(this.outputChannels.build());
          = pagesHashStrategyFactory.createPagesHashStrategy(this.this.);
 
        startNewPage();
        // reserve memory for the arrays
        int hashSize = arraySize(expectedSize);
         = maxFill(hashSize);
         = hashSize - 1;
         = new long[hashSize];
        Arrays.fill(, -1);
         = new int[hashSize];
         = new LongBigArray();
    }
    public long getEstimatedSize()
    {
        return (sizeOf(.get(0).elements()) * .size()) +
                 +
                .getSizeInBytes() +
                sizeOf() +
                sizeOf() +
                .sizeOf();
    }
    public List<TypegetTypes()
    {
        return ;
    }
    public int getGroupCount()
    {
        return ;
    }
    public void appendValuesTo(int groupIdPageBuilder pageBuilderint outputChannelOffset)
    {
        long address = .get(groupId);
        int blockIndex = decodeSliceIndex(address);
        int position = decodePosition(address);
        .appendTo(blockIndexpositionpageBuilderoutputChannelOffset);
    }
    public GroupByIdBlock getGroupIds(Page page)
    {
        int positionCount = page.getPositionCount();
        // we know the exact size required for the block
        BlockBuilder blockBuilder = .createFixedSizeBlockBuilder(positionCount);
        // extract the hash columns
        Block[] hashBlocks = new Block[.];
        for (int i = 0; i < .i++) {
            hashBlocks[i] = page.getBlock([i]);
        }
        // get the group id for each position
        for (int position = 0; position < positionCountposition++) {
            // get the group for the current row
            int groupId = putIfAbsent(positionpagehashBlocks);
            // output the group id for this row
            .writeLong(blockBuildergroupId);
        }
        return new GroupByIdBlock(blockBuilder.build());
    }
    public boolean contains(int positionPage page)
    {
        // if hash is not provided, compute it using all the blocks in the page
        return contains(positionpage.hashRow(positionpage.getBlocks()));
    }
    public boolean contains(int positionPage pageint rawHash)
    {
        int hashPosition = getHashPosition(rawHash);
        // look for a slot containing this key
        while ([hashPosition] != -1) {
            long address = [hashPosition];
            if (.positionEqualsRow(decodeSliceIndex(address), decodePosition(address), positionpage.getBlocks())) {
                // found an existing slot for this key
                return true;
            }
            // increment position and mask to handle wrap around
            hashPosition = (hashPosition + 1) & ;
        }
        return false;
    }
    public int putIfAbsent(int positionPage pageBlock[] hashBlocks)
    {
        int rawHash = .hashPosition(positionpage);
        int hashPosition = getHashPosition(rawHash);
        // look for an empty slot or a slot containing this key
        int groupId = -1;
        while ([hashPosition] != -1) {
            long address = [hashPosition];
            if (positionEqualsCurrentRow(decodeSliceIndex(address), decodePosition(address), positionhashBlocks)) {
                // found an existing slot for this key
                groupId = [hashPosition];
                break;
            }
            // increment position and mask to handle wrap around
            hashPosition = (hashPosition + 1) & ;
        }
        // did we find an existing group?
        if (groupId < 0) {
            groupId = addNewGroup(hashPositionpositionpagerawHash);
        }
        return groupId;
    }
    private int addNewGroup(int hashPositionint positionPage pageint rawHash)
    {
        // add the row to the open page
        Block[] blocks = page.getBlocks();
        for (int i = 0; i < .i++) {
            int hashChannel = [i];
            Type type = .get(i);
            type.appendTo(blocks[hashChannel], position.getBlockBuilder(i));
        }
        if (.isPresent()) {
        }
        int pageIndex = .get(0).size() - 1;
        int pagePosition = .getPositionCount() - 1;
        long address = encodeSyntheticAddress(pageIndexpagePosition);
        // record group id in hash
        int groupId = ++;
        [hashPosition] = address;
        [hashPosition] = groupId;
        .set(groupIdaddress);
        // create new page builder if this page is full
        if (.isFull()) {
            startNewPage();
        }
        // increase capacity, if necessary
        if ( >= ) {
            rehash( * 2);
        }
        return groupId;
    }
    private void startNewPage()
    {
        if ( != null) {
        }
         = new PageBuilder();
        for (int i = 0; i < .size(); i++) {
        }
    }
    private void rehash(int size)
    {
        int newSize = arraySize(size + 1, );
        int newMask = newSize - 1;
        long[] newKey = new long[newSize];
        Arrays.fill(newKey, -1);
        int[] newValue = new int[newSize];
        int oldIndex = 0;
        for (int groupId = 0; groupId < groupId++) {
            // seek to the next used slot
            while ([oldIndex] == -1) {
                oldIndex++;
            }
            // get the address for this slot
            long address = [oldIndex];
            // find an empty slot for the address
            int pos = getHashPosition(hashPosition(address), newMask);
            while (newKey[pos] != -1) {
                pos = (pos + 1) & newMask;
            }
            // record the mapping
            newKey[pos] = address;
            newValue[pos] = [oldIndex];
            oldIndex++;
        }
        this. = newMask;
        this. = maxFill(newSize);
        this. = newKey;
        this. = newValue;
    }
    private int hashPosition(long sliceAddress)
    {
        int sliceIndex = decodeSliceIndex(sliceAddress);
        int position = decodePosition(sliceAddress);
        if (.isPresent()) {
            return getRawHash(sliceIndexposition);
        }
        return .hashPosition(sliceIndexposition);
    }
    private int getRawHash(int sliceIndexint position)
    {
        return (int.get(.get()).get(sliceIndex).getLong(position, 0);
    }
    private boolean positionEqualsCurrentRow(int sliceIndexint slicePositionint positionBlock[] blocks)
    {
        return .positionEqualsRow(sliceIndexslicePositionpositionblocks);
    }
    private static int getHashPosition(int rawHashint mask)
    {
        return ((int) XxHash64.hash(rawHash)) & mask;
    }
New to GrepCode? Check out our FAQ X