gix_hashtable/
lib.rs

1//! Customized `HashMap` and Hasher implementation optimized for using `ObjectId`s as keys.
2//!
3//! The crate mirrors `std::collections` in layout for familiarity.
4#![deny(missing_docs, rust_2018_idioms)]
5#![forbid(unsafe_code)]
6
7use gix_hash::ObjectId;
8pub use hashbrown::{hash_map, hash_set, hash_table, Equivalent};
9
10/// thread-safe types
11pub mod sync {
12    /// A map for associating data with object ids in a thread-safe fashion. It should scale well up to 256 threads.
13    pub struct ObjectIdMap<V> {
14        /// Sharing is done by the first byte of the incoming object id.
15        shards: [parking_lot::Mutex<super::HashMap<gix_hash::ObjectId, V>>; 256],
16    }
17
18    impl<V> Default for ObjectIdMap<V> {
19        fn default() -> Self {
20            Self {
21                shards: std::array::from_fn(|_| parking_lot::Mutex::new(super::HashMap::default())),
22            }
23        }
24    }
25
26    /// access and modifications - we only implement what's used within the `gix-*` ecosystem.
27    impl<V> ObjectIdMap<V> {
28        /// Insert `value` at `key` and return `None` if it's the first value at that location, or `Some(previous-value)`
29        /// if `key` was already set.
30        pub fn insert(&self, key: gix_hash::ObjectId, value: V) -> Option<V> {
31            self.shards[key.as_slice()[0] as usize].lock().insert(key, value)
32        }
33    }
34}
35
36///
37pub mod hash {
38    /// A Hasher for usage with `HashMap` keys that are already robust hashes (like an `ObjectId`).
39    /// The first `8` bytes of the hash are used as the `HashMap` hash
40    #[derive(Default, Clone, Copy)]
41    pub struct Hasher(u64);
42
43    macro_rules! panic_other_writers {
44        ($func:ident, $type:ty) => {
45            #[cold]
46            fn $func(&mut self, _i: $type) {
47                panic!("This hasher only supports manually verified `Hash` implementations")
48            }
49        };
50    }
51
52    impl std::hash::Hasher for Hasher {
53        fn finish(&self) -> u64 {
54            self.0
55        }
56
57        #[inline(always)]
58        fn write(&mut self, bytes: &[u8]) {
59            self.0 = u64::from_ne_bytes(bytes[..8].try_into().unwrap());
60        }
61
62        // Panic if someone tries to use this with a different function,
63        // only manually verified types should be used with this hasher
64        panic_other_writers!(write_u8, u8);
65        panic_other_writers!(write_u16, u16);
66        panic_other_writers!(write_u32, u32);
67        panic_other_writers!(write_u64, u64);
68        panic_other_writers!(write_u128, u128);
69        panic_other_writers!(write_usize, usize);
70        panic_other_writers!(write_i8, i8);
71        panic_other_writers!(write_i16, i16);
72        panic_other_writers!(write_i32, i32);
73        panic_other_writers!(write_i64, i64);
74        panic_other_writers!(write_i128, i128);
75        panic_other_writers!(write_isize, isize);
76    }
77
78    /// A Hasher for usage with `HashMap` keys that are already robust hashes (like an `ObjectId`).
79    /// The first `8` bytes of the hash are used as the `HashMap` hash
80    #[derive(Default, Clone, Copy)]
81    pub struct Builder;
82    impl std::hash::BuildHasher for Builder {
83        type Hasher = Hasher;
84
85        fn build_hasher(&self) -> Self::Hasher {
86            Hasher::default()
87        }
88    }
89}
90
91/// A `HashMap` for usage with keys that are already robust hashes (like an `ObjectId`).
92/// The first `8` bytes of the hash are used as the `HashMap` hash
93pub type HashMap<K, V> = hashbrown::HashMap<K, V, hash::Builder>;
94/// A `HashSet` for usage with keys that are already robust hashes (like an `ObjectId`).
95/// The first `8` bytes of the hash are used as the `HashMap` hash
96pub type HashSet<T = ObjectId> = hashbrown::HashSet<T, hash::Builder>;
gix_hashtable/lib.rs

gix_hashtable/
lib.rs
