diff --git a/rust/treedirstate/src/lib.rs b/rust/treedirstate/src/lib.rs
--- a/rust/treedirstate/src/lib.rs
+++ b/rust/treedirstate/src/lib.rs
@@ -11,3 +11,5 @@
//!
//! The directory state also stores files that are in the working copy parent manifest but have
//! been marked as removed.
+
+pub mod vecmap;
diff --git a/rust/treedirstate/src/vecmap.rs b/rust/treedirstate/src/vecmap.rs
new file mode 100644
--- /dev/null
+++ b/rust/treedirstate/src/vecmap.rs
@@ -0,0 +1,281 @@
+// Copyright Facebook, Inc. 2017
+//! Ordered map implementation using a sorted vector
+
+use std::mem;
+use std::borrow::Borrow;
+use std::slice::{Iter as VecIter, IterMut as VecIterMut};
+use std::collections::Bound;
+use std::collections::Bound::*;
+
+#[derive(Debug)]
+pub struct VecMap<K, V> {
+ vec: Vec<(K, V)>,
+}
+
+pub struct Iter<'a, K: 'a, V: 'a>(VecIter<'a, (K, V)>);
+
+pub struct IterMut<'a, K: 'a, V: 'a>(VecIterMut<'a, (K, V)>);
+
+impl<K, V> VecMap<K, V>
+where
+ K: Ord,
+{
+ pub fn new() -> VecMap<K, V> {
+ VecMap { vec: Vec::new() }
+ }
+
+ pub fn with_capacity(capacity: usize) -> VecMap<K, V> {
+ VecMap {
+ vec: Vec::with_capacity(capacity),
+ }
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.vec.is_empty()
+ }
+
+ pub fn len(&self) -> usize {
+ self.vec.len()
+ }
+
+ /// Inserts a key-value pair into the map. If the key already had a value present in the
+ /// map, that value is returned. Otherwise, `None` is returned.
+ pub fn insert(&mut self, k: K, mut v: V) -> Option<V> {
+ match self.vec.binary_search_by(|e| e.0.cmp(&k)) {
+ Ok(index) => {
+ mem::swap(&mut self.vec[index].1, &mut v);
+ Some(v)
+ }
+ Err(index) => {
+ self.vec.insert(index, (k, v));
+ None
+ }
+ }
+ }
+
+ /// Inserts a key-value pair into the map. Fast-path for when the key is not already
+ /// present and is at the end of the map.
+ pub fn insert_hint_end(&mut self, k: K, v: V) -> Option<V> {
+ let len = self.vec.len();
+ if len == 0 || self.vec[len - 1].0 < k {
+ self.vec.push((k, v));
+ None
+ } else {
+ self.insert(k, v)
+ }
+ }
+
+ /// Removes a key-value pair from the map, returning the value if the key was previously in
+ /// the map.
+ pub fn remove<Q: ?Sized>(&mut self, q: &Q) -> Option<V>
+ where
+ K: Borrow<Q>,
+ Q: Ord,
+ {
+ match self.vec.binary_search_by(|e| e.0.borrow().cmp(q)) {
+ Ok(index) => {
+ let (_k, v) = self.vec.remove(index);
+ Some(v)
+ }
+ Err(_index) => None,
+ }
+ }
+
+ /// Returns a reference to the value corresponding to the key.
+ pub fn get<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<&'a V>
+ where
+ K: Borrow<Q>,
+ Q: Ord,
+ {
+ match self.vec.binary_search_by(|e| e.0.borrow().cmp(q)) {
+ Ok(index) => Some(&self.vec[index].1),
+ Err(_index) => None,
+ }
+ }
+
+ /// Returns a mutable reference to the value corresponding to the key.
+ pub fn get_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<&'a mut V>
+ where
+ K: Borrow<Q>,
+ Q: Ord,
+ {
+ match self.vec.binary_search_by(|e| e.0.borrow().cmp(q)) {
+ Ok(index) => Some(&mut self.vec[index].1),
+ Err(_index) => None,
+ }
+ }
+
+ // Returns an iterator over the pairs of entries in the map.
+ pub fn iter(&self) -> Iter<K, V> {
+ Iter(self.vec.iter())
+ }
+
+ /// Returns a mutable iterator over the pairs of entries in the map.
+ pub fn iter_mut(&mut self) -> IterMut<K, V> {
+ IterMut(self.vec.iter_mut())
+ }
+
+ /// Convert a range boundary to a slice index.
+ fn range_index<Q: ?Sized>(&self, b: Bound<&Q>, start: bool) -> Option<usize>
+ where
+ K: Borrow<Q>,
+ Q: Ord,
+ {
+ match b {
+ Unbounded => None,
+ Included(q) => match self.vec.binary_search_by(|e| e.0.borrow().cmp(q)) {
+ Ok(index) => if start {
+ Some(index)
+ } else {
+ Some(index + 1)
+ },
+ Err(index) => Some(index),
+ },
+ Excluded(q) => match self.vec.binary_search_by(|e| e.0.borrow().cmp(q)) {
+ Ok(index) => if start {
+ Some(index + 1)
+ } else {
+ Some(index)
+ },
+ Err(index) => Some(index),
+ },
+ }
+ }
+
+ /// Returns an iterator over the given range of keys.
+ pub fn range<Q>(&self, range: (Bound<&Q>, Bound<&Q>)) -> Iter<K, V>
+ where
+ K: Borrow<Q>,
+ Q: Ord + ?Sized,
+ {
+ let start = self.range_index(range.0, true);
+ let end = self.range_index(range.1, false);
+ match (start, end) {
+ (None, None) => Iter(self.vec.iter()),
+ (Some(s), None) => Iter(self.vec[s..].iter()),
+ (None, Some(e)) => Iter(self.vec[..e].iter()),
+ (Some(s), Some(e)) => Iter(self.vec[s..e].iter()),
+ }
+ }
+
+ /// Returns a mutuable iterator over the given range of keys.
+ pub fn range_mut<Q>(&mut self, range: (Bound<&Q>, Bound<&Q>)) -> IterMut<K, V>
+ where
+ K: Borrow<Q>,
+ Q: Ord + ?Sized,
+ {
+ let start = self.range_index(range.0, true);
+ let end = self.range_index(range.1, false);
+ match (start, end) {
+ (None, None) => IterMut(self.vec.iter_mut()),
+ (Some(s), None) => IterMut(self.vec[s..].iter_mut()),
+ (None, Some(e)) => IterMut(self.vec[..e].iter_mut()),
+ (Some(s), Some(e)) => IterMut(self.vec[s..e].iter_mut()),
+ }
+ }
+}
+
+impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
+ type Item = (&'a K, &'a V);
+
+ #[inline]
+ fn next(&mut self) -> Option<(&'a K, &'a V)> {
+ self.0.next().map(|next| (&next.0, &next.1))
+ }
+}
+
+impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
+ type Item = (&'a K, &'a mut V);
+
+ #[inline]
+ fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
+ self.0.next().map(|next| (&next.0, &mut next.1))
+ }
+}
+
+#[cfg(test)]
+mod tests {
+
+ use vecmap::{Iter, VecMap};
+ use std::collections::Bound::*;
+
+ #[test]
+ fn insert_get_remove() {
+ let mut vm = VecMap::new();
+ assert_eq!(vm.insert("test1", "value1".to_string()), None);
+ assert_eq!(vm.insert("test2", "value2".to_string()), None);
+ assert_eq!(
+ vm.insert("test1", "value3".to_string()),
+ Some("value1".to_string())
+ );
+ assert_eq!(vm.get(&"test1"), Some(&"value3".to_string()));
+ if let Some(v) = vm.get_mut(&"test1") {
+ *v = "value4".to_string();
+ }
+ assert_eq!(vm.get(&"test1"), Some(&"value4".to_string()));
+ assert_eq!(vm.remove("test2"), Some("value2".to_string()));
+ assert_eq!(vm.remove("test2"), None);
+ assert_eq!(vm.get(&"test2"), None);
+ }
+
+ #[test]
+ fn iter() {
+ let mut vm = VecMap::with_capacity(4);
+ assert!(vm.is_empty());
+ vm.insert(2, "value2");
+ vm.insert(1, "value1");
+ vm.insert(4, "value4");
+ vm.insert(3, "value3");
+ assert!(!vm.is_empty());
+ assert_eq!(vm.len(), 4);
+ {
+ let mut im = vm.iter_mut();
+ im.next();
+ let e2 = im.next().unwrap();
+ *e2.1 = "value2 - modified";
+ }
+ let mut i = vm.iter();
+ assert_eq!(i.next(), Some((&1, &"value1")));
+ assert_eq!(i.next(), Some((&2, &"value2 - modified")));
+ assert_eq!(i.next(), Some((&3, &"value3")));
+ assert_eq!(i.next(), Some((&4, &"value4")));
+ assert_eq!(i.next(), None);
+ }
+
+ #[test]
+ fn range() {
+ let mut vm: VecMap<i32, i32> = VecMap::new();
+ for n in 0..20 {
+ vm.insert(n * 2, n * 4);
+ }
+
+ fn check_iter(mut x: Iter<i32, i32>, start: i32, end: i32) {
+ let mut i = start;
+ while i < end {
+ assert_eq!(x.next(), Some((&i, &(i * 2))));
+ i += 2;
+ }
+ assert_eq!(x.next(), None);
+ }
+
+ check_iter(vm.range((Unbounded, Unbounded)), 0, 39);
+ check_iter(vm.range((Unbounded, Included(&2))), 0, 3);
+ check_iter(vm.range((Unbounded, Excluded(&2))), 0, 1);
+ check_iter(vm.range((Unbounded, Excluded(&7))), 0, 7);
+ check_iter(vm.range((Unbounded, Included(&13))), 0, 13);
+ check_iter(vm.range((Included(&4), Included(&13))), 4, 13);
+ check_iter(vm.range((Included(&5), Included(&14))), 6, 15);
+ check_iter(vm.range((Excluded(&5), Included(&20))), 6, 21);
+ check_iter(vm.range((Excluded(&6), Included(&60))), 8, 39);
+ check_iter(vm.range((Excluded(&-30), Unbounded)), 0, 39);
+ check_iter(vm.range((Included(&-1), Unbounded)), 0, 39);
+
+ assert_eq!(vm.get(&16), Some(&32));
+ {
+ let mut im = vm.range_mut((Included(&16), Excluded(&18)));
+ *im.next().unwrap().1 *= 2;
+ assert_eq!(im.next(), None);
+ }
+ assert_eq!(vm.get(&16), Some(&64));
+ }
+}