Struct DelayQueue

pub struct DelayQueue<T> { /* private fields */ }

A queue of delayed elements.

Once an element is inserted into the DelayQueue, it is yielded once the specified deadline has been reached.

Usage

Elements are inserted into DelayQueue using the insert or insert_at methods. A deadline is provided with the item and a Key is returned. The key is used to remove the entry or to change the deadline at which it should be yielded back.

Once delays have been configured, the DelayQueue is used via its Stream implementation. poll_expired is called. If an entry has reached its deadline, it is returned. If not, Poll::Pending is returned indicating that the current task will be notified once the deadline has been reached.

Stream implementation

Items are retrieved from the queue via DelayQueue::poll_expired. If no delays have expired, no items are returned. In this case, Poll::Pending is returned and the current task is registered to be notified once the next item’s delay has expired.

If no items are in the queue, i.e. is_empty() returns true, then poll returns Poll::Ready(None). This indicates that the stream has reached an end. However, if a new item is inserted after, poll will once again start returning items or Poll::Pending.

Items are returned ordered by their expirations. Items that are configured to expire first will be returned first. There are no ordering guarantees for items configured to expire at the same instant. Also note that delays are rounded to the closest millisecond.

Implementation

The DelayQueue is backed by a separate instance of a timer wheel similar to that used internally by Tokio’s standalone timer utilities such as sleep. Because of this, it offers the same performance and scalability benefits.

State associated with each entry is stored in a slab. This amortizes the cost of allocation, and allows reuse of the memory allocated for expired entries.

Capacity can be checked using capacity and allocated preemptively by using the reserve method.

Usage

Using DelayQueue to manage cache entries.

use tokio_util::time::{DelayQueue, delay_queue};

use std::collections::HashMap;
use std::task::{ready, Context, Poll};
use std::time::Duration;

struct Cache {
    entries: HashMap<CacheKey, (Value, delay_queue::Key)>,
    expirations: DelayQueue<CacheKey>,
}

const TTL_SECS: u64 = 30;

impl Cache {
    fn insert(&mut self, key: CacheKey, value: Value) {
        let delay = self.expirations
            .insert(key.clone(), Duration::from_secs(TTL_SECS));

        self.entries.insert(key, (value, delay));
    }

    fn get(&self, key: &CacheKey) -> Option<&Value> {
        self.entries.get(key)
            .map(|&(ref v, _)| v)
    }

    fn remove(&mut self, key: &CacheKey) {
        if let Some((_, cache_key)) = self.entries.remove(key) {
            self.expirations.remove(&cache_key);
        }
    }

    fn poll_purge(&mut self, cx: &mut Context<'_>) -> Poll<()> {
        while let Some(entry) = ready!(self.expirations.poll_expired(cx)) {
            self.entries.remove(entry.get_ref());
        }

        Poll::Ready(())
    }
}

Implementations

impl<T> DelayQueue<T>

pub fn new() -> DelayQueue<T>

Creates a new, empty, DelayQueue.

The queue will not allocate storage until items are inserted into it.

Examples

let delay_queue: DelayQueue<u32> = DelayQueue::new();

pub fn with_capacity(capacity: usize) -> DelayQueue<T>

Creates a new, empty, DelayQueue with the specified capacity.

The queue will be able to hold at least capacity elements without reallocating. If capacity is 0, the queue will not allocate for storage.

Examples

let mut delay_queue = DelayQueue::with_capacity(10);

// These insertions are done without further allocation
for i in 0..10 {
    delay_queue.insert(i, Duration::from_secs(i));
}

// This will make the queue allocate additional storage
delay_queue.insert(11, Duration::from_secs(11));

pub fn insert_at(&mut self, value: T, when: Instant) -> Key

Inserts value into the queue set to expire at a specific instant in time.

This function is identical to insert, but takes an Instant instead of a Duration.

value is stored in the queue until when is reached. At which point, value will be returned from poll_expired. If when has already been reached, then value is immediately made available to poll.

The return value represents the insertion and is used as an argument to remove and reset. Note that Key is a token and is reused once value is removed from the queue either by calling poll_expired after when is reached or by calling remove. At this point, the caller must take care to not use the returned Key again as it may reference a different item in the queue.

See type level documentation for more details.

Panics

This function panics if when is too far in the future.

Examples

Basic usage

use tokio::time::{Duration, Instant};
use tokio_util::time::DelayQueue;

