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 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
//! Wrapper type for by-address hashing and comparison. //! //! [ByAddress] can be used to wrap any pointer type (i.e. any type that implements the Deref //! trait). This includes references, raw pointers, smart pointers like `Rc<T>` and `Box<T>`, and //! specialized pointer-like types such as `Vec<T>` and `String`. //! //! Comparison, ordering, and hashing of the wrapped pointer will be based on the address of its //! contents, rather than their value. //! //! ``` //! use by_address::ByAddress; //! use std::rc::Rc; //! //! let rc = Rc::new(5); //! let x = ByAddress(rc.clone()); //! let y = ByAddress(rc.clone()); //! //! // x and y are two pointers to the same address: //! assert_eq!(x, y); //! //! let z = ByAddress(Rc::new(5)); //! //! // *x and *z have the same value, but not the same address: //! assert_ne!(x, z); //! ``` //! //! You can use wrapped pointers as keys in hashed or ordered collections, like BTreeMap/BTreeSet //! or HashMap/HashSet, even if the target of the pointer doesn't implement hashing or ordering. //! This even includes pointers to trait objects, which usually don't implement the Eq trait //! because it is not object-safe. //! //! ``` //! # use by_address::ByAddress; //! # use std::collections::HashSet; //! # //! /// Call each item in `callbacks`, skipping any duplicate references. //! fn call_each_once(callbacks: &[&Fn()]) { //! let mut seen: HashSet<ByAddress<&Fn()>> = HashSet::new(); //! for &f in callbacks { //! if seen.insert(ByAddress(f)) { //! f(); //! } //! } //! } //! ``` //! //! If `T` is a pointer to an unsized type, then comparison and ordering of `ByAddress<T>` compare //! the entire fat pointer, not just the "thin" data address. This means that two slice pointers //! are consider equal only if they have the same starting address *and* length. //! //! ``` //! # use by_address::ByAddress; //! # //! let v = [1, 2, 3, 4]; //! //! assert_eq!(ByAddress(&v[0..4]), ByAddress(&v[0..4])); // Same address and length. //! assert_ne!(ByAddress(&v[0..4]), ByAddress(&v[0..2])); // Same address, different length. //! ``` //! //! However, due to limitations of safe Rust, hashing takes only the data address into account. //! **This may cause performance problems if you use slices as keys in a by-address HashMap or //! HashSet.** It won't cause correctness bugs, but it may cause a high rate of hash collisions if //! the keys include many slices with the same starting points but different lengths. //! //! ``` //! # use by_address::ByAddress; //! # use std::collections::hash_map::DefaultHasher; //! # use std::hash::{Hash, Hasher}; //! # //! fn hash<T: Hash>(t: T) -> u64 { //! let mut s = DefaultHasher::new(); //! t.hash(&mut s); //! s.finish() //! } //! //! let v = [1, 2, 3, 4]; //! assert_eq!(hash(ByAddress(&v[0..4])), //! hash(ByAddress(&v[0..2]))); // Uh-oh! //! ``` //! //! This crate does not depend on libstd, so it can be used in [`no_std`] projects. //! //! [`no_std`]: https://doc.rust-lang.org/book/first-edition/using-rust-without-the-standard-library.html //! [ByAddress]: struct.ByAddress.html // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your // option. This file may not be copied, modified, or distributed // except according to those terms. #![no_std] use core::cmp::Ordering; use core::convert::AsRef; use core::hash::{Hash, Hasher}; use core::ops::{Deref, DerefMut}; /// Wrapper for pointer types that implements by-address comparison. /// /// See the [crate-level documentation](index.html) for details. #[derive(Copy, Clone, Debug, Default)] pub struct ByAddress<T>(pub T) where T: ?Sized + Deref; impl<T> ByAddress<T> where T: ?Sized + Deref { /// Convenience method for pointer casts. fn addr(&self) -> *const T::Target { &*self.0 } } /// Raw pointer equality impl<T> PartialEq for ByAddress<T> where T: ?Sized + Deref { fn eq(&self, other: &Self) -> bool { self.addr() == other.addr() } } impl<T> Eq for ByAddress<T> where T: ?Sized + Deref {} /// Raw pointer ordering impl<T> Ord for ByAddress<T> where T: ?Sized + Deref { fn cmp(&self, other: &Self) -> Ordering { self.addr().cmp(&other.addr()) } } /// Raw pointer comparison impl<T> PartialOrd for ByAddress<T> where T: ?Sized + Deref { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.addr().cmp(&other.addr())) } } /// Raw pointer hashing impl<T> Hash for ByAddress<T> where T: ?Sized + Deref { fn hash<H: Hasher>(&self, state: &mut H) { // FIXME: For fat pointers to dynamically-sized types, this discards the extra data (vtable // pointer or length), so it may have a high collision rate in certain cases. (self.addr() as *const ()).hash(state) } } // Generic conversion traits: impl<T> Deref for ByAddress<T> where T: ?Sized + Deref { type Target = T; fn deref(&self) -> &Self::Target { &self.0 } } impl<T> DerefMut for ByAddress<T> where T: ?Sized + Deref { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.0 } } impl<T, U> AsRef<U> for ByAddress<T> where T: ?Sized + Deref + AsRef<U> { fn as_ref(&self) -> &U { self.0.as_ref() } } impl<T, U> AsMut<U> for ByAddress<T> where T: ?Sized + Deref + AsMut<U> { fn as_mut(&mut self) -> &mut U { self.0.as_mut() } } impl<T> From<T> for ByAddress<T> where T: Deref { fn from(t: T) -> ByAddress<T> { ByAddress(t) } }