upstream/mercurial-mirror Files · rust/hg-core/src/dirstate/dirstate_tree.rs

rust: add `dirstate_tree` module...

rust: add `dirstate_tree` module Mercurial needs to represent the filesystem hierarchy on which it operates, for example in the dirstate. Its current on-disk representation is an unsorted, flat structure that gets transformed in the current Rust code into a `HashMap`. This loses the hierarchical information of the dirstate, leading to some unfortunate performance and algorithmic compromises. This module adds an implementation of a radix tree that is specialized for representing the dirstate: its unit is the path component. I have made no efforts to optimize either its memory footprint or its insertion speed: they're pretty bad for now. Following will be a few patches that modify the dirstate.status logic to use that new hierarchical information, fixing issue 6335 in the same swing. Differential Revision: https://phab.mercurial-scm.org/D9085

Raphaël Gomès - - Load All Authors

File last commit:

r46136:b51167d7 default


                r46136:b51167d7

default

Download file

             dirstate_tree.rs
        
                    14 lines
            
             | 398 B
            
                | application/rls-services+xml
            
             |
                RustLexer
            
             / rust / hg-core / src / dirstate / dirstate_tree.rs
          
                    History
                
                 |
                  Annotation
                 | Raw
                 |Copy content
                 |Copy permalink

      // dirstate_tree.rs

      //

      // Copyright 2020, Raphaël Gomès <rgomes@octobus.net>

      //

      // This software may be used and distributed according to the terms of the

      // GNU General Public License version 2 or any later version.

      //! Special-case radix tree that matches a filesystem hierarchy for use in the

      //! dirstate.

      //! It has not been optimized at all yet.

      pub mod iter;

      pub mod node;

      pub mod tree;

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages

				// dirstate_tree.rs
				//
				// Copyright 2020, Raphaël Gomès <rgomes@octobus.net>
				//
				// This software may be used and distributed according to the terms of the
				// GNU General Public License version 2 or any later version.

				//! Special-case radix tree that matches a filesystem hierarchy for use in the
				//! dirstate.
				//! It has not been optimized at all yet.

				pub mod iter;
				pub mod node;
				pub mod tree;