Initial vendor packages

Signed-off-by: Valentin Popov <valentin@popov.link>

1 files changed, 1702 insertions, 0 deletions

diff --git a/vendor/crossbeam-epoch/src/atomic.rs b/vendor/crossbeam-epoch/src/atomic.rs
new file mode 100644
index 0000000..41b4cd9
--- /dev/null
+++ b/vendor/crossbeam-epoch/src/atomic.rs
@@ -0,0 +1,1702 @@
+use alloc::boxed::Box;
+use core::alloc::Layout;
+use core::borrow::{Borrow, BorrowMut};
+use core::cmp;
+use core::fmt;
+use core::marker::PhantomData;
+use core::mem::{self, MaybeUninit};
+use core::ops::{Deref, DerefMut};
+use core::ptr;
+use core::slice;
+
+use crate::guard::Guard;
+use crate::primitive::sync::atomic::{AtomicUsize, Ordering};
+use crossbeam_utils::atomic::AtomicConsume;
+
+/// Given ordering for the success case in a compare-exchange operation, returns the strongest
+/// appropriate ordering for the failure case.
+#[inline]
+fn strongest_failure_ordering(ord: Ordering) -> Ordering {
+    use self::Ordering::*;
+    match ord {
+        Relaxed | Release => Relaxed,
+        Acquire | AcqRel => Acquire,
+        _ => SeqCst,
+    }
+}
+
+/// The error returned on failed compare-and-set operation.
+// TODO: remove in the next major version.
+#[deprecated(note = "Use `CompareExchangeError` instead")]
+pub type CompareAndSetError<'g, T, P> = CompareExchangeError<'g, T, P>;
+
+/// The error returned on failed compare-and-swap operation.
+pub struct CompareExchangeError<'g, T: ?Sized + Pointable, P: Pointer<T>> {
+    /// The value in the atomic pointer at the time of the failed operation.
+    pub current: Shared<'g, T>,
+
+    /// The new value, which the operation failed to store.
+    pub new: P,
+}
+
+impl<T, P: Pointer<T> + fmt::Debug> fmt::Debug for CompareExchangeError<'_, T, P> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("CompareExchangeError")
+            .field("current", &self.current)
+            .field("new", &self.new)
+            .finish()
+    }
+}
+
+/// Memory orderings for compare-and-set operations.
+///
+/// A compare-and-set operation can have different memory orderings depending on whether it
+/// succeeds or fails. This trait generalizes different ways of specifying memory orderings.
+///
+/// The two ways of specifying orderings for compare-and-set are:
+///
+/// 1. Just one `Ordering` for the success case. In case of failure, the strongest appropriate
+///    ordering is chosen.
+/// 2. A pair of `Ordering`s. The first one is for the success case, while the second one is
+///    for the failure case.
+// TODO: remove in the next major version.
+#[deprecated(
+    note = "`compare_and_set` and `compare_and_set_weak` that use this trait are deprecated, \
+            use `compare_exchange` or `compare_exchange_weak instead`"
+)]
+pub trait CompareAndSetOrdering {
+    /// The ordering of the operation when it succeeds.
+    fn success(&self) -> Ordering;
+
+    /// The ordering of the operation when it fails.
+    ///
+    /// The failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than
+    /// the success ordering.
+    fn failure(&self) -> Ordering;
+}
+
+#[allow(deprecated)]
+impl CompareAndSetOrdering for Ordering {
+    #[inline]
+    fn success(&self) -> Ordering {
+        *self
+    }
+
+    #[inline]
+    fn failure(&self) -> Ordering {
+        strongest_failure_ordering(*self)
+    }
+}
+
+#[allow(deprecated)]
+impl CompareAndSetOrdering for (Ordering, Ordering) {
+    #[inline]
+    fn success(&self) -> Ordering {
+        self.0
+    }
+
+    #[inline]
+    fn failure(&self) -> Ordering {
+        self.1
+    }
+}
+
+/// Returns a bitmask containing the unused least significant bits of an aligned pointer to `T`.
+#[inline]
+fn low_bits<T: ?Sized + Pointable>() -> usize {
+    (1 << T::ALIGN.trailing_zeros()) - 1
+}
+
+/// Panics if the pointer is not properly unaligned.
+#[inline]
+fn ensure_aligned<T: ?Sized + Pointable>(raw: usize) {
+    assert_eq!(raw & low_bits::<T>(), 0, "unaligned pointer");
+}
+
+/// Given a tagged pointer `data`, returns the same pointer, but tagged with `tag`.
+///
+/// `tag` is truncated to fit into the unused bits of the pointer to `T`.
+#[inline]
+fn compose_tag<T: ?Sized + Pointable>(data: usize, tag: usize) -> usize {
+    (data & !low_bits::<T>()) | (tag & low_bits::<T>())
+}
+
+/// Decomposes a tagged pointer `data` into the pointer and the tag.
+#[inline]
+fn decompose_tag<T: ?Sized + Pointable>(data: usize) -> (usize, usize) {
+    (data & !low_bits::<T>(), data & low_bits::<T>())
+}
+
+/// Types that are pointed to by a single word.
+///
+/// In concurrent programming, it is necessary to represent an object within a word because atomic
+/// operations (e.g., reads, writes, read-modify-writes) support only single words.  This trait
+/// qualifies such types that are pointed to by a single word.
+///
+/// The trait generalizes `Box<T>` for a sized type `T`.  In a box, an object of type `T` is
+/// allocated in heap and it is owned by a single-word pointer.  This trait is also implemented for
+/// `[MaybeUninit<T>]` by storing its size along with its elements and pointing to the pair of array
+/// size and elements.
+///
+/// Pointers to `Pointable` types can be stored in [`Atomic`], [`Owned`], and [`Shared`].  In
+/// particular, Crossbeam supports dynamically sized slices as follows.
+///
+/// ```
+/// use std::mem::MaybeUninit;
+/// use crossbeam_epoch::Owned;
+///
+/// let o = Owned::<[MaybeUninit<i32>]>::init(10); // allocating [i32; 10]
+/// ```
+pub trait Pointable {
+    /// The alignment of pointer.
+    const ALIGN: usize;
+
+    /// The type for initializers.
+    type Init;
+
+    /// Initializes a with the given initializer.
+    ///
+    /// # Safety
+    ///
+    /// The result should be a multiple of `ALIGN`.
+    unsafe fn init(init: Self::Init) -> usize;
+
+    /// Dereferences the given pointer.
+    ///
+    /// # Safety
+    ///
+    /// - The given `ptr` should have been initialized with [`Pointable::init`].
+    /// - `ptr` should not have yet been dropped by [`Pointable::drop`].
+    /// - `ptr` should not be mutably dereferenced by [`Pointable::deref_mut`] concurrently.
+    unsafe fn deref<'a>(ptr: usize) -> &'a Self;
+
+    /// Mutably dereferences the given pointer.
+    ///
+    /// # Safety
+    ///
+    /// - The given `ptr` should have been initialized with [`Pointable::init`].
+    /// - `ptr` should not have yet been dropped by [`Pointable::drop`].
+    /// - `ptr` should not be dereferenced by [`Pointable::deref`] or [`Pointable::deref_mut`]
+    ///   concurrently.
+    unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut Self;
+
+    /// Drops the object pointed to by the given pointer.
+    ///
+    /// # Safety
+    ///
+    /// - The given `ptr` should have been initialized with [`Pointable::init`].
+    /// - `ptr` should not have yet been dropped by [`Pointable::drop`].
+    /// - `ptr` should not be dereferenced by [`Pointable::deref`] or [`Pointable::deref_mut`]
+    ///   concurrently.
+    unsafe fn drop(ptr: usize);
+}
+
+impl<T> Pointable for T {
+    const ALIGN: usize = mem::align_of::<T>();
+
+    type Init = T;
+
+    unsafe fn init(init: Self::Init) -> usize {
+        Box::into_raw(Box::new(init)) as usize
+    }
+
+    unsafe fn deref<'a>(ptr: usize) -> &'a Self {
+        &*(ptr as *const T)
+    }
+
+    unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut Self {
+        &mut *(ptr as *mut T)
+    }
+
+    unsafe fn drop(ptr: usize) {
+        drop(Box::from_raw(ptr as *mut T));
+    }
+}
+
+/// Array with size.
+///
+/// # Memory layout
+///
+/// An array consisting of size and elements:
+///
+/// ```text
+///          elements
+///          |
+///          |
+/// ------------------------------------
+/// | size | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+/// ------------------------------------
+/// ```
+///
+/// Its memory layout is different from that of `Box<[T]>` in that size is in the allocation (not
+/// along with pointer as in `Box<[T]>`).
+///
+/// Elements are not present in the type, but they will be in the allocation.
+/// ```
+#[repr(C)]
+struct Array<T> {
+    /// The number of elements (not the number of bytes).
+    len: usize,
+    elements: [MaybeUninit<T>; 0],
+}
+
+impl<T> Array<T> {
+    fn layout(len: usize) -> Layout {
+        Layout::new::<Self>()
+            .extend(Layout::array::<MaybeUninit<T>>(len).unwrap())
+            .unwrap()
+            .0
+            .pad_to_align()
+    }
+}
+
+impl<T> Pointable for [MaybeUninit<T>] {
+    const ALIGN: usize = mem::align_of::<Array<T>>();
+
+    type Init = usize;
+
+    unsafe fn init(len: Self::Init) -> usize {
+        let layout = Array::<T>::layout(len);
+        let ptr = alloc::alloc::alloc(layout).cast::<Array<T>>();
+        if ptr.is_null() {
+            alloc::alloc::handle_alloc_error(layout);
+        }
+        ptr::addr_of_mut!((*ptr).len).write(len);
+        ptr as usize
+    }
+
+    unsafe fn deref<'a>(ptr: usize) -> &'a Self {
+        let array = &*(ptr as *const Array<T>);
+        slice::from_raw_parts(array.elements.as_ptr() as *const _, array.len)
+    }
+
+    unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut Self {
+        let array = &*(ptr as *mut Array<T>);
+        slice::from_raw_parts_mut(array.elements.as_ptr() as *mut _, array.len)
+    }
+
+    unsafe fn drop(ptr: usize) {
+        let len = (*(ptr as *mut Array<T>)).len;
+        let layout = Array::<T>::layout(len);
+        alloc::alloc::dealloc(ptr as *mut u8, layout);
+    }
+}
+
+/// An atomic pointer that can be safely shared between threads.
+///
+/// The pointer must be properly aligned. Since it is aligned, a tag can be stored into the unused
+/// least significant bits of the address. For example, the tag for a pointer to a sized type `T`
+/// should be less than `(1 << mem::align_of::<T>().trailing_zeros())`.
+///
+/// Any method that loads the pointer must be passed a reference to a [`Guard`].
+///
+/// Crossbeam supports dynamically sized types.  See [`Pointable`] for details.
+pub struct Atomic<T: ?Sized + Pointable> {
+    data: AtomicUsize,
+    _marker: PhantomData<*mut T>,
+}
+
+unsafe impl<T: ?Sized + Pointable + Send + Sync> Send for Atomic<T> {}
+unsafe impl<T: ?Sized + Pointable + Send + Sync> Sync for Atomic<T> {}
+
+impl<T> Atomic<T> {
+    /// Allocates `value` on the heap and returns a new atomic pointer pointing to it.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Atomic;
+    ///
+    /// let a = Atomic::new(1234);
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn new(init: T) -> Atomic<T> {
+        Self::init(init)
+    }
+}
+
+impl<T: ?Sized + Pointable> Atomic<T> {
+    /// Allocates `value` on the heap and returns a new atomic pointer pointing to it.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Atomic;
+    ///
+    /// let a = Atomic::<i32>::init(1234);
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn init(init: T::Init) -> Atomic<T> {
+        Self::from(Owned::init(init))
+    }
+
+    /// Returns a new atomic pointer pointing to the tagged pointer `data`.
+    fn from_usize(data: usize) -> Self {
+        Self {
+            data: AtomicUsize::new(data),
+            _marker: PhantomData,
+        }
+    }
+
+    /// Returns a new null atomic pointer.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Atomic;
+    ///
+    /// let a = Atomic::<i32>::null();
+    /// ```
+    #[cfg(not(crossbeam_loom))]
+    pub const fn null() -> Atomic<T> {
+        Self {
+            data: AtomicUsize::new(0),
+            _marker: PhantomData,
+        }
+    }
+    /// Returns a new null atomic pointer.
+    #[cfg(crossbeam_loom)]
+    pub fn null() -> Atomic<T> {
+        Self {
+            data: AtomicUsize::new(0),
+            _marker: PhantomData,
+        }
+    }
+
+    /// Loads a `Shared` from the atomic pointer.
+    ///
+    /// This method takes an [`Ordering`] argument which describes the memory ordering of this
+    /// operation.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// let guard = &epoch::pin();
+    /// let p = a.load(SeqCst, guard);
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn load<'g>(&self, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
+        unsafe { Shared::from_usize(self.data.load(ord)) }
+    }
+
+    /// Loads a `Shared` from the atomic pointer using a "consume" memory ordering.
+    ///
+    /// This is similar to the "acquire" ordering, except that an ordering is
+    /// only guaranteed with operations that "depend on" the result of the load.
+    /// However consume loads are usually much faster than acquire loads on
+    /// architectures with a weak memory model since they don't require memory
+    /// fence instructions.
+    ///
+    /// The exact definition of "depend on" is a bit vague, but it works as you
+    /// would expect in practice since a lot of software, especially the Linux
+    /// kernel, rely on this behavior.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    ///
+    /// let a = Atomic::new(1234);
+    /// let guard = &epoch::pin();
+    /// let p = a.load_consume(guard);
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn load_consume<'g>(&self, _: &'g Guard) -> Shared<'g, T> {
+        unsafe { Shared::from_usize(self.data.load_consume()) }
+    }
+
+    /// Stores a `Shared` or `Owned` pointer into the atomic pointer.
+    ///
+    /// This method takes an [`Ordering`] argument which describes the memory ordering of this
+    /// operation.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{Atomic, Owned, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// # unsafe { drop(a.load(SeqCst, &crossbeam_epoch::pin()).into_owned()); } // avoid leak
+    /// a.store(Shared::null(), SeqCst);
+    /// a.store(Owned::new(1234), SeqCst);
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn store<P: Pointer<T>>(&self, new: P, ord: Ordering) {
+        self.data.store(new.into_usize(), ord);
+    }
+
+    /// Stores a `Shared` or `Owned` pointer into the atomic pointer, returning the previous
+    /// `Shared`.
+    ///
+    /// This method takes an [`Ordering`] argument which describes the memory ordering of this
+    /// operation.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// let guard = &epoch::pin();
+    /// let p = a.swap(Shared::null(), SeqCst, guard);
+    /// # unsafe { drop(p.into_owned()); } // avoid leak
+    /// ```
+    pub fn swap<'g, P: Pointer<T>>(&self, new: P, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
+        unsafe { Shared::from_usize(self.data.swap(new.into_usize(), ord)) }
+    }
+
+    /// Stores the pointer `new` (either `Shared` or `Owned`) into the atomic pointer if the current
+    /// value is the same as `current`. The tag is also taken into account, so two pointers to the
+    /// same object, but with different tags, will not be considered equal.
+    ///
+    /// The return value is a result indicating whether the new pointer was written. On success the
+    /// pointer that was written is returned. On failure the actual current value and `new` are
+    /// returned.
+    ///
+    /// This method takes two `Ordering` arguments to describe the memory
+    /// ordering of this operation. `success` describes the required ordering for the
+    /// read-modify-write operation that takes place if the comparison with `current` succeeds.
+    /// `failure` describes the required ordering for the load operation that takes place when
+    /// the comparison fails. Using `Acquire` as success ordering makes the store part
+    /// of this operation `Relaxed`, and using `Release` makes the successful load
+    /// `Relaxed`. The failure ordering can only be `SeqCst`, `Acquire` or `Relaxed`
+    /// and must be equivalent to or weaker than the success ordering.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    ///
+    /// let guard = &epoch::pin();
+    /// let curr = a.load(SeqCst, guard);
+    /// let res1 = a.compare_exchange(curr, Shared::null(), SeqCst, SeqCst, guard);
+    /// let res2 = a.compare_exchange(curr, Owned::new(5678), SeqCst, SeqCst, guard);
+    /// # unsafe { drop(curr.into_owned()); } // avoid leak
+    /// ```
+    pub fn compare_exchange<'g, P>(
+        &self,
+        current: Shared<'_, T>,
+        new: P,
+        success: Ordering,
+        failure: Ordering,
+        _: &'g Guard,
+    ) -> Result<Shared<'g, T>, CompareExchangeError<'g, T, P>>
+    where
+        P: Pointer<T>,
+    {
+        let new = new.into_usize();
+        self.data
+            .compare_exchange(current.into_usize(), new, success, failure)
+            .map(|_| unsafe { Shared::from_usize(new) })
+            .map_err(|current| unsafe {
+                CompareExchangeError {
+                    current: Shared::from_usize(current),
+                    new: P::from_usize(new),
+                }
+            })
+    }
+
+    /// Stores the pointer `new` (either `Shared` or `Owned`) into the atomic pointer if the current
+    /// value is the same as `current`. The tag is also taken into account, so two pointers to the
+    /// same object, but with different tags, will not be considered equal.
+    ///
+    /// Unlike [`compare_exchange`], this method is allowed to spuriously fail even when comparison
+    /// succeeds, which can result in more efficient code on some platforms.  The return value is a
+    /// result indicating whether the new pointer was written. On success the pointer that was
+    /// written is returned. On failure the actual current value and `new` are returned.
+    ///
+    /// This method takes two `Ordering` arguments to describe the memory
+    /// ordering of this operation. `success` describes the required ordering for the
+    /// read-modify-write operation that takes place if the comparison with `current` succeeds.
+    /// `failure` describes the required ordering for the load operation that takes place when
+    /// the comparison fails. Using `Acquire` as success ordering makes the store part
+    /// of this operation `Relaxed`, and using `Release` makes the successful load
+    /// `Relaxed`. The failure ordering can only be `SeqCst`, `Acquire` or `Relaxed`
+    /// and must be equivalent to or weaker than the success ordering.
+    ///
+    /// [`compare_exchange`]: Atomic::compare_exchange
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// let guard = &epoch::pin();
+    ///
+    /// let mut new = Owned::new(5678);
+    /// let mut ptr = a.load(SeqCst, guard);
+    /// # unsafe { drop(a.load(SeqCst, guard).into_owned()); } // avoid leak
+    /// loop {
+    ///     match a.compare_exchange_weak(ptr, new, SeqCst, SeqCst, guard) {
+    ///         Ok(p) => {
+    ///             ptr = p;
+    ///             break;
+    ///         }
+    ///         Err(err) => {
+    ///             ptr = err.current;
+    ///             new = err.new;
+    ///         }
+    ///     }
+    /// }
+    ///
+    /// let mut curr = a.load(SeqCst, guard);
+    /// loop {
+    ///     match a.compare_exchange_weak(curr, Shared::null(), SeqCst, SeqCst, guard) {
+    ///         Ok(_) => break,
+    ///         Err(err) => curr = err.current,
+    ///     }
+    /// }
+    /// # unsafe { drop(curr.into_owned()); } // avoid leak
+    /// ```
+    pub fn compare_exchange_weak<'g, P>(
+        &self,
+        current: Shared<'_, T>,
+        new: P,
+        success: Ordering,
+        failure: Ordering,
+        _: &'g Guard,
+    ) -> Result<Shared<'g, T>, CompareExchangeError<'g, T, P>>
+    where
+        P: Pointer<T>,
+    {
+        let new = new.into_usize();
+        self.data
+            .compare_exchange_weak(current.into_usize(), new, success, failure)
+            .map(|_| unsafe { Shared::from_usize(new) })
+            .map_err(|current| unsafe {
+                CompareExchangeError {
+                    current: Shared::from_usize(current),
+                    new: P::from_usize(new),
+                }
+            })
+    }
+
+    /// Fetches the pointer, and then applies a function to it that returns a new value.
+    /// Returns a `Result` of `Ok(previous_value)` if the function returned `Some`, else `Err(_)`.
+    ///
+    /// Note that the given function may be called multiple times if the value has been changed by
+    /// other threads in the meantime, as long as the function returns `Some(_)`, but the function
+    /// will have been applied only once to the stored value.
+    ///
+    /// `fetch_update` takes two [`Ordering`] arguments to describe the memory
+    /// ordering of this operation. The first describes the required ordering for
+    /// when the operation finally succeeds while the second describes the
+    /// required ordering for loads. These correspond to the success and failure
+    /// orderings of [`Atomic::compare_exchange`] respectively.
+    ///
+    /// Using [`Acquire`] as success ordering makes the store part of this
+    /// operation [`Relaxed`], and using [`Release`] makes the final successful
+    /// load [`Relaxed`]. The (failed) load ordering can only be [`SeqCst`],
+    /// [`Acquire`] or [`Relaxed`] and must be equivalent to or weaker than the
+    /// success ordering.
+    ///
+    /// [`Relaxed`]: Ordering::Relaxed
+    /// [`Acquire`]: Ordering::Acquire
+    /// [`Release`]: Ordering::Release
+    /// [`SeqCst`]: Ordering::SeqCst
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// let guard = &epoch::pin();
+    ///
+    /// let res1 = a.fetch_update(SeqCst, SeqCst, guard, |x| Some(x.with_tag(1)));
+    /// assert!(res1.is_ok());
+    ///
+    /// let res2 = a.fetch_update(SeqCst, SeqCst, guard, |x| None);
+    /// assert!(res2.is_err());
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn fetch_update<'g, F>(
+        &self,
+        set_order: Ordering,
+        fail_order: Ordering,
+        guard: &'g Guard,
+        mut func: F,
+    ) -> Result<Shared<'g, T>, Shared<'g, T>>
+    where
+        F: FnMut(Shared<'g, T>) -> Option<Shared<'g, T>>,
+    {
+        let mut prev = self.load(fail_order, guard);
+        while let Some(next) = func(prev) {
+            match self.compare_exchange_weak(prev, next, set_order, fail_order, guard) {
+                Ok(shared) => return Ok(shared),
+                Err(next_prev) => prev = next_prev.current,
+            }
+        }
+        Err(prev)
+    }
+
+    /// Stores the pointer `new` (either `Shared` or `Owned`) into the atomic pointer if the current
+    /// value is the same as `current`. The tag is also taken into account, so two pointers to the
+    /// same object, but with different tags, will not be considered equal.
+    ///
+    /// The return value is a result indicating whether the new pointer was written. On success the
+    /// pointer that was written is returned. On failure the actual current value and `new` are
+    /// returned.
+    ///
+    /// This method takes a [`CompareAndSetOrdering`] argument which describes the memory
+    /// ordering of this operation.
+    ///
+    /// # Migrating to `compare_exchange`
+    ///
+    /// `compare_and_set` is equivalent to `compare_exchange` with the following mapping for
+    /// memory orderings:
+    ///
+    /// Original | Success | Failure
+    /// -------- | ------- | -------
+    /// Relaxed  | Relaxed | Relaxed
+    /// Acquire  | Acquire | Acquire
+    /// Release  | Release | Relaxed
+    /// AcqRel   | AcqRel  | Acquire
+    /// SeqCst   | SeqCst  | SeqCst
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![allow(deprecated)]
+    /// use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    ///
+    /// let guard = &epoch::pin();
+    /// let curr = a.load(SeqCst, guard);
+    /// let res1 = a.compare_and_set(curr, Shared::null(), SeqCst, guard);
+    /// let res2 = a.compare_and_set(curr, Owned::new(5678), SeqCst, guard);
+    /// # unsafe { drop(curr.into_owned()); } // avoid leak
+    /// ```
+    // TODO: remove in the next major version.
+    #[allow(deprecated)]
+    #[deprecated(note = "Use `compare_exchange` instead")]
+    pub fn compare_and_set<'g, O, P>(
+        &self,
+        current: Shared<'_, T>,
+        new: P,
+        ord: O,
+        guard: &'g Guard,
+    ) -> Result<Shared<'g, T>, CompareAndSetError<'g, T, P>>
+    where
+        O: CompareAndSetOrdering,
+        P: Pointer<T>,
+    {
+        self.compare_exchange(current, new, ord.success(), ord.failure(), guard)
+    }
+
+    /// Stores the pointer `new` (either `Shared` or `Owned`) into the atomic pointer if the current
+    /// value is the same as `current`. The tag is also taken into account, so two pointers to the
+    /// same object, but with different tags, will not be considered equal.
+    ///
+    /// Unlike [`compare_and_set`], this method is allowed to spuriously fail even when comparison
+    /// succeeds, which can result in more efficient code on some platforms.  The return value is a
+    /// result indicating whether the new pointer was written. On success the pointer that was
+    /// written is returned. On failure the actual current value and `new` are returned.
+    ///
+    /// This method takes a [`CompareAndSetOrdering`] argument which describes the memory
+    /// ordering of this operation.
+    ///
+    /// [`compare_and_set`]: Atomic::compare_and_set
+    ///
+    /// # Migrating to `compare_exchange_weak`
+    ///
+    /// `compare_and_set_weak` is equivalent to `compare_exchange_weak` with the following mapping for
+    /// memory orderings:
+    ///
+    /// Original | Success | Failure
+    /// -------- | ------- | -------
+    /// Relaxed  | Relaxed | Relaxed
+    /// Acquire  | Acquire | Acquire
+    /// Release  | Release | Relaxed
+    /// AcqRel   | AcqRel  | Acquire
+    /// SeqCst   | SeqCst  | SeqCst
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![allow(deprecated)]
+    /// use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// let guard = &epoch::pin();
+    ///
+    /// let mut new = Owned::new(5678);
+    /// let mut ptr = a.load(SeqCst, guard);
+    /// # unsafe { drop(a.load(SeqCst, guard).into_owned()); } // avoid leak
+    /// loop {
+    ///     match a.compare_and_set_weak(ptr, new, SeqCst, guard) {
+    ///         Ok(p) => {
+    ///             ptr = p;
+    ///             break;
+    ///         }
+    ///         Err(err) => {
+    ///             ptr = err.current;
+    ///             new = err.new;
+    ///         }
+    ///     }
+    /// }
+    ///
+    /// let mut curr = a.load(SeqCst, guard);
+    /// loop {
+    ///     match a.compare_and_set_weak(curr, Shared::null(), SeqCst, guard) {
+    ///         Ok(_) => break,
+    ///         Err(err) => curr = err.current,
+    ///     }
+    /// }
+    /// # unsafe { drop(curr.into_owned()); } // avoid leak
+    /// ```
+    // TODO: remove in the next major version.
+    #[allow(deprecated)]
+    #[deprecated(note = "Use `compare_exchange_weak` instead")]
+    pub fn compare_and_set_weak<'g, O, P>(
+        &self,
+        current: Shared<'_, T>,
+        new: P,
+        ord: O,
+        guard: &'g Guard,
+    ) -> Result<Shared<'g, T>, CompareAndSetError<'g, T, P>>
+    where
+        O: CompareAndSetOrdering,
+        P: Pointer<T>,
+    {
+        self.compare_exchange_weak(current, new, ord.success(), ord.failure(), guard)
+    }
+
+    /// Bitwise "and" with the current tag.
+    ///
+    /// Performs a bitwise "and" operation on the current tag and the argument `val`, and sets the
+    /// new tag to the result. Returns the previous pointer.
+    ///
+    /// This method takes an [`Ordering`] argument which describes the memory ordering of this
+    /// operation.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::<i32>::from(Shared::null().with_tag(3));
+    /// let guard = &epoch::pin();
+    /// assert_eq!(a.fetch_and(2, SeqCst, guard).tag(), 3);
+    /// assert_eq!(a.load(SeqCst, guard).tag(), 2);
+    /// ```
+    pub fn fetch_and<'g>(&self, val: usize, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
+        unsafe { Shared::from_usize(self.data.fetch_and(val | !low_bits::<T>(), ord)) }
+    }
+
+    /// Bitwise "or" with the current tag.
+    ///
+    /// Performs a bitwise "or" operation on the current tag and the argument `val`, and sets the
+    /// new tag to the result. Returns the previous pointer.
+    ///
+    /// This method takes an [`Ordering`] argument which describes the memory ordering of this
+    /// operation.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::<i32>::from(Shared::null().with_tag(1));
+    /// let guard = &epoch::pin();
+    /// assert_eq!(a.fetch_or(2, SeqCst, guard).tag(), 1);
+    /// assert_eq!(a.load(SeqCst, guard).tag(), 3);
+    /// ```
+    pub fn fetch_or<'g>(&self, val: usize, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
+        unsafe { Shared::from_usize(self.data.fetch_or(val & low_bits::<T>(), ord)) }
+    }
+
+    /// Bitwise "xor" with the current tag.
+    ///
+    /// Performs a bitwise "xor" operation on the current tag and the argument `val`, and sets the
+    /// new tag to the result. Returns the previous pointer.
+    ///
+    /// This method takes an [`Ordering`] argument which describes the memory ordering of this
+    /// operation.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Shared};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::<i32>::from(Shared::null().with_tag(1));
+    /// let guard = &epoch::pin();
+    /// assert_eq!(a.fetch_xor(3, SeqCst, guard).tag(), 1);
+    /// assert_eq!(a.load(SeqCst, guard).tag(), 2);
+    /// ```
+    pub fn fetch_xor<'g>(&self, val: usize, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
+        unsafe { Shared::from_usize(self.data.fetch_xor(val & low_bits::<T>(), ord)) }
+    }
+
+    /// Takes ownership of the pointee.
+    ///
+    /// This consumes the atomic and converts it into [`Owned`]. As [`Atomic`] doesn't have a
+    /// destructor and doesn't drop the pointee while [`Owned`] does, this is suitable for
+    /// destructors of data structures.
+    ///
+    /// # Panics
+    ///
+    /// Panics if this pointer is null, but only in debug mode.
+    ///
+    /// # Safety
+    ///
+    /// This method may be called only if the pointer is valid and nobody else is holding a
+    /// reference to the same object.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use std::mem;
+    /// # use crossbeam_epoch::Atomic;
+    /// struct DataStructure {
+    ///     ptr: Atomic<usize>,
+    /// }
+    ///
+    /// impl Drop for DataStructure {
+    ///     fn drop(&mut self) {
+    ///         // By now the DataStructure lives only in our thread and we are sure we don't hold
+    ///         // any Shared or & to it ourselves.
+    ///         unsafe {
+    ///             drop(mem::replace(&mut self.ptr, Atomic::null()).into_owned());
+    ///         }
+    ///     }
+    /// }
+    /// ```
+    pub unsafe fn into_owned(self) -> Owned<T> {
+        Owned::from_usize(self.data.into_inner())
+    }
+
+    /// Takes ownership of the pointee if it is non-null.
+    ///
+    /// This consumes the atomic and converts it into [`Owned`]. As [`Atomic`] doesn't have a
+    /// destructor and doesn't drop the pointee while [`Owned`] does, this is suitable for
+    /// destructors of data structures.
+    ///
+    /// # Safety
+    ///
+    /// This method may be called only if the pointer is valid and nobody else is holding a
+    /// reference to the same object, or the pointer is null.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use std::mem;
+    /// # use crossbeam_epoch::Atomic;
+    /// struct DataStructure {
+    ///     ptr: Atomic<usize>,
+    /// }
+    ///
+    /// impl Drop for DataStructure {
+    ///     fn drop(&mut self) {
+    ///         // By now the DataStructure lives only in our thread and we are sure we don't hold
+    ///         // any Shared or & to it ourselves, but it may be null, so we have to be careful.
+    ///         let old = mem::replace(&mut self.ptr, Atomic::null());
+    ///         unsafe {
+    ///             if let Some(x) = old.try_into_owned() {
+    ///                 drop(x)
+    ///             }
+    ///         }
+    ///     }
+    /// }
+    /// ```
+    pub unsafe fn try_into_owned(self) -> Option<Owned<T>> {
+        let data = self.data.into_inner();
+        if decompose_tag::<T>(data).0 == 0 {
+            None
+        } else {
+            Some(Owned::from_usize(data))
+        }
+    }
+}
+
+impl<T: ?Sized + Pointable> fmt::Debug for Atomic<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let data = self.data.load(Ordering::SeqCst);
+        let (raw, tag) = decompose_tag::<T>(data);
+
+        f.debug_struct("Atomic")
+            .field("raw", &raw)
+            .field("tag", &tag)
+            .finish()
+    }
+}
+
+impl<T: ?Sized + Pointable> fmt::Pointer for Atomic<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let data = self.data.load(Ordering::SeqCst);
+        let (raw, _) = decompose_tag::<T>(data);
+        fmt::Pointer::fmt(&(unsafe { T::deref(raw) as *const _ }), f)
+    }
+}
+
+impl<T: ?Sized + Pointable> Clone for Atomic<T> {
+    /// Returns a copy of the atomic value.
+    ///
+    /// Note that a `Relaxed` load is used here. If you need synchronization, use it with other
+    /// atomics or fences.
+    fn clone(&self) -> Self {
+        let data = self.data.load(Ordering::Relaxed);
+        Atomic::from_usize(data)
+    }
+}
+
+impl<T: ?Sized + Pointable> Default for Atomic<T> {
+    fn default() -> Self {
+        Atomic::null()
+    }
+}
+
+impl<T: ?Sized + Pointable> From<Owned<T>> for Atomic<T> {
+    /// Returns a new atomic pointer pointing to `owned`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{Atomic, Owned};
+    ///
+    /// let a = Atomic::<i32>::from(Owned::new(1234));
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    fn from(owned: Owned<T>) -> Self {
+        let data = owned.data;
+        mem::forget(owned);
+        Self::from_usize(data)
+    }
+}
+
+impl<T> From<Box<T>> for Atomic<T> {
+    fn from(b: Box<T>) -> Self {
+        Self::from(Owned::from(b))
+    }
+}
+
+impl<T> From<T> for Atomic<T> {
+    fn from(t: T) -> Self {
+        Self::new(t)
+    }
+}
+
+impl<'g, T: ?Sized + Pointable> From<Shared<'g, T>> for Atomic<T> {
+    /// Returns a new atomic pointer pointing to `ptr`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{Atomic, Shared};
+    ///
+    /// let a = Atomic::<i32>::from(Shared::<i32>::null());
+    /// ```
+    fn from(ptr: Shared<'g, T>) -> Self {
+        Self::from_usize(ptr.data)
+    }
+}
+
+impl<T> From<*const T> for Atomic<T> {
+    /// Returns a new atomic pointer pointing to `raw`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::ptr;
+    /// use crossbeam_epoch::Atomic;
+    ///
+    /// let a = Atomic::<i32>::from(ptr::null::<i32>());
+    /// ```
+    fn from(raw: *const T) -> Self {
+        Self::from_usize(raw as usize)
+    }
+}
+
+/// A trait for either `Owned` or `Shared` pointers.
+pub trait Pointer<T: ?Sized + Pointable> {
+    /// Returns the machine representation of the pointer.
+    fn into_usize(self) -> usize;
+
+    /// Returns a new pointer pointing to the tagged pointer `data`.
+    ///
+    /// # Safety
+    ///
+    /// The given `data` should have been created by `Pointer::into_usize()`, and one `data` should
+    /// not be converted back by `Pointer::from_usize()` multiple times.
+    unsafe fn from_usize(data: usize) -> Self;
+}
+
+/// An owned heap-allocated object.
+///
+/// This type is very similar to `Box<T>`.
+///
+/// The pointer must be properly aligned. Since it is aligned, a tag can be stored into the unused
+/// least significant bits of the address.
+pub struct Owned<T: ?Sized + Pointable> {
+    data: usize,
+    _marker: PhantomData<Box<T>>,
+}
+
+impl<T: ?Sized + Pointable> Pointer<T> for Owned<T> {
+    #[inline]
+    fn into_usize(self) -> usize {
+        let data = self.data;
+        mem::forget(self);
+        data
+    }
+
+    /// Returns a new pointer pointing to the tagged pointer `data`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the data is zero in debug mode.
+    #[inline]
+    unsafe fn from_usize(data: usize) -> Self {
+        debug_assert!(data != 0, "converting zero into `Owned`");
+        Owned {
+            data,
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<T> Owned<T> {
+    /// Returns a new owned pointer pointing to `raw`.
+    ///
+    /// This function is unsafe because improper use may lead to memory problems. Argument `raw`
+    /// must be a valid pointer. Also, a double-free may occur if the function is called twice on
+    /// the same raw pointer.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `raw` is not properly aligned.
+    ///
+    /// # Safety
+    ///
+    /// The given `raw` should have been derived from `Owned`, and one `raw` should not be converted
+    /// back by `Owned::from_raw()` multiple times.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Owned;
+    ///
+    /// let o = unsafe { Owned::from_raw(Box::into_raw(Box::new(1234))) };
+    /// ```
+    pub unsafe fn from_raw(raw: *mut T) -> Owned<T> {
+        let raw = raw as usize;
+        ensure_aligned::<T>(raw);
+        Self::from_usize(raw)
+    }
+
+    /// Converts the owned pointer into a `Box`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Owned;
+    ///
+    /// let o = Owned::new(1234);
+    /// let b: Box<i32> = o.into_box();
+    /// assert_eq!(*b, 1234);
+    /// ```
+    pub fn into_box(self) -> Box<T> {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        mem::forget(self);
+        unsafe { Box::from_raw(raw as *mut _) }
+    }
+
+    /// Allocates `value` on the heap and returns a new owned pointer pointing to it.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Owned;
+    ///
+    /// let o = Owned::new(1234);
+    /// ```
+    pub fn new(init: T) -> Owned<T> {
+        Self::init(init)
+    }
+}
+
+impl<T: ?Sized + Pointable> Owned<T> {
+    /// Allocates `value` on the heap and returns a new owned pointer pointing to it.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Owned;
+    ///
+    /// let o = Owned::<i32>::init(1234);
+    /// ```
+    pub fn init(init: T::Init) -> Owned<T> {
+        unsafe { Self::from_usize(T::init(init)) }
+    }
+
+    /// Converts the owned pointer into a [`Shared`].
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Owned};
+    ///
+    /// let o = Owned::new(1234);
+    /// let guard = &epoch::pin();
+    /// let p = o.into_shared(guard);
+    /// # unsafe { drop(p.into_owned()); } // avoid leak
+    /// ```
+    #[allow(clippy::needless_lifetimes)]
+    pub fn into_shared<'g>(self, _: &'g Guard) -> Shared<'g, T> {
+        unsafe { Shared::from_usize(self.into_usize()) }
+    }
+
+    /// Returns the tag stored within the pointer.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Owned;
+    ///
+    /// assert_eq!(Owned::new(1234).tag(), 0);
+    /// ```
+    pub fn tag(&self) -> usize {
+        let (_, tag) = decompose_tag::<T>(self.data);
+        tag
+    }
+
+    /// Returns the same pointer, but tagged with `tag`. `tag` is truncated to be fit into the
+    /// unused bits of the pointer to `T`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Owned;
+    ///
+    /// let o = Owned::new(0u64);
+    /// assert_eq!(o.tag(), 0);
+    /// let o = o.with_tag(2);
+    /// assert_eq!(o.tag(), 2);
+    /// ```
+    pub fn with_tag(self, tag: usize) -> Owned<T> {
+        let data = self.into_usize();
+        unsafe { Self::from_usize(compose_tag::<T>(data, tag)) }
+    }
+}
+
+impl<T: ?Sized + Pointable> Drop for Owned<T> {
+    fn drop(&mut self) {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        unsafe {
+            T::drop(raw);
+        }
+    }
+}
+
+impl<T: ?Sized + Pointable> fmt::Debug for Owned<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let (raw, tag) = decompose_tag::<T>(self.data);
+
+        f.debug_struct("Owned")
+            .field("raw", &raw)
+            .field("tag", &tag)
+            .finish()
+    }
+}
+
+impl<T: Clone> Clone for Owned<T> {
+    fn clone(&self) -> Self {
+        Owned::new((**self).clone()).with_tag(self.tag())
+    }
+}
+
+impl<T: ?Sized + Pointable> Deref for Owned<T> {
+    type Target = T;
+
+    fn deref(&self) -> &T {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        unsafe { T::deref(raw) }
+    }
+}
+
+impl<T: ?Sized + Pointable> DerefMut for Owned<T> {
+    fn deref_mut(&mut self) -> &mut T {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        unsafe { T::deref_mut(raw) }
+    }
+}
+
+impl<T> From<T> for Owned<T> {
+    fn from(t: T) -> Self {
+        Owned::new(t)
+    }
+}
+
+impl<T> From<Box<T>> for Owned<T> {
+    /// Returns a new owned pointer pointing to `b`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the pointer (the `Box`) is not properly aligned.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Owned;
+    ///
+    /// let o = unsafe { Owned::from_raw(Box::into_raw(Box::new(1234))) };
+    /// ```
+    fn from(b: Box<T>) -> Self {
+        unsafe { Self::from_raw(Box::into_raw(b)) }
+    }
+}
+
+impl<T: ?Sized + Pointable> Borrow<T> for Owned<T> {
+    fn borrow(&self) -> &T {
+        self.deref()
+    }
+}
+
+impl<T: ?Sized + Pointable> BorrowMut<T> for Owned<T> {
+    fn borrow_mut(&mut self) -> &mut T {
+        self.deref_mut()
+    }
+}
+
+impl<T: ?Sized + Pointable> AsRef<T> for Owned<T> {
+    fn as_ref(&self) -> &T {
+        self.deref()
+    }
+}
+
+impl<T: ?Sized + Pointable> AsMut<T> for Owned<T> {
+    fn as_mut(&mut self) -> &mut T {
+        self.deref_mut()
+    }
+}
+
+/// A pointer to an object protected by the epoch GC.
+///
+/// The pointer is valid for use only during the lifetime `'g`.
+///
+/// The pointer must be properly aligned. Since it is aligned, a tag can be stored into the unused
+/// least significant bits of the address.
+pub struct Shared<'g, T: 'g + ?Sized + Pointable> {
+    data: usize,
+    _marker: PhantomData<(&'g (), *const T)>,
+}
+
+impl<T: ?Sized + Pointable> Clone for Shared<'_, T> {
+    fn clone(&self) -> Self {
+        *self
+    }
+}
+
+impl<T: ?Sized + Pointable> Copy for Shared<'_, T> {}
+
+impl<T: ?Sized + Pointable> Pointer<T> for Shared<'_, T> {
+    #[inline]
+    fn into_usize(self) -> usize {
+        self.data
+    }
+
+    #[inline]
+    unsafe fn from_usize(data: usize) -> Self {
+        Shared {
+            data,
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<'g, T> Shared<'g, T> {
+    /// Converts the pointer to a raw pointer (without the tag).
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Owned};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let o = Owned::new(1234);
+    /// let raw = &*o as *const _;
+    /// let a = Atomic::from(o);
+    ///
+    /// let guard = &epoch::pin();
+    /// let p = a.load(SeqCst, guard);
+    /// assert_eq!(p.as_raw(), raw);
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn as_raw(&self) -> *const T {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        raw as *const _
+    }
+}
+
+impl<'g, T: ?Sized + Pointable> Shared<'g, T> {
+    /// Returns a new null pointer.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Shared;
+    ///
+    /// let p = Shared::<i32>::null();
+    /// assert!(p.is_null());
+    /// ```
+    pub fn null() -> Shared<'g, T> {
+        Shared {
+            data: 0,
+            _marker: PhantomData,
+        }
+    }
+
+    /// Returns `true` if the pointer is null.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Owned};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::null();
+    /// let guard = &epoch::pin();
+    /// assert!(a.load(SeqCst, guard).is_null());
+    /// a.store(Owned::new(1234), SeqCst);
+    /// assert!(!a.load(SeqCst, guard).is_null());
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn is_null(&self) -> bool {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        raw == 0
+    }
+
+    /// Dereferences the pointer.
+    ///
+    /// Returns a reference to the pointee that is valid during the lifetime `'g`.
+    ///
+    /// # Safety
+    ///
+    /// Dereferencing a pointer is unsafe because it could be pointing to invalid memory.
+    ///
+    /// Another concern is the possibility of data races due to lack of proper synchronization.
+    /// For example, consider the following scenario:
+    ///
+    /// 1. A thread creates a new object: `a.store(Owned::new(10), Relaxed)`
+    /// 2. Another thread reads it: `*a.load(Relaxed, guard).as_ref().unwrap()`
+    ///
+    /// The problem is that relaxed orderings don't synchronize initialization of the object with
+    /// the read from the second thread. This is a data race. A possible solution would be to use
+    /// `Release` and `Acquire` orderings.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// let guard = &epoch::pin();
+    /// let p = a.load(SeqCst, guard);
+    /// unsafe {
+    ///     assert_eq!(p.deref(), &1234);
+    /// }
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub unsafe fn deref(&self) -> &'g T {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        T::deref(raw)
+    }
+
+    /// Dereferences the pointer.
+    ///
+    /// Returns a mutable reference to the pointee that is valid during the lifetime `'g`.
+    ///
+    /// # Safety
+    ///
+    /// * There is no guarantee that there are no more threads attempting to read/write from/to the
+    ///   actual object at the same time.
+    ///
+    ///   The user must know that there are no concurrent accesses towards the object itself.
+    ///
+    /// * Other than the above, all safety concerns of `deref()` applies here.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(vec![1, 2, 3, 4]);
+    /// let guard = &epoch::pin();
+    ///
+    /// let mut p = a.load(SeqCst, guard);
+    /// unsafe {
+    ///     assert!(!p.is_null());
+    ///     let b = p.deref_mut();
+    ///     assert_eq!(b, &vec![1, 2, 3, 4]);
+    ///     b.push(5);
+    ///     assert_eq!(b, &vec![1, 2, 3, 4, 5]);
+    /// }
+    ///
+    /// let p = a.load(SeqCst, guard);
+    /// unsafe {
+    ///     assert_eq!(p.deref(), &vec![1, 2, 3, 4, 5]);
+    /// }
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub unsafe fn deref_mut(&mut self) -> &'g mut T {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        T::deref_mut(raw)
+    }
+
+    /// Converts the pointer to a reference.
+    ///
+    /// Returns `None` if the pointer is null, or else a reference to the object wrapped in `Some`.
+    ///
+    /// # Safety
+    ///
+    /// Dereferencing a pointer is unsafe because it could be pointing to invalid memory.
+    ///
+    /// Another concern is the possibility of data races due to lack of proper synchronization.
+    /// For example, consider the following scenario:
+    ///
+    /// 1. A thread creates a new object: `a.store(Owned::new(10), Relaxed)`
+    /// 2. Another thread reads it: `*a.load(Relaxed, guard).as_ref().unwrap()`
+    ///
+    /// The problem is that relaxed orderings don't synchronize initialization of the object with
+    /// the read from the second thread. This is a data race. A possible solution would be to use
+    /// `Release` and `Acquire` orderings.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// let guard = &epoch::pin();
+    /// let p = a.load(SeqCst, guard);
+    /// unsafe {
+    ///     assert_eq!(p.as_ref(), Some(&1234));
+    /// }
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub unsafe fn as_ref(&self) -> Option<&'g T> {
+        let (raw, _) = decompose_tag::<T>(self.data);
+        if raw == 0 {
+            None
+        } else {
+            Some(T::deref(raw))
+        }
+    }
+
+    /// Takes ownership of the pointee.
+    ///
+    /// # Panics
+    ///
+    /// Panics if this pointer is null, but only in debug mode.
+    ///
+    /// # Safety
+    ///
+    /// This method may be called only if the pointer is valid and nobody else is holding a
+    /// reference to the same object.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// unsafe {
+    ///     let guard = &epoch::unprotected();
+    ///     let p = a.load(SeqCst, guard);
+    ///     drop(p.into_owned());
+    /// }
+    /// ```
+    pub unsafe fn into_owned(self) -> Owned<T> {
+        debug_assert!(!self.is_null(), "converting a null `Shared` into `Owned`");
+        Owned::from_usize(self.data)
+    }
+
+    /// Takes ownership of the pointee if it is not null.
+    ///
+    /// # Safety
+    ///
+    /// This method may be called only if the pointer is valid and nobody else is holding a
+    /// reference to the same object, or if the pointer is null.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(1234);
+    /// unsafe {
+    ///     let guard = &epoch::unprotected();
+    ///     let p = a.load(SeqCst, guard);
+    ///     if let Some(x) = p.try_into_owned() {
+    ///         drop(x);
+    ///     }
+    /// }
+    /// ```
+    pub unsafe fn try_into_owned(self) -> Option<Owned<T>> {
+        if self.is_null() {
+            None
+        } else {
+            Some(Owned::from_usize(self.data))
+        }
+    }
+
+    /// Returns the tag stored within the pointer.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic, Owned};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::<u64>::from(Owned::new(0u64).with_tag(2));
+    /// let guard = &epoch::pin();
+    /// let p = a.load(SeqCst, guard);
+    /// assert_eq!(p.tag(), 2);
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn tag(&self) -> usize {
+        let (_, tag) = decompose_tag::<T>(self.data);
+        tag
+    }
+
+    /// Returns the same pointer, but tagged with `tag`. `tag` is truncated to be fit into the
+    /// unused bits of the pointer to `T`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::{self as epoch, Atomic};
+    /// use std::sync::atomic::Ordering::SeqCst;
+    ///
+    /// let a = Atomic::new(0u64);
+    /// let guard = &epoch::pin();
+    /// let p1 = a.load(SeqCst, guard);
+    /// let p2 = p1.with_tag(2);
+    ///
+    /// assert_eq!(p1.tag(), 0);
+    /// assert_eq!(p2.tag(), 2);
+    /// assert_eq!(p1.as_raw(), p2.as_raw());
+    /// # unsafe { drop(a.into_owned()); } // avoid leak
+    /// ```
+    pub fn with_tag(&self, tag: usize) -> Shared<'g, T> {
+        unsafe { Self::from_usize(compose_tag::<T>(self.data, tag)) }
+    }
+}
+
+impl<T> From<*const T> for Shared<'_, T> {
+    /// Returns a new pointer pointing to `raw`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `raw` is not properly aligned.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use crossbeam_epoch::Shared;
+    ///
+    /// let p = Shared::from(Box::into_raw(Box::new(1234)) as *const _);
+    /// assert!(!p.is_null());
+    /// # unsafe { drop(p.into_owned()); } // avoid leak
+    /// ```
+    fn from(raw: *const T) -> Self {
+        let raw = raw as usize;
+        ensure_aligned::<T>(raw);
+        unsafe { Self::from_usize(raw) }
+    }
+}
+
+impl<'g, T: ?Sized + Pointable> PartialEq<Shared<'g, T>> for Shared<'g, T> {
+    fn eq(&self, other: &Self) -> bool {
+        self.data == other.data
+    }
+}
+
+impl<T: ?Sized + Pointable> Eq for Shared<'_, T> {}
+
+impl<'g, T: ?Sized + Pointable> PartialOrd<Shared<'g, T>> for Shared<'g, T> {
+    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
+        self.data.partial_cmp(&other.data)
+    }
+}
+
+impl<T: ?Sized + Pointable> Ord for Shared<'_, T> {
+    fn cmp(&self, other: &Self) -> cmp::Ordering {
+        self.data.cmp(&other.data)
+    }
+}
+
+impl<T: ?Sized + Pointable> fmt::Debug for Shared<'_, T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let (raw, tag) = decompose_tag::<T>(self.data);
+
+        f.debug_struct("Shared")
+            .field("raw", &raw)
+            .field("tag", &tag)
+            .finish()
+    }
+}
+
+impl<T: ?Sized + Pointable> fmt::Pointer for Shared<'_, T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Pointer::fmt(&(unsafe { self.deref() as *const _ }), f)
+    }
+}
+
+impl<T: ?Sized + Pointable> Default for Shared<'_, T> {
+    fn default() -> Self {
+        Shared::null()
+    }
+}
+
+#[cfg(all(test, not(crossbeam_loom)))]
+mod tests {
+    use super::{Owned, Shared};
+    use std::mem::MaybeUninit;
+
+    #[test]
+    fn valid_tag_i8() {
+        Shared::<i8>::null().with_tag(0);
+    }
+
+    #[test]
+    fn valid_tag_i64() {
+        Shared::<i64>::null().with_tag(7);
+    }
+
+    #[test]
+    fn const_atomic_null() {
+        use super::Atomic;
+        static _U: Atomic<u8> = Atomic::<u8>::null();
+    }
+
+    #[test]
+    fn array_init() {
+        let owned = Owned::<[MaybeUninit<usize>]>::init(10);
+        let arr: &[MaybeUninit<usize>] = &owned;
+        assert_eq!(arr.len(), 10);
+    }
+}