/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/chk_serializer.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/chk_serializer.py
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008, 2009 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
139
139
    revision_format_num = None
140
140
    support_altered_by_hack = False
141
141
 
142
 
    def _unpack_entry(self, elt, entry_cache=None, return_from_cache=False):
 
142
    def _unpack_entry(self, elt):
143
143
        kind = elt.tag
144
144
        if not kind in self.supported_kinds:
145
145
            raise AssertionError('unsupported entry kind %s' % kind)
152
152
            return inventory.TreeReference(file_id, name, parent_id, revision,
153
153
                                           reference_revision)
154
154
        else:
155
 
            return xml7.Serializer_v7._unpack_entry(self, elt,
156
 
                entry_cache=entry_cache, return_from_cache=return_from_cache)
 
155
            return xml7.Serializer_v7._unpack_entry(self, elt)
157
156
 
158
157
    def __init__(self, node_size, search_key_name):
159
158
        self.maximum_size = node_size