coca - Data Structures with Constant Capacity

Allocation-free data structures that make do with the memory they're given.

[dependencies]
coca = "0.3"

Overview

Rust's standard collection library provides efficient implementations of the most common general purpose programming data structures. By using the standard implementations, it should be possible for two libraries to communicate without significant data conversion.

However, these standard implementations manage their own memory using an Allocator, defaulting to the global heap. This is generally convenient, but may pose a problem in some cases, e.g. in (soft) real-time applications, or in memory-constrained embedded systems, where the alloc crate may not even be available.

coca aims to serve as a replacement in such environments by providing data structures that operate on a given block of backing memory, without allocating on their own. They are generic over the storage type, which may be any of the following:

• InlineStorage: Store the contents inside the struct, without indirection. Requires capacities that are truly const, i.e. statically known at compile time.
• AllocStorage: Store the contents in globally allocated memory. Requires the alloc feature flag.
• SliceStorage: For array-like data structures only, store the contents in any given slice of uninitialized memory.
• ArenaStorage: coca includes an arena allocator, and allows ergonomic construction of data structures using arena-allocated memory as storage.

Within this paradigm, direct analogs to the following types are provided:

• alloc::vec::Vec
• alloc::string::String
• alloc::collections::VecDeque
• alloc::collections::BinaryHeap
• slotmap::{SlotMap, DenseSlotMap}

Additionally, coca also includes the following container types:

• ListSet, a set implemented as a Vec.
• ListMap, an association list implemented as a pair of parallel arrays.
• CacheTable, a forgetful hash map with a configurable eviction policy; ideal for caching, hence the name.
• OptionGroup, a tuple or array of optional values with the occupancy flags packed into a single bitmap field.
• InlineObject, a statically-sized container for dynamically-sized types, mainly trait objects; this requires unstable language features, and therefore needs the unstable feature flag to be enabled.

Comparison with Other Libraries

First of all, unless you are trying to avoid hitting the global allocator, or don't have one in your target environment, you are almost certainly better off just using Rust's standard collections, or in the case of coca::collections::pool, the slotmap crate. Even in such a scenario, however, there are several crates filling a similar niche that are more mature than coca.

coca::arena vs bumpalo

• Bumpalo is a no_std crate, but it does have a hard dependency on the alloc crate, which it uses to automatically add chunks to its arenas whenever they run out of space. This helps in avoiding failed allocations, but makes it harder to bound memory usage. By contrast, coca's dependency on alloc is optional; a coca::arena::Arena always returns None (or panics, at your option) when it runs out of space, but can be constructed from any mutable byte slice.
• Bumpalo has its own forks of Rust's standard Vec and String that use its Bump allocator, and optionally supports the nightly-only Allocator API for compatibility with the other standard collections. On stable Rust, coca::arena supports a wider variety of data structures, but it won't benefit from the stabilization of feature(allocator_api).
• Uniquely, coca's arenas can be nested, allowing for stack-like de/allocation patterns.

coca::collections vs heapless

• heapless provides a variety of data structures with statically known capacity, the equivalent of coca's InlineStorage. It has no support for dynamic allocations.
• heapless provides direct analogs to std::collections::HashMap and HashSet, which coca does not have (yet).
• None of coca's data structures are thread-safe, while heapless provides multiple synchronization mechanisms: a lock-free memory pool with atomically reference-counting pointers, and both MPMC and SPSC lock-free queues.
• heapless does not provide equivalents to std::collections::VecDeque, slotmap::SlotMap or slotmap::DenseSlotMap, while coca does, on top of the more niche data structures (CacheTable, OptionGroup, InlineObject).

coca::collections::vec vs tinyvec and arrayvec

• tinyvec uses no unsafe code, but requires the element type to implement the Default trait. coca has no such restriction, and offers equivalents to tinyvec::ArrayVec and tinyvec::SliceVec, but not tinyvec::TinyVec, which is a small-size optimized vector with the ability to reallocate. coca also requires a newer rust version (min. 1.59) than tinyvec (min. 1.34).

• Both arrayvec and tinyvec have optional serde support, while coca does not.

• coca::collections::Vec supports more storage modes with just one implementation, meaning its instantiations inter-operate more easily, and you can write generic code to handle all of them. It is also generic over the index type, similar to what is offered by the typed_index_collections crate.

Feature Flags

• alloc: By default, coca is no_std compatible; this feature flag enables some trait implementations for conveniently working with heap-allocated storage.
• profile: Enables memory profiling in arenas; see the module-level documentation for details.
• unstable: If you're working with the nightly rust toolchain, and don't mind depending on unstable features, you can enable this feature to get access to InlineObject, allowing you to create trait objects without indirection.

License

Licensed under either Apache License, Version 2.0 or Zlib license at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this crate by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.