/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/clean_tree.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/clean_tree.py
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
 
 
18
import errno
18
19
import os
19
20
import shutil
 
21
import sys
20
22
 
21
 
from bzrlib.osutils import isdir
 
23
from bzrlib.osutils import has_symlinks, isdir
22
24
from bzrlib.trace import note
23
25
from bzrlib.workingtree import WorkingTree
24
26