zsh/
linklist.rs

1//! Linked list implementation for zshrs
2//!
3//! Direct port from zsh/Src/linklist.c
4//!
5//! Provides a doubly-linked list with operations matching zsh's LinkList API.
6
7use std::marker::PhantomData;
8use std::ptr::NonNull;
9
10/// A node in the linked list
11pub struct LinkNode<T> {
12    pub data: T,
13    next: Option<NonNull<LinkNode<T>>>,
14    prev: Option<NonNull<LinkNode<T>>>,
15}
16
17/// A doubly-linked list
18pub struct LinkList<T> {
19    head: Option<NonNull<LinkNode<T>>>,
20    tail: Option<NonNull<LinkNode<T>>>,
21    len: usize,
22    _marker: PhantomData<Box<LinkNode<T>>>,
23}
24
25impl<T> Default for LinkList<T> {
26    fn default() -> Self {
27        Self::new()
28    }
29}
30
31impl<T> LinkList<T> {
32    /// Create a new empty linked list
33    pub fn new() -> Self {
34        LinkList {
35            head: None,
36            tail: None,
37            len: 0,
38            _marker: PhantomData,
39        }
40    }
41
42    /// Check if the list is empty
43    pub fn is_empty(&self) -> bool {
44        self.head.is_none()
45    }
46
47    /// Get the length of the list
48    pub fn len(&self) -> usize {
49        self.len
50    }
51
52    /// Add an element to the front of the list
53    pub fn push_front(&mut self, data: T) {
54        let new_node = Box::new(LinkNode {
55            data,
56            next: self.head,
57            prev: None,
58        });
59        let new_node = NonNull::new(Box::into_raw(new_node));
60
61        match self.head {
62            Some(old_head) => unsafe {
63                (*old_head.as_ptr()).prev = new_node;
64            },
65            None => self.tail = new_node,
66        }
67
68        self.head = new_node;
69        self.len += 1;
70    }
71
72    /// Add an element to the back of the list
73    pub fn push_back(&mut self, data: T) {
74        let new_node = Box::new(LinkNode {
75            data,
76            next: None,
77            prev: self.tail,
78        });
79        let new_node = NonNull::new(Box::into_raw(new_node));
80
81        match self.tail {
82            Some(old_tail) => unsafe {
83                (*old_tail.as_ptr()).next = new_node;
84            },
85            None => self.head = new_node,
86        }
87
88        self.tail = new_node;
89        self.len += 1;
90    }
91
92    /// Remove and return the first element
93    pub fn pop_front(&mut self) -> Option<T> {
94        self.head.map(|node| unsafe {
95            let node = Box::from_raw(node.as_ptr());
96            self.head = node.next;
97
98            match self.head {
99                Some(new_head) => (*new_head.as_ptr()).prev = None,
100                None => self.tail = None,
101            }
102
103            self.len -= 1;
104            node.data
105        })
106    }
107
108    /// Remove and return the last element
109    pub fn pop_back(&mut self) -> Option<T> {
110        self.tail.map(|node| unsafe {
111            let node = Box::from_raw(node.as_ptr());
112            self.tail = node.prev;
113
114            match self.tail {
115                Some(new_tail) => (*new_tail.as_ptr()).next = None,
116                None => self.head = None,
117            }
118
119            self.len -= 1;
120            node.data
121        })
122    }
123
124    /// Get a reference to the first element
125    pub fn front(&self) -> Option<&T> {
126        self.head.map(|node| unsafe { &(*node.as_ptr()).data })
127    }
128
129    /// Get a mutable reference to the first element
130    pub fn front_mut(&mut self) -> Option<&mut T> {
131        self.head.map(|node| unsafe { &mut (*node.as_ptr()).data })
132    }
133
134    /// Get a reference to the last element
135    pub fn back(&self) -> Option<&T> {
136        self.tail.map(|node| unsafe { &(*node.as_ptr()).data })
137    }
138
139    /// Get a mutable reference to the last element
140    pub fn back_mut(&mut self) -> Option<&mut T> {
141        self.tail.map(|node| unsafe { &mut (*node.as_ptr()).data })
142    }
143
144    /// Create an iterator over references
145    pub fn iter(&self) -> Iter<'_, T> {
146        Iter {
147            current: self.head,
148            _marker: PhantomData,
149        }
150    }
151
152    /// Create an iterator over mutable references
153    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
154        IterMut {
155            current: self.head,
156            _marker: PhantomData,
157        }
158    }
159
160    /// Append another list to the end of this one
161    pub fn append(&mut self, other: &mut LinkList<T>) {
162        if other.is_empty() {
163            return;
164        }
165
166        match self.tail {
167            Some(tail) => unsafe {
168                (*tail.as_ptr()).next = other.head;
169                if let Some(other_head) = other.head {
170                    (*other_head.as_ptr()).prev = Some(tail);
171                }
172            },
173            None => {
174                self.head = other.head;
175            }
176        }
177
178        self.tail = other.tail;
179        self.len += other.len;
180
181        other.head = None;
182        other.tail = None;
183        other.len = 0;
184    }
185
186    /// Convert to a Vec
187    pub fn to_vec(self) -> Vec<T> {
188        self.into_iter().collect()
189    }
190
191    /// Clear the list
192    pub fn clear(&mut self) {
193        while self.pop_front().is_some() {}
194    }
195}
196
197impl<T> Drop for LinkList<T> {
198    fn drop(&mut self) {
199        self.clear();
200    }
201}
202
203impl<T> FromIterator<T> for LinkList<T> {
204    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
205        let mut list = LinkList::new();
206        for item in iter {
207            list.push_back(item);
208        }
209        list
210    }
211}
212
213impl<T> IntoIterator for LinkList<T> {
214    type Item = T;
215    type IntoIter = IntoIter<T>;
216
217    fn into_iter(self) -> IntoIter<T> {
218        IntoIter { list: self }
219    }
220}
221
222impl<'a, T> IntoIterator for &'a LinkList<T> {
223    type Item = &'a T;
224    type IntoIter = Iter<'a, T>;
225
226    fn into_iter(self) -> Iter<'a, T> {
227        self.iter()
228    }
229}
230
231/// Iterator over references
232pub struct Iter<'a, T> {
233    current: Option<NonNull<LinkNode<T>>>,
234    _marker: PhantomData<&'a LinkNode<T>>,
235}
236
237impl<'a, T> Iterator for Iter<'a, T> {
238    type Item = &'a T;
239
240    fn next(&mut self) -> Option<Self::Item> {
241        self.current.map(|node| unsafe {
242            let node_ref = node.as_ref();
243            self.current = node_ref.next;
244            &node_ref.data
245        })
246    }
247}
248
249/// Iterator over mutable references
250pub struct IterMut<'a, T> {
251    current: Option<NonNull<LinkNode<T>>>,
252    _marker: PhantomData<&'a mut LinkNode<T>>,
253}
254
255impl<'a, T> Iterator for IterMut<'a, T> {
256    type Item = &'a mut T;
257
258    fn next(&mut self) -> Option<Self::Item> {
259        self.current.map(|node| unsafe {
260            let node_ref = &mut *node.as_ptr();
261            self.current = node_ref.next;
262            &mut node_ref.data
263        })
264    }
265}
266
267/// Owning iterator
268pub struct IntoIter<T> {
269    list: LinkList<T>,
270}
271
272impl<T> Iterator for IntoIter<T> {
273    type Item = T;
274
275    fn next(&mut self) -> Option<Self::Item> {
276        self.list.pop_front()
277    }
278}
279
280impl<T> DoubleEndedIterator for IntoIter<T> {
281    fn next_back(&mut self) -> Option<Self::Item> {
282        self.list.pop_back()
283    }
284}
285
286/// Convert a linked list of strings to a Vec
287pub fn linklist_to_vec(list: &LinkList<String>) -> Vec<String> {
288    list.iter().cloned().collect()
289}
290
291/// Convert a Vec to a linked list
292pub fn vec_to_linklist<T>(vec: Vec<T>) -> LinkList<T> {
293    vec.into_iter().collect()
294}
295
296#[cfg(test)]
297mod tests {
298    use super::*;
299
300    #[test]
301    fn test_new_list() {
302        let list: LinkList<i32> = LinkList::new();
303        assert!(list.is_empty());
304        assert_eq!(list.len(), 0);
305    }
306
307    #[test]
308    fn test_push_front() {
309        let mut list = LinkList::new();
310        list.push_front(1);
311        list.push_front(2);
312        list.push_front(3);
313
314        assert_eq!(list.len(), 3);
315        assert_eq!(list.front(), Some(&3));
316        assert_eq!(list.back(), Some(&1));
317    }
318
319    #[test]
320    fn test_push_back() {
321        let mut list = LinkList::new();
322        list.push_back(1);
323        list.push_back(2);
324        list.push_back(3);
325
326        assert_eq!(list.len(), 3);
327        assert_eq!(list.front(), Some(&1));
328        assert_eq!(list.back(), Some(&3));
329    }
330
331    #[test]
332    fn test_pop_front() {
333        let mut list = LinkList::new();
334        list.push_back(1);
335        list.push_back(2);
336        list.push_back(3);
337
338        assert_eq!(list.pop_front(), Some(1));
339        assert_eq!(list.pop_front(), Some(2));
340        assert_eq!(list.pop_front(), Some(3));
341        assert_eq!(list.pop_front(), None);
342    }
343
344    #[test]
345    fn test_pop_back() {
346        let mut list = LinkList::new();
347        list.push_back(1);
348        list.push_back(2);
349        list.push_back(3);
350
351        assert_eq!(list.pop_back(), Some(3));
352        assert_eq!(list.pop_back(), Some(2));
353        assert_eq!(list.pop_back(), Some(1));
354        assert_eq!(list.pop_back(), None);
355    }
356
357    #[test]
358    fn test_iter() {
359        let mut list = LinkList::new();
360        list.push_back(1);
361        list.push_back(2);
362        list.push_back(3);
363
364        let vec: Vec<_> = list.iter().copied().collect();
365        assert_eq!(vec, vec![1, 2, 3]);
366    }
367
368    #[test]
369    fn test_into_iter() {
370        let mut list = LinkList::new();
371        list.push_back(1);
372        list.push_back(2);
373        list.push_back(3);
374
375        let vec: Vec<_> = list.into_iter().collect();
376        assert_eq!(vec, vec![1, 2, 3]);
377    }
378
379    #[test]
380    fn test_append() {
381        let mut list1 = LinkList::new();
382        list1.push_back(1);
383        list1.push_back(2);
384
385        let mut list2 = LinkList::new();
386        list2.push_back(3);
387        list2.push_back(4);
388
389        list1.append(&mut list2);
390
391        assert_eq!(list1.len(), 4);
392        assert!(list2.is_empty());
393
394        let vec: Vec<_> = list1.into_iter().collect();
395        assert_eq!(vec, vec![1, 2, 3, 4]);
396    }
397
398    #[test]
399    fn test_from_iter() {
400        let list: LinkList<i32> = vec![1, 2, 3].into_iter().collect();
401        assert_eq!(list.len(), 3);
402
403        let vec: Vec<_> = list.into_iter().collect();
404        assert_eq!(vec, vec![1, 2, 3]);
405    }
406
407    #[test]
408    fn test_clear() {
409        let mut list = LinkList::new();
410        list.push_back(1);
411        list.push_back(2);
412        list.push_back(3);
413
414        list.clear();
415        assert!(list.is_empty());
416        assert_eq!(list.len(), 0);
417    }
418}
zsh/linklist.rs

zsh/
linklist.rs
