lib/bup/midx.py

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