nt_list/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::PhantomPinned;
6use core::pin::Pin;
7use core::ptr;
8
9use moveit::{new, New};
10
11use super::traits::NtList;
12use crate::traits::{NtListElement, NtTypedList};
13
14/// A doubly linked list header compatible to [`LIST_ENTRY`] of the Windows NT API.
15///
16/// This variant requires elements to be allocated beforehand on a stable address and be
17/// valid as long as the list is used.
18/// As the Rust compiler cannot guarantee the validity of them, almost all `NtListHead`
19/// functions are `unsafe`.
20/// You almost always want to use [`NtBoxingListHead`] over this.
21///
22/// See the [module-level documentation](crate::list) for more details.
23///
24/// This structure substitutes the `LIST_ENTRY` structure of the Windows NT API for the list header.
25///
26/// [`LIST_ENTRY`]: https://docs.microsoft.com/en-us/windows/win32/api/ntdef/ns-ntdef-list_entry
27/// [`NtBoxingListHead`]: crate::list::NtBoxingListHead
28#[repr(C)]
29pub struct NtListHead<E: NtListElement<L>, L: NtTypedList<T = NtList>> {
30    pub(crate) flink: *mut NtListEntry<E, L>,
31    pub(crate) blink: *mut NtListEntry<E, L>,
32    pub(crate) pin: PhantomPinned,
33}
34
35impl<E, L> NtListHead<E, L>
36where
37    E: NtListElement<L>,
38    L: NtTypedList<T = NtList>,
39{
40    /// Creates a new doubly linked list.
41    ///
42    /// This function substitutes [`InitializeListHead`] of the Windows NT API.
43    ///
44    /// [`InitializeListHead`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-initializelisthead
45    pub fn new() -> impl New<Output = Self> {
46        new::of(Self {
47            flink: ptr::null_mut(),
48            blink: ptr::null_mut(),
49            pin: PhantomPinned,
50        })
51        .with(|this| {
52            let this = unsafe { this.get_unchecked_mut() };
53            this.flink = (this as *mut Self).cast();
54            this.blink = this.flink;
55        })
56    }
57
58    /// Moves all elements from `other` to the end of the list.
59    ///
60    /// This reuses all the nodes from `other` and moves them into `self`.
61    /// After this operation, `other` becomes empty.
62    ///
63    /// This operation computes in *O*(*1*) time.
64    pub unsafe fn append(mut self: Pin<&mut Self>, other: Pin<&mut Self>) {
65        if other.as_ref().is_empty() {
66            return;
67        }
68
69        // Append `other` to `self` by remounting the respective elements:
70        // - The last element of `self` shall be followed by the first element of `other`.
71        // - The first element of `other` shall be preceded by the last element of `self`.
72        // - The last element of `other` shall be followed by the end marker of `self`.
73        // - The last element of `self` shall be changed to the last element of `other`.
74        (*self.blink).flink = other.flink;
75        (*other.flink).blink = self.blink;
76        (*other.blink).flink = self.as_mut().end_marker_mut();
77        self.get_unchecked_mut().blink = other.blink;
78
79        // Clear `other` without touching any of its elements.
80        other.clear();
81    }
82
83    /// Provides a reference to the last element, or `None` if the list is empty.
84    ///
85    /// This operation computes in *O*(*1*) time.
86    pub unsafe fn back(self: Pin<&Self>) -> Option<&E> {
87        (!self.is_empty()).then(|| NtListEntry::containing_record(self.blink))
88    }
89
90    /// Provides a mutable reference to the last element, or `None` if the list is empty.
91    ///
92    /// This operation computes in *O*(*1*) time.
93    pub unsafe fn back_mut(self: Pin<&mut Self>) -> Option<&mut E> {
94        (!self.as_ref().is_empty()).then(|| NtListEntry::containing_record_mut(self.blink))
95    }
96
97    /// Removes all elements from the list.
98    ///
99    /// This operation computes in *O*(*1*) time, because it only resets the forward and
100    /// backward links of the header.
101    pub fn clear(mut self: Pin<&mut Self>) {
102        let end_marker = self.as_mut().end_marker_mut();
103        let self_mut = unsafe { self.get_unchecked_mut() };
104
105        self_mut.flink = end_marker;
106        self_mut.blink = end_marker;
107    }
108
109    /// Returns a const pointer to the "end marker element" (which is the address of our own `NtListHead`, but interpreted as a `NtListEntry` element address).
110    pub(crate) fn end_marker(self: Pin<&Self>) -> *const NtListEntry<E, L> {
111        (self.get_ref() as *const Self).cast()
112    }
113
114    /// Returns a mutable pointer to the "end marker element" (which is the address of our own `NtListHead`, but interpreted as a `NtListEntry` element address).
115    pub(crate) fn end_marker_mut(self: Pin<&mut Self>) -> *mut NtListEntry<E, L> {
116        (unsafe { self.get_unchecked_mut() } as *mut Self).cast()
117    }
118
119    /// Returns the [`NtListEntry`] for the given element.
120    pub(crate) fn entry(element: &mut E) -> *mut NtListEntry<E, L> {
121        let element_ptr = element as *mut E;
122
123        // This is the canonical implementation of `byte_add`
124        let entry = unsafe { element_ptr.cast::<u8>().add(E::offset()).cast::<E>() };
125
126        entry.cast()
127    }
128
129    /// Provides a reference to the first element, or `None` if the list is empty.
130    ///
131    /// This operation computes in *O*(*1*) time.
132    pub unsafe fn front(self: Pin<&Self>) -> Option<&E> {
133        (!self.is_empty()).then(|| NtListEntry::containing_record(self.flink))
134    }
135
136    /// Provides a mutable reference to the first element, or `None` if the list is empty.
137    ///
138    /// This operation computes in *O*(*1*) time.
139    pub unsafe fn front_mut(self: Pin<&mut Self>) -> Option<&mut E> {
140        (!self.as_ref().is_empty()).then(|| NtListEntry::containing_record_mut(self.flink))
141    }
142
143    /// Returns `true` if the list is empty.
144    ///
145    /// This function substitutes [`IsListEmpty`] of the Windows NT API.
146    ///
147    /// This operation computes in *O*(*1*) time.
148    ///
149    /// [`IsListEmpty`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-islistempty
150    pub fn is_empty(self: Pin<&Self>) -> bool {
151        self.flink as *const NtListEntry<E, L> == (self.get_ref() as *const Self).cast()
152    }
153
154    /// Returns an iterator yielding references to each element of the list.
155    pub unsafe fn iter(self: Pin<&Self>) -> Iter<E, L> {
156        let head = self;
157        let flink = head.flink;
158        let blink = head.blink;
159
160        Iter { head, flink, blink }
161    }
162
163    /// Returns an iterator yielding mutable references to each element of the list.
164    pub unsafe fn iter_mut(self: Pin<&mut Self>) -> IterMut<E, L> {
165        let head = self;
166        let flink = head.flink;
167        let blink = head.blink;
168
169        IterMut { head, flink, blink }
170    }
171
172    /// Counts all elements and returns the length of the list.
173    ///
174    /// This operation computes in *O*(*n*) time.
175    pub unsafe fn len(self: Pin<&Self>) -> usize {
176        self.iter().count()
177    }
178
179    /// Removes the last element from the list and returns it, or `None` if the list is empty.
180    ///
181    /// This function substitutes [`RemoveTailList`] of the Windows NT API.
182    ///
183    /// This operation computes in *O*(*1*) time.
184    ///
185    /// [`RemoveTailList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-removetaillist
186    pub unsafe fn pop_back(self: Pin<&mut Self>) -> Option<&mut E> {
187        (!self.as_ref().is_empty()).then(|| {
188            let entry = self.blink;
189            (*entry).remove();
190            NtListEntry::containing_record_mut(entry)
191        })
192    }
193
194    /// Removes the first element from the list and returns it, or `None` if the list is empty.
195    ///
196    /// This function substitutes [`RemoveHeadList`] of the Windows NT API.
197    ///
198    /// This operation computes in *O*(*1*) time.
199    ///
200    /// [`RemoveHeadList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-removeheadlist
201    pub unsafe fn pop_front(self: Pin<&mut Self>) -> Option<&mut E> {
202        (!self.as_ref().is_empty()).then(|| {
203            let entry = self.flink;
204            (*entry).remove();
205            NtListEntry::containing_record_mut(entry)
206        })
207    }
208
209    /// Appends an element to the back of the list.
210    ///
211    /// This function substitutes [`InsertTailList`] of the Windows NT API.
212    ///
213    /// This operation computes in *O*(*1*) time.
214    ///
215    /// [`InsertTailList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-inserttaillist
216    pub unsafe fn push_back(mut self: Pin<&mut Self>, element: &mut E) {
217        let entry = Self::entry(element);
218
219        let old_blink = self.blink;
220        (*entry).flink = self.as_mut().end_marker_mut();
221        (*entry).blink = old_blink;
222        (*old_blink).flink = entry;
223        self.get_unchecked_mut().blink = entry;
224    }
225
226    /// Appends an element to the front of the list.
227    ///
228    /// This function substitutes [`InsertHeadList`] of the Windows NT API.
229    ///
230    /// This operation computes in *O*(*1*) time.
231    ///
232    /// [`InsertHeadList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-insertheadlist
233    pub unsafe fn push_front(mut self: Pin<&mut Self>, element: &mut E) {
234        let entry = Self::entry(element);
235
236        let old_flink = self.flink;
237        (*entry).flink = old_flink;
238        (*entry).blink = self.as_mut().end_marker_mut();
239        (*old_flink).blink = entry;
240        self.get_unchecked_mut().flink = entry;
241    }
242
243    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
244    ///
245    /// In other words, remove all elements `e` for which `f(&mut e)` returns `false`.
246    /// This method operates in place, visiting each element exactly once in the original order,
247    /// and preserves the order of the retained elements.
248    ///
249    /// This function substitutes [`RemoveEntryList`] of the Windows NT API.
250    ///
251    /// This operation computes in *O*(*n*) time.
252    ///
253    /// [`RemoveEntryList`]: https://docs.microsoft.com/en-us/windows-hardware/drivers/ddi/wdm/nf-wdm-removeentrylist
254    pub unsafe fn retain<F>(self: Pin<&mut Self>, mut f: F)
255    where
256        F: FnMut(&mut E) -> bool,
257    {
258        for element in self.iter_mut() {
259            if !f(element) {
260                let entry = Self::entry(element);
261                (*entry).remove();
262            }
263        }
264    }
265}
266
267/// Iterator over the elements of a doubly linked list.
268///
269/// This iterator is returned from the [`NtListHead::iter`] and [`NtBoxingListHead::iter`] functions.
270///
271/// [`NtBoxingListHead::iter`]: crate::list::NtBoxingListHead::iter
272pub struct Iter<'a, E: NtListElement<L>, L: NtTypedList<T = NtList>> {
273    head: Pin<&'a NtListHead<E, L>>,
274    flink: *const NtListEntry<E, L>,
275    blink: *const NtListEntry<E, L>,
276}
277
278impl<'a, E, L> Iter<'a, E, L>
279where
280    E: NtListElement<L>,
281    L: NtTypedList<T = NtList>,
282{
283    fn terminate(&mut self) {
284        self.flink = self.head.end_marker();
285        self.blink = self.flink;
286    }
287}
288
289impl<'a, E, L> Iterator for Iter<'a, E, L>
290where
291    E: NtListElement<L>,
292    L: NtTypedList<T = NtList>,
293{
294    type Item = &'a E;
295
296    fn next(&mut self) -> Option<&'a E> {
297        if self.flink == self.head.end_marker() {
298            None
299        } else {
300            unsafe {
301                let element_ptr = self.flink;
302
303                if self.flink == self.blink {
304                    // We are crossing the other end of the iterator and must not iterate any further.
305                    self.terminate();
306                } else {
307                    self.flink = (*self.flink).flink;
308                }
309
310                Some(NtListEntry::containing_record(element_ptr))
311            }
312        }
313    }
314
315    fn last(mut self) -> Option<&'a E> {
316        self.next_back()
317    }
318}
319
320impl<'a, E, L> DoubleEndedIterator for Iter<'a, E, L>
321where
322    E: NtListElement<L>,
323    L: NtTypedList<T = NtList>,
324{
325    fn next_back(&mut self) -> Option<&'a E> {
326        if self.blink == self.head.end_marker() {
327            None
328        } else {
329            unsafe {
330                let element_ptr = self.blink;
331
332                if self.blink == self.flink {
333                    // We are crossing the other end of the iterator and must not iterate any further.
334                    self.terminate();
335                } else {
336                    self.blink = (*self.blink).blink;
337                }
338
339                Some(NtListEntry::containing_record(element_ptr))
340            }
341        }
342    }
343}
344
345impl<'a, E, L> FusedIterator for Iter<'a, E, L>
346where
347    E: NtListElement<L>,
348    L: NtTypedList<T = NtList>,
349{
350}
351
352/// Mutable iterator over the elements of a doubly linked list.
353///
354/// This iterator is returned from the [`NtListHead::iter_mut`] and [`NtBoxingListHead::iter_mut`] functions.
355///
356/// [`NtBoxingListHead::iter_mut`]: crate::list::NtBoxingListHead::iter_mut
357pub struct IterMut<'a, E: NtListElement<L>, L: NtTypedList<T = NtList>> {
358    head: Pin<&'a mut NtListHead<E, L>>,
359    flink: *mut NtListEntry<E, L>,
360    blink: *mut NtListEntry<E, L>,
361}
362
363impl<'a, E, L> IterMut<'a, E, L>
364where
365    E: NtListElement<L>,
366    L: NtTypedList<T = NtList>,
367{
368    fn terminate(&mut self) {
369        self.flink = self.head.as_mut().end_marker_mut();
370        self.blink = self.flink;
371    }
372}
373
374impl<'a, E, L> Iterator for IterMut<'a, E, L>
375where
376    E: NtListElement<L>,
377    L: NtTypedList<T = NtList>,
378{
379    type Item = &'a mut E;
380
381    fn next(&mut self) -> Option<&'a mut E> {
382        if self.flink == self.head.as_mut().end_marker_mut() {
383            None
384        } else {
385            unsafe {
386                let element_ptr = self.flink;
387
388                if self.flink == self.blink {
389                    // We are crossing the other end of the iterator and must not iterate any further.
390                    self.terminate();
391                } else {
392                    self.flink = (*self.flink).flink;
393                }
394
395                Some(NtListEntry::containing_record_mut(element_ptr))
396            }
397        }
398    }
399
400    fn last(mut self) -> Option<&'a mut E> {
401        self.next_back()
402    }
403}
404
405impl<'a, E, L> DoubleEndedIterator for IterMut<'a, E, L>
406where
407    E: NtListElement<L>,
408    L: NtTypedList<T = NtList>,
409{
410    fn next_back(&mut self) -> Option<&'a mut E> {
411        if self.blink == self.head.as_mut().end_marker_mut() {
412            None
413        } else {
414            unsafe {
415                let element_ptr = self.blink;
416
417                if self.blink == self.flink {
418                    // We are crossing the other end of the iterator and must not iterate any further.
419                    self.terminate();
420                } else {
421                    self.blink = (*self.blink).blink;
422                }
423
424                Some(NtListEntry::containing_record_mut(element_ptr))
425            }
426        }
427    }
428}
429
430impl<'a, E, L> FusedIterator for IterMut<'a, E, L>
431where
432    E: NtListElement<L>,
433    L: NtTypedList<T = NtList>,
434{
435}
436
437/// This structure substitutes the `LIST_ENTRY` structure of the Windows NT API for actual list entries.
438#[derive(Debug)]
439#[repr(C)]
440pub struct NtListEntry<E: NtListElement<L>, L: NtTypedList<T = NtList>> {
441    pub(crate) flink: *mut NtListEntry<E, L>,
442    pub(crate) blink: *mut NtListEntry<E, L>,
443    pin: PhantomPinned,
444}
445
446impl<E, L> NtListEntry<E, L>
447where
448    E: NtListElement<L>,
449    L: NtTypedList<T = NtList>,
450{
451    /// Allows the creation of an `NtListEntry`, but leaves all fields uninitialized.
452    ///
453    /// Its fields are only initialized when an entry is pushed to a list.
454    pub fn new() -> Self {
455        Self {
456            flink: ptr::null_mut(),
457            blink: ptr::null_mut(),
458            pin: PhantomPinned,
459        }
460    }
461
462    pub(crate) unsafe fn containing_record<'a>(ptr: *const Self) -> &'a E {
463        // This is the canonical implementation of `byte_sub`
464        let element_ptr = unsafe { ptr.cast::<u8>().sub(E::offset()).cast::<Self>() };
465
466        unsafe { &*element_ptr.cast() }
467    }
468
469    pub(crate) unsafe fn containing_record_mut<'a>(ptr: *mut Self) -> &'a mut E {
470        // This is the canonical implementation of `byte_sub`
471        let element_ptr = unsafe { ptr.cast::<u8>().sub(E::offset()).cast::<Self>() };
472
473        unsafe { &mut *element_ptr.cast() }
474    }
475
476    pub(crate) unsafe fn remove(&mut self) {
477        let old_flink = self.flink;
478        let old_blink = self.blink;
479        (*old_flink).blink = old_blink;
480        (*old_blink).flink = old_flink;
481    }
482}
483
484impl<E, L> Default for NtListEntry<E, L>
485where
486    E: NtListElement<L>,
487    L: NtTypedList<T = NtList>,
488{
489    fn default() -> Self {
490        Self::new()
491    }
492}
nt_list/list/base.rs

nt_list/list/
base.rs
