Skip to content

Latest commit

 

History

History
387 lines (360 loc) · 13.3 KB

README.md

File metadata and controls

387 lines (360 loc) · 13.3 KB
Raw

source: https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Rust

VSCode toolage

1. refresher

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[should_panic(expected = "xxx")]
    fn do_something() {
        assert!(...);
    }
}
  • Option<T>, Result<T, E> - if let Some, match .. Some .. None, match .. Ok .. Err
  • vec![] macro:
#[macro_export]
macro_rules!
 vec {
     ( $( $x:expr ),* ) => {
         {             
	     let mut temp_vec = Vec::new();              
            $( temp_vec.push($x); )*      
            temp_vec
         }     
    }; 
}
  • #[derive(Clone, Debug)] - "{:?}"
  • Box, Rc
  • &x, mut, clone
fn f<'a>(mut pass_through: MyStruct<'a>, x: &'a Vec<u32>) -> MyStruct<'a> {
  • multiple owners:
use std::rc::Rc;

#[derive(Debug)]
struct FileName {
    name: Rc<String>,
    ext: Rc<String> 
}

fn ref_counter() {
    let name = Rc::new(String::from("main"));
    let ext = Rc::new(String::from("rs")));

    for _ in 0..3 {
        println!("{;?}", FileName {
                    name: name.clone(), 
                    ext: ext.clone() 
        });
    }
}
  • RefCell interior mutability - maintains single ownership of a value but allows mutable borrowing checked at runtime. Instead of compiler errors, violating rules of borrowing will lead to a runtime panic!, crashing the program. used in combination with Rc to provide a value to multiple owners with mutability. borrow_mut() - mutable reference only lives as long as the assignment
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Clone)]
struct Node {
    value: String,
    next: Link,
    prev: Link,
}


type Link = Option<Rc<RefCell<Node>>>;

pub fn append(&mut self, value: String) {
    let new = Rc::new(RefCell::new(Node::new(value)));
    match self.tail.take() {
        Some(old) => {
            old.borrow_mut().next = Some(new.clone());
            new.borrow_mut().prev = Some(old);
        }
        None => self.head = Some(new.clone()),
    };
}
use std::thread; 
use std::sync::{Mutex, Arc};
use std::sync::mpsc::{channel, Sender, Receiver};
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
...
fn main() {
    threading();
    shared_state();
    channels();
    ref_counter();
}
  • marker traits:
    • Send: type is safe to send (move) from one thread to the other
    • Sync: type can be shared across threads without Mutex

2. cargo refreher

  • doc tests
  • cargo config
  • cargo workspace
  • cargo flags:
    • --version
    • --list List installed commands
    • --explain <CODE> Run rustc --explain CODE
    • --verbose (-vv very verbose build.rs output)
    • --quiet
    • --color <WHEN>
    • --frozen Require Cargo.lock and cache are up to date
    • --locked Require Cargo.lock is up to date
    • -Z <FLAG>... Unstable (nightly-only) flags to Cargo
  • cargo commands:
    • build Compile
    • check Analyze, but don't build object files
    • clean Remove target directory
    • doc Build project + its dependencies' docs
    • new Create a new cargo project
    • init Create a new cargo project in an existing directory
    • run Build and execute src/main.rs
    • test Run tests
    • bench Run benchmarks - #[bench] is nightly unstable in RUst 2021
    • update Update dependencies listed in Cargo.lock
    • search Search registry for crates
    • publish Package as *.crate file and upload project to https://crates.io
    • yank prohibit updates to a particular published version
    • install Install a Rust binary
    • uninstall Uninstall a Rust binary
  • .cargo/config file: https://doc.rust-lang.org/cargo/reference/config.html
    • paths - local repos
    • [cargo-new] - commandline args
    • [registry] - remote repos
    • [http] - proxy address + port, cainfo, timeout
    • [build] - number of jobs, binaries (eg rustc, rustdoc), incremental compilation
  • Cargo.lock https://doc.rust-lang.org/cargo/faq.html provide deterministic builds of dependency versions. architecture specific. frozen unless you run cargo update
  • Cargo.toml manifest
    • package.metadata
    • [target.$triple]
      • eg [target.wasm32-unknown-unknown] for Wasm target via LLVM backend - has to be installed: rustup target add wasm32-unknown-unknown. wasm-bindgen https://github.com/rustwasm/wasm-bindgen
      • specify linker, ar (archiver), runner, compiler rustflags
      • compiled to target///
      • profiles:
      • [profile.dev] -> cargo build
      • [profile.release] -> cargo build --release
      • [profile.test] -> , cargo test
      • [profile.bench] -> cargo bench
      • defaults:
[profile.release] 
 opt-level = 3 
 debug = false 
 rpath = false 
 lto = false 
 debug-assertions = false
 codegen-units = 16
 panic = 'unwind'
 incremental = false
 overflow-checks = false
  • [dependencies]
[dependencies]
# import in Rust with "use x::*"
x = "*"
# (~): Only semver patch increases allowed
# (^): only semver minor increases allowed
# (*): semver major increases allowed. Note: isn't possible to cargo publish a crate with wildcard dependencies
y = { version = "0.5", optional = true } 
v = { git = "https://github.com/vvv", branch = "0.4" }
# import in Rust with "use z::*"
[dependencies.z]
version = "0.5"
features = ["www"] # only install subcomponents

