001/* 002// This software is subject to the terms of the Eclipse Public License v1.0 003// Agreement, available at the following URL: 004// http://www.eclipse.org/legal/epl-v10.html. 005// You must accept the terms of that agreement to use this software. 006// 007// Copyright (C) 2007-2011 Pentaho and others 008// Copyright (C) 2007-2007 Tasecurity Group S.L, Spain 009// All Rights Reserved. 010*/ 011package mondrian.util; 012 013import java.lang.ref.WeakReference; 014import java.util.*; 015 016/** 017 * Map with limited size to be used as cache. 018 * 019 * @author lcanals, www.tasecurity.net 020 */ 021public class CacheMap<S, T> implements Map<S, T> { 022 private LinkedNode head; 023 private LinkedNode tail; 024 private final Map<S, Pair<S, T>> map; 025 private final int maxSize; 026 027 /** 028 * Creates an empty map with limited size. 029 * 030 * @param size Maximum number of mapped elements. 031 */ 032 public CacheMap(final int size) { 033 this.head = new LinkedNode(null, null); 034 this.tail = new LinkedNode(head, null); 035 this.map = new WeakHashMap<S, Pair<S, T>>(size); 036 this.maxSize = size; 037 } 038 039 public void clear() { 040 this.head = new LinkedNode(null, null); 041 this.tail = new LinkedNode(head, null); 042 map.clear(); 043 } 044 045 public boolean containsKey(final Object key) { 046 return map.containsKey(key); 047 } 048 049 public boolean containsValue(final Object value) { 050 return this.values().contains(value); 051 } 052 053 public Set entrySet() { 054 final Set<Map.Entry<S, T>> set = new HashSet<Map.Entry<S, T>>(); 055 for (final Map.Entry<S, Pair<S, T>> entry : this.map.entrySet()) { 056 set.add( 057 new Map.Entry<S, T>() { 058 public boolean equals(Object s) { 059 if (s instanceof Map.Entry) { 060 return ((Map.Entry) s).getKey().equals( 061 entry.getKey()) 062 && ((Map.Entry) s).getValue().equals( 063 entry.getValue().value); 064 } else { 065 return false; 066 } 067 } 068 069 public S getKey() { 070 return entry.getKey(); 071 } 072 073 public T getValue() { 074 return entry.getValue().value; 075 } 076 077 public int hashCode() { 078 return entry.hashCode(); 079 } 080 081 public T setValue(final T x) { 082 return entry.setValue( 083 new Pair<S, T>( 084 x, 085 new LinkedNode(head, entry.getKey()))).value; 086 } 087 }); 088 } 089 return set; 090 } 091 092 public T get(final Object key) { 093 final Pair<S, T> pair = map.get(key); 094 if (pair != null) { 095 final LinkedNode<S> node = pair.getNode(); 096 if (node == null) { 097 map.remove(key); 098 return null; 099 } 100 node.moveTo(head); 101 return pair.value; 102 } else { 103 return null; 104 } 105 } 106 107 public boolean isEmpty() { 108 return map.isEmpty(); 109 } 110 111 public Set<S> keySet() { 112 return map.keySet(); 113 } 114 115 public T put(final S key, final T value) { 116 final Pair<S, T> pair = 117 new Pair<S, T>(value, new LinkedNode(head, key)); 118 final Pair<S, T> obj = map.put(key, pair); 119 if (map.size() > maxSize) { 120 tail.getPrevious().remove(); 121 map.remove(key); 122 } 123 if (obj != null) { 124 return obj.value; 125 } else { 126 return null; 127 } 128 } 129 130 public void putAll(final Map t) { 131 throw new UnsupportedOperationException(); 132 } 133 134 public T remove(final Object key) { 135 final Pair<S, T> pair = map.get(key); 136 if (pair == null) { 137 return null; 138 } 139 pair.getNode().remove(); 140 return map.remove(key).value; 141 } 142 143 public int size() { 144 return map.size(); 145 } 146 147 public Collection<T> values() { 148 final List<T> vals = new ArrayList<T>(); 149 for (final Pair<S, T> pair : map.values()) { 150 vals.add(pair.value); 151 } 152 return vals; 153 } 154 155 public int hashCode() { 156 return map.hashCode(); 157 } 158 159 public String toString() { 160 return "Ordered keys: " + head.toString() + "\n" 161 + "Map:" + map.toString(); 162 } 163 164 public boolean equals(Object o) { 165 CacheMap c = (CacheMap) o; 166 return map.equals(c.map); 167 } 168 169 // 170 // PRIVATE STUFF ------------------ 171 // 172 173 /** 174 * Pair of linked key - value 175 */ 176 private final class Pair<S, T> implements java.io.Serializable { 177 private final T value; 178 private final WeakReference<LinkedNode<S>> node; 179 private Pair(final T value, final LinkedNode<S> node) { 180 this.node = new WeakReference<LinkedNode<S>>(node); 181 this.value = value; 182 } 183 184 private LinkedNode<S> getNode() { 185 return node.get(); 186 } 187 188 public boolean equals(final Object o) { 189 return o != null && o.equals(this.value); 190 } 191 } 192 193 194 /** 195 * Represents a node in a linked list. 196 */ 197 private class LinkedNode<S> implements java.io.Serializable { 198 private LinkedNode<S> next, prev; 199 private S key; 200 201 public LinkedNode(final LinkedNode<S> prev, final S key) { 202 this.key = key; 203 insertAfter(prev); 204 } 205 206 public void remove() { 207 if (this.prev != null) { 208 this.prev.next = this.next; 209 } 210 if (this.next != null) { 211 this.next.prev = this.prev; 212 } 213 } 214 215 public void moveTo(final LinkedNode<S> prev) { 216 remove(); 217 insertAfter(prev); 218 } 219 220 public LinkedNode<S> getPrevious() { 221 return this.prev; 222 } 223 224 public String toString() { 225 if (this.next != null) { 226 if (key != null) { 227 return key.toString() + ", " + this.next.toString(); 228 } else { 229 return "<null>, " + this.next.toString(); 230 } 231 } else { 232 if (key != null) { 233 return key.toString(); 234 } else { 235 return "<null>"; 236 } 237 } 238 } 239 240 private void insertAfter(final LinkedNode<S> prev) { 241 if (prev != null) { 242 this.next = prev.next; 243 } else { 244 this.prev = null; 245 } 246 this.prev = prev; 247 248 if (prev != null) { 249 if (prev.next != null) { 250 prev.next.prev = this; 251 } 252 prev.next = this; 253 } 254 } 255 } 256} 257 258// End CacheMap.java