io_engine/
embedded_list.rs

1use std::{fmt, mem::transmute, ptr::null_mut};
2
3pub struct EmbeddedListNode {
4    pub prev: *mut EmbeddedListNode,
5    pub next: *mut EmbeddedListNode,
6    l: *mut EmbeddedList,
7}
8
9unsafe impl Sync for EmbeddedListNode {}
10unsafe impl Send for EmbeddedListNode {}
11
12impl Default for EmbeddedListNode {
13    #[inline(always)]
14    fn default() -> Self {
15        Self { prev: null_mut(), next: null_mut(), l: null_mut() }
16    }
17}
18
19impl fmt::Debug for EmbeddedListNode {
20    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
21        write!(f, "(")?;
22
23        if !self.prev.is_null() {
24            write!(f, "prev: {:p} ", self.prev)?;
25        } else {
26            write!(f, "prev: none ")?;
27        }
28
29        if !self.next.is_null() {
30            write!(f, "next: {:p} ", self.next)?;
31        } else {
32            write!(f, "next: none ")?;
33        }
34        write!(f, ")")
35    }
36}
37
38pub struct EmbeddedList {
39    length: u64,
40    head: *mut EmbeddedListNode,
41    tail: *mut EmbeddedListNode,
42    node_offset: usize,
43}
44
45unsafe impl Sync for EmbeddedList {}
46unsafe impl Send for EmbeddedList {}
47
48impl fmt::Debug for EmbeddedList {
49    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
50        write!(f, "{{ length: {} ", self.length)?;
51
52        if !self.head.is_null() {
53            write!(f, "head: {:?} ", self.head)?;
54        } else {
55            write!(f, "head: none ")?;
56        }
57
58        if !self.tail.is_null() {
59            write!(f, "tail: {:?} ", self.tail)?;
60        } else {
61            write!(f, "tail: none ")?;
62        }
63
64        write!(f, "}}")
65    }
66}
67
68impl EmbeddedList {
69    #[inline(always)]
70    pub fn new(node_offset: usize) -> Self {
71        EmbeddedList { length: 0, head: null_mut(), tail: null_mut(), node_offset }
72    }
73
74    #[inline]
75    pub fn clear(&mut self) {
76        self.length = 0;
77        self.head = null_mut();
78        self.tail = null_mut();
79    }
80
81    #[inline(always)]
82    fn to_item_mut<T>(&self, data: *mut EmbeddedListNode) -> *mut T {
83        let off = unsafe { transmute::<*mut EmbeddedListNode, usize>(data) };
84        (off - self.node_offset) as *mut T
85    }
86
87    #[inline(always)]
88    pub fn get_length(&self) -> u64 {
89        return self.length;
90    }
91
92    #[inline(always)]
93    pub fn len(&self) -> usize {
94        return self.length as usize;
95    }
96
97    #[inline(always)]
98    pub fn remove(&mut self, del: &mut EmbeddedListNode) {
99        if del.l != self {
100            return;
101        }
102        self.remove_node(del);
103    }
104
105    #[inline(always)]
106    fn remove_node(&mut self, del: &mut EmbeddedListNode) {
107        let prev = del.prev;
108        let next = del.next;
109        if prev.is_null() {
110            self.head = next;
111        } else {
112            unsafe {
113                (*prev).next = next;
114            }
115            del.prev = null_mut();
116        }
117        if next.is_null() {
118            self.tail = prev;
119        } else {
120            unsafe {
121                (*next).prev = prev;
122            }
123            del.next = null_mut();
124        }
125        del.l = null_mut();
126        debug_assert!(del.next.is_null());
127        debug_assert!(del.prev.is_null());
128        self.length -= 1;
129    }
130
131    #[inline(always)]
132    pub fn peak(&mut self, node: &mut EmbeddedListNode) {
133        let node_raw = node as *mut EmbeddedListNode;
134        let head = self.head;
135        if head == node_raw {
136            return;
137        }
138        debug_assert!(!head.is_null());
139        // remove node from current position
140        let prev = node.prev;
141        let next = node.next;
142        debug_assert!(!prev.is_null());
143        unsafe {
144            (*head).prev = node_raw;
145            (*prev).next = next;
146            if next.is_null() {
147                self.tail = prev;
148            } else {
149                (*next).prev = prev;
150            }
151        }
152        // insert to head
153        node.next = head;
154        node.prev = null_mut();
155        self.head = node_raw;
156    }
157
158    #[inline]
159    pub fn push_front(&mut self, new_node: &mut EmbeddedListNode) {
160        let head = self.head;
161        new_node.next = head;
162        new_node.l = self as *mut EmbeddedList;
163        new_node.prev = null_mut();
164        if head.is_null() {
165            self.tail = new_node as *mut EmbeddedListNode;
166        } else {
167            unsafe {
168                (*head).prev = new_node as *mut EmbeddedListNode;
169            }
170        }
171        self.head = new_node as *mut EmbeddedListNode;
172        self.length += 1;
173    }
174
175    #[inline]
176    pub fn push_back(&mut self, new_node: &mut EmbeddedListNode) {
177        let tail = self.tail;
178        // push back node, set node.prev = list.tail and node.next = None
179        new_node.prev = tail;
180        new_node.l = self as *mut EmbeddedList;
181        new_node.next = null_mut();
182
183        if tail.is_null() {
184            self.head = new_node as *mut EmbeddedListNode;
185        } else {
186            unsafe {
187                (*tail).next = new_node as *mut EmbeddedListNode;
188            }
189        }
190        self.tail = new_node as *mut EmbeddedListNode;
191        self.length += 1;
192    }
193
194    #[inline]
195    pub fn pop_back<T>(&mut self) -> Option<*mut T> {
196        if self.tail.is_null() {
197            None
198        } else {
199            let item = self.to_item_mut(self.tail);
200            self.remove_node(unsafe { transmute(self.tail) });
201            Some(item)
202        }
203    }
204
205    #[inline]
206    pub fn pop_front<T>(&mut self) -> Option<*mut T> {
207        if self.head.is_null() {
208            None
209        } else {
210            let item = self.to_item_mut(self.head);
211            self.remove_node(unsafe { transmute(self.head) });
212            Some(item)
213        }
214    }
215
216    #[inline]
217    pub fn get_front<T>(&self) -> Option<&mut T> {
218        if self.head.is_null() {
219            None
220        } else {
221            Some(unsafe { transmute(self.to_item_mut::<T>(self.head)) })
222        }
223    }
224
225    #[inline]
226    pub fn get_back<T>(&self) -> Option<&mut T> {
227        if self.tail.is_null() {
228            None
229        } else {
230            Some(unsafe { transmute(self.to_item_mut::<T>(self.tail)) })
231        }
232    }
233
234    #[inline(always)]
235    pub fn remove_front(&mut self) {
236        if !self.head.is_null() {
237            self.remove_node(unsafe { transmute(self.head) });
238        }
239    }
240
241    #[inline(always)]
242    pub fn remove_back(&mut self) {
243        if !self.tail.is_null() {
244            self.remove_node(unsafe { transmute(self.tail) });
245        }
246    }
247
248    #[inline(always)]
249    pub fn is_front(&self, node: &mut EmbeddedListNode) -> bool {
250        if self.head.is_null() {
251            return false;
252        } else {
253            return self.head == node as *mut EmbeddedListNode;
254        }
255    }
256
257    #[inline]
258    pub fn has_node(&self, node: &EmbeddedListNode) -> bool {
259        node.l as *const EmbeddedList == self as *const EmbeddedList
260    }
261
262    pub fn print<T: std::fmt::Debug>(&self) {
263        println!("print list begin! length={}", self.length);
264        let mut node = self.head;
265        while !node.is_null() {
266            unsafe {
267                let node_item = self.to_item_mut::<T>(node);
268                println!("node={:?}", *node_item);
269                node = (*node).next;
270            }
271        }
272        println!("print list end:");
273    }
274
275    // NOTE: If you plan on turn the raw pointer to owned, use drain instead
276    #[inline(always)]
277    pub fn iter<'a, T>(&'a self) -> EmbeddedListIterator<'a, T> {
278        EmbeddedListIterator { list: self, cur: null_mut(), phan: Default::default() }
279    }
280
281    #[inline(always)]
282    pub fn drain<'a, T>(&'a mut self) -> EmbeddedListDrainer<'a, T> {
283        EmbeddedListDrainer { list: self, phan: Default::default() }
284    }
285}
286
287pub struct EmbeddedListIterator<'a, T> {
288    list: &'a EmbeddedList,
289    cur: *mut EmbeddedListNode,
290    phan: std::marker::PhantomData<T>,
291}
292
293unsafe impl<'a, T> Sync for EmbeddedListIterator<'a, T> {}
294unsafe impl<'a, T> Send for EmbeddedListIterator<'a, T> {}
295
296impl<'a, T> Iterator for EmbeddedListIterator<'a, T> {
297    type Item = *mut T;
298
299    fn next(&mut self) -> Option<*mut T> {
300        if self.cur == null_mut() {
301            if self.list.head == null_mut() {
302                return None;
303            } else {
304                self.cur = self.list.head;
305                Some(self.list.to_item_mut::<T>(self.cur))
306            }
307        } else {
308            let next = unsafe { (*self.cur).next };
309            if next == null_mut() {
310                None
311            } else {
312                self.cur = next;
313                Some(self.list.to_item_mut::<T>(self.cur))
314            }
315        }
316    }
317}
318
319pub struct EmbeddedListDrainer<'a, T> {
320    list: &'a mut EmbeddedList,
321    phan: std::marker::PhantomData<T>,
322}
323
324unsafe impl<'a, T> Sync for EmbeddedListDrainer<'a, T> {}
325unsafe impl<'a, T> Send for EmbeddedListDrainer<'a, T> {}
326
327impl<'a, T> Iterator for EmbeddedListDrainer<'a, T> {
328    type Item = *mut T;
329
330    #[inline]
331    fn next(&mut self) -> Option<*mut T> {
332        self.list.pop_front::<T>()
333    }
334}
335
336#[cfg(test)]
337mod tests {
338    use super::*;
339
340    pub struct IntListNode {
341        pub value: i64,
342        pub node: EmbeddedListNode,
343    }
344
345    impl fmt::Debug for IntListNode {
346        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
347            write!(f, "{} {:#?}", self.value, self.node)
348        }
349    }
350
351    impl fmt::Display for IntListNode {
352        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
353            write!(f, "{}", self.value)
354        }
355    }
356
357    type IntLinkList = EmbeddedList;
358
359    fn new_intnode(i: i64) -> Box<IntListNode> {
360        Box::new(IntListNode { node: EmbeddedListNode::default(), value: i })
361    }
362
363    fn new_intlist() -> IntLinkList {
364        let off = std::mem::offset_of!(IntListNode, node);
365        EmbeddedList::new(off)
366    }
367
368    #[test]
369    fn list_push_back() {
370        println!();
371        let mut l = new_intlist();
372        println!("empty list:{:?}", l);
373        let mut node1 = new_intnode(1);
374        l.push_back(&mut node1.node);
375        let mut node2 = new_intnode(2);
376        l.push_back(&mut node2.node);
377        let mut node3 = new_intnode(3);
378        l.push_back(&mut node3.node);
379        println!("list:{:?}", l);
380        l.print::<IntListNode>();
381
382        assert_eq!(3, l.get_length());
383
384        // node1.prev = None and node1.next = node2
385        assert!(node1.node.prev.is_null());
386        assert_eq!(node1.node.next, &mut node2.node as *mut EmbeddedListNode);
387
388        // node2.prev = node1 and node2.next = node3
389        assert_eq!(node2.node.prev, &mut node1.node as *mut EmbeddedListNode);
390        assert_eq!(node2.node.next, &mut node3.node as *mut EmbeddedListNode);
391
392        // node3.prev = node2 and node3.next = None
393        assert_eq!(node3.node.prev, &mut node2.node as *mut EmbeddedListNode);
394        assert!(node3.node.next.is_null());
395
396        assert!(l.is_front(&mut node1.node));
397
398        // peak node2
399        l.peak(&mut node2.node);
400        println!("list:{:?}", l);
401        l.print::<IntListNode>();
402
403        // node2.prev = None and node2.next = node1
404        assert!(node2.node.prev.is_null());
405        assert_eq!(node2.node.next, &mut node1.node as *mut EmbeddedListNode);
406
407        // node1.prev = node2 and node1.next = node3
408        assert_eq!(node1.node.prev, &mut node2.node as *mut EmbeddedListNode);
409        assert_eq!(node1.node.next, &mut node3.node as *mut EmbeddedListNode);
410
411        // node3.prev = node1 and node3.next = None
412        assert_eq!(node3.node.prev, &mut node1.node as *mut EmbeddedListNode);
413        assert!(node3.node.next.is_null());
414
415        assert!(l.is_front(&mut node2.node));
416
417        // peak node3
418        l.peak(&mut node3.node);
419        println!("list:{:?}", l);
420        l.print::<IntListNode>();
421
422        // node3.prev = None and node3.next = node2
423        assert!(node3.node.prev.is_null());
424        assert_eq!(node3.node.next, &mut node2.node as *mut EmbeddedListNode);
425
426        // node2.prev = node3 and node2.next = node1
427        assert_eq!(node2.node.prev, &mut node3.node as *mut EmbeddedListNode);
428        assert_eq!(node2.node.next, &mut node1.node as *mut EmbeddedListNode);
429
430        // node1.prev = node2 and node1.next = None
431        assert_eq!(node1.node.prev, &mut node2.node as *mut EmbeddedListNode);
432        assert!(node1.node.next.is_null());
433
434        assert!(l.is_front(&mut node3.node));
435
436        // peak node3 again
437        l.peak(&mut node3.node);
438        println!("list:{:?}", l);
439        l.print::<IntListNode>();
440
441        // node3.prev = None and node3.next = node2
442        assert!(node3.node.prev.is_null());
443        assert_eq!(node3.node.next, &mut node2.node as *mut EmbeddedListNode);
444
445        // node2.prev = node3 and node2.next = node1
446        assert_eq!(node2.node.prev, &mut node3.node as *mut EmbeddedListNode);
447        assert_eq!(node2.node.next, &mut node1.node as *mut EmbeddedListNode);
448
449        // node1.prev = node2 and node1.next = None
450        assert_eq!(node1.node.prev, &mut node2.node as *mut EmbeddedListNode);
451        assert!(node1.node.next.is_null());
452
453        assert!(l.is_front(&mut node3.node));
454    }
455
456    #[test]
457    fn list_push_front() {
458        println!();
459        let mut l = new_intlist();
460        println!("empty list:{:?}", l);
461        let mut node3 = new_intnode(3);
462        l.push_front(&mut node3.node);
463        let mut node2 = new_intnode(2);
464        l.push_front(&mut node2.node);
465        let mut node1 = new_intnode(1);
466        l.push_front(&mut node1.node);
467        println!("list:{:?}", l);
468        l.print::<IntListNode>();
469
470        assert_eq!(3, l.get_length());
471
472        // node1.prev = None and node1.next = node2
473        assert!(node1.node.prev.is_null());
474        assert_eq!(node1.node.next, &mut node2.node as *mut EmbeddedListNode);
475
476        // node2.prev = node1 and node2.next = node3
477        assert_eq!(node2.node.prev, &mut node1.node as *mut EmbeddedListNode);
478        assert_eq!(node2.node.next, &mut node3.node as *mut EmbeddedListNode);
479
480        // node3.prev = node2 and node3.next = None
481        assert_eq!(node3.node.prev, &mut node2.node as *mut EmbeddedListNode);
482        assert!(node3.node.next.is_null());
483
484        assert!(l.is_front(&mut node1.node));
485    }
486
487    #[test]
488    fn list_remove_node() {
489        println!();
490        let mut l = new_intlist();
491        println!("empty list:{:?}", l);
492        let mut node1 = new_intnode(1);
493        l.push_back(&mut node1.node);
494        let mut node2 = new_intnode(2);
495        l.push_back(&mut node2.node);
496        let mut node3 = new_intnode(3);
497        l.push_back(&mut node3.node);
498        println!("list:{:?}", l);
499        l.print::<IntListNode>();
500
501        assert_eq!(3, l.get_length());
502
503        // remove node2
504        l.remove(&mut node2.node);
505        assert_eq!(2, l.get_length());
506        println!("after remove node2...");
507        println!("list:{:?}", l);
508        l.print::<IntListNode>();
509
510        // node1.prev = None and node1.next = node3
511        assert!(node1.node.prev.is_null());
512        assert_eq!(node1.node.next, &mut node3.node as *mut EmbeddedListNode);
513
514        // node2 = None
515        assert!(node2.node.prev.is_null());
516        assert!(node2.node.next.is_null());
517
518        // node3.prev = node1 and node3.next = None
519        assert_eq!(node3.node.prev, &mut node1.node as *mut EmbeddedListNode);
520        assert!(node3.node.next.is_null());
521
522        // list.head = node1 and list.tail = node3
523        assert_eq!(l.head, &mut node1.node as *mut EmbeddedListNode);
524        assert_eq!(l.tail, &mut node3.node as *mut EmbeddedListNode);
525
526        // remove node1
527        l.remove(&mut node1.node);
528        assert_eq!(1, l.get_length());
529        println!("after remove node1...");
530        println!("list:{:?}", l);
531        l.print::<IntListNode>();
532
533        // node1 = None
534        assert!(node1.node.prev.is_null());
535        assert!(node1.node.next.is_null());
536
537        // node3.prev = None and node3.next = None
538        assert!(node3.node.prev.is_null());
539        assert!(node3.node.next.is_null());
540
541        // list.head = node3 and list.tail = node3
542        assert_eq!(l.head, &mut node3.node as *mut EmbeddedListNode);
543        assert_eq!(l.tail, &mut node3.node as *mut EmbeddedListNode);
544
545        assert!(node1.node.l.is_null());
546        // remove node not in this list
547        l.remove(&mut node1.node);
548        assert_eq!(1, l.get_length());
549
550        // remove node3
551        l.remove(&mut node3.node);
552        assert_eq!(0, l.get_length());
553        println!("after remove node3...");
554        println!("list:{:?}", l);
555        l.print::<IntListNode>();
556
557        // node3.prev = None and node3.next = None
558        assert!(node3.node.prev.is_null());
559        assert!(node3.node.next.is_null());
560
561        // list.head = None and list.tail = None
562        assert!(l.head.is_null());
563        assert!(l.tail.is_null());
564    }
565
566    #[test]
567    fn list_pop_front() {
568        println!();
569        let mut l = new_intlist();
570        println!("empty list:{:?}", l);
571        let mut node1 = new_intnode(1);
572        l.push_back(&mut node1.node);
573        let mut node2 = new_intnode(2);
574        l.push_back(&mut node2.node);
575        let mut node3 = new_intnode(3);
576        l.push_back(&mut node3.node);
577        println!("list:{:?}", l);
578        l.print::<IntListNode>();
579
580        let del_node = l.pop_front::<IntListNode>();
581        assert_eq!(2, l.get_length());
582        println!("after pop front...");
583        println!("list:{:?}", l);
584        l.print::<IntListNode>();
585
586        assert!(del_node.is_some());
587        unsafe {
588            assert_eq!((*del_node.unwrap()).value, 1);
589        }
590
591        // list.head = node2 and list.tail = node3
592        assert_eq!(l.head, &mut node2.node as *mut EmbeddedListNode);
593        assert_eq!(l.tail, &mut node3.node as *mut EmbeddedListNode);
594    }
595
596    #[test]
597    fn list_pop_back() {
598        println!();
599        let mut l = new_intlist();
600        println!("empty list:{:?}", l);
601        let mut node1 = new_intnode(1);
602        l.push_back(&mut node1.node);
603        let mut node2 = new_intnode(2);
604        l.push_back(&mut node2.node);
605        let mut node3 = new_intnode(3);
606        l.push_back(&mut node3.node);
607        println!("list:{:?}", l);
608        l.print::<IntListNode>();
609
610        let del_node = l.pop_back::<IntListNode>();
611        assert_eq!(2, l.get_length());
612        println!("after pop back...");
613        println!("list:{:?}", l);
614        l.print::<IntListNode>();
615
616        // del node is node3
617        assert!(del_node.is_some());
618        unsafe {
619            assert_eq!((*del_node.unwrap()).value, 3);
620        }
621
622        // list.head = node1 and list.tail = node2
623        assert_eq!(l.head, &mut node1.node as *mut EmbeddedListNode);
624        assert_eq!(l.tail, &mut node2.node as *mut EmbeddedListNode);
625    }
626
627    #[test]
628    fn list_iter() {
629        println!();
630        let mut l = new_intlist();
631        let mut count = 0;
632        for _item in l.iter::<IntListNode>() {
633            count += 1;
634        }
635        assert_eq!(count, 0);
636        let mut node1 = new_intnode(1);
637        l.push_back(&mut node1.node);
638        let mut node2 = new_intnode(2);
639        l.push_back(&mut node2.node);
640        let mut node3 = new_intnode(3);
641        l.push_back(&mut node3.node);
642        for _item in l.iter::<IntListNode>() {
643            count += 1;
644            println!("{}", unsafe { (*_item).value });
645        }
646        assert_eq!(count, 3);
647    }
648
649    #[test]
650    fn push_front_pop_front_one() {
651        let mut l = new_intlist();
652        let mut node1 = new_intnode(1);
653        l.push_front(&mut node1.node);
654        let del_node = l.pop_front::<IntListNode>();
655        unsafe {
656            assert_eq!((*del_node.unwrap()).value, 1);
657        }
658        assert_eq!(0, l.get_length());
659        assert!(l.pop_front::<IntListNode>().is_none());
660    }
661
662    #[test]
663    fn push_front_pop_back_one() {
664        let mut l = new_intlist();
665        let mut node1 = new_intnode(1);
666        l.push_front(&mut node1.node);
667        let del_node = l.pop_back::<IntListNode>();
668        unsafe {
669            assert_eq!((*del_node.unwrap()).value, 1);
670        }
671        assert_eq!(0, l.get_length());
672        assert!(l.pop_front::<IntListNode>().is_none());
673    }
674
675    #[test]
676    fn push_back_pop_front_one() {
677        let mut l = new_intlist();
678        let mut node1 = new_intnode(1);
679        l.push_back(&mut node1.node);
680        let del_node = l.pop_front::<IntListNode>();
681        unsafe {
682            assert_eq!((*del_node.unwrap()).value, 1);
683        }
684        assert_eq!(0, l.get_length());
685        assert!(l.pop_front::<IntListNode>().is_none());
686    }
687
688    #[test]
689    fn push_back_pop_back_one() {
690        let mut l = new_intlist();
691        let mut node1 = new_intnode(1);
692        l.push_back(&mut node1.node);
693        let del_node = l.pop_back::<IntListNode>();
694        unsafe {
695            assert_eq!((*del_node.unwrap()).value, 1);
696        }
697        assert_eq!(0, l.get_length());
698        assert!(l.pop_back::<IntListNode>().is_none());
699    }
700}
io_engine/embedded_list.rs

io_engine/
embedded_list.rs
