Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 iakovlev.org 
 Languages
 С
 GNU С Library 
 Qt 
 STL 
 Threads 
 C++ 
 Samples 
 stanford.edu 
 ANSI C
 Libs
 LD
 Socket
 Pusher
 Pipes
 Encryption
 Plugin
 Inter-Process
 Errors
 Deep C Secrets
 C + UNIX
 Linked Lists / Trees
 Asm
 Perl
 Python
 Shell
 Erlang
 Go
 Rust
 Алгоритмы
NEWS
Последние статьи :
  Тренажёр 16.01   
  Эльбрус 05.12   
  Алгоритмы 12.04   
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
 
TOP 20
 MINIX...3057 
 Solaris...2933 
 LD...2904 
 Linux Kernel 2.6...2470 
 William Gropp...2180 
 Rodriguez 6...2011 
 C++ Templates 3...1945 
 Trees...1937 
 Kamran Husain...1865 
 Secure Programming for Li...1791 
 Максвелл 5...1710 
 DevFS...1693 
 Part 3...1682 
 Stein-MacEachern-> Час...1632 
 Go Web ...1624 
 Ethreal 4...1618 
 Arrays...1606 
 Стивенс 9...1603 
 Максвелл 1...1592 
 FAQ...1538 
 
  01.01.2024 : 3621733 посещений 

iakovlev.org

Связные списки в Rust

Это перевод документации, которая лежит тут

Исходники к данной статье можно взять тут

Реализация связных списков на расте - не самая простая задача. Для этого нужно разбираться в таких аспектах языка, как:
различные типы указателей: &, &mut, Box, Rc, Arc, *const, *mut
ownership, borrowing, inherited mutability, interior mutability, Copy
struct, enum, fn, pub, impl, use, ...
переключатели, дженерики, деструкторы
тестирование
unsafe

Начнем с того, что создадим проект:
 cargo new lists
 cd lists
Вообще говоря, для коллекций больше подходит вектор, а использование связного списка необходимо не так часто, например, если вы пишете модуль ядра операционной системы или реализуете задачу, в которой присутствует большое количество слияний и разбиений списков. По сравнению с массивами связный список имеет тот недостаток, что ему нужно дополнительное место в памяти для хранения указателей. В связных списках также нужно продумывать стратегию освобождения памяти, особенно в случае, когда сама нода имеет большой размер. В массивах мы можем использовать слайсы, в связных списках не можем. Вы должны отдавать себе отчет в том, на что вы идете и что вам прийдется реализовать для того, чтобы ваш связный список по-настоящему работал.
Связные списки - подходящий обьект для функционального программирования, можно например использовать рекурсию и неограниченно увеличивать размер самого списка. Для совершения различных операций над связными списками, такими, как фильтрация, реверс, конкатенация, используются итераторы.





First.rs

У нас будет несколько версий, первую мы положим в first.rs. Для этого в файле lib.rs мы обьявим публичный доступ к нему:

 // in lib.rs
 pub mod first;
Связный список - это набор нод, которые связаны друг с другом. Определим в нашем списке ноду, которая будет хранить число. Будем использовать растовский тип Box. В данном случае растовский стандартный тип Box<T> - тип указателя для выделения памяти. Например

 let x = Box::new(5);
Здесь мы фактически создаем рекурсивную структуру данных

 enum List {
     Cons(T, Box<List>),
     Nil,
 }
которую можем использовать так:

 fn main() {
     let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
     println!("{:?}", list);
 }
В результате получим вывод

 Cons(1, Box(Cons(2, Box(Nil))))
Определим наш список с помощью бокса

 // in first.rs
 
 // pub says we want people outside this module to be able to use List
 pub enum List {
     Empty,
     Elem(i32, Box<List>),
 }
Схематично связный список можно представить следующим образом
 [ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)
У нас есть указатель на начальную ноду, каждая нода хранит в себе число и указатель на следующую ноду. Если мы хотим разбить список на 2 списка
 [ptr] -> (Elem A, ptr) -> (Elem B, *null*)
 [ptr] -> (Elem C, *null*)
