OLD | NEW |
| (Empty) |
1 # Copyright 2013 The Chromium Authors. All rights reserved. | |
2 # Use of this source code is governed by a BSD-style license that can be | |
3 # found in the LICENSE file. | |
4 | |
5 """Defines a dictionary that can evict least recently used items.""" | |
6 | |
7 import collections | |
8 import json | |
9 | |
10 # Monkey patch collections to contain OrderedDict on python 2.6. | |
11 from third_party.chromium import python26_polyfill # pylint: disable=W0611 | |
12 | |
13 | |
14 class LRUDict(object): | |
15 """Dictionary that can evict least recently used items. | |
16 | |
17 Implemented as a wrapper around OrderedDict object. An OrderedDict stores | |
18 (key, value) pairs in order they are inserted and can effectively pop oldest | |
19 items. | |
20 | |
21 Can also store its state as *.json file on disk. | |
22 """ | |
23 | |
24 def __init__(self): | |
25 # Ordered key -> value mapping, newest items at the bottom. | |
26 self._items = collections.OrderedDict() | |
27 # True if was modified after loading. | |
28 self._dirty = True | |
29 | |
30 def __nonzero__(self): | |
31 """False if dict is empty.""" | |
32 return bool(self._items) | |
33 | |
34 def __len__(self): | |
35 """Number of items in the dict.""" | |
36 return len(self._items) | |
37 | |
38 def __contains__(self, key): | |
39 """True if |key| is in the dict.""" | |
40 return key in self._items | |
41 | |
42 @classmethod | |
43 def load(cls, state_file): | |
44 """Loads previously saved state and returns LRUDict in that state. | |
45 | |
46 Raises ValueError if state file is corrupted. | |
47 """ | |
48 try: | |
49 state = json.load(open(state_file, 'r')) | |
50 except (IOError, ValueError) as e: | |
51 raise ValueError('Broken state file %s: %s' % (state_file, e)) | |
52 | |
53 if not isinstance(state, list): | |
54 raise ValueError( | |
55 'Broken state file %s, should be json list' % (state_file,)) | |
56 | |
57 # Items are stored oldest to newest. Put them back in the same order. | |
58 lru = cls() | |
59 for pair in state: | |
60 if not isinstance(pair, (list, tuple)) or len(pair) != 2: | |
61 raise ValueError( | |
62 'Broken state file %s, expecting pairs: %s' % (state_file, pair)) | |
63 lru.add(pair[0], pair[1]) | |
64 | |
65 # Check for duplicate keys. | |
66 if len(lru) != len(state): | |
67 raise ValueError( | |
68 'Broken state file %s, found duplicate keys' % (state_file,)) | |
69 | |
70 # Now state from the file corresponds to state in the memory. | |
71 lru._dirty = False | |
72 return lru | |
73 | |
74 def save(self, state_file): | |
75 """Saves cache state to a file if it was modified.""" | |
76 if not self._dirty: | |
77 return False | |
78 | |
79 with open(state_file, 'wb') as f: | |
80 json.dump(self._items.items(), f, separators=(',',':')) | |
81 | |
82 self._dirty = False | |
83 return True | |
84 | |
85 def add(self, key, value): | |
86 """Adds or replaces a |value| for |key|, marks it as most recently used.""" | |
87 self._items.pop(key, None) | |
88 self._items[key] = value | |
89 self._dirty = True | |
90 | |
91 def batch_insert_oldest(self, items): | |
92 """Prepends list of |items| to the dict, marks them as least recently used. | |
93 | |
94 |items| is a list of (key, value) pairs to add. | |
95 | |
96 It's a very slow operation that completely rebuilds the dictionary. | |
97 """ | |
98 new_items = collections.OrderedDict() | |
99 | |
100 # Insert |items| first, so they became oldest. | |
101 for key, value in items: | |
102 new_items[key] = value | |
103 | |
104 # Insert the rest, be careful not to override keys from |items|. | |
105 for key, value in self._items.iteritems(): | |
106 if key not in new_items: | |
107 new_items[key] = value | |
108 | |
109 self._items = new_items | |
110 self._dirty = True | |
111 | |
112 def keys_set(self): | |
113 """Set of keys of items in this dict.""" | |
114 return set(self._items) | |
115 | |
116 def get(self, key, default=None): | |
117 """Returns value for |key| or |default| if not found.""" | |
118 return self._items.get(key, default) | |
119 | |
120 def touch(self, key): | |
121 """Marks |key| as most recently used. | |
122 | |
123 Raises KeyError if |key| is not in the dict. | |
124 """ | |
125 self._items[key] = self._items.pop(key) | |
126 self._dirty = True | |
127 | |
128 def pop(self, key): | |
129 """Removes item from the dict, returns its value. | |
130 | |
131 Raises KeyError if |key| is not in the dict. | |
132 """ | |
133 value = self._items.pop(key) | |
134 self._dirty = True | |
135 return value | |
136 | |
137 def pop_oldest(self): | |
138 """Removes oldest item from the dict and returns it as tuple (key, value). | |
139 | |
140 Raises KeyError if dict is empty. | |
141 """ | |
142 pair = self._items.popitem(last=False) | |
143 self._dirty = True | |
144 return pair | |
145 | |
146 def itervalues(self): | |
147 """Iterator over stored values in arbitrary order.""" | |
148 return self._items.itervalues() | |
OLD | NEW |