equal
deleted
inserted
replaced
1238 new head node. |
1238 new head node. |
1239 |
1239 |
1240 Items in the cache can be inserted with an optional "cost" value. This is |
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 |
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. |
1242 for the total cost of all items presently in the cache. |
|
1243 |
|
1244 The cache can also define a maximum cost. If a cache insertion would |
|
1245 cause the total cost of the cache to go beyond the maximum cost limit, |
|
1246 nodes will be evicted to make room for the new code. This can be used |
|
1247 to e.g. set a max memory limit and associate an estimated bytes size |
|
1248 cost to each item in the cache. By default, no maximum cost is enforced. |
1243 """ |
1249 """ |
1244 def __init__(self, max): |
1250 def __init__(self, max, maxcost=0): |
1245 self._cache = {} |
1251 self._cache = {} |
1246 |
1252 |
1247 self._head = head = _lrucachenode() |
1253 self._head = head = _lrucachenode() |
1248 head.prev = head |
1254 head.prev = head |
1249 head.next = head |
1255 head.next = head |
1250 self._size = 1 |
1256 self._size = 1 |
1251 self.capacity = max |
1257 self.capacity = max |
1252 self.totalcost = 0 |
1258 self.totalcost = 0 |
|
1259 self.maxcost = maxcost |
1253 |
1260 |
1254 def __len__(self): |
1261 def __len__(self): |
1255 return len(self._cache) |
1262 return len(self._cache) |
1256 |
1263 |
1257 def __contains__(self, k): |
1264 def __contains__(self, k): |
1277 self.totalcost -= node.cost |
1284 self.totalcost -= node.cost |
1278 node.value = v |
1285 node.value = v |
1279 node.cost = cost |
1286 node.cost = cost |
1280 self.totalcost += cost |
1287 self.totalcost += cost |
1281 self._movetohead(node) |
1288 self._movetohead(node) |
|
1289 |
|
1290 if self.maxcost: |
|
1291 self._enforcecostlimit() |
|
1292 |
1282 return |
1293 return |
1283 |
1294 |
1284 if self._size < self.capacity: |
1295 if self._size < self.capacity: |
1285 node = self._addcapacity() |
1296 node = self._addcapacity() |
1286 else: |
1297 else: |
1299 self._cache[k] = node |
1310 self._cache[k] = node |
1300 # And mark it as newest entry. No need to adjust order since it |
1311 # And mark it as newest entry. No need to adjust order since it |
1301 # is already self._head.prev. |
1312 # is already self._head.prev. |
1302 self._head = node |
1313 self._head = node |
1303 |
1314 |
|
1315 if self.maxcost: |
|
1316 self._enforcecostlimit() |
|
1317 |
1304 def __setitem__(self, k, v): |
1318 def __setitem__(self, k, v): |
1305 self.insert(k, v) |
1319 self.insert(k, v) |
1306 |
1320 |
1307 def __delitem__(self, k): |
1321 def __delitem__(self, k): |
1308 node = self._cache.pop(k) |
1322 node = self._cache.pop(k) |
1329 n.markempty() |
1343 n.markempty() |
1330 n = n.next |
1344 n = n.next |
1331 |
1345 |
1332 self._cache.clear() |
1346 self._cache.clear() |
1333 |
1347 |
1334 def copy(self, capacity=None): |
1348 def copy(self, capacity=None, maxcost=0): |
1335 """Create a new cache as a copy of the current one. |
1349 """Create a new cache as a copy of the current one. |
1336 |
1350 |
1337 By default, the new cache has the same capacity as the existing one. |
1351 By default, the new cache has the same capacity as the existing one. |
1338 But, the cache capacity can be changed as part of performing the |
1352 But, the cache capacity can be changed as part of performing the |
1339 copy. |
1353 copy. |
1341 Items in the copy have an insertion/access order matching this |
1355 Items in the copy have an insertion/access order matching this |
1342 instance. |
1356 instance. |
1343 """ |
1357 """ |
1344 |
1358 |
1345 capacity = capacity or self.capacity |
1359 capacity = capacity or self.capacity |
1346 result = lrucachedict(capacity) |
1360 maxcost = maxcost or self.maxcost |
|
1361 result = lrucachedict(capacity, maxcost=maxcost) |
1347 |
1362 |
1348 # We copy entries by iterating in oldest-to-newest order so the copy |
1363 # We copy entries by iterating in oldest-to-newest order so the copy |
1349 # has the correct ordering. |
1364 # has the correct ordering. |
1350 |
1365 |
1351 # Find the first non-empty entry. |
1366 # Find the first non-empty entry. |
1442 node.prev = head.prev |
1457 node.prev = head.prev |
1443 node.next = head |
1458 node.next = head |
1444 head.prev = node |
1459 head.prev = node |
1445 self._size += 1 |
1460 self._size += 1 |
1446 return node |
1461 return node |
|
1462 |
|
1463 def _enforcecostlimit(self): |
|
1464 # This should run after an insertion. It should only be called if total |
|
1465 # cost limits are being enforced. |
|
1466 # The most recently inserted node is never evicted. |
|
1467 while len(self) > 1 and self.totalcost > self.maxcost: |
|
1468 self.popoldest() |
1447 |
1469 |
1448 def lrucachefunc(func): |
1470 def lrucachefunc(func): |
1449 '''cache most recent results of function calls''' |
1471 '''cache most recent results of function calls''' |
1450 cache = {} |
1472 cache = {} |
1451 order = collections.deque() |
1473 order = collections.deque() |