[dev-dependencies]

[build-dependencies]

[workspace] 
members = [ "core", "web", "data"]
[build-dependencies] # no other dependencies allowed

extern "C" {
    fn imported_function() -> i32; # must be bound via the linker. call must be wrapped in an `unsafe` section
}

#[no_mangle]
pub extern "C" fn exported_function() -> i32 {      # no_mangle -> can be found using its name
    42
}

3. efficient storage refresher

  • stack - allows for zero overhead structures
  • heap - Types that don't have predictable sizes. objects wrapped into Rc, Cell, RefCell, or Box instances
  • store fixed-size reference &str to String heap-allocated value, along with metadata for length in bytes. Similar to pointers, a fixed-size view into a previously-unsized value.
  • mem::size_of
  • generics - equivelent:
fn f<T: MyTrait>(t: T) {}
fn f <T>(t: T) where T: MyTrait {}
fn f(t: impl MyTrait) {}
  • fn f(x: T) where T: Clone + Debug + MyTrait {}
  • Generic type parameters are Sized by default fn f <T: Sized>(t: T) {} - marker trait for mostly stack-allocated values is the default, can be relaxed to ?Sized
  • memory leaks are still possible in Rust via Rc
  • Box<dyn TheTrait> put a reference to a trait inside of a struct. dynamic dispatch: location is only known at runtime - vtable lookup is slower. use concrete types instead of traits to avoid multiple dereference operations
  • Copy via assignment for sized stack values is an implicit, bitwise copy. implement or derive #derive[Clone] for unsized heap refs clone()
  • std::borrow::Cow lazily clones a contained reference whenever mutation or ownership is requested https://doc.rust-lang.org/std/borrow/enum.Cow.html
  • Rust Persistent Data Structures (RPDS) https://crates.io/crates/rpds utilize copy-on-write with versioning to capture state changes. Persistent data structures: keep original data immutable and store versioned change sets.

4. lists

#[derive(Clone)]
struct Node {
    next: Vec<Link>,
    pub offset: u64,
    pub value: String,
}

#[derive(Clone)]
pub struct MySkipList {
    head: Link,
    tails: Vec<Link>,
    max_level: usize,
    pub length: u64,
}

fn get_level(&self) -> usize {
    let mut n = 0;
    // bool = p(true) = 0.5
    while rand::random::<bool>() && n < self.max_level {
        n += 1;
    }
    n
}
  • dynamic array
    • Box<[Node]>, vec! into_boxed_slice, clone_from_slice

5. Trees

  • tests
    • binary search tree
      • binary_search_tree_walk_in_order
      • binary_search_tree_find
    • red black tree
      • red_black_tree_add
      • red_black_tree_walk_in_order
      • red_black_tree_find
    • binary heap
      • binary_heap_add
      • binary_heap_pop
    • trie
      • trie_add
      • trie_walk_in_order
      • trie_find
    • btree
      • btree_add
      • btree_find
      • btree_walk_in_order
    • graphs
      • graph_insert_edges
      • graph_neighbors
      • graph_find_shortest_path
  • binary search tree
    • mem::replace
    • pass callback and build a vector by walking tree:
 walk(&self, callback: impl Fn(&T) -> ()) {   
    self.walk_in_order(&self.root, &callback);
}

fn walk_in_order(&self, node: &Tree, callback: &impl Fn(&T) -> ()) {
    if let Some(n) = node {
        self.walk_in_order(&n.left, callback);
        callback(&n.dev);
        self.walk_in_order(&n.right, callback);
    }
}

let items: RefCell<Vec<T>> = RefCell::new(vec![]);
tree.walk(|n|items.borrow_mut().push(n.clone()));
  • test with rand
    use rand::thread_rng;
    use rand::seq::SliceRandom;
    use rand::Rng;
    ...
        let mut items: Vec<T> = (0..len).map(new_item_with_id).collect();

        // let mut rng = thread_rng();
        // rng.shuffle(&mut items);
        items.shuffle(&mut thread_rng());

        for item in items.iter() {
            tree.add(item.clone());
        }

        assert_eq!(tree.length, len);
        let v: RefCell<Vec<T>> = RefCell::new(vec![]);
        tree.walk(|n| v.borrow_mut().push(n.clone()));
        let mut items = items;
        // sort in descending order:
        items.sort_by(|a, b| b.numerical_id.cmp(&a.numerical_id));
        assert_eq!(v.into_inner(), items)
  • random shuffle:
use rand::thread_rng;
use rand::seq::SliceRandom;
use rand::Rng;

let mut tree = btree::DeviceDatabase::new_empty(3);
let mut items: Vec<IoTDevice> = (0..len).map(new_device_with_id).collect();

items.shuffle(&mut thread_rng());

for item in items.iter() {
    tree.add(item.clone());
}
  • red-black tree
  • heap
    • Vec<T>.swap_remove() - remove 1st element of by replacing it with last element
  • trie
    • random gen_range:
use rand::thread_rng;
use rand::Rng;

let mut trie = trie::BestDeviceRegistry::new_empty();
let len = 10;

let mut rng = thread_rng();

for i in 0..len {
    trie.add(new_device_with_id_path(
        i,
        format!("factory{}/machineA/{}", rng.gen_range(0..len), i),
    ));
}
  • btree - implementation was complex :(
  • graphs - need to revise & deep dive