root/galaxy-central/eggs/Routes-1.12.3-py2.6.egg/routes/lru.py

リビジョン 3, 1.9 KB (コミッタ: kohda, 14 年 前)

Install Unix tools  http://hannonlab.cshl.edu/galaxy_unix_tools/galaxy.html

行番号 
1"""LRU caching class and decorator"""
2import threading
3
4_marker = object()
5
6class LRUCache(object):
7    def __init__(self, size):
8        """ Implements a psueudo-LRU algorithm (CLOCK) """
9        if size < 1:
10            raise ValueError('size must be >1')
11        self.clock = []
12        for i in xrange(0, size):
13            self.clock.append({'key':_marker, 'ref':False})
14        self.size = size
15        self.maxpos = size - 1
16        self.hand = 0
17        self.data = {}
18        self.lock = threading.Lock()
19   
20    def __contains__(self, key):
21        return key in self.data
22
23    def __getitem__(self, key, default=None):
24        try:
25            datum = self.data[key]
26        except KeyError:
27            return default
28        pos, val = datum
29        self.clock[pos]['ref'] = True
30        hand = pos + 1
31        if hand > self.maxpos:
32            hand = 0
33        self.hand = hand
34        return val
35
36    def __setitem__(self, key, val, _marker=_marker):
37        hand = self.hand
38        maxpos = self.maxpos
39        clock = self.clock
40        data = self.data
41        lock = self.lock
42
43        end = hand - 1
44        if end < 0:
45            end = maxpos
46
47        while 1:
48            current = clock[hand]
49            ref = current['ref']
50            if ref is True:
51                current['ref'] = False
52                hand = hand + 1
53                if hand > maxpos:
54                    hand = 0
55            elif ref is False or hand == end:
56                lock.acquire()
57                try:
58                    oldkey = current['key']
59                    if oldkey in data:
60                        del data[oldkey]
61                    current['key'] = key
62                    current['ref'] = True
63                    data[key] = (hand, val)
64                    hand += 1
65                    if hand > maxpos:
66                        hand = 0
67                    self.hand = hand
68                finally:
69                    lock.release()
70                break
Note: リポジトリブラウザについてのヘルプは TracBrowser を参照してください。