[GNUnet-SVN] r8108 - GNUnet/src/applications/dv/module

[gnunet]

Author: nevans
Date: 2009-01-14 10:58:25 -0700 (Wed, 14 Jan 2009)
New Revision: 8108

Modified:
   GNUnet/src/applications/dv/module/Makefile.am
   GNUnet/src/applications/dv/module/dv.c
   GNUnet/src/applications/dv/module/heap.c
   GNUnet/src/applications/dv/module/heap.h
Log:


Modified: GNUnet/src/applications/dv/module/Makefile.am
===================================================================
--- GNUnet/src/applications/dv/module/Makefile.am       2009-01-14 13:03:05 UTC 
(rev 8107)
+++ GNUnet/src/applications/dv/module/Makefile.am       2009-01-14 17:58:25 UTC 
(rev 8108)
@@ -13,7 +13,7 @@
   libgnunetmodule_dv.la
 
 libgnunetmodule_dv_la_SOURCES = \
-  dv.c 
+  dv.c heap.c
 libgnunetmodule_dv_la_LDFLAGS = \
   $(GN_PLUGIN_LDFLAGS)
 libgnunetmodule_dv_la_LIBADD = \

Modified: GNUnet/src/applications/dv/module/dv.c
===================================================================
--- GNUnet/src/applications/dv/module/dv.c      2009-01-14 13:03:05 UTC (rev 
8107)
+++ GNUnet/src/applications/dv/module/dv.c      2009-01-14 17:58:25 UTC (rev 
8108)
@@ -41,8 +41,6 @@
   unsigned long long max_table_size;
   unsigned int send_interval;
 
-  unsigned int curr_neighbor_table_size;
-  unsigned int curr_connected_neighbor_table_size;
   unsigned short closing;
 
   struct GNUNET_Mutex *dvMutex;
@@ -68,11 +66,18 @@
   struct GNUNET_dv_neighbor *neighbor = (struct GNUNET_dv_neighbor *) value;
   char *type = (char *) cls;
   GNUNET_EncName encPeer;
+  GNUNET_EncName encReferrer;
 
-  GNUNET_hash_to_enc (&neighbor->referrer->hashPubKey, &encPeer);
-  fprintf (stderr, "%s\tNeighbor: %s\nCost: %d", type, (char *) &encPeer,
+  GNUNET_hash_to_enc (&neighbor->neighbor->hashPubKey, &encPeer);
+  if (neighbor->referrer == NULL)
+       fprintf (stderr, "%s\tNeighbor: %s\nCost: %d\n", type, (char *) 
&encPeer,
            neighbor->cost);
-
+  else
+  {
+       GNUNET_hash_to_enc (&neighbor->referrer->hashPubKey, &encReferrer);
+       fprintf (stderr, "%s\tNeighbor: %s\nCost: %d Referred by: %s\n", type, 
(char *) &encPeer,
+                  neighbor->cost, (char*)&encReferrer);
+  }
   return GNUNET_OK;
 }
 
@@ -105,7 +110,7 @@
  * or having been gossiped about, also called when a cost for a neighbor
  * needs to be updated.
  *
- * @param neighbor - ident of the peer whose info is being added/updated
+ * @param neighbor - identity of the peer whose info is being added/updated
  * @param referrer - if this is a gossiped peer, who did we hear it from?
  * @param cost - the cost to this peer (the actual important part!)
  *
@@ -118,12 +123,17 @@
   struct GNUNET_dv_neighbor *neighbor;
 #ifdef DEBUG_DV
   GNUNET_EncName encPeer;
+  GNUNET_EncName encReferrer;
+  fprintf (stderr, "Entering addUpdateNeighbor\n");
 
-  fprintf (stderr, "Entering addUpdateNeighbor\n");
+  GNUNET_hash_to_enc (&peer->hashPubKey, &encPeer);
   if (referrer == NULL)
