1207 """A node in a doubly linked list. |
1207 """A node in a doubly linked list. |
1208 |
1208 |
1209 Holds a reference to nodes on either side as well as a key-value |
1209 Holds a reference to nodes on either side as well as a key-value |
1210 pair for the dictionary entry. |
1210 pair for the dictionary entry. |
1211 """ |
1211 """ |
1212 __slots__ = (u'next', u'prev', u'key', u'value') |
1212 __slots__ = (u'next', u'prev', u'key', u'value', u'cost') |
1213 |
1213 |
1214 def __init__(self): |
1214 def __init__(self): |
1215 self.next = None |
1215 self.next = None |
1216 self.prev = None |
1216 self.prev = None |
1217 |
1217 |
1218 self.key = _notset |
1218 self.key = _notset |
1219 self.value = None |
1219 self.value = None |
|
1220 self.cost = 0 |
1220 |
1221 |
1221 def markempty(self): |
1222 def markempty(self): |
1222 """Mark the node as emptied.""" |
1223 """Mark the node as emptied.""" |
1223 self.key = _notset |
1224 self.key = _notset |
|
1225 self.value = None |
|
1226 self.cost = 0 |
1224 |
1227 |
1225 class lrucachedict(object): |
1228 class lrucachedict(object): |
1226 """Dict that caches most recent accesses and sets. |
1229 """Dict that caches most recent accesses and sets. |
1227 |
1230 |
1228 The dict consists of an actual backing dict - indexed by original |
1231 The dict consists of an actual backing dict - indexed by original |
1231 |
1234 |
1232 The head node is the newest entry in the cache. If the cache is full, |
1235 The head node is the newest entry in the cache. If the cache is full, |
1233 we recycle head.prev and make it the new head. Cache accesses result in |
1236 we recycle head.prev and make it the new head. Cache accesses result in |
1234 the node being moved to before the existing head and being marked as the |
1237 the node being moved to before the existing head and being marked as the |
1235 new head node. |
1238 new head node. |
|
1239 |
|
1240 Items in the cache can be inserted with an optional "cost" value. This is |
|
1241 simply an integer that is specified by the caller. The cache can be queried |
|
1242 for the total cost of all items presently in the cache. |
1236 """ |
1243 """ |
1237 def __init__(self, max): |
1244 def __init__(self, max): |
1238 self._cache = {} |
1245 self._cache = {} |
1239 |
1246 |
1240 self._head = head = _lrucachenode() |
1247 self._head = head = _lrucachenode() |
1241 head.prev = head |
1248 head.prev = head |
1242 head.next = head |
1249 head.next = head |
1243 self._size = 1 |
1250 self._size = 1 |
1244 self.capacity = max |
1251 self.capacity = max |
|
1252 self.totalcost = 0 |
1245 |
1253 |
1246 def __len__(self): |
1254 def __len__(self): |
1247 return len(self._cache) |
1255 return len(self._cache) |
1248 |
1256 |
1249 def __contains__(self, k): |
1257 def __contains__(self, k): |
1259 def __getitem__(self, k): |
1267 def __getitem__(self, k): |
1260 node = self._cache[k] |
1268 node = self._cache[k] |
1261 self._movetohead(node) |
1269 self._movetohead(node) |
1262 return node.value |
1270 return node.value |
1263 |
1271 |
1264 def __setitem__(self, k, v): |
1272 def insert(self, k, v, cost=0): |
|
1273 """Insert a new item in the cache with optional cost value.""" |
1265 node = self._cache.get(k) |
1274 node = self._cache.get(k) |
1266 # Replace existing value and mark as newest. |
1275 # Replace existing value and mark as newest. |
1267 if node is not None: |
1276 if node is not None: |
|
1277 self.totalcost -= node.cost |
1268 node.value = v |
1278 node.value = v |
|
1279 node.cost = cost |
|
1280 self.totalcost += cost |
1269 self._movetohead(node) |
1281 self._movetohead(node) |
1270 return |
1282 return |
1271 |
1283 |
1272 if self._size < self.capacity: |
1284 if self._size < self.capacity: |
1273 node = self._addcapacity() |
1285 node = self._addcapacity() |
1275 # Grab the last/oldest item. |
1287 # Grab the last/oldest item. |
1276 node = self._head.prev |
1288 node = self._head.prev |
1277 |
1289 |
1278 # At capacity. Kill the old entry. |
1290 # At capacity. Kill the old entry. |
1279 if node.key is not _notset: |
1291 if node.key is not _notset: |
|
1292 self.totalcost -= node.cost |
1280 del self._cache[node.key] |
1293 del self._cache[node.key] |
1281 |
1294 |
1282 node.key = k |
1295 node.key = k |
1283 node.value = v |
1296 node.value = v |
|
1297 node.cost = cost |
|
1298 self.totalcost += cost |
1284 self._cache[k] = node |
1299 self._cache[k] = node |
1285 # And mark it as newest entry. No need to adjust order since it |
1300 # And mark it as newest entry. No need to adjust order since it |
1286 # is already self._head.prev. |
1301 # is already self._head.prev. |
1287 self._head = node |
1302 self._head = node |
1288 |
1303 |
|
1304 def __setitem__(self, k, v): |
|
1305 self.insert(k, v) |
|
1306 |
1289 def __delitem__(self, k): |
1307 def __delitem__(self, k): |
1290 node = self._cache.pop(k) |
1308 node = self._cache.pop(k) |
|
1309 self.totalcost -= node.cost |
1291 node.markempty() |
1310 node.markempty() |
1292 |
1311 |
1293 # Temporarily mark as newest item before re-adjusting head to make |
1312 # Temporarily mark as newest item before re-adjusting head to make |
1294 # this node the oldest item. |
1313 # this node the oldest item. |
1295 self._movetohead(node) |
1314 self._movetohead(node) |
1334 n = n.prev |
1354 n = n.prev |
1335 |
1355 |
1336 # We could potentially skip the first N items when decreasing capacity. |
1356 # We could potentially skip the first N items when decreasing capacity. |
1337 # But let's keep it simple unless it is a performance problem. |
1357 # But let's keep it simple unless it is a performance problem. |
1338 for i in range(len(self._cache)): |
1358 for i in range(len(self._cache)): |
1339 result[n.key] = n.value |
1359 result.insert(n.key, n.value, cost=n.cost) |
1340 n = n.prev |
1360 n = n.prev |
1341 |
1361 |
1342 return result |
1362 return result |
1343 |
1363 |
1344 def popoldest(self): |
1364 def popoldest(self): |
1357 |
1377 |
1358 key, value = n.key, n.value |
1378 key, value = n.key, n.value |
1359 |
1379 |
1360 # And remove it from the cache and mark it as empty. |
1380 # And remove it from the cache and mark it as empty. |
1361 del self._cache[n.key] |
1381 del self._cache[n.key] |
|
1382 self.totalcost -= n.cost |
1362 n.markempty() |
1383 n.markempty() |
1363 |
1384 |
1364 return key, value |
1385 return key, value |
1365 |
1386 |
1366 def _movetohead(self, node): |
1387 def _movetohead(self, node): |