Mercurial > hg
annotate rust/hg-core/src/dirstate/dirstate_tree.rs @ 45562:b51167d70f5a
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
author | Raphaël Gomès <rgomes@octobus.net> |
---|---|
date | Fri, 25 Sep 2020 17:51:34 +0200 |
parents | |
children |
rev | line source |
---|---|
45562
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
1 // dirstate_tree.rs |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
2 // |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
3 // Copyright 2020, Raphaël Gomès <rgomes@octobus.net> |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
4 // |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
5 // This software may be used and distributed according to the terms of the |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
6 // GNU General Public License version 2 or any later version. |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
7 |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
8 //! Special-case radix tree that matches a filesystem hierarchy for use in the |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
9 //! dirstate. |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
10 //! It has not been optimized at all yet. |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
11 |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
12 pub mod iter; |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
13 pub mod node; |
b51167d70f5a
rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents:
diff
changeset
|
14 pub mod tree; |