You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@activemq.apache.org by ta...@apache.org on 2013/03/21 23:49:15 UTC
svn commit: r1459566 [1/3] - in
/activemq/activemq-cpp/trunk/activemq-cpp/src: main/ main/decaf/util/ test/
test/decaf/util/
Author: tabish
Date: Thu Mar 21 22:49:14 2013
New Revision: 1459566
URL: http://svn.apache.org/r1459566
Log:
Adds
LinkedHashMap
LinkedHashSet
LRUCache
Adds additional test cases.
Added:
activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.cpp (with props)
activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.h (with props)
activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.cpp (with props)
activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.h (with props)
activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LinkedHashMapTest.cpp (with props)
activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LinkedHashMapTest.h (with props)
activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LinkedHashSetTest.cpp (with props)
activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LinkedHashSetTest.h (with props)
Modified:
activemq/activemq-cpp/trunk/activemq-cpp/src/main/Makefile.am
activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashMap.h
activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashSet.h
activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LRUCache.h
activemq/activemq-cpp/trunk/activemq-cpp/src/test/Makefile.am
activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.cpp
activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.h
activemq/activemq-cpp/trunk/activemq-cpp/src/test/testRegistry.cpp
Modified: activemq/activemq-cpp/trunk/activemq-cpp/src/main/Makefile.am
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/Makefile.am?rev=1459566&r1=1459565&r2=1459566&view=diff
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/Makefile.am (original)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/Makefile.am Thu Mar 21 22:49:14 2013
@@ -553,6 +553,8 @@ cc_sources = \
decaf/util/HashSet.cpp \
decaf/util/Iterator.cpp \
decaf/util/LRUCache.cpp \
+ decaf/util/LinkedHashMap.cpp \
+ decaf/util/LinkedHashSet.cpp \
decaf/util/LinkedList.cpp \
decaf/util/List.cpp \
decaf/util/ListIterator.cpp \
@@ -1202,6 +1204,8 @@ h_sources = \
decaf/util/HashSet.h \
decaf/util/Iterator.h \
decaf/util/LRUCache.h \
+ decaf/util/LinkedHashMap.h \
+ decaf/util/LinkedHashSet.h \
decaf/util/LinkedList.h \
decaf/util/List.h \
decaf/util/ListIterator.h \
Modified: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashMap.h
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashMap.h?rev=1459566&r1=1459565&r2=1459566&view=diff
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashMap.h (original)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashMap.h Thu Mar 21 22:49:14 2013
@@ -93,7 +93,7 @@ namespace util {
*/
template<typename K, typename V, typename HASHCODE = HashCode<K> >
class HashMap : public AbstractMap<K, V> {
- private:
+ protected:
class HashMapEntry : public MapEntry<K, V> {
private:
@@ -452,7 +452,7 @@ namespace util {
}
};
- private:
+ protected:
// Special Set implementation that is backed by this HashMap
class HashMapEntrySet : public AbstractSet< MapEntry<K, V> > {
@@ -557,7 +557,7 @@ namespace util {
}
};
- private:
+ protected:
class HashMapKeySet : public AbstractSet<K> {
private:
@@ -651,7 +651,7 @@ namespace util {
}
};
- private:
+ protected:
class HashMapValueCollection : public AbstractCollection<V> {
private:
@@ -731,7 +731,7 @@ namespace util {
}
};
- private:
+ protected:
/**
* The Hash Code generator for this map's keys.
@@ -1089,7 +1089,7 @@ namespace util {
protected:
- HashMapEntry* getEntry(const K& key) const {
+ virtual HashMapEntry* getEntry(const K& key) const {
HashMapEntry* result = NULL;
int hash = hashFunc(key);
@@ -1099,7 +1099,12 @@ namespace util {
return result;
}
- bool putImpl(const K& key, const V& value, V& oldValue) {
+ 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) {
bool replaced = true;
HashMapEntry* entry = NULL;
@@ -1124,30 +1129,22 @@ namespace util {
return replaced;
}
- bool putImpl(const K& key, const V& value) {
-
- bool replaced = true;
- HashMapEntry* entry = NULL;
-
- int hash = hashFunc(key);
- int index = hash & (elementData.length() - 1);
-
- entry = findKeyEntry(key, index, hash);
-
- if (entry == NULL) {
- modCount++;
- entry = createHashedEntry(key, index, hash);
- if (++elementCount > threshold) {
- rehash();
- }
- replaced = false;
- }
-
- entry->setValue(value);
+ virtual HashMapEntry* createEntry(const K& key, int index, const V& value) {
+ HashMapEntry* entry = new HashMapEntry(key, value);
+ entry->next = elementData[index];
+ elementData[index] = entry;
+ return entry;
+ }
- return replaced;
+ virtual HashMapEntry* createHashedEntry(const K& key, int index, int hash) {
+ HashMapEntry* entry = new HashMapEntry(key, V(), hash);
+ entry->next = elementData[index];
+ elementData[index] = entry;
+ return entry;
}
+ protected:
+
void putAllImpl(const Map<K, V>& map) {
int capacity = elementCount + map.size();
if (capacity > threshold) {
@@ -1192,20 +1189,6 @@ namespace util {
rehash(elementData.length());
}
- HashMapEntry* createEntry(const K& key, int index, const V& value) {
- HashMapEntry* entry = new HashMapEntry(key, value);
- entry->next = elementData[index];
- elementData[index] = entry;
- return entry;
- }
-
- HashMapEntry* createHashedEntry(const K& key, int index, int hash) {
- HashMapEntry* entry = new HashMapEntry(key, V(), hash);
- entry->next = elementData[index];
- elementData[index] = entry;
- return entry;
- }
-
// Removes the given entry from the map and deletes it
void removeEntry(HashMapEntry* entry) {
int index = entry->origKeyHash & (elementData.length() - 1);
Modified: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashSet.h
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashSet.h?rev=1459566&r1=1459565&r2=1459566&view=diff
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashSet.h (original)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/HashSet.h Thu Mar 21 22:49:14 2013
@@ -131,6 +131,19 @@ namespace util {
DECAF_CATCHALL_NOTHROW()
}
+ protected:
+
+ /**
+ * Protected constructor for use by subclasses that wish to use an alternate type
+ * of backing Map.
+ *
+ * @param backingMap
+ * The instance of the Map type used to back this HashSet.
+ */
+ HashSet(HashMap<E, Set<E>*, HASHCODE>* backingMap) :
+ AbstractSet<E>(), backingMap(backingMap) {
+ }
+
public:
HashSet<E>& operator= (const Collection<E>& collection) {
Modified: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LRUCache.h
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LRUCache.h?rev=1459566&r1=1459565&r2=1459566&view=diff
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LRUCache.h (original)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LRUCache.h Thu Mar 21 22:49:14 2013
@@ -20,7 +20,7 @@
#include <decaf/util/Config.h>
-#include <decaf/util/AbstractMap.h>
+#include <decaf/util/LinkedHashMap.h>
#include <decaf/lang/exceptions/IllegalArgumentException.h>
namespace decaf {
@@ -29,17 +29,69 @@ namespace util {
/**
* A Basic Least Recently Used (LRU) Cache Map.
*
+ * This LRUCache implements the LinkedHashMap class so all the standard Map
+ * operations are provided. When the sive of this LRUCache map exceeds the
+ * specified maxCacheSize value then by default the oldest entry is evicted
+ * from the Cache.
+ *
+ * Subclasses can override the LinkedHashMap::onEviction method to perform
+ * custom cache eviction processing.
+ *
* @since 1.0
*/
- template<typename K, typename V, typename COMPARATOR = std::less<K> >
- class LRUCache : decaf::util::AbstractMap<K, V> {
+ template<typename K, typename V, typename HASHCODE = HashCode<K> >
+ class LRUCache : public LinkedHashMap<K, V, HASHCODE> {
protected:
int maxCacheSize;
public:
- LRUCache() : maxCacheSize(1024) {}
+
+ /**
+ * Default constructor for an LRU Cache The default capacity is 10000
+ */
+ LRUCache() : LinkedHashMap<K, V, HASHCODE>(0, 0.75f, true), maxCacheSize(10000) {}
+
+ /**
+ * Constructs a LRUCache with a maximum capacity
+ *
+ * @param maximumCacheSize
+ * The maximum number of cached entries before eviction begins.
+ */
+ LRUCache(int maximumCacheSize) :
+ LinkedHashMap<K, V, HASHCODE>(0, 0.75f, true), maxCacheSize(maximumCacheSize) {
+
+ if (maximumCacheSize <= 0) {
+ throw decaf::lang::exceptions::IllegalArgumentException(
+ __FILE__, __LINE__, "Cache size must be greater than zero.");
+ }
+ }
+
+ /**
+ * Constructs an empty LRUCache instance with the specified initial capacity,
+ * maximumCacheSize, load factor and ordering mode.
+ *
+ * @param initialCapacity
+ * The initial capacity of the LRUCache.
+ * @param maximumCacheSize
+ * The maximum number of cached entries before eviction begins.
+ * @param loadFactor the load factor.
+ * The initial load factor for this LRUCache.
+ * @param accessOrder
+ * The ordering mode - true for access-order, false for insertion-order.
+ *
+ * @throws IllegalArgumentException if the initial capacity is negative or
+ * the load factor is non-positive.
+ */
+ LRUCache(int initialCapacity, int maximumCacheSize, float loadFactor, bool accessOrder) :
+ LinkedHashMap<K, V, HASHCODE>(initialCapacity, loadFactor, accessOrder), maxCacheSize(maximumCacheSize) {
+
+ if (maximumCacheSize <= 0) {
+ throw decaf::lang::exceptions::IllegalArgumentException(
+ __FILE__, __LINE__, "Cache size must be greater than zero.");
+ }
+ }
virtual ~LRUCache() {}
@@ -71,7 +123,10 @@ namespace util {
protected:
- virtual bool removeEldestEntry(const typename Map<K,V>::Entry & entry) {
+ virtual bool removeEldestEntry(const MapEntry<K, V>& eldest) {
+ if (this->size() > maxCacheSize) {
+ return true;
+ }
return false;
}
Added: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.cpp
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.cpp?rev=1459566&view=auto
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.cpp (added)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.cpp Thu Mar 21 22:49:14 2013
@@ -0,0 +1,18 @@
+/*
+ * 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.
+ */
+
+#include "LinkedHashMap.h"
Propchange: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.cpp
------------------------------------------------------------------------------
svn:eol-style = native
Added: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.h
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.h?rev=1459566&view=auto
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.h (added)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.h Thu Mar 21 22:49:14 2013
@@ -0,0 +1,942 @@
+/*
+ * 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() {}
+
+ 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);
+ }
+ };
+
+ 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) {
+ 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) {}
+
+ 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_ */
Propchange: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashMap.h
------------------------------------------------------------------------------
svn:eol-style = native
Added: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.cpp
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.cpp?rev=1459566&view=auto
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.cpp (added)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.cpp Thu Mar 21 22:49:14 2013
@@ -0,0 +1,18 @@
+/*
+ * 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.
+ */
+
+#include "LinkedHashSet.h"
Propchange: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.cpp
------------------------------------------------------------------------------
svn:eol-style = native
Added: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.h
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.h?rev=1459566&view=auto
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.h (added)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.h Thu Mar 21 22:49:14 2013
@@ -0,0 +1,153 @@
+/*
+ * 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_LINKEDHASHSET_H_
+#define _DECAF_UTIL_LINKEDHASHSET_H_
+
+#include <decaf/util/Config.h>
+
+#include <decaf/util/LinkedHashMap.h>
+#include <decaf/util/HashSet.h>
+#include <decaf/util/ConcurrentModificationException.h>
+#include <decaf/lang/exceptions/UnsupportedOperationException.h>
+
+namespace decaf {
+namespace util {
+
+ /**
+ * Hash table and linked list implementation of the Set interface, with predictable iteration
+ * order. This implementation differs from HashSet in that it maintains a doubly-linked list
+ * running through all of its entries. This linked list defines the iteration ordering, which
+ * is the order in which elements were inserted into the set (insertion-order). Note that
+ * insertion order is not affected if an element is re-inserted into the set. (An element e
+ * is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true
+ * immediately prior to the invocation.)
+ *
+ * This implementation spares its clients from the unspecified, generally chaotic ordering
+ * provided by HashSet, without incurring the increased cost associated with TreeSet. It
+ * can be used to produce a copy of a set that has the same order as the original, regardless
+ * of the original set's implementation:
+ *
+ * void foo(const Set<E& s) {
+ * Set<E>* copy = new LinkedHashSet<E>(s);
+ * ...
+ * }
+ *
+ * This technique is particularly useful if a module takes a set 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.)
+ *
+ * This class provides all of the optional Set operations, and permits null elements. Like
+ * HashSet, 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 HashSet, due to the added expense
+ * of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires
+ * time proportional to the size of the set, regardless of its capacity. Iteration over a
+ * HashSet is likely to be more expensive, requiring time proportional to its capacity.
+ *
+ * A linked hash set has two parameters that affect its performance: initial capacity and load
+ * factor. They are defined precisely as for HashSet. Note, however, that the penalty for
+ * choosing an excessively high value for initial capacity is less severe for this class than
+ * for HashSet, as iteration times for this class are unaffected by capacity.
+ *
+ * Note that this implementation is not synchronized. If multiple threads access a linked hash
+ * set concurrently, and at least one of the threads modifies the set, it must be synchronized
+ * externally. This is typically accomplished by synchronizing on some object that naturally
+ * encapsulates the set. If no such object exists, the set should be "wrapped" using the
+ * Collections.synchronizedSet method. This is best done at creation time, to prevent accidental
+ * unsynchronized access to the set:
+ *
+ * Set<E>* s = Collections::synchronizedSet(new LinkedHashSet<E>(...));
+ *
+ * The iterators returned by this class's iterator method are fail-fast: if the set is 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 E, typename HASHCODE = HashCode<E> >
+ class LinkedHashSet : public HashSet<E, HASHCODE> {
+ public:
+
+ /**
+ * Constructs a new, empty set; the backing HashMap instance has default initial
+ * capacity (16) and load factor (0.75).
+ */
+ LinkedHashSet() : HashSet<E, HASHCODE>(new LinkedHashMap<E, Set<E>*, HASHCODE>()) {
+ }
+
+ /**
+ * Constructs a new, empty set; the backing HashMap instance has the specified initial
+ * capacity and default load factor (0.75).
+ *
+ * @param capacity
+ * The initial capacity of this LinkedHashSet.
+ */
+ LinkedHashSet(int capacity) : HashSet<E, HASHCODE>(new LinkedHashMap<E, Set<E>*, HASHCODE>(capacity)) {
+ }
+
+ /**
+ * Constructs a new instance of {@code HashSet} with the specified capacity
+ * and load factor.
+ *
+ * @param capacity
+ * The initial capacity for this LinkedHashSet.
+ * @param loadFactor
+ * The initial load factor for this LinkedHashSet.
+ */
+ LinkedHashSet(int capacity, float loadFactor) :
+ HashSet<E, HASHCODE>(new LinkedHashMap<E, Set<E>*, HASHCODE>(capacity, loadFactor)) {
+ }
+
+ /**
+ * Constructs a new set containing the elements in the specified collection.
+ *
+ * The HashMap is created with default load factor (0.75) and an initial capacity
+ * sufficient to contain the elements in the specified collection.
+ *
+ * @param collection
+ * The collection of elements to add to this LinkedHashSet.
+ */
+ LinkedHashSet(const Collection<E>& collection) :
+ HashSet<E, HASHCODE>(new LinkedHashMap<E, Set<E>*, HASHCODE>(
+ (collection.size() < 6 ? 11 : collection.size() * 2))) {
+
+ decaf::lang::Pointer<Iterator<E> > iter(collection.iterator());
+ while (iter->hasNext()) {
+ this->add(iter->next());
+ }
+ }
+
+ virtual ~LinkedHashSet() {
+ }
+
+ virtual std::string toString() const {
+ return "LinkedHashSet";
+ }
+ };
+
+}}
+
+#endif /* _DECAF_UTIL_LINKEDHASHSET_H_ */
Propchange: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/LinkedHashSet.h
------------------------------------------------------------------------------
svn:eol-style = native
Modified: activemq/activemq-cpp/trunk/activemq-cpp/src/test/Makefile.am
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/test/Makefile.am?rev=1459566&r1=1459565&r2=1459566&view=diff
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/test/Makefile.am (original)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/test/Makefile.am Thu Mar 21 22:49:14 2013
@@ -206,6 +206,8 @@ cc_sources = \
decaf/util/HashMapTest.cpp \
decaf/util/HashSetTest.cpp \
decaf/util/LRUCacheTest.cpp \
+ decaf/util/LinkedHashMapTest.cpp \
+ decaf/util/LinkedHashSetTest.cpp \
decaf/util/LinkedListTest.cpp \
decaf/util/ListTest.cpp \
decaf/util/PriorityQueueTest.cpp \
@@ -451,6 +453,8 @@ h_sources = \
decaf/util/HashMapTest.h \
decaf/util/HashSetTest.h \
decaf/util/LRUCacheTest.h \
+ decaf/util/LinkedHashMapTest.h \
+ decaf/util/LinkedHashSetTest.h \
decaf/util/LinkedListTest.h \
decaf/util/ListTest.h \
decaf/util/PriorityQueueTest.h \
Modified: activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.cpp
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.cpp?rev=1459566&r1=1459565&r2=1459566&view=diff
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.cpp (original)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.cpp Thu Mar 21 22:49:14 2013
@@ -18,12 +18,15 @@
#include "LRUCacheTest.h"
#include <decaf/util/LRUCache.h>
+#include <decaf/lang/System.h>
#include <string>
using namespace std;
using namespace decaf;
using namespace decaf::util;
+using namespace decaf::lang;
+using namespace decaf::lang::exceptions;
////////////////////////////////////////////////////////////////////////////////
LRUCacheTest::LRUCacheTest() {
@@ -36,5 +39,52 @@ LRUCacheTest::~LRUCacheTest() {
////////////////////////////////////////////////////////////////////////////////
void LRUCacheTest::testConstructor() {
- //LRUCache<string, string> lruCache;
+ LRUCache<int, int> underTest(1000);
+
+ for (int count; count < 5000; count++) {
+ if (!underTest.containsKey(count)) {
+ underTest.put(count, count);
+ }
+ }
+ CPPUNIT_ASSERT_EQUAL_MESSAGE("size is still in order", 1000, underTest.size());
+}
+
+////////////////////////////////////////////////////////////////////////////////
+void LRUCacheTest::testExceptions() {
+
+ try {
+ LRUCache<int, int> underTest(-1);
+ CPPUNIT_FAIL("Should have thrown an IllegalArgumentException");
+ } catch(IllegalArgumentException& ex) {}
+
+ LRUCache<int, int> underTest(1000);
+
+ CPPUNIT_ASSERT_THROW_MESSAGE(
+ "Should throw an IllegalArgumentException",
+ underTest.setMaxCacheSize(-1),
+ IllegalArgumentException );
+}
+
+////////////////////////////////////////////////////////////////////////////////
+void LRUCacheTest::testChangeMaxCacheSize() {
+
+ LRUCache<int, int> underTest(1000);
+
+ for (int count = 0; count < 5000; count++) {
+ if (!underTest.containsKey(count)) {
+ underTest.put(count, count);
+ }
+ }
+
+ CPPUNIT_ASSERT_EQUAL_MESSAGE("size is still in order", 1000, underTest.size());
+ underTest.setMaxCacheSize(2000);
+
+ for (int count = 0; count < 5000; count++) {
+ if (!underTest.containsKey(count)) {
+ underTest.put(count, count);
+ }
+ }
+
+ CPPUNIT_ASSERT_EQUAL_MESSAGE("size is still in order", 2000, underTest.size());
}
+
Modified: activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.h
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.h?rev=1459566&r1=1459565&r2=1459566&view=diff
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.h (original)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/test/decaf/util/LRUCacheTest.h Thu Mar 21 22:49:14 2013
@@ -24,20 +24,24 @@
namespace decaf {
namespace util {
- class LRUCacheTest : public CppUnit::TestFixture
- {
+ class LRUCacheTest : public CppUnit::TestFixture {
+
CPPUNIT_TEST_SUITE( LRUCacheTest );
CPPUNIT_TEST( testConstructor );
+ CPPUNIT_TEST( testExceptions );
+ CPPUNIT_TEST( testChangeMaxCacheSize );
CPPUNIT_TEST_SUITE_END();
- public:
+ public:
- LRUCacheTest();
- virtual ~LRUCacheTest();
+ LRUCacheTest();
+ virtual ~LRUCacheTest();
- void testConstructor();
+ void testConstructor();
+ void testExceptions();
+ void testChangeMaxCacheSize();
- };
+ };
}}