Crate heaparray

This crate aims to give people better control of how they allocate memory, by providing a customizable way to allocate blocks of memory, that optionally contains metadata about the block itself. This makes it much easier to implement Dynamically-Sized Types (DSTs), and also reduces the number of pointer indirections necessary to share data between threads.

It has two main features that provide the foundation for the rest:

• Storing data next to an array: From the Rust documentation on exotically sized types, at the end of the section on dynamically-sized types:

  Currently the only properly supported way to create a custom DST is by making your type generic and performing an unsizing coercion ... (Yes, custom DSTs are a largely half-baked feature for now.)

  This crate aims to provide some of that functionality; the code that the docs give is the following:

  struct MySuperSliceable<T: ?Sized> {
      info: u32,
      data: T
  }
  
  fn main() {
      let sized: MySuperSliceable<[u8; 8]> = MySuperSliceable {
          info: 17,
          data: [0; 8],
      };
  
      let dynamic: &MySuperSliceable<[u8]> = &sized;
  
      // prints: "17 [0, 0, 0, 0, 0, 0, 0, 0]"
      println!("{} {:?}", dynamic.info, &dynamic.data);
  }

  using this crate, the MySuperSliceable<[u8]> type would be implemented like this:

  use heaparray::*;
  
  fn main() {
      let dynamic = HeapArray::<u8,u32>::with_label(17, 8, |_,_| 0);
      println!("{:?}", dynamic);
  }

• Thin pointer arrays: in Rust, unsized structs are referenced with pointers that are stored with an associated length. This behavior isn't always desired, so this crate provides both thin and fat pointer-referenced arrays, where the length is stored with the data instead of with the pointer in the thin pointer variant.

Features

• Arrays are allocated on the heap, with optional extra space allocated for metadata
• Support for 1-word and 2-word pointers
• Atomically reference-counted memory blocks of arbitrary size without using a Vec; this means you can access reference-counted memory with only a single pointer indirection.
• Swap owned objects in and out with array.insert()
• Arbitrarily sized objects using label and an array of bytes (u8)

Examples

Creating an array:

use heaparray::*;
let len = 10;
let array = HeapArray::new(len, |idx| idx + 3);
assert!(array[1] == 4);

Indexing works as you would expect:

use heaparray::*;
let mut array = HeapArray::new(10, |_| 0);
array[3] = 2;
assert!(array[3] == 2);

You can take ownership of objects back from the container:

let mut array = HeapArray::new(10, |_| Vec::<u8>::new());
let replacement_object = Vec::new();
let owned_object = array.insert(0, replacement_object);

but you need to give the array a replacement object to fill its slot with.

Additionally, you can customize what information should be stored alongside the elements in the array using the HeapArray::with_label function:

struct MyLabel {
    pub even: usize,
    pub odd: usize,
}

let mut array = HeapArray::with_label(
    MyLabel { even: 0, odd: 0 },
    100,
    |label, index| {
        if index % 2 == 0 {
            label.even += 1;
            index
        } else {
            label.odd += 1;
            index
        }
    });

Use of unsafe Keyword

This library relies heavily on the use of the unsafe keyword to do both reference counting and atomic operations; there are 40 instances total, not including tests.

Customizability

All of the implementation details of this crate are public and documented; if you'd like to implement your own version of the tools available through this crate, note that you don't need to reinvent the wheel; many of the types in this crate are generic over certain traits, so you might not need to do that much.

Modules

alloc_utils	Contains pointer math and allocation utilities.
base	Module for simple heap arrays. ThinPtrArray and AtomicPtrArray are a single word on the stack, whereas FatPtrArray is a 2-word struct.
mem_block	Contains the struct MemBlock, which handles pointer math and very low-level interactions with memory.
naive_rc	This module contains naively reference counted arrays, both as atomic and regular versions; i.e. if you're not careful, you could make a cycle that never gets deallocated.

Structs

HeapArray

Heap-allocated array, with array size stored with the pointer to the memory.

Traits

ArrayRef	A reference to an array, whose clone points to the same data.
AtomicArrayRef	Atomically modified array reference. Guarrantees that all operations on the array reference are atomic (i.e. all changes to the internal array pointer). Additionally, guarrantees that all reads to a reference of this pointer use atomic loads.
BaseArrayRef	A basic reference to a heap-allocated array. Should be paired with exactly one of either heaparray::UnsafeArrayRef or heaparray::ArrayRef.
Container	Trait for a simple container.
CopyMap	Trait for a container indexed by a value that implements Copy and Eq.
DefaultLabelledArray	Trait for a labelled array with a default value.
LabelledArray	Array with an optional label struct stored next to the data.
LabelledArrayMut	Array with optional label struct stored next to the data that can be mutated
LabelledArrayRefMut	Array with optional label struct stored next to the data that can be conditionally mutated.
MakeArray	An array of arbitrary (sized) values that can be safely initialized.
SliceArray	Array that returns slices into its contents
SliceArrayRef	Array reference that can return a slice into its contents.

Type Definitions

ArcArray	Atomically reference counted array, referenced using a raw pointer.
RcArray	Reference counted array, referenced using a fat pointer.