1use alloc::boxed::Box;
2use core::alloc::Layout;
3use core::borrow::{Borrow, BorrowMut};
4use core::cmp;
5use core::fmt;
6use core::marker::PhantomData;
7use core::mem::{self, MaybeUninit};
8use core::ops::{Deref, DerefMut};
9use core::ptr;
10use core::slice;
11
12use crate::guard::Guard;
13use crate::primitive::sync::atomic::{AtomicUsize, Ordering};
14use crossbeam_utils::atomic::AtomicConsume;
15
16/// Given ordering for the success case in a compare-exchange operation, returns the strongest
17/// appropriate ordering for the failure case.
18#[inline]
19fn strongest_failure_ordering(ord: Ordering) -> Ordering {
20 use self::Ordering::*;
21 match ord {
22 Relaxed | Release => Relaxed,
23 Acquire | AcqRel => Acquire,
24 _ => SeqCst,
25 }
26}
27
28/// The error returned on failed compare-and-set operation.
29// TODO: remove in the next major version.
30#[deprecated(note = "Use `CompareExchangeError` instead")]
31pub type CompareAndSetError<'g, T, P> = CompareExchangeError<'g, T, P>;
32
33/// The error returned on failed compare-and-swap operation.
34pub struct CompareExchangeError<'g, T: ?Sized + Pointable, P: Pointer<T>> {
35 /// The value in the atomic pointer at the time of the failed operation.
36 pub current: Shared<'g, T>,
37
38 /// The new value, which the operation failed to store.
39 pub new: P,
40}
41
42impl<T, P: Pointer<T> + fmt::Debug> fmt::Debug for CompareExchangeError<'_, T, P> {
43 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44 f&mut DebugStruct<'_, '_>.debug_struct("CompareExchangeError")
45 .field("current", &self.current)
46 .field(name:"new", &self.new)
47 .finish()
48 }
49}
50
51/// Memory orderings for compare-and-set operations.
52///
53/// A compare-and-set operation can have different memory orderings depending on whether it
54/// succeeds or fails. This trait generalizes different ways of specifying memory orderings.
55///
56/// The two ways of specifying orderings for compare-and-set are:
57///
58/// 1. Just one `Ordering` for the success case. In case of failure, the strongest appropriate
59/// ordering is chosen.
60/// 2. A pair of `Ordering`s. The first one is for the success case, while the second one is
61/// for the failure case.
62// TODO: remove in the next major version.
63#[deprecated(
64 note = "`compare_and_set` and `compare_and_set_weak` that use this trait are deprecated, \
65 use `compare_exchange` or `compare_exchange_weak instead`"
66)]
67pub trait CompareAndSetOrdering {
68 /// The ordering of the operation when it succeeds.
69 fn success(&self) -> Ordering;
70
71 /// The ordering of the operation when it fails.
72 ///
73 /// The failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than
74 /// the success ordering.
75 fn failure(&self) -> Ordering;
76}
77
78#[allow(deprecated)]
79impl CompareAndSetOrdering for Ordering {
80 #[inline]
81 fn success(&self) -> Ordering {
82 *self
83 }
84
85 #[inline]
86 fn failure(&self) -> Ordering {
87 strongest_failure_ordering(*self)
88 }
89}
90
91#[allow(deprecated)]
92impl CompareAndSetOrdering for (Ordering, Ordering) {
93 #[inline]
94 fn success(&self) -> Ordering {
95 self.0
96 }
97
98 #[inline]
99 fn failure(&self) -> Ordering {
100 self.1
101 }
102}
103
104/// Returns a bitmask containing the unused least significant bits of an aligned pointer to `T`.
105#[inline]
106fn low_bits<T: ?Sized + Pointable>() -> usize {
107 (1 << T::ALIGN.trailing_zeros()) - 1
108}
109
110/// Panics if the pointer is not properly unaligned.
111#[inline]
112fn ensure_aligned<T: ?Sized + Pointable>(raw: usize) {
113 assert_eq!(raw & low_bits::<T>(), 0, "unaligned pointer");
114}
115
116/// Given a tagged pointer `data`, returns the same pointer, but tagged with `tag`.
117///
118/// `tag` is truncated to fit into the unused bits of the pointer to `T`.
119#[inline]
120fn compose_tag<T: ?Sized + Pointable>(data: usize, tag: usize) -> usize {
121 (data & !low_bits::<T>()) | (tag & low_bits::<T>())
122}
123
124/// Decomposes a tagged pointer `data` into the pointer and the tag.
125#[inline]
126fn decompose_tag<T: ?Sized + Pointable>(data: usize) -> (usize, usize) {
127 (data & !low_bits::<T>(), data & low_bits::<T>())
128}
129
130/// Types that are pointed to by a single word.
131///
132/// In concurrent programming, it is necessary to represent an object within a word because atomic
133/// operations (e.g., reads, writes, read-modify-writes) support only single words. This trait
134/// qualifies such types that are pointed to by a single word.
135///
136/// The trait generalizes `Box<T>` for a sized type `T`. In a box, an object of type `T` is
137/// allocated in heap and it is owned by a single-word pointer. This trait is also implemented for
138/// `[MaybeUninit<T>]` by storing its size along with its elements and pointing to the pair of array
139/// size and elements.
140///
141/// Pointers to `Pointable` types can be stored in [`Atomic`], [`Owned`], and [`Shared`]. In
142/// particular, Crossbeam supports dynamically sized slices as follows.
143///
144/// ```
145/// use std::mem::MaybeUninit;
146/// use crossbeam_epoch::Owned;
147///
148/// let o = Owned::<[MaybeUninit<i32>]>::init(10); // allocating [i32; 10]
149/// ```
150pub trait Pointable {
151 /// The alignment of pointer.
152 const ALIGN: usize;
153
154 /// The type for initializers.
155 type Init;
156
157 /// Initializes a with the given initializer.
158 ///
159 /// # Safety
160 ///
161 /// The result should be a multiple of `ALIGN`.
162 unsafe fn init(init: Self::Init) -> usize;
163
164 /// Dereferences the given pointer.
165 ///
166 /// # Safety
167 ///
168 /// - The given `ptr` should have been initialized with [`Pointable::init`].
169 /// - `ptr` should not have yet been dropped by [`Pointable::drop`].
170 /// - `ptr` should not be mutably dereferenced by [`Pointable::deref_mut`] concurrently.
171 unsafe fn deref<'a>(ptr: usize) -> &'a Self;
172
173 /// Mutably dereferences the given pointer.
174 ///
175 /// # Safety
176 ///
177 /// - The given `ptr` should have been initialized with [`Pointable::init`].
178 /// - `ptr` should not have yet been dropped by [`Pointable::drop`].
179 /// - `ptr` should not be dereferenced by [`Pointable::deref`] or [`Pointable::deref_mut`]
180 /// concurrently.
181 unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut Self;
182
183 /// Drops the object pointed to by the given pointer.
184 ///
185 /// # Safety
186 ///
187 /// - The given `ptr` should have been initialized with [`Pointable::init`].
188 /// - `ptr` should not have yet been dropped by [`Pointable::drop`].
189 /// - `ptr` should not be dereferenced by [`Pointable::deref`] or [`Pointable::deref_mut`]
190 /// concurrently.
191 unsafe fn drop(ptr: usize);
192}
193
194impl<T> Pointable for T {
195 const ALIGN: usize = mem::align_of::<T>();
196
197 type Init = T;
198
199 unsafe fn init(init: Self::Init) -> usize {
200 Box::into_raw(Box::new(init)) as usize
201 }
202
203 unsafe fn deref<'a>(ptr: usize) -> &'a Self {
204 &*(ptr as *const T)
205 }
206
207 unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut Self {
208 &mut *(ptr as *mut T)
209 }
210
211 unsafe fn drop(ptr: usize) {
212 drop(Box::from_raw(ptr as *mut T));
213 }
214}
215
216/// Array with size.
217///
218/// # Memory layout
219///
220/// An array consisting of size and elements:
221///
222/// ```text
223/// elements
224/// |
225/// |
226/// ------------------------------------
227/// | size | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
228/// ------------------------------------
229/// ```
230///
231/// Its memory layout is different from that of `Box<[T]>` in that size is in the allocation (not
232/// along with pointer as in `Box<[T]>`).
233///
234/// Elements are not present in the type, but they will be in the allocation.
235/// ```
236#[repr(C)]
237struct Array<T> {
238 /// The number of elements (not the number of bytes).
239 len: usize,
240 elements: [MaybeUninit<T>; 0],
241}
242
243impl<T> Array<T> {
244 fn layout(len: usize) -> Layout {
245 LayoutLayout::new::<Self>()
246 .extend(next:Layout::array::<MaybeUninit<T>>(len).unwrap())
247 .unwrap()
248 .0
249 .pad_to_align()
250 }
251}
252
253impl<T> Pointable for [MaybeUninit<T>] {
254 const ALIGN: usize = mem::align_of::<Array<T>>();
255
256 type Init = usize;
257
258 unsafe fn init(len: Self::Init) -> usize {
259 let layout = Array::<T>::layout(len);
260 let ptr = alloc::alloc::alloc(layout).cast::<Array<T>>();
261 if ptr.is_null() {
262 alloc::alloc::handle_alloc_error(layout);
263 }
264 ptr::addr_of_mut!((*ptr).len).write(len);
265 ptr as usize
266 }
267
268 unsafe fn deref<'a>(ptr: usize) -> &'a Self {
269 let array = &*(ptr as *const Array<T>);
270 slice::from_raw_parts(array.elements.as_ptr() as *const _, array.len)
271 }
272
273 unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut Self {
274 let array = &*(ptr as *mut Array<T>);
275 slice::from_raw_parts_mut(array.elements.as_ptr() as *mut _, array.len)
276 }
277
278 unsafe fn drop(ptr: usize) {
279 let len = (*(ptr as *mut Array<T>)).len;
280 let layout = Array::<T>::layout(len);
281 alloc::alloc::dealloc(ptr as *mut u8, layout);
282 }
283}
284
285/// An atomic pointer that can be safely shared between threads.
286///
287/// The pointer must be properly aligned. Since it is aligned, a tag can be stored into the unused
288/// least significant bits of the address. For example, the tag for a pointer to a sized type `T`
289/// should be less than `(1 << mem::align_of::<T>().trailing_zeros())`.
290///
291/// Any method that loads the pointer must be passed a reference to a [`Guard`].
292///
293/// Crossbeam supports dynamically sized types. See [`Pointable`] for details.
294pub struct Atomic<T: ?Sized + Pointable> {
295 data: AtomicUsize,
296 _marker: PhantomData<*mut T>,
297}
298
299unsafe impl<T: ?Sized + Pointable + Send + Sync> Send for Atomic<T> {}
300unsafe impl<T: ?Sized + Pointable + Send + Sync> Sync for Atomic<T> {}
301
302impl<T> Atomic<T> {
303 /// Allocates `value` on the heap and returns a new atomic pointer pointing to it.
304 ///
305 /// # Examples
306 ///
307 /// ```
308 /// use crossbeam_epoch::Atomic;
309 ///
310 /// let a = Atomic::new(1234);
311 /// # unsafe { drop(a.into_owned()); } // avoid leak
312 /// ```
313 pub fn new(init: T) -> Atomic<T> {
314 Self::init(init)
315 }
316}
317
318impl<T: ?Sized + Pointable> Atomic<T> {
319 /// Allocates `value` on the heap and returns a new atomic pointer pointing to it.
320 ///
321 /// # Examples
322 ///
323 /// ```
324 /// use crossbeam_epoch::Atomic;
325 ///
326 /// let a = Atomic::<i32>::init(1234);
327 /// # unsafe { drop(a.into_owned()); } // avoid leak
328 /// ```
329 pub fn init(init: T::Init) -> Atomic<T> {
330 Self::from(Owned::init(init))
331 }
332
333 /// Returns a new atomic pointer pointing to the tagged pointer `data`.
334 fn from_usize(data: usize) -> Self {
335 Self {
336 data: AtomicUsize::new(data),
337 _marker: PhantomData,
338 }
339 }
340
341 /// Returns a new null atomic pointer.
342 ///
343 /// # Examples
344 ///
345 /// ```
346 /// use crossbeam_epoch::Atomic;
347 ///
348 /// let a = Atomic::<i32>::null();
349 /// ```
350 #[cfg(not(crossbeam_loom))]
351 pub const fn null() -> Atomic<T> {
352 Self {
353 data: AtomicUsize::new(0),
354 _marker: PhantomData,
355 }
356 }
357 /// Returns a new null atomic pointer.
358 #[cfg(crossbeam_loom)]
359 pub fn null() -> Atomic<T> {
360 Self {
361 data: AtomicUsize::new(0),
362 _marker: PhantomData,
363 }
364 }
365
366 /// Loads a `Shared` from the atomic pointer.
367 ///
368 /// This method takes an [`Ordering`] argument which describes the memory ordering of this
369 /// operation.
370 ///
371 /// # Examples
372 ///
373 /// ```
374 /// use crossbeam_epoch::{self as epoch, Atomic};
375 /// use std::sync::atomic::Ordering::SeqCst;
376 ///
377 /// let a = Atomic::new(1234);
378 /// let guard = &epoch::pin();
379 /// let p = a.load(SeqCst, guard);
380 /// # unsafe { drop(a.into_owned()); } // avoid leak
381 /// ```
382 pub fn load<'g>(&self, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
383 unsafe { Shared::from_usize(self.data.load(ord)) }
384 }
385
386 /// Loads a `Shared` from the atomic pointer using a "consume" memory ordering.
387 ///
388 /// This is similar to the "acquire" ordering, except that an ordering is
389 /// only guaranteed with operations that "depend on" the result of the load.
390 /// However consume loads are usually much faster than acquire loads on
391 /// architectures with a weak memory model since they don't require memory
392 /// fence instructions.
393 ///
394 /// The exact definition of "depend on" is a bit vague, but it works as you
395 /// would expect in practice since a lot of software, especially the Linux
396 /// kernel, rely on this behavior.
397 ///
398 /// # Examples
399 ///
400 /// ```
401 /// use crossbeam_epoch::{self as epoch, Atomic};
402 ///
403 /// let a = Atomic::new(1234);
404 /// let guard = &epoch::pin();
405 /// let p = a.load_consume(guard);
406 /// # unsafe { drop(a.into_owned()); } // avoid leak
407 /// ```
408 pub fn load_consume<'g>(&self, _: &'g Guard) -> Shared<'g, T> {
409 unsafe { Shared::from_usize(self.data.load_consume()) }
410 }
411
412 /// Stores a `Shared` or `Owned` pointer into the atomic pointer.
413 ///
414 /// This method takes an [`Ordering`] argument which describes the memory ordering of this
415 /// operation.
416 ///
417 /// # Examples
418 ///
419 /// ```
420 /// use crossbeam_epoch::{Atomic, Owned, Shared};
421 /// use std::sync::atomic::Ordering::SeqCst;
422 ///
423 /// let a = Atomic::new(1234);
424 /// # unsafe { drop(a.load(SeqCst, &crossbeam_epoch::pin()).into_owned()); } // avoid leak
425 /// a.store(Shared::null(), SeqCst);
426 /// a.store(Owned::new(1234), SeqCst);
427 /// # unsafe { drop(a.into_owned()); } // avoid leak
428 /// ```
429 pub fn store<P: Pointer<T>>(&self, new: P, ord: Ordering) {
430 self.data.store(new.into_usize(), ord);
431 }
432
433 /// Stores a `Shared` or `Owned` pointer into the atomic pointer, returning the previous
434 /// `Shared`.
435 ///
436 /// This method takes an [`Ordering`] argument which describes the memory ordering of this
437 /// operation.
438 ///
439 /// # Examples
440 ///
441 /// ```
442 /// use crossbeam_epoch::{self as epoch, Atomic, Shared};
443 /// use std::sync::atomic::Ordering::SeqCst;
444 ///
445 /// let a = Atomic::new(1234);
446 /// let guard = &epoch::pin();
447 /// let p = a.swap(Shared::null(), SeqCst, guard);
448 /// # unsafe { drop(p.into_owned()); } // avoid leak
449 /// ```
450 pub fn swap<'g, P: Pointer<T>>(&self, new: P, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
451 unsafe { Shared::from_usize(self.data.swap(new.into_usize(), ord)) }
452 }
453
454 /// Stores the pointer `new` (either `Shared` or `Owned`) into the atomic pointer if the current
455 /// value is the same as `current`. The tag is also taken into account, so two pointers to the
456 /// same object, but with different tags, will not be considered equal.
457 ///
458 /// The return value is a result indicating whether the new pointer was written. On success the
459 /// pointer that was written is returned. On failure the actual current value and `new` are
460 /// returned.
461 ///
462 /// This method takes two `Ordering` arguments to describe the memory
463 /// ordering of this operation. `success` describes the required ordering for the
464 /// read-modify-write operation that takes place if the comparison with `current` succeeds.
465 /// `failure` describes the required ordering for the load operation that takes place when
466 /// the comparison fails. Using `Acquire` as success ordering makes the store part
467 /// of this operation `Relaxed`, and using `Release` makes the successful load
468 /// `Relaxed`. The failure ordering can only be `SeqCst`, `Acquire` or `Relaxed`
469 /// and must be equivalent to or weaker than the success ordering.
470 ///
471 /// # Examples
472 ///
473 /// ```
474 /// use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
475 /// use std::sync::atomic::Ordering::SeqCst;
476 ///
477 /// let a = Atomic::new(1234);
478 ///
479 /// let guard = &epoch::pin();
480 /// let curr = a.load(SeqCst, guard);
481 /// let res1 = a.compare_exchange(curr, Shared::null(), SeqCst, SeqCst, guard);
482 /// let res2 = a.compare_exchange(curr, Owned::new(5678), SeqCst, SeqCst, guard);
483 /// # unsafe { drop(curr.into_owned()); } // avoid leak
484 /// ```
485 pub fn compare_exchange<'g, P>(
486 &self,
487 current: Shared<'_, T>,
488 new: P,
489 success: Ordering,
490 failure: Ordering,
491 _: &'g Guard,
492 ) -> Result<Shared<'g, T>, CompareExchangeError<'g, T, P>>
493 where
494 P: Pointer<T>,
495 {
496 let new = new.into_usize();
497 self.data
498 .compare_exchange(current.into_usize(), new, success, failure)
499 .map(|_| unsafe { Shared::from_usize(new) })
500 .map_err(|current| unsafe {
501 CompareExchangeError {
502 current: Shared::from_usize(current),
503 new: P::from_usize(new),
504 }
505 })
506 }
507
508 /// Stores the pointer `new` (either `Shared` or `Owned`) into the atomic pointer if the current
509 /// value is the same as `current`. The tag is also taken into account, so two pointers to the
510 /// same object, but with different tags, will not be considered equal.
511 ///
512 /// Unlike [`compare_exchange`], this method is allowed to spuriously fail even when comparison
513 /// succeeds, which can result in more efficient code on some platforms. The return value is a
514 /// result indicating whether the new pointer was written. On success the pointer that was
515 /// written is returned. On failure the actual current value and `new` are returned.
516 ///
517 /// This method takes two `Ordering` arguments to describe the memory
518 /// ordering of this operation. `success` describes the required ordering for the
519 /// read-modify-write operation that takes place if the comparison with `current` succeeds.
520 /// `failure` describes the required ordering for the load operation that takes place when
521 /// the comparison fails. Using `Acquire` as success ordering makes the store part
522 /// of this operation `Relaxed`, and using `Release` makes the successful load
523 /// `Relaxed`. The failure ordering can only be `SeqCst`, `Acquire` or `Relaxed`
524 /// and must be equivalent to or weaker than the success ordering.
525 ///
526 /// [`compare_exchange`]: Atomic::compare_exchange
527 ///
528 /// # Examples
529 ///
530 /// ```
531 /// use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
532 /// use std::sync::atomic::Ordering::SeqCst;
533 ///
534 /// let a = Atomic::new(1234);
535 /// let guard = &epoch::pin();
536 ///
537 /// let mut new = Owned::new(5678);
538 /// let mut ptr = a.load(SeqCst, guard);
539 /// # unsafe { drop(a.load(SeqCst, guard).into_owned()); } // avoid leak
540 /// loop {
541 /// match a.compare_exchange_weak(ptr, new, SeqCst, SeqCst, guard) {
542 /// Ok(p) => {
543 /// ptr = p;
544 /// break;
545 /// }
546 /// Err(err) => {
547 /// ptr = err.current;
548 /// new = err.new;
549 /// }
550 /// }
551 /// }
552 ///
553 /// let mut curr = a.load(SeqCst, guard);
554 /// loop {
555 /// match a.compare_exchange_weak(curr, Shared::null(), SeqCst, SeqCst, guard) {
556 /// Ok(_) => break,
557 /// Err(err) => curr = err.current,
558 /// }
559 /// }
560 /// # unsafe { drop(curr.into_owned()); } // avoid leak
561 /// ```
562 pub fn compare_exchange_weak<'g, P>(
563 &self,
564 current: Shared<'_, T>,
565 new: P,
566 success: Ordering,
567 failure: Ordering,
568 _: &'g Guard,
569 ) -> Result<Shared<'g, T>, CompareExchangeError<'g, T, P>>
570 where
571 P: Pointer<T>,
572 {
573 let new = new.into_usize();
574 self.data
575 .compare_exchange_weak(current.into_usize(), new, success, failure)
576 .map(|_| unsafe { Shared::from_usize(new) })
577 .map_err(|current| unsafe {
578 CompareExchangeError {
579 current: Shared::from_usize(current),
580 new: P::from_usize(new),
581 }
582 })
583 }
584
585 /// Fetches the pointer, and then applies a function to it that returns a new value.
586 /// Returns a `Result` of `Ok(previous_value)` if the function returned `Some`, else `Err(_)`.
587 ///
588 /// Note that the given function may be called multiple times if the value has been changed by
589 /// other threads in the meantime, as long as the function returns `Some(_)`, but the function
590 /// will have been applied only once to the stored value.
591 ///
592 /// `fetch_update` takes two [`Ordering`] arguments to describe the memory
593 /// ordering of this operation. The first describes the required ordering for
594 /// when the operation finally succeeds while the second describes the
595 /// required ordering for loads. These correspond to the success and failure
596 /// orderings of [`Atomic::compare_exchange`] respectively.
597 ///
598 /// Using [`Acquire`] as success ordering makes the store part of this
599 /// operation [`Relaxed`], and using [`Release`] makes the final successful
600 /// load [`Relaxed`]. The (failed) load ordering can only be [`SeqCst`],
601 /// [`Acquire`] or [`Relaxed`] and must be equivalent to or weaker than the
602 /// success ordering.
603 ///
604 /// [`Relaxed`]: Ordering::Relaxed
605 /// [`Acquire`]: Ordering::Acquire
606 /// [`Release`]: Ordering::Release
607 /// [`SeqCst`]: Ordering::SeqCst
608 ///
609 /// # Examples
610 ///
611 /// ```
612 /// use crossbeam_epoch::{self as epoch, Atomic};
613 /// use std::sync::atomic::Ordering::SeqCst;
614 ///
615 /// let a = Atomic::new(1234);
616 /// let guard = &epoch::pin();
617 ///
618 /// let res1 = a.fetch_update(SeqCst, SeqCst, guard, |x| Some(x.with_tag(1)));
619 /// assert!(res1.is_ok());
620 ///
621 /// let res2 = a.fetch_update(SeqCst, SeqCst, guard, |x| None);
622 /// assert!(res2.is_err());
623 /// # unsafe { drop(a.into_owned()); } // avoid leak
624 /// ```
625 pub fn fetch_update<'g, F>(
626 &self,
627 set_order: Ordering,
628 fail_order: Ordering,
629 guard: &'g Guard,
630 mut func: F,
631 ) -> Result<Shared<'g, T>, Shared<'g, T>>
632 where
633 F: FnMut(Shared<'g, T>) -> Option<Shared<'g, T>>,
634 {
635 let mut prev = self.load(fail_order, guard);
636 while let Some(next) = func(prev) {
637 match self.compare_exchange_weak(prev, next, set_order, fail_order, guard) {
638 Ok(shared) => return Ok(shared),
639 Err(next_prev) => prev = next_prev.current,
640 }
641 }
642 Err(prev)
643 }
644
645 /// Stores the pointer `new` (either `Shared` or `Owned`) into the atomic pointer if the current
646 /// value is the same as `current`. The tag is also taken into account, so two pointers to the
647 /// same object, but with different tags, will not be considered equal.
648 ///
649 /// The return value is a result indicating whether the new pointer was written. On success the
650 /// pointer that was written is returned. On failure the actual current value and `new` are
651 /// returned.
652 ///
653 /// This method takes a [`CompareAndSetOrdering`] argument which describes the memory
654 /// ordering of this operation.
655 ///
656 /// # Migrating to `compare_exchange`
657 ///
658 /// `compare_and_set` is equivalent to `compare_exchange` with the following mapping for
659 /// memory orderings:
660 ///
661 /// Original | Success | Failure
662 /// -------- | ------- | -------
663 /// Relaxed | Relaxed | Relaxed
664 /// Acquire | Acquire | Acquire
665 /// Release | Release | Relaxed
666 /// AcqRel | AcqRel | Acquire
667 /// SeqCst | SeqCst | SeqCst
668 ///
669 /// # Examples
670 ///
671 /// ```
672 /// # #![allow(deprecated)]
673 /// use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
674 /// use std::sync::atomic::Ordering::SeqCst;
675 ///
676 /// let a = Atomic::new(1234);
677 ///
678 /// let guard = &epoch::pin();
679 /// let curr = a.load(SeqCst, guard);
680 /// let res1 = a.compare_and_set(curr, Shared::null(), SeqCst, guard);
681 /// let res2 = a.compare_and_set(curr, Owned::new(5678), SeqCst, guard);
682 /// # unsafe { drop(curr.into_owned()); } // avoid leak
683 /// ```
684 // TODO: remove in the next major version.
685 #[allow(deprecated)]
686 #[deprecated(note = "Use `compare_exchange` instead")]
687 pub fn compare_and_set<'g, O, P>(
688 &self,
689 current: Shared<'_, T>,
690 new: P,
691 ord: O,
692 guard: &'g Guard,
693 ) -> Result<Shared<'g, T>, CompareAndSetError<'g, T, P>>
694 where
695 O: CompareAndSetOrdering,
696 P: Pointer<T>,
697 {
698 self.compare_exchange(current, new, ord.success(), ord.failure(), guard)
699 }
700
701 /// Stores the pointer `new` (either `Shared` or `Owned`) into the atomic pointer if the current
702 /// value is the same as `current`. The tag is also taken into account, so two pointers to the
703 /// same object, but with different tags, will not be considered equal.
704 ///
705 /// Unlike [`compare_and_set`], this method is allowed to spuriously fail even when comparison
706 /// succeeds, which can result in more efficient code on some platforms. The return value is a
707 /// result indicating whether the new pointer was written. On success the pointer that was
708 /// written is returned. On failure the actual current value and `new` are returned.
709 ///
710 /// This method takes a [`CompareAndSetOrdering`] argument which describes the memory
711 /// ordering of this operation.
712 ///
713 /// [`compare_and_set`]: Atomic::compare_and_set
714 ///
715 /// # Migrating to `compare_exchange_weak`
716 ///
717 /// `compare_and_set_weak` is equivalent to `compare_exchange_weak` with the following mapping for
718 /// memory orderings:
719 ///
720 /// Original | Success | Failure
721 /// -------- | ------- | -------
722 /// Relaxed | Relaxed | Relaxed
723 /// Acquire | Acquire | Acquire
724 /// Release | Release | Relaxed
725 /// AcqRel | AcqRel | Acquire
726 /// SeqCst | SeqCst | SeqCst
727 ///
728 /// # Examples
729 ///
730 /// ```
731 /// # #![allow(deprecated)]
732 /// use crossbeam_epoch::{self as epoch, Atomic, Owned, Shared};
733 /// use std::sync::atomic::Ordering::SeqCst;
734 ///
735 /// let a = Atomic::new(1234);
736 /// let guard = &epoch::pin();
737 ///
738 /// let mut new = Owned::new(5678);
739 /// let mut ptr = a.load(SeqCst, guard);
740 /// # unsafe { drop(a.load(SeqCst, guard).into_owned()); } // avoid leak
741 /// loop {
742 /// match a.compare_and_set_weak(ptr, new, SeqCst, guard) {
743 /// Ok(p) => {
744 /// ptr = p;
745 /// break;
746 /// }
747 /// Err(err) => {
748 /// ptr = err.current;
749 /// new = err.new;
750 /// }
751 /// }
752 /// }
753 ///
754 /// let mut curr = a.load(SeqCst, guard);
755 /// loop {
756 /// match a.compare_and_set_weak(curr, Shared::null(), SeqCst, guard) {
757 /// Ok(_) => break,
758 /// Err(err) => curr = err.current,
759 /// }
760 /// }
761 /// # unsafe { drop(curr.into_owned()); } // avoid leak
762 /// ```
763 // TODO: remove in the next major version.
764 #[allow(deprecated)]
765 #[deprecated(note = "Use `compare_exchange_weak` instead")]
766 pub fn compare_and_set_weak<'g, O, P>(
767 &self,
768 current: Shared<'_, T>,
769 new: P,
770 ord: O,
771 guard: &'g Guard,
772 ) -> Result<Shared<'g, T>, CompareAndSetError<'g, T, P>>
773 where
774 O: CompareAndSetOrdering,
775 P: Pointer<T>,
776 {
777 self.compare_exchange_weak(current, new, ord.success(), ord.failure(), guard)
778 }
779
780 /// Bitwise "and" with the current tag.
781 ///
782 /// Performs a bitwise "and" operation on the current tag and the argument `val`, and sets the
783 /// new tag to the result. Returns the previous pointer.
784 ///
785 /// This method takes an [`Ordering`] argument which describes the memory ordering of this
786 /// operation.
787 ///
788 /// # Examples
789 ///
790 /// ```
791 /// use crossbeam_epoch::{self as epoch, Atomic, Shared};
792 /// use std::sync::atomic::Ordering::SeqCst;
793 ///
794 /// let a = Atomic::<i32>::from(Shared::null().with_tag(3));
795 /// let guard = &epoch::pin();
796 /// assert_eq!(a.fetch_and(2, SeqCst, guard).tag(), 3);
797 /// assert_eq!(a.load(SeqCst, guard).tag(), 2);
798 /// ```
799 pub fn fetch_and<'g>(&self, val: usize, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
800 unsafe { Shared::from_usize(self.data.fetch_and(val | !low_bits::<T>(), ord)) }
801 }
802
803 /// Bitwise "or" with the current tag.
804 ///
805 /// Performs a bitwise "or" operation on the current tag and the argument `val`, and sets the
806 /// new tag to the result. Returns the previous pointer.
807 ///
808 /// This method takes an [`Ordering`] argument which describes the memory ordering of this
809 /// operation.
810 ///
811 /// # Examples
812 ///
813 /// ```
814 /// use crossbeam_epoch::{self as epoch, Atomic, Shared};
815 /// use std::sync::atomic::Ordering::SeqCst;
816 ///
817 /// let a = Atomic::<i32>::from(Shared::null().with_tag(1));
818 /// let guard = &epoch::pin();
819 /// assert_eq!(a.fetch_or(2, SeqCst, guard).tag(), 1);
820 /// assert_eq!(a.load(SeqCst, guard).tag(), 3);
821 /// ```
822 pub fn fetch_or<'g>(&self, val: usize, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
823 unsafe { Shared::from_usize(self.data.fetch_or(val & low_bits::<T>(), ord)) }
824 }
825
826 /// Bitwise "xor" with the current tag.
827 ///
828 /// Performs a bitwise "xor" operation on the current tag and the argument `val`, and sets the
829 /// new tag to the result. Returns the previous pointer.
830 ///
831 /// This method takes an [`Ordering`] argument which describes the memory ordering of this
832 /// operation.
833 ///
834 /// # Examples
835 ///
836 /// ```
837 /// use crossbeam_epoch::{self as epoch, Atomic, Shared};
838 /// use std::sync::atomic::Ordering::SeqCst;
839 ///
840 /// let a = Atomic::<i32>::from(Shared::null().with_tag(1));
841 /// let guard = &epoch::pin();
842 /// assert_eq!(a.fetch_xor(3, SeqCst, guard).tag(), 1);
843 /// assert_eq!(a.load(SeqCst, guard).tag(), 2);
844 /// ```
845 pub fn fetch_xor<'g>(&self, val: usize, ord: Ordering, _: &'g Guard) -> Shared<'g, T> {
846 unsafe { Shared::from_usize(self.data.fetch_xor(val & low_bits::<T>(), ord)) }
847 }
848
849 /// Takes ownership of the pointee.
850 ///
851 /// This consumes the atomic and converts it into [`Owned`]. As [`Atomic`] doesn't have a
852 /// destructor and doesn't drop the pointee while [`Owned`] does, this is suitable for
853 /// destructors of data structures.
854 ///
855 /// # Panics
856 ///
857 /// Panics if this pointer is null, but only in debug mode.
858 ///
859 /// # Safety
860 ///
861 /// This method may be called only if the pointer is valid and nobody else is holding a
862 /// reference to the same object.
863 ///
864 /// # Examples
865 ///
866 /// ```rust
867 /// # use std::mem;
868 /// # use crossbeam_epoch::Atomic;
869 /// struct DataStructure {
870 /// ptr: Atomic<usize>,
871 /// }
872 ///
873 /// impl Drop for DataStructure {
874 /// fn drop(&mut self) {
875 /// // By now the DataStructure lives only in our thread and we are sure we don't hold
876 /// // any Shared or & to it ourselves.
877 /// unsafe {
878 /// drop(mem::replace(&mut self.ptr, Atomic::null()).into_owned());
879 /// }
880 /// }
881 /// }
882 /// ```
883 pub unsafe fn into_owned(self) -> Owned<T> {
884 Owned::from_usize(self.data.into_inner())
885 }
886
887 /// Takes ownership of the pointee if it is non-null.
888 ///
889 /// This consumes the atomic and converts it into [`Owned`]. As [`Atomic`] doesn't have a
890 /// destructor and doesn't drop the pointee while [`Owned`] does, this is suitable for
891 /// destructors of data structures.
892 ///
893 /// # Safety
894 ///
895 /// This method may be called only if the pointer is valid and nobody else is holding a
896 /// reference to the same object, or the pointer is null.
897 ///
898 /// # Examples
899 ///
900 /// ```rust
901 /// # use std::mem;
902 /// # use crossbeam_epoch::Atomic;
903 /// struct DataStructure {
904 /// ptr: Atomic<usize>,
905 /// }
906 ///
907 /// impl Drop for DataStructure {
908 /// fn drop(&mut self) {
909 /// // By now the DataStructure lives only in our thread and we are sure we don't hold
910 /// // any Shared or & to it ourselves, but it may be null, so we have to be careful.
911 /// let old = mem::replace(&mut self.ptr, Atomic::null());
912 /// unsafe {
913 /// if let Some(x) = old.try_into_owned() {
914 /// drop(x)
915 /// }
916 /// }
917 /// }
918 /// }
919 /// ```
920 pub unsafe fn try_into_owned(self) -> Option<Owned<T>> {
921 let data = self.data.into_inner();
922 if decompose_tag::<T>(data).0 == 0 {
923 None
924 } else {
925 Some(Owned::from_usize(data))
926 }
927 }
928}
929
930impl<T: ?Sized + Pointable> fmt::Debug for Atomic<T> {
931 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
932 let data: usize = self.data.load(order:Ordering::SeqCst);
933 let (raw: usize, tag: usize) = decompose_tag::<T>(data);
934
935 f&mut DebugStruct<'_, '_>.debug_struct("Atomic")
936 .field("raw", &raw)
937 .field(name:"tag", &tag)
938 .finish()
939 }
940}
941
942impl<T: ?Sized + Pointable> fmt::Pointer for Atomic<T> {
943 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
944 let data: usize = self.data.load(order:Ordering::SeqCst);
945 let (raw: usize, _) = decompose_tag::<T>(data);
946 fmt::Pointer::fmt(&(unsafe { T::deref(ptr:raw) as *const _ }), f)
947 }
948}
949
950impl<T: ?Sized + Pointable> Clone for Atomic<T> {
951 /// Returns a copy of the atomic value.
952 ///
953 /// Note that a `Relaxed` load is used here. If you need synchronization, use it with other
954 /// atomics or fences.
955 fn clone(&self) -> Self {
956 let data: usize = self.data.load(order:Ordering::Relaxed);
957 Atomic::from_usize(data)
958 }
959}
960
961impl<T: ?Sized + Pointable> Default for Atomic<T> {
962 fn default() -> Self {
963 Atomic::null()
964 }
965}
966
967impl<T: ?Sized + Pointable> From<Owned<T>> for Atomic<T> {
968 /// Returns a new atomic pointer pointing to `owned`.
969 ///
970 /// # Examples
971 ///
972 /// ```
973 /// use crossbeam_epoch::{Atomic, Owned};
974 ///
975 /// let a = Atomic::<i32>::from(Owned::new(1234));
976 /// # unsafe { drop(a.into_owned()); } // avoid leak
977 /// ```
978 fn from(owned: Owned<T>) -> Self {
979 let data: usize = owned.data;
980 mem::forget(owned);
981 Self::from_usize(data)
982 }
983}
984
985impl<T> From<Box<T>> for Atomic<T> {
986 fn from(b: Box<T>) -> Self {
987 Self::from(Owned::from(b))
988 }
989}
990
991impl<T> From<T> for Atomic<T> {
992 fn from(t: T) -> Self {
993 Self::new(init:t)
994 }
995}
996
997impl<'g, T: ?Sized + Pointable> From<Shared<'g, T>> for Atomic<T> {
998 /// Returns a new atomic pointer pointing to `ptr`.
999 ///
1000 /// # Examples
1001 ///
1002 /// ```
1003 /// use crossbeam_epoch::{Atomic, Shared};
1004 ///
1005 /// let a = Atomic::<i32>::from(Shared::<i32>::null());
1006 /// ```
1007 fn from(ptr: Shared<'g, T>) -> Self {
1008 Self::from_usize(ptr.data)
1009 }
1010}
1011
1012impl<T> From<*const T> for Atomic<T> {
1013 /// Returns a new atomic pointer pointing to `raw`.
1014 ///
1015 /// # Examples
1016 ///
1017 /// ```
1018 /// use std::ptr;
1019 /// use crossbeam_epoch::Atomic;
1020 ///
1021 /// let a = Atomic::<i32>::from(ptr::null::<i32>());
1022 /// ```
1023 fn from(raw: *const T) -> Self {
1024 Self::from_usize(data:raw as usize)
1025 }
1026}
1027
1028/// A trait for either `Owned` or `Shared` pointers.
1029pub trait Pointer<T: ?Sized + Pointable> {
1030 /// Returns the machine representation of the pointer.
1031 fn into_usize(self) -> usize;
1032
1033 /// Returns a new pointer pointing to the tagged pointer `data`.
1034 ///
1035 /// # Safety
1036 ///
1037 /// The given `data` should have been created by `Pointer::into_usize()`, and one `data` should
1038 /// not be converted back by `Pointer::from_usize()` multiple times.
1039 unsafe fn from_usize(data: usize) -> Self;
1040}
1041
1042/// An owned heap-allocated object.
1043///
1044/// This type is very similar to `Box<T>`.
1045///
1046/// The pointer must be properly aligned. Since it is aligned, a tag can be stored into the unused
1047/// least significant bits of the address.
1048pub struct Owned<T: ?Sized + Pointable> {
1049 data: usize,
1050 _marker: PhantomData<Box<T>>,
1051}
1052
1053impl<T: ?Sized + Pointable> Pointer<T> for Owned<T> {
1054 #[inline]
1055 fn into_usize(self) -> usize {
1056 let data: usize = self.data;
1057 mem::forget(self);
1058 data
1059 }
1060
1061 /// Returns a new pointer pointing to the tagged pointer `data`.
1062 ///
1063 /// # Panics
1064 ///
1065 /// Panics if the data is zero in debug mode.
1066 #[inline]
1067 unsafe fn from_usize(data: usize) -> Self {
1068 debug_assert!(data != 0, "converting zero into `Owned`");
1069 Owned {
1070 data,
1071 _marker: PhantomData,
1072 }
1073 }
1074}
1075
1076impl<T> Owned<T> {
1077 /// Returns a new owned pointer pointing to `raw`.
1078 ///
1079 /// This function is unsafe because improper use may lead to memory problems. Argument `raw`
1080 /// must be a valid pointer. Also, a double-free may occur if the function is called twice on
1081 /// the same raw pointer.
1082 ///
1083 /// # Panics
1084 ///
1085 /// Panics if `raw` is not properly aligned.
1086 ///
1087 /// # Safety
1088 ///
1089 /// The given `raw` should have been derived from `Owned`, and one `raw` should not be converted
1090 /// back by `Owned::from_raw()` multiple times.
1091 ///
1092 /// # Examples
1093 ///
1094 /// ```
1095 /// use crossbeam_epoch::Owned;
1096 ///
1097 /// let o = unsafe { Owned::from_raw(Box::into_raw(Box::new(1234))) };
1098 /// ```
1099 pub unsafe fn from_raw(raw: *mut T) -> Owned<T> {
1100 let raw = raw as usize;
1101 ensure_aligned::<T>(raw);
1102 Self::from_usize(raw)
1103 }
1104
1105 /// Converts the owned pointer into a `Box`.
1106 ///
1107 /// # Examples
1108 ///
1109 /// ```
1110 /// use crossbeam_epoch::Owned;
1111 ///
1112 /// let o = Owned::new(1234);
1113 /// let b: Box<i32> = o.into_box();
1114 /// assert_eq!(*b, 1234);
1115 /// ```
1116 pub fn into_box(self) -> Box<T> {
1117 let (raw, _) = decompose_tag::<T>(self.data);
1118 mem::forget(self);
1119 unsafe { Box::from_raw(raw as *mut _) }
1120 }
1121
1122 /// Allocates `value` on the heap and returns a new owned pointer pointing to it.
1123 ///
1124 /// # Examples
1125 ///
1126 /// ```
1127 /// use crossbeam_epoch::Owned;
1128 ///
1129 /// let o = Owned::new(1234);
1130 /// ```
1131 pub fn new(init: T) -> Owned<T> {
1132 Self::init(init)
1133 }
1134}
1135
1136impl<T: ?Sized + Pointable> Owned<T> {
1137 /// Allocates `value` on the heap and returns a new owned pointer pointing to it.
1138 ///
1139 /// # Examples
1140 ///
1141 /// ```
1142 /// use crossbeam_epoch::Owned;
1143 ///
1144 /// let o = Owned::<i32>::init(1234);
1145 /// ```
1146 pub fn init(init: T::Init) -> Owned<T> {
1147 unsafe { Self::from_usize(T::init(init)) }
1148 }
1149
1150 /// Converts the owned pointer into a [`Shared`].
1151 ///
1152 /// # Examples
1153 ///
1154 /// ```
1155 /// use crossbeam_epoch::{self as epoch, Owned};
1156 ///
1157 /// let o = Owned::new(1234);
1158 /// let guard = &epoch::pin();
1159 /// let p = o.into_shared(guard);
1160 /// # unsafe { drop(p.into_owned()); } // avoid leak
1161 /// ```
1162 #[allow(clippy::needless_lifetimes)]
1163 pub fn into_shared<'g>(self, _: &'g Guard) -> Shared<'g, T> {
1164 unsafe { Shared::from_usize(self.into_usize()) }
1165 }
1166
1167 /// Returns the tag stored within the pointer.
1168 ///
1169 /// # Examples
1170 ///
1171 /// ```
1172 /// use crossbeam_epoch::Owned;
1173 ///
1174 /// assert_eq!(Owned::new(1234).tag(), 0);
1175 /// ```
1176 pub fn tag(&self) -> usize {
1177 let (_, tag) = decompose_tag::<T>(self.data);
1178 tag
1179 }
1180
1181 /// Returns the same pointer, but tagged with `tag`. `tag` is truncated to be fit into the
1182 /// unused bits of the pointer to `T`.
1183 ///
1184 /// # Examples
1185 ///
1186 /// ```
1187 /// use crossbeam_epoch::Owned;
1188 ///
1189 /// let o = Owned::new(0u64);
1190 /// assert_eq!(o.tag(), 0);
1191 /// let o = o.with_tag(2);
1192 /// assert_eq!(o.tag(), 2);
1193 /// ```
1194 pub fn with_tag(self, tag: usize) -> Owned<T> {
1195 let data = self.into_usize();
1196 unsafe { Self::from_usize(compose_tag::<T>(data, tag)) }
1197 }
1198}
1199
1200impl<T: ?Sized + Pointable> Drop for Owned<T> {
1201 fn drop(&mut self) {
1202 let (raw: usize, _) = decompose_tag::<T>(self.data);
1203 unsafe {
1204 T::drop(ptr:raw);
1205 }
1206 }
1207}
1208
1209impl<T: ?Sized + Pointable> fmt::Debug for Owned<T> {
1210 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1211 let (raw: usize, tag: usize) = decompose_tag::<T>(self.data);
1212
1213 f&mut DebugStruct<'_, '_>.debug_struct("Owned")
1214 .field("raw", &raw)
1215 .field(name:"tag", &tag)
1216 .finish()
1217 }
1218}
1219
1220impl<T: Clone> Clone for Owned<T> {
1221 fn clone(&self) -> Self {
1222 Owned::new((**self).clone()).with_tag(self.tag())
1223 }
1224}
1225
1226impl<T: ?Sized + Pointable> Deref for Owned<T> {
1227 type Target = T;
1228
1229 fn deref(&self) -> &T {
1230 let (raw: usize, _) = decompose_tag::<T>(self.data);
1231 unsafe { T::deref(ptr:raw) }
1232 }
1233}
1234
1235impl<T: ?Sized + Pointable> DerefMut for Owned<T> {
1236 fn deref_mut(&mut self) -> &mut T {
1237 let (raw: usize, _) = decompose_tag::<T>(self.data);
1238 unsafe { T::deref_mut(ptr:raw) }
1239 }
1240}
1241
1242impl<T> From<T> for Owned<T> {
1243 fn from(t: T) -> Self {
1244 Owned::new(init:t)
1245 }
1246}
1247
1248impl<T> From<Box<T>> for Owned<T> {
1249 /// Returns a new owned pointer pointing to `b`.
1250 ///
1251 /// # Panics
1252 ///
1253 /// Panics if the pointer (the `Box`) is not properly aligned.
1254 ///
1255 /// # Examples
1256 ///
1257 /// ```
1258 /// use crossbeam_epoch::Owned;
1259 ///
1260 /// let o = unsafe { Owned::from_raw(Box::into_raw(Box::new(1234))) };
1261 /// ```
1262 fn from(b: Box<T>) -> Self {
1263 unsafe { Self::from_raw(Box::into_raw(b)) }
1264 }
1265}
1266
1267impl<T: ?Sized + Pointable> Borrow<T> for Owned<T> {
1268 fn borrow(&self) -> &T {
1269 self.deref()
1270 }
1271}
1272
1273impl<T: ?Sized + Pointable> BorrowMut<T> for Owned<T> {
1274 fn borrow_mut(&mut self) -> &mut T {
1275 self.deref_mut()
1276 }
1277}
1278
1279impl<T: ?Sized + Pointable> AsRef<T> for Owned<T> {
1280 fn as_ref(&self) -> &T {
1281 self.deref()
1282 }
1283}
1284
1285impl<T: ?Sized + Pointable> AsMut<T> for Owned<T> {
1286 fn as_mut(&mut self) -> &mut T {
1287 self.deref_mut()
1288 }
1289}
1290
1291/// A pointer to an object protected by the epoch GC.
1292///
1293/// The pointer is valid for use only during the lifetime `'g`.
1294///
1295/// The pointer must be properly aligned. Since it is aligned, a tag can be stored into the unused
1296/// least significant bits of the address.
1297pub struct Shared<'g, T: 'g + ?Sized + Pointable> {
1298 data: usize,
1299 _marker: PhantomData<(&'g (), *const T)>,
1300}
1301
1302impl<T: ?Sized + Pointable> Clone for Shared<'_, T> {
1303 fn clone(&self) -> Self {
1304 *self
1305 }
1306}
1307
1308impl<T: ?Sized + Pointable> Copy for Shared<'_, T> {}
1309
1310impl<T: ?Sized + Pointable> Pointer<T> for Shared<'_, T> {
1311 #[inline]
1312 fn into_usize(self) -> usize {
1313 self.data
1314 }
1315
1316 #[inline]
1317 unsafe fn from_usize(data: usize) -> Self {
1318 Shared {
1319 data,
1320 _marker: PhantomData,
1321 }
1322 }
1323}
1324
1325impl<'g, T> Shared<'g, T> {
1326 /// Converts the pointer to a raw pointer (without the tag).
1327 ///
1328 /// # Examples
1329 ///
1330 /// ```
1331 /// use crossbeam_epoch::{self as epoch, Atomic, Owned};
1332 /// use std::sync::atomic::Ordering::SeqCst;
1333 ///
1334 /// let o = Owned::new(1234);
1335 /// let raw = &*o as *const _;
1336 /// let a = Atomic::from(o);
1337 ///
1338 /// let guard = &epoch::pin();
1339 /// let p = a.load(SeqCst, guard);
1340 /// assert_eq!(p.as_raw(), raw);
1341 /// # unsafe { drop(a.into_owned()); } // avoid leak
1342 /// ```
1343 pub fn as_raw(&self) -> *const T {
1344 let (raw: usize, _) = decompose_tag::<T>(self.data);
1345 raw as *const _
1346 }
1347}
1348
1349impl<'g, T: ?Sized + Pointable> Shared<'g, T> {
1350 /// Returns a new null pointer.
1351 ///
1352 /// # Examples
1353 ///
1354 /// ```
1355 /// use crossbeam_epoch::Shared;
1356 ///
1357 /// let p = Shared::<i32>::null();
1358 /// assert!(p.is_null());
1359 /// ```
1360 pub fn null() -> Shared<'g, T> {
1361 Shared {
1362 data: 0,
1363 _marker: PhantomData,
1364 }
1365 }
1366
1367 /// Returns `true` if the pointer is null.
1368 ///
1369 /// # Examples
1370 ///
1371 /// ```
1372 /// use crossbeam_epoch::{self as epoch, Atomic, Owned};
1373 /// use std::sync::atomic::Ordering::SeqCst;
1374 ///
1375 /// let a = Atomic::null();
1376 /// let guard = &epoch::pin();
1377 /// assert!(a.load(SeqCst, guard).is_null());
1378 /// a.store(Owned::new(1234), SeqCst);
1379 /// assert!(!a.load(SeqCst, guard).is_null());
1380 /// # unsafe { drop(a.into_owned()); } // avoid leak
1381 /// ```
1382 pub fn is_null(&self) -> bool {
1383 let (raw, _) = decompose_tag::<T>(self.data);
1384 raw == 0
1385 }
1386
1387 /// Dereferences the pointer.
1388 ///
1389 /// Returns a reference to the pointee that is valid during the lifetime `'g`.
1390 ///
1391 /// # Safety
1392 ///
1393 /// Dereferencing a pointer is unsafe because it could be pointing to invalid memory.
1394 ///
1395 /// Another concern is the possibility of data races due to lack of proper synchronization.
1396 /// For example, consider the following scenario:
1397 ///
1398 /// 1. A thread creates a new object: `a.store(Owned::new(10), Relaxed)`
1399 /// 2. Another thread reads it: `*a.load(Relaxed, guard).as_ref().unwrap()`
1400 ///
1401 /// The problem is that relaxed orderings don't synchronize initialization of the object with
1402 /// the read from the second thread. This is a data race. A possible solution would be to use
1403 /// `Release` and `Acquire` orderings.
1404 ///
1405 /// # Examples
1406 ///
1407 /// ```
1408 /// use crossbeam_epoch::{self as epoch, Atomic};
1409 /// use std::sync::atomic::Ordering::SeqCst;
1410 ///
1411 /// let a = Atomic::new(1234);
1412 /// let guard = &epoch::pin();
1413 /// let p = a.load(SeqCst, guard);
1414 /// unsafe {
1415 /// assert_eq!(p.deref(), &1234);
1416 /// }
1417 /// # unsafe { drop(a.into_owned()); } // avoid leak
1418 /// ```
1419 pub unsafe fn deref(&self) -> &'g T {
1420 let (raw, _) = decompose_tag::<T>(self.data);
1421 T::deref(raw)
1422 }
1423
1424 /// Dereferences the pointer.
1425 ///
1426 /// Returns a mutable reference to the pointee that is valid during the lifetime `'g`.
1427 ///
1428 /// # Safety
1429 ///
1430 /// * There is no guarantee that there are no more threads attempting to read/write from/to the
1431 /// actual object at the same time.
1432 ///
1433 /// The user must know that there are no concurrent accesses towards the object itself.
1434 ///
1435 /// * Other than the above, all safety concerns of `deref()` applies here.
1436 ///
1437 /// # Examples
1438 ///
1439 /// ```
1440 /// use crossbeam_epoch::{self as epoch, Atomic};
1441 /// use std::sync::atomic::Ordering::SeqCst;
1442 ///
1443 /// let a = Atomic::new(vec![1, 2, 3, 4]);
1444 /// let guard = &epoch::pin();
1445 ///
1446 /// let mut p = a.load(SeqCst, guard);
1447 /// unsafe {
1448 /// assert!(!p.is_null());
1449 /// let b = p.deref_mut();
1450 /// assert_eq!(b, &vec![1, 2, 3, 4]);
1451 /// b.push(5);
1452 /// assert_eq!(b, &vec![1, 2, 3, 4, 5]);
1453 /// }
1454 ///
1455 /// let p = a.load(SeqCst, guard);
1456 /// unsafe {
1457 /// assert_eq!(p.deref(), &vec![1, 2, 3, 4, 5]);
1458 /// }
1459 /// # unsafe { drop(a.into_owned()); } // avoid leak
1460 /// ```
1461 pub unsafe fn deref_mut(&mut self) -> &'g mut T {
1462 let (raw, _) = decompose_tag::<T>(self.data);
1463 T::deref_mut(raw)
1464 }
1465
1466 /// Converts the pointer to a reference.
1467 ///
1468 /// Returns `None` if the pointer is null, or else a reference to the object wrapped in `Some`.
1469 ///
1470 /// # Safety
1471 ///
1472 /// Dereferencing a pointer is unsafe because it could be pointing to invalid memory.
1473 ///
1474 /// Another concern is the possibility of data races due to lack of proper synchronization.
1475 /// For example, consider the following scenario:
1476 ///
1477 /// 1. A thread creates a new object: `a.store(Owned::new(10), Relaxed)`
1478 /// 2. Another thread reads it: `*a.load(Relaxed, guard).as_ref().unwrap()`
1479 ///
1480 /// The problem is that relaxed orderings don't synchronize initialization of the object with
1481 /// the read from the second thread. This is a data race. A possible solution would be to use
1482 /// `Release` and `Acquire` orderings.
1483 ///
1484 /// # Examples
1485 ///
1486 /// ```
1487 /// use crossbeam_epoch::{self as epoch, Atomic};
1488 /// use std::sync::atomic::Ordering::SeqCst;
1489 ///
1490 /// let a = Atomic::new(1234);
1491 /// let guard = &epoch::pin();
1492 /// let p = a.load(SeqCst, guard);
1493 /// unsafe {
1494 /// assert_eq!(p.as_ref(), Some(&1234));
1495 /// }
1496 /// # unsafe { drop(a.into_owned()); } // avoid leak
1497 /// ```
1498 pub unsafe fn as_ref(&self) -> Option<&'g T> {
1499 let (raw, _) = decompose_tag::<T>(self.data);
1500 if raw == 0 {
1501 None
1502 } else {
1503 Some(T::deref(raw))
1504 }
1505 }
1506
1507 /// Takes ownership of the pointee.
1508 ///
1509 /// # Panics
1510 ///
1511 /// Panics if this pointer is null, but only in debug mode.
1512 ///
1513 /// # Safety
1514 ///
1515 /// This method may be called only if the pointer is valid and nobody else is holding a
1516 /// reference to the same object.
1517 ///
1518 /// # Examples
1519 ///
1520 /// ```
1521 /// use crossbeam_epoch::{self as epoch, Atomic};
1522 /// use std::sync::atomic::Ordering::SeqCst;
1523 ///
1524 /// let a = Atomic::new(1234);
1525 /// unsafe {
1526 /// let guard = &epoch::unprotected();
1527 /// let p = a.load(SeqCst, guard);
1528 /// drop(p.into_owned());
1529 /// }
1530 /// ```
1531 pub unsafe fn into_owned(self) -> Owned<T> {
1532 debug_assert!(!self.is_null(), "converting a null `Shared` into `Owned`");
1533 Owned::from_usize(self.data)
1534 }
1535
1536 /// Takes ownership of the pointee if it is not null.
1537 ///
1538 /// # Safety
1539 ///
1540 /// This method may be called only if the pointer is valid and nobody else is holding a
1541 /// reference to the same object, or if the pointer is null.
1542 ///
1543 /// # Examples
1544 ///
1545 /// ```
1546 /// use crossbeam_epoch::{self as epoch, Atomic};
1547 /// use std::sync::atomic::Ordering::SeqCst;
1548 ///
1549 /// let a = Atomic::new(1234);
1550 /// unsafe {
1551 /// let guard = &epoch::unprotected();
1552 /// let p = a.load(SeqCst, guard);
1553 /// if let Some(x) = p.try_into_owned() {
1554 /// drop(x);
1555 /// }
1556 /// }
1557 /// ```
1558 pub unsafe fn try_into_owned(self) -> Option<Owned<T>> {
1559 if self.is_null() {
1560 None
1561 } else {
1562 Some(Owned::from_usize(self.data))
1563 }
1564 }
1565
1566 /// Returns the tag stored within the pointer.
1567 ///
1568 /// # Examples
1569 ///
1570 /// ```
1571 /// use crossbeam_epoch::{self as epoch, Atomic, Owned};
1572 /// use std::sync::atomic::Ordering::SeqCst;
1573 ///
1574 /// let a = Atomic::<u64>::from(Owned::new(0u64).with_tag(2));
1575 /// let guard = &epoch::pin();
1576 /// let p = a.load(SeqCst, guard);
1577 /// assert_eq!(p.tag(), 2);
1578 /// # unsafe { drop(a.into_owned()); } // avoid leak
1579 /// ```
1580 pub fn tag(&self) -> usize {
1581 let (_, tag) = decompose_tag::<T>(self.data);
1582 tag
1583 }
1584
1585 /// Returns the same pointer, but tagged with `tag`. `tag` is truncated to be fit into the
1586 /// unused bits of the pointer to `T`.
1587 ///
1588 /// # Examples
1589 ///
1590 /// ```
1591 /// use crossbeam_epoch::{self as epoch, Atomic};
1592 /// use std::sync::atomic::Ordering::SeqCst;
1593 ///
1594 /// let a = Atomic::new(0u64);
1595 /// let guard = &epoch::pin();
1596 /// let p1 = a.load(SeqCst, guard);
1597 /// let p2 = p1.with_tag(2);
1598 ///
1599 /// assert_eq!(p1.tag(), 0);
1600 /// assert_eq!(p2.tag(), 2);
1601 /// assert_eq!(p1.as_raw(), p2.as_raw());
1602 /// # unsafe { drop(a.into_owned()); } // avoid leak
1603 /// ```
1604 pub fn with_tag(&self, tag: usize) -> Shared<'g, T> {
1605 unsafe { Self::from_usize(compose_tag::<T>(self.data, tag)) }
1606 }
1607}
1608
1609impl<T> From<*const T> for Shared<'_, T> {
1610 /// Returns a new pointer pointing to `raw`.
1611 ///
1612 /// # Panics
1613 ///
1614 /// Panics if `raw` is not properly aligned.
1615 ///
1616 /// # Examples
1617 ///
1618 /// ```
1619 /// use crossbeam_epoch::Shared;
1620 ///
1621 /// let p = Shared::from(Box::into_raw(Box::new(1234)) as *const _);
1622 /// assert!(!p.is_null());
1623 /// # unsafe { drop(p.into_owned()); } // avoid leak
1624 /// ```
1625 fn from(raw: *const T) -> Self {
1626 let raw: usize = raw as usize;
1627 ensure_aligned::<T>(raw);
1628 unsafe { Self::from_usize(data:raw) }
1629 }
1630}
1631
1632impl<'g, T: ?Sized + Pointable> PartialEq<Shared<'g, T>> for Shared<'g, T> {
1633 fn eq(&self, other: &Self) -> bool {
1634 self.data == other.data
1635 }
1636}
1637
1638impl<T: ?Sized + Pointable> Eq for Shared<'_, T> {}
1639
1640impl<'g, T: ?Sized + Pointable> PartialOrd<Shared<'g, T>> for Shared<'g, T> {
1641 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1642 self.data.partial_cmp(&other.data)
1643 }
1644}
1645
1646impl<T: ?Sized + Pointable> Ord for Shared<'_, T> {
1647 fn cmp(&self, other: &Self) -> cmp::Ordering {
1648 self.data.cmp(&other.data)
1649 }
1650}
1651
1652impl<T: ?Sized + Pointable> fmt::Debug for Shared<'_, T> {
1653 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1654 let (raw: usize, tag: usize) = decompose_tag::<T>(self.data);
1655
1656 f&mut DebugStruct<'_, '_>.debug_struct("Shared")
1657 .field("raw", &raw)
1658 .field(name:"tag", &tag)
1659 .finish()
1660 }
1661}
1662
1663impl<T: ?Sized + Pointable> fmt::Pointer for Shared<'_, T> {
1664 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1665 fmt::Pointer::fmt(&(unsafe { self.deref() as *const _ }), f)
1666 }
1667}
1668
1669impl<T: ?Sized + Pointable> Default for Shared<'_, T> {
1670 fn default() -> Self {
1671 Shared::null()
1672 }
1673}
1674
1675#[cfg(all(test, not(crossbeam_loom)))]
1676mod tests {
1677 use super::{Owned, Shared};
1678 use std::mem::MaybeUninit;
1679
1680 #[test]
1681 fn valid_tag_i8() {
1682 Shared::<i8>::null().with_tag(0);
1683 }
1684
1685 #[test]
1686 fn valid_tag_i64() {
1687 Shared::<i64>::null().with_tag(7);
1688 }
1689
1690 #[test]
1691 fn const_atomic_null() {
1692 use super::Atomic;
1693 static _U: Atomic<u8> = Atomic::<u8>::null();
1694 }
1695
1696 #[test]
1697 fn array_init() {
1698 let owned = Owned::<[MaybeUninit<usize>]>::init(10);
1699 let arr: &[MaybeUninit<usize>] = &owned;
1700 assert_eq!(arr.len(), 10);
1701 }
1702}
1703