gix_hashtable/
lib.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//! Customized `HashMap` and Hasher implementation optimized for using `ObjectId`s as keys.
//!
//! The crate mirrors `std::collections` in layout for familiarity.
#![deny(missing_docs, rust_2018_idioms)]
#![forbid(unsafe_code)]

use gix_hash::ObjectId;
pub use hashbrown::{hash_map, hash_set, raw, Equivalent};

/// thread-safe types
pub mod sync {
    /// A map for associating data with object ids in a thread-safe fashion. It should scale well up to 256 threads.
    pub struct ObjectIdMap<V> {
        /// Sharing is done by the first byte of the incoming object id.
        shards: [parking_lot::Mutex<super::HashMap<gix_hash::ObjectId, V>>; 256],
    }

    impl<V> Default for ObjectIdMap<V> {
        fn default() -> Self {
            Self {
                shards: std::array::from_fn(|_| parking_lot::Mutex::new(super::HashMap::default())),
            }
        }
    }

    /// access and modifications - we only implement what's used within the `gix-*` ecosystem.
    impl<V> ObjectIdMap<V> {
        /// Insert `value` at `key` and return `None` if it's the first value at that location, or `Some(previous-value)`
        /// if `key` was already set.
        pub fn insert(&self, key: gix_hash::ObjectId, value: V) -> Option<V> {
            self.shards[key.as_slice()[0] as usize].lock().insert(key, value)
        }
    }
}

///
pub mod hash {
    /// A Hasher for usage with `HashMap` keys that are already robust hashes (like an `ObjectId`).
    /// The first `8` bytes of the hash are used as the `HashMap` hash
    #[derive(Default, Clone, Copy)]
    pub struct Hasher(u64);

    macro_rules! panic_other_writers {
        ($func:ident, $type:ty) => {
            #[cold]
            fn $func(&mut self, _i: $type) {
                panic!("This hasher only supports manually verified `Hash` implementations")
            }
        };
    }

    impl std::hash::Hasher for Hasher {
        fn finish(&self) -> u64 {
            self.0
        }

        #[inline(always)]
        fn write(&mut self, bytes: &[u8]) {
            self.0 = u64::from_ne_bytes(bytes[..8].try_into().unwrap());
        }

        // Panic if someone tries to use this with a different function,
        // only manually verified types should be used with this hasher
        panic_other_writers!(write_u8, u8);
        panic_other_writers!(write_u16, u16);
        panic_other_writers!(write_u32, u32);
        panic_other_writers!(write_u64, u64);
        panic_other_writers!(write_u128, u128);
        panic_other_writers!(write_usize, usize);
        panic_other_writers!(write_i8, i8);
        panic_other_writers!(write_i16, i16);
        panic_other_writers!(write_i32, i32);
        panic_other_writers!(write_i64, i64);
        panic_other_writers!(write_i128, i128);
        panic_other_writers!(write_isize, isize);
    }

    /// A Hasher for usage with `HashMap` keys that are already robust hashes (like an `ObjectId`).
    /// The first `8` bytes of the hash are used as the `HashMap` hash
    #[derive(Default, Clone, Copy)]
    pub struct Builder;
    impl std::hash::BuildHasher for Builder {
        type Hasher = Hasher;

        fn build_hasher(&self) -> Self::Hasher {
            Hasher::default()
        }
    }
}

/// A `HashMap` for usage with keys that are already robust hashes (like an `ObjectId`).
/// The first `8` bytes of the hash are used as the `HashMap` hash
pub type HashMap<K, V> = hashbrown::HashMap<K, V, hash::Builder>;
/// A `HashSet` for usage with keys that are already robust hashes (like an `ObjectId`).
/// The first `8` bytes of the hash are used as the `HashMap` hash
pub type HashSet<T = ObjectId> = hashbrown::HashSet<T, hash::Builder>;