Mercurial > public > mercurial-scm > hg

comparison mercurial/revlog.py @ 16803:107a3270a24a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
cleanup: use the deque type where appropriate There have been quite a few places where we pop elements off the front of a list. This can turn O(n) algorithms into something more like O(n**2). Python has provided a deque type that can do this efficiently since at least 2.4. As an example of the difference a deque can make, it improves perfancestors performance on a Linux repo from 0.50 seconds to 0.36.
author Bryan O'Sullivan <bryano@fb.com>
date Tue, 15 May 2012 10:46:23 -0700
parents 2631cd5dd244
children cafd8a8fb713
comparison
equal deleted inserted replaced
16802:7e5d94381cd1 16803:107a3270a24a
13 13
14 # import stuff from node for others to import from revlog 14 # import stuff from node for others to import from revlog
15 from node import bin, hex, nullid, nullrev 15 from node import bin, hex, nullid, nullrev
16 from i18n import _ 16 from i18n import _
17 import ancestor, mdiff, parsers, error, util, dagutil 17 import ancestor, mdiff, parsers, error, util, dagutil
18 import struct, zlib, errno 18 import struct, zlib, errno, collections
19 19
20 _pack = struct.pack 20 _pack = struct.pack
21 _unpack = struct.unpack 21 _unpack = struct.unpack
22 _compress = zlib.compress 22 _compress = zlib.compress
23 _decompress = zlib.decompress 23 _decompress = zlib.decompress
360 360
361 def reachable(self, node, stop=None): 361 def reachable(self, node, stop=None):
362 """return the set of all nodes ancestral to a given node, including 362 """return the set of all nodes ancestral to a given node, including
363 the node itself, stopping when stop is matched""" 363 the node itself, stopping when stop is matched"""
364 reachable = set((node,)) 364 reachable = set((node,))
365 visit = [node] 365 visit = collections.deque([node])
366 if stop: 366 if stop:
367 stopn = self.rev(stop) 367 stopn = self.rev(stop)
368 else: 368 else:
369 stopn = 0 369 stopn = 0
370 while visit: 370 while visit:
371 n = visit.pop(0) 371 n = visit.popleft()
372 if n == stop: 372 if n == stop:
373 continue 373 continue
374 if n == nullid: 374 if n == nullid:
375 continue 375 continue
376 for p in self.parents(n): 376 for p in self.parents(n):
387 Yield a sequence of revision numbers starting with the parents 387 Yield a sequence of revision numbers starting with the parents
388 of each revision in revs, i.e., each revision is *not* considered 388 of each revision in revs, i.e., each revision is *not* considered
389 an ancestor of itself. Results are in breadth-first order: 389 an ancestor of itself. Results are in breadth-first order:
390 parents of each rev in revs, then parents of those, etc. Result 390 parents of each rev in revs, then parents of those, etc. Result
391 does not include the null revision.""" 391 does not include the null revision."""
392 visit = list(revs) 392 visit = collections.deque(revs)
393 seen = set([nullrev]) 393 seen = set([nullrev])
394 while visit: 394 while visit:
395 for parent in self.parentrevs(visit.pop(0)): 395 for parent in self.parentrevs(visit.popleft()):
396 if parent not in seen: 396 if parent not in seen:
397 visit.append(parent) 397 visit.append(parent)
398 seen.add(parent) 398 seen.add(parent)
399 yield parent 399 yield parent
400 400
445 has.add(nullrev) 445 has.add(nullrev)
446 has.update(common) 446 has.update(common)
447 447
448 # take all ancestors from heads that aren't in has 448 # take all ancestors from heads that aren't in has
449 missing = set() 449 missing = set()
450 visit = [r for r in heads if r not in has] 450 visit = collections.deque(r for r in heads if r not in has)
451 while visit: 451 while visit:
452 r = visit.pop(0) 452 r = visit.popleft()
453 if r in missing: 453 if r in missing:
454 continue 454 continue
455 else: 455 else:
456 missing.add(r) 456 missing.add(r)
457 for p in self.parentrevs(r): 457 for p in self.parentrevs(r):