from bup.helpers import *
-def merge_indexes(out, r1, r2):
- for e in index.MergeIter([r1, r2]):
- # FIXME: shouldn't we remove deleted entries eventually? When?
- out.add_ixentry(e)
-
-
class IterHelper:
def __init__(self, l):
self.i = iter(l)
log('check: before merging: newfile\n')
check_index(wr)
mi = index.Writer(indexfile)
- merge_indexes(mi, ri, wr)
+
+ for e in index.merge(ri, wr):
+ # FIXME: shouldn't we remove deleted entries eventually? When?
+ mi.add_ixentry(e)
+
ri.close()
mi.close()
wr.close()
bup repositories are in Git format. This library allows us to
interact with the Git data structures.
"""
-import os, sys, zlib, time, subprocess, struct, stat, re, tempfile, heapq
+import os, sys, zlib, time, subprocess, struct, stat, re, tempfile
from bup.helpers import *
from bup import _helpers, path
def idxmerge(idxlist, final_progress=True):
"""Generate a list of all the objects reachable in a PackIdxList."""
- total = sum(len(i) for i in idxlist)
- iters = (iter(i) for i in idxlist)
- heap = [(next(it), it) for it in iters]
- heapq.heapify(heap)
- count = 0
- last = None
- while heap:
- if (count % 10024) == 0:
- progress('Reading indexes: %.2f%% (%d/%d)\r'
- % (count*100.0/total, count, total))
- (e, it) = heap[0]
- if e != last:
- yield e
- last = e
- count += 1
- e = next(it)
- if e:
- heapq.heapreplace(heap, (e, it))
- else:
- heapq.heappop(heap)
- if final_progress:
- log('Reading indexes: %.2f%% (%d/%d), done.\n' % (100, total, total))
+ def pfunc(count, total):
+ progress('Reading indexes: %.2f%% (%d/%d)\r'
+ % (count*100.0/total, count, total))
+ def pfinal(count, total):
+ if final_progress:
+ log('Reading indexes: %.2f%% (%d/%d), done.\n' % (100, total, total))
+ return merge_iter(idxlist, 10024, pfunc, pfinal)
def _make_objcache():
"""Helper functions and classes for bup."""
import sys, os, pwd, subprocess, errno, socket, select, mmap, stat, re
+import heapq, operator
from bup import _version
# This function should really be in helpers, not in bup.options. But we
return None
+def merge_iter(iters, pfreq, pfunc, pfinal, key=None):
+ if key:
+ samekey = lambda e, pe: getattr(e, key) == getattr(pe, key, None)
+ else:
+ samekey = operator.eq
+ count = 0
+ total = sum(len(it) for it in iters)
+ iters = (iter(it) for it in iters)
+ heap = ((next(it),it) for it in iters)
+ heap = [(e,it) for e,it in heap if e]
+
+ heapq.heapify(heap)
+ pe = None
+ while heap:
+ if not count % pfreq:
+ pfunc(count, total)
+ e, it = heap[0]
+ if not samekey(e, pe):
+ pe = e
+ yield e
+ count += 1
+ try:
+ e = it.next() # Don't use next() function, it's too expensive
+ except StopIteration:
+ heapq.heappop(heap) # remove current
+ else:
+ heapq.heapreplace(heap, (e, it)) # shift current to new location
+ pfinal(count, total)
+
+
def unlink(f):
"""Delete a file at path 'f' if it currently exists.
return not self.ctime
def __cmp__(a, b):
- return (cmp(a.name, b.name)
- or -cmp(a.is_valid(), b.is_valid())
- or -cmp(a.is_fake(), b.is_fake()))
+ return (cmp(b.name, a.name)
+ or cmp(a.is_valid(), b.is_valid())
+ or cmp(a.is_fake(), b.is_fake()))
def write(self, f):
f.write(self.basename + '\0' + self.packed())
paths.sort(reverse=True)
return paths
-
-class MergeIter:
- def __init__(self, iters):
- self.iters = iters
-
- def __len__(self):
- # FIXME: doesn't remove duplicated entries between iters.
- # That only happens for parent directories, but will mean the
- # actual iteration returns fewer entries than this function counts.
- return sum(len(it) for it in self.iters)
-
- def __iter__(self):
- total = len(self)
- l = [iter(it) for it in self.iters]
- l = [(next(it),it) for it in l]
- l = filter(lambda x: x[0], l)
- count = 0
- lastname = None
- while l:
- if not (count % 1024):
- progress('bup: merging indexes (%d/%d)\r' % (count, total))
- l.sort()
- (e,it) = l.pop()
- if not e:
- continue
- if e.name != lastname:
- yield e
- lastname = e.name
- n = next(it)
- if n:
- l.append((n,it))
- count += 1
+def merge(*iters):
+ def pfunc(count, total):
+ progress('bup: merging indexes (%d/%d)\r' % (count, total))
+ def pfinal(count, total):
log('bup: merging indexes (%d/%d), done.\n' % (count, total))
+ return merge_iter(iters, 1024, pfunc, pfinal, key='name')
r3all = [e.name for e in r3]
WVPASSEQ(r3all,
['/a/c/n/3', '/a/c/n/', '/a/c/', '/a/', '/'])
- m = index.MergeIter([r2,r1,r3])
- all = [e.name for e in m]
+ all = [e.name for e in index.merge(r2, r1, r3)]
WVPASSEQ(all,
['/a/c/n/3', '/a/c/n/', '/a/c/',
'/a/b/x', '/a/b/n/2', '/a/b/n/', '/a/b/c',
print [hex(e.flags) for e in r1]
WVPASSEQ([e.name for e in r1 if e.is_valid()], r1all)
WVPASSEQ([e.name for e in r1 if not e.is_valid()], [])
- WVPASSEQ([e.name for e in m if not e.is_valid()],
+ WVPASSEQ([e.name for e in index.merge(r2, r1, r3) if not e.is_valid()],
['/a/c/n/3', '/a/c/n/', '/a/c/',
'/a/b/n/2', '/a/b/n/', '/a/b/', '/a/', '/'])
expect_invalid = ['/'] + r2all + r3all
expect_real = (set(r1all) - set(r2all) - set(r3all)) \
| set(['/a/b/n/2', '/a/c/n/3'])
- dump(m)
- for e in m:
+ dump(index.merge(r2, r1, r3))
+ for e in index.merge(r2, r1, r3):
print e.name, hex(e.flags), e.ctime
eiv = e.name in expect_invalid
er = e.name in expect_real
WVPASSEQ(eiv, not e.is_valid())
WVPASSEQ(er, e.is_real())
fake_validate(r2, r3)
- dump(m)
- WVPASSEQ([e.name for e in m if not e.is_valid()], [])
+ dump(index.merge(r2, r1, r3))
+ WVPASSEQ([e.name for e in index.merge(r2, r1, r3) if not e.is_valid()], [])
- e = eget(m, '/a/b/c')
+ e = eget(index.merge(r2, r1, r3), '/a/b/c')
e.invalidate()
e.repack()
- dump(m)
- WVPASSEQ([e.name for e in m if not e.is_valid()],
+ dump(index.merge(r2, r1, r3))
+ WVPASSEQ([e.name for e in index.merge(r2, r1, r3) if not e.is_valid()],
['/a/b/c', '/a/b/', '/a/', '/'])
projects / bup.git / commitdiff