/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/xml4.py

  • Committer: John Arbash Meinel
  • Date: 2009-10-12 15:55:26 UTC
  • mto: (4679.5.3 2.1-static-tuple-no-use)
  • mto: This revision was merged to the branch mainline in revision 4735.
  • Revision ID: john@arbash-meinel.com-20091012155526-b46tuz5cibebbnct
Change the _lookup function to use Quadratic Probing.

The main strength is that we get a bit of locality (collision resolution
looks quickly close to the location.)
The main weakness is that we don't use the upper bits of the hash to
induce divergence. So while we nicely handle collisions in neighboring
buckets (Quadratic means their resolution chains will diverge), if
two objects hash to the same bucket, their resolution chains are identical.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/xml4.py
1
 
# Copyright (C) 2005-2010 Canonical Ltd
 
1
# Copyright (C) 2005, 2006 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
from bzrlib.xml_serializer import (
18
18
    Element,
 
19
    ElementTree,
19
20
    SubElement,
20
21
    XMLSerializer,
21
22
    escape_invalid_chars,
22
23
    )
23
 
from bzrlib.inventory import ROOT_ID, Inventory
 
24
from bzrlib.inventory import ROOT_ID, Inventory, InventoryEntry
24
25
import bzrlib.inventory as inventory
25
26
from bzrlib.revision import Revision
26
27
from bzrlib.errors import BzrError
62
63
        return e
63
64
 
64
65
 
65
 
    def _unpack_inventory(self, elt, revision_id=None, entry_cache=None,
66
 
                          return_from_cache=False):
 
66
    def _unpack_inventory(self, elt, revision_id=None, entry_cache=None):
67
67
        """Construct from XML Element
68
68
 
69
69
        :param revision_id: Ignored parameter used by xml5.
71
71
        root_id = elt.get('file_id') or ROOT_ID
72
72
        inv = Inventory(root_id)
73
73
        for e in elt:
74
 
            ie = self._unpack_entry(e, entry_cache=entry_cache,
75
 
                                    return_from_cache=return_from_cache)
 
74
            ie = self._unpack_entry(e, entry_cache=entry_cache)
76
75
            if ie.parent_id == ROOT_ID:
77
76
                ie.parent_id = root_id
78
77
            inv.add(ie)
79
78
        return inv
80
79
 
81
80
 
82
 
    def _unpack_entry(self, elt, entry_cache=None, return_from_cache=False):
 
81
    def _unpack_entry(self, elt, entry_cache=None):
83
82
        ## original format inventories don't have a parent_id for
84
83
        ## nodes in the root directory, but it's cleaner to use one
85
84
        ## internally.