##// END OF EJS Templates
match: convert O(n) to O(log n) in exactmatcher.visitchildrenset...
Kyle Lippincott -
r47634:8bca353b default
parent child Browse files
Show More
@@ -7,6 +7,7 b''
7
7
8 from __future__ import absolute_import, print_function
8 from __future__ import absolute_import, print_function
9
9
10 import bisect
10 import copy
11 import copy
11 import itertools
12 import itertools
12 import os
13 import os
@@ -798,14 +799,38 b' class exactmatcher(basematcher):'
798 def visitdir(self, dir):
799 def visitdir(self, dir):
799 return dir in self._dirs
800 return dir in self._dirs
800
801
802 @propertycache
803 def _visitchildrenset_candidates(self):
804 """A memoized set of candidates for visitchildrenset."""
805 return self._fileset | self._dirs - {b''}
806
807 @propertycache
808 def _sorted_visitchildrenset_candidates(self):
809 """A memoized sorted list of candidates for visitchildrenset."""
810 return sorted(self._visitchildrenset_candidates)
811
801 def visitchildrenset(self, dir):
812 def visitchildrenset(self, dir):
802 if not self._fileset or dir not in self._dirs:
813 if not self._fileset or dir not in self._dirs:
803 return set()
814 return set()
804
815
805 candidates = self._fileset | self._dirs - {b''}
816 if dir == b'':
806 if dir != b'':
817 candidates = self._visitchildrenset_candidates
818 else:
819 candidates = self._sorted_visitchildrenset_candidates
807 d = dir + b'/'
820 d = dir + b'/'
808 candidates = {c[len(d) :] for c in candidates if c.startswith(d)}
821 # Use bisect to find the first element potentially starting with d
822 # (i.e. >= d). This should always find at least one element (we'll
823 # assert later if this is not the case).
824 first = bisect.bisect_left(candidates, d)
825 # We need a representation of the first element that is > d that
826 # does not start with d, so since we added a `/` on the end of dir,
827 # we'll add whatever comes after slash (we could probably assume
828 # that `0` is after `/`, but let's not) to the end of dir instead.
829 dnext = dir + encoding.strtolocal(chr(ord(b'/') + 1))
830 # Use bisect to find the first element >= d_next
831 last = bisect.bisect_left(candidates, dnext, lo=first)
832 dlen = len(d)
833 candidates = {c[dlen:] for c in candidates[first:last]}
809 # self._dirs includes all of the directories, recursively, so if
834 # self._dirs includes all of the directories, recursively, so if
810 # we're attempting to match foo/bar/baz.txt, it'll have '', 'foo',
835 # we're attempting to match foo/bar/baz.txt, it'll have '', 'foo',
811 # 'foo/bar' in it. Thus we can safely ignore a candidate that has a
836 # 'foo/bar' in it. Thus we can safely ignore a candidate that has a
General Comments 0
You need to be logged in to leave comments. Login now