src/routing/olsr/olsr-routing-protocol.cc
changeset 5756 31623ed9b682
parent 5524 efed7493f2c1
child 5757 c2dc9d69d547
--- a/src/routing/olsr/olsr-routing-protocol.cc	Thu Nov 19 11:19:39 2009 +0000
+++ b/src/routing/olsr/olsr-routing-protocol.cc	Thu Nov 19 18:22:54 2009 +0300
@@ -464,6 +464,37 @@
   return degree;
 }
 
+namespace {
+///
+/// \brief Remove all covered 2-hop neighbors from N2 set. This is a helper function used by MprComputation algorithm.
+///
+void 
+CoverTwoHopNeighbors (Ipv4Address neighborMainAddr, TwoHopNeighborSet & N2)
+{
+  // first gather all 2-hop neighbors to be removed
+  std::set<Ipv4Address> toRemove;
+  for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin (); twoHopNeigh != N2.end (); twoHopNeigh ++)
+    {
+      if (twoHopNeigh->neighborMainAddr == neighborMainAddr)
+        {
+          toRemove.insert (twoHopNeigh->twoHopNeighborAddr);
+        }
+    }
+  // Now remove all matching records from N2
+  for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin (); twoHopNeigh != N2.end (); )
+    {
+      if (toRemove.find (twoHopNeigh->twoHopNeighborAddr) != toRemove.end ())
+        {
+          twoHopNeigh = N2.erase (twoHopNeigh);
+        }
+      else
+        {
+          twoHopNeigh ++;
+        }
+    }
+}
+} // anonymous namespace
+
 ///
 /// \brief Computates MPR set of a node following RFC 3626 hints.
 ///
@@ -577,18 +608,7 @@
           mprSet.insert (neighbor->neighborMainAddr);
           // (not in RFC but I think is needed: remove the 2-hop
           // neighbors reachable by the MPR from N2)
-          for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin ();
-               twoHopNeigh != N2.end (); )
-            {
-              if (twoHopNeigh->neighborMainAddr == neighbor->neighborMainAddr)
-                {
-                  twoHopNeigh = N2.erase (twoHopNeigh);
-                }
-              else
-                {
-                  twoHopNeigh++;
-                }
-            }
+          CoverTwoHopNeighbors (neighbor->neighborMainAddr, N2);
         }
     }
   
@@ -637,6 +657,8 @@
     {
       if (coveredTwoHopNeighbors.find (twoHopNeigh->twoHopNeighborAddr) != coveredTwoHopNeighbors.end ())
         {
+          // This works correctly only because it is known that twoHopNeigh is reachable by exactly one neighbor, 
+          // so only one record in N2 exists for each of them. This record is erased here.
           NS_LOG_LOGIC ("2-hop neigh. " << twoHopNeigh->twoHopNeighborAddr << " is already covered by an MPR.");
           twoHopNeigh = N2.erase (twoHopNeigh);
         }
@@ -714,10 +736,6 @@
               if (max == NULL || nb_tuple->willingness > max->willingness)
                 {
                   max = nb_tuple;
-                  for (TwoHopNeighborSet::iterator newCovered = N2.begin (); newCovered != N2.end (); newCovered++)
-                    {
-                      coveredTwoHopNeighbors.insert (newCovered->twoHopNeighborAddr);
-                    }
                   max_r = r;
                 }
               else if (nb_tuple->willingness == max->willingness)
@@ -742,19 +760,8 @@
       if (max != NULL)
         {
           mprSet.insert (max->neighborMainAddr);
-          // Remove the nodes from N2 which are now covered by a node in the MPR set.
-          for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin (); twoHopNeigh != N2.end (); )
-            {
-              if (coveredTwoHopNeighbors.find (twoHopNeigh->twoHopNeighborAddr) != coveredTwoHopNeighbors.end ())
-                {
-                  NS_LOG_LOGIC ("2-hop neigh. " << twoHopNeigh->twoHopNeighborAddr << " is already covered by an MPR.");
-                  twoHopNeigh = N2.erase (twoHopNeigh);
-                }
-              else
-                {
-                  twoHopNeigh++;
-                }
-            }
+          CoverTwoHopNeighbors (max->neighborMainAddr, N2);
+          NS_LOG_LOGIC (N2.size () << " 2-hop neighbors left to cover!");           
         }
     }