This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4501

util: add a popoldest() method to lrucachedict
ClosedPublic

Authored by indygreg on Sep 6 2018, 9:17 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGbd9d3a89f07b: util: add a popoldest() method to lrucachedict
Summary

This allows consumers to prune the oldest item from the cache. This
could be useful for e.g. a consumer that wishes for the size of
items tracked by the cache to remain under a high water mark.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

indygreg created this revision.Sep 6 2018, 9:17 PM
Closed by commit rHGbd9d3a89f07b: util: add a popoldest() method to lrucachedict (authored by indygreg). · Explain WhySep 12 2018, 10:52 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/util.py (22 lines)
Mtests/test-lrucachedict.py (25 lines)

Diff 10940

mercurial/util.py

# We could potentially skip the first N items when decreasing capacity. # We could potentially skip the first N items when decreasing capacity.
# But let's keep it simple unless it is a performance problem. # But let's keep it simple unless it is a performance problem.
for i in range(len(self._cache)): for i in range(len(self._cache)):
result[n.key] = n.value result[n.key] = n.value
n = n.prev n = n.prev
return result return result
def popoldest(self):
"""Remove the oldest item from the cache.
Returns the (key, value) describing the removed cache entry.
"""
if not self._cache:
return
# Walk the linked list backwards starting at tail node until we hit
# a non-empty node.
n = self._head.prev
while n.key is _notset:
n = n.prev
key, value = n.key, n.value
# And remove it from the cache and mark it as empty.
del self._cache[n.key]
n.markempty()
return key, value
def _movetohead(self, node): def _movetohead(self, node):
"""Mark a node as the newest, making it the new head. """Mark a node as the newest, making it the new head.
When a node is accessed, it becomes the freshest entry in the LRU When a node is accessed, it becomes the freshest entry in the LRU
list, which is denoted by self._head. list, which is denoted by self._head.
Visually, let's make ``N`` the new head node (* denotes head): Visually, let's make ``N`` the new head node (* denotes head):

tests/test-lrucachedict.py

self.assertIn(key, dc) self.assertIn(key, dc)
self.assertEqual(dc[key], 'v%s' % key) self.assertEqual(dc[key], 'v%s' % key)
# Original should remain unchanged. # Original should remain unchanged.
for key in ('a', 'b', 'c', 'd'): for key in ('a', 'b', 'c', 'd'):
self.assertIn(key, d) self.assertIn(key, d)
self.assertEqual(d[key], 'v%s' % key) self.assertEqual(d[key], 'v%s' % key)
def testpopoldest(self):
d = util.lrucachedict(4)
d['a'] = 'va'
d['b'] = 'vb'
self.assertEqual(len(d), 2)
self.assertEqual(d.popoldest(), ('a', 'va'))
self.assertEqual(len(d), 1)
self.assertEqual(d.popoldest(), ('b', 'vb'))
self.assertEqual(len(d), 0)
self.assertIsNone(d.popoldest())
d['a'] = 'va'
d['b'] = 'vb'
d['c'] = 'vc'
d['d'] = 'vd'
self.assertEqual(d.popoldest(), ('a', 'va'))
self.assertEqual(len(d), 3)
for key in ('b', 'c', 'd'):
self.assertEqual(d[key], 'v%s' % key)
d['a'] = 'va'
self.assertEqual(d.popoldest(), ('b', 'vb'))
if __name__ == '__main__': if __name__ == '__main__':
silenttestrunner.main(__name__) silenttestrunner.main(__name__)