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