Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | Related Pages

safe_set.h

00001 /*
00002   libwftk - Worldforge Toolkit - a widget library
00003   Copyright (C) 2002 Ron Steinke <rsteinke@w-link.net>
00004 
00005   This library is free software; you can redistribute it and/or
00006   modify it under the terms of the GNU Lesser General Public
00007   License as published by the Free Software Foundation; either
00008   version 2.1 of the License, or (at your option) any later version.
00009   
00010   This library is distributed in the hope that it will be useful,
00011   but WITHOUT ANY WARRANTY; without even the implied warranty of
00012   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013   Lesser General Public License for more details.
00014   
00015   You should have received a copy of the GNU Lesser General Public
00016   License along with this library; if not, write to the
00017   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00018   Boston, MA  02111-1307, SA.
00019 */
00020 
00021 #ifndef _SAFE_SET_H_
00022 #define _SAFE_SET_H_
00023 
00024 #include <set>
00025 #include <map>
00026 
00027 namespace wftk {
00028 
00029 // This is basically std::set<> without iterators.
00030 // Using the for_each() functions instead makes it possible
00031 // to do locking so insert()/erase() calls that would otherwise
00032 // invalidate the iterators don't.
00033 
00034 template<class C>
00035 class SafeSet
00036 {
00037  public:
00038   SafeSet() : lock_(0) {}
00039   SafeSet(const SafeSet& s) : map_(s.map_), deleted_(s.deleted_),
00040     pending_(s.pending_), lock_(0) {if(s.lock_) cleanup();}
00041 
00043   bool insert(C*);
00045   bool erase(C*);
00046 
00048   bool has(C*) const;
00049 
00050   // These functions are for_each() instead of forEach() to
00051   // conform to the naming of the STL for_each function
00052 
00053   void for_each(void (*func)(C*))
00054   {
00055     ++lock_;
00056     for(MapIterator I = map_.begin(); I != map_.end(); ++I)
00057       if(I->second)
00058         func(I->first);
00059     if(--lock_ == 0)
00060       cleanup();
00061   }
00062   template<class D>
00063   void for_each(void (*func)(C*, D), D d)
00064   {
00065     ++lock_;
00066     for(MapIterator I = map_.begin(); I != map_.end(); ++I)
00067       if(I->second)
00068         func(I->first, d);
00069     if(--lock_ == 0)
00070       cleanup();
00071   }
00072   void for_each(void (C::*func)(void))
00073   {
00074     ++lock_;
00075     for(MapIterator I = map_.begin(); I != map_.end(); ++I)
00076       if(I->second)
00077         (I->first->*func)();
00078     if(--lock_ == 0)
00079       cleanup();
00080   }
00081   template<class D>
00082   void for_each(void (C::*func)(D), D d)
00083   {
00084     ++lock_;
00085     for(MapIterator I = map_.begin(); I != map_.end(); ++I)
00086       if(I->second)
00087         (I->first->*func)(d);
00088     if(--lock_ == 0)
00089       cleanup();
00090   }
00091 
00092  private:
00093   SafeSet& operator=(const SafeSet&);
00094 
00095   void cleanup();
00096 
00097   // A map from instances to 'valid' flags
00098   typedef typename std::map<C*,bool> Map;
00099     typedef typename Map::iterator MapIterator;
00100     typedef typename Map::const_iterator MapConstIterator;
00101     typedef typename Map::value_type MapValueType;
00102   Map map_;
00103   typedef typename std::set<C*> Set;
00104     typedef typename Set::iterator SetIterator;
00105   Set deleted_;
00106   Set pending_;
00107   unsigned long lock_;
00108 };
00109 
00110 template<class C>
00111 bool SafeSet<C>::insert(C* c)
00112 {
00113   if(!lock_)
00114     return map_.insert(Map::value_type(c, true)).second;
00115 
00116   MapIterator I;
00117   if((I = map_.find(c)) != map_.end() && I->second)
00118     return false; // reinserting a valid iterator in the main map
00119 
00120   return pending_.insert(c).second;
00121 }
00122 
00123 template<class C>
00124 bool SafeSet<C>::erase(C* c)
00125 {
00126   MapIterator I = map_.find(c);
00127 
00128   assert(I == map_.end() || I->second || lock_);
00129 
00130   if(I == map_.end() || !I->second) {
00131     // We may be erasing an id that was added inside the current lock
00132     SetIterator J;
00133     if(lock_ && (J = pending_.find(c)) != pending_.end()) {
00134       pending_.erase(J);
00135       return true;
00136     }
00137     return false;
00138   }
00139 
00140   if(lock_) {
00141     bool success = deleted_.insert(c).second;
00142     assert(success);
00143     I->second = false;
00144   }
00145   else
00146     map_.erase(I);
00147 
00148   return true;
00149 }
00150 
00151 template<class C>
00152 bool SafeSet<C>::has(C* c) const
00153 {
00154   MapConstIterator I = map_.find(c);
00155 
00156   assert(I == map_.end() || I->second || lock_);
00157 
00158   if(I != map_.end() && I->second)
00159     return true;
00160 
00161   if(!lock_)
00162     return false;
00163 
00164   return pending_.find(c) != pending_.end();
00165 }
00166 
00167 template<class C>
00168 void SafeSet<C>::cleanup()
00169 {
00170   // Must do deletion first, since the memory for deleted
00171   // instances may have been reallocated to new instances.
00172   // Thus, while pointers in map_ and pending_ are separately
00173   // unique, they may overlap
00174 
00175   for(SetIterator I = deleted_.begin(); I != deleted_.end(); ++I) {
00176     MapIterator J = map_.find(*I);
00177     assert(J != map_.end());
00178     assert(!J->second);
00179     map_.erase(J);
00180   }
00181   deleted_.clear();
00182 
00183   for(SetIterator I = pending_.begin(); I != pending_.end(); ++I) {
00184     MapValueType val(*I, true);
00185     bool success = map_.insert(val).second;
00186     assert(success);
00187   }
00188   pending_.clear();
00189 }
00190 
00191 } // namespace
00192 
00193 #endif

Generated Tue Apr 12 22:48:52 2005.
Copyright © 1998-2003 by the respective authors.

This document is licensed under the terms of the GNU Free Documentation License and may be freely distributed under the conditions given by this license.