Struct lockfree_cuckoohash::LockFreeCuckooHash

pub struct LockFreeCuckooHash<K, V> where
    K: Eq + Hash,  { /* private fields */ }

LockFreeCuckooHash is a lock-free hash table using cuckoo hashing scheme. This implementation is based on the approach discussed in the paper:

“Nguyen, N., & Tsigas, P. (2014). Lock-Free Cuckoo Hashing. 2014 IEEE 34th International Conference on Distributed Computing Systems, 627-636.”

Cuckoo hashing is an open addressing solution for hash collisions. The basic idea of cuckoo hashing is to resolve collisions by using two or more hash functions instead of only one. In this implementation, we use two hash functions and two arrays (or tables).

The search operation only looks up two slots, i.e. table[0][hash0(key)] and table[1][hash1(key)]. If these two slots do not contain the key, the hash table does not contain the key. So the search operation only takes a constant time in the worst case.

The insert operation must pay the price for the quick search. The insert operation can only put the key into one of the two slots. However, when both slots are already occupied by other entries, it will be necessary to move other keys to their second locations (or back to their first locations) to make room for the new key, which is called a relocation. If the moved key can’t be relocated because the other slot of it is also occupied, another relocation is required and so on. If relocation is a very long chain or meets a infinite loop, the table should be resized or rehashed.

Implementations

impl<'guard, K, V> LockFreeCuckooHash<K, V> where
    K: 'guard + Eq + Hash, 

pub const DEFAULT_CAPACITY: usize

The default capacity of a new LockFreeCuckooHash when created by LockFreeHashMap::new().

pub fn new() -> Self

Create an empty LockFreeCuckooHash with default capacity.

pub fn with_capacity(capacity: usize) -> Self

Creates an empty LockFreeCuckooHash with the specified capacity.

pub fn capacity(&self) -> usize

Returns the capacity of this hash table.

pub fn size(&self) -> usize

Returns the number of used slots of this hash table.

pub unsafe fn clear(&self)

Safety

Clear the hashmap with the specified capacity. The caller must make sure the hashmap is not during a resize.

pub unsafe fn clear_with_capacity(&self, capacity: usize)

Safety

Clear the hashmap with the specified capacity. The caller must make sure the hashmap is not during a resize.

