summaryrefslogtreecommitdiff
path: root/tests/src/betree
diff options
context:
space:
mode:
Diffstat (limited to 'tests/src/betree')
-rw-r--r--tests/src/betree/src/betree.rs197
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
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-30 19:37:57 +0000