-    fprintf (stderr, "Referrer is NULL\n");
-  GNUNET_hash_to_enc (&peer->hashPubKey, &encPeer);
-  fprintf (stderr, "Adding/Updating Node %s\n", (char *) &encPeer);
+       fprintf (stderr, "Adding/Updating Node %s\n", (char *) &encPeer);
+  else
+  {
+       GNUNET_hash_to_enc (&referrer->hashPubKey, &encReferrer);
+       fprintf (stderr, "Adding/Updating Node %s, Learned about from %s\n", 
(char *) &encPeer, (char *) &encReferrer);
+  }
 #endif
   ret = GNUNET_OK;
 
@@ -299,13 +309,29 @@
 }
 
 /*
- * May use as a callback for deleting nodes from heaps...
+ * A callback for deleting nodes from heaps...
  */
-static void
+static int
 delete_callback (struct GNUNET_dv_neighbor *neighbor,
-                 struct GNUNET_dv_heap *root, GNUNET_PeerIdentity * toMatch)
+               struct GNUNET_dv_heap *root, void * cls)
 {
-  if (memcmp (neighbor->referrer, toMatch, sizeof (GNUNET_PeerIdentity)) == 0)
+       GNUNET_PeerIdentity * toMatch = cls;
+#ifdef DEBUG_DV
+       GNUNET_EncName encNeighbor;
+       GNUNET_EncName encReferrer;
+       GNUNET_EncName encToMatch;
+
+       GNUNET_hash_to_enc (&neighbor->neighbor->hashPubKey, &encNeighbor);
+       GNUNET_hash_to_enc (&toMatch->hashPubKey, &encToMatch);
+       if (neighbor->referrer != NULL)
+       {
+               GNUNET_hash_to_enc (&neighbor->referrer->hashPubKey, 
&encReferrer);
+               fprintf(stderr, "Checking for node\n%s to match\n%s or\n%s\n", 
(char *)&encToMatch, (char *)&encNeighbor, (char *)&encReferrer);
+       }
+       fprintf(stderr, "Checking for node %s to match %s\n", (char 
*)&encToMatch, (char *)&encNeighbor);
+#endif
+
+  if ((memcmp (neighbor->neighbor, toMatch, sizeof (GNUNET_PeerIdentity)) == 
0) || ((neighbor->referrer != NULL) && (memcmp (neighbor->referrer, toMatch, 
sizeof (GNUNET_PeerIdentity)) == 0)))
     {
       GNUNET_DV_Heap_removeNode (&ctx->neighbor_max_heap, neighbor);
       GNUNET_DV_Heap_removeNode (&ctx->neighbor_min_heap, neighbor);
@@ -313,26 +339,23 @@
                                         &neighbor->neighbor->hashPubKey);
 
       GNUNET_free (neighbor->neighbor);
-      GNUNET_free (neighbor->referrer);
+      if (neighbor->referrer != NULL)
+       GNUNET_free (neighbor->referrer);
       GNUNET_free (neighbor);
     }
