diff options
| -rw-r--r-- | tests/src/betree/src/betree.rs | 197 |
1 files changed, 98 insertions, 99 deletions
diff --git a/tests/src/betree/src/betree.rs b/tests/src/betree/src/betree.rs index 12f2847d..8ba07824 100644 --- a/tests/src/betree/src/betree.rs +++ b/tests/src/betree/src/betree.rs @@ -274,25 +274,41 @@ pub fn upsert_update(prev: Option<Value>, st: UpsertFunState) -> Value { impl<T> List<T> { fn len(&self) -> u64 { - match self { - List::Nil => 0, - List::Cons(_, tl) => 1 + tl.len(), + let mut l = self; + let mut len = 0; + while let List::Cons(_, tl) = l { + len += 1; + l = tl; } + len } /// Split a list at a given length - fn split_at(self, n: u64) -> (List<T>, List<T>) { - if n == 0 { - (List::Nil, self) - } else { - match self { + fn split_at(self, mut n: u64) -> (List<T>, List<T>) { + let mut beg = List::Nil; + let mut end = self; + while n > 0 { + match end { List::Nil => unreachable!(), - List::Cons(hd, tl) => { - let (ls0, ls1) = tl.split_at(n - 1); - (List::Cons(hd, Box::new(ls0)), ls1) + List::Cons(hd, mut tl) => { + n -= 1; + end = *tl; + *tl = beg; + beg = List::Cons(hd, tl); } } } + (beg.reverse(), end) + } + + fn reverse(mut self) -> Self { + let mut out = List::Nil; + while let List::Cons(hd, mut tl) = self { + self = *tl; + *tl = out; + out = List::Cons(hd, tl); + } + out } /// Push an element at the front of the list. @@ -337,17 +353,20 @@ impl<T> Map<Key, T> { /// Note that the bindings in the map are supposed to be sorted in /// order of increasing keys. fn partition_at_pivot(self, pivot: Key) -> (Map<Key, T>, Map<Key, T>) { - match self { - List::Nil => (List::Nil, List::Nil), - List::Cons(hd, tl) => { - if hd.0 >= pivot { - (List::Nil, List::Cons(hd, tl)) - } else { - let (ls0, ls1) = tl.partition_at_pivot(pivot); - (List::Cons(hd, Box::new(ls0)), ls1) - } + let mut beg = List::Nil; + let mut end = List::Nil; + let mut curr = self; + while let List::Cons(hd, mut tl) = curr { + curr = *tl; + if hd.0 >= pivot { + *tl = end; + end = List::Cons(hd, tl); + } else { + *tl = beg; + beg = List::Cons(hd, tl); } } + (beg.reverse(), end.reverse()) } } @@ -443,14 +462,11 @@ impl Node { /// Apply a list of message to ourselves: leaf node case fn apply_messages_to_leaf<'a>( bindings: &'a mut Map<Key, Value>, - new_msgs: List<(Key, Message)>, + mut new_msgs: List<(Key, Message)>, ) { - match new_msgs { - List::Nil => (), - List::Cons(new_msg, new_msgs_tl) => { - Node::apply_to_leaf(bindings, new_msg.0, new_msg.1); - Node::apply_messages_to_leaf(bindings, *new_msgs_tl); - } + while let List::Cons(new_msg, new_msgs_tl) = new_msgs { + Node::apply_to_leaf(bindings, new_msg.0, new_msg.1); + new_msgs = *new_msgs_tl; } } @@ -501,14 +517,11 @@ impl Node { /// Apply a list of message to ourselves: internal node case fn apply_messages_to_internal<'a>( msgs: &'a mut Map<Key, Message>, - new_msgs: List<(Key, Message)>, + mut new_msgs: List<(Key, Message)>, ) { - match new_msgs { - List::Nil => (), - List::Cons(new_msg, new_msgs_tl) => { - Node::apply_to_internal(msgs, new_msg.0, new_msg.1); - Node::apply_messages_to_internal(msgs, *new_msgs_tl); - } + while let List::Cons(new_msg, new_msgs_tl) = new_msgs { + Node::apply_to_internal(msgs, new_msg.0, new_msg.1); + new_msgs = *new_msgs_tl; } } @@ -633,38 +646,34 @@ impl Node { /// Lookup a value in a list of bindings. /// Note that the values should be stored in order of increasing key. - fn lookup_in_bindings(key: Key, bindings: &Map<Key, Value>) -> Option<Value> { - match bindings { - List::Nil => Option::None, - List::Cons(hd, tl) => { - if hd.0 == key { - Option::Some(hd.1) - } else if hd.0 > key { - Option::None - } else { - Node::lookup_in_bindings(key, tl) - } + fn lookup_in_bindings(key: Key, mut bindings: &Map<Key, Value>) -> Option<Value> { + while let List::Cons(hd, tl) = bindings { + if hd.0 == key { + return Option::Some(hd.1); + } else if hd.0 > key { + return Option::None; + } else { + bindings = tl; } } + Option::None } /// Lookup a value in a list of bindings, and return a borrow to the position /// where the value is (or should be inserted, if the key is not in the bindings). fn lookup_mut_in_bindings<'a>( key: Key, - bindings: &'a mut Map<Key, Value>, + mut bindings: &'a mut Map<Key, Value>, ) -> &'a mut Map<Key, Value> { - match bindings { - List::Nil => bindings, - List::Cons(hd, tl) => { - // This requires Polonius - if hd.0 >= key { - bindings - } else { - Node::lookup_mut_in_bindings(key, tl) - } + while let List::Cons(hd, tl) = bindings { + // This requires Polonius + if hd.0 >= key { + break; + } else { + bindings = tl; } } + bindings } /// Filter all the messages which concern [key]. @@ -672,34 +681,28 @@ impl Node { /// Note that the stack of messages must start with a message for [key]: /// we stop filtering at the first message which is not about [key]. fn filter_messages_for_key<'a>(key: Key, msgs: &'a mut Map<Key, Message>) { - match msgs { - List::Nil => (), - List::Cons((k, _), _) => { - if *k == key { - msgs.pop_front(); - Node::filter_messages_for_key(key, msgs); - } else { - // Stop - () - } + while let List::Cons((k, _), _) = msgs { + if *k == key { + msgs.pop_front(); + } else { + // Stop + break; } } } fn lookup_first_message_after_key<'a>( key: Key, - msgs: &'a mut Map<Key, Message>, + mut msgs: &'a mut Map<Key, Message>, ) -> &'a mut Map<Key, Message> { - match msgs { - List::Nil => msgs, - List::Cons((k, _), next_msgs) => { - if *k == key { - Node::lookup_first_message_after_key(key, next_msgs) - } else { - msgs - } + while let List::Cons((k, _), next_msgs) = msgs { + if *k == key { + msgs = next_msgs; + } else { + break; } } + return msgs; } /// Returns the value bound to a key. @@ -788,24 +791,22 @@ impl Node { /// of the list). fn lookup_first_message_for_key<'a>( key: Key, - msgs: &'a mut Map<Key, Message>, + mut msgs: &'a mut Map<Key, Message>, ) -> &'a mut Map<Key, Message> { - match msgs { - List::Nil => msgs, - List::Cons(x, next_msgs) => { - // Rk.: we need Polonius here - // We wouldn't need Polonius if directly called the proper - // function to make the modifications here (because we wouldn't - // need to return anything). However, it would not be very - // idiomatic, especially with regards to the fact that we will - // rewrite everything with loops at some point. - if x.0 >= key { - msgs - } else { - Node::lookup_first_message_for_key(key, next_msgs) - } + while let List::Cons(x, next_msgs) = msgs { + // Rk.: we need Polonius here + // We wouldn't need Polonius if directly called the proper + // function to make the modifications here (because we wouldn't + // need to return anything). However, it would not be very + // idiomatic, especially with regards to the fact that we will + // rewrite everything with loops at some point. + if x.0 >= key { + return msgs; + } else { + msgs = next_msgs; } } + msgs } /// Apply the upserts from the current messages stack to a looked up value. @@ -816,8 +817,8 @@ impl Node { /// Note that if there are no more upserts to apply, then the value must be /// `Some`. Also note that we use the invariant that in the message stack, /// upsert messages are sorted from the first to the last to apply. - fn apply_upserts(msgs: &mut Map<Key, Message>, prev: Option<Value>, key: Key) -> Value { - if msgs.head_has_key(key) { + fn apply_upserts(msgs: &mut Map<Key, Message>, mut prev: Option<Value>, key: Key) -> Value { + while msgs.head_has_key(key) { // Pop the front message. // Note that it *must* be an upsert. let msg = msgs.pop_front(); @@ -825,9 +826,8 @@ impl Node { Message::Upsert(s) => { // Apply the update let v = upsert_update(prev, s); - let prev = Option::Some(v); + prev = Option::Some(v); // Continue - Node::apply_upserts(msgs, prev, key) } _ => { // Unreachable: we can only have [Upsert] messages @@ -835,13 +835,12 @@ impl Node { unreachable!(); } } - } else { - // We applied all the upsert messages: simply put an [Insert] - // message and return the value. - let v = prev.unwrap(); - msgs.push_front((key, Message::Insert(v))); - return v; } + // We applied all the upsert messages: simply put an [Insert] + // message and return the value. + let v = prev.unwrap(); + msgs.push_front((key, Message::Insert(v))); + v } } |