Back to index

obnam  1.1
checksumtree.py
Go to the documentation of this file.
00001 # Copyright 2010  Lars Wirzenius
00002 # 
00003 # This program is free software: you can redistribute it and/or modify
00004 # it under the terms of the GNU General Public License as published by
00005 # the Free Software Foundation, either version 3 of the License, or
00006 # (at your option) any later version.
00007 # 
00008 # This program is distributed in the hope that it will be useful,
00009 # but WITHOUT ANY WARRANTY; without even the implied warranty of
00010 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00011 # GNU General Public License for more details.
00012 # 
00013 # You should have received a copy of the GNU General Public License
00014 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
00015 
00016 
00017 import struct
00018 import tracing
00019 
00020 import obnamlib
00021 
00022 
00023 class ChecksumTree(obnamlib.RepositoryTree):
00024 
00025     '''Repository map of checksum to integer id.
00026 
00027     The checksum might be, for example, an MD5 one (as returned by
00028     hashlib.md5().digest()). The id would be a chunk id.
00029 
00030     '''
00031 
00032     def __init__(self, fs, name, checksum_length, node_size, 
00033                  upload_queue_size, lru_size, hooks):
00034         tracing.trace('new ChecksumTree name=%s' % name)
00035         self.fmt = '!%dsQQ' % checksum_length
00036         key_bytes = len(self.key('', 0, 0))
00037         obnamlib.RepositoryTree.__init__(self, fs, name, key_bytes, node_size, 
00038                                          upload_queue_size, lru_size, hooks)
00039         self.keep_just_one_tree = True
00040 
00041     def key(self, checksum, chunk_id, client_id):
00042         return struct.pack(self.fmt, checksum, chunk_id, client_id)
00043 
00044     def unkey(self, key):
00045         return struct.unpack(self.fmt, key)
00046 
00047     def add(self, checksum, chunk_id, client_id):
00048         tracing.trace('checksum=%s', repr(checksum))
00049         tracing.trace('chunk_id=%s', chunk_id)
00050         tracing.trace('client_id=%s', client_id)
00051         self.start_changes()
00052         key = self.key(checksum, chunk_id, client_id)
00053         self.tree.insert(key, '')
00054 
00055     def find(self, checksum):
00056         if self.init_forest() and self.forest.trees:
00057             minkey = self.key(checksum, 0, 0)
00058             maxkey = self.key(checksum, obnamlib.MAX_ID, obnamlib.MAX_ID)
00059             t = self.forest.trees[-1]
00060             pairs = t.lookup_range(minkey, maxkey)
00061             return [self.unkey(key)[1] for key, value in pairs]
00062         else:
00063             return []
00064 
00065     def remove(self, checksum, chunk_id, client_id):
00066         tracing.trace('checksum=%s', repr(checksum))
00067         tracing.trace('chunk_id=%s', chunk_id)
00068         tracing.trace('client_id=%s', client_id)
00069         self.start_changes()
00070         key = self.key(checksum, chunk_id, client_id)
00071         self.tree.remove_range(key, key)
00072 
00073     def chunk_is_used(self, checksum, chunk_id):
00074         '''Is a given chunk used by anyone?'''
00075         if self.init_forest() and self.forest.trees:
00076             minkey = self.key(checksum, chunk_id, 0)
00077             maxkey = self.key(checksum, chunk_id, obnamlib.MAX_ID)
00078             t = self.forest.trees[-1]
00079             return not t.range_is_empty(minkey, maxkey)
00080         else:
00081             return False
00082