← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/bisect_multi.py

  • Committer: v.ladeuil+lp at free
  • Date: 2006-10-12 14:29:32 UTC
  • mto: (2145.1.1 keepalive)
  • mto: This revision was merged to the branch mainline in revision 2146.
  • Revision ID: v.ladeuil+lp@free.fr-20061012142932-7221fe16d2b48fa3
Shuffle http related test code. Hopefully it ends up at the right place :)

* bzrlib/tests/HttpServer.py: 
New file. bzrlib.tests.ChrootedTestCase use HttpServer. So the
class can't be defined in bzrlib.tests.HTTPUtils because it
creates a circular dependency (bzrlib.tests.HTTPUtils needs to
import bzrlib.tests).

* bzrlib/transport/http/_urllib.py: 
Transfer test server definition to bzrlib.tests.HttpServer. Clean
up imports.

* bzrlib/transport/http/_pycurl.py: 
Transfer test server definition to bzrlib.tests.HttpServer. Clean
up imports.

* bzrlib/transport/http/__init__.py: 
Transfer all test related code to either bzrlib.tests.HttpServer
and bzrlib.tests.HTTPUtils.
Fix all use of TransportNotPossible and InvalidURL by prefixing it
by 'errors.' (this seems to be the preferred way in the rest of
bzr).
Get rid of unused imports.

* bzrlib/tests/test_transport.py:
(ReadonlyDecoratorTransportTest.test_local_parameters,
FakeNFSDecoratorTests.test_http_parameters): Use HttpServer from
bzrlib.tests.HttpServer instead of bzrlib.transport.http.

* bzrlib/tests/test_sftp_transport.py:
(set_test_transport_to_sftp): Use HttpServer from
bzrlib.tests.HttpServer instead of bzrlib.transport.http.

* bzrlib/tests/test_selftest.py:
(TestTestCaseWithTransport.test_get_readonly_url_http): Use
HttpServer from bzrlib.tests.HttpServer instead of
bzrlib.transport.http.

* bzrlib/tests/test_repository.py: 
Does *not* use HttpServer.

* bzrlib/tests/test_http.py: 
Build on top of bzrlib.tests.HttpServer and bzrlib.tests.HTTPUtils
instead of bzrlib.transport.http.

* bzrlib/tests/test_bzrdir.py:
(ChrootedTests.setUp): Use HttpServer from bzrlib.tests.HttpServer
instead of bzrlib.transport.http.

* bzrlib/tests/branch_implementations/test_http.py:
(HTTPBranchTests.setUp): Use HttpServer from bzrlib.tests.HttpServer
instead of bzrlib.transport.http.

* bzrlib/tests/branch_implementations/test_branch.py:
(ChrootedTests.setUp): Use HttpServer from bzrlib.tests.HttpServer
instead of bzrlib.transport.http.

* bzrlib/tests/__init__.py:
(ChrootedTestCase.setUp): Use HttpServer from
bzrlib.tests.HttpServer instead of bzrlib.transport.http.

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
 
__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