sys::RefCountedMap - reference-counted weak map of reference-counted objects.

Ensures objects are atomically deleted and removed from the map.



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

3 files changed, 202 insertions, 172 deletions

diff --git a/cpp/src/qpid/RefCounted.h b/cpp/src/qpid/RefCounted.h
index bcef69d21e..c325b204d4 100644
--- a/cpp/src/qpid/RefCounted.h
+++ b/cpp/src/qpid/RefCounted.h
@@ -39,10 +39,9 @@ class AbstractRefCounted {
 };
 
 /**
- * Reference-counted virtual base class.
+ * Reference-counted base class.
  */
-class RefCounted : public AbstractRefCounted
-{
+class RefCounted : public AbstractRefCounted {
   public:
     RefCounted() {}
     virtual void addRef() const { ++count; }
@@ -53,12 +52,26 @@ class RefCounted : public AbstractRefCounted
     // Copy/assign do not copy refcounts. 
     RefCounted(const RefCounted&) : AbstractRefCounted() {}
     RefCounted& operator=(const RefCounted&) { return *this; }
-    virtual void released() const { delete this; }
+    virtual void released() const { assert(count==0); delete this; }
 
-  private:
     mutable sys::AtomicCount count;
 };
 
+/**
+ * Reference-counted member of a reference-counted parent class.
+ * Delegates reference counts to the parent so that the parent is
+ * deleted only when there are no references to the parent or any of
+ * its children.
+ */
+struct RefCountedChild : public AbstractRefCounted {
+  protected:
+    AbstractRefCounted& parent;
+    RefCountedChild(AbstractRefCounted& parent_) : parent(parent_) {}
+  public:
+    void addRef() const { parent.addRef(); }
+    void release() const { parent.release(); }
+};
+
 using boost::intrusive_ptr;
 
 } // namespace qpid
diff --git a/cpp/src/qpid/sys/RefCountedMap.h b/cpp/src/qpid/sys/RefCountedMap.h
index 2041548667..7db1d34953 100644
--- a/cpp/src/qpid/sys/RefCountedMap.h
+++ b/cpp/src/qpid/sys/RefCountedMap.h
@@ -24,121 +24,140 @@
 
 #include "qpid/sys/Mutex.h"
 #include "qpid/RefCounted.h"
-
+#include <boost/type_traits/remove_pointer.hpp>
+#include <boost/bind.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/cast.hpp>
+#include <vector>
 #include <map>
