zng_unique_id/
lib.rs

Help
1#![doc(html_favicon_url = "https://raw.githubusercontent.com/zng-ui/zng/main/examples/image/res/zng-logo-icon.png")]
2#![doc(html_logo_url = "https://raw.githubusercontent.com/zng-ui/zng/main/examples/image/res/zng-logo.png")]
3//!
4//! Macros for generating unique ID types.
5//!
6//! # Crate
7//!
8#![doc = include_str!(concat!("../", std::env!("CARGO_PKG_README")))]
9#![warn(unused_extern_crates)]
10#![warn(missing_docs)]
11
12use std::{
13    hash::{BuildHasher, Hash, Hasher},
14    num::{NonZeroU32, NonZeroU64},
15    ops,
16    sync::atomic::{AtomicU32, Ordering},
17};
18
19use rayon::iter::{FromParallelIterator, IntoParallelIterator, IntoParallelRefIterator, IntoParallelRefMutIterator};
20
21#[doc(hidden)]
22#[cfg(target_has_atomic = "64")]
23pub use std::sync::atomic::AtomicU64;
24
25#[doc(hidden)]
26#[cfg(not(target_has_atomic = "64"))]
27pub struct AtomicU64(parking_lot::Mutex<u64>);
28#[cfg(not(target_has_atomic = "64"))]
29impl AtomicU64 {
30    pub const fn new(u: u64) -> Self {
31        Self(parking_lot::Mutex::new(u))
32    }
33
34    fn fetch_add(&self, u: u64, _: Ordering) -> u64 {
35        let mut a = self.0.lock();
36        let r = *a;
37        *a += u;
38        r
39    }
40}
41
42#[cfg(feature = "named")]
43mod named;
44
45#[doc(hidden)]
46pub mod hot_reload;
47
48pub use hot_reload::lazy_static_init;
49
50#[cfg(feature = "named")]
51pub use named::*;
52
53#[doc(hidden)]
54pub use pastey::paste;
55
56/// Declare a new unique id type that is backed by a `NonZeroU32`.
57#[macro_export]
58macro_rules! unique_id_32 {
59    ($(#[$attrs:meta])* $vis:vis struct $Type:ident $(< $T:ident $(:($($bounds:tt)+))? >)? $(: $ParentId:path)? ;) => {
60       $crate::unique_id! {
61            request {
62                $(#[$attrs])*
63                ///
64                /// # Memory
65                ///
66                /// The internal number is a [`NonZeroU32`], that means that
67                #[doc=concat!("`Option<", stringify!($Type), ">`")]
68                /// and
69                #[doc=concat!("`", stringify!($Type), "`")]
70                /// are the same size as `u32`.
71                ///
72                /// # As Hash
73                ///
74                /// The generated internal number has good statistical distribution and can be used as its own hash,
75                /// although it is not cryptographically safe, as it is simply a sequential counter scrambled using a modified
76                /// `splitmix64`.
77                ///
78                /// [`NonZeroU32`]: std::num::NonZeroU32
79                ///
80                /// # Static
81                ///
82                /// The unique ID cannot be generated at compile time, but you can use the `static_id!` macro to declare
83                /// a lazy static that instantiates the ID.
84                $vis struct $Type $(< $T $(:($($bounds)+))? >)? $(: $ParentId)? ;
85            }
86            non_zero {
87                std::num::NonZeroU32
88            }
89            atomic {
90                std::sync::atomic::AtomicU32
91            }
92            next_id {
93                $crate::next_id32
94            }
95            literal {
96                u32
97            }
98            to_hash {
99                $crate::un_hash32
100            }
101            to_sequential {
102                $crate::un_hash32
103            }
104       }
105    }
106}
107
108/// Declare a new unique id type that is backed by a `NonZeroU64`.
109#[macro_export]
110macro_rules! unique_id_64 {
111    ($(#[$attrs:meta])* $vis:vis struct $Type:ident $(< $T:ident $(:($($bounds:tt)+))? >)? $(: $ParentId:path)? ;) => {
112        $crate::unique_id! {
113            request {
114                $(#[$attrs])*
115                ///
116                /// # Memory
117                ///
118                /// The internal number is a [`NonZeroU64`], that means that
119                #[doc=concat!("`Option<", stringify!($Type), ">`")]
120                /// and
121                #[doc=concat!("`", stringify!($Type), "`")]
122                /// are the same size as `u64`.
123                ///
124                /// # As Hash
125                ///
126                /// The generated internal number has good statistical distribution and can be used as its own hash,
127                /// although it is not cryptographically safe, as it is simply a sequential counter scrambled using `splitmix64`.
128                ///
129                /// [`NonZeroU64`]: std::num::NonZeroU64
130                ///
131                /// # Static
132                ///
133                /// The unique ID cannot be generated at compile time, but you can use the `static_id!` macro to declare
134                /// a lazy static that instantiates the ID.
135                $vis struct $Type $(< $T $(:($($bounds)+))? >)? $(: $ParentId)? ;
136            }
137            non_zero {
138                std::num::NonZeroU64
139            }
140            atomic {
141                $crate::AtomicU64
142            }
143            next_id {
144                $crate::next_id64
145            }
146            literal {
147                u64
148            }
149            to_hash {
150                $crate::splitmix64
151            }
152            to_sequential {
153                $crate::un_splitmix64
154            }
155        }
156    };
157}
158
159/// Implement [`bytemuck`] trait for the unique ID.
160///
161/// [`bytemuck`]: https://docs.rs/bytemuck/
162#[macro_export]
163macro_rules! impl_unique_id_bytemuck {
164    ($Type:ident $(< $T:ident $(:($($bounds:tt)+))? >)?) => {
165        // SAFETY: $Type a transparent wrapper on a std non-zero integer.
166        unsafe impl$(<$T $(: $($bounds)+)?>)? bytemuck::NoUninit for $Type $(<$T>)? { }
167        unsafe impl$(<$T $(: $($bounds)+)?>)? bytemuck::ZeroableInOption for $Type $(<$T>)? { }
168        unsafe impl$(<$T $(: $($bounds)+)?>)? bytemuck::PodInOption for $Type $(<$T>)? { }
169    }
170}
171
172#[doc(hidden)]
173#[macro_export]
174macro_rules! unique_id {
175    (
176        request {
177            $(#[$attrs:meta])* $vis:vis struct $Type:ident $(< $T:ident $(:($($bounds:tt)+))? >)? $(: $ParentId:path)? ;
178        }
179        non_zero {
180            $non_zero:path
181        }
182        atomic {
183            $atomic:path
184        }
185        next_id {
186            $next_id:path
187        }
188        literal {
189            $lit:ident
190        }
191        to_hash {
192            $to_hash:path
193        }
194        to_sequential {
195            $to_sequential:path
196        }
197    ) => {
198
199        $(#[$attrs])*
200        #[repr(transparent)]
201        $vis struct $Type $(<$T $(: $($bounds)+)?>)? ($non_zero $(, std::marker::PhantomData<$T>)?);
202
203        impl$(<$T $(: $($bounds)+)?>)? Clone for $Type $(<$T>)? {
204            fn clone(&self) -> Self {
205                *self
206            }
207        }
208        impl$(<$T $(: $($bounds)+)?>)? Copy for $Type $(<$T>)? {
209        }
210        impl$(<$T $(: $($bounds)+)?>)? PartialEq for $Type $(<$T>)? {
211            fn eq(&self, other: &Self) -> bool {
212                self.0 == other.0
213            }
214        }
215        impl$(<$T $(: $($bounds)+)?>)? Eq for $Type $(<$T>)? {
216        }
217        impl$(<$T $(: $($bounds)+)?>)? std::hash::Hash for $Type $(<$T>)? {
218            fn hash<H>(&self, state: &mut H)
219            where
220                H: std::hash::Hasher
221            {
222                std::hash::Hash::hash(&self.0, state)
223            }
224        }
225        impl$(<$T $(: $($bounds)+)?>)? $crate::UniqueId for $Type $(<$T>)? {
226            fn new_unique() -> Self {
227                Self::new_unique()
228            }
229        }
230
231        #[allow(dead_code)]
232        impl$(<$T $(: $($bounds)+)?>)? $Type $(<$T>)? {
233            $crate::unique_id! {
234                new_unique {
235                    $($ParentId, )? $(<$T>)?
236                }
237                atomic {
238                    $atomic
239                }
240                next_id {
241                    $next_id
242                }
243            }
244
245            /// Retrieve the underlying value.
246            pub fn get(self) -> $lit {
247                self.0.get()
248            }
249
250            /// Un-scramble the underlying value to get the original sequential count number.
251            ///
252            /// If two IDs, `id0` and `id1` where generated by the same thread then `id0.sequential() < id1.sequential()`.
253            pub fn sequential(self) -> $lit {
254                $to_sequential(self.0.get())
255            }
256
257            /// Creates an ID from a raw value.
258            ///
259            /// The value must not be zero, panics if it is, the value must have been provided by [`get`] otherwise
260            /// the ID will not be unique.
261            ///
262            /// [`get`]: Self::get
263            pub fn from_raw(raw: $lit) -> Self {
264                use $non_zero as __non_zero;
265
266                Self(__non_zero::new(raw).unwrap() $(, std::marker::PhantomData::<$T>)?)
267            }
268
269            /// Creates an ID from a [`sequential`] number.
270            ///
271            /// # Safety
272            ///
273            /// The value must not be zero, panics if it is, the value must have been provided by [`sequential`] otherwise
274            /// the ID will not be unique.
275            ///
276            /// [`sequential`]: Self::sequential
277            pub fn from_sequential(num: $lit) -> Self {
278                use $non_zero as __non_zero;
279
280                Self(__non_zero::new($to_hash(num)).unwrap() $(, std::marker::PhantomData::<$T>)?)
281            }
282        }
283    };
284
285    (
286        new_unique {
287            $ParentId:path, $(<$T:ident>)?
288        }
289        atomic {
290            $atomic:path
291        }
292        next_id {
293            $next_id:path
294        }
295    ) => {
296        /// Generates a new unique ID.
297        pub fn new_unique() -> Self {
298            use $ParentId as __parent;
299            let id = __parent $(::<$T>)? ::new_unique().get();
300            Self::from_raw(id)
301        }
302    };
303
304    (
305        new_unique {
306            $(<$T:ident>)?
307        }
308        atomic {
309            $atomic:path
310        }
311        next_id {
312            $next_id:path
313        }
314    ) => {
315        /// Generates a new unique ID.
316        pub fn new_unique() -> Self {
317            use $atomic as __atomic;
318
319            $crate::hot_static! {
320                static NEXT: __atomic = __atomic::new(1);
321            }
322            let __ref = $crate::hot_static_ref!(NEXT);
323            Self($next_id(__ref) $(, std::marker::PhantomData::<$T>)?)
324        }
325    };
326}
327
328#[doc(hidden)]
329pub fn next_id32(next: &'static AtomicU32) -> NonZeroU32 {
330    loop {
331        // the sequential next id is already in the variable.
332        let id = next.fetch_add(1, Ordering::Relaxed);
333
334        if id == 0 {
335            tracing::error!("id factory reached `u32::MAX`, will start reusing");
336        } else {
337            let id = hash32(id);
338            if let Some(id) = NonZeroU32::new(id) {
339                return id;
340            }
341        }
342    }
343}
344#[doc(hidden)]
345pub fn next_id64(next: &'static AtomicU64) -> NonZeroU64 {
346    loop {
347        // the sequential next id is already in the variable.
348        let id = next.fetch_add(1, Ordering::Relaxed);
349
350        if id == 0 {
351            tracing::error!("id factory reached `u64::MAX`, will start reusing");
352        } else {
353            // remove the sequential clustering.
354            let id = splitmix64(id);
355            if let Some(id) = NonZeroU64::new(id) {
356                return id;
357            }
358        }
359    }
360}
361
362#[doc(hidden)]
363pub fn hash32(n: u32) -> u32 {
364    use std::num::Wrapping as W;
365
366    let mut z = W(n);
367    z = ((z >> 16) ^ z) * W(0x45d9f3b);
368    z = ((z >> 16) ^ z) * W(0x45d9f3b);
369    z = (z >> 16) ^ z;
370    z.0
371}
372#[doc(hidden)]
373pub fn un_hash32(z: u32) -> u32 {
374    use std::num::Wrapping as W;
375
376    let mut n = W(z);
377    n = ((n >> 16) ^ n) * W(0x119de1f3);
378    n = ((n >> 16) ^ n) * W(0x119de1f3);
379    n = (n >> 16) ^ n;
380    n.0
381}
382
383#[doc(hidden)]
384pub fn splitmix64(n: u64) -> u64 {
385    use std::num::Wrapping as W;
386
387    let mut z = W(n);
388    z = (z ^ (z >> 30)) * W(0xBF58476D1CE4E5B9u64);
389    z = (z ^ (z >> 27)) * W(0x94D049BB133111EBu64);
390    z = z ^ (z >> 31);
391    z.0
392}
393#[doc(hidden)]
394pub fn un_splitmix64(z: u64) -> u64 {
395    use std::num::Wrapping as W;
396
397    let mut n = W(z);
398    n = (n ^ (n >> 31) ^ (n >> 62)) * W(0x319642b2d24d8ec3u64);
399    n = (n ^ (n >> 27) ^ (n >> 54)) * W(0x96de1b173f119089u64);
400    n = n ^ (n >> 30) ^ (n >> 60);
401    n.0
402}
403
404/// Map specialized for unique IDs that are already a randomized hash.
405#[derive(Clone, Debug)]
406pub struct IdMap<K, V>(hashbrown::HashMap<K, V, BuildIdHasher>);
407impl<K, V> IdMap<K, V> {
408    /// New `const` default.
409    pub const fn new() -> Self {
410        Self(hashbrown::HashMap::with_hasher(BuildIdHasher))
411    }
412}
413impl<K, V> Default for IdMap<K, V> {
414    fn default() -> Self {
415        Self::new()
416    }
417}
418impl<K, V> ops::Deref for IdMap<K, V> {
419    type Target = hashbrown::HashMap<K, V, BuildIdHasher>;
420
421    fn deref(&self) -> &Self::Target {
422        &self.0
423    }
424}
425impl<K, V> ops::DerefMut for IdMap<K, V> {
426    fn deref_mut(&mut self) -> &mut Self::Target {
427        &mut self.0
428    }
429}
430impl<K, V> IntoIterator for IdMap<K, V> {
431    type Item = (K, V);
432
433    type IntoIter = hashbrown::hash_map::IntoIter<K, V>;
434
435    fn into_iter(self) -> Self::IntoIter {
436        self.0.into_iter()
437    }
438}
439impl<'a, K, V> IntoIterator for &'a IdMap<K, V> {
440    type Item = (&'a K, &'a V);
441
442    type IntoIter = hashbrown::hash_map::Iter<'a, K, V>;
443
444    fn into_iter(self) -> Self::IntoIter {
445        self.0.iter()
446    }
447}
448impl<'a, K, V> IntoIterator for &'a mut IdMap<K, V> {
449    type Item = (&'a K, &'a mut V);
450
451    type IntoIter = hashbrown::hash_map::IterMut<'a, K, V>;
452
453    fn into_iter(self) -> Self::IntoIter {
454        self.0.iter_mut()
455    }
456}
457impl<K: Send, V: Send> IntoParallelIterator for IdMap<K, V> {
458    type Iter = hashbrown::hash_map::rayon::IntoParIter<K, V>;
459
460    type Item = (K, V);
461
462    fn into_par_iter(self) -> Self::Iter {
463        self.0.into_par_iter()
464    }
465}
466impl<'a, K: Sync, V: Sync> IntoParallelIterator for &'a IdMap<K, V> {
467    type Iter = hashbrown::hash_map::rayon::ParIter<'a, K, V>;
468
469    type Item = (&'a K, &'a V);
470
471    fn into_par_iter(self) -> Self::Iter {
472        self.0.par_iter()
473    }
474}
475impl<'a, K: Sync, V: Send> IntoParallelIterator for &'a mut IdMap<K, V> {
476    type Iter = hashbrown::hash_map::rayon::ParIterMut<'a, K, V>;
477
478    type Item = (&'a K, &'a mut V);
479
480    fn into_par_iter(self) -> Self::Iter {
481        self.0.par_iter_mut()
482    }
483}
484impl<K: Eq + Hash, V> FromIterator<(K, V)> for IdMap<K, V> {
485    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
486        Self(FromIterator::from_iter(iter))
487    }
488}
489impl<K: Eq + Hash + Send, V: Send> FromParallelIterator<(K, V)> for IdMap<K, V> {
490    fn from_par_iter<I>(par_iter: I) -> Self
491    where
492        I: IntoParallelIterator<Item = (K, V)>,
493    {
494        Self(FromParallelIterator::from_par_iter(par_iter))
495    }
496}
497
498/// Set specialized for unique IDs that are already a randomized hash.
499#[derive(Clone, Debug)]
500pub struct IdSet<K>(hashbrown::HashSet<K, BuildIdHasher>);
501impl<K> IdSet<K> {
502    /// New `const` default.
503    pub const fn new() -> Self {
504        Self(hashbrown::HashSet::with_hasher(BuildIdHasher))
505    }
506}
507impl<K> Default for IdSet<K> {
508    fn default() -> Self {
509        Self::new()
510    }
511}
512impl<K> ops::Deref for IdSet<K> {
513    type Target = hashbrown::HashSet<K, BuildIdHasher>;
514
515    fn deref(&self) -> &Self::Target {
516        &self.0
517    }
518}
519impl<K> ops::DerefMut for IdSet<K> {
520    fn deref_mut(&mut self) -> &mut Self::Target {
521        &mut self.0
522    }
523}
524impl<K> IntoIterator for IdSet<K> {
525    type Item = K;
526
527    type IntoIter = hashbrown::hash_set::IntoIter<K>;
528
529    fn into_iter(self) -> Self::IntoIter {
530        self.0.into_iter()
531    }
532}
533impl<'a, K> IntoIterator for &'a IdSet<K> {
534    type Item = &'a K;
535
536    type IntoIter = hashbrown::hash_set::Iter<'a, K>;
537
538    fn into_iter(self) -> Self::IntoIter {
539        self.0.iter()
540    }
541}
542impl<K: Send> IntoParallelIterator for IdSet<K> {
543    type Iter = hashbrown::hash_set::rayon::IntoParIter<K>;
544
545    type Item = K;
546
547    fn into_par_iter(self) -> Self::Iter {
548        self.0.into_par_iter()
549    }
550}
551impl<'a, K: Sync> IntoParallelIterator for &'a IdSet<K> {
552    type Iter = hashbrown::hash_set::rayon::ParIter<'a, K>;
553
554    type Item = &'a K;
555
556    fn into_par_iter(self) -> Self::Iter {
557        self.0.par_iter()
558    }
559}
560impl<K: Eq + Hash> FromIterator<K> for IdSet<K> {
561    fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self {
562        Self(FromIterator::from_iter(iter))
563    }
564}
565impl<K: Eq + Hash + Send> FromParallelIterator<K> for IdSet<K> {
566    fn from_par_iter<I>(par_iter: I) -> Self
567    where
568        I: IntoParallelIterator<Item = K>,
569    {
570        Self(FromParallelIterator::from_par_iter(par_iter))
571    }
572}
573impl<K: Eq + Hash> PartialEq for IdSet<K> {
574    fn eq(&self, other: &Self) -> bool {
575        self.0 == other.0
576    }
577}
578impl<K: Eq + Hash> Eq for IdSet<K> {}
579
580/// Entry in [`IdMap`].
581pub type IdEntry<'a, K, V> = hashbrown::hash_map::Entry<'a, K, V, BuildIdHasher>;
582
583/// Occupied entry in an [`IdEntry`].
584pub type IdOccupiedEntry<'a, K, V> = hashbrown::hash_map::OccupiedEntry<'a, K, V, BuildIdHasher>;
585
586/// Vacant entry in an [`IdEntry`].
587pub type IdVacantEntry<'a, K, V> = hashbrown::hash_map::VacantEntry<'a, K, V, BuildIdHasher>;
588
589/// Build [`IdHasher`].
590#[derive(Default, Clone, Debug, Copy)]
591pub struct BuildIdHasher;
592impl BuildHasher for BuildIdHasher {
593    type Hasher = IdHasher;
594
595    fn build_hasher(&self) -> Self::Hasher {
596        IdHasher::default()
597    }
598}
599
600/// No-op hasher.
601///
602/// This hasher supports only `write_u32` and `write_u64`, other methods panic.
603///
604/// This hasher does nothing, it uses the `u32` or `u64` value directly as a hash.
605#[derive(Default)]
606pub struct IdHasher(u64);
607impl Hasher for IdHasher {
608    fn write(&mut self, _: &[u8]) {
609        unimplemented!("`only `write_u32` and `write_u64` are supported");
610    }
611
612    fn write_u32(&mut self, id: u32) {
613        self.0 = id as u64;
614    }
615
616    fn write_u64(&mut self, id: u64) {
617        self.0 = id;
618    }
619
620    fn finish(&self) -> u64 {
621        self.0
622    }
623}
624
625/// Trait implemented for all generated unique ID types.
626pub trait UniqueId: Clone + Copy + PartialEq + Eq + Hash {
627    /// New unique ID.
628    fn new_unique() -> Self;
629}
630
631/// Declares a static unique ID that is lazy inited.
632///
633/// Dereferencing this static generates the ID and caches it.
634///
635/// # Examples
636///
637/// ```
638/// # fn main() { }
639/// # use zng_unique_id::*;
640/// #
641/// # unique_id_32! {
642/// #     pub struct StateId<T: (std::any::Any)>;
643/// # }
644/// #
645/// static_id! {
646///     /// Metadata foo ID.
647///     pub static ref FOO_ID: StateId<bool>;
648/// }
649/// ```
650#[macro_export]
651macro_rules! static_id {
652    ($(
653        $(#[$attr:meta])*
654        $vis:vis static ref $IDENT:ident: $IdTy:ty;
655    )+) => {
656        $(
657            $crate::lazy_static! {
658                $(#[$attr])*
659                $vis static ref $IDENT: $IdTy = <$IdTy as $crate::UniqueId>::new_unique();
660            }
661        )+
662    };
663}
zng_unique_id/lib.rs

zng_unique_id/
lib.rs
