apma 0.1.0

Adaptive Packed Memory Array (APMA) — a cache-efficient sorted associative container
Documentation
  • Coverage
  • 50%
    2 out of 4 items documented0 out of 0 items with examples
  • Size
  • Source code size: 72.35 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 3.28 MB This is the summed size of all files generated by rustdoc for all configured targets
  • Links
  • krzysztofwos/apma
    0 0 0
  • crates.io
  • Dependencies
    • —
  • Versions
  • Owners
  • krzysztofwos

APMA (Adaptive Packed Memory Array)

Crates.io Documentation License: MIT/Apache-2.0 Build Status

A Rust implementation of the Adaptive Packed Memory Array (APMA) data structure, providing an efficient sorted associative container.

Overview

The Adaptive Packed Memory Array is a cache-efficient data structure that maintains elements in a sorted order while providing the following benefits:

  • Cache-friendly: Elements are stored in a packed array, improving cache locality
  • Efficient operations: O(log n) search, insert, and delete operations
  • Adaptive density: Self-adjusts to maintain efficient space utilization
  • Memory-efficient: Automatically rebalances to manage space usage

Features

  • Fast lookup by key with binary search
  • Efficient insertion and deletion with automatic rebalancing
  • Double-ended iteration over all elements in sorted order
  • Customizable density thresholds for fine-tuning performance

Usage

use apma::Apma;

// Create a new empty APMA
let mut map = Apma::new();

// Insert key-value pairs
map.insert("apple", 5);
map.insert("banana", 3);
map.insert("cherry", 7);

// Lookup values
if let Some(count) = map.get(&"banana") {
    println!("Banana count: {}", count);
}

// Remove entries
let removed_value = map.remove(&"apple");

// Iterate through all entries in sorted order
for (key, value) in &map {
    println!("{}: {}", key, value);
}

Implementation Details

The APMA maintains elements in a packed array with intentional gaps to facilitate efficient insertions and deletions. The key features include:

  • Adaptive rebalancing: Maintains density thresholds that vary by level in a conceptual tree structure
  • Efficient element distribution: Uses specialized algorithms to pack and spread elements
  • Binary search: Modified to handle gaps in the array efficiently
  • Automatic resizing: Grows or shrinks as needed based on element count

API Reference

Constructor Methods

  • new(): Creates a new, empty APMA with default density thresholds
  • with_thresholds(up_h, up_0, low_h, low_0): Creates an APMA with custom density thresholds
  • from_sorted_slice(items): Creates an APMA from a pre-sorted slice of key-value pairs

Core Operations

  • insert(key, value): Inserts a key-value pair, returning whether it was a new insertion
  • remove(key): Removes a key, returning the associated value if found
  • get(key): Retrieves a reference to the value for a given key
  • contains_key(key): Checks if a key exists in the APMA

Utility Methods

  • len(): Returns the number of elements
  • is_empty(): Checks if the APMA contains no elements
  • capacity(): Returns the total capacity (used and unused slots)
  • clear(): Removes all elements

Iteration

  • iter(): Returns an iterator over all key-value pairs in sorted order

Performance Characteristics

  • Search: O(log n)
  • Insert: O(log n) amortized
  • Delete: O(log n) amortized
  • Space usage: O(n)

The data structure is optimized for scenarios requiring sorted key access with frequent modifications, providing better cache performance than traditional tree structures in many cases.

License

Licensed under either of

at the option of the user.

Contribution

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