author | Nishanth Amuluru <nishanth@fossee.in> |
Sat, 08 Jan 2011 11:20:57 +0530 | |
changeset 69 | c6bca38c1cbf |
permissions | -rw-r--r-- |
69
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
1 |
""" |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
2 |
This module contains multithread-safe cache implementations. |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
3 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
4 |
All Caches have |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
5 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
6 |
getorbuild(key, builder) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
7 |
delentry(key) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
8 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
9 |
methods and allow configuration when instantiating the cache class. |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
10 |
""" |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
11 |
from time import time as gettime |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
12 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
13 |
class BasicCache(object): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
14 |
def __init__(self, maxentries=128): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
15 |
self.maxentries = maxentries |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
16 |
self.prunenum = int(maxentries - maxentries/8) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
17 |
self._dict = {} |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
18 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
19 |
def clear(self): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
20 |
self._dict.clear() |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
21 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
22 |
def _getentry(self, key): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
23 |
return self._dict[key] |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
24 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
25 |
def _putentry(self, key, entry): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
26 |
self._prunelowestweight() |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
27 |
self._dict[key] = entry |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
28 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
29 |
def delentry(self, key, raising=False): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
30 |
try: |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
31 |
del self._dict[key] |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
32 |
except KeyError: |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
33 |
if raising: |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
34 |
raise |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
35 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
36 |
def getorbuild(self, key, builder): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
37 |
try: |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
38 |
entry = self._getentry(key) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
39 |
except KeyError: |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
40 |
entry = self._build(key, builder) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
41 |
self._putentry(key, entry) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
42 |
return entry.value |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
43 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
44 |
def _prunelowestweight(self): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
45 |
""" prune out entries with lowest weight. """ |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
46 |
numentries = len(self._dict) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
47 |
if numentries >= self.maxentries: |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
48 |
# evict according to entry's weight |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
49 |
items = [(entry.weight, key) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
50 |
for key, entry in self._dict.items()] |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
51 |
items.sort() |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
52 |
index = numentries - self.prunenum |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
53 |
if index > 0: |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
54 |
for weight, key in items[:index]: |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
55 |
# in MT situations the element might be gone |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
56 |
self.delentry(key, raising=False) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
57 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
58 |
class BuildcostAccessCache(BasicCache): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
59 |
""" A BuildTime/Access-counting cache implementation. |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
60 |
the weight of a value is computed as the product of |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
61 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
62 |
num-accesses-of-a-value * time-to-build-the-value |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
63 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
64 |
The values with the least such weights are evicted |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
65 |
if the cache maxentries threshold is superceded. |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
66 |
For implementation flexibility more than one object |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
67 |
might be evicted at a time. |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
68 |
""" |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
69 |
# time function to use for measuring build-times |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
70 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
71 |
def _build(self, key, builder): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
72 |
start = gettime() |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
73 |
val = builder() |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
74 |
end = gettime() |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
75 |
return WeightedCountingEntry(val, end-start) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
76 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
77 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
78 |
class WeightedCountingEntry(object): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
79 |
def __init__(self, value, oneweight): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
80 |
self._value = value |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
81 |
self.weight = self._oneweight = oneweight |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
82 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
83 |
def value(self): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
84 |
self.weight += self._oneweight |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
85 |
return self._value |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
86 |
value = property(value) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
87 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
88 |
class AgingCache(BasicCache): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
89 |
""" This cache prunes out cache entries that are too old. |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
90 |
""" |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
91 |
def __init__(self, maxentries=128, maxseconds=10.0): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
92 |
super(AgingCache, self).__init__(maxentries) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
93 |
self.maxseconds = maxseconds |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
94 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
95 |
def _getentry(self, key): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
96 |
entry = self._dict[key] |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
97 |
if entry.isexpired(): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
98 |
self.delentry(key) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
99 |
raise KeyError(key) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
100 |
return entry |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
101 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
102 |
def _build(self, key, builder): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
103 |
val = builder() |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
104 |
entry = AgingEntry(val, gettime() + self.maxseconds) |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
105 |
return entry |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
106 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
107 |
class AgingEntry(object): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
108 |
def __init__(self, value, expirationtime): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
109 |
self.value = value |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
110 |
self.weight = expirationtime |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
111 |
|
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
112 |
def isexpired(self): |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
113 |
t = gettime() |
c6bca38c1cbf
Added buildout stuff and made changes accordingly
Nishanth Amuluru <nishanth@fossee.in>
parents:
diff
changeset
|
114 |
return t >= self.weight |