+#include <algorithm>
 
 namespace qpid {
 namespace sys {
 
-/**
- * A thread-safe, RefCounted map of RefCounted entries.  Entries are
- * automatically erased when released 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.
- *
- * The map can be cleared with close()
- *
- * WARNING: Assigning an intrusive_ptr<D> returned by the map 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.
- *
- * @param D must be public RefCounted 
- */
-template <class Key, class Data>
-class RefCountedMap : public RefCounted
-{
+template <class, class, class> class RefCountedMap;
+
+template <class Key, class Data, class Base=RefCounted,
+          class Impl=std::map<Key, Data*> >
+class RefCountedMapData : public Base {
   public:
-    typedef intrusive_ptr<Data> DataPtr;
+    typedef RefCountedMap<Key, Data, Impl> Map;
+
+    bool attached() {
+        assert(map || self->second == this);
+        return map;
+    }
+    const Key& getKey() const { assert(attached()); return self->first; }
+    void released() const { if (map) map->lockedDetach(self); delete this; }
 
   private:
-    struct Entry : public Data {
-        typedef typename RefCountedMap::Iterator Iterator;
-        intrusive_ptr<RefCountedMap> map;
-        Iterator self;
-        void init(intrusive_ptr<RefCountedMap> m, Iterator s) {
-            map=m; self=s;
-        }
-        void released() const {
-            if (map) {
-                intrusive_ptr<RefCountedMap> protect(map);
-                map->map.erase(self);
-            }
-        }
-    };
+      friend class RefCountedMap<Key, Data, Impl>;
+    intrusive_ptr<Map> map;
+    typename Impl::iterator self;
 
-    typedef std::map<Key,Entry> Map;
-    typedef typename Map::iterator Iterator;
+  public:
+};
 
-    typedef Mutex::ScopedLock Lock;
-    struct OpenLock : public Lock {
-        OpenLock(RefCountedMap& m) : Lock(m.lock) { assert(!m.closed); }
-    };
+/**
+ * A thread-safe, reference-counted, weak map of reference-counted values.
+ * 
+ * The map does not hold a reference to its members, they must have
+ * external references to exist.  When last external reference is
+ * released, the value is atomically erased from the map and deleted.
+ *
+ * The map itself is a member of a ref-counted holder class, the
+ * map ensures its holder is not deleted till the map is empty.
+ */
+template <class Key, class Data, class Impl=std::map<Key, Data*> >
+class RefCountedMap : public RefCountedChild {
+  template <class, class, class, class> friend class RefCountedMapData;
+    typedef typename Impl::iterator iterator;
+    typedef typename Impl::value_type value_type;
     
-    DataPtr ptr_(Iterator i) { return i==map.end() ? 0 : &i->second; }
+    mutable sys::Mutex lock;
+    Impl map;
+
+    // Acquire the lock and ensure map is not deleted before unlock.
+    class Lock {
+        intrusive_ptr<const RefCountedMap> map;
+        sys::Mutex::ScopedLock lock;
+      public:
+        Lock(const RefCountedMap* m) : map(m), lock(m->lock) {}
+    };
 
-    Mutex lock;
-    Map map;
-    bool closed;
+    // Called from Data::released.
+    void lockedDetach(iterator i) { Lock l(this); detach(i); }
     
-  friend struct Entry;
-  friend class iterator;
+    void detach(iterator i) {
+        // Must be called with lock held.
+        assert(i->second->map == this);
+        map.erase(i);
+        i->second->map = 0; // May call this->release()
+    }
 
   public:
-    RefCountedMap() : closed(false) {}
+    RefCountedMap(RefCounted& container) : RefCountedChild(container) {}
+    ~RefCountedMap() {}
     
-    /** Return 0 if not found
-     * @pre !isClosed()
-     */
-    DataPtr find(const Key& k) {
-        OpenLock l(*this);
-        return ptr_(map.find(k));
+    /** Return 0 if not found */
+    intrusive_ptr<Data> find(const Key& k) {
+        Lock l(this);
+        iterator i = map.find(k);
+        return (i == map.end()) ? 0 : i->second;
     }
 
-    /** Find existing or create new entry for k 
-     * @pre !isClosed()
-     */
-    DataPtr get(const Key& k)  {
-        OpenLock l(*this);
-        std::pair<Iterator,bool> ib=
-            map.insert(std::make_pair(k, Entry()));
-        if (ib.second)
-            ib.first->second.init(this, ib.first);
-        return ptr_(ib.first);
+    bool insert(const Key& k, intrusive_ptr<Data> d) {
+        Lock l(this);
+        iterator i;
+        bool inserted;
+        boost::tuples::tie(i, inserted) =
+            map.insert(std::make_pair(k, d.get()));
+        if (inserted)  {
+            assert(!d->map);
+            d->map=boost::polymorphic_downcast<RefCountedMap*>(this);
+            d->self=i;
+        }
+        return inserted;
     }
     
-    size_t size() { Lock l(lock); return map.size(); }
+    size_t size() { Lock l(this); return map.size(); }
 
-    bool empty() { return size() == 0u; }
+    bool empty() { Lock l(this); return map.empty(); }
 
-    bool isClosed() { Lock l(lock); return closed; }
-    
-    /**
-     * Close the map and call functor on each remaining entry.
-     * Note the map will not be deleted until all entries are
-     * released, the assumption is that functor takes some
-     * action that will release the entry.
-     *
-     * close() does nothing if isClosed() 
-     */
-    template <class F>
-    void close(F functor) {
-        Lock l(lock);
-        if (closed) return;
-        closed=true;            // No more inserts
-        intrusive_ptr<RefCountedMap> protect(this);
-        Iterator i=map.begin();
-        while (i != map.end()) {
-            Iterator j=i;
-            ++i;
-            functor(j->second); // May erase j
+    void erase(const Key& k) { Lock l(this); detach(map.find(k)); }
+
+    void clear() { Lock l(this); while (!map.empty()) detach(map.begin()); }
+
+    /** Clear the map, apply functor to each entry before erasing */
+    template <class F> void clear(F functor) {
+        Lock l(this);
+        while (!map.empty()) {
+            intrusive_ptr<Data> ptr;
+            if (map.empty()) return;
+            ptr = map.begin()->second;
+            detach(map.begin());
+            sys::Mutex::ScopedUnlock u(lock);
+            functor(ptr);
         }
     }
-};
 
+    /** Apply functor to each map entry. */
+    template <class F> void apply(F functor) {
+        std::vector<intrusive_ptr<Data> > snapshot;
+        {
+            // Take a snapshot referencing all values in map.
+            Lock l(this);
+            snapshot.resize(map.size());
+            typedef value_type value_type;
+            std::transform(map.begin(), map.end(), snapshot.begin(),
+                           boost::bind(&value_type::second, _1));
+        }
+        // Drop the lock to call functor.
+        std::for_each(snapshot.begin(), snapshot.end(), functor);
+    }
+};
 
+    
 }} // namespace qpid::sys
 
 #endif  /*!QPID_SYS_REFCOUNTEDMAP_H*/
diff --git a/cpp/src/tests/RefCountedMap.cpp b/cpp/src/tests/RefCountedMap.cpp
index 1875b8161c..79a0d94eb7 100644
--- a/cpp/src/tests/RefCountedMap.cpp
+++ b/cpp/src/tests/RefCountedMap.cpp
@@ -17,9 +17,10 @@
  */
 
 #include "qpid/sys/RefCountedMap.h"
-
 #include "unit_test.h"
+#include "test_tools.h"
 #include <boost/bind.hpp>
+#include <map>
 
 QPID_AUTO_TEST_SUITE(RefCountedMapTestSuite)
 
@@ -27,99 +28,96 @@ using namespace std;
 using namespace qpid;
 using namespace qpid::sys;
 
-template <int ID> struct CountEm {
+template <int Id> struct Counted {
     static int instances;
-    CountEm() { instances++; }
-    ~CountEm() { instances--; }
-    CountEm(const CountEm&) { instances++; }
+    Counted() { ++instances; }
+    Counted(const Counted&) { ++instances; }
+    ~Counted() { --instances; }
 };
-template <int ID> int CountEm<ID>::instances = 0;
-    
-struct Data;
+template <int Id>int Counted<Id>::instances=0;
 
-struct Attachment : public RefCounted, public CountEm<1> {
-    intrusive_ptr<Data> link;
+struct Data : public RefCountedMapData<int, Data>, public Counted<2> {
+    Data(int i=0) : value(i) {}
+    int value;
+    void inc()  { value++; }
 };
 
-struct Data : public RefCounted, public CountEm<2> {
-    intrusive_ptr<Attachment> link;
-    void attach(intrusive_ptr<Attachment> a) {
-        if (!a) return;
-        a->link=this;
-        link=a;
-    }
-    void detach() {
-        if (!link) return;
-        intrusive_ptr<Data> protect(this);
-        link->link=0;
-        link=0;
-    }
+struct Container : public RefCounted, public Counted<3>  {
+    Data::Map map;
+    Container() : map(*this) {}
 };
-typedef intrusive_ptr<Data> DataPtr;
-
-struct Map : public  RefCountedMap<int,Data>, public CountEm<3> {};
-
-
-
-
-BOOST_AUTO_TEST_CASE(testRefCountedMap) {
-    BOOST_CHECK_EQUAL(0, Map::instances);
-    BOOST_CHECK_EQUAL(0, Data::instances);
-
-    intrusive_ptr<Map> map=new Map();
-    BOOST_CHECK_EQUAL(1, Map::instances);
-
-    // Empty map
-    BOOST_CHECK(!map->isClosed());
-    BOOST_CHECK(map->empty());
-    BOOST_CHECK_EQUAL(map->size(), 0u);
-    BOOST_CHECK(!map->find(1));
-
+    
+struct RefCountedMapFixture {
+    intrusive_ptr<Container> cont;
+    intrusive_ptr<Data> p, q;
+    RefCountedMapFixture() :
+        cont(new Container()), p(new Data(1)), q(new Data(2))
     {
-        // Add entries
-        DataPtr p=map->get(1);
-        DataPtr q=map->get(2);
+        cont->map.insert(1,p);
+        cont->map.insert(2,q);
+    }
+    ~RefCountedMapFixture() { if (cont) cont->map.clear(); }
+};
 
-        BOOST_CHECK_EQUAL(Data::instances, 2);
-        BOOST_CHECK_EQUAL(map->size(), 2u);
+BOOST_FIXTURE_TEST_CASE(testFixtureSetup, RefCountedMapFixture) {
+    BOOST_CHECK_EQUAL(1, Container::instances);
+    BOOST_CHECK_EQUAL(2, Data::instances);
+    BOOST_CHECK_EQUAL(cont->map.size(), 2u);
+    BOOST_CHECK_EQUAL(cont->map.find(1)->value, 1);
+    BOOST_CHECK_EQUAL(cont->map.find(2)->value, 2);
+}
 
-        p=0;                    // verify erased
-        BOOST_CHECK_EQUAL(Data::instances, 1);
-        BOOST_CHECK_EQUAL(map->size(), 1u);
+BOOST_FIXTURE_TEST_CASE(testReleaseRemoves, RefCountedMapFixture)
+{
+    // Release external ref, removes from map
+    p = 0;
+    BOOST_CHECK_EQUAL(Data::instances, 1);
+    BOOST_CHECK_EQUAL(cont->map.size(), 1u);
+    BOOST_CHECK(!cont->map.find(1));
+    BOOST_CHECK_EQUAL(cont->map.find(2)->value, 2);
+
+    q = 0;
+    BOOST_CHECK(cont->map.empty());
+}
 
-        p=map->find(2);
-        BOOST_CHECK(q==p);
+// Functor that releases values as a side effect.
+struct Release {
+    RefCountedMapFixture& f ;
+    Release(RefCountedMapFixture& ff) : f(ff) {}
+    void operator()(const intrusive_ptr<Data>& ptr) {
+        BOOST_CHECK(ptr->value > 0); // Make sure ptr is not released.
+        f.p = 0;
+        f.q = 0;
+        BOOST_CHECK(ptr->value > 0); // Make sure ptr is not released.
     }
+};
 
-    BOOST_CHECK(map->empty());
-    BOOST_CHECK_EQUAL(1, Map::instances); 
-    BOOST_CHECK_EQUAL(0, Data::instances); 
 
-    {
-        // Hold the map via a reference to an entry.
-        DataPtr p=map->get(3);
-        map=0;               
-        BOOST_CHECK_EQUAL(1, Map::instances); // Held by entry.
-    }
-    BOOST_CHECK_EQUAL(0, Map::instances); // entry released
+BOOST_FIXTURE_TEST_CASE(testApply, RefCountedMapFixture) {
+    cont->map.apply(boost::bind(&Data::inc, _1));
+    BOOST_CHECK_EQUAL(2, p->value);
+    BOOST_CHECK_EQUAL(3, q->value);
+
+    // Allow functors to release valuse as side effects.
+    cont->map.apply(Release(*this));
+    BOOST_CHECK(cont->map.empty());
+    BOOST_CHECK_EQUAL(Data::instances, 0);
 }
 
+BOOST_FIXTURE_TEST_CASE(testClearFunctor, RefCountedMapFixture) {
+    cont->map.clear(boost::bind(&Data::inc, _1));
+    BOOST_CHECK(cont->map.empty());
+    BOOST_CHECK_EQUAL(2, p->value);
+    BOOST_CHECK_EQUAL(3, q->value);
+}
 
-BOOST_AUTO_TEST_CASE(testRefCountedMapAttachClose) {
-    intrusive_ptr<Map> map=new Map();
-    DataPtr d=map->get(5);
-    d->attach(new Attachment());
-    d=0;
-    // Attachment keeps entry pinned
-    BOOST_CHECK_EQUAL(1u, map->size());
-    BOOST_CHECK(map->find(5));
-
-    // Close breaks attachment
-    map->close(boost::bind(&Data::detach, _1));
-    BOOST_CHECK(map->empty());
-    BOOST_CHECK(map->isClosed());
-    BOOST_CHECK_EQUAL(0, Data::instances);
-    BOOST_CHECK_EQUAL(0, Attachment::instances);
+BOOST_FIXTURE_TEST_CASE(testReleaseEmptyMap, RefCountedMapFixture) {
+    // Container must not be deleted till map is empty.
+    cont = 0;
+    BOOST_CHECK_EQUAL(1, Container::instances); // Not empty.
+    p = 0;
+    q = 0;
+    BOOST_CHECK_EQUAL(0, Container::instances); // Deleted
 }
 
 QPID_AUTO_TEST_SUITE_END()