nt_list/single_list/
base.rs

1// Copyright 2022 Colin Finck <colin@reactos.org>
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use core::iter::FusedIterator;
5use core::marker::PhantomData;
6use core::ptr;
7
8use super::traits::NtSingleList;
9use crate::traits::{NtListElement, NtTypedList};
10
11/// A singly linked list header compatible to [`SINGLE_LIST_ENTRY`] of the Windows NT API.
12///
13/// This variant requires elements to be allocated beforehand on a stable address and be
14/// valid as long as the list is used.
15/// As the Rust compiler cannot guarantee the validity of them, almost all `NtSingleListHead`
16/// functions are `unsafe`.
17/// You almost always want to use [`NtBoxingSingleListHead`] over this.
18///
19/// See the [module-level documentation](crate::single_list) for more details.
20///
21/// This structure substitutes the `SINGLE_LIST_ENTRY` structure of the Windows NT API for the list header.
22///
23/// [`NtBoxingSingleListHead`]: crate::single_list::NtBoxingSingleListHead
24/// [`SINGLE_LIST_ENTRY`]: https://docs.microsoft.com/en-us/windows/win32/api/ntdef/ns-ntdef-single_list_entry
25#[repr(C)]
26pub struct NtSingleListHead<E: NtListElement<L>, L: NtTypedList<T = NtSingleList>> {
27    pub(crate) next: *mut NtSingleListEntry<E, L>,
28}
29
30impl<E, L> NtSingleListHead<E, L>
31where
32    E: NtListElement<L>,
33    L: NtTypedList<T = NtSingleList>,
34{
35    /// Creates a new singly linked list.
36    pub fn new() -> Self {
37        Self {
38            next: ptr::null_mut(),
39        }
40    }
41
42    /// Removes all elements from the list.
43    ///
44    /// This operation computes in *O*(*1*) time, because it only resets the forward link of the header.
45    pub fn clear(&mut self) {
46        self.next = ptr::null_mut();
47    }
48
49    /// Returns the [`NtSingleListEntry`] for the given element.
50    pub(crate) fn entry(element: &mut E) -> *mut NtSingleListEntry<E, L> {
51        let element_ptr = element as *mut E;
52
53        // This is the canonical implementation of `byte_add`
54        let entry = unsafe { element_ptr.cast::<u8>().add(E::offset()).cast::<E>() };
55
56        entry.cast()
57    }
58
59    /// Provides a reference to the first element, or `None` if the list is empty.
60    ///
61    /// This operation computes in *O*(*1*) time.
62    pub unsafe fn front(&self) -> Option<&E> {
63        (!self.is_empty()).then(|| NtSingleListEntry::containing_record(self.next))
64    }
65
66    /// Provides a mutable reference to the first element, or `None` if the list is empty.
67    ///
68    /// This operation computes in *O*(*1*) time.
69    pub unsafe fn front_mut(&mut self) -> Option<&mut E> {
70        (!self.is_empty()).then(|| NtSingleListEntry::containing_record_mut(self.next))
71    }
72
73    /// Returns `true` if the list is empty.
74    ///
75    /// This operation computes in *O*(*1*) time.
76    pub fn is_empty(&self) -> bool {
77        self.next.is_null()
78    }
79
80    /// Returns an iterator yielding references to each element of the list.
81    pub unsafe fn iter(&self) -> Iter<E, L> {
82        Iter {
83            current: self.next,
84            phantom: PhantomData,
85        }
86    }
87
88    /// Returns an iterator yielding mutable references to each element of the list.
89    pub unsafe fn iter_mut(&mut self) -> IterMut<E, L> {
90        IterMut {
91            current: self.next,
92            phantom: PhantomData,
93        }
94    }
95
96    /// Counts all elements and returns the length of the list.
97    ///
98    /// This operation computes in *O*(*n*) time.
99    pub unsafe fn len(&self) -> usize {
100        self.iter().count()
101    }
102
103    /// Removes the first element from the list and returns it, or `None` if the list is empty.
104    ///
105    /// This function substitutes [`PopEntryList`] of the Windows NT API.
106    ///
107    /// This operation computes in *O*(*1*) time.
108    ///
109    /// [`PopEntryList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-popentrylist
110    pub unsafe fn pop_front(&mut self) -> Option<&mut E> {
111        (!self.is_empty()).then(|| {
112            let entry = self.next;
113            self.next = (*entry).next;
114            NtSingleListEntry::containing_record_mut(entry)
115        })
116    }
117
118    /// Appends an element to the front of the list.
119    ///
120    /// This function substitutes [`PushEntryList`] of the Windows NT API.
121    ///
122    /// This operation computes in *O*(*1*) time.
123    ///
124    /// [`PushEntryList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-pushentrylist
125    pub unsafe fn push_front(&mut self, element: &mut E) {
126        let entry = Self::entry(element);
127
128        (*entry).next = self.next;
129        self.next = entry;
130    }
131
132    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
133    ///
134    /// In other words, remove all elements `e` for which `f(&mut e)` returns `false`.
135    /// This method operates in place, visiting each element exactly once in the original order,
136    /// and preserves the order of the retained elements.
137    ///
138    /// This operation computes in *O*(*n*) time.
139    pub unsafe fn retain<F>(&mut self, mut f: F)
140    where
141        F: FnMut(&mut E) -> bool,
142    {
143        let mut previous = (self as *mut Self).cast();
144        let mut current = self.next;
145
146        while !current.is_null() {
147            let element = NtSingleListEntry::containing_record_mut(current);
148
149            if f(element) {
150                previous = current;
151            } else {
152                (*previous).next = (*current).next;
153            }
154
155            current = (*current).next;
156        }
157    }
158}
159
160impl<E, L> Default for NtSingleListHead<E, L>
161where
162    E: NtListElement<L>,
163    L: NtTypedList<T = NtSingleList>,
164{
165    fn default() -> Self {
166        Self::new()
167    }
168}
169
170/// Iterator over the elements of a singly linked list.
171///
172/// This iterator is returned from the [`NtSingleListHead::iter`] and
173/// [`NtBoxingSingleListHead::iter`] functions.
174///
175/// [`NtBoxingSingleListHead::iter`]: crate::single_list::NtBoxingSingleListHead::iter
176pub struct Iter<'a, E: NtListElement<L>, L: NtTypedList<T = NtSingleList>> {
177    current: *const NtSingleListEntry<E, L>,
178    phantom: PhantomData<&'a NtSingleListHead<E, L>>,
179}
180
181impl<'a, E, L> Iterator for Iter<'a, E, L>
182where
183    E: NtListElement<L>,
184    L: NtTypedList<T = NtSingleList>,
185{
186    type Item = &'a E;
187
188    fn next(&mut self) -> Option<&'a E> {
189        if self.current.is_null() {
190            None
191        } else {
192            unsafe {
193                let element_ptr = self.current;
194                self.current = (*self.current).next;
195                Some(NtSingleListEntry::<E, L>::containing_record(element_ptr))
196            }
197        }
198    }
199}
200
201impl<'a, E, L> FusedIterator for Iter<'a, E, L>
202where
203    E: NtListElement<L>,
204    L: NtTypedList<T = NtSingleList>,
205{
206}
207
208/// Mutable iterator over the elements of a singly linked list.
209///
210/// This iterator is returned from the [`NtSingleListHead::iter_mut`] and
211/// [`NtBoxingSingleListHead::iter_mut`] functions.
212///
213/// [`NtBoxingSingleListHead::iter_mut`]: crate::single_list::NtBoxingSingleListHead::iter_mut
214pub struct IterMut<'a, E: NtListElement<L>, L: NtTypedList<T = NtSingleList>> {
215    current: *mut NtSingleListEntry<E, L>,
216    phantom: PhantomData<&'a mut NtSingleListHead<E, L>>,
217}
218
219impl<'a, E, L> Iterator for IterMut<'a, E, L>
220where
221    E: NtListElement<L>,
222    L: NtTypedList<T = NtSingleList>,
223{
224    type Item = &'a mut E;
225
226    fn next(&mut self) -> Option<&'a mut E> {
227        if self.current.is_null() {
228            None
229        } else {
230            unsafe {
231                let element_ptr = self.current;
232                self.current = (*self.current).next;
233                Some(NtSingleListEntry::containing_record_mut(element_ptr))
234            }
235        }
236    }
237}
238
239impl<'a, E, L> FusedIterator for IterMut<'a, E, L>
240where
241    E: NtListElement<L>,
242    L: NtTypedList<T = NtSingleList>,
243{
244}
245
246/// This structure substitutes the `SINGLE_LIST_ENTRY` structure of the Windows NT API for actual list entries.
247#[derive(Debug)]
248#[repr(C)]
249pub struct NtSingleListEntry<E: NtListElement<L>, L: NtTypedList<T = NtSingleList>> {
250    pub(crate) next: *mut NtSingleListEntry<E, L>,
251}
252
253impl<E, L> NtSingleListEntry<E, L>
254where
255    E: NtListElement<L>,
256    L: NtTypedList<T = NtSingleList>,
257{
258    /// Allows the creation of an `NtSingleListEntry`, but leaves all fields uninitialized.
259    ///
260    /// Its fields are only initialized when an entry is pushed to a list.
261    pub fn new() -> Self {
262        Self {
263            next: ptr::null_mut(),
264        }
265    }
266
267    pub(crate) unsafe fn containing_record<'a>(ptr: *const Self) -> &'a E {
268        // This is the canonical implementation of `byte_sub`
269        let element_ptr = unsafe { ptr.cast::<u8>().sub(E::offset()).cast::<Self>() };
270
271        unsafe { &*element_ptr.cast() }
272    }
273
274    pub(crate) unsafe fn containing_record_mut<'a>(ptr: *mut Self) -> &'a mut E {
275        // This is the canonical implementation of `byte_sub`
276        let element_ptr = unsafe { ptr.cast::<u8>().sub(E::offset()).cast::<Self>() };
277
278        unsafe { &mut *element_ptr.cast() }
279    }
280}
281
282impl<E, L> Default for NtSingleListEntry<E, L>
283where
284    E: NtListElement<L>,
285    L: NtTypedList<T = NtSingleList>,
286{
287    fn default() -> Self {
288        Self::new()
289    }
290}
nt_list/single_list/base.rs

nt_list/single_list/
base.rs
