/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/xml5.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/xml5.py
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2005, 2006, 2007, 2008 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
30
30
    format_num = '5'
31
31
    root_id = inventory.ROOT_ID
32
32
 
33
 
    def _unpack_inventory(self, elt, revision_id, entry_cache=None,
34
 
                          return_from_cache=False):
 
33
    def _unpack_inventory(self, elt, revision_id, entry_cache=None):
35
34
        """Construct from XML Element
36
35
        """
37
36
        root_id = elt.get('file_id') or inventory.ROOT_ID
55
54
        unpack_entry = self._unpack_entry
56
55
        byid = inv._byid
57
56
        for e in elt:
58
 
            ie = unpack_entry(e, entry_cache=entry_cache,
59
 
                              return_from_cache=return_from_cache)
 
57
            ie = unpack_entry(e, entry_cache=entry_cache)
60
58
            parent_id = ie.parent_id
61
59
            if parent_id is None:
62
60
                ie.parent_id = parent_id = root_id