physdes/
dllink.rs

1//! Doubly-linked link node for polygon decomposition algorithms.
2//!
3//! Provides a low-level intrusive doubly-linked list node (`Dllink<T>`)
4//! used internally by rectilinear polygon cut and hull algorithms.
5
6use std::marker::PhantomData;
7
8/// A doubly-linked list node.
9///
10/// Each node holds a value of type `T` and pointers to the next and previous
11/// nodes in the list. A freshly created node is "locked" (points to itself),
12/// acting as a sentinel. Call `lock()` / `is_locked()` to manage this state.
13///
14/// # Safety
15///
16/// This type uses raw pointers internally and is neither `Send` nor `Sync`.
17/// The caller must ensure that all nodes outlive any pointers referencing them.
18#[repr(C)]
19pub struct Dllink<T> {
20    /// Pointer to the next node.
21    pub next: *mut Dllink<T>,
22    /// Pointer to the previous node.
23    pub prev: *mut Dllink<T>,
24    /// Stored data value.
25    pub data: T,
26    /// Marker to opt out of auto-Send/Sync.
27    _marker: PhantomData<*mut T>,
28}
29
30// SAFETY: Dllink is designed for single-threaded internal use.
31// We explicitly opt out of Send/Sync because of raw pointer fields.
32// However, T itself should still be Send/Sync if possible.
33// The auto-derived impls are correct: raw pointers make it !Send/!Sync by default.
34
35impl<T> Dllink<T> {
36    /// Creates a new locked (detached) `Dllink` with the given data.
37    ///
38    /// A locked node has null pointers and is not part of any list.
39    /// Use `new_linked` for an alias, or manually set `next`/`prev` to
40    /// link the node into a list.
41    #[inline]
42    pub const fn new(data: T) -> Self {
43        Dllink {
44            next: std::ptr::null_mut(),
45            prev: std::ptr::null_mut(),
46            data,
47            _marker: PhantomData,
48        }
49    }
50
51    /// Creates a new locked (detached) `Dllink`.
52    #[inline]
53    pub fn new_linked(data: T) -> Self {
54        Dllink {
55            next: std::ptr::null_mut(),
56            prev: std::ptr::null_mut(),
57            data,
58            _marker: PhantomData,
59        }
60    }
61
62    /// Locks the node (nulls pointers). After locking, the node is not
63    /// part of any list.
64    #[inline]
65    pub fn lock(&mut self) {
66        self.next = std::ptr::null_mut();
67        self.prev = std::ptr::null_mut();
68    }
69
70    /// Returns `true` if the node is locked (null pointers, not in a list).
71    #[inline]
72    pub fn is_locked(&self) -> bool {
73        self.next.is_null() && self.prev.is_null()
74    }
75
76    /// Detaches this node from its containing list.
77    ///
78    /// Panics if the node is locked (not in a list).
79    #[inline]
80    pub fn detach(&mut self) {
81        assert!(!self.is_locked(), "cannot detach a locked node");
82        let n = self.next;
83        let p = self.prev;
84        unsafe {
85            (*p).next = n;
86            (*n).prev = p;
87        }
88        self.lock();
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn test_new_locked() {
98        let node = Dllink::new_linked(42);
99        assert!(node.is_locked());
100        assert_eq!(node.data, 42);
101    }
102
103    #[test]
104    fn test_lock_unlock() {
105        let mut n1 = Dllink::new_linked(1);
106        let mut n2 = Dllink::new_linked(2);
107
108        // Link n1 -> n2 circularly
109        n1.next = &mut n2;
110        n2.prev = &mut n1;
111
112        assert!(!n1.is_locked());
113        assert!(!n2.is_locked());
114
115        n1.lock();
116        assert!(n1.is_locked());
117    }
118
119    #[test]
120    fn test_detach() {
121        let mut n1 = Dllink::new_linked(1);
122        let mut n2 = Dllink::new_linked(2);
123        let mut n3 = Dllink::new_linked(3);
124
125        // Set up circular list: n1 -> n2 -> n3 -> n1
126        let p1: *mut Dllink<i32> = &mut n1;
127        let p2: *mut Dllink<i32> = &mut n2;
128        let p3: *mut Dllink<i32> = &mut n3;
129
130        n1.next = p2;
131        n1.prev = p3;
132        n2.next = p3;
133        n2.prev = p1;
134        n3.next = p1;
135        n3.prev = p2;
136
137        // Detach n2
138        n2.detach();
139        assert!(n2.is_locked());
140
141        // Now n1.next should be n3
142        assert_eq!(unsafe { (*n1.next).data }, 3);
143        // And n3.prev should be n1
144        assert_eq!(unsafe { (*n3.prev).data }, 1);
145    }
146
147    #[test]
148    #[should_panic(expected = "cannot detach a locked node")]
149    fn test_detach_locked_panics() {
150        let mut node = Dllink::new_linked(99);
151        node.detach();
152    }
153}
physdes/dllink.rs

physdes/
dllink.rs
