c_linked_list/
lib.rs

1//! This crate provides utilities for working with NULL-terminated linked lists provided
2//! by C code. Suppose you call a foreign function which returns either NULL or a pointer
3//! to a node of the following C type.
4//!
5//! ```c
6//! struct LinkedListNode {
7//!     int value;
8//!     struct LinkedListNode *next;
9//! };
10//! ```
11//!
12//! You can use this library to wrap the C linked list in a rust type, allowing
13//! operations such as iteration to be performed on it.
14//!
15//! ```ignore
16//! let some_c_linked_list = foreign_function_which_returns_c_linked_list();
17//! let rust_linked_list = unsafe { CLinkedListMut::from_ptr(some_c_linked_list, |n| n.next) };
18//! for (i, node) in rust_linked_list.iter().enumerate() {
19//!     println!("some_c_linked_list[{}] == {}", i, node.value);
20//! }
21//! ```
22
23use std::fmt;
24
25/// Wraps a C linked list comprised of mutable pointers between nodes.
26pub struct CLinkedListMut<T, N: Fn(&T) -> *mut T> {
27    head: *mut T,
28    next: N,
29}
30
31/// Iterator over a `CLinkedListMut`. Returns references to the nodes of the list.
32pub struct CLinkedListMutIter<'a, T: 'a, N: Fn(&T) -> *mut T + 'a> {
33    cll: &'a CLinkedListMut<T, N>,
34    prev: Option<&'a T>,
35}
36
37/// Iterator over a `CLinkedListMut`. Returns mutable references to the nodes of the list.
38pub struct CLinkedListMutIterMut<'a, T: 'a, N: Fn(&T) -> *mut T + 'a> {
39    cll: &'a mut CLinkedListMut<T, N>,
40    prev: Option<&'a mut T>,
41}
42
43impl<'a, T: 'a, N: Fn(&T) -> *mut T + 'a> CLinkedListMut<T, N> {
44    /// Construct a `CLinkedListMut` by wrapping a C linked list. `head` points to the head element
45    /// of the list or is NULL for a list of length 0. `next` is a function that takes a node and
46    /// returns a pointer to the next element.
47    ///
48    /// # Example
49    ///
50    /// To wrap this C type.
51    ///
52    /// ```c
53    /// struct LinkedListNode {
54    ///     int value;
55    ///     struct LinkedListNode *next;
56    /// };
57    /// ```
58    ///
59    /// Call this function as `CLinkedListMut::from_ptr(ptr_to_head, |n| n.next)`.
60    ///
61    /// # Unsafety
62    ///
63    /// This function is unsafe because it is up to the caller to ensure that `head` is valid.
64    pub unsafe fn from_ptr(head: *mut T, next: N) -> CLinkedListMut<T, N> {
65        CLinkedListMut {
66            head: head,
67            next: next,
68        }
69    }
70
71    /// Iterate over the linked list, returning references to the nodes of the list.
72    pub fn iter(&'a self) -> CLinkedListMutIter<'a, T, N> {
73        CLinkedListMutIter {
74            cll: self,
75            prev: None,
76        }
77    }
78
79    /// Iterate over the linked list, returning mutable references to the nodes of the list.
80    pub fn iter_mut(&'a mut self) -> CLinkedListMutIterMut<'a, T, N> {
81        CLinkedListMutIterMut {
82            cll: self,
83            prev: None,
84        }
85    }
86
87    /// Returns `true` if the list is empty.
88    pub fn is_empty(&self) -> bool {
89        self.head.is_null()
90    }
91
92    /// Calculates the length of the list. This is an `O(n)` operation.
93    pub fn len(&self) -> usize {
94        let mut node = self.head;
95        let mut ret = 0;
96        while !node.is_null() {
97            node = unsafe { (self.next)(&mut *node) };
98            ret += 1;
99        }
100        ret
101    }
102
103    /// Provides a reference to the front element in the list, or `None` if the list is empty.
104    pub fn front(&self) -> Option<&T> {
105        if self.head.is_null() {
106            None
107        }
108        else {
109            unsafe { Some(&*self.head) }
110        }
111    }
112
113    /// Provides a mutable reference to the front element in the list, or `None` if the list is
114    /// empty.
115    pub fn front_mut(&self) -> Option<&mut T> {
116        if self.head.is_null() {
117            None
118        }
119        else {
120            unsafe { Some(&mut *self.head) }
121        }
122    }
123}
124
125impl<'a, T: 'a, N: Fn(&T) -> *mut T + 'a> IntoIterator for &'a CLinkedListMut<T, N> {
126    type Item = &'a T;
127    type IntoIter = CLinkedListMutIter<'a, T, N>;
128
129    fn into_iter(self) -> CLinkedListMutIter<'a, T, N> {
130        self.iter()
131    }
132}
133
134impl<'a, T: 'a, N: Fn(&T) -> *mut T + 'a> IntoIterator for &'a mut CLinkedListMut<T, N> {
135    type Item = &'a mut T;
136    type IntoIter = CLinkedListMutIterMut<'a, T, N>;
137
138    fn into_iter(mut self) -> CLinkedListMutIterMut<'a, T, N> {
139        self.iter_mut()
140    }
141}
142
143impl<'a, T: 'a, N: Fn(&T) -> *mut T + 'a> Iterator for CLinkedListMutIter<'a, T, N> {
144    type Item = &'a T;
145
146    #[allow(unsafe_code)]
147    fn next(&mut self) -> Option<&'a T> {
148        // Note: implemented this way so that if the user changes the next pointer during iteration
149        // it will iterate to the correct next element.
150        let next = match self.prev {
151            None => self.cll.head,
152            Some(ref mut prev) => (self.cll.next)(*prev),
153        };
154        if next.is_null() {
155            None
156        }
157        else {
158            self.prev = Some(unsafe { &*next });
159            Some(unsafe { &*next })
160        }
161    }
162}
163
164impl<'a, T: 'a, N: Fn(&T) -> *mut T + 'a> Iterator for CLinkedListMutIterMut<'a, T, N> {
165    type Item = &'a mut T;
166
167    #[allow(unsafe_code)]
168    fn next(&mut self) -> Option<&'a mut T> {
169        // Note: implemented this way so that if the user changes the next pointer during iteration
170        // it will iterate to the correct next element.
171        let next = match self.prev {
172            None => self.cll.head,
173            Some(ref mut prev) => (self.cll.next)(*prev),
174        };
175        if next.is_null() {
176            None
177        }
178        else {
179            self.prev = Some(unsafe { &mut *next });
180            Some(unsafe { &mut *next })
181        }
182    }
183}
184
185impl<'a, T: fmt::Debug + 'a, N: Fn(&T) -> *mut T + 'a> fmt::Debug for CLinkedListMut<T, N> {
186    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
187        f.debug_list().entries(self.iter()).finish()
188    }
189}
190
191/// Wraps a C linked list comprised of const pointers between nodes.
192pub struct CLinkedListConst<T, N: Fn(&T) -> *const T> {
193    head: *const T,
194    next: N,
195}
196
197/// Iterator over a `CLinkedListConst`. Returns immutable references to the nodes of the list.
198pub struct CLinkedListConstIter<'a, T: 'a, N: Fn(&T) -> *const T + 'a> {
199    cll: &'a CLinkedListConst<T, N>,
200    prev: Option<&'a T>,
201}
202
203impl<'a, T: 'a, N: Fn(&T) -> *const T + 'a> CLinkedListConst<T, N> {
204    /// Construct a `CLinkedListConst` by wrapping a C linked list. `head` points to the head
205    /// element of the list or is NULL for a list of length 0. `next` is a function that takes a
206    /// node and returns a pointer to the next element.
207    ///
208    /// # Example
209    ///
210    /// To wrap this C type.
211    ///
212    /// ```c
213    /// struct LinkedListNode {
214    ///     int value;
215    ///     const struct LinkedListNode *next;
216    /// };
217    /// ```
218    ///
219    /// Call this function as `CLinkedListConst::from_ptr(ptr_to_head, |n| n.next)`.
220    ///
221    /// # Unsafety
222    ///
223    /// This function is unsafe because it is up to the caller to ensure that `head` is valid.
224    pub unsafe fn from_ptr(head: *const T, next: N) -> CLinkedListConst<T, N> {
225        CLinkedListConst {
226            head: head,
227            next: next,
228        }
229    }
230
231    /// Iterate over the linked list, returning immutable references to the nodes of the list.
232    pub fn iter(&'a self) -> CLinkedListConstIter<'a, T, N> {
233        CLinkedListConstIter {
234            cll: self,
235            prev: None,
236        }
237    }
238
239    /// Returns `true` if the list is empty.
240    pub fn is_empty(&self) -> bool {
241        self.head.is_null()
242    }
243
244    /// Calculates the length of the list. This is an `O(n)` operation.
245    pub fn len(&self) -> usize {
246        let mut node = self.head;
247        let mut ret = 0;
248        while !node.is_null() {
249            node = unsafe { (self.next)(&*node) };
250            ret += 1;
251        }
252        ret
253    }
254
255    /// Provides a reference to the front element in the list, or `None` if the list is empty.
256    pub fn front(&self) -> Option<&T> {
257        if self.head.is_null() {
258            None
259        }
260        else {
261            unsafe { Some(&*self.head) }
262        }
263    }
264}
265
266impl<'a, T: 'a, N: Fn(&T) -> *const T + 'a> IntoIterator for &'a CLinkedListConst<T, N> {
267    type Item = &'a T;
268    type IntoIter = CLinkedListConstIter<'a, T, N>;
269
270    fn into_iter(self) -> CLinkedListConstIter<'a, T, N> {
271        self.iter()
272    }
273}
274
275impl<'a, T: 'a, N: Fn(&T) -> *const T + 'a> Iterator for CLinkedListConstIter<'a, T, N> {
276    type Item = &'a T;
277
278    #[allow(unsafe_code)]
279    fn next(&mut self) -> Option<&'a T> {
280        // Note: implemented this way so that if the user changes the next pointer during iteration
281        // it will iterate to the correct next element.
282        let next = match self.prev {
283            None => self.cll.head,
284            Some(prev) => (self.cll.next)(prev),
285        };
286        if next.is_null() {
287            None
288        }
289        else {
290            self.prev = Some(unsafe { &*next });
291            self.prev
292        }
293    }
294}
295
296impl<'a, T: fmt::Debug + 'a, N: Fn(&T) -> *const T + 'a> fmt::Debug for CLinkedListConst<T, N> {
297    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
298        f.debug_list().entries(self.iter()).finish()
299    }
300}
301
302#[cfg(test)]
303mod tests{
304    use super::*;
305
306    use std;
307
308    struct TestNodeConst {
309        val: u32,
310        next: *const TestNodeConst,
311    }
312
313    fn make_list_const() -> *const TestNodeConst {
314        fn malloc<T>(t: T) -> *const T {
315            Box::into_raw(Box::new(t)) as *const T
316        }
317
318        malloc(TestNodeConst {
319            val: 0,
320            next: malloc(TestNodeConst {
321                val: 1,
322                next: malloc(TestNodeConst {
323                    val: 2,
324                    next: std::ptr::null(),
325                }),
326            }),
327        })
328    }
329
330    #[test]
331    fn test_const() {
332        let ptr: *const TestNodeConst = std::ptr::null();
333        let list = unsafe { CLinkedListConst::from_ptr(ptr, |n| n.next) };
334        let vec: Vec<u32> = list.iter().map(|n| n.val).collect();
335        assert_eq!(vec, &[]);
336        assert_eq!(list.len(), 0);
337        assert!(list.is_empty());
338        assert!(list.front().is_none());
339
340        let ptr = make_list_const();
341        let list = unsafe { CLinkedListConst::from_ptr(ptr, |n| n.next) };
342        let vec: Vec<u32> = list.iter().map(|n| n.val).collect();
343        assert_eq!(vec, &[0, 1, 2]);
344        assert_eq!(list.len(), 3);
345        assert!(! list.is_empty());
346        let front = list.front().unwrap();
347        assert_eq!(front.val, 0);
348    }
349
350    struct TestNodeMut {
351        val: u32,
352        next: *mut TestNodeMut,
353    }
354
355    fn make_list_mut() -> *mut TestNodeMut {
356        fn malloc<T>(t: T) -> *mut T {
357            Box::into_raw(Box::new(t))
358        }
359
360        malloc(TestNodeMut {
361            val: 0,
362            next: malloc(TestNodeMut {
363                val: 1,
364                next: malloc(TestNodeMut {
365                    val: 2,
366                    next: std::ptr::null_mut(),
367                }),
368            }),
369        })
370    }
371
372    #[test]
373    fn test_mut() {
374        let ptr: *mut TestNodeMut = std::ptr::null_mut();
375        let list = unsafe { CLinkedListMut::from_ptr(ptr, |n| n.next) };
376        let vec: Vec<u32> = list.iter().map(|n| n.val).collect();
377        assert_eq!(vec, &[]);
378        assert_eq!(list.len(), 0);
379        assert!(list.is_empty());
380        assert!(list.front().is_none());
381
382        let ptr = make_list_mut();
383        let mut list = unsafe { CLinkedListMut::from_ptr(ptr, |n| n.next) };
384        let vec: Vec<u32> = list.iter().map(|n| n.val).collect();
385        assert_eq!(vec, &[0, 1, 2]);
386        assert_eq!(list.len(), 3);
387        assert!(! list.is_empty());
388        {
389            let front = list.front().unwrap();
390            assert_eq!(front.val, 0);
391        }
392
393        for node in list.iter_mut() {
394            node.val += 1;
395        }
396
397        let vec: Vec<u32> = list.iter().map(|n| n.val).collect();
398        assert_eq!(vec, &[1, 2, 3]);
399        assert_eq!(list.len(), 3);
400        assert!(! list.is_empty());
401        let front = list.front().unwrap();
402        assert_eq!(front.val, 1);
403    }
404}
405
406
c_linked_list/lib.rs

c_linked_list/
lib.rs
