Package translate :: Package misc :: Module lru
[hide private]
[frames] | no frames]

Source Code for Module translate.misc.lru

  1  #!/usr/bin/env python 
  2  # -*- coding: utf-8 -*- 
  3  # 
  4  # Copyright 2009 Zuza Software Foundation 
  5  # 
  6  # This file is part of translate. 
  7  # 
  8  # This program is free software; you can redistribute it and/or modify 
  9  # it under the terms of the GNU General Public License as published by 
 10  # the Free Software Foundation; either version 2 of the License, or 
 11  # (at your option) any later version. 
 12  # 
 13  # This program is distributed in the hope that it will be useful, 
 14  # but WITHOUT ANY WARRANTY; without even the implied warranty of 
 15  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 16  # GNU General Public License for more details. 
 17  # 
 18  # You should have received a copy of the GNU General Public License 
 19  # along with this program; if not, see <http://www.gnu.org/licenses/>. 
 20   
 21  from collections import deque 
 22  from weakref import WeakValueDictionary 
 23  import gc 
 24   
 25   
26 -class LRUCachingDict(WeakValueDictionary):
27 """Caching dictionary like object that discards the least recently 28 used objects when number of cached items exceeds maxsize. 29 30 cullsize is the fraction of items that will be discarded when 31 maxsize is reached. 32 """ 33
34 - def __init__(self, maxsize, cullsize=2, peakmult=10, aggressive_gc=True, *args, **kwargs):
35 self.cullsize = max(2, cullsize) 36 self.maxsize = max(cullsize, maxsize) 37 self.aggressive_gc = aggressive_gc 38 self.peakmult = peakmult 39 self.queue = deque() 40 WeakValueDictionary.__init__(self, *args, **kwargs)
41
42 - def cull(self):
43 """free memory by deleting old items from cache""" 44 # maximum cache size exceeded, cull old items 45 # 46 # note queue is the real cache but its size is boundless 47 # since it might have duplicate references. 48 # 49 # don't bother culling if queue is smaller than weakref, 50 # this means there are too many references outside the 51 # cache, culling won't free much memory (if any). 52 while len(self) >= self.maxsize <= len(self.queue): 53 cullsize = max(int(len(self.queue) / self.cullsize), 2) 54 try: 55 for i in xrange(cullsize): 56 self.queue.popleft() 57 except IndexError: 58 # queue is empty, bail out. 59 #FIXME: should we force garbage collection here too? 60 break 61 62 # call garbage collecter manually since objects 63 # with circular references take some time to get 64 # collected 65 if self.aggressive_gc: 66 rounds = min(max(int(self.aggressive_gc), 5), 50) 67 for i in xrange(rounds): 68 gc.collect() 69 else: 70 gc.collect()
71
72 - def __setitem__(self, key, value):
73 # check boundaries to minimiza duplicate references 74 while len(self.queue) and self.queue[0][0] == key: 75 # item at left end of queue pop it since it'll be appended 76 # to right 77 self.queue.popleft() 78 79 while len(self.queue) and self.queue[-1][0] == key: 80 # item at right end of queue pop it since it'll be 81 # appended again 82 self.queue.pop() 83 84 if len(self) >= self.maxsize or len(self.queue) >= self.maxsize * self.peakmult: 85 self.cull() 86 87 self.queue.append((key, value)) 88 WeakValueDictionary.__setitem__(self, key, value)
89
90 - def __getitem__(self, key):
91 value = WeakValueDictionary.__getitem__(self, key) 92 # check boundaries to minimiza duplicate references 93 while len(self.queue) > 0 and self.queue[0][0] == key: 94 # item at left end of queue pop it since it'll be appended 95 # to right 96 self.queue.popleft() 97 98 # only append if item is not at right end of queue 99 if not (len(self.queue) and self.queue[-1][0] == key): 100 if len(self) >= self.maxsize or len(self.queue) >= self.maxsize * self.peakmult: 101 self.cull() 102 self.queue.append((key, value)) 103 104 return value
105
106 - def __delitem__(self, key):
107 # can't efficiently find item in queue to delete, check 108 # boundaries. otherwise just wait till next cache purge 109 while len(self.queue) and self.queue[0][0] == key: 110 # item at left end of queue pop it since it'll be appended 111 # to right 112 self.queue.popleft() 113 114 while len(self.queue) and self.queue[-1][0] == key: 115 # item at right end of queue pop it since it'll be 116 # appended again 117 self.queue.pop() 118 119 return WeakValueDictionary.__delitem__(self, key)
120
121 - def clear(self):
122 self.queue.clear() 123 return WeakValueDictionary.clear(self)
124
125 - def setdefault(self, key, default):
126 if key not in self: 127 self[key] = default 128 129 return self[key]
130