comparison rust/hg-core/src/dirstate.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 5ac243a92e37
children e604a3c03ab9
comparison
equal deleted inserted replaced
45558:80bf7b1ada15 45562:b51167d70f5a
9 use std::collections::hash_map; 9 use std::collections::hash_map;
10 use std::convert::TryFrom; 10 use std::convert::TryFrom;
11 11
12 pub mod dirs_multiset; 12 pub mod dirs_multiset;
13 pub mod dirstate_map; 13 pub mod dirstate_map;
14 pub mod dirstate_tree;
14 pub mod parsers; 15 pub mod parsers;
15 pub mod status; 16 pub mod status;
16 17
17 #[derive(Debug, PartialEq, Clone)] 18 #[derive(Debug, PartialEq, Clone)]
18 pub struct DirstateParents { 19 pub struct DirstateParents {