let mut delay_queue = DelayQueue::new();
let key = delay_queue.insert_at(
    "foo", Instant::now() + Duration::from_secs(5));

// Remove the entry
let item = delay_queue.remove(&key);
assert_eq!(*item.get_ref(), "foo");

pub fn poll_expired(&mut self, cx: &mut Context<'_>) -> Poll<Option<Expired<T>>>

Attempts to pull out the next value of the delay queue, registering the current task for wakeup if the value is not yet available, and returning None if the queue is exhausted.

pub fn insert(&mut self, value: T, timeout: Duration) -> Key

Inserts value into the queue set to expire after the requested duration elapses.

This function is identical to insert_at, but takes a Duration instead of an Instant.

value is stored in the queue until timeout duration has elapsed after insert was called. At that point, value will be returned from poll_expired. If timeout is a Duration of zero, then value is immediately made available to poll.

The return value represents the insertion and is used as an argument to remove and reset. Note that Key is a token and is reused once value is removed from the queue either by calling poll_expired after timeout has elapsed or by calling remove. At this point, the caller must not use the returned Key again as it may reference a different item in the queue.

See type level documentation for more details.

Panics

This function panics if timeout is greater than the maximum duration supported by the timer in the current Runtime.

Examples

Basic usage

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();
let key = delay_queue.insert("foo", Duration::from_secs(5));

// Remove the entry
let item = delay_queue.remove(&key);
assert_eq!(*item.get_ref(), "foo");

pub fn deadline(&self, key: &Key) -> Instant

Returns the deadline of the item associated with key.

Since the queue operates at millisecond granularity, the returned deadline may not exactly match the value that was given when initially inserting the item into the queue.

Panics

This function panics if key is not contained by the queue.

Examples

Basic usage

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();

let key1 = delay_queue.insert("foo", Duration::from_secs(5));
let key2 = delay_queue.insert("bar", Duration::from_secs(10));

assert!(delay_queue.deadline(&key1) < delay_queue.deadline(&key2));

pub fn remove(&mut self, key: &Key) -> Expired<T>

Removes the item associated with key from the queue.

There must be an item associated with key. The function returns the removed item as well as the Instant at which it will the delay will have expired.

Panics

The function panics if key is not contained by the queue.

Examples

Basic usage

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();
let key = delay_queue.insert("foo", Duration::from_secs(5));

// Remove the entry
let item = delay_queue.remove(&key);
assert_eq!(*item.get_ref(), "foo");

pub fn try_remove(&mut self, key: &Key) -> Option<Expired<T>>

Attempts to remove the item associated with key from the queue.

Removes the item associated with key, and returns it along with the Instant at which it would have expired, if it exists.

Returns None if key is not in the queue.

Examples

Basic usage

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();
let key = delay_queue.insert("foo", Duration::from_secs(5));

// The item is in the queue, `try_remove` returns `Some(Expired("foo"))`.
let item = delay_queue.try_remove(&key);
assert_eq!(item.unwrap().into_inner(), "foo");

// The item is not in the queue anymore, `try_remove` returns `None`.
let item = delay_queue.try_remove(&key);
assert!(item.is_none());

pub fn reset_at(&mut self, key: &Key, when: Instant)

Sets the delay of the item associated with key to expire at when.

This function is identical to reset but takes an Instant instead of a Duration.

The item remains in the queue but the delay is set to expire at when. If when is in the past, then the item is immediately made available to the caller.

Panics

This function panics if when is too far in the future or if key is not contained by the queue.

Examples

Basic usage

use tokio::time::{Duration, Instant};
use tokio_util::time::DelayQueue;

let mut delay_queue = DelayQueue::new();
let key = delay_queue.insert("foo", Duration::from_secs(5));

// "foo" is scheduled to be returned in 5 seconds

delay_queue.reset_at(&key, Instant::now() + Duration::from_secs(10));

// "foo" is now scheduled to be returned in 10 seconds

pub fn shrink_to_fit(&mut self)

Shrink the capacity of the slab, which DelayQueue uses internally for storage allocation. This function is not guaranteed to, and in most cases, won’t decrease the capacity of the slab to the number of elements still contained in it, because elements cannot be moved to a different index. To decrease the capacity to the size of the slab use compact.

This function can take O(n) time even when the capacity cannot be reduced or the allocation is shrunk in place. Repeated calls run in O(1) though.

pub fn compact(&mut self)

Shrink the capacity of the slab, which DelayQueue uses internally for storage allocation, to the number of elements that are contained in it.

This methods runs in O(n).

Examples

Basic usage

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::with_capacity(10);

let key1 = delay_queue.insert(5, Duration::from_secs(5));
let key2 = delay_queue.insert(10, Duration::from_secs(10));
let key3 = delay_queue.insert(15, Duration::from_secs(15));

delay_queue.remove(&key2);

delay_queue.compact();
assert_eq!(delay_queue.capacity(), 2);

pub fn peek(&self) -> Option<Key>

Gets the Key that poll_expired will pull out of the queue next, without pulling it out or waiting for the deadline to expire.

Entries that have already expired may be returned in any order, but it is guaranteed that this method returns them in the same order as when items are popped from the DelayQueue.

Examples

Basic usage

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();

let key1 = delay_queue.insert("foo", Duration::from_secs(10));
let key2 = delay_queue.insert("bar", Duration::from_secs(5));
let key3 = delay_queue.insert("baz", Duration::from_secs(15));

assert_eq!(delay_queue.peek().unwrap(), key2);

pub fn reset(&mut self, key: &Key, timeout: Duration)

Sets the delay of the item associated with key to expire after timeout.

This function is identical to reset_at but takes a Duration instead of an Instant.

The item remains in the queue but the delay is set to expire after timeout. If timeout is zero, then the item is immediately made available to the caller.

Panics

This function panics if timeout is greater than the maximum supported duration or if key is not contained by the queue.

Examples

Basic usage

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();
let key = delay_queue.insert("foo", Duration::from_secs(5));

// "foo" is scheduled to be returned in 5 seconds

delay_queue.reset(&key, Duration::from_secs(10));

// "foo"is now scheduled to be returned in 10 seconds

pub fn clear(&mut self)

Clears the queue, removing all items.

After calling clear, poll_expired will return Ok(Ready(None)).

Note that this method has no effect on the allocated capacity.

Examples

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();

delay_queue.insert("foo", Duration::from_secs(5));

assert!(!delay_queue.is_empty());

delay_queue.clear();

assert!(delay_queue.is_empty());

pub fn capacity(&self) -> usize

Returns the number of elements the queue can hold without reallocating.

Examples

use tokio_util::time::DelayQueue;

let delay_queue: DelayQueue<i32> = DelayQueue::with_capacity(10);
assert_eq!(delay_queue.capacity(), 10);

pub fn len(&self) -> usize

Returns the number of elements currently in the queue.

Examples

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue: DelayQueue<i32> = DelayQueue::with_capacity(10);
assert_eq!(delay_queue.len(), 0);
delay_queue.insert(3, Duration::from_secs(5));
assert_eq!(delay_queue.len(), 1);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more items to be queued without allocating.

reserve does nothing if the queue already has sufficient capacity for additional more values. If more capacity is required, a new segment of memory will be allocated and all existing values will be copied into it. As such, if the queue is already very large, a call to reserve can end up being expensive.

The queue may reserve more than additional extra space in order to avoid frequent reallocations.

Panics

Panics if the new capacity exceeds the maximum number of entries the queue can contain.

Examples

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();

delay_queue.insert("hello", Duration::from_secs(10));
delay_queue.reserve(10);

assert!(delay_queue.capacity() >= 11);

pub fn is_empty(&self) -> bool

Returns true if there are no items in the queue.

Note that this function returns false even if all items have not yet expired and a call to poll will return Poll::Pending.

Examples

use tokio_util::time::DelayQueue;
use std::time::Duration;

let mut delay_queue = DelayQueue::new();
assert!(delay_queue.is_empty());

delay_queue.insert("hello", Duration::from_secs(5));
assert!(!delay_queue.is_empty());

Trait Implementations

impl<T: Debug> Debug for DelayQueue<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for DelayQueue<T>

fn default() -> DelayQueue<T>

Returns the “default value” for a type.

impl<T> Stream for DelayQueue<T>

type Item = Expired<T>

Values yielded by the stream.

fn poll_next( self: Pin<&mut Self>, cx: &mut Context<'_>, ) -> Poll<Option<Self::Item>>

Attempt to pull out the next value of this stream, registering the current task for wakeup if the value is not yet available, and returning None if the stream is exhausted.

fn size_hint(&self) -> (usize, Option<usize>)

Returns the bounds on the remaining length of the stream.

impl<T> Unpin for DelayQueue<T>