This library provides a chain of HashMap
s with interior mutability of each intermediate layer. The HashMap
s are reference-counted, thus it is possible to create a tree of layers of HashMap
s and not just a single chain.
The higher maps in the tree (close to the leaves) have higher priority.
The implementation allows several maps to read and write to a common root. Not as many items are cloned as when using a HashMap
. Calls to insert
have been measured to be about twice as slow as when using a plain HashMap
, and both update
and get
are linear relative to the depth of the ChainMap
: do not use this crate if what you want to do can be solved with a plain HashMap
.
On the other hand, you might want to use this if:
- you have many calls to
clone
on aHashMap
with constant values, in which case you can pass aroundChainMap
s withmap.extend().readonly()
- you want a
HashMap
shared by multiple objects/threads, then you can usemap.extend()
and make calls toupdate
on it - you have a collection of mappings that you want to override locally without affecting the default values, this can be done with
map.extend()
then calls toinsert
Possible use cases that group all of the above include:
An example from the appropriate section of the Book: 15. Scoping rules - RAII
fn create_box() {
// CreateBoxScope
let _box1 = Box::new(3i32);
}
fn main() {
// MainScope
let _box2 = Box::new(5i32);
{
// NestedScope
let box3 = Box::new(4i32);
}
for i in 0u32..1_000 {
// LoopScope<i>
create_box();
}
}
Could be represented as
MainScope["_box2" => 5i32]
├── NestedScope["_box3" => 4i32]
├── LoopScope0[]
│ └── CreateBoxScope["_box1" => 3i32]
├── LoopScope1[]
│ └── CreateBoxScope["_box1" => 3i32]
│ ...
└── LoopScope999[]
└── CreateBoxScope["_box1" => 3i32]
Where each [ $( $key => $value ),* ]
is a level of a tree of ChainMap
s built on the previous one.
This it turn could be declared as
let mut main_scope = ChainMap::new();
main_scope.insert("_box2", 5i32);
let mut nested_scope = main_scope.extend();
nested_scope.insert("_box1", 5i32);
let mut loop_scope = Vec::new();
for _ in 0..1000 {
let mut h = HashMap::new();
h.insert("_box1", 3i32);
loop_scope.push(main_scope.extend().extend_with(h));
}
The rules for which map entries are accessible from a certain level of the ChainMap
tree are exactly the same as how they would be for the corresponding scopes.
For example with cargo
:
~
├── proj/
│ ├── foo/
│ │ ├── bar/
│ │ │ └── .cargo/config
│ │ ├── baz/
│ │ │ └── .cargo/config
│ │ └── .cargo/config
│ ├── quux/
│ │ └── .cargo/config
│ └── .cargo/config
└── .cargo/config
The config
files closer to the leaves have higher priority and can override the configuration settings defined closer to the root in the directory tree.
This situation can be trivially abstracted with a ChainMap
:
let home = ChainMap::new();
let proj = home.extend();
let foo = proj.extend();
let quux = proj.extend();
let bar = foo.extend();
let baz = foo.extend();
There are already chain maps out there:
However, both of these implementations of a chain map do not allow multiple branches from a single root, as they are wrappers around a Vec<HashMap<K, V>>
.
On the other hand, this crate allows one to fork several maps out of a common root, saving memory usage at the cost of a less friendly internal representation: A Vec<HashMap<K, V>>
is certainly better to work with than a tree of Option<Rc<Mutex<HashMap<K, V>>>>
.
The ChainMap
could just as well take &self
everywhere instead of requiring &mut self
, and it would still work. After all, a Mutex
can have its contents changed even if its container is immutable.
There are two reasons for not making all methods take &self
:
-
Despite interior mutability, it would feel weird to
insert
into a non-mut
structure.A
HashMap
requiresmut
toinsert
, and I wanted theChainMap
to feel like aHashMap
as much as possible, hence the choice of the same method namesinsert
andget
. -
The
fork
andfork_with
methods do require&mut self
and there is no (safe) way to bypass that.fork
is declared as:pub fn fork(&mut self) -> Self { let newlevel = self.extend(); let oldlevel = self.extend_fallthrough(); // This line requires &mut self std::mem::replace(&mut *self, oldlevel); newlevel }
When used:
let ch = ChainMap::new(); let _ = ch.fork();
ch
is not the same object before and after the call tofork
!The object that used to be contained in
ch
has been moved out and there is now no way to access the formerch
other than implicitly by reading it from one of its children.It is also impossible to insert a new key into it.