| /* |
| * Copyright 2000-2013 JetBrains s.r.o. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package com.intellij.util.containers.hash; |
| |
| |
| import org.jetbrains.annotations.NotNull; |
| import org.jetbrains.annotations.Nullable; |
| |
| import java.util.*; |
| |
| |
| public class LinkedHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> { |
| private Entry<K, V>[] table; |
| private Entry<K, V> top; |
| private Entry<K, V> back; |
| private int capacity; |
| private int size; |
| private final float loadFactor; |
| private final EqualityPolicy<K> hashingStrategy; |
| private final boolean accessOrder; |
| |
| public LinkedHashMap() { |
| this(0); |
| } |
| |
| public LinkedHashMap(int capacity) { |
| this(capacity, HashUtil.DEFAULT_LOAD_FACTOR); |
| } |
| public LinkedHashMap(int capacity, boolean accessOrder) { |
| this(capacity, HashUtil.DEFAULT_LOAD_FACTOR, accessOrder); |
| } |
| |
| public LinkedHashMap(int capacity, float loadFactor) { |
| this(capacity, loadFactor, (EqualityPolicy)EqualityPolicy.CANONICAL); |
| } |
| |
| public LinkedHashMap(int capacity, float loadFactor, boolean accessOrder) { |
| this(capacity, loadFactor, (EqualityPolicy)EqualityPolicy.CANONICAL, accessOrder); |
| } |
| |
| public LinkedHashMap(EqualityPolicy<K> hashingStrategy) { |
| this(0, HashUtil.DEFAULT_LOAD_FACTOR, hashingStrategy); |
| } |
| |
| public LinkedHashMap(int capacity, float loadFactor, EqualityPolicy<K> hashingStrategy) { |
| this(capacity, loadFactor, hashingStrategy, false); |
| } |
| public LinkedHashMap(int capacity, float loadFactor, EqualityPolicy<K> hashingStrategy, boolean accessOrder) { |
| this.loadFactor = loadFactor; |
| this.hashingStrategy = hashingStrategy; |
| clear(capacity); |
| this.accessOrder = accessOrder; |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public boolean isEmpty() { |
| return size() == 0; |
| } |
| |
| @Override |
| public void clear() { |
| clear(0); |
| } |
| |
| @Override |
| public V get(final Object key) { |
| final Entry<K, V>[] table = this.table; |
| final int hash = HashUtil.hash(key, hashingStrategy); |
| final int index = hash % table.length; |
| |
| for (Entry<K, V> e = table[index]; e != null; e = e.hashNext) { |
| final K entryKey; |
| if (e.keyHash == hash && ((entryKey = e.key) == key || hashingStrategy.isEqual(entryKey, (K)key))) { |
| moveToTop(e); |
| return e.value; |
| |
| } |
| } |
| return null; |
| } |
| |
| @Override |
| public V put(final K key, @NotNull final V value) { |
| final Entry<K, V>[] table = this.table; |
| final int hash = HashUtil.hash(key, hashingStrategy); |
| final int index = hash % table.length; |
| for (Entry<K, V> e = table[index]; e != null; e = e.hashNext) { |
| final K entryKey; |
| if (e.keyHash == hash && ((entryKey = e.key) == key || hashingStrategy.isEqual(entryKey, key))) { |
| moveToTop(e); |
| return e.setValue(value); |
| } |
| } |
| final Entry<K, V> e = new Entry<K, V>(key, value, hash); |
| e.hashNext = table[index]; |
| table[index] = e; |
| final Entry<K, V> top = this.top; |
| e.next = top; |
| if (top != null) { |
| top.previous = e; |
| } |
| else { |
| back = e; |
| } |
| this.top = e; |
| size++; |
| if (removeEldestEntry(back, back.key, back.value)) { |
| doRemoveEldestEntry(); |
| } |
| else if (size > capacity) { |
| rehash((int)(capacity * HashUtil.CAPACITY_MULTIPLE)); |
| } |
| return null; |
| } |
| |
| public void doRemoveEldestEntry() { |
| final V val = remove(back.key); |
| assert val != null : "LinkedHashMap.Entry was not removed. Possibly mutable key: " + back.key; |
| } |
| |
| @Override |
| public boolean containsKey(final Object key) { |
| return get(key) != null; |
| } |
| |
| @Override |
| public V remove(final Object key) { |
| final Entry<K, V>[] table = this.table; |
| final int hash = HashUtil.hash(key, hashingStrategy); |
| final int index = hash % table.length; |
| Entry<K, V> e = table[index]; |
| if (e == null) { |
| return null; |
| } |
| K entryKey; |
| if (e.keyHash == hash && ((entryKey = e.key) == key || hashingStrategy.isEqual(entryKey, (K)key))) { |
| table[index] = e.hashNext; |
| } |
| else { |
| for (; ;) { |
| final Entry<K, V> last = e; |
| e = e.hashNext; |
| if (e == null) { |
| return null; |
| } |
| if (e.keyHash == hash && ((entryKey = e.key) == key || hashingStrategy.isEqual(entryKey, (K)key))) { |
| last.hashNext = e.hashNext; |
| break; |
| } |
| } |
| } |
| unlink(e); |
| size--; |
| return e.value; |
| } |
| |
| @NotNull |
| @Override |
| public Set<K> keySet() { |
| return new KeySet(); |
| } |
| |
| @NotNull |
| @Override |
| public Collection<V> values() { |
| return new Values(); |
| } |
| |
| @NotNull |
| @Override |
| public Set<Map.Entry<K, V>> entrySet() { |
| return new EntrySet(); |
| } |
| |
| protected boolean removeEldestEntry(Map.Entry<K, V> eldest, K key, V value) { |
| return removeEldestEntry(eldest); |
| } |
| |
| protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { |
| return false; |
| } |
| |
| private void init(int capacity) { |
| table = new Entry[HashUtil.adjustTableSize((int)(capacity / loadFactor))]; |
| top = back = null; |
| this.capacity = capacity; |
| } |
| |
| private void clear(int capacity) { |
| if (capacity < HashUtil.MIN_CAPACITY) { |
| capacity = HashUtil.MIN_CAPACITY; |
| } |
| init(capacity); |
| size = 0; |
| } |
| |
| @Nullable |
| public K getLastKey() { |
| return top != null ? top.key : null; |
| } |
| |
| @Nullable |
| public V getLastValue() { |
| return top != null ? top.value : null; |
| } |
| |
| private void moveToTop(final Entry<K, V> e) { |
| if (!accessOrder) { |
| return; |
| } |
| |
| final Entry<K, V> top = this.top; |
| if (top != e) { |
| final Entry<K, V> prev = e.previous; |
| final Entry<K, V> next = e.next; |
| prev.next = next; |
| if (next != null) { |
| next.previous = prev; |
| } |
| else { |
| back = prev; |
| } |
| top.previous = e; |
| e.next = top; |
| e.previous = null; |
| this.top = e; |
| } |
| } |
| |
| private void unlink(final Entry<K, V> e) { |
| final Entry<K, V> prev = e.previous; |
| final Entry<K, V> next = e.next; |
| if (prev != null) { |
| prev.next = next; |
| } |
| else { |
| top = next; |
| } |
| if (next != null) { |
| next.previous = prev; |
| } |
| else { |
| back = prev; |
| } |
| |
| // Help GC |
| e.previous = null; |
| e.next = null; |
| } |
| |
| private void rehash(int capacity) { |
| table = new Entry[HashUtil.adjustTableSize((int)(capacity / loadFactor))]; |
| this.capacity = capacity; |
| final Entry<K, V>[] table = this.table; |
| final int tableLen = table.length; |
| for (Entry<K, V> e = back; e != null; e = e.previous) { |
| final int hash = e.keyHash % tableLen; |
| e.hashNext = table[hash]; |
| table[hash] = e; |
| } |
| } |
| |
| private static class Entry<K, V> implements Map.Entry<K, V> { |
| |
| private final K key; |
| private final int keyHash; |
| private V value; |
| private Entry<K, V> next; |
| private Entry<K, V> previous; |
| private Entry<K, V> hashNext; |
| |
| public Entry(final K key, final V value, int hash) { |
| this.key = key; |
| keyHash = hash; |
| this.value = value; |
| } |
| |
| @Override |
| public K getKey() { |
| return key; |
| } |
| |
| @Override |
| public V getValue() { |
| return value; |
| } |
| |
| @Override |
| public V setValue(final V value) { |
| final V result = this.value; |
| this.value = value; |
| return result; |
| } |
| } |
| |
| private abstract class LinkedHashIterator<T> implements Iterator<T> { |
| |
| private LinkedHashMap.Entry<K, V> e = back; |
| private LinkedHashMap.Entry<K, V> last; |
| |
| @Override |
| public boolean hasNext() { |
| return e != null; |
| } |
| |
| @Override |
| public void remove() { |
| if (last == null) { |
| throw new IllegalStateException(); |
| } |
| LinkedHashMap.this.remove(last.key); |
| last = null; |
| } |
| |
| protected LinkedHashMap.Entry<K, V> nextEntry() { |
| final LinkedHashMap.Entry<K, V> result = last = e; |
| e = result.previous; |
| return result; |
| } |
| } |
| |
| private final class EntrySet extends AbstractSet<Map.Entry<K, V>> { |
| |
| @NotNull |
| @Override |
| public Iterator<Map.Entry<K, V>> iterator() { |
| return new LinkedHashIterator<Map.Entry<K, V>>() { |
| @Override |
| public Map.Entry<K, V> next() { |
| return nextEntry(); |
| } |
| }; |
| } |
| |
| @Override |
| public boolean contains(Object o) { |
| if (!(o instanceof Map.Entry)) { |
| return false; |
| } |
| final Map.Entry<K, V> e = (Map.Entry<K, V>)o; |
| final V value = get(e.getKey()); |
| return value != null && value.equals(e.getValue()); |
| } |
| |
| @Override |
| public boolean remove(Object o) { |
| if (!(o instanceof Map.Entry)) { |
| return false; |
| } |
| final Map.Entry<K, V> e = (Map.Entry<K, V>)o; |
| return LinkedHashMap.this.remove(e.getKey()) != null; |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public void clear() { |
| LinkedHashMap.this.clear(); |
| } |
| } |
| |
| private final class KeySet extends AbstractSet<K> { |
| |
| @NotNull |
| @Override |
| public Iterator<K> iterator() { |
| return new LinkedHashIterator<K>() { |
| @Override |
| public K next() { |
| return nextEntry().key; |
| } |
| }; |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public boolean contains(Object o) { |
| return LinkedHashMap.this.containsKey(o); |
| } |
| |
| @Override |
| public boolean remove(Object o) { |
| return LinkedHashMap.this.remove(o) != null; |
| } |
| |
| @Override |
| public void clear() { |
| LinkedHashMap.this.clear(); |
| } |
| } |
| |
| private final class Values extends AbstractCollection<V> { |
| |
| @NotNull |
| @Override |
| public Iterator<V> iterator() { |
| return new LinkedHashIterator<V>() { |
| @Override |
| public V next() { |
| return nextEntry().value; |
| } |
| }; |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| @Override |
| public boolean contains(Object o) { |
| return containsValue(o); |
| } |
| |
| @Override |
| public void clear() { |
| LinkedHashMap.this.clear(); |
| } |
| } |
| } |