/*
 * Licensed to the University of California, Berkeley 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 tachyon.worker.block.allocator;

import java.util.HashMap;
import java.util.Map;

import com.google.common.base.Preconditions;

import tachyon.worker.block.BlockMetadataManagerView;
import tachyon.worker.block.BlockStoreLocation;
import tachyon.worker.block.meta.StorageDirView;
import tachyon.worker.block.meta.StorageTierView;

/**
 * A round-robin allocator that allocates a block in the storage dir. It will allocate the block in
 * the highest tier possible: It always starts from the highest tier in a RR manner and goes to the
 * next tier when there is no enough space. The allocator only considers non-specific writes in its
 * RR policy (the location is either AnyTier or AnyDirInTier).
 */
public final class RoundRobinAllocator implements Allocator {
  private BlockMetadataManagerView mManagerView;

  // We need to remember the last dir index for every storage tier
  private Map<StorageTierView, Integer> mTierToLastDirMap = new HashMap<StorageTierView, Integer>();

  /**
   * Creates a new instance of {@link RoundRobinAllocator}.
   *
   * @param view {@link BlockMetadataManagerView} to pass to the allocator
   */
  public RoundRobinAllocator(BlockMetadataManagerView view) {
    mManagerView = Preconditions.checkNotNull(view);
    for (StorageTierView tierView : mManagerView.getTierViews()) {
      mTierToLastDirMap.put(tierView, -1);
    }
  }

  @Override
  public StorageDirView allocateBlockWithView(long sessionId, long blockSize,
      BlockStoreLocation location, BlockMetadataManagerView view) {
    mManagerView = Preconditions.checkNotNull(view);
    return allocateBlock(sessionId, blockSize, location);
  }

  /**
   * Allocates a block from the given block store location. The location can be a specific location,
   * or {@link BlockStoreLocation#anyTier()} or {@link BlockStoreLocation#anyDirInTier(String)}.
   *
   * @param sessionId the id of session to apply for the block allocation
   * @param blockSize the size of block in bytes
   * @param location the location in block store
   * @return a {@link StorageDirView} in which to create the temp block meta if success, null
   *         otherwise
   * @throws IllegalArgumentException if block location is invalid
   */
  private StorageDirView allocateBlock(long sessionId, long blockSize,
      BlockStoreLocation location) {
    Preconditions.checkNotNull(location);
    if (location.equals(BlockStoreLocation.anyTier())) {
      int tierIndex = 0; // always starting from the first tier
      for (int i = 0; i < mManagerView.getTierViews().size(); i ++) {
        StorageTierView tierView = mManagerView.getTierViews().get(tierIndex);
        int dirViewIndex = getNextAvailDirInTier(tierView, blockSize);
        if (dirViewIndex >= 0) {
          mTierToLastDirMap.put(tierView, dirViewIndex); // update
          return tierView.getDirView(dirViewIndex);
        } else { // we didn't find one in this tier, go to next tier
          tierIndex ++;
        }
      }
    } else if (location.equals(BlockStoreLocation.anyDirInTier(location.tierAlias()))) {
      StorageTierView tierView = mManagerView.getTierView(location.tierAlias());
      int dirViewIndex = getNextAvailDirInTier(tierView, blockSize);
      if (dirViewIndex >= 0) {
        mTierToLastDirMap.put(tierView, dirViewIndex); // update
        return tierView.getDirView(dirViewIndex);
      }
    } else {
      StorageTierView tierView = mManagerView.getTierView(location.tierAlias());
      StorageDirView dirView = tierView.getDirView(location.dir());
      if (dirView.getAvailableBytes() >= blockSize) {
        return dirView;
      }
    }

    return null;
  }

  /**
   * Finds an available dir in a given tier for a block with blockSize
   *
   * @param tierView the tier to find a dir
   * @param blockSize the requested block size
   * @return the index of the dir if non-negative; -1 if fail to find a dir
   */
  private int getNextAvailDirInTier(StorageTierView tierView, long blockSize) {
    int dirViewIndex = mTierToLastDirMap.get(tierView);
    for (int i = 0; i < tierView.getDirViews().size(); i ++) { // try this many times
      dirViewIndex = (dirViewIndex + 1) % tierView.getDirViews().size();
      if (tierView.getDirView(dirViewIndex).getAvailableBytes() >= blockSize) {
        return dirViewIndex;
      }
    }
    return -1;
  }
}

@@ -831,34 +831,8 @@
 r;%0A%0A
-import java.util.HashMap;%0A
 impo
@@ -849,16 +849,16 @@
 il.Map;%0A
+
 %0Aimport 
@@ -894,16 +894,55 @@
 ditions;
+%0Aimport com.google.common.collect.Maps;
 %0A%0Aimport
@@ -1370,16 +1370,17 @@
 re is no
+t
  enough 
@@ -1700,37 +1700,28 @@
 ivate Map%3CSt
-orageTierView
+ring
 , Integer%3E m
@@ -1720,24 +1720,29 @@
 teger%3E mTier
+Alias
 ToLastDirMap
@@ -1748,45 +1748,23 @@
 p = 
+Maps.
 new
- 
 HashMap
-%3CStorageTierView, Integer%3E
 ();%0A
@@ -2101,32 +2101,37 @@
 )) %7B%0A      mTier
+Alias
 ToLastDirMap.put
@@ -2139,16 +2139,35 @@
 tierView
+.getTierViewAlias()
 , -1);%0A 
@@ -3552,32 +3552,37 @@
 %0A          mTier
+Alias
 ToLastDirMap.put
@@ -3582,32 +3582,51 @@
 Map.put(tierView
+.getTierViewAlias()
 , dirViewIndex);
@@ -3621,34 +3621,24 @@
 rViewIndex);
- // update
 %0A          r
@@ -4068,24 +4068,29 @@
        mTier
+Alias
 ToLastDirMap
@@ -4102,16 +4102,35 @@
 tierView
+.getTierViewAlias()
 , dirVie
@@ -4141,18 +4141,8 @@
 ex);
- // update
 %0A   
@@ -4836,16 +4836,21 @@
  = mTier
+Alias
 ToLastDi
@@ -4866,16 +4866,35 @@
 tierView
+.getTierViewAlias()
 );%0A    f

Fix tier lookup in RoundRobinAllocator