Index: src/test/java/org/apache/hadoop/hbase/io/hfile/TestCachedBlockQueue.java =================================================================== --- src/test/java/org/apache/hadoop/hbase/io/hfile/TestCachedBlockQueue.java (revision 1198132) +++ src/test/java/org/apache/hadoop/hbase/io/hfile/TestCachedBlockQueue.java (working copy) @@ -60,17 +60,14 @@ assertEquals(queue.heapSize(), expectedSize); - LinkedList blocks = - queue.get(); - assertEquals(blocks.poll().getName(), "cb1"); - assertEquals(blocks.poll().getName(), "cb2"); - assertEquals(blocks.poll().getName(), "cb3"); - assertEquals(blocks.poll().getName(), "cb4"); - assertEquals(blocks.poll().getName(), "cb5"); - assertEquals(blocks.poll().getName(), "cb6"); - assertEquals(blocks.poll().getName(), "cb7"); - assertEquals(blocks.poll().getName(), "cb8"); - + assertEquals(queue.poll().getName(), "cb1"); + assertEquals(queue.poll().getName(), "cb2"); + assertEquals(queue.poll().getName(), "cb3"); + assertEquals(queue.poll().getName(), "cb4"); + assertEquals(queue.poll().getName(), "cb5"); + assertEquals(queue.poll().getName(), "cb6"); + assertEquals(queue.poll().getName(), "cb7"); + assertEquals(queue.poll().getName(), "cb8"); } public void testQueueSmallBlockEdgeCase() throws Exception { @@ -113,17 +110,15 @@ assertEquals(queue.heapSize(), expectedSize); - LinkedList blocks = queue.get(); - assertEquals(blocks.poll().getName(), "cb0"); - assertEquals(blocks.poll().getName(), "cb1"); - assertEquals(blocks.poll().getName(), "cb2"); - assertEquals(blocks.poll().getName(), "cb3"); - assertEquals(blocks.poll().getName(), "cb4"); - assertEquals(blocks.poll().getName(), "cb5"); - assertEquals(blocks.poll().getName(), "cb6"); - assertEquals(blocks.poll().getName(), "cb7"); - assertEquals(blocks.poll().getName(), "cb8"); - + assertEquals(queue.poll().getName(), "cb0"); + assertEquals(queue.poll().getName(), "cb1"); + assertEquals(queue.poll().getName(), "cb2"); + assertEquals(queue.poll().getName(), "cb3"); + assertEquals(queue.poll().getName(), "cb4"); + assertEquals(queue.poll().getName(), "cb5"); + assertEquals(queue.poll().getName(), "cb6"); + assertEquals(queue.poll().getName(), "cb7"); + assertEquals(queue.poll().getName(), "cb8"); } private static class CachedBlock extends org.apache.hadoop.hbase.io.hfile.CachedBlock Index: src/main/java/org/apache/hadoop/hbase/io/hfile/LruBlockCache.java =================================================================== --- src/main/java/org/apache/hadoop/hbase/io/hfile/LruBlockCache.java (revision 1198132) +++ src/main/java/org/apache/hadoop/hbase/io/hfile/LruBlockCache.java (working copy) @@ -24,7 +24,6 @@ import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; -import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.PriorityQueue; @@ -494,11 +493,11 @@ } public long free(long toFree) { - LinkedList blocks = queue.get(); + CachedBlock cb; long freedBytes = 0; - for(CachedBlock cb: blocks) { + while ((cb = queue.pollLast()) != null) { freedBytes += evictBlock(cb); - if(freedBytes >= toFree) { + if (freedBytes >= toFree) { return freedBytes; } } Index: src/main/java/org/apache/hadoop/hbase/io/hfile/CachedBlockQueue.java =================================================================== --- src/main/java/org/apache/hadoop/hbase/io/hfile/CachedBlockQueue.java (revision 1198132) +++ src/main/java/org/apache/hadoop/hbase/io/hfile/CachedBlockQueue.java (working copy) @@ -19,8 +19,7 @@ */ package org.apache.hadoop.hbase.io.hfile; -import java.util.LinkedList; -import java.util.PriorityQueue; +import com.google.common.collect.MinMaxPriorityQueue; import org.apache.hadoop.hbase.io.HeapSize; @@ -39,7 +38,7 @@ */ public class CachedBlockQueue implements HeapSize { - private PriorityQueue queue; + private MinMaxPriorityQueue queue; private long heapSize; private long maxSize; @@ -51,7 +50,7 @@ public CachedBlockQueue(long maxSize, long blockSize) { int initialSize = (int)(maxSize / blockSize); if(initialSize == 0) initialSize++; - queue = new PriorityQueue(initialSize); + queue = MinMaxPriorityQueue.create(); heapSize = 0; this.maxSize = maxSize; } @@ -84,17 +83,22 @@ } /** - * @return a sorted List of all elements in this queue, in descending order + * @return The next element in this queue, or {@code null} if the queue is + * empty. */ - public LinkedList get() { - LinkedList blocks = new LinkedList(); - while (!queue.isEmpty()) { - blocks.addFirst(queue.poll()); - } - return blocks; + public CachedBlock poll() { + return queue.poll(); } /** + * @return The last element in this queue, or {@code null} if the queue is + * empty. + */ + public CachedBlock pollLast() { + return queue.pollLast(); + } + + /** * Total size of all elements in this queue. * @return size of all elements currently in queue, in bytes */