Added qpid::sys::RefCountedMap: thread safe refcounted map of refcounted entries.

 - Entries are atomically erased when released.
 - Map is released when all entries are erased.


git-svn-id: https://svn.apache.org/repos/asf/incubator/qpid/trunk/qpid@590907 13f79535-47bb-0310-9956-ffa450edef68

5 files changed, 286 insertions, 5 deletions

diff --git a/cpp/src/Makefile.am b/cpp/src/Makefile.am
index 218b7fcd1d..2f1d0b32d4 100644
--- a/cpp/src/Makefile.am
+++ b/cpp/src/Makefile.am
@@ -127,6 +127,7 @@ libqpidcommon_la_SOURCES = \
   qpid/sys/AsynchIOAcceptor.cpp \
   qpid/sys/Dispatcher.cpp \
   qpid/sys/Runnable.cpp \
+  qpid/sys/RefCountedMap.h \
   qpid/sys/Serializer.cpp \
   qpid/sys/Shlib.cpp \
   qpid/Options.cpp \
diff --git a/cpp/src/qpid/RefCounted.h b/cpp/src/qpid/RefCounted.h
index 790076b463..bcef69d21e 100644
--- a/cpp/src/qpid/RefCounted.h
+++ b/cpp/src/qpid/RefCounted.h
@@ -65,8 +65,8 @@ using boost::intrusive_ptr;
 
 // intrusive_ptr support.
 namespace boost {
-void intrusive_ptr_add_ref(const qpid::AbstractRefCounted* p) { p->addRef(); }
-void intrusive_ptr_release(const qpid::AbstractRefCounted* p) { p->release(); }
+inline void intrusive_ptr_add_ref(const qpid::AbstractRefCounted* p) { p->addRef(); }
+inline void intrusive_ptr_release(const qpid::AbstractRefCounted* p) { p->release(); }
 }
 
 
