View Javadoc

1   /**
2    * Copyright 2010 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.util;
21  
22  import java.lang.ref.ReferenceQueue;
23  import java.lang.ref.SoftReference;
24  import java.util.ArrayList;
25  import java.util.Collection;
26  import java.util.Comparator;
27  import java.util.Map;
28  import java.util.Set;
29  import java.util.SortedMap;
30  import java.util.TreeMap;
31  import java.util.TreeSet;
32  
33  /**
34   * A SortedMap implementation that uses Soft Reference values
35   * internally to make it play well with the GC when in a low-memory
36   * situation. Use as a cache where you also need SortedMap functionality.
37   *
38   * @param <K> key class
39   * @param <V> value class
40   */
41  public class SoftValueSortedMap<K,V> implements SortedMap<K,V> {
42    private final SortedMap<K, SoftValue<K,V>> internalMap;
43    private final ReferenceQueue rq = new ReferenceQueue();
44  
45    /** Constructor */
46    public SoftValueSortedMap() {
47      this(new TreeMap<K, SoftValue<K,V>>());
48    }
49  
50    /**
51     * Constructor
52     * @param c comparator
53     */
54    public SoftValueSortedMap(final Comparator<K> c) {
55      this(new TreeMap<K, SoftValue<K,V>>(c));
56    }
57  
58    /** For headMap and tailMap support
59     * @param original object to wrap
60     */
61    private SoftValueSortedMap(SortedMap<K,SoftValue<K,V>> original) {
62      this.internalMap = original;
63    }
64  
65    /**
66     * Checks soft references and cleans any that have been placed on
67     * ReferenceQueue.  Call if get/put etc. are not called regularly.
68     * Internally these call checkReferences on each access.
69     * @return How many references cleared.
70     */
71    private int checkReferences() {
72      int i = 0;
73      for (Object obj; (obj = this.rq.poll()) != null;) {
74        i++;
75        //noinspection unchecked
76        this.internalMap.remove(((SoftValue<K,V>)obj).key);
77      }
78      return i;
79    }
80  
81    public synchronized V put(K key, V value) {
82      checkReferences();
83      SoftValue<K,V> oldValue = this.internalMap.put(key,
84        new SoftValue<K,V>(key, value, this.rq));
85      return oldValue == null ? null : oldValue.get();
86    }
87  
88    @SuppressWarnings("unchecked")
89    public synchronized void putAll(Map map) {
90      throw new RuntimeException("Not implemented");
91    }
92  
93    @SuppressWarnings({"SuspiciousMethodCalls"})
94    public synchronized V get(Object key) {
95      checkReferences();
96      SoftValue<K,V> value = this.internalMap.get(key);
97      if (value == null) {
98        return null;
99      }
100     if (value.get() == null) {
101       this.internalMap.remove(key);
102       return null;
103     }
104     return value.get();
105   }
106 
107   public synchronized V remove(Object key) {
108     checkReferences();
109     SoftValue<K,V> value = this.internalMap.remove(key);
110     return value == null ? null : value.get();
111   }
112 
113   public synchronized boolean containsKey(Object key) {
114     checkReferences();
115     return this.internalMap.containsKey(key);
116   }
117 
118   public synchronized boolean containsValue(Object value) {
119 /*    checkReferences();
120     return internalMap.containsValue(value);*/
121     throw new UnsupportedOperationException("Don't support containsValue!");
122   }
123 
124   public synchronized K firstKey() {
125     checkReferences();
126     return internalMap.firstKey();
127   }
128 
129   public synchronized K lastKey() {
130     checkReferences();
131     return internalMap.lastKey();
132   }
133 
134   public synchronized SoftValueSortedMap<K,V> headMap(K key) {
135     checkReferences();
136     return new SoftValueSortedMap<K,V>(this.internalMap.headMap(key));
137   }
138 
139   public synchronized SoftValueSortedMap<K,V> tailMap(K key) {
140     checkReferences();
141     return new SoftValueSortedMap<K,V>(this.internalMap.tailMap(key));
142   }
143 
144   public synchronized SoftValueSortedMap<K,V> subMap(K fromKey, K toKey) {
145     checkReferences();
146     return new SoftValueSortedMap<K,V>(this.internalMap.subMap(fromKey, toKey));
147   }
148 
149   public synchronized boolean isEmpty() {
150     checkReferences();
151     return this.internalMap.isEmpty();
152   }
153 
154   public synchronized int size() {
155     checkReferences();
156     return this.internalMap.size();
157   }
158 
159   public synchronized void clear() {
160     checkReferences();
161     this.internalMap.clear();
162   }
163 
164   public synchronized Set<K> keySet() {
165     checkReferences();
166     return this.internalMap.keySet();
167   }
168 
169   @SuppressWarnings("unchecked")
170   public synchronized Comparator comparator() {
171     return this.internalMap.comparator();
172   }
173 
174   public synchronized Set<Map.Entry<K,V>> entrySet() {
175     throw new RuntimeException("Not implemented");
176   }
177 
178   public synchronized Collection<V> values() {
179     checkReferences();
180     Collection<SoftValue<K,V>> softValues = this.internalMap.values();
181     ArrayList<V> hardValues = new ArrayList<V>();
182     for(SoftValue<K,V> softValue : softValues) {
183       hardValues.add(softValue.get());
184     }
185     return hardValues;
186   }
187 
188   private static class SoftValue<K,V> extends SoftReference<V> {
189     final K key;
190 
191     SoftValue(K key, V value, ReferenceQueue q) {
192       super(value, q);
193       this.key = key;
194     }
195   }
196 }