From dd14e61875eedc443d6004db819562a9b7f98a14 Mon Sep 17 00:00:00 2001 From: "Tim \"S.D.Eagle\" Zeitz" Date: Mon, 15 Oct 2018 17:09:20 +0200 Subject: [PATCH 1/1] Initial commit --- .gitignore | 2 + Cargo.lock | 53 +++++++++++ Cargo.toml | 7 ++ src/index_heap.rs | 222 ++++++++++++++++++++++++++++++++++++++++++++++ src/io.rs | 67 ++++++++++++++ src/main.rs | 33 +++++++ src/time.rs | 45 ++++++++++ src/types.rs | 10 +++ 8 files changed, 439 insertions(+) create mode 100644 .gitignore create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 src/index_heap.rs create mode 100644 src/io.rs create mode 100644 src/main.rs create mode 100644 src/time.rs create mode 100644 src/types.rs diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..53eaa21 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +/target +**/*.rs.bk diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..bc66e43 --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,53 @@ +[[package]] +name = "libc" +version = "0.2.43" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "redox_syscall" +version = "0.1.40" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "stud-rust-base" +version = "0.1.0" +dependencies = [ + "time 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "time" +version = "0.1.40" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "libc 0.2.43 (registry+https://github.com/rust-lang/crates.io-index)", + "redox_syscall 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "winapi" +version = "0.3.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[metadata] +"checksum libc 0.2.43 (registry+https://github.com/rust-lang/crates.io-index)" = "76e3a3ef172f1a0b9a9ff0dd1491ae5e6c948b94479a3021819ba7d860c8645d" +"checksum redox_syscall 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)" = "c214e91d3ecf43e9a4e41e578973adeb14b474f2bee858742d127af75a0112b1" +"checksum time 0.1.40 (registry+https://github.com/rust-lang/crates.io-index)" = "d825be0eb33fda1a7e68012d51e9c7f451dc1a69391e7fdc197060bb8c56667b" +"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0" +"checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" +"checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..efe5553 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,7 @@ +[package] +name = "stud-rust-base" +version = "0.1.0" +authors = ["Tim Zeitz "] + +[dependencies] +time = "0.1.40" diff --git a/src/index_heap.rs b/src/index_heap.rs new file mode 100644 index 0000000..2f608d9 --- /dev/null +++ b/src/index_heap.rs @@ -0,0 +1,222 @@ +use std; +use std::cmp::min; +use std::mem::swap; +use std::ptr; + +pub trait Indexing { + fn as_index(&self) -> usize; +} + +// A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor. +// The elements are sorted by integer keys. +#[derive(Debug)] +pub struct IndexdMinHeap { + positions: Vec, + data: Vec +} + +const TREE_ARITY: usize = 4; +const INVALID_POSITION: usize = std::usize::MAX; + +impl IndexdMinHeap { + #[allow(dead_code)] + pub fn new(max_id: usize) -> IndexdMinHeap { + IndexdMinHeap { + positions: vec![INVALID_POSITION; max_id], + data: Vec::new() + } + } + + pub fn len(&self) -> usize { + self.data.len() + } + + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + #[allow(dead_code)] + pub fn contains_index(&self, id: usize) -> bool { + self.positions[id] != INVALID_POSITION + } + + #[allow(dead_code)] + pub fn clear(&mut self) { + for element in &self.data { + self.positions[element.as_index()] = INVALID_POSITION; + } + self.data.clear(); + } + + #[allow(dead_code)] + pub fn peek(&self) -> Option<&T> { + self.data.first() + } + + #[allow(dead_code)] + pub fn pop(&mut self) -> Option { + self.data.pop().map(|mut item| { + self.positions[item.as_index()] = INVALID_POSITION; + if !self.is_empty() { + self.positions[item.as_index()] = 0; + self.positions[self.data[0].as_index()] = INVALID_POSITION; + swap(&mut item, &mut self.data[0]); + self.move_down_in_tree(0); + } + item + }) + } + + #[allow(dead_code)] + pub fn push(&mut self, element: T) { + assert!(!self.contains_index(element.as_index())); + let insert_position = self.len(); + self.positions[element.as_index()] = insert_position; + self.data.push(element); + self.move_up_in_tree(insert_position); + } + + // Updates the key of an element if the new key is smaller than the old key. + // Does nothing if the new key is larger. + // Undefined if the element is not part of the queue. + #[allow(dead_code)] + pub fn decrease_key(&mut self, element: T) { + let position = self.positions[element.as_index()]; + self.data[position] = element; + self.move_up_in_tree(position); + } + + // Updates the key of an element if the new key is larger than the old key. + // Does nothing if the new key is smaller. + // Undefined if the element is not part of the queue. + #[allow(dead_code)] + pub fn increase_key(&mut self, element: T) { + let position = self.positions[element.as_index()]; + self.data[position] = element; + self.move_down_in_tree(position); + } + + fn move_up_in_tree(&mut self, position: usize) { + unsafe { + let mut position = position; + let mut hole = Hole::new(&mut self.data, position); + + while position > 0 { + let parent = (position - 1) / TREE_ARITY; + + if hole.get(parent) < hole.element() { + break; + } + + self.positions[hole.get(parent).as_index()] = position; + hole.move_to(parent); + position = parent; + } + + self.positions[hole.element().as_index()] = position; + } + } + + fn move_down_in_tree(&mut self, position: usize) { + unsafe { + let mut position = position; + let heap_size = self.len(); + let mut hole = Hole::new(&mut self.data, position); + + loop { + if let Some(smallest_child) = IndexdMinHeap::::children_index_range(position, heap_size).min_by_key(|&child_index| hole.get(child_index)) { + if hole.get(smallest_child) >= hole.element() { + self.positions[hole.element().as_index()] = position; + return; // no child is smaller + } + + self.positions[hole.get(smallest_child).as_index()] = position; + hole.move_to(smallest_child); + position = smallest_child; + } else { + self.positions[hole.element().as_index()] = position; + return; // no children at all + } + } + } + } + + fn children_index_range(parent_index: usize, heap_size: usize) -> std::ops::Range { + let first_child = TREE_ARITY * parent_index + 1; + let last_child = min(TREE_ARITY * parent_index + TREE_ARITY + 1, heap_size); + first_child..last_child + } +} + + +// This is an optimization copied straight from the rust stdlib binary heap +// it allows to avoid always swapping elements pairwise and rather +// move each element only once. + + +/// Hole represents a hole in a slice i.e. an index without valid value +/// (because it was moved from or duplicated). +/// In drop, `Hole` will restore the slice by filling the hole +/// position with the value that was originally removed. +struct Hole<'a, T: 'a> { + data: &'a mut [T], + /// `elt` is always `Some` from new until drop. + elt: Option, + pos: usize, +} + +impl<'a, T> Hole<'a, T> { + /// Create a new Hole at index `pos`. + /// + /// Unsafe because pos must be within the data slice. + #[inline] + unsafe fn new(data: &'a mut [T], pos: usize) -> Self { + debug_assert!(pos < data.len()); + let elt = ptr::read(&data[pos]); + Hole { + data, + elt: Some(elt), + pos, + } + } + + /// Returns a reference to the element removed. + #[inline] + fn element(&self) -> &T { + self.elt.as_ref().unwrap() + } + + /// Returns a reference to the element at `index`. + /// + /// Unsafe because index must be within the data slice and not equal to pos. + #[inline] + unsafe fn get(&self, index: usize) -> &T { + debug_assert!(index != self.pos); + debug_assert!(index < self.data.len()); + self.data.get_unchecked(index) + } + + /// Move hole to new location + /// + /// Unsafe because index must be within the data slice and not equal to pos. + #[inline] + unsafe fn move_to(&mut self, index: usize) { + debug_assert!(index != self.pos); + debug_assert!(index < self.data.len()); + let index_ptr: *const _ = self.data.get_unchecked(index); + let hole_ptr = self.data.get_unchecked_mut(self.pos); + ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1); + self.pos = index; + } +} + +impl<'a, T> Drop for Hole<'a, T> { + #[inline] + fn drop(&mut self) { + // fill the hole again + unsafe { + let pos = self.pos; + ptr::write(self.data.get_unchecked_mut(pos), self.elt.take().unwrap()); + } + } +} diff --git a/src/io.rs b/src/io.rs new file mode 100644 index 0000000..489d9e0 --- /dev/null +++ b/src/io.rs @@ -0,0 +1,67 @@ +use std::fs; +use std::fs::File; +use std::io::prelude::*; +use std::io::Result; +use std::mem; +use std::slice; + +pub trait DataBytes { + fn data_bytes(&self) -> &[u8]; +} + +pub trait DataBytesMut { + fn data_bytes_mut(&mut self) -> &mut [u8]; +} + +impl DataBytes for [T] { + fn data_bytes(&self) -> &[u8] { + let num_bytes = self.len() * mem::size_of::(); + unsafe { slice::from_raw_parts(self.as_ptr() as *const u8, num_bytes) } + } +} + +impl DataBytesMut for [T] { + fn data_bytes_mut(&mut self) -> &mut [u8] { + let num_bytes = self.len() * mem::size_of::(); + unsafe { slice::from_raw_parts_mut(self.as_mut_ptr() as *mut u8, num_bytes) } + } +} + +impl DataBytesMut for Vec { + fn data_bytes_mut(&mut self) -> &mut [u8] { + let num_bytes = self.len() * mem::size_of::(); + unsafe { slice::from_raw_parts_mut(self.as_mut_ptr() as *mut u8, num_bytes) } + } +} + +pub trait Store : DataBytes { + fn write_to(&self, filename: &str) -> Result<()> { + File::create(filename)?.write_all(self.data_bytes()) + } +} + +impl Store for T {} +impl Store for [T] where [T]: DataBytes {} + +pub trait Load : DataBytesMut + Sized { + fn new_with_bytes(num_bytes: usize) -> Self; + + fn load_from(filename: &str) -> Result { + let metadata = fs::metadata(filename)?; + let mut file = File::open(filename)?; + + let mut object = Self::new_with_bytes(metadata.len() as usize); + assert_eq!(metadata.len() as usize, object.data_bytes_mut().len()); + file.read_exact(object.data_bytes_mut())?; + + Ok(object) + } +} + +impl Load for Vec { + fn new_with_bytes(num_bytes: usize) -> Self { + assert_eq!(num_bytes % mem::size_of::(), 0); + let num_elements = num_bytes / mem::size_of::(); + (0..num_elements).map(|_| T::default()).collect() + } +} diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..c920768 --- /dev/null +++ b/src/main.rs @@ -0,0 +1,33 @@ +extern crate time as time_crate; + +mod index_heap; +mod io; +mod time; +mod types; + +use types::*; +use io::*; +use time::*; + +use std::{env, path::Path}; + +fn main() { + let mut args = env::args(); + args.next(); + + let arg = &args.next().expect("No directory arg given"); + let path = Path::new(arg); + + let first_out: Vec = Vec::load_from(path.join("first_out").to_str().unwrap()).expect("could not read first_out"); + let head: Vec = Vec::load_from(path.join("head").to_str().unwrap()).expect("could not read head"); + let travel_time: Vec = Vec::load_from(path.join("travel_time").to_str().unwrap()).expect("could not read travel_time"); + + report_time("iterating over arcs of some node", || { + let node_id = 42; + for &edge_id in &head[first_out[node_id] as usize .. first_out[node_id + 1] as usize] { + println!("There is an arc from {} to {} with weight {}", node_id, head[edge_id as usize], travel_time[edge_id as usize]); + } + }); + + vec![42; 42].write_to(path.join("distances").to_str().unwrap()).expect("could not write distances"); +} diff --git a/src/time.rs b/src/time.rs new file mode 100644 index 0000000..2f6e9ac --- /dev/null +++ b/src/time.rs @@ -0,0 +1,45 @@ +use time_crate as time; + +#[allow(dead_code)] +pub fn report_time Out>(name: &str, f: F) -> Out { + let start = time::now(); + println!("starting {}", name); + let res = f(); + println!("done {} - took: {}", name, (time::now() - start)); + res +} + +#[allow(dead_code)] +pub fn measure Out>(f: F) -> (Out, time::Duration) { + let start = time::now(); + let res = f(); + (res, time::now() - start) +} + +#[allow(dead_code)] +#[derive(Debug)] +pub struct Timer { + start: time::Tm +} + +impl Timer { + #[allow(dead_code)] + pub fn new() -> Timer { + Timer { start: time::now() } + } + + #[allow(dead_code)] + pub fn restart(&mut self) { + self.start = time::now(); + } + + #[allow(dead_code)] + pub fn report_passed_ms(&self) { + println!("{}ms", (time::now() - self.start).num_milliseconds()); + } + + #[allow(dead_code)] + pub fn get_passed_ms(&self) -> i64 { + (time::now() - self.start).num_milliseconds() + } +} diff --git a/src/types.rs b/src/types.rs new file mode 100644 index 0000000..bb11a00 --- /dev/null +++ b/src/types.rs @@ -0,0 +1,10 @@ +use std; + +#[allow(dead_code)] +pub type NodeId = u32; +#[allow(dead_code)] +pub type EdgeId = u32; +#[allow(dead_code)] +pub type Weight = u32; +#[allow(dead_code)] +pub const INFINITY: Weight = std::u32::MAX / 2; -- 2.34.1