activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tab...@apache.org
Subject svn commit: r1459566 [1/3] - in /activemq/activemq-cpp/trunk/activemq-cpp/src: main/ main/decaf/util/ test/ test/decaf/util/
Date Thu, 21 Mar 2013 22:49:15 GMT
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();
 
-	};
+    };
 
 }}
 



Mime
View raw message