| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You 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. |
| */ |
| |
| #ifndef _DECAF_UTIL_LINKEDHASHMAP_H_ |
| #define _DECAF_UTIL_LINKEDHASHMAP_H_ |
| |
| #include <decaf/util/Config.h> |
| |
| #include <decaf/util/HashMap.h> |
| |
| namespace decaf { |
| namespace util { |
| |
| /** |
| * Hashed and linked list implementation of the Map interface, with predictable iteration order. |
| * |
| * This implementation differs from HashMap in that it maintains a doubly-linked list running |
| * through all of its entries. This linked list defines the iteration ordering, which is |
| * normally the order in which keys were inserted into the map (insertion-order). Note that |
| * insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted |
| * into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately |
| * prior to the invocation.) |
| * |
| * This implementation spares its clients from the unspecified, generally chaotic ordering |
| * provided by HashMap, without incurring the increased cost associated with TreeMap. It can |
| * be used to produce a copy of a map that has the same order as the original, regardless of |
| * the original map's implementation: |
| * |
| * void foo(Map m) { |
| * Map copy = new LinkedHashMap(m); |
| * ... |
| * } |
| * |
| * This technique is particularly useful if a module takes a map on input, copies it, and later |
| * returns results whose order is determined by that of the copy. (Clients generally appreciate |
| * having things returned in the same order they were presented.) |
| * |
| * A special constructor is provided to create a linked hash map whose order of iteration is the |
| * order in which its entries were last accessed, from least-recently accessed to most-recently |
| * (access-order). This kind of map is well-suited to building LRU caches. Invoking the put or |
| * get method results in an access to the corresponding entry (assuming it exists after the |
| * invocation completes). The putAll method generates one entry access for each mapping in the |
| * specified map, in the order that key-value mappings are provided by the specified map's entry |
| * set iterator. No other methods generate entry accesses. In particular, operations on |
| * collection-views do not affect the order of iteration of the backing map. |
| * |
| * The removeEldestEntry(MapEntry) method may be overridden to impose a policy for removing |
| * stale mappings automatically when new mappings are added to the map. When the entries are |
| * about to be removed from the map the onEviction method is called giving subclasses a |
| * chance to delete pointer values or perform other cleanup prior to the mapping being |
| * removed. |
| * |
| * This class provides all of the optional Map operations. Like HashMap, it provides |
| * constant-time performance for the basic operations (add, contains and remove), assuming |
| * the hash function disperses elements properly among the buckets. Performance is likely |
| * to be just slightly below that of HashMap, due to the added expense of maintaining the |
| * linked list, with one exception: Iteration over the collection-views of a LinkedHashMap |
| * requires time proportional to the size of the map, regardless of its capacity. Iteration |
| * over a HashMap is likely to be more expensive, requiring time proportional to its capacity. |
| * |
| * A linked hash map has two parameters that affect its performance: initial capacity and load |
| * factor. They are defined precisely as for HashMap. Note, however, that the penalty for |
| * choosing an excessively high value for initial capacity is less severe for this class than |
| * for HashMap, as iteration times for this class are unaffected by capacity. |
| * |
| * Note that this implementation is not synchronized. If multiple threads access a linked hash |
| * map concurrently, and at least one of the threads modifies the map structurally, it must |
| * be synchronized externally. This is typically accomplished by synchronizing on some object |
| * that naturally encapsulates the map. If no such object exists, the map should be "wrapped" |
| * using the Collections.synchronizedMap method. This is best done at creation time, to prevent |
| * accidental unsynchronized access to the map: |
| * |
| * Map<K,V>* m = Collections::synchronizedMap(new LinkedHashMap(...)); |
| * |
| * A structural modification is any operation that adds or deletes one or more mappings or, in |
| * the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered |
| * linked hash maps, merely changing the value associated with a key that is already contained |
| * in the map is not a structural modification. In access-ordered linked hash maps, merely |
| * querying the map with get is a structural modification.) |
| * |
| * The iterators returned by the iterator method of the collections returned by all of this |
| * class's collection view methods are fail-fast: if the map is structurally modified at any |
| * time after the iterator is created, in any way except through the iterator's own remove |
| * method, the iterator will throw a ConcurrentModificationException. Thus, in the face of |
| * concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, |
| * non-deterministic behavior at an undetermined time in the future. |
| * |
| * Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally |
| * speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent |
| * modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. |
| * Therefore, it would be wrong to write a program that depended on this exception for its |
| * correctness: the fail-fast behavior of iterators should be used only to detect bugs. |
| * |
| * @since 1.0 |
| */ |
| template<typename K, typename V, typename HASHCODE = HashCode<K> > |
| class LinkedHashMap : public HashMap<K, V, HASHCODE> { |
| private: |
| |
| class LinkedHashMapEntry : public HashMap<K, V, HASHCODE>::HashMapEntry { |
| private: |
| |
| LinkedHashMapEntry(const LinkedHashMapEntry&); |
| LinkedHashMapEntry& operator= (const LinkedHashMapEntry&); |
| |
| public: |
| |
| LinkedHashMapEntry* chainForward; |
| LinkedHashMapEntry* chainBackward; |
| |
| public: |
| |
| LinkedHashMapEntry(const K& key, const V& value, int hash) : |
| HashMap<K, V, HASHCODE>::HashMapEntry(key, value, hash), chainForward(), chainBackward() { |
| } |
| |
| LinkedHashMapEntry(const K& key, const V& value) : |
| HashMap<K, V, HASHCODE>::HashMapEntry(key, value), chainForward(), chainBackward() { |
| } |
| }; |
| |
| private: |
| |
| bool accessOrder; |
| mutable LinkedHashMapEntry* head; |
| mutable LinkedHashMapEntry* tail; |
| |
| private: |
| |
| class AbstractMapIterator { |
| protected: |
| |
| int expectedModCount; |
| LinkedHashMapEntry* futureEntry; |
| LinkedHashMapEntry* currentEntry; |
| LinkedHashMap* associatedMap; |
| |
| private: |
| |
| AbstractMapIterator(const AbstractMapIterator&); |
| AbstractMapIterator& operator= (const AbstractMapIterator&); |
| |
| public: |
| |
| AbstractMapIterator(LinkedHashMap* parent) : expectedModCount(parent->modCount), |
| futureEntry(parent->head), |
| currentEntry(NULL), |
| associatedMap(parent) { |
| } |
| |
| virtual ~AbstractMapIterator() {} |
| |
| void checkConcurrentMod() const { |
| if (expectedModCount != associatedMap->modCount) { |
| throw ConcurrentModificationException( |
| __FILE__, __LINE__, "LinkedHashMap modified outside this iterator"); |
| } |
| } |
| |
| virtual bool checkHasNext() const { |
| return (futureEntry != NULL); |
| } |
| |
| void makeNext() { |
| checkConcurrentMod(); |
| if (!checkHasNext()) { |
| throw decaf::util::NoSuchElementException( |
| __FILE__, __LINE__, "No next element"); |
| } |
| currentEntry = futureEntry; |
| futureEntry = futureEntry->chainForward; |
| } |
| |
| virtual void doRemove() { |
| checkConcurrentMod(); |
| if (currentEntry == NULL) { |
| throw decaf::lang::exceptions::IllegalStateException( |
| __FILE__, __LINE__, "Remove called before call to next()"); |
| } |
| |
| LinkedHashMapEntry* entry = currentEntry; |
| LinkedHashMapEntry* prev = entry->chainBackward; |
| LinkedHashMapEntry* next = entry->chainForward; |
| LinkedHashMap* map = associatedMap; |
| |
| // currentEntry gets deleted here. |
| associatedMap->removeEntry(currentEntry); |
| currentEntry = NULL; |
| |
| if (prev != NULL) { |
| prev->chainForward = next; |
| if (next != NULL) { |
| next->chainBackward = prev; |
| } else { |
| map->tail = prev; |
| } |
| } else { |
| map->head = next; |
| if (next != NULL) { |
| next->chainBackward = NULL; |
| } else { |
| map->tail = NULL; |
| } |
| } |
| expectedModCount++; |
| } |
| |
| }; |
| |
| class EntryIterator : public Iterator< MapEntry<K,V> >, public AbstractMapIterator { |
| private: |
| |
| EntryIterator(const EntryIterator&); |
| EntryIterator& operator= (const EntryIterator&); |
| |
| public: |
| |
| EntryIterator(LinkedHashMap* parent) : AbstractMapIterator(parent) { |
| } |
| |
| virtual ~EntryIterator() {} |
| |
| virtual bool hasNext() const { |
| return this->checkHasNext(); |
| } |
| |
| virtual MapEntry<K, V> next() { |
| this->makeNext(); |
| return *(this->currentEntry); |
| } |
| |
| virtual void remove() { |
| this->doRemove(); |
| } |
| }; |
| |
| class KeyIterator : public Iterator<K>, public AbstractMapIterator { |
| private: |
| |
| KeyIterator(const KeyIterator&); |
| KeyIterator& operator= (const KeyIterator&); |
| |
| public: |
| |
| KeyIterator(LinkedHashMap* parent) : AbstractMapIterator(parent) { |
| } |
| |
| virtual ~KeyIterator() {} |
| |
| virtual bool hasNext() const { |
| return this->checkHasNext(); |
| } |
| |
| virtual K next() { |
| this->makeNext(); |
| return this->currentEntry->getKey(); |
| } |
| |
| virtual void remove() { |
| this->doRemove(); |
| } |
| }; |
| |
| class ValueIterator : public Iterator<V>, public AbstractMapIterator { |
| private: |
| |
| ValueIterator(const ValueIterator&); |
| ValueIterator& operator= (const ValueIterator&); |
| |
| public: |
| |
| ValueIterator(LinkedHashMap* parent) : AbstractMapIterator(parent) { |
| } |
| |
| virtual ~ValueIterator() {} |
| |
| virtual bool hasNext() const { |
| return this->checkHasNext(); |
| } |
| |
| virtual V next() { |
| this->makeNext(); |
| return this->currentEntry->getValue(); |
| } |
| |
| virtual void remove() { |
| this->doRemove(); |
| } |
| }; |
| |
| private: |
| |
| class ConstAbstractMapIterator { |
| protected: |
| |
| int expectedModCount; |
| const LinkedHashMapEntry* futureEntry; |
| const LinkedHashMapEntry* currentEntry; |
| const LinkedHashMap* associatedMap; |
| |
| private: |
| |
| ConstAbstractMapIterator(const ConstAbstractMapIterator&); |
| ConstAbstractMapIterator& operator= (const ConstAbstractMapIterator&); |
| |
| public: |
| |
| ConstAbstractMapIterator(const LinkedHashMap* parent) : expectedModCount(parent->modCount), |
| futureEntry(parent->head), |
| currentEntry(NULL), |
| associatedMap(parent) { |
| } |
| |
| virtual ~ConstAbstractMapIterator() {} |
| |
| virtual bool checkHasNext() const { |
| return (futureEntry != NULL); |
| } |
| |
| void checkConcurrentMod() const { |
| if (expectedModCount != associatedMap->modCount) { |
| throw ConcurrentModificationException( |
| __FILE__, __LINE__, "LinkedHashMap modified outside this iterator"); |
| } |
| } |
| |
| void makeNext() { |
| checkConcurrentMod(); |
| if (!checkHasNext()) { |
| throw decaf::util::NoSuchElementException( |
| __FILE__, __LINE__, "No next element"); |
| } |
| currentEntry = futureEntry; |
| futureEntry = futureEntry->chainForward; |
| } |
| }; |
| |
| class ConstEntryIterator : public Iterator< MapEntry<K,V> >, public ConstAbstractMapIterator { |
| private: |
| |
| ConstEntryIterator(const ConstEntryIterator&); |
| ConstEntryIterator& operator= (const ConstEntryIterator&); |
| |
| public: |
| |
| ConstEntryIterator(const LinkedHashMap* parent) : ConstAbstractMapIterator(parent) { |
| } |
| |
| virtual ~ConstEntryIterator() {} |
| |
| virtual bool hasNext() const { |
| return this->checkHasNext(); |
| } |
| |
| virtual MapEntry<K, V> next() { |
| this->makeNext(); |
| return *(this->currentEntry); |
| } |
| |
| virtual void remove() { |
| throw lang::exceptions::UnsupportedOperationException( |
| __FILE__, __LINE__, "Cannot write to a const Iterator." ); |
| } |
| }; |
| |
| class ConstKeyIterator : public Iterator<K>, public ConstAbstractMapIterator { |
| private: |
| |
| ConstKeyIterator(const ConstKeyIterator&); |
| ConstKeyIterator& operator= (const ConstKeyIterator&); |
| |
| public: |
| |
| ConstKeyIterator(const LinkedHashMap* parent) : ConstAbstractMapIterator(parent) { |
| } |
| |
| virtual ~ConstKeyIterator() {} |
| |
| virtual bool hasNext() const { |
| return this->checkHasNext(); |
| } |
| |
| virtual K next() { |
| this->makeNext(); |
| return this->currentEntry->getKey(); |
| } |
| |
| virtual void remove() { |
| throw lang::exceptions::UnsupportedOperationException( |
| __FILE__, __LINE__, "Cannot write to a const Iterator." ); |
| } |
| }; |
| |
| class ConstValueIterator : public Iterator<V>, public ConstAbstractMapIterator { |
| private: |
| |
| ConstValueIterator(const ConstValueIterator&); |
| ConstValueIterator& operator= (const ConstValueIterator&); |
| |
| public: |
| |
| ConstValueIterator(const LinkedHashMap* parent) : ConstAbstractMapIterator(parent) { |
| } |
| |
| virtual ~ConstValueIterator() {} |
| |
| virtual bool hasNext() const { |
| return this->checkHasNext(); |
| } |
| |
| virtual V next() { |
| this->makeNext(); |
| return this->currentEntry->getValue(); |
| } |
| |
| virtual void remove() { |
| throw lang::exceptions::UnsupportedOperationException( |
| __FILE__, __LINE__, "Cannot write to a const Iterator." ); |
| } |
| }; |
| |
| private: |
| |
| // Special Set implementation that is backed by this HashMap |
| class LinkedHashMapEntrySet : public HashMap<K, V, HASHCODE>::HashMapEntrySet { |
| private: |
| |
| LinkedHashMap* associatedMap; |
| |
| private: |
| |
| LinkedHashMapEntrySet(const LinkedHashMapEntrySet&); |
| LinkedHashMapEntrySet& operator= (const LinkedHashMapEntrySet&); |
| |
| public: |
| |
| LinkedHashMapEntrySet(LinkedHashMap* parent) : |
| HashMap<K, V, HASHCODE>::HashMapEntrySet(parent), associatedMap(parent) { |
| } |
| |
| virtual ~LinkedHashMapEntrySet() {} |
| |
| virtual Iterator< MapEntry<K, V> >* iterator() { |
| return new EntryIterator(associatedMap); |
| } |
| |
| virtual Iterator< MapEntry<K, V> >* iterator() const { |
| return new ConstEntryIterator(associatedMap); |
| } |
| }; |
| |
| // Special Set implementation that is backed by this HashMap |
| class ConstLinkedHashMapEntrySet : public HashMap<K, V, HASHCODE>::ConstHashMapEntrySet { |
| private: |
| |
| const LinkedHashMap* associatedMap; |
| |
| private: |
| |
| ConstLinkedHashMapEntrySet(const ConstLinkedHashMapEntrySet&); |
| ConstLinkedHashMapEntrySet& operator= (const ConstLinkedHashMapEntrySet&); |
| |
| public: |
| |
| ConstLinkedHashMapEntrySet(const LinkedHashMap* parent) : |
| HashMap<K, V, HASHCODE>::ConstHashMapEntrySet(parent), associatedMap(parent) { |
| } |
| |
| virtual ~ConstLinkedHashMapEntrySet() {} |
| |
| virtual Iterator< MapEntry<K, V> >* iterator() { |
| throw decaf::lang::exceptions::UnsupportedOperationException( |
| __FILE__, __LINE__, "Can't return a non-const iterator for a const collection"); |
| } |
| |
| virtual Iterator< MapEntry<K, V> >* iterator() const { |
| return new ConstEntryIterator(associatedMap); |
| } |
| }; |
| |
| private: |
| |
| class LinkedHashMapKeySet : public HashMap<K, V, HASHCODE>::HashMapKeySet { |
| private: |
| |
| LinkedHashMap* associatedMap; |
| |
| private: |
| |
| LinkedHashMapKeySet(const LinkedHashMapKeySet&); |
| LinkedHashMapKeySet& operator= (const LinkedHashMapKeySet&); |
| |
| public: |
| |
| LinkedHashMapKeySet(LinkedHashMap* parent) : |
| HashMap<K, V, HASHCODE>::HashMapKeySet(parent), associatedMap(parent) { |
| } |
| |
| virtual ~LinkedHashMapKeySet() {} |
| |
| virtual Iterator<K>* iterator() { |
| return new KeyIterator(this->associatedMap); |
| } |
| |
| virtual Iterator<K>* iterator() const { |
| return new ConstKeyIterator(this->associatedMap); |
| } |
| }; |
| |
| class ConstLinkedHashMapKeySet : public HashMap<K, V, HASHCODE>::ConstHashMapKeySet { |
| private: |
| |
| const LinkedHashMap* associatedMap; |
| |
| private: |
| |
| ConstLinkedHashMapKeySet(const ConstLinkedHashMapKeySet&); |
| ConstLinkedHashMapKeySet& operator= (const ConstLinkedHashMapKeySet&); |
| |
| public: |
| |
| ConstLinkedHashMapKeySet(const LinkedHashMap* parent) : |
| HashMap<K, V, HASHCODE>::ConstHashMapKeySet(parent), associatedMap(parent) { |
| } |
| |
| virtual ~ConstLinkedHashMapKeySet() {} |
| |
| using HashMap<K, V, HASHCODE>::ConstHashMapKeySet::iterator; |
| |
| virtual Iterator<K>* iterator() const { |
| return new ConstKeyIterator(this->associatedMap); |
| } |
| }; |
| |
| private: |
| |
| class LinkedHashMapValueCollection : public HashMap<K, V, HASHCODE>::HashMapValueCollection { |
| private: |
| |
| LinkedHashMap* associatedMap; |
| |
| private: |
| |
| LinkedHashMapValueCollection(const LinkedHashMapValueCollection&); |
| LinkedHashMapValueCollection& operator= (const LinkedHashMapValueCollection&); |
| |
| public: |
| |
| LinkedHashMapValueCollection(LinkedHashMap* parent) : |
| HashMap<K, V, HASHCODE>::HashMapValueCollection(parent), associatedMap(parent) { |
| } |
| |
| virtual ~LinkedHashMapValueCollection() {} |
| |
| virtual Iterator<V>* iterator() { |
| return new ValueIterator(this->associatedMap); |
| } |
| |
| virtual Iterator<V>* iterator() const { |
| return new ConstValueIterator(this->associatedMap); |
| } |
| }; |
| |
| class ConstLinkedHashMapValueCollection : public HashMap<K, V, HASHCODE>::ConstHashMapValueCollection { |
| private: |
| |
| const LinkedHashMap* associatedMap; |
| |
| private: |
| |
| ConstLinkedHashMapValueCollection(const ConstLinkedHashMapValueCollection&); |
| ConstLinkedHashMapValueCollection& operator= (const ConstLinkedHashMapValueCollection&); |
| |
| public: |
| |
| ConstLinkedHashMapValueCollection(const LinkedHashMap* parent) : |
| HashMap<K, V, HASHCODE>::ConstHashMapValueCollection(parent), associatedMap(parent) { |
| } |
| |
| virtual ~ConstLinkedHashMapValueCollection() {} |
| |
| virtual Iterator<V>* iterator() const { |
| return new ConstValueIterator(this->associatedMap); |
| } |
| |
| using HashMap<K, V, HASHCODE>::ConstHashMapValueCollection::iterator; |
| }; |
| |
| public: |
| |
| /** |
| * Constructs an empty insertion-ordered LinkedHashMap instance with the default |
| * initial capacity (16) and load factor (0.75). |
| */ |
| LinkedHashMap() : HashMap<K, V, HASHCODE>(), accessOrder(false), head(), tail() { |
| } |
| |
| /** |
| * Constructs a new LinkedHashMap instance with the specified capacity. |
| * |
| * @param capacity |
| * The initial capacity of this map. |
| * |
| * @throws IllegalArgumentException if the capacity is less than zero. |
| */ |
| LinkedHashMap(int capacity) : HashMap<K, V, HASHCODE>(capacity), accessOrder(false), head(), tail() { |
| } |
| |
| /** |
| * Constructs a new {@code LinkedHashMap} instance with the specified |
| * capacity and load factor. |
| * |
| * @param capacity |
| * The initial capacity of this map. |
| * @param load |
| * The initial load factor for this map. |
| * |
| * @throws IllegalArgumentException |
| * If the capacity is less than zero or the load factor is less or equal to zero. |
| */ |
| LinkedHashMap(int capacity, float load) : |
| HashMap<K, V, HASHCODE>(capacity, load), accessOrder(false), head(), tail() { |
| |
| } |
| |
| /** |
| * Constructs a new {@code LinkedHashMap} instance with the specified |
| * capacity, load factor and a flag specifying the ordering behavior. |
| * |
| * @param capacity |
| * The initial capacity of this map. |
| * @param load |
| * The initial load factor for this map. |
| * @param order |
| * True if the ordering should be done based on the last access (from |
| * least-recently accessed to most-recently accessed), and false if |
| * the ordering should be the order in which the entries were inserted. |
| * |
| * @throws IllegalArgumentException |
| * If the capacity is less than zero or the load factor is less or equal to zero. |
| */ |
| LinkedHashMap(int capacity, float load, bool order) : |
| HashMap<K, V, HASHCODE>(capacity, load), accessOrder(order), head(), tail() { |
| } |
| |
| /** |
| * Constructs a new LinkedHashMap instance containing the mappings |
| * from the specified map. The order of the elements is preserved. |
| * |
| * @param map |
| * The mappings to add to this Map instance. |
| */ |
| LinkedHashMap(const HashMap<K,V>& map) : HashMap<K, V, HASHCODE>(map), accessOrder(false), head(), tail() { |
| } |
| |
| virtual ~LinkedHashMap() {} |
| |
| protected: |
| |
| /** |
| * This method is queried from the put and putAll methods to check if the |
| * eldest member of the map should be deleted before adding the new member. |
| * If this map was created with accessOrder = true, then the result of |
| * removeEldestEntry is assumed to be false. |
| * |
| * @param eldest |
| * The entry to check if it should be removed. |
| * |
| * @return true if the eldest member should be removed. |
| */ |
| virtual bool removeEldestEntry(const MapEntry<K, V>& eldest DECAF_UNUSED) { |
| return false; |
| } |
| |
| /** |
| * This method is called when the removeEldestEntry has returned true and a |
| * MapEntry is about to be removed from the Map. This method allows for Maps |
| * that contain pointers in their MapEntry object to have a chance to properly |
| * delete the pointer when the entry is removed. |
| * |
| * @param eldest |
| * The MapEntry value that is about to be removed from the Map. |
| */ |
| virtual void onEviction(const MapEntry<K, V>& eldest DECAF_UNUSED) {} |
| |
| public: |
| |
| virtual bool containsValue(const V& value) const { |
| LinkedHashMapEntry* entry = head; |
| while (entry != NULL) { |
| if (value == entry->getValue()) { |
| return true; |
| } |
| entry = entry->chainForward; |
| } |
| return false; |
| } |
| |
| virtual void clear() { |
| HashMap<K, V, HASHCODE>::clear(); |
| this->head = NULL; |
| this->tail = NULL; |
| } |
| |
| virtual bool put(const K& key, const V& value) { |
| bool result = this->putImpl(key, value); |
| |
| if (this->removeEldestEntry(*head)) { |
| this->onEviction(*head); |
| this->remove(head->getKey()); |
| } |
| |
| return result; |
| } |
| |
| virtual bool put(const K& key, const V& value, V& oldValue) { |
| bool result = this->putImpl(key, value, oldValue); |
| |
| if (this->removeEldestEntry(*head)) { |
| this->onEviction(*head); |
| this->remove(head->getKey()); |
| } |
| |
| return result; |
| } |
| |
| virtual V remove(const K& key) { |
| |
| LinkedHashMapEntry* toRemove = (LinkedHashMapEntry*) this->removeEntry(key); |
| if (toRemove != NULL) { |
| LinkedHashMapEntry* prev = toRemove->chainBackward; |
| LinkedHashMapEntry* next = toRemove->chainForward; |
| if (prev != NULL) { |
| prev->chainForward = next; |
| } else { |
| head = next; |
| } |
| if (next != NULL) { |
| next->chainBackward = prev; |
| } else { |
| tail = prev; |
| } |
| |
| V oldValue = toRemove->getValue(); |
| delete toRemove; |
| return oldValue; |
| } |
| |
| throw NoSuchElementException( |
| __FILE__, __LINE__, "Specified key not present in the Map."); |
| } |
| |
| virtual Set< MapEntry<K,V> >& entrySet() { |
| if (this->cachedEntrySet == NULL) { |
| this->cachedEntrySet.reset(new LinkedHashMapEntrySet(this)); |
| } |
| return *(this->cachedEntrySet); |
| } |
| |
| virtual const Set< MapEntry<K,V> >& entrySet() const { |
| if (this->cachedConstEntrySet == NULL) { |
| this->cachedConstEntrySet.reset(new ConstLinkedHashMapEntrySet(this)); |
| } |
| return *(this->cachedConstEntrySet); |
| } |
| |
| virtual Set<K>& keySet() { |
| if (this->cachedKeySet == NULL) { |
| this->cachedKeySet.reset(new LinkedHashMapKeySet(this)); |
| } |
| return *(this->cachedKeySet); |
| } |
| |
| virtual const Set<K>& keySet() const { |
| if (this->cachedConstKeySet == NULL) { |
| this->cachedConstKeySet.reset(new ConstLinkedHashMapKeySet(this)); |
| } |
| return *(this->cachedConstKeySet); |
| } |
| |
| virtual Collection<V>& values() { |
| if (this->cachedValueCollection == NULL) { |
| this->cachedValueCollection.reset(new LinkedHashMapValueCollection(this)); |
| } |
| return *(this->cachedValueCollection); |
| } |
| |
| virtual const Collection<V>& values() const { |
| if (this->cachedConstValueCollection == NULL) { |
| this->cachedConstValueCollection.reset(new ConstLinkedHashMapValueCollection(this)); |
| } |
| return *(this->cachedConstValueCollection); |
| } |
| |
| virtual std::string toString() const { |
| return "LinkedHashMap"; |
| } |
| |
| protected: |
| |
| virtual LinkedHashMapEntry* getEntry(const K& key) const { |
| LinkedHashMapEntry* result = NULL; |
| |
| int hash = this->hashFunc(key); |
| int index = hash & (this->elementData.length() - 1); |
| result = (LinkedHashMapEntry*) this->findKeyEntry(key, index, hash); |
| |
| if (result != NULL && accessOrder && tail != result) { |
| LinkedHashMapEntry* prev = result->chainBackward; |
| LinkedHashMapEntry* next = result->chainForward; |
| next->chainBackward = prev; |
| if (prev != NULL) { |
| prev->chainForward = next; |
| } else { |
| head = next; |
| } |
| result->chainForward = NULL; |
| result->chainBackward = tail; |
| tail->chainForward = result; |
| tail = result; |
| } |
| |
| return result; |
| } |
| |
| virtual typename HashMap<K, V, HASHCODE>::HashMapEntry* createEntry(const K& key, int index, const V& value) { |
| LinkedHashMapEntry* entry = new LinkedHashMapEntry(key, value); |
| entry->next = this->elementData[index]; |
| this->elementData[index] = entry; |
| linkEntry(entry); |
| return entry; |
| } |
| |
| virtual typename HashMap<K, V, HASHCODE>::HashMapEntry* createHashedEntry(const K& key, int index, int hash) { |
| LinkedHashMapEntry* entry = new LinkedHashMapEntry(key, V(), hash); |
| entry->next = this->elementData[index]; |
| this->elementData[index] = entry; |
| linkEntry(entry); |
| return entry; |
| } |
| |
| void linkEntry(LinkedHashMapEntry* entry) { |
| if (tail == entry) { |
| return; |
| } |
| |
| if (head == NULL) { |
| // Check if the map is empty |
| head = tail = entry; |
| return; |
| } |
| |
| // we need to link the new entry into either the head or tail |
| // of the chain depending on if the LinkedHashMap is accessOrder or not |
| LinkedHashMapEntry* prev = entry->chainBackward; |
| LinkedHashMapEntry* next = entry->chainForward; |
| if (prev == NULL) { |
| if (next != NULL) { |
| // The entry must be the head but not the tail |
| if (accessOrder) { |
| head = next; |
| next->chainBackward = NULL; |
| entry->chainBackward = tail; |
| entry->chainForward = NULL; |
| tail->chainForward = entry; |
| tail = entry; |
| } |
| } else { |
| // This is a new entry |
| entry->chainBackward = tail; |
| entry->chainForward = NULL; |
| tail->chainForward = entry; |
| tail = entry; |
| } |
| return; |
| } |
| |
| if (next == NULL) { |
| // The entry must be the tail so we can't get here |
| return; |
| } |
| |
| // The entry is neither the head nor tail |
| if (accessOrder) { |
| prev->chainForward = next; |
| next->chainBackward = prev; |
| entry->chainForward = NULL; |
| entry->chainBackward = tail; |
| tail->chainForward = entry; |
| tail = entry; |
| } |
| } |
| |
| virtual bool putImpl(const K& key, const V& value) { |
| V oldValue; |
| return putImpl(key, value, oldValue); |
| } |
| |
| virtual bool putImpl(const K& key, const V& value, V& oldValue) { |
| |
| LinkedHashMapEntry* entry; |
| if (this->elementCount == 0) { |
| head = tail = NULL; |
| } |
| |
| bool replaced = true; |
| int hash = this->hashFunc(key); |
| int index = hash & (this->elementData.length() - 1); |
| |
| entry = (LinkedHashMapEntry*) this->findKeyEntry(key, index, hash); |
| if (entry == NULL) { |
| this->modCount++; |
| if (++this->elementCount > this->threshold) { |
| this->rehash(); |
| index = hash & (this->elementData.length() - 1); |
| } |
| entry = (LinkedHashMapEntry*) this->createHashedEntry(key, index, hash); |
| replaced = false; |
| } else { |
| this->linkEntry(entry); |
| oldValue = entry->getValue(); |
| } |
| |
| entry->setValue(value); |
| return replaced; |
| } |
| |
| }; |
| |
| }} |
| |
| #endif /* _DECAF_UTIL_LINKEDHASHMAP_H_ */ |