Re: Donc pour résumer...

J'ai réfléchi depuis l'autre jour sur cette notion de shared_ptr (qui n'est qu'un « fichu stupide pointeur », mais géré d'une manière particulière) et je te propose une autre utilisation possible : s'en servir, effectivement, comme une zone mémoire partagée où tous les possesseurs peuvent écrire dedans pour implémenter une structures de tableaux persistants. :-)

Le principe de l'encodage sera écrit en OCaml (ce sera plus simple pour moi, et je laisse la traduction en C++ à toi ou un autre). Avant cela, je vais revenir sur la notion de constructeurs de type dans ce langage pour que tu puisses faire le lien.

Quand j'ai présenté la définition du type des listes chaînées, je l'ai écrit ainsi :

type 'a liste =
 | Nil
 | Cons of 'a * 'a liste

Une expression de la forme Cons of ... est en réalité un « pointeur » en lecture seule sur la structure décrite ensuite. On pourrait l'illustrer ainsi :

type 'a ptr = Ptr of 'a;;
let read (Ptr x) = x;;
let i = Ptr 1;;
val i : int ptr = Ptr 1
read i;;
- : int = 1

Ceci dit, ce langage propose également la notion de zone mémoire accessible en lecture et écriture avec la notion de référence (mot clé ref).

let i = ref 1;;
val i : int ref = {contents = 1}
(* lecture avec l'opérateur préfixe !*)
!i;;
- : int = 1
(* écriture avec l'opérateur infixe := *)
i := 2;;
- : unit = () (* le type unit est équivalent à void *)
(* nouvelle lecture *)
!i;;
- : int = 2

Avant d'en venir au cœur de ce commentaire, il me faut présenter rapidement une autre structure représentant une zone mémoire accessible en lecture et écriture, commune à tous les langages impératifs : les tableaux (ou array).

let tab = [|0; 1; 2; 3|];;
val tab : int array = [|0; 1; 2; 3|]
Array.get tab 0;;
- : int = 0
Array.set tab 0 4;;
- : unit = ()
Array.get tab 0;;
- : int = 4
(* on peut faire la même chose avec cette notation *)
tab.(0) <- 5;;
- : unit = ()
tab.(0);;
- : int = 5
tab;;
- : int array = [|5; 1; 2; 3|]

Ces présentations préliminaires étant faites, venons en à l'objectif principal : coder une structure de tableaux persistants en recourant à une zone mémoire accessible en lecture-écriture commune à chacun d'eux. On pourrait faire cela en recopiant le tableau à chaque écriture puis en renvoyant la copie modifiée, mais ce serait vite coûteux en mémoire. L'idée pour obtenir la persistance à moindre coût va être celle qui est derrière les gestionnaires de versions (git, svn, mercurial...) : une écriture sera vu comme un patch et on conservera en mémoire la structure des diff.

On commence par définir le type polymorphe 'a t de nos tableaux :

type 'a t = 'a data ref
and 'a data = |Arr of 'a array 
 |Diff of int * 'a * 'a t

On a deux types mutuellement récursifs : le type 'a data qui pointe en lecture soit sur un tableau, soit sur un triplet correspondant à une écriture atomique sur un tableau, qui lui est un pointeur en lecture-écriture sur une structure 'a data.

Tout le code sur cette structure va reposer sur la fonction reroot qui modifie le graphe des pointeurs afin de toujours rentrer dans la structure par un pointeur en lecture sur un tableau 'a array. Autrement dit : on applique tous les patchs sur le tableau d'origine pour présenter le tableau résultant.

let rec reroot pa = match !pa with
 |Arr a -> a
 |Diff (i, v, pa') ->
 (* pa est vu comme un diff de pa', on commence par rerooter sur lui *)
 let a = reroot pa' in
 (* on applique le patch atomique *)
 let old = a.(i) in
 a.(i) <- v;
 pa := Arr a;
 (* maintenant c'est pa' qui est vu comme un diff de pa *)
 pa' := Diff (i, old, pa);
 (* on retourne le « véritable » tableau correspondant à pa *)
 a

À partir de cette fonction utilitaire, on peut définir les fonctions usuelles sur les tableaux à partir de celles sur les array.

let length pa = Array.length (reroot pa)
let get pa i = (reroot pa).(i)
let iter f pa = Array.iter f (reroot pa)
(* ici la fonction f que l'on itère prend deux paramètres : l'indice et la valeur *)
let iteri f pa = Array.iteri f (reroot pa)

Pour la fonction set, il faut prendre soin de rerooter sur le tableau que l'on veut patcher puis rajouter le diff dans la structure :

let set pa i v =
 let a = reroot pa in
 let old = a.(i) in
 a.(i) <- v;
 let res = ref (Arr a) in
 pa := Diff (i, old, res);
 res

On peut également, par exemple, rajouter des fonctions de conversions vers et à partir des tableaux non persistants ainsi qu'une fonction de copie qui oublie tout l'historique des patchs.

let to_array = reroot
let of_array a = ref (Arr a)
let copy pa = ref (Arr (Array.copy (reroot pa))

Maintenant, à la manière de la POO, on peut masquer une partie de la mécanique interne ainsi que le type implémentant une telle structure à l'utilisateur. On passe pour cela par le système de modules en n'exposant pas certains détails dans l'interface.

(* l'interface du module :
 * - la définition du type n'est pas exposée
 * - le type 'a data non plus
 * - la fonction reroot reste privée *)
module type PA = sig
 type 'a t
 val init : int -> (int -> 'a) -> 'a t
 val length : 'a t -> int
 val get : 'a t -> int -> 'a
 val set : 'a t -> int -> 'a -> 'a t
 val iteri : (int -> 'a -> unit) -> 'a t -> unit
 val iter : ('a -> unit) -> 'a t -> unit
 val to_array : 'a t -> 'a array
 val of_array : 'a array -> 'a t
 val copy : 'a t -> 'at
end
(* le code complet du module *)
module Persistent_Array : PA = struct
 type 'a t = 'a data ref
 and 'a data = |Arr of 'a array 
 |Diff of int * 'a * 'a t
 let init n f = ref (Arr (Array.init n f))
 let rec reroot pa = match !pa with
 |Arr a -> a
 |Diff (i, v, pa') -> 
 let a = reroot pa' in
 let old = a.(i) in
 a.(i) <- v;
 pa := Arr a;
 pa' := Diff (i, old, pa);
 a
 let length pa = Array.length (reroot pa)
 let to_array = reroot
 let of_array a = ref (Arr a)
 let copy pa = ref (Arr (Array.copy (reroot pa))
 let get pa i = (reroot pa).(i)
 let iteri f pa = Array.iteri f (reroot pa)
 let iter f pa = Array.iter f (reroot pa)
 let set pa i v = 
 let a = reroot pa in
 let old = a.(i) in
 a.(i) <- v;
 let res = ref (Arr a) in
 pa := Diff (i, old, res);
 res
end

Illustration du module :

module PA = Persistent_Array;;
let tab = PA.of_array [|0; 1; 2; 3|];;
val tab : int PA.t = <abstr> (* la représentation est abstraite pour l'utilisateur *)
let tab' = PA.set tab 0 4;;
val tab' : int PA.t = <abstr>
(* le tableau est bien persistant *)
PA.to_array tab;;
- : int array = [|0; 1; 2; 3|]
PA.to_array tab';;
- : int array = [|4; 1; 2; 3|]

Il reste à noter, tout de même, que la fonction reroot qui réorganise la structure des pointeurs n'est pas thread safe (les merge peuvent créer des conflits ;-), donc la structure ne l'est pas non plus. On pourrait, par exemple, la rendre thread safe en rajoutant un verrou que l'on pose au début de reroot et qu'on libère une fois la réorganisation effectuée.

Voilà, à mon avis, une structure qu'il peut être intéressant d'implémenter avec des shared_ptr plutôt qu'avec de « simples » pointeurs — si j'en ai bien compris le principe. Et encore une fois : la persistance des données, c'est le bien ! :-)

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.