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.Reference;
23  import java.lang.ref.ReferenceQueue;
24  import java.lang.ref.SoftReference;
25  import java.util.ArrayList;
26  import java.util.Collection;
27  import java.util.Collections;
28  import java.util.Comparator;
29  import java.util.LinkedHashSet;
30  import java.util.Map;
31  import java.util.NavigableMap;
32  import java.util.Set;
33  import java.util.SortedMap;
34  import java.util.TreeMap;
35  
36  /**
37   * A SortedMap implementation that uses Soft Reference values
38   * internally to make it play well with the GC when in a low-memory
39   * situation. Use as a cache where you also need SortedMap functionality.
40   *
41   * @param <K> key class
42   * @param <V> value class
43   */
44  public class SoftValueSortedMap<K,V> implements SortedMap<K,V> {
45    private final SortedMap<K, SoftValue<K,V>> internalMap;
46    private final ReferenceQueue<V> rq = new ReferenceQueue<V>();
47    private Object sync;
48  
49    /** Constructor */
50    public SoftValueSortedMap() {
51      this(new TreeMap<K, SoftValue<K,V>>());
52    }
53  
54    /**
55     * Constructor
56     * @param c comparator
57     */
58    public SoftValueSortedMap(final Comparator<K> c) {
59      this(new TreeMap<K, SoftValue<K,V>>(c));
60    }
61  
62    /** Internal constructor
63     * @param original object to wrap and synchronize on
64     */
65    private SoftValueSortedMap(SortedMap<K,SoftValue<K,V>> original) {
66      this(original, original);
67    }
68  
69    /** Internal constructor
70     * For headMap, tailMap, and subMap support
71     * @param original object to wrap
72     * @param sync object to synchronize on
73     */
74    private SoftValueSortedMap(SortedMap<K,SoftValue<K,V>> original, Object sync) {
75      this.internalMap = original;
76      this.sync = sync;
77    }
78  
79    /**
80     * Checks soft references and cleans any that have been placed on
81     * ReferenceQueue.  Call if get/put etc. are not called regularly.
82     * Internally these call checkReferences on each access.
83     * @return How many references cleared.
84     */
85    @SuppressWarnings("unchecked")
86    private int checkReferences() {
87      int i = 0;
88      for (Reference<? extends V> ref; (ref = this.rq.poll()) != null;) {
89        i++;
90        this.internalMap.remove(((SoftValue<K,V>)ref).key);
91      }
92      return i;
93    }
94  
95    public V put(K key, V value) {
96      synchronized(sync) {
97        checkReferences();
98        SoftValue<K,V> oldValue = this.internalMap.put(key,
99          new SoftValue<K,V>(key, value, this.rq));
100       return oldValue == null ? null : oldValue.get();
101     }
102   }
103 
104   @Override
105   public void putAll(Map<? extends K, ? extends V> m) {
106     throw new RuntimeException("Not implemented");
107   }
108 
109   public V get(Object key) {
110     synchronized(sync) {
111       checkReferences();
112       SoftValue<K,V> value = this.internalMap.get(key);
113       if (value == null) {
114         return null;
115       }
116       if (value.get() == null) {
117         this.internalMap.remove(key);
118         return null;
119       }
120       return value.get();
121     }
122   }
123 
124   public V remove(Object key) {
125     synchronized(sync) {
126       checkReferences();
127       SoftValue<K,V> value = this.internalMap.remove(key);
128       return value == null ? null : value.get();
129     }
130   }
131 
132   public boolean containsKey(Object key) {
133     synchronized(sync) {
134       checkReferences();
135       return this.internalMap.containsKey(key);
136     }
137   }
138 
139   public boolean containsValue(Object value) {
140     throw new UnsupportedOperationException("Don't support containsValue!");
141   }
142 
143   public K firstKey() {
144     synchronized(sync) {
145       checkReferences();
146       return internalMap.firstKey();
147     }
148   }
149 
150   public K lastKey() {
151     synchronized(sync) {
152       checkReferences();
153       return internalMap.lastKey();
154     }
155   }
156 
157   public SoftValueSortedMap<K,V> headMap(K key) {
158     synchronized(sync) {
159       checkReferences();
160       return new SoftValueSortedMap<K,V>(this.internalMap.headMap(key), sync);
161     }
162   }
163 
164   public SoftValueSortedMap<K,V> tailMap(K key) {
165     synchronized(sync) {
166       checkReferences();
167       return new SoftValueSortedMap<K,V>(this.internalMap.tailMap(key), sync);
168     }
169   }
170 
171   public SoftValueSortedMap<K,V> subMap(K fromKey, K toKey) {
172     synchronized(sync) {
173       checkReferences();
174       return new SoftValueSortedMap<K,V>(this.internalMap.subMap(fromKey,
175           toKey), sync);
176     }
177   }
178 
179   /*
180    * retrieves the value associated with the greatest key strictly less than
181    *  the given key, or null if there is no such key
182    * @param key the key we're interested in
183    */
184   public synchronized V lowerValueByKey(K key) {
185     synchronized(sync) {
186       checkReferences();
187 
188       Map.Entry<K,SoftValue<K,V>> entry =
189         ((NavigableMap<K, SoftValue<K,V>>) this.internalMap).lowerEntry(key);
190       if (entry==null) {
191         return null;
192       }
193       SoftValue<K,V> value=entry.getValue();
194       if (value==null) {
195         return null;
196       }
197       if (value.get() == null) {
198         this.internalMap.remove(key);
199         return null;
200       }
201       return value.get();
202     }
203   }
204   
205   public boolean isEmpty() {
206     synchronized(sync) {
207       checkReferences();
208       return this.internalMap.isEmpty();
209     }
210   }
211 
212   public int size() {
213     synchronized(sync) {
214       checkReferences();
215       return this.internalMap.size();
216     }
217   }
218 
219   public void clear() {
220     synchronized(sync) {
221       checkReferences();
222       this.internalMap.clear();
223     }
224   }
225 
226   public Set<K> keySet() {
227     synchronized(sync) {
228       checkReferences();
229       // this is not correct as per SortedMap contract (keySet should be
230       // modifiable)
231       // needed here so that another thread cannot modify the keyset
232       // without locking
233       return Collections.unmodifiableSet(this.internalMap.keySet());
234     }
235   }
236 
237   public Comparator<? super K> comparator() {
238     return this.internalMap.comparator();
239   }
240 
241   public Set<Map.Entry<K,V>> entrySet() {
242     synchronized(sync) {
243       checkReferences();
244       // this is not correct as per SortedMap contract (entrySet should be
245       // backed by map)
246       Set<Map.Entry<K, V>> realEntries = new LinkedHashSet<Map.Entry<K, V>>();
247       for (Map.Entry<K, SoftValue<K, V>> entry : this.internalMap.entrySet()) {
248         realEntries.add(entry.getValue());
249       }
250       return realEntries;
251     }
252   }
253 
254   public Collection<V> values() {
255     synchronized(sync) {
256       checkReferences();
257       ArrayList<V> hardValues = new ArrayList<V>();
258       for (SoftValue<K,V> softValue : this.internalMap.values()) {
259         hardValues.add(softValue.get());
260       }
261       return hardValues;
262     }
263   }
264 
265   private static class SoftValue<K,V> extends SoftReference<V> implements Map.Entry<K, V> {
266     final K key;
267 
268     SoftValue(K key, V value, ReferenceQueue<V> q) {
269       super(value, q);
270       this.key = key;
271     }
272 
273     public K getKey() {
274       return this.key;
275     }
276 
277     public V getValue() {
278       return get();
279     }
280 
281     public V setValue(V value) {
282       throw new RuntimeException("Not implemented");
283     }
284   }
285 }