Keep track of the peer position for faster distance computation.

git-svn-id: https://scm.gforge.inria.fr/svn/pacemaker@31 30fcff6e-8de6-41c7-acce-77ff6d1dd07b

4 files changed, 43 insertions, 26 deletions

diff --git a/sources/thibaut/globals.ml b/sources/thibaut/globals.ml
index 5dfa722..41c8b0c 100644
--- a/sources/thibaut/globals.ml
+++ b/sources/thibaut/globals.ml
@@ -76,19 +76,6 @@ end = struct
 		
 end
 
-let random_iter f a = 
-	let rec aux n = match n with
-		| 1 -> ()
-		| n -> let pos = 1+ Random.int (n-1) in
-			let b = a.(pos) in
-			a.(pos) <- a.(n-1);
-			a.(n-1) <- b;
-			f a.(n-1);
-			aux (n-1)
-	in
-	aux (Array.length a)
-	 
-
 type message_content = 
     | Seed of int * int (* seed, duration *)
     | SeedReply of int (* hash *)
@@ -262,11 +249,33 @@ type peer = {
     mutable rounds_data : round_data RoundMap.t;
     messages : message Queue.t;
     mutable history : (int * (int HashMap.t list)) RoundMap.t; (* seed, branch *)
-    mutable distance : int
+    mutable distance : int;
+    mutable connection_time : int
 }
 and slot = peer SlotArray.slot
 
 let disconnect peer =
     SlotArray.clear peer.slots;
     peer.con_state <- OFF;
-    peer.distance <- -1;
+    peer.distance <- -1
+
+let swap a pos1 pos2 =
+    let temp = a.(pos1) in
+    a.(pos1) <- a.(pos2);
+    a.(pos2) <- temp
+    
+let swap_track tracking_array real_array pos1 pos2 =
+    let id1 = real_array.(pos1).id in
+    let id2 = real_array.(pos2).id in
+    swap tracking_array id1 id2;
+    swap real_array pos1 pos2
+    
+let random_iter f a tracking = 
+	let rec aux n = match n with
+		| 1 -> ()
+		| n -> let pos = 1+ Random.int (n-1) in
+            swap_track tracking a pos (n-1);
+			f a.(n-1);
+			aux (n-1)
+	in
+	aux (Array.length a)
diff --git a/sources/thibaut/graph.ml b/sources/thibaut/graph.ml
index 28cd19d..d3cbdfe 100644
--- a/sources/thibaut/graph.ml
+++ b/sources/thibaut/graph.ml
@@ -14,7 +14,7 @@ let find_peer id peers =
         Found p -> p
 
 (* compute distances from root *)
-let distances peers =
+let update_distances peers tracking_array =
     let  n = Array.length peers in
     let visited = Array.make n false in
     let queue = Queue.create() in
@@ -23,7 +23,7 @@ let distances peers =
     Queue.push 0 queue;
     while not (Queue.is_empty queue) do
         let id = Queue.pop queue in
-        let peer = find_peer id peers in
+        let peer = peers.(tracking_array.(id)) in
         let aux p =
             if not visited.(p.id) then begin
                 visited.(p.id) <- true;
@@ -34,15 +34,18 @@ let distances peers =
         SlotArray.iter (fun (SlotArray.Peer p) -> aux p) peer.slots
     done
 
-let repart peers =
+let repart round peers =
     let n = Array.length peers in
     let result = Array.make 20 0 in
+    let old = ref 0 in
     for i = 0 to n-1 do
         let peer = peers.(i) in
         if peer.distance < 19 && peer.con_state = ON then
-            result.(peer.distance + 1 ) <- result.(peer.distance + 1 ) +1
+            result.(peer.distance + 1 ) <- result.(peer.distance + 1 ) +1;
+        if peer.con_state = ON && peer.connection_time < round -2 && peer.distance = -1 then
+            incr old
     done;
-    result
+    result, !old
         
         
         
diff --git a/sources/thibaut/simulator.ml b/sources/thibaut/simulator.ml
index c59b939..5a08784 100644
--- a/sources/thibaut/simulator.ml
+++ b/sources/thibaut/simulator.ml
@@ -48,9 +48,12 @@ let peers = Array.init npeers (fun i -> {
     rounds_data = RoundMap.empty;
     messages = Queue.create();
     history = RoundMap.empty;
-    distance = -1
+    distance = -1;
+    connection_time = 0;
 })
 
+let tracking_array = Array.init npeers (fun i -> i)
+
 let do_trace_round = Trace.read ic peers
 
 let nticks = (days)*24*60*(!tpm)
@@ -86,7 +89,7 @@ let _ =
               	incr connected
             end
         in
-        random_iter do_peer peers;
+        random_iter do_peer peers tracking_array;
         
         if i mod !tpm = 0 then begin
         	Printf.printf "Minute %d, " (i/(!tpm));
@@ -96,8 +99,10 @@ let _ =
 		    Printf.printf "Askroots: %d" !Mesh.askroot;
 		    print_newline ();
 		    
-		    distances peers;
-		    let rep = repart peers in
+		    update_distances peers tracking_array;
+		    let rep, old = repart (i/(!tpm)) peers in
+		    Printf.printf "Olds: %d" old;
+		    print_newline ();
 		    for i = 0 to Array.length rep - 1 do
 		    	Printf.printf "%d, " rep.(i)
 		    done;
@@ -105,7 +110,7 @@ let _ =
 		    (*for i = 0 to (npeers-1) do
 		    	let p = peers.(i) in
 		    	if p.con_state = ON then begin
-		    		Printf.printf "%d: %d | " p.id distance.(p.id);
+		    		Printf.printf "%d: %d | " p.id p.distance;
 		    		SlotArray.iter (fun (SlotArray.Peer p) -> Printf.printf "%d, " p.id ) p.slots;
 		    		print_newline ()
     			end
diff --git a/sources/thibaut/trace.ml b/sources/thibaut/trace.ml
index fb139ea..360e3b6 100644
--- a/sources/thibaut/trace.ml
+++ b/sources/thibaut/trace.ml
@@ -69,7 +69,7 @@ let read ic peers =
     let rec read_round round = 
         match !event with
             | Round n -> if n = round then next round
-            | On i -> peers.(i).con_state <- ON; next round
+            | On i -> peers.(i).con_state <- ON; peers.(i).connection_time <- round; next round
             | Off i -> disconnect peers.(i);
                        next round
             | _ -> ()