1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18// BEGIN android-note 19// Completely different implementation from harmony. Runs much faster. 20// BEGIN android-note 21 22package java.util; 23 24/** 25 * LinkedHashMap is an implementation of {@link Map} that guarantees iteration order. 26 * All optional operations are supported. 27 * 28 * <p>All elements are permitted as keys or values, including null. 29 * 30 * <p>Entries are kept in a doubly-linked list. The iteration order is, by default, the 31 * order in which keys were inserted. Reinserting an already-present key doesn't change the 32 * order. If the three argument constructor is used, and {@code accessOrder} is specified as 33 * {@code true}, the iteration will be in the order that entries were accessed. 34 * The access order is affected by {@code put}, {@code get}, and {@code putAll} operations, 35 * but not by operations on the collection views. 36 * 37 * <p>Note: the implementation of {@code LinkedHashMap} is not synchronized. 38 * If one thread of several threads accessing an instance modifies the map 39 * structurally, access to the map needs to be synchronized. For 40 * insertion-ordered instances a structural modification is an operation that 41 * removes or adds an entry. Access-ordered instances also are structurally 42 * modified by {@code put}, {@code get}, and {@code putAll} since these methods 43 * change the order of the entries. Changes in the value of an entry are not structural changes. 44 * 45 * <p>The {@code Iterator} created by calling the {@code iterator} method 46 * may throw a {@code ConcurrentModificationException} if the map is structurally 47 * changed while an iterator is used to iterate over the elements. Only the 48 * {@code remove} method that is provided by the iterator allows for removal of 49 * elements during iteration. It is not possible to guarantee that this 50 * mechanism works in all cases of unsynchronized concurrent modification. It 51 * should only be used for debugging purposes. 52 */ 53public class LinkedHashMap<K, V> extends HashMap<K, V> { 54 55 /** 56 * A dummy entry in the circular linked list of entries in the map. 57 * The first real entry is header.nxt, and the last is header.prv. 58 * If the map is empty, header.nxt == header && header.prv == header. 59 */ 60 transient LinkedEntry<K, V> header; 61 62 /** 63 * True if access ordered, false if insertion ordered. 64 */ 65 private final boolean accessOrder; 66 67 /** 68 * Constructs a new empty {@code LinkedHashMap} instance. 69 */ 70 public LinkedHashMap() { 71 super(); 72 init(); 73 accessOrder = false; 74 } 75 76 /** 77 * Constructs a new {@code LinkedHashMap} instance with the specified 78 * capacity. 79 * 80 * @param initialCapacity 81 * the initial capacity of this map. 82 * @exception IllegalArgumentException 83 * when the capacity is less than zero. 84 */ 85 public LinkedHashMap(int initialCapacity) { 86 this(initialCapacity, DEFAULT_LOAD_FACTOR); 87 } 88 89 /** 90 * Constructs a new {@code LinkedHashMap} instance with the specified 91 * capacity and load factor. 92 * 93 * @param initialCapacity 94 * the initial capacity of this map. 95 * @param loadFactor 96 * the initial load factor. 97 * @throws IllegalArgumentException 98 * when the capacity is less than zero or the load factor is 99 * less or equal to zero. 100 */ 101 public LinkedHashMap(int initialCapacity, float loadFactor) { 102 this(initialCapacity, loadFactor, false); 103 } 104 105 /** 106 * Constructs a new {@code LinkedHashMap} instance with the specified 107 * capacity, load factor and a flag specifying the ordering behavior. 108 * 109 * @param initialCapacity 110 * the initial capacity of this hash map. 111 * @param loadFactor 112 * the initial load factor. 113 * @param accessOrder 114 * {@code true} if the ordering should be done based on the last 115 * access (from least-recently accessed to most-recently 116 * accessed), and {@code false} if the ordering should be the 117 * order in which the entries were inserted. 118 * @throws IllegalArgumentException 119 * when the capacity is less than zero or the load factor is 120 * less or equal to zero. 121 */ 122 public LinkedHashMap( 123 int initialCapacity, float loadFactor, boolean accessOrder) { 124 super(initialCapacity, loadFactor); 125 init(); 126 this.accessOrder = accessOrder; 127 } 128 129 /** 130 * Constructs a new {@code LinkedHashMap} instance containing the mappings 131 * from the specified map. The order of the elements is preserved. 132 * 133 * @param map 134 * the mappings to add. 135 */ 136 public LinkedHashMap(Map<? extends K, ? extends V> map) { 137 this(capacityForInitSize(map.size())); 138 constructorPutAll(map); 139 } 140 141 @Override void init() { 142 header = new LinkedEntry<K, V>(); 143 } 144 145 /** 146 * LinkedEntry adds nxt/prv double-links to plain HashMapEntry. 147 */ 148 static class LinkedEntry<K, V> extends HashMapEntry<K, V> { 149 LinkedEntry<K, V> nxt; 150 LinkedEntry<K, V> prv; 151 152 /** Create the header entry */ 153 LinkedEntry() { 154 super(null, null, 0, null); 155 nxt = prv = this; 156 } 157 158 /** Create a normal entry */ 159 LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next, 160 LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) { 161 super(key, value, hash, next); 162 this.nxt = nxt; 163 this.prv = prv; 164 } 165 } 166 167 /** 168 * Evicts eldest entry if instructed, creates a new entry and links it in 169 * as head of linked list. This method should call constructorNewEntry 170 * (instead of duplicating code) if the performance of your VM permits. 171 * 172 * <p>It may seem strange that this method is tasked with adding the entry 173 * to the hash table (which is properly the province of our superclass). 174 * The alternative of passing the "next" link in to this method and 175 * returning the newly created element does not work! If we remove an 176 * (eldest) entry that happens to be the first entry in the same bucket 177 * as the newly created entry, the "next" link would become invalid, and 178 * the resulting hash table corrupt. 179 */ 180 @Override void addNewEntry(K key, V value, int hash, int index) { 181 LinkedEntry<K, V> header = this.header; 182 183 // Remove eldest entry if instructed to do so. 184 LinkedEntry<K, V> eldest = header.nxt; 185 if (eldest != header && removeEldestEntry(eldest)) { 186 remove(eldest.key); 187 } 188 189 // Create new entry, link it on to list, and put it into table 190 LinkedEntry<K, V> oldTail = header.prv; 191 LinkedEntry<K, V> newTail = new LinkedEntry<K,V>( 192 key, value, hash, table[index], header, oldTail); 193 table[index] = oldTail.nxt = header.prv = newTail; 194 } 195 196 @Override void addNewEntryForNullKey(V value) { 197 LinkedEntry<K, V> header = this.header; 198 199 // Remove eldest entry if instructed to do so. 200 LinkedEntry<K, V> eldest = header.nxt; 201 if (eldest != header && removeEldestEntry(eldest)) { 202 remove(eldest.key); 203 } 204 205 // Create new entry, link it on to list, and put it into table 206 LinkedEntry<K, V> oldTail = header.prv; 207 LinkedEntry<K, V> newTail = new LinkedEntry<K,V>( 208 null, value, 0, null, header, oldTail); 209 entryForNullKey = oldTail.nxt = header.prv = newTail; 210 } 211 212 /** 213 * As above, but without eviction. 214 */ 215 @Override HashMapEntry<K, V> constructorNewEntry( 216 K key, V value, int hash, HashMapEntry<K, V> next) { 217 LinkedEntry<K, V> header = this.header; 218 LinkedEntry<K, V> oldTail = header.prv; 219 LinkedEntry<K, V> newTail 220 = new LinkedEntry<K,V>(key, value, hash, next, header, oldTail); 221 return oldTail.nxt = header.prv = newTail; 222 } 223 224 /** 225 * Returns the value of the mapping with the specified key. 226 * 227 * @param key 228 * the key. 229 * @return the value of the mapping with the specified key, or {@code null} 230 * if no mapping for the specified key is found. 231 */ 232 @Override public V get(Object key) { 233 /* 234 * This method is overridden to eliminate the need for a polymorphic 235 * invocation in superclass at the expense of code duplication. 236 */ 237 if (key == null) { 238 HashMapEntry<K, V> e = entryForNullKey; 239 if (e == null) 240 return null; 241 if (accessOrder) 242 makeTail((LinkedEntry<K, V>) e); 243 return e.value; 244 } 245 246 // Doug Lea's supplemental secondaryHash function (inlined) 247 int hash = key.hashCode(); 248 hash ^= (hash >>> 20) ^ (hash >>> 12); 249 hash ^= (hash >>> 7) ^ (hash >>> 4); 250 251 HashMapEntry<K, V>[] tab = table; 252 for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; 253 e != null; e = e.next) { 254 K eKey = e.key; 255 if (eKey == key || (e.hash == hash && key.equals(eKey))) { 256 if (accessOrder) 257 makeTail((LinkedEntry<K, V>) e); 258 return e.value; 259 } 260 } 261 return null; 262 } 263 264 /** 265 * Relinks the given entry to the tail of the list. Under access ordering, 266 * this method is invoked whenever the value of a pre-existing entry is 267 * read by Map.get or modified by Map.put. 268 */ 269 private void makeTail(LinkedEntry<K, V> e) { 270 // Unlink e 271 e.prv.nxt = e.nxt; 272 e.nxt.prv = e.prv; 273 274 // Relink e as tail 275 LinkedEntry<K, V> header = this.header; 276 LinkedEntry<K, V> oldTail = header.prv; 277 e.nxt = header; 278 e.prv = oldTail; 279 oldTail.nxt = header.prv = e; 280 modCount++; 281 } 282 283 @Override void preModify(HashMapEntry<K, V> e) { 284 if (accessOrder) { 285 makeTail((LinkedEntry<K, V>) e); 286 } 287 } 288 289 @Override void postRemove(HashMapEntry<K, V> e) { 290 LinkedEntry<K, V> le = (LinkedEntry<K, V>) e; 291 le.prv.nxt = le.nxt; 292 le.nxt.prv = le.prv; 293 le.nxt = le.prv = null; // Help the GC (for performance) 294 } 295 296 /** 297 * This override is done for LinkedHashMap performance: iteration is cheaper 298 * via LinkedHashMap nxt links. 299 */ 300 @Override public boolean containsValue(Object value) { 301 if (value == null) { 302 for (LinkedEntry<K, V> header = this.header, e = header.nxt; 303 e != header; e = e.nxt) { 304 if (e.value == null) { 305 return true; 306 } 307 } 308 return false; 309 } 310 311 // value is non-null 312 for (LinkedEntry<K, V> header = this.header, e = header.nxt; 313 e != header; e = e.nxt) { 314 if (value.equals(e.value)) { 315 return true; 316 } 317 } 318 return false; 319 } 320 321 public void clear() { 322 super.clear(); 323 324 // Clear all links to help GC 325 LinkedEntry<K, V> header = this.header; 326 for (LinkedEntry<K, V> e = header.nxt; e != header; ) { 327 LinkedEntry<K, V> nxt = e.nxt; 328 e.nxt = e.prv = null; 329 e = nxt; 330 } 331 332 header.nxt = header.prv = header; 333 } 334 335 private abstract class LinkedHashIterator<T> implements Iterator<T> { 336 LinkedEntry<K, V> next = header.nxt; 337 LinkedEntry<K, V> lastReturned = null; 338 int expectedModCount = modCount; 339 340 public final boolean hasNext() { 341 return next != header; 342 } 343 344 final LinkedEntry<K, V> nextEntry() { 345 if (modCount != expectedModCount) 346 throw new ConcurrentModificationException(); 347 LinkedEntry<K, V> e = next; 348 if (e == header) 349 throw new NoSuchElementException(); 350 next = e.nxt; 351 return lastReturned = e; 352 } 353 354 public final void remove() { 355 if (modCount != expectedModCount) 356 throw new ConcurrentModificationException(); 357 if (lastReturned == null) 358 throw new IllegalStateException(); 359 LinkedHashMap.this.remove(lastReturned.key); 360 lastReturned = null; 361 expectedModCount = modCount; 362 } 363 } 364 365 private final class KeyIterator extends LinkedHashIterator<K> { 366 public final K next() { return nextEntry().key; } 367 } 368 369 private final class ValueIterator extends LinkedHashIterator<V> { 370 public final V next() { return nextEntry().value; } 371 } 372 373 private final class EntryIterator 374 extends LinkedHashIterator<Map.Entry<K, V>> { 375 public final Map.Entry<K, V> next() { return nextEntry(); } 376 } 377 378 // Override view iterator methods to generate correct iteration order 379 @Override Iterator<K> newKeyIterator() { 380 return new KeyIterator(); 381 } 382 @Override Iterator<V> newValueIterator() { 383 return new ValueIterator(); 384 } 385 @Override Iterator<Map.Entry<K, V>> newEntryIterator() { 386 return new EntryIterator(); 387 } 388 389 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { 390 return false; 391 } 392 393 private static final long serialVersionUID = 3801124242820219131L; 394} 395