Определим базовые структуры. Сделаем публичную структуру List, а детали реализации сделаем приватными:

 pub struct List {
     head: Link,
 }
 
 enum Link {
     Empty,
     More(Box<Node>),
 }
 
 struct Node {
     elem: i32,
     next: Link,
 }
Имплементация списка

 impl List {
     // TODO, make code happen
 }
Вспомним, как в расте обьявляется функция

 fn foo(arg1: Type1, arg2: Type2) -> ReturnType {
     // body
 }
Для начала нам надо проинициализировать список. Поскольку детали мы сделали приватными, напишем внутри имплементации списка функцию

 impl List {
     pub fn new() -> Self {
         List { head: Link::Empty }
     }
 }
Здесь Self - это алиас для создаваемого обьекта. В этой функции мы не ставим return или точку с запятой, это такой стиль в расте - функция и так вернет последнее выражение. Теперь нам нужно написать какой-нибудь метод для списка

 fn foo(self, arg2: Type2) -> ReturnType {
     // body
 }
При этом алиас может выступать в одной из трех форм

 self
 &mut self
 &self
Первая форма вернет значение, второе - изменяемую ссылку. третья - глобальную ссылку. В первом случае с возвращаемым значением мы можем делать все что угодно - перемещать, удалять, изменять и т.д. При этом мы создаем копию обьекта, что ни есть хорошо. Вторая форма копию не создает, но позволяет с обьектом делать также все, что угодно. Третья форма не позволяет изменить обьект, она позволяет прочитать его.

Напишем метод, который добавляет ноду в список.

 use std::mem;
 
 impl List { 
 pub fn push(&mut self, elem: i32) {
     let new_node = Box::new(Node {
         elem: elem,
         next: mem::replace(&mut self.head, Link::Empty),
     });
 
     self.head = Link::More(new_node);
   }
 }
Здесь мы создаем новую ноду, добавляем ее в начало списка, но перед этим мы должны поменять указатель на следующую ноду.

Теперь напишем второй метод - pop - удаляющий ноду. В отличие от push, нам нужно что-то вернуть из этой функции. У нас возможны два варианта - список пустой и не пустой.

 pub fn pop(&mut self) -> Option<i32> {
     //TODO
 }
Option<T> - нумератор произвольного типа, т.е. фактически это дженерик

 pub fn pop(&mut self) -> Option<i32> {
     match mem::replace(&mut self.head, Link::Empty) {
         Link::Empty => None,
         Link::More(boxed_node) => {
             let node = *boxed_node;
             self.head = node.next;
             Some(node.elem)
         }
     }
 }
Мы проверяем, пустой ли список. Если пустой, мы возвращаем None, если не пустой, удаляем головную ноду, перемещаем указатель головы на следующую ноду и возвращаем ее.

Теперь нам надо протестировать код.

 // in first.rs
 
 mod test {
     #[test]
     fn basics() {
         // TODO
     }
 }
Для начала выполним команду
 cargo test
Пока тест ничего не делает. Добавим в него макрос assert_eq!

 #[cfg(test)]
 mod test {
     use super::List;
     
     #[test]
     fn basics() {
         let mut list = List::new();
 
         // Check empty list behaves right
         assert_eq!(list.pop(), None);
 
         // Populate list
         list.push(1);
         list.push(2);
         list.push(3);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(3));
         assert_eq!(list.pop(), Some(2));
 
         // Push some more just to make sure nothing's corrupted
         list.push(4);
         list.push(5);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(5));
         assert_eq!(list.pop(), Some(4));
 
         // Check exhaustion
         assert_eq!(list.pop(), Some(1));
         assert_eq!(list.pop(), None);
     }
 }


Следующий шаг - удаление всего списка. Для этого в расте есть деструкторы. Тип в расте имеет деструктор, если в нем имплементирован трэйт(типаж) по имени Drop

 pub trait Drop {
    fn drop(&mut self);
 }
Если в списке три ноды
 list -> A -> B -> C 
