Thread-safe value register

help
1

I need a thread-safe container that can give unique ids to values that are different.
There should be method to get a reference to the value from the id. Cloning creates a struct that points to the same underlying register.

struct Id(usize);
trait Register: Send + Clone {
    type Value: PartialEq;
    // registration via non-mut reference is possible
    fn add(&self, v: Self::Value) -> Id;
    fn get(&self, id: Id) -> &Self::Value;
}

A simple Arc<Mutex<Vec<Value>>>> does not allow giving out a reference since the lifetime of a reference is tied to MutexGuard. I could wrap MutexGuard in another reference type but that is bound to lead a dead-lock at some point.

A lock-free structure that is Vec of Vec where Vecs are never resized might work. Does something like this exist?

2

The solution is to not guard the values with a mutex.

struct Register {
    map: Arc<Mutex<HashMap<Id, Arc<Value>>>>>,
}

Here you would be able to return a clone of the Arc to the user.

3

Here is a small implementation using the given solution. The register has RegisterValues that can be compared without referencing pointers. The cost of comparison has already been paid when the value was added. To get the value, another wrapper is needed: ValueRef. These should only be kept around briefly to avoid allocation cost of Arc::make_mut when more items are added.

use std::sync::{Arc, Mutex};

type Value = String;

#[derive(Clone, Copy)]
struct Id(usize);

#[derive(Clone)]
pub struct Register {
    register: Arc<Mutex<Arc<Vec<Value>>>>,
}

impl Register {
    pub fn new() -> Self {
        Self {
            register: Arc::new(Mutex::new(Arc::new(Vec::new()))),
        }
    }
    pub fn add(&self, value: &Value) -> RegisterValue {
        let mut reg = self.register.lock().unwrap();
        // look for value
        if let Some(pos) = reg.iter().position(|v| v == value) {
            return self.register_value(pos);
        }
        // When there is still a ValueRef pointing to this block,
        // it will be cloned.
        let reg = Arc::make_mut(&mut reg);
        let pos = reg.len();
        reg.push(value.clone());
        self.register_value(pos)
    }
    fn register_value(&self, id: usize) -> RegisterValue {
        RegisterValue {
            register: self.clone(),
            id: Id(id),
        }
    }
    fn get(&self, id: Id) -> ValueRef {
        let reg = self.register.lock().unwrap();
        ValueRef {
            data: reg.clone(),
            id: id.0,
        }
    }
}

#[derive(Clone)]
pub struct RegisterValue {
    register: Register,
    id: Id,
}

impl RegisterValue {
    pub fn to_ref(&self) -> ValueRef {
        self.register.get(self.id)
    }
    pub fn register(&self) -> &Register {
        &self.register
    }
}

// Quickly compare values without dereferencing any pointers when values are
// from the same register, full comparison otherwise
impl PartialEq<RegisterValue> for RegisterValue {
    fn eq(&self, rhs: &RegisterValue) -> bool {
        if Arc::ptr_eq(&self.register.register, &rhs.register.register) {
            self.id.0 == rhs.id.0
        } else {
            *self.register.get(self.id) == *rhs.register.get(rhs.id)
        }
    }
}

pub struct ValueRef {
    data: Arc<Vec<Value>>,
    id: usize,
}

impl std::ops::Deref for ValueRef {
    type Target = Value;
    fn deref(&self) -> &Self::Target {
        &self.data[self.id]
    }
}

fn main() {
    let register = Register::new();
    let v1 = String::from("zzz");
    let rv1 = register.add(&v1);
    let v2 = String::from("aaa");
    let rv2 = register.add(&v2);
    let result = rv1 == rv2;
    println!("{} == {}: {}", *rv1.to_ref(), *rv2.to_ref(), result);
}
4

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.