##// END OF EJS Templates
util: reimplement lrucachedict...
Gregory Szorc -
r27371:45d996a5 default
parent child Browse files
Show More
@@ -510,34 +510,178 b' class sortdict(dict):'
510 self._list.insert(index, key)
510 self._list.insert(index, key)
511 dict.__setitem__(self, key, val)
511 dict.__setitem__(self, key, val)
512
512
513 class _lrucachenode(object):
514 """A node in a doubly linked list.
515
516 Holds a reference to nodes on either side as well as a key-value
517 pair for the dictionary entry.
518 """
519 __slots__ = ('next', 'prev', 'key', 'value')
520
521 def __init__(self):
522 self.next = None
523 self.prev = None
524
525 self.key = _notset
526 self.value = None
527
528 def markempty(self):
529 """Mark the node as emptied."""
530 self.key = _notset
531
513 class lrucachedict(object):
532 class lrucachedict(object):
514 '''cache most recent gets from or sets to this dictionary'''
533 """Dict that caches most recent accesses and sets.
515 def __init__(self, maxsize):
534
535 The dict consists of an actual backing dict - indexed by original
536 key - and a doubly linked circular list defining the order of entries in
537 the cache.
538
539 The head node is the newest entry in the cache. If the cache is full,
540 we recycle head.prev and make it the new head. Cache accesses result in
541 the node being moved to before the existing head and being marked as the
542 new head node.
543
544 NOTE: construction of this class doesn't scale well if the cache size
545 is in the thousands. Avoid creating hundreds or thousands of instances
546 with large capacities.
547 """
548 def __init__(self, max):
516 self._cache = {}
549 self._cache = {}
517 self._maxsize = maxsize
550
518 self._order = collections.deque()
551 self._head = head = _lrucachenode()
552 head.prev = head
553 head.next = head
554 self._size = 1
555 self._capacity = max
556
557 def __len__(self):
558 return len(self._cache)
559
560 def __contains__(self, k):
561 return k in self._cache
519
562
520 def __getitem__(self, key):
563 def __iter__(self):
521 value = self._cache[key]
564 # We don't have to iterate in cache order, but why not.
522 self._order.remove(key)
565 n = self._head
523 self._order.append(key)
566 for i in range(len(self._cache)):
524 return value
567 yield n.key
568 n = n.next
569
570 def __getitem__(self, k):
571 node = self._cache[k]
572 self._movetohead(node)
573 return node.value
574
575 def __setitem__(self, k, v):
576 node = self._cache.get(k)
577 # Replace existing value and mark as newest.
578 if node is not None:
579 node.value = v
580 self._movetohead(node)
581 return
582
583 if self._size < self._capacity:
584 node = self._addcapacity()
585 else:
586 # Grab the last/oldest item.
587 node = self._head.prev
525
588
526 def __setitem__(self, key, value):
589 # At capacity. Kill the old entry.
527 if key not in self._cache:
590 if node.key is not _notset:
528 if len(self._cache) >= self._maxsize:
591 del self._cache[node.key]
529 del self._cache[self._order.popleft()]
592
530 else:
593 node.key = k
531 self._order.remove(key)
594 node.value = v
532 self._cache[key] = value
595 self._cache[k] = node
533 self._order.append(key)
596 # And mark it as newest entry. No need to adjust order since it
597 # is already self._head.prev.
598 self._head = node
534
599
535 def __contains__(self, key):
600 def __delitem__(self, k):
536 return key in self._cache
601 node = self._cache.pop(k)
602 node.markempty()
603
604 # Temporarily mark as newest item before re-adjusting head to make
605 # this node the oldest item.
606 self._movetohead(node)
607 self._head = node.next
608
609 # Additional dict methods.
610
611 def get(self, k, default=None):
612 try:
613 return self._cache[k]
614 except KeyError:
615 return default
537
616
538 def clear(self):
617 def clear(self):
618 n = self._head
619 while n.key is not _notset:
620 n.markempty()
621 n = n.next
622
539 self._cache.clear()
623 self._cache.clear()
540 self._order = collections.deque()
624
625 def _movetohead(self, node):
626 """Mark a node as the newest, making it the new head.
627
628 When a node is accessed, it becomes the freshest entry in the LRU
629 list, which is denoted by self._head.
630
631 Visually, let's make ``N`` the new head node (* denotes head):
632
633 previous/oldest <-> head <-> next/next newest
634
635 ----<->--- A* ---<->-----
636 | |
637 E <-> D <-> N <-> C <-> B
638
639 To:
640
641 ----<->--- N* ---<->-----
642 | |
643 E <-> D <-> C <-> B <-> A
644
645 This requires the following moves:
646
647 C.next = D (node.prev.next = node.next)
648 D.prev = C (node.next.prev = node.prev)
649 E.next = N (head.prev.next = node)
650 N.prev = E (node.prev = head.prev)
651 N.next = A (node.next = head)
652 A.prev = N (head.prev = node)
653 """
654 head = self._head
655 # C.next = D
656 node.prev.next = node.next
657 # D.prev = C
658 node.next.prev = node.prev
659 # N.prev = E
660 node.prev = head.prev
661 # N.next = A
662 # It is tempting to do just "head" here, however if node is
663 # adjacent to head, this will do bad things.
664 node.next = head.prev.next
665 # E.next = N
666 node.next.prev = node
667 # A.prev = N
668 node.prev.next = node
669
670 self._head = node
671
672 def _addcapacity(self):
673 """Add a node to the circular linked list.
674
675 The new node is inserted before the head node.
676 """
677 head = self._head
678 node = _lrucachenode()
679 head.prev.next = node
680 node.prev = head.prev
681 node.next = head
682 head.prev = node
683 self._size += 1
684 return node
541
685
542 def lrucachefunc(func):
686 def lrucachefunc(func):
543 '''cache most recent results of function calls'''
687 '''cache most recent results of function calls'''
@@ -34,5 +34,13 b' def test_lrucachedict():'
34 d.clear()
34 d.clear()
35 printifpresent(d, ['b', 'c', 'd', 'e', 'f'])
35 printifpresent(d, ['b', 'c', 'd', 'e', 'f'])
36
36
37 # Now test dicts that aren't full.
38 d = util.lrucachedict(4)
39 d['a'] = 1
40 d['b'] = 2
41 d['a']
42 d['b']
43 printifpresent(d, ['a', 'b'])
44
37 if __name__ == '__main__':
45 if __name__ == '__main__':
38 test_lrucachedict()
46 test_lrucachedict()
@@ -29,3 +29,7 b" d['f']: vf"
29 'd' in d: False
29 'd' in d: False
30 'e' in d: False
30 'e' in d: False
31 'f' in d: False
31 'f' in d: False
32 'a' in d: True
33 d['a']: 1
34 'b' in d: True
35 d['b']: 2
General Comments 0
You need to be logged in to leave comments. Login now