A highly flexible, non-amortized worst-case O(log n) intrusive skip list.
The skip list can be used both as a sorted sequence (allowing it to be used as a set or map) and as an unsorted sequence of elements in arbitrary order (allowing it to be used as a vector/dynamic array). Elements support an optional notion of “size”, allowing insertions, removals, and lookups by index, as well as, due to the intrusive nature of the skip list, the ability to query an element’s index.
Internal nodes in the skip list are allocated deterministically so that between any two consecutive nodes at layer L, there are always between F / 2 and F nodes at layer L - 1, where F is a configurable fanout parameter. This is very similar to a B+ tree; in fact, this skip list is essentially a B+ tree where children are stored in linked lists rather than arrays.
If the crate feature allocator_api is enabled, the skip list can be
configured with the unstable Allocator trait. Otherwise,
allocator-fallback will be used.
This crate can be used in no_std contexts by disabling the std feature with
default-features = false. In this case, one of allocator-fallback or
allocator_api must be enabled.
Documentation is available on docs.rs.
Skippy is licensed under version 3 of the GNU Affero General Public License, or (at your option) any later version. See LICENSE.
In addition, the Eips Lesser Network Exception and Eips Peer-to-Peer Exception apply to Skippy. These exceptions are additional permissions under section 7 of the GNU AGPL, version 3; as such, if you modify Skippy, you may choose whether to extend them to your modified version. For more information about these exceptions, see this repository.
Please note that you do not have to license your project under the AGPL if you use Skippy. Your project can be licensed under any AGPLv3-compatible license, including nearly all permissive licenses such as MIT or Apache 2.0. The terms of the AGPL will apply only to the combination of your project with Skippy (e.g., source code must be provided along with any compiled binaries); any portion of your project that does not depend on Skippy may be used without adherence to the AGPL.
By contributing to Skippy, you agree that your contribution may be used according to the terms of Skippy’s license, including the Eips Lesser Network Exception and Eips Peer-to-Peer Exception.