~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/bisect_multi.py

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

• reverse the comparison (6479 to 1943)
• stop comparing with revision 1943

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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

 

16

 

 

17

"""Bisection lookup multiple keys."""

 

18

 

 

19

from __future__ import absolute_import

 

20

 

 

21

__all__ = [

 

22

    'bisect_multi_bytes',

 

23

    ]

 

24

 

 

25

 

 

26

def bisect_multi_bytes(content_lookup, size, keys):

 

27

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

 

28

 

 

29

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

 

30

    routine gives bisect_multi_bytes information about where to keep looking up

 

31

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

 

32

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

 

33

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

 

34

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

 

35

 

 

36

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

 

37

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

 

38

        result can be one of:

 

39

          -1: The key comes earlier in the content.

 

40

          False: The key is not present in the content.

 

41

          +1: The key comes later in the content.

 

42

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

 

43

    :param size: The length of the content.

 

44

    :param keys: The keys to bisect for.

 

45

    :return: An iterator of the results.

 

46

    """

 

47

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

 

48

    result = []

 

49

    delta = size // 2

 

50

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

 

51

    while search_keys:

 

52

        search_results = content_lookup(search_keys)

 

53

        if delta > 1:

 

54

            delta = delta // 2

 

55

        search_keys = []

 

56

        for (location, key), status in search_results:

 

57

            if status == -1:

 

58

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

 

59

            elif status == 1:

 

60

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

 

61

            elif status == False:

 

62

                # not present, stop searching

 

63

                continue

 

64

            else:

 

65

                result.append((key, status))

 

66

    return result

• Older »

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