nt_list/list/
boxing.rs

1// Copyright 2022 Colin Finck <colin@reactos.org>
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use core::marker::PhantomPinned;
5use core::pin::Pin;
6use core::ptr;
7
8use alloc::boxed::Box;
9use moveit::{new, New};
10
11use super::base::{Iter, IterMut, NtListEntry, NtListHead};
12use super::traits::NtList;
13use crate::traits::{NtBoxedListElement, NtListElement, NtTypedList};
14
15/// A variant of [`NtListHead`] that boxes every element on insertion.
16///
17/// This guarantees ownership and therefore all `NtBoxingListHead` functions can be used without
18/// resorting to `unsafe`.
19/// If you can, use this implementation over [`NtListHead`].
20///
21/// You need to implement the [`NtBoxedListElement`] trait to designate a single list as the boxing one.
22/// This also establishes clear ownership when a single element is part of more than one list.
23///
24/// See the [module-level documentation](crate::list) for more details.
25///
26/// This structure substitutes the [`LIST_ENTRY`] structure of the Windows NT API for the list header.
27///
28/// [`LIST_ENTRY`]: https://docs.microsoft.com/en-us/windows/win32/api/ntdef/ns-ntdef-list_entry
29#[repr(transparent)]
30#[cfg_attr(docsrs, doc(cfg(feature = "alloc")))]
31pub struct NtBoxingListHead<
32    E: NtBoxedListElement<L = L> + NtListElement<L>,
33    L: NtTypedList<T = NtList>,
34>(NtListHead<E, L>);
35
36impl<E, L> NtBoxingListHead<E, L>
37where
38    E: NtBoxedListElement<L = L> + NtListElement<L>,
39    L: NtTypedList<T = NtList>,
40{
41    /// Creates a new doubly linked list that owns all elements.
42    ///
43    /// This function substitutes [`InitializeListHead`] of the Windows NT API.
44    ///
45    /// [`InitializeListHead`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-initializelisthead
46    pub fn new() -> impl New<Output = Self> {
47        new::of(Self(NtListHead {
48            flink: ptr::null_mut(),
49            blink: ptr::null_mut(),
50            pin: PhantomPinned,
51        }))
52        .with(|this| {
53            let this = unsafe { this.get_unchecked_mut() };
54            this.0.flink = (this as *mut Self).cast();
55            this.0.blink = this.0.flink;
56        })
57    }
58
59    /// Moves all elements from `other` to the end of the list.
60    ///
61    /// This reuses all the nodes from `other` and moves them into `self`.
62    /// After this operation, `other` becomes empty.
63    ///
64    /// This operation computes in *O*(*1*) time.
65    pub fn append(self: Pin<&mut Self>, other: Pin<&mut Self>) {
66        unsafe { self.inner_mut().append(other.inner_mut()) }
67    }
68
69    /// Provides a reference to the last element, or `None` if the list is empty.
70    ///
71    /// This operation computes in *O*(*1*) time.
72    pub fn back(self: Pin<&Self>) -> Option<&E> {
73        unsafe { self.inner().back() }
74    }
75
76    /// Provides a mutable reference to the last element, or `None` if the list is empty.
77    ///
78    /// This operation computes in *O*(*1*) time.
79    pub fn back_mut(self: Pin<&mut Self>) -> Option<&mut E> {
80        unsafe { self.inner_mut().back_mut() }
81    }
82
83    /// Removes all elements from the list, deallocating their memory.
84    ///
85    /// Unlike [`NtListHead::clear`], this operation computes in *O*(*n*) time, because it
86    /// needs to traverse all elements to deallocate them.
87    pub fn clear(mut self: Pin<&mut Self>) {
88        let end_marker = self.as_mut().inner_mut().end_marker_mut();
89
90        // Get the link to the first element before it's being reset.
91        let mut current = self.0.flink;
92
93        // Make the list appear empty before deallocating any element.
94        // By doing this here and not at the very end, we guard against the following scenario:
95        //
96        // 1. We deallocate an element.
97        // 2. The `Drop` handler of that element is called and panics.
98        // 3. Consequently, the `Drop` handler of `NtBoxingListHead` is called and removes all elements.
99        // 4. While removing elements, the just dropped element is dropped again.
100        //
101        // By clearing the list at the beginning, the `Drop` handler of `NtBoxingListHead` won't find any
102        // elements, and thereby it won't drop any elements.
103        self.inner_mut().clear();
104
105        // Traverse the list in the old-fashioned way and deallocate each element.
106        while current != end_marker {
107            unsafe {
108                let element = NtListEntry::containing_record_mut(current);
109                current = (*current).flink;
110                drop(Box::from_raw(element));
111            }
112        }
113    }
114
115    /// Provides a reference to the first element, or `None` if the list is empty.
116    ///
117    /// This operation computes in *O*(*1*) time.
118    pub fn front(self: Pin<&Self>) -> Option<&E> {
119        unsafe { self.inner().front() }
120    }
121
122    /// Provides a mutable reference to the first element, or `None` if the list is empty.
123    ///
124    /// This operation computes in *O*(*1*) time.
125    pub fn front_mut(self: Pin<&mut Self>) -> Option<&mut E> {
126        unsafe { self.inner_mut().front_mut() }
127    }
128
129    fn inner(self: Pin<&Self>) -> Pin<&NtListHead<E, L>> {
130        unsafe { Pin::new_unchecked(&self.get_ref().0) }
131    }
132
133    fn inner_mut(self: Pin<&mut Self>) -> Pin<&mut NtListHead<E, L>> {
134        unsafe { Pin::new_unchecked(&mut self.get_unchecked_mut().0) }
135    }
136
137    /// Returns `true` if the list is empty.
138    ///
139    /// This function substitutes [`IsListEmpty`] of the Windows NT API.
140    ///
141    /// This operation computes in *O*(*1*) time.
142    ///
143    /// [`IsListEmpty`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-islistempty
144    pub fn is_empty(self: Pin<&Self>) -> bool {
145        self.inner().is_empty()
146    }
147
148    /// Returns an iterator yielding references to each element of the list.
149    pub fn iter(self: Pin<&Self>) -> Iter<E, L> {
150        unsafe { self.inner().iter() }
151    }
152
153    /// Returns an iterator yielding mutable references to each element of the list.
154    pub fn iter_mut(self: Pin<&mut Self>) -> IterMut<E, L> {
155        unsafe { self.inner_mut().iter_mut() }
156    }
157
158    /// Counts all elements and returns the length of the list.
159    ///
160    /// This operation computes in *O*(*n*) time.
161    pub fn len(self: Pin<&Self>) -> usize {
162        unsafe { self.inner().len() }
163    }
164
165    /// Removes the last element from the list and returns it, or `None` if the list is empty.
166    ///
167    /// This function substitutes [`RemoveTailList`] of the Windows NT API.
168    ///
169    /// This operation computes in *O*(*1*) time.
170    ///
171    /// [`RemoveTailList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-removetaillist
172    pub fn pop_back(self: Pin<&mut Self>) -> Option<Box<E>> {
173        unsafe {
174            self.inner_mut()
175                .pop_back()
176                .map(|element| Box::from_raw(element))
177        }
178    }
179
180    /// Removes the first element from the list and returns it, or `None` if the list is empty.
181    ///
182    /// This function substitutes [`RemoveHeadList`] of the Windows NT API.
183    ///
184    /// This operation computes in *O*(*1*) time.
185    ///
186    /// [`RemoveHeadList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-removeheadlist
187    pub fn pop_front(self: Pin<&mut Self>) -> Option<Box<E>> {
188        unsafe {
189            self.inner_mut()
190                .pop_front()
191                .map(|element| Box::from_raw(element))
192        }
193    }
194
195    /// Appends an element to the back of the list.
196    ///
197    /// This function substitutes [`InsertTailList`] of the Windows NT API.
198    ///
199    /// This operation computes in *O*(*1*) time.
200    ///
201    /// [`InsertTailList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-inserttaillist
202    pub fn push_back(self: Pin<&mut Self>, element: E) {
203        let boxed_element = Box::new(element);
204        unsafe { self.inner_mut().push_back(Box::leak(boxed_element)) }
205    }
206
207    /// Appends an element to the front of the list.
208    ///
209    /// This function substitutes [`InsertHeadList`] of the Windows NT API.
210    ///
211    /// This operation computes in *O*(*1*) time.
212    ///
213    /// [`InsertHeadList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-insertheadlist
214    pub fn push_front(self: Pin<&mut Self>, element: E) {
215        let boxed_element = Box::new(element);
216        unsafe { self.inner_mut().push_front(Box::leak(boxed_element)) }
217    }
218
219    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
220    ///
221    /// In other words, remove all elements `e` for which `f(&mut e)` returns `false`.
222    /// This method operates in place, visiting each element exactly once in the original order,
223    /// and preserves the order of the retained elements.
224    ///
225    /// This function substitutes [`RemoveEntryList`] of the Windows NT API.
226    ///
227    /// This operation computes in *O*(*n*) time.
228    ///
229    /// [`RemoveEntryList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-removeentrylist
230    pub fn retain<F>(self: Pin<&mut Self>, mut f: F)
231    where
232        F: FnMut(&mut E) -> bool,
233    {
234        for element in self.iter_mut() {
235            if !f(element) {
236                let entry = NtListHead::entry(element);
237
238                unsafe {
239                    (*entry).remove();
240                    drop(Box::from_raw(element));
241                }
242            }
243        }
244    }
245}
246
247impl<E, L> Drop for NtBoxingListHead<E, L>
248where
249    E: NtBoxedListElement<L = L> + NtListElement<L>,
250    L: NtTypedList<T = NtList>,
251{
252    fn drop(&mut self) {
253        let pinned = unsafe { Pin::new_unchecked(self) };
254
255        for element in pinned.iter_mut() {
256            // Reconstruct the `Box` we created in push_back/push_front and let it leave the scope
257            // to call its Drop handler and deallocate the element gracefully.
258            unsafe {
259                drop(Box::from_raw(element));
260            }
261        }
262    }
263}
264
265impl<E, L> Extend<Box<E>> for Pin<&mut NtBoxingListHead<E, L>>
266where
267    E: NtBoxedListElement<L = L> + NtListElement<L>,
268    L: NtTypedList<T = NtList>,
269{
270    fn extend<T>(&mut self, iter: T)
271    where
272        T: IntoIterator<Item = Box<E>>,
273    {
274        let end_marker = self.as_mut().inner_mut().end_marker_mut();
275        let mut previous = self.as_ref().inner().blink;
276
277        for element in iter.into_iter() {
278            // We could use `NtBoxingListHead::push_back` here, but this manual implementation
279            // is slightly optimized (doesn't modify list head's `blink` on every iteration).
280            unsafe {
281                let entry = NtListHead::entry(Box::leak(element));
282
283                (*entry).flink = end_marker;
284                (*entry).blink = previous;
285                (*previous).flink = entry;
286
287                previous = entry;
288            }
289        }
290
291        unsafe {
292            self.as_mut().get_unchecked_mut().0.blink = previous;
293        }
294    }
295}
296
297impl<E, L> Extend<E> for Pin<&mut NtBoxingListHead<E, L>>
298where
299    E: NtBoxedListElement<L = L> + NtListElement<L>,
300    L: NtTypedList<T = NtList>,
301{
302    fn extend<T>(&mut self, iter: T)
303    where
304        T: IntoIterator<Item = E>,
305    {
306        self.extend(iter.into_iter().map(Box::new))
307    }
308}
309
310#[cfg(test)]
311mod tests {
312    use super::*;
313    use crate::list::NtListEntry;
314    use alloc::vec::Vec;
315    use moveit::moveit;
316
317    #[derive(NtList)]
318    enum MyList {}
319
320    #[derive(Default, NtListElement)]
321    #[repr(C)]
322    struct MyElement {
323        value: i32,
324        #[boxed]
325        entry: NtListEntry<Self, MyList>,
326    }
327
328    impl MyElement {
329        fn new(value: i32) -> Self {
330            Self {
331                value,
332                ..Default::default()
333            }
334        }
335    }
336
337    #[test]
338    fn test_append() {
339        // Append two lists of equal size.
340        moveit! {
341            let mut list1 = NtBoxingListHead::<MyElement, MyList>::new();
342            let mut list2 = NtBoxingListHead::<MyElement, MyList>::new();
343        }
344
345        for i in 0..10 {
346            list1.as_mut().push_back(MyElement::new(i));
347            list2.as_mut().push_back(MyElement::new(i));
348        }
349
350        list1.as_mut().append(list2.as_mut());
351
352        assert_eq!(list1.as_ref().len(), 20);
353        assert_eq!(list2.as_ref().len(), 0);
354
355        for (i, element) in (0..10).chain(0..10).zip(list1.as_ref().iter()) {
356            assert_eq!(i, element.value);
357        }
358
359        verify_all_links(list1.as_ref().inner());
360
361        // Append the final list to an empty list.
362        moveit! {
363            let mut list3 = NtBoxingListHead::<MyElement, MyList>::new();
364        }
365
366        list3.as_mut().append(list1.as_mut());
367
368        assert_eq!(list3.as_ref().len(), 20);
369        assert_eq!(list1.as_ref().len(), 0);
370
371        verify_all_links(list3.as_ref().inner());
372    }
373
374    #[test]
375    fn test_clear_and_append() {
376        // Append two lists of equal size.
377        moveit! {
378            let mut list1 = NtBoxingListHead::<MyElement, MyList>::new();
379            let mut list2 = NtBoxingListHead::<MyElement, MyList>::new();
380        }
381
382        for i in 0..10 {
383            list1.as_mut().push_back(MyElement::new(i));
384            list2.as_mut().push_back(MyElement::new(i));
385        }
386
387        list1.as_mut().append(list2.as_mut());
388
389        assert_eq!(list1.as_ref().len(), 20);
390        assert_eq!(list2.as_ref().len(), 0);
391
392        for (i, element) in (0..10).chain(0..10).zip(list1.as_ref().iter()) {
393            assert_eq!(i, element.value);
394        }
395
396        verify_all_links(list1.as_ref().inner());
397
398        // Add more elements to both lists
399        list1.as_mut().push_back(MyElement::new(21));
400        list1.as_mut().push_front(MyElement::new(22));
401
402        list2.as_mut().push_back(MyElement::new(21));
403        list2.as_mut().push_front(MyElement::new(22));
404
405        // Append the final list to a cleared list.
406        moveit! {
407            let mut list3 = NtBoxingListHead::<MyElement, MyList>::new();
408        }
409
410        list3.as_mut().clear();
411        list3.as_mut().append(list1.as_mut());
412
413        assert_eq!(list3.as_ref().len(), 22);
414        assert_eq!(list1.as_ref().len(), 0);
415
416        verify_all_links(list3.as_ref().inner());
417    }
418
419    #[test]
420    fn test_clear_and_push() {
421        moveit! {
422            let mut list = NtBoxingListHead::<MyElement, MyList>::new();
423        }
424
425        list.as_mut().clear();
426
427        for i in 0..=3 {
428            list.as_mut().push_back(MyElement::new(i));
429        }
430        for i in 4..=6 {
431            list.as_mut().push_front(MyElement::new(i));
432        }
433
434        assert_eq!(list.as_ref().back().unwrap().value, 3);
435        assert_eq!(list.as_mut().back_mut().unwrap().value, 3);
436        assert_eq!(list.as_ref().front().unwrap().value, 6);
437        assert_eq!(list.as_mut().front_mut().unwrap().value, 6);
438
439        verify_all_links(list.as_ref().inner());
440    }
441
442    #[test]
443    fn test_back_and_front() {
444        moveit! {
445            let mut list = NtBoxingListHead::<MyElement, MyList>::new();
446        }
447
448        for i in 0..=3 {
449            list.as_mut().push_back(MyElement::new(i));
450        }
451
452        assert_eq!(list.as_ref().back().unwrap().value, 3);
453        assert_eq!(list.as_mut().back_mut().unwrap().value, 3);
454        assert_eq!(list.as_ref().front().unwrap().value, 0);
455        assert_eq!(list.as_mut().front_mut().unwrap().value, 0);
456    }
457
458    #[test]
459    fn test_extend() {
460        let integers = [0, 1, 2, 3, 4, 5];
461
462        moveit! {
463            let mut list = NtBoxingListHead::<MyElement, MyList>::new();
464        }
465
466        list.as_mut()
467            .extend(integers.into_iter().map(MyElement::new));
468
469        for (i, element) in integers.into_iter().zip(list.as_ref().iter()) {
470            assert_eq!(i, element.value);
471        }
472
473        verify_all_links(list.as_ref().inner());
474    }
475
476    #[test]
477    fn test_pop_back() {
478        moveit! {
479            let mut list = NtBoxingListHead::<MyElement, MyList>::new();
480        }
481
482        for i in 0..10 {
483            list.as_mut().push_back(MyElement::new(i));
484        }
485
486        for i in (0..10).rev() {
487            let element = list.as_mut().pop_back().unwrap();
488            assert_eq!(i, element.value);
489            verify_all_links(list.as_ref().inner());
490        }
491
492        assert!(list.as_ref().is_empty());
493    }
494
495    #[test]
496    fn test_pop_front() {
497        moveit! {
498            let mut list = NtBoxingListHead::<MyElement, MyList>::new();
499        }
500
501        for i in 0..10 {
502            list.as_mut().push_back(MyElement::new(i));
503        }
504
505        for i in 0..10 {
506            let element = list.as_mut().pop_front().unwrap();
507            assert_eq!(i, element.value);
508            verify_all_links(list.as_ref().inner());
509        }
510
511        assert!(list.as_ref().is_empty());
512    }
513
514    #[test]
515    fn test_push_back() {
516        moveit! {
517            let mut list = NtBoxingListHead::<MyElement, MyList>::new();
518        }
519
520        for i in 0..10 {
521            list.as_mut().push_back(MyElement::new(i));
522        }
523
524        assert_eq!(list.as_ref().len(), 10);
525
526        for (i, element) in (0..10).zip(list.as_ref().iter()) {
527            assert_eq!(i, element.value);
528        }
529
530        verify_all_links(list.as_ref().inner());
531    }
532
533    #[test]
534    fn test_push_front() {
535        moveit! {
536            let mut list = NtBoxingListHead::<MyElement, MyList>::new();
537        }
538
539        for i in 0..10 {
540            list.as_mut().push_front(MyElement::new(i));
541        }
542
543        assert_eq!(list.as_ref().len(), 10);
544
545        for (i, element) in (0..10).rev().zip(list.as_ref().iter()) {
546            assert_eq!(i, element.value);
547        }
548
549        verify_all_links(list.as_ref().inner());
550    }
551
552    #[test]
553    fn test_retain() {
554        moveit! {
555            let mut list = NtBoxingListHead::<MyElement, MyList>::new();
556        }
557
558        for i in 0..10 {
559            list.as_mut().push_back(MyElement::new(i));
560        }
561
562        // Keep only the even elements.
563        list.as_mut().retain(|element| element.value % 2 == 0);
564
565        assert_eq!(list.as_ref().len(), 5);
566
567        for (i, element) in (0..10).step_by(2).zip(list.as_ref().iter()) {
568            assert_eq!(i, element.value);
569        }
570
571        verify_all_links(list.as_ref().inner());
572
573        // Keep only the first and last of the remaining elements.
574        list.as_mut()
575            .retain(|element| element.value == 0 || element.value == 8);
576
577        let mut iter = list.as_ref().iter();
578        assert_eq!(iter.next().unwrap().value, 0);
579        assert_eq!(iter.next().unwrap().value, 8);
580        assert!(matches!(iter.next(), None));
581    }
582
583    fn verify_all_links<E, L>(head: Pin<&NtListHead<E, L>>)
584    where
585        E: NtListElement<L>,
586        L: NtTypedList<T = NtList>,
587    {
588        let mut current;
589        let end = (head.get_ref() as *const _ as *mut NtListHead<E, L>).cast();
590
591        // Traverse the list in forward direction and collect all entries.
592        current = head.flink;
593        let mut forward_entries = Vec::<*mut NtListEntry<E, L>>::new();
594
595        while current != end {
596            if !forward_entries.is_empty() {
597                // Verify that the previous entry is referenced by this entry's `blink`.
598                unsafe {
599                    assert_eq!(*forward_entries.last().unwrap(), (*current).blink);
600                }
601            }
602
603            forward_entries.push(current);
604            current = unsafe { (*current).flink };
605        }
606
607        // Traverse the list in backward direction and collect all entries.
608        current = head.blink;
609        let mut backward_entries =
610            Vec::<*mut NtListEntry<E, L>>::with_capacity(forward_entries.len());
611
612        while current != end {
613            if !backward_entries.is_empty() {
614                // Verify that the previous entry is referenced by this entry's `flink`.
615                unsafe {
616                    assert_eq!(*backward_entries.last().unwrap(), (*current).flink);
617                }
618            }
619
620            backward_entries.push(current);
621            current = unsafe { (*current).blink };
622        }
623
624        // Verify that `backward_entries` is the exact reverse of `forward_entries`.
625        assert_eq!(forward_entries.len(), backward_entries.len());
626
627        for (fe, be) in forward_entries.iter().zip(backward_entries.iter().rev()) {
628            assert_eq!(fe, be);
629        }
630    }
631}
nt_list/list/boxing.rs

nt_list/list/
boxing.rs
