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

gix_hashtable/
lib.rs
