![]() |
RTBKit
0.9
Open-source framework to create real-time ad bidding systems.
|
00001 /* timeout_map.h -*- C++ -*- 00002 Jeremy Barnes, 2 February 2012 00003 Copyright (c) 2012 Datacratic. All rights reserved. 00004 00005 Map from key -> value with inbuilt timeouts. 00006 00007 Eventually will allow persistance. 00008 */ 00009 00010 #ifndef __router__timeout_map_h__ 00011 #define __router__timeout_map_h__ 00012 00013 #include <map> 00014 #include "soa/types/date.h" 00015 #include <boost/function.hpp> 00016 #include "jml/arch/exception.h" 00017 #include <math.h> 00018 00019 namespace Datacratic { 00020 00021 template<typename Key, class Value> 00022 struct TimeoutMap { 00023 00024 TimeoutMap(double defaultTimeout = -INFINITY) 00025 : defaultTimeout(defaultTimeout), earliest(Date::positiveInfinity()) 00026 { 00027 } 00028 00029 double defaultTimeout; 00030 00031 boost::function<void (const std::string & reason)> throwException; 00032 00033 void doThrowException(const std::string & reason) const 00034 { 00035 if (throwException) throwException(reason); 00036 else throw ML::Exception(reason); 00037 std::cerr << "TimeoutMap exception thrower returned" << std::endl; 00038 abort(); 00039 } 00040 00041 struct Node; 00042 00047 Node & operator [] (const Key & key) 00048 { 00049 auto res = nodes.insert(std::make_pair(key, Node())); 00050 auto it = res.first; 00051 if (res.second) { 00052 if (!std::isnormal(defaultTimeout) || defaultTimeout < 0.0) 00053 doThrowException("no default timeout specified and insert " 00054 "not used"); 00055 Date timeout = Date::now().plusSeconds(defaultTimeout); 00056 it->second.timeoutIt = timeouts.insert(std::make_pair(timeout, it)); 00057 if (timeout < earliest) earliest = timeout; 00058 } 00059 00060 return it->second; 00061 } 00062 00066 Node & access(const Key & key, Date timeout) 00067 { 00068 auto res = nodes.insert(std::make_pair(key, Node(Value(), timeout))); 00069 auto it = res.first; 00070 if (res.second) { 00071 // inserted... insert the timeout 00072 it->second.timeoutIt = timeouts.insert(std::make_pair(timeout, it)); 00073 if (timeout < earliest) earliest = timeout; 00074 } 00075 else { 00076 // already existed... update the timeout 00077 updateTimeout(it, timeout); 00078 } 00079 return it->second; 00080 } 00081 00085 Node & insert(const Key & key, const Value & value, 00086 Date timeout) 00087 { 00088 auto res = nodes.insert(std::make_pair(key, Node(value, timeout))); 00089 if (!res.second) { 00090 std::cerr << "key = " << key << std::endl; 00091 std::cerr << "contents (" << nodes.size() << ") = " << std::endl; 00092 int n = 0; 00093 for (auto it = nodes.begin(), end = nodes.end(); it != end && n < 20; ++it, ++n) 00094 std::cerr << it->first << " @ " << it->second.timeoutIt->first << " " 00095 << (it->first == key ? "*****" : "") << std::endl; 00096 doThrowException("TimeoutMap: " 00097 "attempt to re-insert existing key"); 00098 } 00099 auto it = res.first; 00100 it->second.timeoutIt = timeouts.insert(std::make_pair(timeout, it)); 00101 if (timeout < earliest) earliest = timeout; 00102 return it->second; 00103 } 00104 00108 Node & insert(const Key & key, Value && value, Date timeout) 00109 { 00110 auto res = nodes.insert(std::make_pair(key, Node(value, timeout))); 00111 if (!res.second) { 00112 std::cerr << "key = " << key << std::endl; 00113 std::cerr << "contents (" << nodes.size() << ") = " << std::endl; 00114 int n = 0; 00115 for (auto it = nodes.begin(), end = nodes.end(); it != end && n < 20; ++it, ++n) 00116 std::cerr << it->first << " @ " << it->second.timeoutIt->first << " " 00117 << (it->first == key ? "*****" : "") << std::endl; 00118 doThrowException("TimeoutMap: " 00119 "attempt to re-insert existing key"); 00120 } 00121 auto it = res.first; 00122 it->second.timeoutIt = timeouts.insert(std::make_pair(timeout, it)); 00123 if (timeout < earliest) earliest = timeout; 00124 return it->second; 00125 } 00126 00128 Node & update(const Key & key, Value && value) 00129 { 00130 auto it = nodes.find(key); 00131 if (it == nodes.end()) 00132 doThrowException("TimeoutMap: " 00133 "attempt to update nonexistant key"); 00134 Value & v = it->second; 00135 v = value; 00136 return it->second; 00137 } 00138 00140 Node & update(const Key & key, const Value & value) 00141 { 00142 auto it = nodes.find(key); 00143 if (it == nodes.end()) 00144 doThrowException("TimeoutMap: " 00145 "attempt to update nonexistant key"); 00146 Value & v = it->second; 00147 v = value; 00148 return it->second; 00149 } 00150 00151 void updateTimeout(const Key & key, Date timeout) 00152 { 00153 auto it = nodes.find(key); 00154 if (it == nodes.end()) 00155 doThrowException("TimeoutMap: " 00156 "attempt to update nonexistant key"); 00157 updateTimeout(it, timeout); 00158 } 00159 00160 #if 0 00161 00164 const Node & operator [] (const Key & key) const 00165 { 00166 auto res = nodes.insert(std::make_pair(key, Node())); 00167 if (!res.second) 00168 doThrowException("TimeoutMap: " 00169 "attempt to re-insert existing key"); 00170 auto it = res.first; 00171 return it->second; 00172 } 00173 #endif 00174 00178 template<typename Callback> 00179 void expire(const Callback & callback, Date now = Date::now()) 00180 { 00181 // Look for loss timeout expiries 00182 for (auto it = timeouts.begin(), end = timeouts.end(); 00183 it != end && it->first <= now; /* no inc */) { 00184 auto it2 = it; 00185 auto expired = it->second; 00186 Date newExpiry = callback(expired->first, expired->second); 00187 ++it; 00188 if (newExpiry != Date()) { 00189 auto tit = expired->second.timeoutIt; 00190 timeouts.erase(tit); 00191 expired->second.timeoutIt 00192 = timeouts.insert(make_pair(newExpiry, expired)); 00193 if (newExpiry < earliest) earliest = newExpiry; 00194 } else { 00195 erase(expired); 00196 } 00197 } 00198 } 00199 00201 void expire(Date now = Date::now()) 00202 { 00203 // Look for loss timeout expiries 00204 for (auto it = timeouts.begin(), end = timeouts.end(); 00205 it != end && it->first <= now; /* no inc */) { 00206 auto expired = it->second; 00207 ++it; 00208 erase(expired); 00209 } 00210 } 00211 00212 typedef std::map<Key, Node> Nodes; 00213 Nodes nodes; 00214 00216 typedef std::multimap<Date, typename Nodes::iterator> Timeouts; 00217 Timeouts timeouts; 00218 00219 // Date of the earliest timeout 00220 Date earliest; 00221 00222 struct Node : public Value { 00223 Node() {} 00224 Node(const Value & val, Date timeout) 00225 : Value(val), timeout(timeout) 00226 { 00227 } 00228 00229 Node(Value && val, Date timeout) 00230 : Value(val), timeout(timeout) 00231 { 00232 } 00233 00234 Date timeout; 00235 typename Timeouts::iterator timeoutIt; 00236 }; 00237 00238 typedef typename Nodes::const_iterator const_iterator; 00239 typedef typename Nodes::iterator iterator; 00240 00241 bool count(const Key & key) const 00242 { 00243 return nodes.count(key); 00244 } 00245 00246 Value get(const Key & key) const 00247 { 00248 auto it = find(key); 00249 if (it == end()) return Value(); 00250 return it->second; 00251 } 00252 00253 iterator find(const Key & key) 00254 { 00255 return nodes.find(key); 00256 } 00257 00258 const_iterator find(const Key & key) const 00259 { 00260 return nodes.find(key); 00261 } 00262 00263 iterator begin() 00264 { 00265 return nodes.begin(); 00266 } 00267 00268 iterator end() 00269 { 00270 return nodes.end(); 00271 } 00272 00273 const_iterator begin() const 00274 { 00275 return nodes.begin(); 00276 } 00277 00278 const_iterator end() const 00279 { 00280 return nodes.end(); 00281 } 00282 00286 bool erase(const Key & key) 00287 { 00288 auto it = nodes.find(key); 00289 if (it == nodes.end()) return false; 00290 erase(it); 00291 return true; 00292 } 00293 00294 void erase(const typename Nodes::iterator & it) 00295 { 00296 if (it == nodes.end()) 00297 doThrowException("erasing with invalid iterator"); 00298 auto tit = it->second.timeoutIt; 00299 nodes.erase(it); 00300 timeouts.erase(tit); 00301 if (timeouts.empty()) 00302 earliest = Date::positiveInfinity(); 00303 else earliest = timeouts.begin()->first; 00304 } 00305 00306 void updateTimeout(const iterator & it, Date timeout) 00307 { 00308 if (it == nodes.end()) 00309 throw ML::Exception("attempt to update wrong timeout"); 00310 00311 auto & tit = it->second.timeoutIt; 00312 timeouts.erase(tit); 00313 tit = timeouts.insert(std::make_pair(timeout, it)); 00314 earliest = timeouts.begin()->first; 00315 } 00316 00317 size_t size() const 00318 { 00319 return nodes.size(); 00320 } 00321 00322 bool empty() const 00323 { 00324 return nodes.empty(); 00325 } 00326 00327 void clear() 00328 { 00329 timeouts.clear(); 00330 nodes.clear(); 00331 earliest = Date::positiveInfinity(); 00332 } 00333 }; 00334 00335 00336 } // namespace Datacratic 00337 00338 00339 #endif /* __router__timeout_map_h__ */