diff options
author | bescoto <bescoto@2b77aa54-bcbc-44c9-a7ec-4f6cf2b41109> | 2003-02-12 16:24:08 +0000 |
---|---|---|
committer | bescoto <bescoto@2b77aa54-bcbc-44c9-a7ec-4f6cf2b41109> | 2003-02-12 16:24:08 +0000 |
commit | 61ef4309f5246529e09db428c2bfe5c3bb29a3a8 (patch) | |
tree | 921ee55e6911307a98bbf85c71f31746473f4099 /rdiff-backup/rdiff_backup | |
parent | adc9d7a9a9cd90c8d078b1276cfdad98d0303d07 (diff) | |
download | rdiff-backup-61ef4309f5246529e09db428c2bfe5c3bb29a3a8.tar.gz |
Added CachedIndexableProcessor to rorpiter
git-svn-id: http://svn.savannah.nongnu.org/svn/rdiff-backup/trunk@279 2b77aa54-bcbc-44c9-a7ec-4f6cf2b41109
Diffstat (limited to 'rdiff-backup/rdiff_backup')
-rw-r--r-- | rdiff-backup/rdiff_backup/rorpiter.py | 50 |
1 files changed, 49 insertions, 1 deletions
diff --git a/rdiff-backup/rdiff_backup/rorpiter.py b/rdiff-backup/rdiff_backup/rorpiter.py index f75d8e8..3849fdc 100644 --- a/rdiff-backup/rdiff_backup/rorpiter.py +++ b/rdiff-backup/rdiff_backup/rorpiter.py @@ -440,5 +440,53 @@ class CacheIndexable: def get(self, index): """Return element with index index from cache""" try: return self.cache_dict[index] - except KeyError: return None + except KeyError: + assert index > self.cache_indicies[0], index + return None + +class CachedIndexableProcessor: + """Reorder indicies, then feed into some function in order + + Use this class when you want to run some function on a stream of + objects in index order. However, the objects may be slightly out + of index order. This class will cache a certain number, and then + reorder them. + + An error is signaled if the indicies arrive too out of order. + + """ + def __init__(self, function, cache_size): + """CIP initializer. function is called on every elem.""" + self.function = function + self.cache_size = cache_size + self.cache_indicies = [] + self.cache_dict = {} + + def process(self, elem): + """Call CIP (and underlying self.function) on indexed elem""" + index = elem.index + self.cache_dict[index] = elem + if self.cache_indicies and index <= self.cache_indicies[-1]: + assert index > self.cache_indicies[0] + self.cache_indicies.append(index) + self.cache_indicies.sort() # Ack, n log n, should be log n!!! + else: self.cache_indicies.append(index) + + if len(self.cache_indicies) > self.cache_size: + first_index = self.cache_indicies[0] + first_elem = self.cache_dict[first_index] + del self.cache_indicies[0] + del self.cache_dict[first_index] + self.function(first_elem) + + __call__ = process + + def close(self): + """Flush cache by running function on remaining elems""" + while self.cache_indicies: + index = self.cache_indicies[0] + elem = self.cache_dict[index] + del self.cache_indicies[0] + del self.cache_dict[index] + self.function(elem) |