lib/bup/midx.py

   1 import mmap
   2 from bup import _helpers
   3 from bup.helpers import *
   4
   5 MIDX_VERSION = 4
   6
   7 extract_bits = _helpers.extract_bits
   8 _total_searches = 0
   9 _total_steps = 0
  10
  11
  12 class PackMidx:
  13     """Wrapper which contains data from multiple index files.
  14     Multiple index (.midx) files constitute a wrapper around index (.idx) files
  15     and make it possible for bup to expand Git's indexing capabilities to vast
  16     amounts of files.
  17     """
  18     def __init__(self, filename):
  19         self.name = filename
  20         self.force_keep = False
  21         assert(filename.endswith('.midx'))
  22         self.map = mmap_read(open(filename))
  23         if str(self.map[0:4]) != 'MIDX':
  24             log('Warning: skipping: invalid MIDX header in %r\n' % filename)
  25             self.force_keep = True
  26             return self._init_failed()
  27         ver = struct.unpack('!I', self.map[4:8])[0]
  28         if ver < MIDX_VERSION:
  29             log('Warning: ignoring old-style (v%d) midx %r\n'
  30                 % (ver, filename))
  31             self.force_keep = False  # old stuff is boring
  32             return self._init_failed()
  33         if ver > MIDX_VERSION:
  34             log('Warning: ignoring too-new (v%d) midx %r\n'
  35                 % (ver, filename))
  36             self.force_keep = True  # new stuff is exciting
  37             return self._init_failed()
  38
  39         self.bits = _helpers.firstword(self.map[8:12])
  40         self.entries = 2**self.bits
  41         self.fanout = buffer(self.map, 12, self.entries*4)
  42         self.sha_ofs = 12 + self.entries*4
  43         self.nsha = nsha = self._fanget(self.entries-1)
  44         self.shatable = buffer(self.map, self.sha_ofs, nsha*20)
  45         self.which_ofs = self.sha_ofs + 20*nsha
  46         self.whichlist = buffer(self.map, self.which_ofs, nsha*4)
  47         self.idxnames = str(self.map[self.which_ofs + 4*nsha:]).split('\0')
  48
  49     def _init_failed(self):
  50         self.bits = 0
  51         self.entries = 1
  52         self.fanout = buffer('\0\0\0\0')
  53         self.shatable = buffer('\0'*20)
  54         self.idxnames = []
  55
  56     def _fanget(self, i):
  57         start = i*4
  58         s = self.fanout[start:start+4]
  59         return _helpers.firstword(s)
  60
  61     def _get(self, i):
  62         return str(self.shatable[i*20:(i+1)*20])
  63
  64     def _get_idx_i(self, i):
  65         return struct.unpack('!I', self.whichlist[i*4:(i+1)*4])[0]
  66
  67     def _get_idxname(self, i):
  68         return self.idxnames[self._get_idx_i(i)]
  69
  70     def exists(self, hash, want_source=False):
  71         """Return nonempty if the object exists in the index files."""
  72         global _total_searches, _total_steps
  73         _total_searches += 1
  74         want = str(hash)
  75         el = extract_bits(want, self.bits)
  76         if el:
  77             start = self._fanget(el-1)
  78             startv = el << (32-self.bits)
  79         else:
  80             start = 0
  81             startv = 0
  82         end = self._fanget(el)
  83         endv = (el+1) << (32-self.bits)
  84         _total_steps += 1   # lookup table is a step
  85         hashv = _helpers.firstword(hash)
  86         #print '(%08x) %08x %08x %08x' % (extract_bits(want, 32), startv, hashv, endv)
  87         while start < end:
  88             _total_steps += 1
  89             #print '! %08x %08x %08x   %d - %d' % (startv, hashv, endv, start, end)
  90             mid = start + (hashv-startv)*(end-start-1)/(endv-startv)
  91             #print '  %08x %08x %08x   %d %d %d' % (startv, hashv, endv, start, mid, end)
  92             v = self._get(mid)
  93             #print '    %08x' % self._num(v)
  94             if v < want:
  95                 start = mid+1
  96                 startv = _helpers.firstword(v)
  97             elif v > want:
  98                 end = mid
  99                 endv = _helpers.firstword(v)
 100             else: # got it!
 101                 return want_source and self._get_idxname(mid) or True
 102         return None
 103
 104     def __iter__(self):
 105         for i in xrange(self._fanget(self.entries-1)):
 106             yield buffer(self.shatable, i*20, 20)
 107
 108     def __len__(self):
 109         return int(self._fanget(self.entries-1))
 110
 111