Если мы попытаемся удалить список, будет запущен рекурсивный механизм, и это плохая идея. Вместо этого варианта мы напишем свою собственную версию Drop

 impl Drop for List {
     fn drop(&mut self) {
         let mut cur_link = mem::replace(&mut self.head, Link::Empty);
         while let Link::More(mut boxed_node) = cur_link {
             cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
         }
     }
 }
Теперь можно подвести итог и представить первую версию кода first.rs:

 use std::mem;
 
 pub struct List {
     head: Link,
 }
 
 enum Link {
     Empty,
     More(Box<Node>),
 }
 
 struct Node {
     elem: i32,
     next: Link,
 }
 
 impl List {
     pub fn new() -> Self {
         List { head: Link::Empty }
     }
 
     pub fn push(&mut self, elem: i32) {
         let new_node = Box::new(Node {
             elem: elem,
             next: mem::replace(&mut self.head, Link::Empty),
         });
 
         self.head = Link::More(new_node);
     }
 
     pub fn pop(&mut self) -> Option<i32> {
         match mem::replace(&mut self.head, Link::Empty) {
             Link::Empty => None,
             Link::More(node) => {
                 let node = *node;
                 self.head = node.next;
                 Some(node.elem)
             }
         }
     }
 }
 
 impl Drop for List {
     fn drop(&mut self) {
         let mut cur_link = mem::replace(&mut self.head, Link::Empty);
         while let Link::More(mut boxed_node) = cur_link {
             cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
         }
     }
 }
 
 #[cfg(test)]
 mod test {
     use super::List;
 
     #[test]
     fn basics() {
         let mut list = List::new();
 
         // Check empty list behaves right
         assert_eq!(list.pop(), None);
 
         // Populate list
         list.push(1);
         list.push(2);
         list.push(3);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(3));
         assert_eq!(list.pop(), Some(2));
 
         // Push some more just to make sure nothing's corrupted
         list.push(4);
         list.push(5);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(5));
         assert_eq!(list.pop(), Some(4));
 
         // Check exhaustion
         assert_eq!(list.pop(), Some(1));
         assert_eq!(list.pop(), None);
     }
 }







Second.rs

Далее, во вторую версию списка мы добавим возможность хранить любой тип, не только числовой. Будут добавлены итераторы.
В библиотеке мы пропишем вторую версию

 // in lib.rs
 
 pub mod first;
 pub mod second;
Для начала мы перепишем структуру

 enum Link {
     Empty,
     More(Box),
 }
в виде

 type Link = Option<Box<Node>>;
Это упростит нашу вторую по счету реализацию, например далее везде вместо Link::Empty мы будем писать просто None. Заменим следующую синтаксическую идиому

 next: mem::replace(&mut self.head, Link::Empty),
на

 next: self.head.take()
Мы перепишем функцию pop. Если рассмотреть конструкцию

 match option { None => None, Some(x) => Some(y) } 
она представляет из себя обертку над функцией map. Функция map берет x, что-то делает в Some(x) и производит Some(y). Мы перепишем функцию pop, возьмем анонимную функцию и передадим ее в качестве праметра в map:

 pub fn pop(&mut self) -> Option<i32> {
     self.head.take().map(|node| {
         let node = *node;
         self.head = node.next;
         node.elem
     })
 }
Теперь добавим возможность произвольно менять тип данных, которые хранятся в ноде

 pub struct List<T> {
     head: Link<T>,
 }
 
 type Link = Option<Box<Node<T>>>;
 
 struct Node<T> {
     elem: T,
     next: Link<T>,
 }
 
 impl<T> List<T> {
     pub fn new() -> Self {
         List { head: None }
     }
 
     pub fn push(&mut self, elem: T) {
         let new_node = Box::new(Node {
             elem: elem,
             next: self.head.take(),
         });
 
         self.head = Some(new_node);
     }
 
     pub fn pop(&mut self) -> Option<T> {
         self.head.take().map(|node| {
             let node = *node;
             self.head = node.next;
             node.elem
         })
     }
 }
 
 impl<T> Drop for List<T> {
     fn drop(&mut self) {
         let mut cur_link = self.head.take();
         while let Some(mut boxed_node) = cur_link {
             cur_link = boxed_node.next.take();
         }
     }
 }
 
Добавим функцию, возвращающую ссылку на головную ноду

 pub fn peek(&self) -> Option<&T> {
     self.head.as_ref().map(|node| {
         &node.elem
     })
 }
либо так

 pub fn peek_mut(&mut self) -> Option<&mut T> {
     self.head.as_mut().map(|node| {
         &mut node.elem
     })
 }
Теперь можно протестировать

 #[test]
 fn peek() {
     let mut list = List::new();
     assert_eq!(list.peek(), None);
     assert_eq!(list.peek_mut(), None);
     list.push(1); list.push(2); list.push(3);
 
     assert_eq!(list.peek(), Some(&3));
     assert_eq!(list.peek_mut(), Some(&mut 3));
 }
Итерацию в растовской коллекции можно сделать с помощью типажа Iterator

 pub trait Iterator {
     type Item;
     fn next(&mut self) -> Option<Self::Item>;
 }
Мы добавили тип Item. В расте нет оператора yield, как в питоне например, и прийдется изобретать велосипед. В коллекции может быть три типа итераторов
 1 T
 2 &mut T
 3 &T
Первая версия

 // Tuple structs are an alternative form of struct,
 // useful for trivial wrappers around other types.
 pub struct IntoIter<T>(List<T>);
 
 impl<T> List<T> {
     pub fn into_iter(self) -> IntoIter<T> {
         IntoIter(self)
     }
 }
 
 impl<T> Iterator for IntoIter<T> {
     type Item = T;
     fn next(&mut self) -> Option<Self::Item> {
         // access fields of a tuple struct numerically
         self.0.pop()
     }
 }
Напишем тест

 #[test]
 fn into_iter() {
     let mut list = List::new();
     list.push(1); list.push(2); list.push(3);
 
     let mut iter = list.into_iter();
     assert_eq!(iter.next(), Some(3));
     assert_eq!(iter.next(), Some(2));
     assert_eq!(iter.next(), Some(1));
 }
В следующей - 3-й версии итератора мы будем хранить указатель на текущую ноду, а yield будем применять для следующей. При этом указатель next должен переместиться на текущую ноду.

 pub struct Iter<'a, T:'a> {
     next: Option<&'a Node<T>>,
 }
 
 impl<T> List<T> {
     pub fn iter<'a>(&'a self) -> Iter<'a, T> {
         Iter { next: self.head.as_ref().map(|node| &**node) }
     }
 }
 
 impl<'a, T> Iterator for Iter<'a, T> {
     type Item = &'a T;
 
     fn next(&mut self) -> Option<Self::Item> {
         self.next.map(|node| {
             self.next = node.next.as_ref().map(|node| &**node);
             &node.elem
         })
     }
 }
Тестируем

 #[test]
 fn iter() {
     let mut list = List::new();
     list.push(1); list.push(2); list.push(3);
 
     let mut iter = list.iter();
     assert_eq!(iter.next(), Some(&3));
     assert_eq!(iter.next(), Some(&2));
     assert_eq!(iter.next(), Some(&1));
 }
Здесь мы применили конструкцию

 fn foo<'a>(&'a A) -> &'a B 
что означает, что время жизни входящих параметров должно быть таким же, как и выходных, т.е. и те и другие должны находиться в одной области видимости или определения. Финальная версия second.rs

 pub struct List<T> {
     head: Link<T>,
 }
 
 type Link = Option<Box<Node<T>>>;
 
 struct Node<T> {
     elem: T,
     next: Link<T>,
 }
 
 pub struct IntoIter<T>(List<T>);
 
 pub struct Iter<'a, T:'a> {
     next: Option<&'a Node<T>>,
 }
 
 pub struct IterMut<'a, T: 'a> {
     next: Option<&'a mut Node>,
 }
 
 
 
 impl List<T> {
     pub fn new() -> Self {
         List { head: None }
     }
 
     pub fn push(&mut self, elem: T) {
         let new_node = Box::new(Node {
             elem: elem,
             next: self.head.take(),
         });
 
         self.head = Some(new_node);
     }
 
     pub fn pop(&mut self) -> Option<T> {
         self.head.take().map(|node| {
             let node = *node;
             self.head = node.next;
             node.elem
         })
     }
 
     pub fn peek(&self) -> Option<&T> {
         self.head.as_ref().map(|node| {
             &node.elem
         })
     }
 
     pub fn peek_mut(&mut self) -> Option<&mut T> {
         self.head.as_mut().map(|node| {
             &mut node.elem
         })
     }
 
     pub fn into_iter(self) -> IntoIter<T> {
         IntoIter(self)
     }
 
     pub fn iter(&self) -> Iter<T> {
         Iter { next: self.head.as_ref().map(|node| &**node) }
     }
 
     pub fn iter_mut(&mut self) -> IterMut<T> {
         IterMut { next: self.head.as_mut().map(|node| &mut **node) }
     }
 }
 
 impl<T> Drop for List<T> {
     fn drop(&mut self) {
         let mut cur_link = self.head.take();
         while let Some(mut boxed_node) = cur_link {
             cur_link = boxed_node.next.take();
         }
     }
 }
 
 impl<T> Iterator for IntoIter<T> {
     type Item = T;
     fn next(&mut self) -> Option<Self::Item> {
         self.0.pop()
     }
 }
 
 impl<'a, T> Iterator for Iter<'a, T> {
     type Item = &'a T;
 
     fn next(&mut self) -> Option<Self::Item> {
         self.next.map(|node| {
             self.next = node.next.as_ref().map(|node| &**node);
             &node.elem
         })
     }
 }
 
 impl<'a, T> Iterator for IterMut<'a, T> {
     type Item = &'a mut T;
 
     fn next(&mut self) -> Option<Self::Item> {
         self.next.take().map(|node| {
             self.next = node.next.as_mut().map(|node| &mut **node);
             &mut node.elem
         })
     }
 }
 
 
 #[cfg(test)]
 mod test {
     use super::List;
 
     #[test]
     fn basics() {
         let mut list = List::new();
 
         // Check empty list behaves right
         assert_eq!(list.pop(), None);
 
         // Populate list
         list.push(1);
         list.push(2);
         list.push(3);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(3));
         assert_eq!(list.pop(), Some(2));
 
         // Push some more just to make sure nothing's corrupted
         list.push(4);
         list.push(5);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(5));
         assert_eq!(list.pop(), Some(4));
 
         // Check exhaustion
         assert_eq!(list.pop(), Some(1));
         assert_eq!(list.pop(), None);
     }
 
     #[test]
     fn peek() {
         let mut list = List::new();
         assert_eq!(list.peek(), None);
         assert_eq!(list.peek_mut(), None);
         list.push(1); list.push(2); list.push(3);
 
         assert_eq!(list.peek(), Some(&3));
         assert_eq!(list.peek_mut(), Some(&mut 3));
     }
 
     #[test]
     fn into_iter() {
         let mut list = List::new();
         list.push(1); list.push(2); list.push(3);
 
         let mut iter = list.into_iter();
         assert_eq!(iter.next(), Some(3));
         assert_eq!(iter.next(), Some(2));
         assert_eq!(iter.next(), Some(1));
     }
 
     #[test]
     fn iter() {
         let mut list = List::new();
         list.push(1); list.push(2); list.push(3);
 
         let mut iter = list.iter();
         assert_eq!(iter.next(), Some(&3));
         assert_eq!(iter.next(), Some(&2));
         assert_eq!(iter.next(), Some(&1));
     }
 
     #[test]
     fn iter_mut() {
         let mut list = List::new();
         list.push(1); list.push(2); list.push(3);
 
         let mut iter = list.iter_mut();
         assert_eq!(iter.next(), Some(&mut 3));
         assert_eq!(iter.next(), Some(&mut 2));
         assert_eq!(iter.next(), Some(&mut 1));
     }
 }
В оригинальной версии далее идет реализация еще трех вариантов. В третьем добавляется функции append, tail, а также делается ставка на многопоточность. В четвертой версии появляется двойной связный список. В пятой версии делается упор на unsafe.




Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье