threadsafe_multimap.h

Go to the documentation of this file.
00001 /*
00002  * threadsafe_multimap.h
00003  * 
00004  * Copyright (C) 2010  Thomas A. Vaughan
00005  * All rights reserved.
00006  *
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions are met:
00010  *     * Redistributions of source code must retain the above copyright
00011  *       notice, this list of conditions and the following disclaimer.
00012  *     * Redistributions in binary form must reproduce the above copyright
00013  *       notice, this list of conditions and the following disclaimer in the
00014  *       documentation and/or other materials provided with the distribution.
00015  *     * Neither the name of the <organization> nor the
00016  *       names of its contributors may be used to endorse or promote products
00017  *       derived from this software without specific prior written permission.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
00020  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00021  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00022  * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
00023  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00024  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00025  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00026  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *
00030  *
00031  * Basic threadsafe multimap (wrapper around std::multimap)
00032  */
00033 
00034 #ifndef WAVEPACKET_THREADSAFE_MULTIMAP_H__
00035 #define WAVEPACKET_THREADSAFE_MULTIMAP_H__
00036 
00037 // includes --------------------------------------------------------------------
00038 #include "common/common.h"
00039 #include "smart_mutex.h"
00040 
00041 #include <pthread.h>
00042 
00043 
00044 ////////////////////////////////////////////////////////////////////////////////
00045 ///
00046 ///     \ingroup threadsafe
00047 ///
00048 ///     A very simple map object that is safe for multiple threads to use at the
00049 ///     same time.  There is a single mutex protecting the entire map.
00050 ///
00051 ///     You can iterate using getIterator()/getNextElement().  However, that is
00052 ///     not guaranteed iteration.  Your iterator will be invalidated (and
00053 ///     getNextElement() will return false) if another thread has since updated
00054 ///     the map.
00055 ///
00056 ////////////////////////////////////////////////////////////////////////////////
00057 template <class K, class T>
00058 class threadsafe_multimap : protected std::multimap<K,T> {
00059 private:
00060         // private typedefs ----------------------------------------------------
00061         typedef std::multimap<K,T>                      base_map_t;
00062         typedef typename std::multimap<K,T>::iterator   base_iterator_t;
00063         typedef typename std::pair<base_iterator_t, base_iterator_t> iter_pair_t;
00064 
00065         struct real_iter_t {
00066                 base_iterator_t         iter; // start at this element
00067                 base_iterator_t         end;  // end before reaching here
00068                 dword_t                 rvn;
00069         };
00070 
00071 public:
00072         // public typedefs -----------------------------------------------------
00073         struct iterator_t {
00074         protected:
00075                 byte_t          opaque[sizeof(real_iter_t)];
00076         };
00077 
00078         // threadsafe_map class interface methods ------------------------------
00079 
00080         /// how many elements in the map
00081         int size(void) {
00082                         // not a const operation because we touch the mutex
00083                         mlock l(m_mutex);
00084                         return base_map_t::size();
00085                 }
00086 
00087         /// how many elements with the given key
00088         int count(IN const K& key) {
00089                         mlock l(m_mutex);
00090                         return base_map_t::count(key);
00091                 }
00092 
00093         /// insert the given object at the given key value
00094         void insert(IN const K& key, IN const T& t) {
00095                         mlock l(m_mutex);
00096                         ++m_rvn;
00097                         base_map_t::insert(std::pair<K, T>(key, t));
00098                 }
00099 
00100         /// remove (erase) all elements with this key
00101         void remove(IN const K& key) {
00102                         mlock l(m_mutex);
00103                         ++m_rvn;
00104                         iter_pair_t pair = this->equal_range(key);
00105                         base_map_t::erase(pair.first, pair.second);
00106                 }
00107 
00108         /// clear out (erase) the entire map
00109         void clear(void) {
00110                         mlock l(m_mutex);
00111                         ++m_rvn;
00112                         base_map_t::clear();
00113                 }
00114 
00115         /// get an iterator (points to the first element in the map)
00116         void getIterator(OUT iterator_t& i) {
00117                         real_iter_t * ri = getRealIterator(i);
00118                         mlock l(m_mutex);
00119                         ri->rvn = m_rvn;
00120                         ri->iter = this->begin();
00121                         ri->end = this->end();
00122                 }
00123 
00124         /// get an iterator just for a particular key
00125         void getIterator(IN const K& key, OUT iterator_t& i) {
00126                         real_iter_t * ri = getRealIterator(i);
00127                         mlock l(m_mutex);
00128                         ri->rvn = m_rvn;
00129                         iter_pair_t pair = base_map_t::equal_range(key);
00130                         ri->iter = pair.first;
00131                         ri->end = pair.second;
00132                 }
00133 
00134         /// get next element in map and increment iterator
00135         bool getNextElement(IO iterator_t& i, OUT K& k, OUT T& t) {
00136                         real_iter_t * ri = getRealIterator(i);
00137                         mlock l(m_mutex);
00138                         T * pt = this->getNextElementInternal(ri, k);
00139                         if (!pt)
00140                                 return false;
00141                         t = *pt;
00142                         return true;
00143                 }
00144 
00145         /// get next element without getting a local copy.  Caller had
00146         ///     better be sure that the element won't be removed after
00147         ///     this call!
00148         T * getNextElementUnsafe(IO iterator_t& i, OUT K& k) {
00149                         real_iter_t * ri = getRealIterator(i);
00150                         mlock l(m_mutex);
00151                         return this->getNextElementInternal(ri, k);
00152                 }
00153 
00154         /// for debugging/validation only
00155         static int getRealIteratorSize(void) throw() {
00156                         return sizeof(real_iter_t);
00157                 }
00158 
00159 private:
00160         // private helper methods ----------------------------------------------
00161         static real_iter_t * getRealIterator(IN iterator_t& i) throw() {
00162                         return (real_iter_t *) &i;
00163                 }
00164 
00165         T * getNextElementInternal(IN real_iter_t * ri, OUT K& k) {
00166                         // only used by other class methods!
00167                         // caller should already have mutex
00168                         if (ri->rvn != this->m_rvn)
00169                                 return NULL;    // iterator is now invalid!
00170                         if (ri->end == ri->iter)
00171                                 return NULL;    // end of iteration
00172 
00173                         // iterator is good!
00174                         k = ri->iter->first;
00175                         T * t = &ri->iter->second;
00176                         ++ri->iter;
00177                         return t;
00178                 }
00179 
00180         // private member data -------------------------------------------------
00181         smart_mutex             m_mutex;
00182         dword_t                 m_rvn;
00183 };
00184 
00185 
00186 #endif  // WAVEPACKET_THREADSAFE_MULTIMAP_H__
00187