#pool #index #pin #vec #allocator

no-std indexed

Convenient allocator for index-linked data structures

3 unstable releases

Uses old Rust 2015

0.2.0 Feb 20, 2020
0.1.1 Nov 9, 2018
0.1.0 Oct 24, 2018

#578 in Data structures

Download history 254/week @ 2021-08-09 263/week @ 2021-08-16 418/week @ 2021-08-23 681/week @ 2021-08-30 697/week @ 2021-09-06 718/week @ 2021-09-13 623/week @ 2021-09-20 499/week @ 2021-09-27 573/week @ 2021-10-04 702/week @ 2021-10-11 606/week @ 2021-10-18 644/week @ 2021-10-25 699/week @ 2021-11-01 791/week @ 2021-11-08 722/week @ 2021-11-15 700/week @ 2021-11-22

1,250 downloads per month

MIT license

36KB
355 lines

The indexed::Pool, a convenient allocator for index-linked data structures.

Features

  1. Vec-like operations.

Supports push(), reserve() and random access by indexes which are similar with std::Vec's methods.

An unsafe write() method is provided, similar with std::ptr::write() except using index instead of pointer.

Other stuff like len(), set_len(), capacity(), iter() and iter_mut()` are also supported. See API doc for more.

Note that all deleting operations e.g. pop(), shrink_to_fit() are not supported.

  1. Using indexes to link elements to each other.

Any element in the pool must implement indexed::Indexed, which stores its index in itself. A user-defined null() index indicates an empty linkage.

  1. Obtaining reference of the pool from any one of its elements.

This feature makes it possible to simply use reference of element instead of the style of using pool + index. It is convenient in some usecases because the library users do not need to store/pass the references of the pool everywhere.

NOTICE: this feature is unsafe and it is up to the caller not to violating memory safety.

  1. No reallocation will happen.

Once an element is located in the pool, it will not move at all.

  1. The pool can be managed or unmanaged.

A managed pool owns its elements and drops them in destruction while an unmanaged pool does not.

  1. Supports no_std.

Performance

  1. The underlying buffers are not continuous but segmented Vecs. Mapping conceptual index to underlying buffer address is as lightweight as doing one integer division.

  2. Elements should provide space for storing their indexes. Index stored in usize occupies one extra pointer size. Index stored in u32 may occupy no extra space if some 32-bit padding exists in the struct in order to meet alignment requirement.

  3. Obtaining the pool's reference from its element is as efficient as one pointer arithmetic and deference operation. Library users can pick the classic pool + index API style if not satisfied with this overhead.

  4. Library users can pick up a different chunk size other than the default 256 for better performance.

License

Licensed under MIT.

Example

See API doc for more.

No runtime deps

Features

  • no_std
HN^