mozilla/rust — pull request #9816 by bill-myers (2013-10-12 01:01:46+00:00)
Title: RFC: add snapshottable/persistent treemap variant

This adds a new type called "SnapMap", which is a snapshottable treemap using copy-on-write and reference counting, in 3 versions, using Rc, Arc and ~ as pointers to the nodes.

This is essentially a persistent balanced tree data structure, but memory is not allocated on any modification, but insntead nodes are cloned when they have reference count > 1, so it behaves exactly like a non-persistent treemap if it is never cloned.

The first commits are the same as pull #9786, and they provide the mechanism to copy-on-write Rc and Arc by cloning the contents when the reference count is > 1.

Note that this is untested beyond compilation, and might well have serious bugs; it is based on treemap.rs, but has been modified to try to minimize useless copy-on-write cases: for instance, when one does a lookup to get a mutable reference, the code first does a normal lookup and records the tree path, and only splits the nodes if the key is indeed present, and the same thing is done on removes.