-  return;
+  return GNUNET_OK;
 }
 
 /*
- * Handles the receipt of a peer disconnect notification.
+ * Handles the receipt of a peer disconnect notification, removing
+ * the direct neighbor from the direct list and any referenced
+ * neighbors as well.
  *
  * @param peer - the peer that has disconnected from us
  */
 static void
 peer_disconnect_handler (const GNUNET_PeerIdentity * peer, void *unused)
 {
-/*
- * Update for heap and hashmap structures.  Namely, replace linked list
- * iteration with hashmap lookup.  Will also need to traverse *both* heaps
- * to find and remove any peers that have peer as their referrer! A
- * callback implementation probably makes more sense...
- */
   struct GNUNET_dv_neighbor *neighbor;
 
 #ifdef DEBUG_DV
@@ -356,8 +379,8 @@
           GNUNET_multi_hash_map_remove_all (ctx->direct_neighbors,
                                             &peer->hashPubKey);
 
-          GNUNET_DV_Heap_Iterator (&delete_callback, &ctx->neighbor_max_heap,
-                                   ctx->neighbor_max_heap.root, peer);
+          GNUNET_DV_Heap_Iterator (&ctx->neighbor_max_heap,
+                                   ctx->neighbor_max_heap.root, 
&delete_callback, (void *)peer);
 
           GNUNET_free (neighbor->neighbor);
           if (neighbor->referrer)
@@ -459,6 +482,14 @@
 {
   int ok = GNUNET_OK;
   unsigned long long max_hosts;
+
+  ctx = GNUNET_malloc(sizeof(struct GNUNET_DV_Context));
+
+  ctx->neighbor_min_heap.type = GNUNET_DV_MIN_HEAP;
+  ctx->neighbor_max_heap.type = GNUNET_DV_MAX_HEAP;
+  ctx->neighbor_min_heap.max_size = GNUNET_DV_MAX_TABLE_SIZE;
+  ctx->neighbor_max_heap.max_size = GNUNET_DV_MAX_TABLE_SIZE;
+  ctx->send_interval = GNUNET_DV_DEFAULT_SEND_INTERVAL;
   ctx->dvMutex = GNUNET_mutex_create (GNUNET_NO);
   coreAPI = capi;
   GNUNET_GE_LOG (capi->ectx,
@@ -484,8 +515,8 @@
     ok = GNUNET_SYSERR;
 
 
-  sendingThread =
-    GNUNET_thread_create (&neighbor_send_thread, &coreAPI, 1024 * 1);
+  /*sendingThread =
+    GNUNET_thread_create (&neighbor_send_thread, &coreAPI, 1024 * 1);*/
 
 
   GNUNET_GC_get_configuration_value_number (coreAPI->cfg,

Modified: GNUnet/src/applications/dv/module/heap.c
===================================================================
--- GNUnet/src/applications/dv/module/heap.c    2009-01-14 13:03:05 UTC (rev 
8107)
+++ GNUnet/src/applications/dv/module/heap.c    2009-01-14 17:58:25 UTC (rev 
8108)
@@ -24,7 +24,9 @@
  * @brief Implementation of heap operations
  */
 
-
+#include "platform.h"
+#include "gnunet_protocols.h"
+#include "gnunet_util.h"
 #include "dv.h"
 #include "heap.h"
 
@@ -205,6 +207,57 @@
   return;
 }
 
+struct GNUNET_dv_neighbor *
+GNUNET_DV_Heap_removeNode (struct GNUNET_dv_heap *root,
+                           struct GNUNET_dv_neighbor *neighbor)
+{
+  struct GNUNET_dv_neighbor *ret;
+  struct GNUNET_dv_heap_node *del_node;
+  struct GNUNET_dv_heap_node *last;
+
+       del_node = NULL;
+  if (root->type == GNUNET_DV_MAX_HEAP)
+    del_node = neighbor->max_loc;
+  else if (root->type == GNUNET_DV_MIN_HEAP)
+    del_node = neighbor->min_loc;
+
+  if (del_node == NULL)
+    return NULL;
+
+  ret = del_node->neighbor;
+  last = getPos (root, root->size);
+  del_node->neighbor = last->neighbor;
+
+  if (last->parent->left_child == last)
+    last->parent->left_child = NULL;
+  if (last->parent->right_child == last)
+    last->parent->right_child = NULL;
+
+  if (root->traversal_pos == last)
+    {
+      root->traversal_pos = root->root;
+    }
+  GNUNET_free (last);
+  root->size--;
+
+  if (del_node->neighbor->cost > ret->cost)
+    {
+      if (root->type == GNUNET_DV_MAX_HEAP)
+        percolateHeap (del_node, root);
+      else if (root->type == GNUNET_DV_MIN_HEAP)
+        percolateDownHeap (del_node, root);
+    }
+  else if (del_node->neighbor->cost < ret->cost)
+    {
+      if (root->type == GNUNET_DV_MAX_HEAP)
+        percolateDownHeap (del_node, root);
+      else if (root->type == GNUNET_DV_MIN_HEAP)
+        percolateHeap (del_node, root);
+    }
+
+  return ret;
+}
+
 int
 GNUNET_DV_Heap_insert (struct GNUNET_dv_heap *root,
                        struct GNUNET_dv_neighbor *neighbor)
@@ -218,6 +271,10 @@
       new_pos = getNextPos (root);
       new_pos->neighbor = neighbor;
       root->size++;
+      if (root->type == GNUNET_DV_MIN_HEAP)
+       new_pos->neighbor->min_loc = new_pos;
+      else if (root->type == GNUNET_DV_MAX_HEAP)
+       new_pos->neighbor->max_loc = new_pos;
       percolateHeap (new_pos, root);
     }
   else
@@ -257,56 +314,6 @@
   return ret;
 }
 
-struct GNUNET_dv_neighbor *
-GNUNET_DV_Heap_removeNode (struct GNUNET_dv_heap *root,
-                           struct GNUNET_dv_neighbor *neighbor)
-{
-  struct GNUNET_dv_neighbor *ret;
-  struct GNUNET_dv_heap_node *del_node;
-  struct GNUNET_dv_heap_node *last;
-
-  if (root->type == GNUNET_DV_MAX_HEAP)
-    del_node = neighbor->max_loc;
-  else if (root->type == GNUNET_DV_MIN_HEAP)
-    del_node = neighbor->min_loc;
-
-  if (del_node == NULL)
-    return NULL;
-
-  ret = del_node->neighbor;
-  last = getPos (root, root->size);
-  del_node->neighbor = last->neighbor;
-
-  if (last->parent->left_child == last)
-    last->parent->left_child = NULL;
-  if (last->parent->right_child == last)
-    last->parent->right_child = NULL;
-
-  if (root->traversal_pos == last)
-    {
-      root->traversal_pos = root->root;
-    }
-  GNUNET_free (last);
-  root->size--;
-
-  if (del_node->neighbor->cost > ret->cost)
-    {
-      if (root->type == GNUNET_DV_MAX_HEAP)
-        percolateHeap (del_node, root);
-      else if (root->type == GNUNET_DV_MIN_HEAP)
-        percolateDownHeap (del_node, root);
-    }
-  else if (del_node->neighbor->cost < ret->cost)
-    {
-      if (root->type == GNUNET_DV_MAX_HEAP)
-        percolateDownHeap (del_node, root);
-      else if (root->type == GNUNET_DV_MIN_HEAP)
-        percolateHeap (del_node, root);
-    }
-
-  return ret;
-}
-
 int
 GNUNET_DV_Heap_updateCost (struct GNUNET_dv_heap *root,
                            struct GNUNET_dv_neighbor *neighbor,
@@ -325,8 +332,6 @@
 {
   struct GNUNET_dv_heap_node *node;
   struct GNUNET_dv_heap_node *parent;
-  struct GNUNET_dv_heap_node *left_child;
-  struct GNUNET_dv_heap_node *right_child;
 
   if (neighbor == NULL)
     return GNUNET_SYSERR;
@@ -363,49 +368,48 @@
                                           struct GNUNET_dv_heap_node *node,
                                           GNUNET_PeerIdentity * toMatch)
 {
+       int count = 0;
   if (node->left_child != NULL)
     {
-      GNUNET_DV_Heap_delete_matching_referrers (root, node->left_child,
+      count += GNUNET_DV_Heap_delete_matching_referrers (root, 
node->left_child,
                                                 toMatch);
     }
   if (node->right_child != NULL)
     {
-      GNUNET_DV_Heap_delete_matching_referrers (root, node->right_child,
+       count += GNUNET_DV_Heap_delete_matching_referrers (root, 
node->right_child,
                                                 toMatch);
     }
   if ((node->neighbor != NULL)
       &&
-      (memcmp (node->neighbor, toMatch, sizeof (struct GNUNET_PeerIdentity))
+      (memcmp (node->neighbor, toMatch, sizeof (GNUNET_PeerIdentity))
        == 0))
     {
-      GNUNET_DV_removeNode (root, node->neighbor);
+      GNUNET_DV_Heap_removeNode (root, node->neighbor);
+      count++;
     }
 
+       return count;
+
 }
 
 void
-GNUNET_DV_Heap_Iterator (void (*callee)
-                         (struct GNUNET_dv_neighbor * neighbor,
-                          struct GNUNET_dv_heap * root,
-                          GNUNET_PeerIdentity * toMatch),
-                         struct GNUNET_dv_heap *root,
-                         struct GNUNET_dv_heap_node *node,
-                         const GNUNET_PeerIdentity * toMatch)
+GNUNET_DV_Heap_Iterator (struct GNUNET_dv_heap *root,struct 
GNUNET_dv_heap_node *node
+                                                                               
                ,GNUNET_HeapIterator iterator,void *cls)
 {
 
   if (node->left_child != NULL)
     {
-      GNUNET_DV_Heap_Iterator (callee, root, node->left_child, toMatch);
+      GNUNET_DV_Heap_Iterator (root, node->left_child, iterator, cls);
     }
 
   if (node->right_child != NULL)
     {
-      GNUNET_DV_Heap_Iterator (callee, root, node->right_child, toMatch);
+      GNUNET_DV_Heap_Iterator (root, node->right_child, iterator, cls);
     }
 
   if (node->neighbor != NULL)
     {
-      callee (node->neighbor, root);
+      iterator(node->neighbor, root, cls);
     }
 }
 
@@ -428,10 +432,12 @@
   choice = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 1);
 
   switch (choice)
+  {
     case 1:
-    root->traversal_pos = root->traversal_pos->right_child;
-case 0:
-  root->traversal_pos = root->traversal_pos->left_child;
+       root->traversal_pos = root->traversal_pos->right_child;
+    case 0:
+       root->traversal_pos = root->traversal_pos->left_child;
+  }
 
   return neighbor;
 

Modified: GNUnet/src/applications/dv/module/heap.h
===================================================================
--- GNUnet/src/applications/dv/module/heap.h    2009-01-14 13:03:05 UTC (rev 
8107)
+++ GNUnet/src/applications/dv/module/heap.h    2009-01-14 17:58:25 UTC (rev 
8108)
@@ -97,12 +97,14 @@
  * Iterator for heap
  *
  * @param value - obj stored in heap
+ * @param root - root of heap in which obj is stored
  * @param cls - client arg passed through
  * @return GNUNET_YES if we should continue to
  *         iterate,
  *         GNUNET_NO if not.
  */
-typedef int (*GNUNET_HeapIterator) (void *value, void *cls);
+typedef int (*GNUNET_HeapIterator) (struct GNUNET_dv_neighbor *neighbor,
+               struct GNUNET_dv_heap *root, void *cls);
 
 /**
  * Iterate over all entries in the map.
@@ -171,13 +173,10 @@
  * Iterator to go over all nodes in the tree... Goes from the bottom up
  */
 void
-GNUNET_DV_Heap_Iterator (void (*callee)
-                         (struct GNUNET_dv_neighbor * neighbor,
-                          struct GNUNET_dv_heap * root,
-                          GNUNET_PeerIdentity * toMatch),
-                         struct GNUNET_dv_heap *root,
+GNUNET_DV_Heap_Iterator (struct GNUNET_dv_heap *root,
                          struct GNUNET_dv_heap_node *node,
-                         const GNUNET_PeerIdentity * toMatch);
+                         GNUNET_HeapIterator iterator,
+                         void *cls);
 
 
 /**