Struct UnsortedMap

pub struct UnsortedMap<K, V>
where
    K: OHash + Default + Debug,
    V: Cmov + Pod + Default + Debug,
{ /* private fields */ }

An unsorted map that is oblivious to the access pattern. The map uses cuckoo hashing with size-2 buckets, two tables and a deamortization queue. INSERTION_QUEUE_MAX_SIZE is the maximum size of the deamortization queue. DEAMORTIZED_INSERTIONS is the number of deamortized insertions to perform per insert call.

Invariants

• A key appears at most once in a valid element in between the two tables and the insertion queue.
• The two tables have the same capacity.
• The two tables have a different hash functions (different keys on the keyed hash function).

Implementations

impl<K, V> UnsortedMap<K, V>

where K: OHash + Default + Debug, V: Cmov + Pod + Default + Debug,

pub fn new(capacity: usize) -> Self

Creates a new UnsortedMap with the given capacity n.

pub fn get(&mut self, key: K, ret: &mut V) -> bool

Tries to get a value from the map.

Returns

• true if the key was found
• false if the key wasn’t found

Postconditions

• If the key was found, the value is written to ret
• If the key wasn’t found, ret is not modified

pub fn deamortize_insertion_queue(&mut self)

Deamortizes the insertion queue by trying to insert elements into the tables.

pub fn insert(&mut self, key: K, value: V)

Inserts an elementn into the map. If the insertion doesn’t finish, the removed element is inserted into the insertion queue.

Preconditions

• The key is not in the map already.

pub fn write(&mut self, key: K, value: V)

Updates a value that is already in the map.

Preconditions

• The key is in the map.

Returns

• true if the value was updated

Trait Implementations

impl<K, V> Debug for UnsortedMap<K, V>

where K: OHash + Default + Debug + Debug, V: Cmov + Pod + Default + Debug + Debug,

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

Formats the value using the given formatter.