~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/bisect_multi.py

• browse files at revision 3815
• compare with another revision
• download diff
• download tarball
• view history from revision 3815

• reverse the comparison (3815 to 408)
• stop comparing with revision 408

Show diffs side-by-side

added

removed

bzrlib/bisect_multi.py

 

1

# Copyright (C) 2007 Canonical Ltd

 

2

#

 

3

# This program is free software; you can redistribute it and/or modify

 

4

# it under the terms of the GNU General Public License as published by

 

5

# the Free Software Foundation; either version 2 of the License, or

 

6

# (at your option) any later version.

 

7

#

 

8

# This program is distributed in the hope that it will be useful,

 

9

# but WITHOUT ANY WARRANTY; without even the implied warranty of

 

10

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 

11

# GNU General Public License for more details.

 

12

#

 

13

# You should have received a copy of the GNU General Public License

 

14

# along with this program; if not, write to the Free Software

 

15

# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 

16

 

 

17

"""Bisection lookup multiple keys."""

 

18

 

 

19

__all__ = [

 

20

    'bisect_multi_bytes',

 

21

    ]

 

22

 

 

23

 

 

24

def bisect_multi_bytes(content_lookup, size, keys):

 

25

    """Perform bisection lookups for keys using byte based addressing.

 

26

    

 

27

    The keys are looked up via the content_lookup routine. The content_lookup

 

28

    routine gives bisect_multi_bytes information about where to keep looking up

 

29

    to find the data for the key, and bisect_multi_bytes feeds this back into

 

30

    the lookup function until the search is complete. The search is complete

 

31

    when the list of keys which have returned something other than -1 or +1 is

 

32

    empty. Keys which are not found are not returned to the caller.

 

33

 

 

34

    :param content_lookup: A callable that takes a list of (offset, key) pairs

 

35

        and returns a list of result tuples ((offset, key), result). Each

 

36

        result can be one of:

 

37

          -1: The key comes earlier in the content.

 

38

          False: The key is not present in the content.

 

39

          +1: The key comes later in the content.

 

40

          Any other value: A final result to return to the caller.

 

41

    :param size: The length of the content.

 

42

    :param keys: The keys to bisect for.

 

43

    :return: An iterator of the results.

 

44

    """

 

45

    # possibly make this a generator, but a list meets the contract for now.

 

46

    result = []

 

47

    delta = size // 2

 

48

    search_keys = [(delta, key) for key in keys]

 

49

    while search_keys:

 

50

        search_results = content_lookup(search_keys)

 

51

        if delta > 1:

 

52

            delta = delta // 2

 

53

        search_keys = []

 

54

        for (location, key), status in search_results:

 

55

            if status == -1:

 

56

                search_keys.append((location - delta, key))

 

57

            elif status == 1:

 

58

                search_keys.append((location + delta, key))

 

59

            elif status == False:

 

60

                # not present, stop searching

 

61

                continue

 

62

            else:

 

63

                result.append((key, status))

 

64

    return result

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1