Instructions
Écris une liste doublement chaînée en Rust unsafe, comprenant un itérateur sur la liste et un curseur pour la modifier efficacement.
La liste doublement chaînée est une structure de données fondamentale en informatique.
Chaque nœud d'une liste doublement chaînée contient une donnée ainsi que des pointeurs vers le nœud suivant et le nœud précédent, s'ils existent.
On peut ajouter de nouveaux nœuds efficacement à n'importe quel endroit de la liste, à condition de disposer déjà d'une référence vers cette position. De même, tous les éléments d'une autre liste peuvent être insérés à n'importe quel endroit en temps constant.
En Rust, les listes chaînées sont très rarement utilisées, mais elles piègent parfois les débutants qui tentent d'en implémenter une. Souvent, ces derniers trouvent étonnamment difficile de composer avec le vérificateur d'emprunts, encore peu familier.
Une note sur unsafe
Rappelle-toi que l'objectif du Rust unsafe est d'écrire du code sûr dans les cas où le compilateur ne peut pas nous aider à garantir la correction. Un utilisateur ne doit en aucun cas pouvoir provoquer la moindre insécurité mémoire en n'utilisant que les interfaces sûres que nous exposons.
Documente les invariants critiques pour la sûreté que tu dois maintenir, et commente chaque bloc unsafe en expliquant pourquoi il est sûr.
Toute fonction pour laquelle l'appelant doit maintenir des invariants critiques pour la sûreté doit être marquée unsafe. Cela inclut les fonctions privées.
Étape 1
Implémente les fonctionnalités d'ajout et de retrait d'éléments (push et pop) à l'avant et à l'arrière. Cela suffit pour utiliser la liste comme une file à double extrémité. Implémente aussi les fonctions len et is_empty.
Dans l'implémentation finale, toutes les modifications de la liste doivent passer par la structure de curseur, afin de minimiser la duplication. Les méthodes push_* et pop_* de LinkedList sont définies à partir des méthodes de curseur requises dans le module pre_implemented. Si tu le souhaites, tu peux pour l'instant ignorer la structure Cursor et redéfinir les méthodes, mais pense à les rétablir à la fin.
Étape 2
Implémente l'itération sur la liste de l'avant vers l'arrière avec la structure Iter.
Étape 3
Complète les fonctionnalités du curseur. Il doit pouvoir se déplacer à n'importe quelle position et y insérer ou retirer des éléments.
Étape 4
Implémente le trait Drop pour ta LinkedList afin de libérer les ressources.
Étape 5 (avancée et facultative)
Les tests de ces deux derniers points sont compilés de manière conditionnelle via le drapeau de fonctionnalité advanced. Ajoute la clé default = ["advanced"] au fichier Cargo.toml, sous [features], pour les activer.
Pour offrir un maximum de flexibilité aux utilisateurs de ta structure, assure-toi que ta LinkedList<T> est covariante sur T. Cela signifie, par exemple, qu'une LinkedList<&'static T> peut aussi être utilisée comme une LinkedList<&'a T>. Consulte le Rustonomicon pour une explication de la variance en Rust.
Assure-toi que ta liste peut être envoyée et partagée d'un thread à l'autre sans danger, et signale-le au système de types en implémentant Send et Sync manuellement. Ces traits sont habituellement dérivés automatiquement, mais ne sont pas implémentés ici de façon automatique, à cause de l'utilisation de pointeurs bruts. Consulte la documentation de Send et Sync, ainsi que le chapitre du rustonomicon qui leur est consacré, pour plus de détails sur leur importance.
