← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Vincent Ladeuil
  • Date: 2011-07-06 09:22:00 UTC
  • mfrom: (6008 +trunk)
  • mto: (6012.1.1 trunk)
  • mto: This revision was merged to the branch mainline in revision 6013.
  • Revision ID: v.ladeuil+lp@free.fr-20110706092200-7iai2mwzc0sqdsvf
Merging in trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
18
18
"""B+Tree indices"""
19
19
 
20
20
import cStringIO
21
 
from bisect import bisect_right
 
21
 
 
22
from bzrlib.lazy_import import lazy_import
 
23
lazy_import(globals(), """
 
24
import bisect
22
25
import math
23
26
import tempfile
24
27
import zlib
 
28
""")
25
29
 
26
30
from bzrlib import (
27
31
    chunk_writer,
158
162
        :param references: An iterable of iterables of keys. Each is a
159
163
            reference to another key.
160
164
        :param value: The value to associate with the key. It may be any
161
 
            bytes as long as it does not contain \0 or \n.
 
165
            bytes as long as it does not contain \\0 or \\n.
162
166
        """
163
167
        # Ensure that 'key' is a StaticTuple
164
168
        key = static_tuple.StaticTuple.from_sequence(key).intern()
1047
1051
        # iter_steps = len(in_keys) + len(fixed_keys)
1048
1052
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1049
1053
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1050
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1054
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1051
1055
        # elif bisect_steps < iter_steps:
1052
1056
        #     offsets = {}
1053
1057
        #     for key in in_keys: