The indexed::Pool, a convenient allocator for index-linked data structures.
Features
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.
- 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.
- 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.
- No reallocation will happen.
Once an element is located in the pool, it will not move at all.
- The pool can be managed or unmanaged.
A managed pool owns its elements and drops them in destruction while an unmanaged pool does not.
- Supports
no_std.
Performance
-
The underlying buffers are not continuous but segmented
Vecs. Mapping conceptual index to underlying buffer address is as lightweight as doing one integer division. -
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.
-
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.
-
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.