← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-05-21 13:36:51 UTC
  • mfrom: (5243.2.1 readdir_cleanup)
  • Revision ID: pqm@pqm.ubuntu.com-20100521133651-p62dndo2giy5ls21
(lifeless) Some cleanups to the readdir pyrex code for a little efficiency
 and to avoid compile warnings. (John A Meinel)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
1
 
# Copyright (C) 2007-2011 Canonical Ltd
 
1
# Copyright (C) 2007-2010 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
16
16
 
17
17
"""Indexing facilities."""
18
18
 
19
 
from __future__ import absolute_import
20
 
 
21
19
__all__ = [
22
20
    'CombinedGraphIndex',
23
21
    'GraphIndex',
33
31
 
34
32
from bzrlib.lazy_import import lazy_import
35
33
lazy_import(globals(), """
36
 
from bzrlib import (
37
 
    bisect_multi,
38
 
    revision as _mod_revision,
39
 
    trace,
40
 
    )
 
34
from bzrlib import trace
 
35
from bzrlib.bisect_multi import bisect_multi_bytes
 
36
from bzrlib.revision import NULL_REVISION
 
37
from bzrlib.trace import mutter
41
38
""")
42
39
from bzrlib import (
43
40
    debug,
72
69
class GraphIndexBuilder(object):
73
70
    """A builder that can build a GraphIndex.
74
71
 
75
 
    The resulting graph has the structure::
 
72
    The resulting graph has the structure:
76
73
 
77
 
      _SIGNATURE OPTIONS NODES NEWLINE
78
 
      _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
79
 
      OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
80
 
      NODES          := NODE*
81
 
      NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
82
 
      KEY            := Not-whitespace-utf8
83
 
      ABSENT         := 'a'
84
 
      REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
85
 
      REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
86
 
      REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
87
 
                                ; referenced key.
88
 
      VALUE          := no-newline-no-null-bytes
 
74
    _SIGNATURE OPTIONS NODES NEWLINE
 
75
    _SIGNATURE     := 'Bazaar Graph Index 1' NEWLINE
 
76
    OPTIONS        := 'node_ref_lists=' DIGITS NEWLINE
 
77
    NODES          := NODE*
 
78
    NODE           := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
 
79
    KEY            := Not-whitespace-utf8
 
80
    ABSENT         := 'a'
 
81
    REFERENCES     := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
 
82
    REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
 
83
    REFERENCE      := DIGITS  ; digits is the byte offset in the index of the
 
84
                              ; referenced key.
 
85
    VALUE          := no-newline-no-null-bytes
89
86
    """
90
87
 
91
88
    def __init__(self, reference_lists=0, key_elements=1):
187
184
        :param value: The value associate with this key. Must not contain
188
185
            newlines or null characters.
189
186
        :return: (node_refs, absent_references)
190
 
        
191
 
            * node_refs: basically a packed form of 'references' where all
192
 
              iterables are tuples
193
 
            * absent_references: reference keys that are not in self._nodes.
194
 
              This may contain duplicates if the same key is referenced in
195
 
              multiple lists.
 
187
            node_refs   basically a packed form of 'references' where all
 
188
                        iterables are tuples
 
189
            absent_references   reference keys that are not in self._nodes.
 
190
                                This may contain duplicates if the same key is
 
191
                                referenced in multiple lists.
196
192
        """
197
193
        as_st = StaticTuple.from_sequence
198
194
        self._check_key(key)
223
219
        :param references: An iterable of iterables of keys. Each is a
224
220
            reference to another key.
225
221
        :param value: The value to associate with the key. It may be any
226
 
            bytes as long as it does not contain \\0 or \\n.
 
222
            bytes as long as it does not contain \0 or \n.
227
223
        """
228
224
        (node_refs,
229
225
         absent_references) = self._check_key_ref_value(key, references, value)
247
243
        """
248
244
        
249
245
    def finish(self):
250
 
        """Finish the index.
251
 
 
252
 
        :returns: cStringIO holding the full context of the index as it 
253
 
        should be written to disk.
254
 
        """
255
246
        lines = [_SIGNATURE]
256
247
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
257
248
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
453
444
            # We already did this
454
445
            return
455
446
        if 'index' in debug.debug_flags:
456
 
            trace.mutter('Reading entire index %s',
457
 
                          self._transport.abspath(self._name))
 
447
            mutter('Reading entire index %s', self._transport.abspath(self._name))
458
448
        if stream is None:
459
449
            stream = self._transport.get(self._name)
460
450
            if self._base_offset != 0:
472
462
        trailers = 0
473
463
        pos = stream.tell()
474
464
        lines = stream.read().split('\n')
475
 
        # GZ 2009-09-20: Should really use a try/finally block to ensure close
476
465
        stream.close()
477
466
        del lines[-1]
478
467
        _, _, _, trailers = self._parse_lines(lines, pos)
681
670
        if self._nodes is not None:
682
671
            return self._iter_entries_from_total_buffer(keys)
683
672
        else:
684
 
            return (result[1] for result in bisect_multi.bisect_multi_bytes(
 
673
            return (result[1] for result in bisect_multi_bytes(
685
674
                self._lookup_keys_via_location, self._size, keys))
686
675
 
687
676
    def iter_entries_prefix(self, keys):
1298
1287
    def get_parent_map(self, keys):
1299
1288
        """See graph.StackedParentsProvider.get_parent_map"""
1300
1289
        search_keys = set(keys)
1301
 
        if _mod_revision.NULL_REVISION in search_keys:
1302
 
            search_keys.discard(_mod_revision.NULL_REVISION)
1303
 
            found_parents = {_mod_revision.NULL_REVISION:[]}
 
1290
        if NULL_REVISION in search_keys:
 
1291
            search_keys.discard(NULL_REVISION)
 
1292
            found_parents = {NULL_REVISION:[]}
1304
1293
        else:
1305
1294
            found_parents = {}
1306
1295
        for index, key, value, refs in self.iter_entries(search_keys):
1307
1296
            parents = refs[0]
1308
1297
            if not parents:
1309
 
                parents = (_mod_revision.NULL_REVISION,)
 
1298
                parents = (NULL_REVISION,)
1310
1299
            found_parents[key] = parents
1311
1300
        return found_parents
1312
1301
 
1444
1433
        """
1445
1434
        indices_info = zip(self._index_names, self._indices)
1446
1435
        if 'index' in debug.debug_flags:
1447
 
            trace.mutter('CombinedGraphIndex reordering: currently %r, '
1448
 
                         'promoting %r', indices_info, hit_indices)
 
1436
            mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
 
1437
                   indices_info, hit_indices)
1449
1438
        hit_names = []
1450
1439
        unhit_names = []
1451
1440
        new_hit_indices = []
1468
1457
        self._indices = new_hit_indices + unhit_indices
1469
1458
        self._index_names = hit_names + unhit_names
1470
1459
        if 'index' in debug.debug_flags:
1471
 
            trace.mutter('CombinedGraphIndex reordered: %r', self._indices)
 
1460
            mutter('CombinedGraphIndex reordered: %r', self._indices)
1472
1461
        return hit_names
1473
1462
 
1474
1463
    def _move_to_front_by_name(self, hit_names):