diff --git a/cpp/src/qpid/sys/RefCountedMap.h b/cpp/src/qpid/sys/RefCountedMap.h
new file mode 100644
index 0000000000..6e5f4b80d0
--- /dev/null
+++ b/cpp/src/qpid/sys/RefCountedMap.h
@@ -0,0 +1,171 @@
+#ifndef QPID_SYS_REFCOUNTEDMAP_H
+#define QPID_SYS_REFCOUNTEDMAP_H
+
+/*
+ *
+ * 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 "qpid/sys/Mutex.h"
+#include "qpid/RefCounted.h"
+
+#include <boost/call_traits.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+
+#include <map>
+
+namespace qpid {
+namespace sys {
+
+/**
+ * A thread-safe, RefCounted map of RefCounted entries.  Entries are
+ * automatically erased when all iterators to them are destroyed.  The
+ * entire map is released when all its entries are erased.
+ *
+ * The assumption is that some other object/thread holds an iterator
+ * to each entry for as long as it is useful.
+ *
+ * API is a subset of std::map
+ *
+ * WARNING: Modifying iterators locks the map.  To avoid deadlock, you
+ * MUST NOT modify an iterator while holding another lock that could be
+ * locked as a result of erasing the entry and destroying its value.
+ *
+ */
+
+template <class K, class D>
+class RefCountedMap : public RefCounted
+{
+    typedef Mutex::ScopedLock Lock;
+
+  public:
+    typedef K key_type;
+    typedef D data_type;
+    typedef std::pair<key_type,data_type> value_type;
+
+    /** Bidirectional iterator maintains a reference count on the map entry.
+     * Provides operator!() and operator bool() to test for end() iterator.
+     */
+    class iterator : 
+        public boost::iterator_facade<iterator, value_type,
+                                      boost::bidirectional_traversal_tag>
+    {
+      public:
+        iterator() {}
+        bool operator!() const { return !ptr; }
+        operator bool() const { return ptr; }
+        void reset() { ptr=0; }
+
+      private:
+        typedef typename RefCountedMap::Entry Entry;
+
+        iterator(intrusive_ptr<Entry> entry) : ptr(entry) {}
+
+        // boost::iterator_facade functions.
+        value_type& dereference() const { return ptr->value; }
+        bool equal(iterator j) const { return ptr==j.ptr; }
+        void increment() { assert(ptr); *this=ptr->map->next(ptr->self); }
+        void decrement() { assert(ptr); *this=ptr->map->prev(ptr->self); }
+
+        intrusive_ptr<Entry> ptr;
+
+      friend class boost::iterator_core_access;
+      friend class RefCountedMap<K,D>;
+    };
+
+    iterator begin() { Lock l(lock); return makeIterator(map.begin()); }
+
+    iterator end() { Lock l(lock); return makeIterator(map.end()); }
+
+    size_t size() { Lock l(lock); return map.size(); }
+
+    bool empty() { return size() == 0u; }
+    
+    iterator find(const key_type& key) {
+        Lock l(lock); return makeIterator(map.find(key));
+    }
+
+    std::pair<iterator, bool> insert(const value_type& x) {
+        Lock l(lock);
+        std::pair<typename Map::iterator,bool> ib=
+            map.insert(make_pair(x.first, Entry(x, this)));
+        ib.first->second.self = ib.first;
+        return std::make_pair(makeIterator(ib.first), ib.second);
+    }
+
+  private:
+
+    //
+    // INVARIANT:
+    //  - All entries in the map have non-0 refcounts.
+    //  - Each entry holds an intrusive_ptr to the map 
+    //
+
+    struct Entry : public RefCounted {
+        typedef typename RefCountedMap::Map::iterator Iterator;
+
+        Entry(const value_type& v, RefCountedMap* m) : value(v), map(m) {}
+        
+        value_type value;
+        intrusive_ptr<RefCountedMap> map;
+        Iterator self;
+
+        // RefCounts are modified with map locked. 
+        struct MapLock : public Lock {
+            MapLock(RefCountedMap& m) : Lock(m.lock) {}
+        };
+
+        void released() const {
+            intrusive_ptr<RefCountedMap> protect(map);
+            map->map.erase(self);
+        }
+    };
+
+    typedef std::map<K,Entry> Map;
+
+    iterator makeIterator(typename Map::iterator i) {
+        // Call with lock held.
+        return iterator(i==map.end() ? 0 : &i->second);
+    }
+
+     void erase(typename RefCountedMap::Map::iterator i) {
+        // Make sure this is not deleted till lock is released.
+        intrusive_ptr<RefCountedMap> self(this);
+        { Lock l(lock); map.erase(i); }
+    }
+
+    iterator next(typename RefCountedMap::Map::iterator i) {
+        { Lock l(lock); return makeIterator(++i); }
+    }
+
+    iterator prev(typename RefCountedMap::Map::iterator i) {
+        { Lock l(lock); return makeIterator(--i); }
+    }
+
+    Mutex lock;
+    Map map;
+
+  friend struct Entry;
+  friend class iterator;
+};
+
+
+}} // namespace qpid::sys
+
+#endif  /*!QPID_SYS_REFCOUNTEDMAP_H*/
diff --git a/cpp/src/tests/Makefile.am b/cpp/src/tests/Makefile.am
index e6626eb1e8..37d59aa9e2 100644
--- a/cpp/src/tests/Makefile.am
+++ b/cpp/src/tests/Makefile.am
@@ -21,14 +21,16 @@ CLEANFILES=
 #
 # Unit tests are built as a single program to reduce valgrind overhead
 # when running the tests. If you want to build a subset of the tests do 
-#   rm unit_test; make unit_test unit_test_SOURCES="SelectedTest.cpp"
+#   rm -f unit_test; make unit_test unit_test_OBJECTS="unit_test.o SelectedTest.o"
 # 
 
 TESTS+=unit_test
 check_PROGRAMS+=unit_test
 unit_test_LDADD=-lboost_unit_test_framework -lboost_regex $(lib_common)
 unit_test_SOURCES= unit_test.cpp \
-	RefCounted.cpp SessionState.cpp Blob.cpp logging.cpp Url.cpp Uuid.cpp \
+	RefCounted.cpp RefCountedMap.cpp \
+	SessionState.cpp Blob.cpp logging.cpp \
+	Url.cpp Uuid.cpp \
 	Shlib.cpp FieldValue.cpp FieldTable.cpp
 
 check_LTLIBRARIES += libshlibtest.la
@@ -96,7 +98,7 @@ testprogs=		\
 
 check_PROGRAMS += $(testprogs) interop_runner
 
-TESTS_ENVIRONMENT = VALGRIND=$(VALGRIND) srcdir=$(srcdir) BOOST_TEST_SHOW_PROGRESS=yes $(srcdir)/run_test
+TESTS_ENVIRONMENT = VALGRIND=$(VALGRIND) srcdir=$(srcdir) $(srcdir)/run_test
 
 system_tests = client_test exception_test quick_perftest quick_topictest
 TESTS += run-unit-tests start_broker $(system_tests) python_tests stop_broker 
diff --git a/cpp/src/tests/RefCountedMap.cpp b/cpp/src/tests/RefCountedMap.cpp
new file mode 100644
index 0000000000..7b0b55db3c
--- /dev/null
+++ b/cpp/src/tests/RefCountedMap.cpp
@@ -0,0 +1,107 @@
+/*
+ *
+ * Copyright (c) 2006 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+#include "qpid/sys/RefCountedMap.h"
+
+#include <boost/test/auto_unit_test.hpp>
+BOOST_AUTO_TEST_SUITE(RefCountedMap);
+
+using namespace std;
+using namespace qpid;
+using namespace qpid::sys;
+
+struct TestMap : public  RefCountedMap<int,int> {
+    static int instances;
+    TestMap() { ++instances; }
+    ~TestMap() { --instances; }
+};
+
+int TestMap::instances=0;
+
+BOOST_AUTO_TEST_CASE(testRefCountedMap) {
+    BOOST_CHECK_EQUAL(0, TestMap::instances);
+    intrusive_ptr<TestMap> map=new TestMap();
+    BOOST_CHECK_EQUAL(1, TestMap::instances);
+
+    // Empty map
+    BOOST_CHECK(map->empty());
+    BOOST_CHECK_EQUAL(map->size(), 0u);
+    BOOST_CHECK(map->begin()==map->end());
+    BOOST_CHECK(!map->begin());
+    BOOST_CHECK(!map->end());
+    BOOST_CHECK(map->find(1)==map->end());
+    BOOST_CHECK(!map->find(1));
+
+    {
+        // Add and modify an entry
+        pair<TestMap::iterator, bool> ib=map->insert(TestMap::value_type(1,11));
+        BOOST_CHECK(ib.second);
+        TestMap::iterator p = ib.first;
+        ib.first.reset();
+        BOOST_CHECK(p);
+        BOOST_CHECK_EQUAL(p->second, 11);
+        p->second=22;
+        BOOST_CHECK_EQUAL(22, map->find(1)->second);
+        BOOST_CHECK(!map->empty());
+        BOOST_CHECK_EQUAL(map->size(), 1u);
+
+        // Find an entry
+        TestMap::iterator q=map->find(1);
+        BOOST_CHECK(q==p);
+        BOOST_CHECK_EQUAL(q->first, 1);
+    }
+
+    BOOST_CHECK(map->empty());
+    BOOST_CHECK_EQUAL(1, TestMap::instances); 
+
+    {
+        // Hold the map via a reference to an entry.
+        TestMap::iterator p=map->insert(TestMap::value_type(2,22)).first;
+        map=0;                      // Release the map->
+        BOOST_CHECK_EQUAL(1, TestMap::instances); // Held by entry.
+        BOOST_CHECK_EQUAL(p->second, 22);
+    }
+
+    BOOST_CHECK_EQUAL(0, TestMap::instances); 
+}
+
+
+BOOST_AUTO_TEST_CASE(testRefCountedMapIterator) {
+    BOOST_CHECK_EQUAL(TestMap::instances, 0);
+    {
+        intrusive_ptr<TestMap> map=new TestMap();
+        TestMap::iterator iter[4], p, q;
+        for (int i = 0; i < 4; ++i) 
+            iter[i] = map->insert(make_pair(i, 10+i)).first;
+        int j=0;
+        for (p = map->begin(); p != map->end(); ++p, ++j)  {
+            BOOST_CHECK_EQUAL(p->first, j);
+            BOOST_CHECK_EQUAL(p->second, 10+j);
+        }
+        BOOST_CHECK_EQUAL(4, j);
+
+        // Release two entries.
+        iter[0]=iter[2]=TestMap::iterator();
+        
+        p=map->begin();
+        BOOST_CHECK_EQUAL(p->second, 11);
+        ++p;
+        BOOST_CHECK_EQUAL(p->second, 13);
+    }
+    BOOST_CHECK_EQUAL(TestMap::instances, 0);
+}