[Solved] Return a vector of references to (some of the) elements from a vector protected by RwLock

Hi all,

I've got a Vec<Container> as part of MyStruct. This vector is protected by an RwLock.

What I need is a method on MyStruct that builds a Vec<&Container> that would essentially be a filtered view of the protected vector.

I imagine that the returned view would need to be guarded by some kind of RwLockReadGuard to ensure soundness.

I found a solution to a seemingly similar problem, where one wants to get a mapped view of the data guarded by lock in the parking-lot crate and its parking_lot::MappedRwLockReadGuard - Rust.

What I need is a (hypothetical) FilteredRwLockReadGuard.

The code shows the struct and the filtering code for an unprotected version of the vector. I would appreciate any help or pointers to how to implement the query_protected method.

I am not looking for unsafe solutions. At least not yet :wink:

#![allow(dead_code)]
use std::sync::{RwLock, RwLockReadGuard};

#[derive(Debug)]
struct Container {
	u: usize,
}

#[derive(Debug)]
struct MyStruct {
	pub unprotected_vector: Vec<Container>,
	pub protected_vector: RwLock<Vec<Container>>,
}

impl MyStruct {
	pub fn empty() -> Self {
		MyStruct {
			unprotected_vector: Vec::new(),
			protected_vector: RwLock::from(Vec::new()),
		}
	}
	pub fn push(&mut self, elem: Container, another_elem: Container) {
		self.unprotected_vector.push(elem);
		self.protected_vector.write().unwrap().push(another_elem);
	}

	/// return a filtered view of the unprotected vector
	pub fn query_unprotected(&self, threshold: usize) -> Vec<&Container> {
		// first, create a vector of references from the vector of structs
		let vec_refs: Vec<&Container> = self.unprotected_vector.iter().collect();

		// then, filter the vector and returned the filtered one
		vec_refs.into_iter().filter(|&i| i.u <= threshold).collect()
	}


	/// should return a filtered view of the protected vector
	pub fn query_protected(&self, threshold: usize) -> RwLockReadGuard<Vec<&Container>> {
		// Help!
	}
}

#[cfg(test)]
mod test {

use super::*;

	#[test]
	fn test() {
		let mut ms = MyStruct::empty();
		ms.push(Container { u: 1 }, Container { u: 11 });
		ms.push(Container { u: 2 }, Container { u: 22 });
		ms.push(Container { u: 3 }, Container { u: 33 });
		ms.push(Container { u: 4 }, Container { u: 44 });
		ms.push(Container { u: 5 }, Container { u: 55 });

		assert_eq!(ms.unprotected_vector.len(), 5);
		assert_eq!(ms.query_unprotected(3).len(), 3);
	}
}

Thanks :slight_smile:

You can do this:

impl MyStruct {
	pub fn query_protected(&self, threshold: usize) -> MyQueryGuard {
		let lock = self.protected_vector.read().unwrap();
		
		let indices = lock.iter()
		    .enumerate()
		    .filter(|(i,v)| v.u <= threshold)
		    .map(|(i,_)| i)
		    .collect();

		MyQueryGuard {
		    guard: lock,
		    indices
		}
	}
}

struct MyQueryGuard<'a> {
    guard: RwLockReadGuard<'a, Vec<Container>>,
    indices: Vec<usize>,
}

impl<'a> std::ops::Index<usize> for MyQueryGuard<'a> {
    type Output = Container;
    fn index(&self, i: usize) -> &Container {
        let idx = self.indices[i];
        &self.guard[idx]
    }
}
2 Likes

You can also look into using CPS (Continuation-Passing Style):

#![forbid(unsafe_code)] // No unsafe!

use ::with_locals::with;

impl MyStruct {
    #[with('local)]
    fn query_protected (
        self: &'_ MyStruct,
        threshold: usize,
    ) -> Vec<&'local Container>
    {
        self.protected_vector
            .read()
            .unwrap()
            .iter()
            .filter(|i| i.u <= threshold)
            .collect()
    }
}

#[with]
fn example ()
{
    let my_struct: MyStruct = ...;
    #[with]
    let elems: Vec<&Container> = my_struct.query_protected();
    …
}

If you don't want to pull an external dependency with "macro magic" / if you want to better understand how it works, you can directly write what this macro unsugars to:

Unsugaring
#![forbid(unsafe_code)] // No unsafe!

impl MyStruct {
    fn with_query_protected<R> (
        self: &'_ MyStruct,
        threshold: usize,
        return_: impl for<'local> FnOnce(Vec<&'local Container>) -> R,
    ) -> R
    {
        return_(
            self.protected_vector
                .read()
                .unwrap()
                .iter()
                .filter(|i| i.u <= threshold)
                .collect()
        )
    }
}

fn example ()
{
    let my_struct: MyStruct = ...;
    my_struct.with_query_protected(|elems: Vec<&Container>| {
        …
    });
}


Removing that last heap-allocation (the .collect() into a Vec)

Now, in Rust we try to avoid heap allocations unless they are necessary. Here, for instance, yielding a fully-fledged Vec may not be necessary if, as a user of the "returned" value, you don't want to perform arbitrary indexing on it, but, instead, to just keep sequentially iterating on it. In that case, rather than a Vec which required eager iteration so as to collect the elements into heap-allocated storage, you can feature lazy iteration so as to be almost zero-cost:

#![forbid(unsafe_code)] // No unsafe!

use ::with_locals::with;

impl MyStruct {
    #[with('local)]
    fn query_protected (
        self: &'_ MyStruct,
        threshold: usize,
-   ) -> Vec<&'local Container>
+   ) -> &'local mut dyn Iterator<Item = &'local Container>
    {
+       &mut
            self.protected_vector
                .read()
                .unwrap()
                .iter()
                .filter(|i| i.u <= threshold)
-               .collect()
    }
}

#[with]
fn example ()
{
    let my_struct: MyStruct = ...;
    #[with]
    let elems = my_struct.query_protected(); // NO heap allocations!
+   for elem in elems {                      // NO heap allocations!
       …
+   }
}
  • Note: ideally we'd be returning an impl Iterator rather than a &mut dyn Iterator, but to be able to write the former when using the CPS pattern one would need to be able to use existential types in arbitrary positions –which is potentially mockable with the (min_)type_alias_impl_trait feature– but that cannot be done on stable Rust (in practice, we can hope that despite using &mut dyn here, the compiler may be able to optimize it into using the same static dispatch as with impl, through clever inlining and const-propagation).

Should the caller need a Vec / arbitrary indexing in example(), they can simply go back to the first shape by calling .collect() on it:

#[with]
let elems = my_struct.query_protected();
let elems: Vec<&Container> = elems.collect();
…
1 Like

This is beautiful guys, thank you @alice and @Yandros.

The first approach feels more natural to me at the moment, but I am inclined to research the CPS more, as I've got no prior experience with it and it seems quite useful.

Thanks again, much appreciated.