SegVec data structure for rust. Similar to Vec, but allocates memory in chunks of increasing size.

Related tags

Data structures segvec
Overview

segvec

docs.rs crates.io

This crate provides the SegVec data structure.

It is similar to Vec, but allocates memory in chunks of increasing size, referred to as "segments". This involves a few trade-offs:

Pros:

  • Element addresses are stable across push operations even if the SegVec must grow.
  • Resizing only allocates the additional space needed, and doesn't require copying.

Cons:

  • Operations are slower (some, like insert, remove, and drain, are much slower) for a SegVec than for a Vec (multiple pointer dereferences, mapping indices to (segment, offset) pairs)
  • Direct slicing is unavailable (i.e. no &[T] or &mut [T]), though slice and slice_mut are available

Use Cases

  1. You have a long-lived Vec whose size fluctuates between very large and very small throughout the life of the program.
  2. You have a large append-only Vec and would benefit from stable references to the elements

License: MIT

Comments
  • Implement Extend<&'a T> for T: Copy

    Implement Extend<&'a T> for T: Copy

    This PR supports the following Vec idiom:

    let mut v: Vec<u8> = vec![];
v.extend("data".as_bytes());
assert_eq!(v, [0x64, 0x61, 0x74, 0x61]);
    opened by interruptinuse 3
  • Rename `checked_log2_ceil`

    Rename `checked_log2_ceil`

    It turns out that checked_log2_ceil is actually checked_log2_floor - this can be seen by calling checked_log2_ceil(3), which returns 1. This is the correct value for the implementation, but the name is misleading. I want to re-name this and document the behavior & implementation.

    opened by mccolljr 1
  • Update `SegVec` sort API

    Update `SegVec` sort API

    1. Rename SegVec::sort* to SegVec::sort_unstable* to indicate that it is an unstable sort, to be more in line with the standard library.
    2. Update the signature of the function required by SegVec::sort_unstable_by to return a std::cmp::Ordering rather than a bool

    Partially addresses #3

    opened by mccolljr 0
  • Stable & unstable sort

    Stable & unstable sort

    Right now, sort is unstable. The API should match Vec here, so should be called sort_unstable and sort_unstable_by. Would also like to add sort and sort_by that are stable.

    opened by mccolljr 0
  • Audit & document `unsafe` usages

    Audit & document `unsafe` usages

    There are a few usages of unsafe - I tried to cover these cases in tests, but I need to make a pass through the code to add // Safety: ... comments + triple-check that things are doing exactly what I think they are.

    opened by mccolljr 0
  • Performance Improvements

    Performance Improvements

    Right now, the implementation is significantly slower than Vec for most things. This can be fixed.

    TODO:

    • [x] insert, remove, and drain can copy mem to avoid some iterative shifting.
    • [ ] sort implementation can be optimized, and should probably be more than a naive quicksort
    • [x] Use SegVec::with_capacity in FromIterator implementation
    opened by mccolljr 3
Owner
Jacob Ryan McCollum
Send me new programming languages.
Jacob Ryan McCollum
GitHub
Rust Vec Doubly Linked List

Rust Vec Doubly Linked List Just like doubly linked list(e.g. std::LinkedList), but supports that returning a index of the vec when push. And you can

~ 2 May 1, 2022
Rust implementation of Adobe's stlab::forest data structure

skog Swedish for "forest". A pure rust implementation of Adobe's stlab::forest data structure. Introduction A "forest" is a tree-like data structure.

Julian 1 Dec 8, 2021
Hypergraph is a data structure library to generate directed hypergraphs.

Hypergraph is data structure library to create a directed hypergraph in which a hyperedge can join any number of vertices.

Davy Duperron 112 Aug 24, 2021
A prefix tree (trie) is a data structure that allows you to store an associative array whose keys are strings

RadixTrie A prefix tree (trie) is a data structure that allows you to store an associative array whose keys are strings. It is a root tree, each edge

null 2 Jan 28, 2022
Message/job queue based on bonsaidb, similar to sqlxmq.

Bonsaimq Simple database message queue based on bonsaidb. The project is highly influenced by sqlxmq. Warning: This project is in early alpha and shou

Flix 6 Nov 8, 2022
NixEl is a Rust library that turns Nix code into a variety of correct, typed, memory-safe data-structures

?? NixEL Lexer, Parser, Abstract Syntax Tree and Concrete Syntax Tree for the Nix Expressions Language. NixEl is a Rust library that turns Nix code in

Kevin Amado 56 Dec 29, 2022
Garbage Collector(Hyaline- Safe Memory Reclaimation) for lock free data structures

Hyaline-SMR This crate provides garbage collection using hyaline algorithm for building concurrent data structures. When a thread removes an object fr

Abishek 2 Dec 21, 2022
Fast, efficient, and robust memory reclamation for concurrent data structures

Seize Fast, efficient, and robust memory reclamation for concurrent data structures. Introduction Concurrent data structures are faced with the proble

Ibraheem Ahmed 240 Dec 23, 2022
Sort (key, value) data sets that don't fit in memory

kv-par-merge-sort Key-Value Parallel Merge Sort Sort Pod (key, value) data sets that don't fit in memory. This crate provides the kv_par_merge_sort li

Duncan 1 Jun 28, 2022
A tree structure in Rust optimized for looking up domain names, with wildcard support

domain-lookup-tree Overview DomainLookupTree is a data structure which provides efficient domain name lookup matching with support for wildcard entrie

null 18 Nov 28, 2022
Redis Tree(Ploytree) Structure Module

RedisTree is a Redis module that implements Polytree as a native data type. It allows creating,locating,pushing and detaching tree from Redi

Bonsai 63 Dec 25, 2022
Rust-algorithm-club - Learn algorithms and data structures with Rust

Rust Algorithm Club ?? ?? This repo is under construction. Most materials are written in Chinese. Check it out here if you are able to read Chinese. W

Weihang Lo 360 Dec 28, 2022
Rust Persistent Data Structures

Rust Persistent Data Structures Rust Persistent Data Structures provides fully persistent data structures with structural sharing. Setup To use rpds a

Diogo Sousa 883 Dec 31, 2022
A proof of concept implementation of cyclic data structures in stable, safe, Rust.

A proof of concept implementation of cyclic data structures in stable, safe, Rust. This demonstrates the combined power of the static-rc crate and the

null 157 Dec 28, 2022
Rust library for string parsing of basic data structures.

afmt Simple rust library for parsing basic data structures from strings. Usage You can specify string formats to any strucute, via the use of the fmt

Eduard 4 May 8, 2021
Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

null 6.5k Dec 31, 2022
Algorithms and Data Structures of all kinds written in Rust.

Classic Algorithms in Rust This repo contains the implementation of various classic algorithms for educational purposes in Rust. Right now, it is in i

Alexander González 49 Dec 14, 2022
Library containing various Data Structures implemented using Rust.

rust-data-structures Library containing various Data Structures implemented using Rust. Running You can test the library by running cargo test, an exa

c1m50c 1 Jan 6, 2022
A library for comparing data structures in Rust, oriented toward testing

Delta: Structural differencing in Rust The delta crate defines the trait Delta, along with a derive macro for auto-generating instances of this trait

John Wiegley 19 Oct 7, 2022