ngx/collections/
queue.rs

1//! Types and utilities for working with [ngx_queue_t], an intrusive doubly-linked list.
2//!
3//! This module provides both the tools for interaction with the existing `ngx_queue_t` objects in
4//! the NGINX, and useful high-level types built on top of the `ngx_queue_t`.
5//!
6//! See <https://nginx.org/en/docs/dev/development_guide.html#queue>.
7
8use core::alloc::Layout;
9use core::marker::PhantomData;
10use core::mem;
11use core::ptr::{self, NonNull};
12
13use nginx_sys::{
14    ngx_queue_data, ngx_queue_empty, ngx_queue_init, ngx_queue_insert_after,
15    ngx_queue_insert_before, ngx_queue_remove, ngx_queue_t,
16};
17
18use crate::allocator::{AllocError, Allocator};
19
20/// Trait for pointer conversions between the queue entry and its container.
21///
22/// # Safety
23///
24/// This trait must only be implemented on types that contain a queue link or wrappers with
25/// compatible layout. The type then can be used to access elements of a raw queue type
26/// [NgxQueue] linked via specified field.
27///
28/// If the struct can belong to several queues through multiple embedded `ngx_queue_t` fields,
29/// a separate [NgxQueueEntry] implementation via wrapper type should be used for each queue.
30pub unsafe trait NgxQueueEntry {
31    /// Gets a container pointer from queue node.
32    fn from_queue(queue: NonNull<ngx_queue_t>) -> NonNull<Self>;
33    /// Gets a queue node from a container reference.
34    fn to_queue(&mut self) -> &mut ngx_queue_t;
35}
36
37unsafe impl NgxQueueEntry for ngx_queue_t {
38    fn from_queue(queue: NonNull<ngx_queue_t>) -> NonNull<Self> {
39        queue
40    }
41
42    fn to_queue(&mut self) -> &mut ngx_queue_t {
43        self
44    }
45}
46
47/// A wrapper over a raw `ngx_queue_t`, an intrusive doubly-linked list.
48///
49/// This wrapper is defined in terms of type `T` that embeds and can be converted from or to the
50/// list entries.
51///
52/// Example:
53/// ```rust,no_run
54/// # use core::ptr::{NonNull, addr_of_mut};
55/// # use nginx_sys::{ngx_event_t, ngx_posted_events, ngx_queue_data, ngx_queue_t};
56/// # use ngx::collections::queue::{NgxQueue, NgxQueueEntry};
57/// // We need a wrapper type to define [NgxQueueEntry] on.
58/// #[repr(transparent)]
59/// struct PostedEvent(ngx_event_t);
60///
61/// unsafe impl NgxQueueEntry for PostedEvent {
62///     fn from_queue(queue: NonNull<ngx_queue_t>) -> NonNull<Self> {
63///         // We can safely cast obtained ngx_event_t to a transparent wrapper.
64///         unsafe { ngx_queue_data!(queue, ngx_event_t, queue) }.cast()
65///     }
66///
67///     fn to_queue(&mut self) -> &mut ngx_queue_t {
68///         &mut self.0.queue
69///     }
70/// }
71///
72/// // SAFETY: `ngx_posted_events` global static is a list of `ngx_event_t` linked via
73/// // `ngx_event_t.queue`.
74/// // NGINX is single-threaded, so we get exclusive access to the static.
75/// let posted: &mut NgxQueue<PostedEvent> =
76///         unsafe { NgxQueue::from_ptr_mut(addr_of_mut!(ngx_posted_events)) };
77/// ```
78///
79/// See <https://nginx.org/en/docs/dev/development_guide.html#queue>.
80#[derive(Debug)]
81#[repr(transparent)]
82pub struct NgxQueue<T> {
83    head: ngx_queue_t,
84    _type: PhantomData<T>,
85}
86
87impl<T> NgxQueue<T>
88where
89    T: NgxQueueEntry,
90{
91    /// Creates a queue reference from a pointer to [ngx_queue_t].
92    ///
93    /// # Safety
94    ///
95    /// `head` is a valid pointer to a list head, and `T::from_queue` on the list entries results in
96    /// valid pointers to `T`.
97    pub unsafe fn from_ptr<'a>(head: *const ngx_queue_t) -> &'a Self {
98        &*head.cast()
99    }
100
101    /// Creates a mutable queue reference from a pointer to [ngx_queue_t].
102    ///
103    /// # Safety
104    ///
105    /// `head` is a valid pointer to a list head, and `T::from_queue` on the list entries results in
106    /// valid pointers to `T`.
107    pub unsafe fn from_ptr_mut<'a>(head: *mut ngx_queue_t) -> &'a mut Self {
108        &mut *head.cast()
109    }
110
111    /// Returns `true` if the queue contains no elements.
112    pub fn is_empty(&self) -> bool {
113        self.head.prev.is_null() || unsafe { ngx_queue_empty(&self.head) }
114    }
115
116    /// Appends an element to the end of the queue.
117    pub fn push_back(&mut self, entry: &mut T) {
118        if self.head.prev.is_null() {
119            unsafe { ngx_queue_init(&mut self.head) }
120        }
121
122        unsafe { ngx_queue_insert_before(&mut self.head, entry.to_queue()) }
123    }
124
125    /// Appends an element to the beginning of the queue.
126    pub fn push_front(&mut self, entry: &mut T) {
127        if self.head.prev.is_null() {
128            unsafe { ngx_queue_init(&mut self.head) }
129        }
130
131        unsafe { ngx_queue_insert_after(&mut self.head, entry.to_queue()) }
132    }
133
134    /// Returns an iterator over the entries of the queue.
135    pub fn iter(&self) -> NgxQueueIter<'_, T> {
136        NgxQueueIter::new(&self.head)
137    }
138
139    /// Returns a mutable iterator over the entries of the queue.
140    pub fn iter_mut(&mut self) -> NgxQueueIterMut<'_, T> {
141        NgxQueueIterMut::new(&mut self.head)
142    }
143}
144
145/// An iterator for the queue.
146pub struct NgxQueueIter<'a, T> {
147    head: NonNull<ngx_queue_t>,
148    current: NonNull<ngx_queue_t>,
149    _lifetime: PhantomData<&'a T>,
150}
151
152impl<'a, T> NgxQueueIter<'a, T>
153where
154    T: NgxQueueEntry,
155{
156    /// Creates a new queue iterator.
157    pub fn new(head: &'a ngx_queue_t) -> Self {
158        let head = NonNull::from(head);
159        NgxQueueIter {
160            head,
161            current: head,
162            _lifetime: PhantomData,
163        }
164    }
165}
166
167impl<'a, T> Iterator for NgxQueueIter<'a, T>
168where
169    T: NgxQueueEntry + 'a,
170{
171    type Item = &'a T;
172
173    fn next(&mut self) -> Option<Self::Item> {
174        unsafe {
175            let next = NonNull::new(self.current.as_ref().next)?;
176            if next == self.head {
177                return None;
178            }
179
180            self.current = next;
181            Some(T::from_queue(self.current).as_ref())
182        }
183    }
184}
185
186/// A mutable iterator for the queue.
187pub struct NgxQueueIterMut<'a, T> {
188    head: NonNull<ngx_queue_t>,
189    current: NonNull<ngx_queue_t>,
190    _lifetime: PhantomData<&'a T>,
191}
192
193impl<'a, T> NgxQueueIterMut<'a, T>
194where
195    T: NgxQueueEntry,
196{
197    /// Creates a new mutable queue iterator.
198    pub fn new(head: &'a mut ngx_queue_t) -> Self {
199        let head = NonNull::from(head);
200        NgxQueueIterMut {
201            head,
202            current: head,
203            _lifetime: PhantomData,
204        }
205    }
206}
207
208impl<'a, T> Iterator for NgxQueueIterMut<'a, T>
209where
210    T: NgxQueueEntry + 'a,
211{
212    type Item = &'a mut T;
213
214    fn next(&mut self) -> Option<Self::Item> {
215        unsafe {
216            let next = NonNull::new(self.current.as_ref().next)?;
217            if next == self.head {
218                return None;
219            }
220
221            self.current = next;
222            Some(T::from_queue(self.current).as_mut())
223        }
224    }
225}
226
227/// A doubly-linked list that owns elements of type `T` backed by the specified allocator `A`.
228#[derive(Debug)]
229pub struct Queue<T, A>
230where
231    A: Allocator,
232{
233    // The address of the NgxQueue with queue head has to be stable, as the queue elements will
234    // contain pointers to the head.
235    raw: NonNull<NgxQueue<QueueEntry<T>>>,
236    len: usize,
237    alloc: A,
238}
239
240impl<T, A> Drop for Queue<T, A>
241where
242    A: Allocator,
243{
244    fn drop(&mut self) {
245        while self.pop_front().is_some() {}
246
247        let layout = Layout::for_value(unsafe { self.raw.as_ref() });
248        unsafe { self.allocator().deallocate(self.raw.cast(), layout) };
249    }
250}
251
252unsafe impl<T, A> Send for Queue<T, A>
253where
254    A: Send + Allocator,
255    T: Send,
256{
257}
258
259unsafe impl<T, A> Sync for Queue<T, A>
260where
261    A: Sync + Allocator,
262    T: Sync,
263{
264}
265
266impl<T, A: Allocator> Queue<T, A> {
267    /// Creates a new list with specified allocator.
268    pub fn try_new_in(alloc: A) -> Result<Self, AllocError> {
269        let raw = NgxQueue {
270            head: unsafe { mem::zeroed() },
271            _type: PhantomData,
272        };
273        let raw = crate::allocator::allocate(raw, &alloc)?;
274        Ok(Self { raw, len: 0, alloc })
275    }
276
277    /// Returns a reference to the underlying allocator.
278    pub fn allocator(&self) -> &A {
279        &self.alloc
280    }
281
282    /// Returns `true` if the list contains no elements.
283    pub fn is_empty(&self) -> bool {
284        self.raw().is_empty()
285    }
286
287    /// Returns the number of elements in the queue.
288    pub fn len(&self) -> usize {
289        self.len
290    }
291
292    /// Returns an iterator over the entries of the list.
293    pub fn iter(&self) -> QueueIter<'_, T> {
294        QueueIter::new(&self.raw().head)
295    }
296
297    /// Returns a mutable iterator over the entries of the list.
298    pub fn iter_mut(&mut self) -> QueueIterMut<'_, T> {
299        QueueIterMut::new(&mut self.raw_mut().head)
300    }
301
302    /// Removes the last element and returns it or `None` if the list is empty.
303    pub fn pop_back(&mut self) -> Option<T> {
304        if self.is_empty() {
305            return None;
306        }
307        let node = NonNull::new(self.raw_mut().head.prev)?;
308        Some(unsafe { self.remove(node) })
309    }
310
311    /// Removes the first element and returns it or `None` if the list is empty.
312    pub fn pop_front(&mut self) -> Option<T> {
313        if self.is_empty() {
314            return None;
315        }
316        let node = NonNull::new(self.raw_mut().head.next)?;
317        Some(unsafe { self.remove(node) })
318    }
319
320    /// Appends an element to the end of the list.
321    pub fn push_back(&mut self, item: T) -> Result<&mut T, AllocError> {
322        let mut entry = QueueEntry::new_in(item, self.allocator())?;
323        let entry = unsafe { entry.as_mut() };
324        self.raw_mut().push_back(entry);
325        self.len += 1;
326        Ok(&mut entry.item)
327    }
328
329    /// Appends an element to the beginning of the list.
330    pub fn push_front(&mut self, item: T) -> Result<&mut T, AllocError> {
331        let mut entry = QueueEntry::new_in(item, self.allocator())?;
332        let entry = unsafe { entry.as_mut() };
333        self.raw_mut().push_front(entry);
334        self.len += 1;
335        Ok(&mut entry.item)
336    }
337
338    fn raw(&self) -> &NgxQueue<QueueEntry<T>> {
339        // SAFETY: we allocated this pointer as well-aligned and convertible to reference.
340        unsafe { self.raw.as_ref() }
341    }
342
343    fn raw_mut(&mut self) -> &mut NgxQueue<QueueEntry<T>> {
344        // SAFETY: we allocated this pointer as well-aligned and convertible to reference.
345        unsafe { self.raw.as_mut() }
346    }
347
348    /// Removes a node from the queue and returns the contained value.
349    ///
350    /// # Safety
351    ///
352    /// `node` must be an element of this list.
353    unsafe fn remove(&mut self, node: NonNull<ngx_queue_t>) -> T {
354        ngx_queue_remove(node.as_ptr());
355        self.len -= 1;
356
357        let entry = QueueEntry::<T>::from_queue(node);
358        let copy = entry.read();
359        // Skip drop as QueueEntry is already copied to `x`.
360        self.allocator()
361            .deallocate(entry.cast(), Layout::for_value(entry.as_ref()));
362        copy.item
363    }
364}
365
366#[derive(Debug)]
367struct QueueEntry<T> {
368    queue: ngx_queue_t,
369    item: T,
370}
371
372unsafe impl<T> NgxQueueEntry for QueueEntry<T> {
373    fn from_queue(queue: NonNull<ngx_queue_t>) -> NonNull<Self> {
374        unsafe { ngx_queue_data!(queue, Self, queue) }
375    }
376
377    fn to_queue(&mut self) -> &mut ngx_queue_t {
378        &mut self.queue
379    }
380}
381
382impl<T> QueueEntry<T> {
383    pub fn new_in(item: T, alloc: &impl Allocator) -> Result<NonNull<Self>, AllocError> {
384        let p: NonNull<Self> = alloc.allocate(Layout::new::<Self>())?.cast();
385
386        unsafe {
387            let u = p.cast::<mem::MaybeUninit<Self>>().as_mut();
388            // does not read the uninitialized data
389            ngx_queue_init(&mut u.assume_init_mut().queue);
390            ptr::write(&mut u.assume_init_mut().item, item);
391        }
392
393        Ok(p)
394    }
395}
396
397/// An iterator for the linked list [Queue].
398pub struct QueueIter<'a, T>(NgxQueueIter<'a, QueueEntry<T>>);
399
400impl<'a, T> QueueIter<'a, T> {
401    /// Creates a new iterator for the linked list.
402    pub fn new(head: &'a ngx_queue_t) -> Self {
403        Self(NgxQueueIter::new(head))
404    }
405}
406
407impl<'a, T> Iterator for QueueIter<'a, T> {
408    type Item = &'a T;
409
410    fn next(&mut self) -> Option<Self::Item> {
411        Some(&self.0.next()?.item)
412    }
413}
414
415/// A mutable iterator for the linked list [Queue].
416pub struct QueueIterMut<'a, T>(NgxQueueIterMut<'a, QueueEntry<T>>);
417
418impl<'a, T> QueueIterMut<'a, T> {
419    /// Creates a new mutable iterator for the linked list.
420    pub fn new(head: &'a mut ngx_queue_t) -> Self {
421        Self(NgxQueueIterMut::new(head))
422    }
423}
424
425impl<'a, T> Iterator for QueueIterMut<'a, T> {
426    type Item = &'a mut T;
427
428    fn next(&mut self) -> Option<Self::Item> {
429        Some(&mut self.0.next()?.item)
430    }
431}
ngx/collections/queue.rs

ngx/collections/
queue.rs
