Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/revlog.py @ 8464:7af92e70bb25

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
revlog: use set instead of dict
author Benoit Boissinot <benoit.boissinot@ens-lyon.org>
date Sun, 17 May 2009 03:49:59 +0200
parents d1ca637b0773
children f9a80054dd3c
comparison
equal deleted inserted replaced
8463:43186df4bb8e 8464:7af92e70bb25
554 l = mdiff.patchedsize(l, self.chunk(x)) 554 l = mdiff.patchedsize(l, self.chunk(x))
555 return l 555 return l
556 """ 556 """
557 557
558 def reachable(self, node, stop=None): 558 def reachable(self, node, stop=None):
559 """return a hash of all nodes ancestral to a given node, including 559 """return the set of all nodes ancestral to a given node, including
560 the node itself, stopping when stop is matched""" 560 the node itself, stopping when stop is matched"""
561 reachable = {} 561 reachable = set((node,))
562 visit = [node] 562 visit = [node]
563 reachable[node] = 1
564 if stop: 563 if stop:
565 stopn = self.rev(stop) 564 stopn = self.rev(stop)
566 else: 565 else:
567 stopn = 0 566 stopn = 0
568 while visit: 567 while visit:
573 continue 572 continue
574 for p in self.parents(n): 573 for p in self.parents(n):
575 if self.rev(p) < stopn: 574 if self.rev(p) < stopn:
576 continue 575 continue
577 if p not in reachable: 576 if p not in reachable:
578 reachable[p] = 1 577 reachable.add(p)
579 visit.append(p) 578 visit.append(p)
580 return reachable 579 return reachable
581 580
582 def ancestors(self, *revs): 581 def ancestors(self, *revs):
583 'Generate the ancestors of revs using a breadth-first visit' 582 'Generate the ancestors of revs using a breadth-first visit'
676 heads = {} 675 heads = {}
677 else: 676 else:
678 heads = list(heads) 677 heads = list(heads)
679 if not heads: 678 if not heads:
680 return nonodes 679 return nonodes
681 ancestors = {} 680 ancestors = set()
682 # Turn heads into a dictionary so we can remove 'fake' heads. 681 # Turn heads into a dictionary so we can remove 'fake' heads.
683 # Also, later we will be using it to filter out the heads we can't 682 # Also, later we will be using it to filter out the heads we can't
684 # find from roots. 683 # find from roots.
685 heads = dict.fromkeys(heads, 0) 684 heads = dict.fromkeys(heads, 0)
686 # Start at the top and keep marking parents until we're done. 685 # Start at the top and keep marking parents until we're done.
698 r = self.rev(n) 697 r = self.rev(n)
699 if r >= lowestrev: 698 if r >= lowestrev:
700 if n not in ancestors: 699 if n not in ancestors:
701 # If we are possibly a descendent of one of the roots 700 # If we are possibly a descendent of one of the roots
702 # and we haven't already been marked as an ancestor 701 # and we haven't already been marked as an ancestor
703 ancestors[n] = 1 # Mark as ancestor 702 ancestors.add(n) # Mark as ancestor
704 # Add non-nullid parents to list of nodes to tag. 703 # Add non-nullid parents to list of nodes to tag.
705 nodestotag.update([p for p in self.parents(n) if 704 nodestotag.update([p for p in self.parents(n) if
706 p != nullid]) 705 p != nullid])
707 elif n in heads: # We've seen it before, is it a fake head? 706 elif n in heads: # We've seen it before, is it a fake head?
708 # So it is, real heads should not be the ancestors of 707 # So it is, real heads should not be the ancestors of
811 start = nullid 810 start = nullid
812 if stop is None: 811 if stop is None:
813 stop = [] 812 stop = []
814 stoprevs = set([self.rev(n) for n in stop]) 813 stoprevs = set([self.rev(n) for n in stop])
815 startrev = self.rev(start) 814 startrev = self.rev(start)
816 reachable = {startrev: 1} 815 reachable = set((startrev,))
817 heads = {startrev: 1} 816 heads = set((startrev,))
818 817
819 parentrevs = self.parentrevs 818 parentrevs = self.parentrevs
820 for r in xrange(startrev + 1, len(self)): 819 for r in xrange(startrev + 1, len(self)):
821 for p in parentrevs(r): 820 for p in parentrevs(r):
822 if p in reachable: 821 if p in reachable:
823 if r not in stoprevs: 822 if r not in stoprevs:
824 reachable[r] = 1 823 reachable.add(r)
825 heads[r] = 1 824 heads.add(r)
826 if p in heads and p not in stoprevs: 825 if p in heads and p not in stoprevs:
827 del heads[p] 826 heads.remove(p)
828 827
829 return [self.node(r) for r in heads] 828 return [self.node(r) for r in heads]
830 829
831 def children(self, node): 830 def children(self, node):
832 """find the children of a given node""" 831 """find the children of a given node"""