Main Page | Namespace List | Class Hierarchy | Class List | 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 Wed Jul 28 17:28:43 2004.
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.