Atomicité, CAS

On souhaite écrire une implantation d'un Set qui soit thread-safe et sans utiliser de verrou, moniteur et autre lock.

L'implantation fonctionne comme une table de hachage de taille fixe utilisant un hachage ouvert mais là ou habituellement on utilise une liste chainée pour stocker les élements qui entre en collisions, on utilisera ici des tableaux secondaires pour stocker les collisions.
Lors d'un ajout d'un élement, une fois l'index trouvé en fonction de la fonction de hachage, on parcours le tableau secondaire pour voir si l'élement ne s'y trouve pas, sinon on crée un nouveau tableau ayant une case supplémentaire, on recopie les anciennes valeurs et on stocke ne nouvel élement dedans. Lors d'une recherche, on parcours simplement le tableau secondaire.

On souhaite écrire une implantation de liste chaînée concurrente n'utilisant ni section critique, ni verrou.
La liste devra possèder deux méthodes addLast(E e) et toString() permettant respectivement d'ajouter un élement en queue de liste et d'afficher celle-ci. La liste sera créée avec un maillon.
L'idée pour éviter toute synchronisation lors de l'ajout consiste à récuperer le maillon à la fin de la liste puis à tester en une opération atomique si le maillon est toujours la fin de la liste et si oui à lui assigner le nouveau maillon créé. Si ce n'est pas le dernier maillon, on récupère de nouveau la fin de la liste et on recommence la même opération.

Dans un premier temps, nous allons définir la liste comme une chaîne de maillons: la liste elle-même est simplement le premier maillon de la chaîne. L'ajout à la fin de la liste se fera après un parcours du chaînage.

1. Définir la classe ConcurrentLink avec ses champs element et next ainsi que son constructeur ConcurrentLink(E firstElement).
2. Rappeler ce qu'est le problème de publication.
   En quoi cela impact la classe que nous venons de déclarer.
3. Implanter la méthode toString.
4. Rappeler la difference entre une AtomicReference et un AtomicReferenceFieldUpdater du paquetage java.util.concurrent.atomic ?
   Indiquer comment utiliser une AtomicReference ici.
   Indiquer comment utiliser une AtomicReferenceFieldUpdater ici.
5. Implanter la méthode addLast en utilisant la classe AtomicReferenceFieldUpdater.

On souhaite maintenant séparer l'implantation de la liste de celle d'un maillon dans le but d'avoir une référence sur le dernier maillon pour effectuer un ajout à la fin plus efficace.

1. Définir la classe ConcurrentList pour qu'elle contienne deux champs head et tail correspondant respectivement au début et à la fin de la liste ainsi que la classe interne Entry correspondant à un maillon de la liste chaînée.
   Pour simplifier les choses, la liste ne pourra être vide, elle sera donc construite avec un élement.
2. Implanter la méthode addLast.
   Attention, il y a un petit piège lorsque l'on met à jour la référence correspondant à la fin de la liste.
3. Implanter la méthode toString .

Si vous avez réussi bravo, vous venez de ré-implanter une partie de la classe ConcurrentLinkedQueue.