intrex

Intrusive collections with items stored in an application-provided object pool and addressed by indices.

Features

• #![no_std] + no-alloc

• Intrusive doubly-linked lists

• Intrusive binary trees with optional search capability

  • Unbalanced
  • Red-black with reshaping hooks (useful for implementing order-statistic trees, etc.; see tests/rbtree_order_stats.rs for an example)

• A generic subroutine to sort singly-linked lists

Example: Doubly-Linked List

use intrex::list::{Head, Link};

struct Node {
    value: i32,
    siblings: Option<Link>,
}

let mut nodes: Vec<_> = (0..4)
    .map(|value| Node { value, siblings: None })
    .collect();
let mut head = Head::default();

// Add [2, 3, 1, 0] to the list
let mut accessor = head.write_ref(&mut nodes, |n: &mut Node| &mut n.siblings);
accessor.push_back(3);
accessor.push_back(0);
accessor.insert(1, Some(0));
accessor.push_front(2);

// Inspect the list
let accessor = head.read_ref(&nodes, |n| &n.siblings);
assert_eq!(accessor.front().unwrap().value, 2);
assert_eq!(accessor.back().unwrap().value, 0);
assert_eq!(
    accessor.values().map(|n| n.value).collect::<Vec<_>>(),
    vec![2, 3, 1, 0],
);

// Sort the list
head.write_ref(&mut nodes, |n: &mut Node| &mut n.siblings)
    .sort_by_key(|nodes, i| nodes.pool[i].value);

let accessor = head.read_ref(&nodes, |n| &n.siblings);
assert_eq!(
    accessor.values().map(|n| n.value).collect::<Vec<_>>(),
    vec![0, 1, 2, 3],
);

License

MIT/Apache-2.0