pub fn get<Q: ?Sized>(&self, key: &Q, guard: &'guard Guard) -> Option<&'guard V> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

Returns a reference to the value corresponding to the key.

Example:

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
map.insert(1, "a");
let guard = pin();
let v = map.get(&1, &guard);
assert_eq!(v, Some(&"a"));

pub fn get_key_value<Q: ?Sized>(
    &self,
    key: &Q,
    guard: &'guard Guard
) -> Option<(&'guard K, &'guard V)> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

Returns the key-value pair corresponding to the supplied key.

Example

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
map.insert(1, "a");
let guard = pin();
let v = map.get_key_value(&1, &guard);
assert_eq!(v, Some((&1, &"a")));

pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Hash + Eq, 

Returns true if the map contains a value for the specified key.

Example

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
map.insert(1, "a");
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

pub fn insert(&self, key: K, value: V) -> bool

Insert a new key-value pair into the map. If the map did not have this key present, false is returned. If the map did have this key present, the value is updated, and true is returned. If you want to get the replaced value, try insert_with_guard instead.

Example:

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
assert_eq!(map.insert(1, "a"), false);
assert_eq!(map.insert(2, "b"), false);
assert_eq!(map.insert(1, "aaa"), true);

pub fn insert_with_guard(
    &self,
    key: K,
    value: V,
    guard: &'guard Guard
) -> Option<&'guard V>

Insert a new key-value pair into the map. If the map did not have this key present, None is returned. If the map did have this key present, the value is updated, and the reference to the old value is returned. Different from insert(k, v), this method requires a user provided guard.

Example:

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
let guard = pin();
assert_eq!(map.insert_with_guard(1, "a", &guard), None);
assert_eq!(map.insert_with_guard(2, "b", &guard), None);
assert_eq!(map.insert_with_guard(1, "abc", &guard), Some(&"a"));

pub fn get_or_insert(&self, key: K, value: V, guard: &'guard Guard) -> &'guard V

Insert a new key-value pair into the map if the map does not contain the key. If the map contains the key, return the old value. If the map does not contain the key, insert the new key-value, and return the new value.

Notice: When two concurrent get_or_insert methods are trying to insert the same key, only one will succeed. But if a get_or_insert and a insert are called simultaneously with the same key, the get_or_insert may still can insert the key-value pair even if insert has already succeeded.

An example for concurrent get_or_inserts：

Thread A | Thread B

call get_or_insert(key, A) | call get_or_insert(key, B)

|

return value = A |

| return value = A

We can see, only one thread can insert the key-value, and the other will return the old value.

An example for concurrent get_or_insert and insert:

Thread A | Thread B

call get_or_insert(key, A) | call insert(key, B)

| return value = B

return value = A |

| call get(key, A)

| return value = A

We can see here, even if Thread B has already inserted (key, B) into the map, but Thread A can still insert (key, A), which is not consistent with the semantics of get_or_insert.

Example:

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
let guard = pin();
assert_eq!(map.get_or_insert(1, "a", &guard), &"a");
assert_eq!(map.get_or_insert(1, "b", &guard), &"a");

pub fn insert_if_not_exists(&self, key: K, value: V) -> bool

Insert a new key-value pair into the map if the map does not contain the key.

Notice: similar to get_or_insert, when two concurent insert_if_not_exists are called, only one will succeed. But when concurrent insert_if_not_exists and insert are called, insert_if_not_exists may still succeed even if insert has already inserted the pair.

Example:

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
let guard = pin();
assert_eq!(map.insert_if_not_exists(1, "a"), true);
assert_eq!(map.get(&1, &guard), Some(&"a"));
assert_eq!(map.insert_if_not_exists(1, "b"), false);
assert_eq!(map.get(&1, &guard), Some(&"a"));

pub fn compare_and_update(&self, key: K, new_value: V, old_value: &V) -> bool where
    V: PartialEq, 

Compare the cuurent value with old_value, update the value to new_value if they are equal. This method returns true if the update succeeds, otherwise returns false.

Example:

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
let guard = pin();
assert_eq!(map.insert(1, "a"), false);
assert_eq!(map.compare_and_update(1, "c", &"b"), false);
assert_eq!(map.get(&1, &guard), Some(&"a"));
assert_eq!(map.compare_and_update(1, "c", &"a"), true);
assert_eq!(map.get(&1, &guard), Some(&"c"));

pub fn remove<Q: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Hash + Eq, 

Removes a key from the map, returning true if the key was previously in the map. If you want to get the old value, try map.remove_with_guard() instead.

Example:

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
map.insert(1, "a");
assert_eq!(map.remove(&2), false);
assert_eq!(map.remove(&1), true);
assert_eq!(map.remove(&1), false);

pub fn remove_with_guard<Q: ?Sized>(
    &self,
    key: &Q,
    guard: &'guard Guard
) -> Option<&'guard V> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

Remove a key from the map. Different from remove(k), this method requires a user provided guard.

Example:

use lockfree_cuckoohash::{pin, LockFreeCuckooHash};
let map = LockFreeCuckooHash::new();
let guard = pin();
map.insert(1, "a");
assert_eq!(map.remove_with_guard(&2, &guard), None);
assert_eq!(map.remove_with_guard(&1, &guard), Some(&"a"));
assert_eq!(map.remove_with_guard(&1, &guard), None);

Trait Implementations

impl<K, V> Debug for LockFreeCuckooHash<K, V> where
    K: Debug + Eq + Hash,
    V: Debug, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V> Default for LockFreeCuckooHash<K, V> where
    K: Eq + Hash, 

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Drop for LockFreeCuckooHash<K, V> where
    K: Eq + Hash, 

fn drop(&mut self)

Executes the destructor for this type.