001 package railo.commons.util.mod; 002 import java.util.ConcurrentModificationException; 003 import java.util.HashMap; 004 import java.util.Iterator; 005 import java.util.LinkedHashMap; 006 import java.util.Map; 007 import java.util.NoSuchElementException; 008 009 import railo.runtime.exp.PageException; 010 011 public class LinkedHashMapPro<K,V> 012 extends HashMapPro<K,V> 013 implements MapPro<K,V> 014 { 015 016 private static final long serialVersionUID = 3801124242820219131L; 017 018 /** 019 * The head of the doubly linked list. 020 */ 021 private transient Entry<K,V> header; 022 023 /** 024 * The iteration ordering method for this linked hash map: <tt>true</tt> 025 * for access-order, <tt>false</tt> for insertion-order. 026 * 027 * @serial 028 */ 029 private final boolean accessOrder; 030 031 /** 032 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance 033 * with the specified initial capacity and load factor. 034 * 035 * @param initialCapacity the initial capacity 036 * @param loadFactor the load factor 037 * @throws IllegalArgumentException if the initial capacity is negative 038 * or the load factor is nonpositive 039 */ 040 public LinkedHashMapPro(int initialCapacity, float loadFactor) { 041 super(initialCapacity, loadFactor); 042 accessOrder = false; 043 } 044 045 /** 046 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance 047 * with the specified initial capacity and a default load factor (0.75). 048 * 049 * @param initialCapacity the initial capacity 050 * @throws IllegalArgumentException if the initial capacity is negative 051 */ 052 public LinkedHashMapPro(int initialCapacity) { 053 super(initialCapacity); 054 accessOrder = false; 055 } 056 057 /** 058 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance 059 * with the default initial capacity (16) and load factor (0.75). 060 */ 061 public LinkedHashMapPro() { 062 super(); 063 accessOrder = false; 064 } 065 066 // TODO better implementation 067 @Override 068 public void writeExternal(java.io.ObjectOutput out) throws java.io.IOException { 069 out.writeObject(new LinkedHashMap(this)); 070 } 071 @Override 072 public void readExternal(java.io.ObjectInput in) throws java.io.IOException, ClassNotFoundException { 073 this.putAll((Map)in.readObject()); 074 } 075 076 /** 077 * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with 078 * the same mappings as the specified map. The <tt>LinkedHashMap</tt> 079 * instance is created with a default load factor (0.75) and an initial 080 * capacity sufficient to hold the mappings in the specified map. 081 * 082 * @param m the map whose mappings are to be placed in this map 083 * @throws NullPointerException if the specified map is null 084 */ 085 public LinkedHashMapPro(Map<? extends K, ? extends V> m) { 086 super(m); 087 accessOrder = false; 088 } 089 090 /** 091 * Constructs an empty <tt>LinkedHashMap</tt> instance with the 092 * specified initial capacity, load factor and ordering mode. 093 * 094 * @param initialCapacity the initial capacity 095 * @param loadFactor the load factor 096 * @param accessOrder the ordering mode - <tt>true</tt> for 097 * access-order, <tt>false</tt> for insertion-order 098 * @throws IllegalArgumentException if the initial capacity is negative 099 * or the load factor is nonpositive 100 */ 101 public LinkedHashMapPro(int initialCapacity, 102 float loadFactor, 103 boolean accessOrder) { 104 super(initialCapacity, loadFactor); 105 this.accessOrder = accessOrder; 106 } 107 108 /** 109 * Called by superclass constructors and pseudoconstructors (clone, 110 * readObject) before any entries are inserted into the map. Initializes 111 * the chain. 112 */ 113 @Override 114 void init() { 115 header = new Entry<K,V>(-1, null, null, null); 116 header.before = header.after = header; 117 } 118 119 /** 120 * Transfers all entries to new table array. This method is called 121 * by superclass resize. It is overridden for performance, as it is 122 * faster to iterate using our linked list. 123 */ 124 @Override 125 void transfer(HashMapPro.Entry[] newTable, boolean rehash) { 126 int newCapacity = newTable.length; 127 for (Entry<K,V> e = header.after; e != header; e = e.after) { 128 if (rehash) 129 e.hash = (e.key == null) ? 0 : hash(e.key); 130 int index = indexFor(e.hash, newCapacity); 131 e.next = newTable[index]; 132 newTable[index] = e; 133 } 134 } 135 136 137 /** 138 * Returns <tt>true</tt> if this map maps one or more keys to the 139 * specified value. 140 * 141 * @param value value whose presence in this map is to be tested 142 * @return <tt>true</tt> if this map maps one or more keys to the 143 * specified value 144 */ 145 public boolean containsValue(Object value) { 146 // Overridden to take advantage of faster iterator 147 if (value==null) { 148 for (Entry e = header.after; e != header; e = e.after) 149 if (e.value==null) 150 return true; 151 } else { 152 for (Entry e = header.after; e != header; e = e.after) 153 if (value.equals(e.value)) 154 return true; 155 } 156 return false; 157 } 158 159 /** 160 * Returns the value to which the specified key is mapped, 161 * or {@code null} if this map contains no mapping for the key. 162 * 163 * <p>More formally, if this map contains a mapping from a key 164 * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 165 * key.equals(k))}, then this method returns {@code v}; otherwise 166 * it returns {@code null}. (There can be at most one such mapping.) 167 * 168 * <p>A return value of {@code null} does not <i>necessarily</i> 169 * indicate that the map contains no mapping for the key; it's also 170 * possible that the map explicitly maps the key to {@code null}. 171 * The {@link #containsKey containsKey} operation may be used to 172 * distinguish these two cases. 173 */ 174 public V get(Object key) { 175 HashMapPro.Entry<K,V> e = getEntry(key); 176 if (e == null) 177 return null; 178 e.recordAccess(this); 179 return e.value; 180 } 181 182 public V g(K key) throws PageException { 183 184 int hash = (key == null) ? 0 : hash(key); 185 for (HashMapPro.Entry<K,V> e = table[indexFor(hash, table.length)]; 186 e != null; 187 e = e.next) { 188 Object k; 189 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { 190 e.recordAccess(this); 191 return e.getValue(); 192 } 193 } 194 throw invalidKey(this, key,false); 195 } 196 197 public V g(K key, V defaultValue) { 198 199 int hash = (key == null) ? 0 : hash(key); 200 for (HashMapPro.Entry<K,V> e = table[indexFor(hash, table.length)]; 201 e != null; 202 e = e.next) { 203 Object k; 204 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { 205 e.recordAccess(this); 206 return e.getValue(); 207 } 208 } 209 return defaultValue; 210 } 211 212 213 214 215 216 /** 217 * Removes all of the mappings from this map. 218 * The map will be empty after this call returns. 219 */ 220 public void clear() { 221 super.clear(); 222 header.before = header.after = header; 223 } 224 225 /** 226 * LinkedHashMap entry. 227 */ 228 private static class Entry<K,V> extends HashMapPro.Entry<K,V> { 229 // These fields comprise the doubly linked list used for iteration. 230 Entry<K,V> before, after; 231 232 Entry(int hash, K key, V value, HashMapPro.Entry<K,V> next) { 233 super(hash, key, value, next); 234 } 235 236 /** 237 * Removes this entry from the linked list. 238 */ 239 private void remove() { 240 before.after = after; 241 after.before = before; 242 } 243 244 /** 245 * Inserts this entry before the specified existing entry in the list. 246 */ 247 private void addBefore(Entry<K,V> existingEntry) { 248 after = existingEntry; 249 before = existingEntry.before; 250 before.after = this; 251 after.before = this; 252 } 253 254 /** 255 * This method is invoked by the superclass whenever the value 256 * of a pre-existing entry is read by Map.get or modified by Map.set. 257 * If the enclosing Map is access-ordered, it moves the entry 258 * to the end of the list; otherwise, it does nothing. 259 */ 260 void recordAccess(HashMapPro<K,V> m) { 261 LinkedHashMapPro<K,V> lm = (LinkedHashMapPro<K,V>)m; 262 if (lm.accessOrder) { 263 lm.modCount++; 264 remove(); 265 addBefore(lm.header); 266 } 267 } 268 269 void recordRemoval(HashMapPro<K,V> m) { 270 remove(); 271 } 272 } 273 274 private abstract class LinkedHashIterator<T> implements Iterator<T> { 275 Entry<K,V> nextEntry = header.after; 276 Entry<K,V> lastReturned = null; 277 278 /** 279 * The modCount value that the iterator believes that the backing 280 * List should have. If this expectation is violated, the iterator 281 * has detected concurrent modification. 282 */ 283 int expectedModCount = modCount; 284 285 public boolean hasNext() { 286 return nextEntry != header; 287 } 288 289 public void remove() { 290 if (lastReturned == null) 291 throw new IllegalStateException(); 292 if (modCount != expectedModCount) 293 throw new ConcurrentModificationException(); 294 295 LinkedHashMapPro.this.remove(lastReturned.key); 296 lastReturned = null; 297 expectedModCount = modCount; 298 } 299 300 Entry<K,V> nextEntry() { 301 if (modCount != expectedModCount) 302 throw new ConcurrentModificationException(); 303 if (nextEntry == header) 304 throw new NoSuchElementException(); 305 306 Entry<K,V> e = lastReturned = nextEntry; 307 nextEntry = e.after; 308 return e; 309 } 310 } 311 312 private class KeyIterator extends LinkedHashIterator<K> { 313 public K next() { return nextEntry().getKey(); } 314 } 315 316 private class ValueIterator extends LinkedHashIterator<V> { 317 public V next() { return nextEntry().value; } 318 } 319 320 private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { 321 public Map.Entry<K,V> next() { return nextEntry(); } 322 } 323 324 // These Overrides alter the behavior of superclass view iterator() methods 325 Iterator<K> newKeyIterator() { return new KeyIterator(); } 326 Iterator<V> newValueIterator() { return new ValueIterator(); } 327 Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } 328 329 /** 330 * This override alters behavior of superclass put method. It causes newly 331 * allocated entry to get inserted at the end of the linked list and 332 * removes the eldest entry if appropriate. 333 */ 334 void addEntry(int hash, K key, V value, int bucketIndex) { 335 super.addEntry(hash, key, value, bucketIndex); 336 337 // Remove eldest entry if instructed 338 Entry<K,V> eldest = header.after; 339 if (removeEldestEntry(eldest)) { 340 removeEntryForKey(eldest.key); 341 } 342 } 343 344 /** 345 * This override differs from addEntry in that it doesn't resize the 346 * table or remove the eldest entry. 347 */ 348 void createEntry(int hash, K key, V value, int bucketIndex) { 349 HashMapPro.Entry<K,V> old = table[bucketIndex]; 350 Entry<K,V> e = new Entry<K,V>(hash, key, value, old); 351 table[bucketIndex] = e; 352 e.addBefore(header); 353 size++; 354 } 355 356 /** 357 * Returns <tt>true</tt> if this map should remove its eldest entry. 358 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after 359 * inserting a new entry into the map. It provides the implementor 360 * with the opportunity to remove the eldest entry each time a new one 361 * is added. This is useful if the map represents a cache: it allows 362 * the map to reduce memory consumption by deleting stale entries. 363 * 364 * <p>Sample use: this override will allow the map to grow up to 100 365 * entries and then delete the eldest entry each time a new entry is 366 * added, maintaining a steady state of 100 entries. 367 * <pre> 368 * private static final int MAX_ENTRIES = 100; 369 * 370 * protected boolean removeEldestEntry(Map.Entry eldest) { 371 * return size() > MAX_ENTRIES; 372 * } 373 * </pre> 374 * 375 * <p>This method typically does not modify the map in any way, 376 * instead allowing the map to modify itself as directed by its 377 * return value. It <i>is</i> permitted for this method to modify 378 * the map directly, but if it does so, it <i>must</i> return 379 * <tt>false</tt> (indicating that the map should not attempt any 380 * further modification). The effects of returning <tt>true</tt> 381 * after modifying the map from within this method are unspecified. 382 * 383 * <p>This implementation merely returns <tt>false</tt> (so that this 384 * map acts like a normal map - the eldest element is never removed). 385 * 386 * @param eldest The least recently inserted entry in the map, or if 387 * this is an access-ordered map, the least recently accessed 388 * entry. This is the entry that will be removed it this 389 * method returns <tt>true</tt>. If the map was empty prior 390 * to the <tt>put</tt> or <tt>putAll</tt> invocation resulting 391 * in this invocation, this will be the entry that was just 392 * inserted; in other words, if the map contains a single 393 * entry, the eldest entry is also the newest. 394 * @return <tt>true</tt> if the eldest entry should be removed 395 * from the map; <tt>false</tt> if it should be retained. 396 */ 397 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 398 return false; 399 } 400 }