#index #list #queue

index_queue

A queue for unique indices with constant-time query and removal

1 unstable release

Uses old Rust 2015

0.1.0 Mar 28, 2017

#49 in #list


Used in synchrotron

MIT/Apache

10KB
264 lines

index_queue

A queue for unique indices (integers) with O(1) push/pop and O(1) lookup/removal. It is a doubly-linked list with all its nodes stored inside a single Vec. The queue is most memory efficient when the integers are relatively small and densely packed. The implementation is similar to ixlist, but index_queue is more specialized: it allows querying whether an index already exists as well as removal by index, but does not allow duplicate indices.

The queue works well with indices obtained from array-based allocators such as vec_arena or slab.

This crate was originally created to implement a cooperative FIFO task scheduler (synchrotron).

No runtime deps