From 7de71198a292c7b0a533abe4f950a4e8c7ec3c97 Mon Sep 17 00:00:00 2001 From: Alan Conway Date: Thu, 1 Nov 2007 05:58:50 +0000 Subject: 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 --- cpp/src/qpid/RefCounted.h | 4 +- cpp/src/qpid/sys/RefCountedMap.h | 171 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 173 insertions(+), 2 deletions(-) create mode 100644 cpp/src/qpid/sys/RefCountedMap.h (limited to 'cpp/src/qpid') 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 +#include + +#include + +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 RefCountedMap : public RefCounted +{ + typedef Mutex::ScopedLock Lock; + + public: + typedef K key_type; + typedef D data_type; + typedef std::pair 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 + { + 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) : 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 ptr; + + friend class boost::iterator_core_access; + friend class RefCountedMap; + }; + + 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 insert(const value_type& x) { + Lock l(lock); + std::pair 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 map; + Iterator self; + + // RefCounts are modified with map locked. + struct MapLock : public Lock { + MapLock(RefCountedMap& m) : Lock(m.lock) {} + }; + + void released() const { + intrusive_ptr protect(map); + map->map.erase(self); + } + }; + + typedef std::map 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 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*/ -- cgit v1.2.1