/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/bisect_multi.py

  • Committer: Vincent Ladeuil
  • Date: 2012-01-18 14:09:19 UTC
  • mto: This revision was merged to the branch mainline in revision 6468.
  • Revision ID: v.ladeuil+lp@free.fr-20120118140919-rlvdrhpc0nq1lbwi
Change set/remove to require a lock for the branch config files.

This means that tests (or any plugin for that matter) do not requires an
explicit lock on the branch anymore to change a single option. This also
means the optimisation becomes "opt-in" and as such won't be as
spectacular as it may be and/or harder to get right (nothing fails
anymore).

This reduces the diff by ~300 lines.

Code/tests that were updating more than one config option is still taking
a lock to at least avoid some IOs and demonstrate the benefits through
the decreased number of hpss calls.

The duplication between BranchStack and BranchOnlyStack will be removed
once the same sharing is in place for local config files, at which point
the Stack class itself may be able to host the changes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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