use std::sync::atomic::{AtomicU32, AtomicU64, Ordering};
#[derive(Debug)]
pub struct AtomicDist {
bits: AtomicU32,
}
impl AtomicDist {
#[inline]
pub fn infinity() -> Self {
Self {
bits: AtomicU32::new(f32::INFINITY.to_bits()),
}
}
#[inline]
pub fn new(value: f32) -> Self {
debug_assert!(
value >= 0.0 && !value.is_nan(),
"AtomicDist requires non-negative non-NaN values; got {}",
value
);
Self {
bits: AtomicU32::new(value.to_bits()),
}
}
#[inline]
pub fn store_zero(&self) {
self.bits.store(0u32, Ordering::Relaxed);
}
#[inline]
pub fn load(&self) -> f32 {
f32::from_bits(self.bits.load(Ordering::Relaxed))
}
#[inline]
pub fn relax(&self, new_dist: f32) -> bool {
debug_assert!(
new_dist >= 0.0 && !new_dist.is_nan(),
"AtomicDist::relax requires non-negative non-NaN; got {}",
new_dist
);
let new_bits = new_dist.to_bits();
let mut current_bits = self.bits.load(Ordering::Relaxed);
loop {
if new_bits >= current_bits {
return false;
}
match self.bits.compare_exchange_weak(
current_bits,
new_bits,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return true,
Err(observed) => current_bits = observed,
}
}
}
}
#[derive(Debug)]
pub struct AtomicDistParent {
packed: AtomicU64,
}
#[inline]
fn pack(parent_plus_one: u32, dist_bits: u32) -> u64 {
((parent_plus_one as u64) << 32) | (dist_bits as u64)
}
#[inline]
fn unpack_parent(packed: u64) -> u32 {
(packed >> 32) as u32
}
#[inline]
fn unpack_dist_bits(packed: u64) -> u32 {
(packed & 0xFFFF_FFFF) as u32
}
impl AtomicDistParent {
#[inline]
pub fn infinity() -> Self {
Self {
packed: AtomicU64::new(pack(0, f32::INFINITY.to_bits())),
}
}
#[inline]
pub fn source() -> Self {
Self {
packed: AtomicU64::new(pack(0, 0.0_f32.to_bits())),
}
}
#[inline]
pub fn int_infinity() -> Self {
Self {
packed: AtomicU64::new(pack(0, u32::MAX)),
}
}
#[inline]
pub fn store_source(&self) {
self.packed
.store(pack(0, 0.0_f32.to_bits()), Ordering::Relaxed);
}
#[inline]
pub fn load(&self) -> (u32, f32) {
let p = self.packed.load(Ordering::Relaxed);
(unpack_parent(p), f32::from_bits(unpack_dist_bits(p)))
}
#[inline]
pub fn load_dist(&self) -> f32 {
let p = self.packed.load(Ordering::Relaxed);
f32::from_bits(unpack_dist_bits(p))
}
#[inline]
pub fn relax_with_parent(&self, new_dist: f32, new_parent_idx: u32) -> bool {
debug_assert!(
new_dist >= 0.0 && !new_dist.is_nan(),
"AtomicDistParent::relax_with_parent requires non-negative non-NaN; got {}",
new_dist
);
debug_assert!(
new_parent_idx < u32::MAX,
"parent_idx + 1 would overflow u32"
);
let new_bits = new_dist.to_bits();
let new_packed = pack(new_parent_idx + 1, new_bits);
let mut current_packed = self.packed.load(Ordering::Relaxed);
loop {
let current_dist_bits = unpack_dist_bits(current_packed);
if new_bits >= current_dist_bits {
return false;
}
match self.packed.compare_exchange_weak(
current_packed,
new_packed,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return true,
Err(observed) => current_packed = observed,
}
}
}
#[inline]
pub fn relax_with_parent_int(&self, new_dist: u32, new_parent_idx: u32) -> bool {
debug_assert!(
new_parent_idx < u32::MAX,
"parent_idx + 1 would overflow u32"
);
let new_packed = pack(new_parent_idx + 1, new_dist);
let mut current_packed = self.packed.load(Ordering::Relaxed);
loop {
let current_dist = unpack_dist_bits(current_packed);
if new_dist >= current_dist {
return false;
}
match self.packed.compare_exchange_weak(
current_packed,
new_packed,
Ordering::Relaxed,
Ordering::Relaxed,
) {
Ok(_) => return true,
Err(observed) => current_packed = observed,
}
}
}
#[inline]
pub fn load_dist_int(&self) -> u32 {
unpack_dist_bits(self.packed.load(Ordering::Relaxed))
}
}
pub fn atomic_dist_vec(n: usize) -> Vec<AtomicDist> {
(0..n).map(|_| AtomicDist::infinity()).collect()
}
pub fn atomic_dist_parent_vec(n: usize) -> Vec<AtomicDistParent> {
(0..n).map(|_| AtomicDistParent::infinity()).collect()
}
pub fn atomic_dist_parent_vec_int(n: usize) -> Vec<AtomicDistParent> {
(0..n).map(|_| AtomicDistParent::int_infinity()).collect()
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::thread;
#[test]
fn atomic_dist_starts_at_infinity() {
let d = AtomicDist::infinity();
assert_eq!(d.load(), f32::INFINITY);
}
#[test]
fn atomic_dist_relax_smaller_succeeds() {
let d = AtomicDist::infinity();
assert!(d.relax(3.5));
assert_eq!(d.load(), 3.5);
}
#[test]
fn atomic_dist_relax_larger_fails() {
let d = AtomicDist::new(3.5);
assert!(!d.relax(10.0));
assert_eq!(d.load(), 3.5);
}
#[test]
fn atomic_dist_relax_equal_fails() {
let d = AtomicDist::new(3.5);
assert!(!d.relax(3.5));
}
#[test]
fn atomic_dist_relax_zero_against_infinity() {
let d = AtomicDist::infinity();
assert!(d.relax(0.0));
assert_eq!(d.load(), 0.0);
}
#[test]
fn atomic_dist_concurrent_relax_keeps_minimum() {
let d = Arc::new(AtomicDist::infinity());
let values: Vec<f32> = (1..=16).map(|i| i as f32).collect();
let handles: Vec<_> = values
.iter()
.map(|&v| {
let d = Arc::clone(&d);
thread::spawn(move || d.relax(v))
})
.collect();
for h in handles {
h.join().unwrap();
}
assert_eq!(d.load(), 1.0, "Concurrent relax must converge to minimum");
}
#[test]
fn atomic_dist_parent_starts_at_infinity_no_parent() {
let dp = AtomicDistParent::infinity();
let (p, d) = dp.load();
assert_eq!(p, 0);
assert_eq!(d, f32::INFINITY);
}
#[test]
fn atomic_dist_parent_source_starts_at_zero_no_parent() {
let dp = AtomicDistParent::source();
let (p, d) = dp.load();
assert_eq!(p, 0);
assert_eq!(d, 0.0);
}
#[test]
fn atomic_dist_parent_relax_with_parent_smaller_succeeds() {
let dp = AtomicDistParent::infinity();
assert!(dp.relax_with_parent(3.5, 42));
let (p, d) = dp.load();
assert_eq!(p, 43, "parent stored with +1 sentinel");
assert_eq!(d, 3.5);
}
#[test]
fn atomic_dist_parent_relax_with_parent_larger_fails() {
let dp = AtomicDistParent::infinity();
assert!(dp.relax_with_parent(3.5, 42));
assert!(!dp.relax_with_parent(10.0, 99));
let (p, d) = dp.load();
assert_eq!(p, 43, "parent unchanged after failed relax");
assert_eq!(d, 3.5);
}
#[test]
fn atomic_dist_parent_concurrent_relax_keeps_minimum_pair() {
let dp = Arc::new(AtomicDistParent::infinity());
let handles: Vec<_> = (1..=16u32)
.map(|i| {
let dp = Arc::clone(&dp);
thread::spawn(move || dp.relax_with_parent(i as f32, i * 100))
})
.collect();
for h in handles {
h.join().unwrap();
}
let (p, d) = dp.load();
assert_eq!(d, 1.0);
assert_eq!(p, 101, "parent must match the winning relax");
}
#[test]
fn atomic_dist_parent_load_dist_matches_load() {
let dp = AtomicDistParent::infinity();
dp.relax_with_parent(7.25, 1234);
let (_, d_full) = dp.load();
let d_fast = dp.load_dist();
assert_eq!(d_full, d_fast);
}
#[test]
fn atomic_dist_vec_initializes_to_infinity() {
let v = atomic_dist_vec(10);
for d in &v {
assert_eq!(d.load(), f32::INFINITY);
}
}
#[test]
fn atomic_dist_parent_vec_initializes_to_infinity_no_parent() {
let v = atomic_dist_parent_vec(10);
for dp in &v {
assert_eq!(dp.load(), (0, f32::INFINITY));
}
}
#[test]
fn atomic_dist_parent_store_source_overrides_infinity() {
let dp = AtomicDistParent::infinity();
dp.store_source();
let (p, d) = dp.load();
assert_eq!(p, 0);
assert_eq!(d, 0.0);
}
#[test]
fn atomic_dist_store_zero_overrides_infinity() {
let d = AtomicDist::infinity();
d.store_zero();
assert_eq!(d.load(), 0.0);
}
#[test]
fn atomic_dist_parent_int_infinity_sentinel() {
let dp = AtomicDistParent::int_infinity();
assert_eq!(dp.load_dist_int(), u32::MAX);
assert_eq!(dp.load().0, 0, "no parent at int-infinity");
}
#[test]
fn atomic_dist_parent_relax_int_smaller_succeeds() {
let dp = AtomicDistParent::int_infinity();
assert!(dp.relax_with_parent_int(100, 42));
assert_eq!(dp.load_dist_int(), 100);
assert_eq!(dp.load().0, 43, "parent stored with +1 sentinel");
}
#[test]
fn atomic_dist_parent_relax_int_larger_and_equal_fail() {
let dp = AtomicDistParent::int_infinity();
assert!(dp.relax_with_parent_int(100, 42));
assert!(!dp.relax_with_parent_int(200, 7), "larger must not relax");
assert!(!dp.relax_with_parent_int(100, 7), "equal must not relax");
assert_eq!(dp.load_dist_int(), 100);
assert_eq!(dp.load().0, 43, "parent unchanged after failed relax");
}
#[test]
fn atomic_dist_parent_relax_int_concurrent_keeps_minimum() {
let dp = Arc::new(AtomicDistParent::int_infinity());
let handles: Vec<_> = (1..=16u32)
.map(|i| {
let dp = Arc::clone(&dp);
thread::spawn(move || dp.relax_with_parent_int(i * 10, i * 100))
})
.collect();
for h in handles {
h.join().unwrap();
}
assert_eq!(dp.load_dist_int(), 10);
assert_eq!(dp.load().0, 100 + 1, "parent must match the winning relax");
}
#[test]
fn atomic_dist_parent_store_source_zeroes_int_distance() {
let dp = AtomicDistParent::int_infinity();
dp.store_source();
assert_eq!(dp.load_dist_int(), 0);
assert_eq!(dp.load().0, 0);
}
#[test]
fn atomic_dist_parent_vec_int_initializes_to_sentinel() {
let v = atomic_dist_parent_vec_int(8);
for dp in &v {
assert_eq!(dp.load_dist_int(), u32::MAX);
assert_eq!(dp.load().0, 0);
}
}
#[test]
fn pack_unpack_roundtrip() {
let cases = [
(0, 0u32),
(1, 0u32),
(42, 0x40000000u32), (u32::MAX - 1, f32::INFINITY.to_bits()),
];
for &(parent, dist_bits) in &cases {
let packed = pack(parent, dist_bits);
assert_eq!(unpack_parent(packed), parent);
assert_eq!(unpack_dist_bits(packed), dist_bits);
}
}
}