1 /** 2 * Copyright 2009 The Apache Software Foundation 3 * 4 * Licensed to the Apache Software Foundation (ASF) under one 5 * or more contributor license agreements. See the NOTICE file 6 * distributed with this work for additional information 7 * regarding copyright ownership. The ASF licenses this file 8 * to you under the Apache License, Version 2.0 (the 9 * "License"); you may not use this file except in compliance 10 * with the License. You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, software 15 * distributed under the License is distributed on an "AS IS" BASIS, 16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 17 * See the License for the specific language governing permissions and 18 * limitations under the License. 19 */ 20 package org.apache.hadoop.hbase.io.hfile; 21 22 import java.util.LinkedList; 23 import java.util.PriorityQueue; 24 25 import org.apache.hadoop.hbase.io.HeapSize; 26 27 /** 28 * A memory-bound queue that will grow until an element brings 29 * total size >= maxSize. From then on, only entries that are sorted larger 30 * than the smallest current entry will be inserted/replaced. 31 * 32 * <p>Use this when you want to find the largest elements (according to their 33 * ordering, not their heap size) that consume as close to the specified 34 * maxSize as possible. Default behavior is to grow just above rather than 35 * just below specified max. 36 * 37 * <p>Object used in this queue must implement {@link HeapSize} as well as 38 * {@link Comparable}. 39 */ 40 public class CachedBlockQueue implements HeapSize { 41 42 private PriorityQueue<CachedBlock> queue; 43 44 private long heapSize; 45 private long maxSize; 46 47 /** 48 * @param maxSize the target size of elements in the queue 49 * @param blockSize expected average size of blocks 50 */ 51 public CachedBlockQueue(long maxSize, long blockSize) { 52 int initialSize = (int)(maxSize / blockSize); 53 if(initialSize == 0) initialSize++; 54 queue = new PriorityQueue<CachedBlock>(initialSize); 55 heapSize = 0; 56 this.maxSize = maxSize; 57 } 58 59 /** 60 * Attempt to add the specified cached block to this queue. 61 * 62 * <p>If the queue is smaller than the max size, or if the specified element 63 * is ordered before the smallest element in the queue, the element will be 64 * added to the queue. Otherwise, there is no side effect of this call. 65 * @param cb block to try to add to the queue 66 */ 67 public void add(CachedBlock cb) { 68 if(heapSize < maxSize) { 69 queue.add(cb); 70 heapSize += cb.heapSize(); 71 } else { 72 CachedBlock head = queue.peek(); 73 if(cb.compareTo(head) > 0) { 74 heapSize += cb.heapSize(); 75 heapSize -= head.heapSize(); 76 if(heapSize > maxSize) { 77 queue.poll(); 78 } else { 79 heapSize += head.heapSize(); 80 } 81 queue.add(cb); 82 } 83 } 84 } 85 86 /** 87 * @return a sorted List of all elements in this queue, in descending order 88 */ 89 public LinkedList<CachedBlock> get() { 90 LinkedList<CachedBlock> blocks = new LinkedList<CachedBlock>(); 91 while (!queue.isEmpty()) { 92 blocks.addFirst(queue.poll()); 93 } 94 return blocks; 95 } 96 97 /** 98 * Total size of all elements in this queue. 99 * @return size of all elements currently in queue, in bytes 100 */ 101 public long heapSize() { 102 return heapSize; 103 } 104 }