Crate read_write_store

A concurrent, unordered collection where each element has an internally generated ID and a read-write lock.

A store has O(1) time complexity for insertion, removal and lookups, although memory allocations triggered by insertion may cause a performance spike.

Example

// Note that we only need an immutable reference to the store
let store = RwStore::new();

// Inserting an element yields an ID
let id = store.insert(42);

{
// You can read the element's value using that ID
let read_lock = store.read(id).unwrap();
assert_eq!(*read_lock, 42);

// Concurrent reads are possible
assert!(store.read_with_timeout(id, DontBlock).is_ok());
// But reading and writing at the same time won't work
assert!(store.write_with_timeout(id, DontBlock).is_err());
}

{
// You can also acquire a write lock using an ID
let mut write_lock = store.write(id).unwrap();
*write_lock = 24;
assert_eq!(*write_lock, 24);

// Predictably, you cannot have multiple writers
assert!(store.write_with_timeout(id, DontBlock).is_err());
}

// Elements can of course be removed using their ID
assert_eq!(store.remove(id), Some(24));

// Now if we try to read using the ID, it will fail gracefully
assert!(store.read(id).is_none());

Allocation behavior

• An empty store does not require any allocation.
• Once an element is inserted, a fixed size block of element slots will be allocated.
• As more space is needed, more blocks will be allocated which tend to increase in size. All allocated blocks are used alongside all previously allocated blocks; elements are never moved.
• All removed elements whose memory is ready for reuse are tracked, so removing an element may allocate.

Caveats

• When a block of elements is allocated internally, it won’t be deallocated until the store is dropped. This allows the element ID’s to contain a pointer to the element that is valid for the lifetime of the store.
• Every element has 8 bytes of overhead.
• The store itself has a non-trivial memory overhead.
• For performance reasons, no facilities are provided for querying the number of elements in the store.

Safety

Each element inserted into a store is given an internal unique ID. This begs the question, what happens when an ID from one store is used with another? When debug assertions are enabled, a best effort attempt is made to panic when using an ID from a different store, but when they are disabled (i.e. in release mode), or if this best effort fails, this may cause undefined behavior.

Re-exports

pub use crate::id::*;

pub use crate::timeout::*;

Modules

id

An opaque handle used to read, modify or remove an element from an RwStore once it has been inserted.

iter

Iterator implementations for RwStore.

lock

RAII read and write locks for RwStore.

timeout

Timeout specifiers and error types.

Structs

RwStore

A concurrent, unordered collection where each element has an internally generated ID and a read-write lock. See the module-level documentation for more.

Constants

MAX_CONCURRENT_READS

The maximum number of read locks which can be held concurrently.