SHARE
TWEET

Untitled

a guest Jun 16th, 2019 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #![deny(elided_lifetimes_in_paths)]
  2.  
  3. use std::pin::Pin;
  4. use std::sync::RwLock;
  5. use std::hash::{Hash, Hasher};
  6. use std::collections::HashSet;
  7. use std::borrow::Borrow;
  8. use std::convert::Infallible;
  9.  
  10. #[derive(Debug, PartialEq, Eq, Hash)]
  11. struct Slot<'ctx>(Pin<Box<DAG<'ctx>>>);
  12.  
  13. pub struct Arena<'ctx>(RwLock<HashSet<Slot<'ctx>>>);
  14.  
  15. impl<'ctx> Borrow<DAG<'ctx>> for Slot<'ctx> {
  16.     fn borrow(&self) -> &DAG<'ctx> {
  17.         &self.0
  18.     }
  19. }
  20.  
  21. #[derive(Clone, Copy, Eq)]
  22. pub enum DAG<'ctx> {
  23.     Nil,
  24.     Branch {
  25.         value: u32,
  26.         left: &'ctx DAG<'ctx>,
  27.         right: &'ctx DAG<'ctx>,
  28.         pin: PhantomPinned
  29.     }
  30. }
  31.  
  32. use std::fmt;
  33.  
  34. impl fmt::Debug for DAG<'_> {
  35.     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  36.         match self {
  37.             DAG::Nil => write!(f, "Nil"),
  38.             DAG::Branch { value, left: DAG::Nil, right: DAG::Nil, .. } =>
  39.                 write!(f, "Graph({})", value),
  40.             DAG::Branch { value, left, right, .. } => {
  41.                 let mut debug = f.debug_struct("Graph");
  42.                 let mut debug = debug.field("value", value);
  43.        
  44.                 let mut debug = if let DAG::Nil = left {
  45.                     debug
  46.                 } else {
  47.                     debug.field("left", left)
  48.                 };
  49.                
  50.                 let mut debug = if let DAG::Nil = right {
  51.                     debug
  52.                 } else {
  53.                     debug.field("right", right)
  54.                 };
  55.                
  56.                 debug.finish()
  57.             }
  58.         }
  59.     }
  60. }
  61.  
  62. use std::marker::PhantomPinned;
  63.  
  64. impl<'a, 'b> PartialEq<DAG<'b>> for DAG<'a> {
  65.     fn eq(&self, other: &DAG<'b>) -> bool {
  66.         match (self, other) {
  67.             (DAG::Nil, DAG::Nil) => true,
  68.             (
  69.                 DAG::Branch { value: av, left: al, right: ar, .. },
  70.                 DAG::Branch { value: bv, left: bl, right: br, .. }
  71.             ) => {
  72.                 std::ptr::eq(al as &DAG<'_>, bl as &DAG<'_>) &&
  73.                 std::ptr::eq(ar as &DAG<'_>, br as &DAG<'_>) &&
  74.                 av == bv
  75.             },
  76.             _ => false
  77.         }
  78.     }
  79. }
  80.  
  81. impl Hash for DAG<'_> {
  82.     fn hash<H: Hasher>(&self, state: &mut H) {
  83.         match self {
  84.             DAG::Nil => state.write_u8(0),
  85.             DAG::Branch { value, left, right, .. } => {
  86.                 std::ptr::hash(left as &DAG<'_>, state);
  87.                 std::ptr::hash(right as &DAG<'_>, state);
  88.                 value.hash(state);
  89.             }
  90.         }
  91.     }
  92. }
  93.  
  94. impl Default for Arena<'_> {
  95.     fn default() -> Self {
  96.         Self::new()
  97.     }
  98. }
  99.  
  100. impl<'ctx> DAG<'ctx> {
  101.     pub fn branch(value: u32, left: &'ctx DAG<'ctx>, right: &'ctx DAG<'ctx>) -> Self {
  102.         DAG::Branch {
  103.             value,
  104.             left,
  105.             right,
  106.             pin: PhantomPinned
  107.         }
  108.     }
  109. }
  110.  
  111. impl<'ctx> Arena<'ctx> {
  112.     pub fn new() -> Self {
  113.         Self(RwLock::new(HashSet::new()))
  114.     }
  115.  
  116.     pub fn insert(&'ctx self, ty: DAG<'ctx>) -> &'ctx DAG<'ctx> {
  117.         let mut elements = self.0.write().unwrap();
  118.         let elements = &mut *elements;
  119.  
  120.         unsafe {
  121.             match elements.get(&ty).map(Slot::borrow) {
  122.                 Some(ty) => std::mem::transmute::<&DAG<'ctx>, &'ctx DAG<'ctx>>(ty),
  123.                 None => {
  124.                     elements.insert(Slot(Box::pin(ty)));
  125.  
  126.                     match elements.get(&ty).map(Slot::borrow) {
  127.                         Some(ty) => std::mem::transmute::<&DAG<'ctx>, &'ctx DAG<'ctx>>(ty),
  128.                         None => {
  129.                             debug_assert!(false, "get failed!");
  130.                             std::hint::unreachable_unchecked()
  131.                         }
  132.                     }
  133.                 }
  134.             }
  135.         }
  136.     }
  137.  
  138.     pub fn get(&'ctx self, ty: &DAG<'ctx>) -> Option<&'ctx DAG<'ctx>> {
  139.         let elements = self.0.read().unwrap();
  140.         let elements = &*elements;
  141.  
  142.         unsafe {
  143.             std::mem::transmute::<Option<&DAG<'ctx>>, Option<&'ctx DAG<'ctx>>>(
  144.                 elements.get(ty).map(Slot::borrow)
  145.             )
  146.         }
  147.     }
  148. }
  149.  
  150. fn main() {
  151.     let arena = Arena::new();
  152.  
  153.     let nil = arena.insert(DAG::Nil);
  154.     let _0 = arena.insert(DAG::branch(0, nil, nil));
  155.     let _1 = arena.insert(DAG::branch(1, nil, _0));
  156.     let _2 = arena.insert(DAG::branch(2, _0, _1));
  157.  
  158.     println!("{:?}", nil);
  159.     println!("{:?}", _0);
  160.     println!("{:?}", _1);
  161.     println!("{:?}", _2);
  162. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top