[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r8000 - GNUnet/src/applications/dv/module
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r8000 - GNUnet/src/applications/dv/module |
|
Date: |
Sat, 13 Dec 2008 17:36:20 -0700 (MST) |
Author: nevans
Date: 2008-12-13 17:36:20 -0700 (Sat, 13 Dec 2008)
New Revision: 8000
Added:
GNUnet/src/applications/dv/module/heap.c
GNUnet/src/applications/dv/module/heap.h
GNUnet/src/applications/dv/module/heaptest.c
Modified:
GNUnet/src/applications/dv/module/dv.c
Log:
compiles for me, DO NOT USE THOUGH
Modified: GNUnet/src/applications/dv/module/dv.c
===================================================================
--- GNUnet/src/applications/dv/module/dv.c 2008-12-12 21:29:30 UTC (rev
7999)
+++ GNUnet/src/applications/dv/module/dv.c 2008-12-14 00:36:20 UTC (rev
8000)
@@ -30,97 +30,183 @@
#include "gnunet_util.h"
#include "gnunet_core.h"
#include "dv.h"
+#include "heap.h"
#define DEBUG_DV
-/**
- * TODO: Add code for initialization/maintenance of directly
- * connected and all known, code for sending and receiving neighbor lists
- * (more likely sending and receiving incrementally) and . ? . ? .
- */
-// CG: if you must have globals, you MUST make them
-// all "static", we do not want to have
-// a global symbol "closing"!
-unsigned long long fisheye_depth;
-unsigned long long max_table_size;
-unsigned int send_interval = 1000;
-// CG: all static/global variables are initially
-// set to zero, so = 0 is superfluous.
-unsigned int curr_neighbor_table_size = 0;
-unsigned int curr_connected_neighbor_table_size = 0;
-unsigned short closing = 0;
+struct GNUNET_DV_Context
+{
+ unsigned long long fisheye_depth;
+ unsigned long long max_table_size;
+ unsigned int send_interval;
-static struct GNUNET_ThreadHandle *connectionThread;
+ unsigned int curr_neighbor_table_size;
+ unsigned int curr_connected_neighbor_table_size;
+ unsigned short closing;
-// CG: document each struct
-struct GNUNET_dv_neighbor
-{
- /**
- * Generic list structure for neighbor lists
- */
- struct GNUNET_dv_neighbor *next;
- struct GNUNET_dv_neighbor *prev;
+ struct GNUNET_Mutex *dvMutex;
+ struct GNUNET_MultiHashMap *direct_neighbors;
- /**
- * Identity of neighbor
- */
- GNUNET_PeerIdentity *neighbor;
+ struct GNUNET_MultiHashMap *extended_neighbors;
+ struct GNUNET_dv_heap neighbor_min_heap;
+ struct GNUNET_dv_heap neighbor_max_heap;
- /**
- * Identity of referrer (where we got the information)
- */
- GNUNET_PeerIdentity *referrer;
- /**
- * Cost to neighbor, used for actual distance vector computations
- */
- unsigned int cost;
};
-struct GNUNET_dv_neighbor *neighbors;
-struct GNUNET_dv_neighbor *connected_neighbors;
-
+static struct GNUNET_DV_Context *ctx;
+static struct GNUNET_ThreadHandle *sendingThread;
static GNUNET_CoreAPIForPlugins *coreAPI;
-static struct GNUNET_Mutex *dvMutex;
+// CG: unless defined in a header and used by
+// other C source files (or used with dlsym),'
+// make sure all of your functions are declared "static"
+static int
+printTableEntry (const GNUNET_HashCode * key,
+ void *value, void *cls)
+{
+ struct GNUNET_dv_neighbor *neighbor = (struct GNUNET_dv_neighbor *)value;
+ char *type = (char *)cls;
+ GNUNET_EncName encPeer;
-static void
-printTables ()
+ GNUNET_hash_to_enc (&neighbor->referrer->hashPubKey, &encPeer);
+ fprintf (stderr, "%s\tNeighbor: %s\nCost: %d",type, (char *) &encPeer,
neighbor->cost);
+
+ return GNUNET_OK;
+}
+
+static void print_tables()
{
- struct GNUNET_dv_neighbor *pos;
- unsigned int count;
+ fprintf (stderr, "Printing directly connected neighbors:\n");
+ GNUNET_multi_hash_map_iterate(ctx->direct_neighbors, &printTableEntry,
"DIRECT");
+
+ fprintf (stderr, "Printing extended neighbors:\n");
+ GNUNET_multi_hash_map_iterate(ctx->extended_neighbors,
&printTableEntry, "EXTENDED");
+
+ return;
+}
+
+/*
+static int
+p2pHandleDVRouteMessage (const GNUNET_PeerIdentity * sender,
+ const GNUNET_MessageHeader * message)
+{
+
+ return GNUNET_OK;
+}
+*/
+
+/*
+ * Handles when a peer is either added due to being newly connected
+ * 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 referrer - if this is a gossiped peer, who did we hear it from?
+ * @param cost - the cost to this peer (the actual important part!)
+ *
+ */
+static int
+addUpdateNeighbor (const GNUNET_PeerIdentity * peer,
+ const GNUNET_PeerIdentity * referrer, unsigned int cost)
+{
+ int ret;
+ struct GNUNET_dv_neighbor *neighbor;
+#ifdef DEBUG_DV
GNUNET_EncName encPeer;
- pos = connected_neighbors;
- count = 0;
- fprintf (stderr, "Directly connected neighbors:\n");
- while (pos != NULL)
- {
- GNUNET_hash_to_enc (&pos->neighbor->hashPubKey, &encPeer);
- fprintf (stderr, "\t%d : %s\n", count, (char *) &encPeer);
- pos = pos->next;
- count++;
- }
+ fprintf (stderr, "Entering addUpdateNeighbor\n");
+ 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);
+#endif
+ ret = GNUNET_OK;
- fprintf (stderr, "Known neighbors:\n");
- pos = neighbors;
- count = 0;
- while (pos != NULL)
- {
- GNUNET_hash_to_enc (&pos->neighbor->hashPubKey, &encPeer);
- fprintf (stderr, "\t%d : %s\n", count, (char *) &encPeer);
- pos = pos->next;
- count++;
- }
+ GNUNET_mutex_lock(ctx->dvMutex);
+ if (GNUNET_YES !=
GNUNET_multi_hash_map_contains(ctx->extended_neighbors,&peer->hashPubKey))
+ {
+ neighbor = GNUNET_malloc(sizeof (struct GNUNET_dv_neighbor));
+ neighbor->cost = cost;
+ neighbor->neighbor = GNUNET_malloc(sizeof(GNUNET_PeerIdentity));
+ memcpy(neighbor->neighbor,peer,sizeof(GNUNET_PeerIdentity));
+ GNUNET_multi_hash_map_put
(ctx->extended_neighbors,&peer->hashPubKey,
+
neighbor,
+
GNUNET_MultiHashMapOption_REPLACE);
+
+ GNUNET_DV_Heap_insert(&ctx->neighbor_max_heap, neighbor);
+ GNUNET_DV_Heap_insert(&ctx->neighbor_min_heap, neighbor);
+
+ }
+ else
+ {
+ neighbor =
GNUNET_multi_hash_map_get(ctx->extended_neighbors,&peer->hashPubKey);
+
+ if (neighbor->cost > cost)
+ {
+ if (memcmp(neighbor->referrer, peer,
sizeof(GNUNET_PeerIdentity)) == 0)
+ {
+ neighbor->cost = cost;
+
GNUNET_DV_Heap_updatedCost(&ctx->neighbor_max_heap, neighbor);
+
GNUNET_DV_Heap_updatedCost(&ctx->neighbor_min_heap, neighbor);
+ }
+ else
+ {
+
GNUNET_DV_Heap_removeNode(&ctx->neighbor_max_heap, neighbor);
+
GNUNET_DV_Heap_removeNode(&ctx->neighbor_min_heap, neighbor);
+ GNUNET_free(neighbor->neighbor);
+ GNUNET_free(neighbor->referrer);
+ GNUNET_free(neighbor);
+
+ neighbor = GNUNET_malloc(sizeof (struct
GNUNET_dv_neighbor));
+ neighbor->cost = cost;
+ neighbor->neighbor =
GNUNET_malloc(sizeof(GNUNET_PeerIdentity));
+
memcpy(neighbor->neighbor,peer,sizeof(GNUNET_PeerIdentity));
+ if (referrer == NULL)
+ neighbor->referrer = NULL;
+ else
+ memcpy(neighbor->referrer, referrer,
sizeof(GNUNET_PeerIdentity));
+
+ GNUNET_multi_hash_map_put
(ctx->extended_neighbors,&peer->hashPubKey,
+
neighbor,
+
GNUNET_MultiHashMapOption_REPLACE);
+
+ GNUNET_DV_Heap_insert(&ctx->neighbor_max_heap,
neighbor);
+ GNUNET_DV_Heap_insert(&ctx->neighbor_min_heap,
neighbor);
+ }
+ }
+ else if ((neighbor->cost < cost) && (memcmp(neighbor->referrer,
referrer, sizeof(GNUNET_PeerIdentity)) == 0))
+ {
+ neighbor->cost = cost;
+
+ GNUNET_DV_Heap_updatedCost(&ctx->neighbor_max_heap,
neighbor);
+ GNUNET_DV_Heap_updatedCost(&ctx->neighbor_min_heap,
neighbor);
+
+ }
+
+ }
+
+#ifdef DEBUG_DV
+ print_tables();
+ fprintf (stderr, "Exiting addUpdateNeighbor\n");
+#endif
+
+ GNUNET_mutex_unlock (ctx->dvMutex);
+ return ret;
}
+
static int
p2pHandleDVNeighborMessage (const GNUNET_PeerIdentity * sender,
const GNUNET_MessageHeader * message)
{
int ret = GNUNET_OK;
const p2p_dv_MESSAGE_NeighborInfo *nmsg;
+#ifdef DEBUG_DV
+ GNUNET_EncName from;
+ GNUNET_EncName about;
+#endif
if (ntohs (message->size) < sizeof (p2p_dv_MESSAGE_NeighborInfo))
{
@@ -128,10 +214,6 @@
return GNUNET_SYSERR; /* invalid message */
}
nmsg = (const p2p_dv_MESSAGE_NeighborInfo *) message;
- /*
- * Need to fix nmsg->cost comparison to make sense!
- */
- /*if ((nmsg->cost + 1 <= fisheye_depth) &&
(findNeighbor(&nmsg->neighbor,sender) == NULL)) */
ret = addUpdateNeighbor (&nmsg->neighbor, sender, ntohl (nmsg->cost));
@@ -140,237 +222,159 @@
GNUNET_GE_DEBUG | GNUNET_GE_REQUEST | GNUNET_GE_USER,
_("Problem adding/updating neighbor in `%s'\n"), "dv");
+#ifdef DEBUG_DV
+ GNUNET_hash_to_enc (&sender->hashPubKey, &from);
+ GNUNET_hash_to_enc (&nmsg->neighbor.hashPubKey, &about);
+ fprintf (stderr,
+ "Received info about peer %s from directly connected peer %s\n",
+ (char *) &about, (char *) &from);
+#endif
return ret;
}
/*
- * Handles the receipt of a peer disconnect notification.
- *
+ * Handles a peer connect notification, eliminates any need for polling.
+ * @param peer - ident of the connected peer
+ * @param unused - unused closure arg
*/
static void
-peer_disconnect_handler (const GNUNET_PeerIdentity * peer, void *unused)
+peer_connect_handler (const GNUNET_PeerIdentity * peer, void *unused)
{
- GNUNET_EncName myself;
- struct GNUNET_dv_neighbor *pos = neighbors;
- struct GNUNET_dv_neighbor *temp = NULL;
-
#ifdef DEBUG_DV
- fprintf (stderr, "Entering peer_disconnect_handler\n");
- GNUNET_hash_to_enc (&peer->hashPubKey, &myself);
- fprintf (stderr, "disconnected peer: %s\n", (char *) &myself);
- printTables ();
+ fprintf (stderr, "Entering peer_connect_handler:\n");
+ print_tables();
+
#endif
- GNUNET_mutex_lock (dvMutex);
+ struct GNUNET_dv_neighbor *neighbor;
+ unsigned int cost = GNUNET_DV_LEAST_COST;
- while (pos != NULL)
- {
- if (memcmp (peer, pos->referrer, sizeof (GNUNET_PeerIdentity)) == 0)
- {
- if (pos->prev != NULL)
- pos->prev->next = pos->next;
- else
- neighbors = pos->next;
+ if (GNUNET_YES !=
GNUNET_multi_hash_map_contains(ctx->direct_neighbors,&peer->hashPubKey))
+ {
+ neighbor = GNUNET_malloc(sizeof (struct GNUNET_dv_neighbor));
+ neighbor->cost = cost;
+ neighbor->neighbor = GNUNET_malloc(sizeof(GNUNET_PeerIdentity));
+ memcpy(neighbor->neighbor,peer, sizeof(GNUNET_PeerIdentity));
+ GNUNET_multi_hash_map_put
(ctx->direct_neighbors,&peer->hashPubKey,
+
neighbor,
+
GNUNET_MultiHashMapOption_REPLACE);
+ }
+ else
+ {
+ neighbor =
GNUNET_multi_hash_map_get(ctx->direct_neighbors,&peer->hashPubKey);
- if (pos->next != NULL)
- pos->next->prev = pos->prev;
- temp = pos->next;
- GNUNET_free (pos->neighbor);
- if (pos->referrer != NULL)
- GNUNET_free (pos->referrer);
- GNUNET_free (pos);
- pos = temp;
- curr_neighbor_table_size--;
- }
- else
- pos = pos->next;
- }
+ if (neighbor->cost != cost)
+ {
+ GNUNET_mutex_lock(ctx->dvMutex);
+ GNUNET_multi_hash_map_put
(ctx->direct_neighbors,&peer->hashPubKey,
+
neighbor,
+
GNUNET_MultiHashMapOption_REPLACE);
+ GNUNET_mutex_unlock(ctx->dvMutex);
+ }
- pos = connected_neighbors;
- while (pos != NULL)
- {
- if (memcmp (peer, pos->neighbor, sizeof (GNUNET_PeerIdentity)) == 0)
- {
- if (pos->prev != NULL)
- pos->prev->next = pos->next;
- else
- connected_neighbors = pos->next;
+ }
- if (pos->next != NULL)
- pos->next->prev = pos->prev;
+ addUpdateNeighbor(peer, NULL, cost);
- temp = pos->next;
- GNUNET_free (pos->neighbor);
- if (pos->referrer != NULL)
- GNUNET_free (pos->referrer);
- GNUNET_free (pos);
- pos = temp;
- curr_connected_neighbor_table_size--;
- }
- else
- pos = pos->next;
- }
-
- GNUNET_mutex_unlock (dvMutex);
#ifdef DEBUG_DV
- printTables ();
- fprintf (stderr, "Exiting peer_disconnect_handler\n");
+ print_tables();
#endif
- return;
+ return;
+
}
/*
- * Finds a neighbor in the distance vector table. Logically there is only one
- * routing table, but for optimization purposes they are separated into those
- * that are directly connected, and those that are known by reference.
- *
- * @param neighbor peer to look up
- * @param connected which list to look in
+ * May use as a callback for deleting nodes from heaps...
*/
-struct GNUNET_dv_neighbor *
-findNeighbor (const GNUNET_PeerIdentity * neighbor, short connected)
+static void
+delete_callback(struct GNUNET_dv_neighbor *neighbor, struct GNUNET_dv_heap
*root,GNUNET_PeerIdentity * toMatch)
{
-#ifdef DEBUG_DV
- fprintf (stderr, "Entering findNeighbor\n");
-#endif
- struct GNUNET_dv_neighbor *pos;
- if (connected)
- pos = connected_neighbors;
- else
- pos = neighbors;
+ if (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);
+ GNUNET_multi_hash_map_remove_all(ctx->extended_neighbors,
&neighbor->neighbor->hashPubKey);
- while (pos != NULL)
- {
- if (memcmp (neighbor, pos->neighbor, sizeof (GNUNET_PeerIdentity)) == 0)
- {
-#ifdef DEBUG_DV
- fprintf (stderr, "FOUND Neighbor!!!\n");
-#endif
- return pos;
-
- }
- pos = pos->next;
- }
-#ifdef DEBUG_DV
- fprintf (stderr, "Exiting findNeighbor\n");
-#endif
- return pos;
+ GNUNET_free(neighbor->neighbor);
+ GNUNET_free(neighbor->referrer);
+ GNUNET_free(neighbor);
+ }
+ return;
}
-static int
-addUpdateNeighbor (const GNUNET_PeerIdentity * neighbor,
- const GNUNET_PeerIdentity * referrer, unsigned int cost)
+/*
+ * Handles the receipt of a peer disconnect notification.
+ *
+ * @param peer - the peer that has disconnected from us
+ */
+static void
+peer_disconnect_handler (const GNUNET_PeerIdentity * peer, void *unused)
{
-#ifdef DEBUG_DV
- fprintf (stderr, "Entering addUpdateNeighbor\n");
- if (referrer == NULL)
- fprintf (stderr, "Referrer is NULL\n");
-#endif
- int ret = GNUNET_OK;
+/*
+ * 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;
- GNUNET_mutex_lock (dvMutex);
- GNUNET_EncName encPeer;
- struct GNUNET_dv_neighbor *dv_neighbor;
-
#ifdef DEBUG_DV
- GNUNET_hash_to_enc (&neighbor->hashPubKey, &encPeer);
- fprintf (stderr, "Adding Node %s\n", (char *) &encPeer);
+ GNUNET_EncName myself;
+ fprintf (stderr, "Entering peer_disconnect_handler\n");
+ GNUNET_hash_to_enc (&peer->hashPubKey, &myself);
+ fprintf (stderr, "disconnected peer: %s\n", (char *) &myself);
+ print_tables();
#endif
- if (referrer == NULL)
- dv_neighbor = findNeighbor (neighbor, 1);
- else
- dv_neighbor = findNeighbor (neighbor, 0);
+ GNUNET_mutex_lock (ctx->dvMutex);
- if (dv_neighbor != NULL)
- {
- if (dv_neighbor->cost != cost)
- {
- dv_neighbor->cost = cost;
- }
- if ((referrer != NULL) && (dv_neighbor->referrer != NULL)
- &&
- (memcmp
- (dv_neighbor->referrer, referrer,
- sizeof (GNUNET_PeerIdentity)) != 0))
- {
- GNUNET_free (dv_neighbor->referrer);
- dv_neighbor->referrer =
- GNUNET_malloc (sizeof (GNUNET_PeerIdentity));
- memcpy (dv_neighbor->referrer, referrer,
- sizeof (GNUNET_PeerIdentity));
- }
- else if ((referrer != NULL) && (dv_neighbor->referrer == NULL))
- {
- dv_neighbor->referrer =
- GNUNET_malloc (sizeof (GNUNET_PeerIdentity));
- memcpy (dv_neighbor->referrer, referrer,
- sizeof (GNUNET_PeerIdentity));
- }
- }
- else
- {
+ if (GNUNET_YES == GNUNET_multi_hash_map_contains(ctx->direct_neighbors,
&peer->hashPubKey))
+ {
+ neighbor = GNUNET_multi_hash_map_get(ctx->direct_neighbors,
&peer->hashPubKey);
+ if (neighbor != NULL)
+ {
+ GNUNET_multi_hash_map_remove_all(ctx->direct_neighbors,
&peer->hashPubKey);
- dv_neighbor = GNUNET_malloc (sizeof (struct GNUNET_dv_neighbor));
- dv_neighbor->neighbor = malloc (sizeof (GNUNET_PeerIdentity));
- memcpy (dv_neighbor->neighbor, neighbor, sizeof (GNUNET_PeerIdentity));
- dv_neighbor->cost = cost;
+ GNUNET_DV_Heap_Iterator (&delete_callback,
&ctx->neighbor_max_heap, ctx->neighbor_max_heap.root, peer);
- if (referrer != NULL)
- {
- dv_neighbor->referrer = malloc (sizeof (GNUNET_PeerIdentity));
- memcpy (dv_neighbor->referrer, referrer,
- sizeof (GNUNET_PeerIdentity));
- dv_neighbor->prev = NULL;
- if (neighbors != NULL)
- neighbors->prev = dv_neighbor;
- dv_neighbor->next = neighbors;
- neighbors = dv_neighbor;
- curr_neighbor_table_size++;
- }
- else
- {
- dv_neighbor->referrer = NULL;
+ GNUNET_free(neighbor->neighbor);
+ if (neighbor->referrer)
+ GNUNET_free(neighbor->referrer);
- dv_neighbor->prev = NULL;
- if (connected_neighbors != NULL)
- connected_neighbors->prev = dv_neighbor;
- dv_neighbor->next = connected_neighbors;
- connected_neighbors = dv_neighbor;
- curr_connected_neighbor_table_size++;
- }
- }
+ GNUNET_free(neighbor);
+ }
+ }
+
+ GNUNET_mutex_unlock (ctx->dvMutex);
#ifdef DEBUG_DV
- printTables ();
- fprintf (stderr, "Exiting addUpdateNeighbor\n");
+ print_tables ();
+ fprintf (stderr, "Exiting peer_disconnect_handler\n");
#endif
-
- GNUNET_mutex_unlock (dvMutex);
- return ret;
+ return;
}
-
-static void
-initialAddNeighbor (const GNUNET_PeerIdentity * neighbor, void *cls)
+static struct GNUNET_dv_neighbor *
+chooseToNeighbor ()
{
- addUpdateNeighbor (neighbor, NULL, GNUNET_DV_LEAST_COST);
- return;
+ if (GNUNET_multi_hash_map_size(ctx->direct_neighbors) == 0)
+ return NULL;
+
+ return (struct GNUNET_dv_neighbor
*)GNUNET_multi_hash_map_get_random(ctx->direct_neighbors);
}
-static void *
-connection_poll_thread (void *rcls)
+static struct GNUNET_dv_neighbor *
+chooseAboutNeighbor ()
{
- while (!closing)
- {
+ if (ctx->neighbor_min_heap.size == 0)
+ return NULL;
+
#ifdef DEBUG_DV
- fprintf (stderr, "Polling connections...\n");
+ fprintf (stderr, "Min heap size %d\nMax heap size %d\n",
ctx->neighbor_min_heap.size,ctx->neighbor_max_heap.size);
#endif
- coreAPI->p2p_connections_iterate (&initialAddNeighbor, NULL);
- GNUNET_thread_sleep (15 * GNUNET_CRON_SECONDS);
- }
- return NULL;
+ return GNUNET_DV_Heap_Walk_getNext(&ctx->neighbor_min_heap);
+
}
static void *
@@ -389,9 +393,9 @@
message->header.size = htons (sizeof (p2p_dv_MESSAGE_NeighborInfo));
message->header.type = htons (GNUNET_P2P_PROTO_DV_NEIGHBOR_MESSAGE);
- message->reserved = htonl (0);
- while (!closing)
+
+ while (!ctx->closing)
{
//updateSendInterval();
about = chooseAboutNeighbor ();
@@ -412,10 +416,10 @@
memcpy (&message->neighbor, about->neighbor,
sizeof (GNUNET_PeerIdentity));
coreAPI->ciphertext_send (to->neighbor, &message->header, 0,
- send_interval * GNUNET_CRON_MILLISECONDS);
+ ctx->send_interval *
GNUNET_CRON_MILLISECONDS);
}
- GNUNET_thread_sleep (send_interval * GNUNET_CRON_MILLISECONDS);
+ GNUNET_thread_sleep (ctx->send_interval * GNUNET_CRON_MILLISECONDS);
}
GNUNET_free (message);
@@ -425,86 +429,29 @@
return NULL;
}
-// CG: unless defined in a header and used by
-// other C source files (or used with dlsym),'
-// make sure all of your functions are declared "static"
-struct GNUNET_dv_neighbor *
-chooseToNeighbor ()
-{
- if (!(curr_connected_neighbor_table_size > 0))
- return NULL;
- unsigned int rand =
- GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK,
- curr_connected_neighbor_table_size);
- int i;
- struct GNUNET_dv_neighbor *pos = connected_neighbors;
-#ifdef DEBUG_DV
- fprintf (stderr, "# Connected: %d Rand: %d\n",
- curr_connected_neighbor_table_size, rand);
-#endif
- i = 0;
- while ((pos != NULL) && (i < rand))
- {
- pos = pos->next;
- i++;
- }
-
- return pos;
-}
-
-struct GNUNET_dv_neighbor *
-chooseAboutNeighbor ()
-{
- if (!(curr_connected_neighbor_table_size + curr_neighbor_table_size > 0))
- return NULL;
- int rand =
- GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK,
- curr_connected_neighbor_table_size +
- curr_neighbor_table_size);
- int i;
- struct GNUNET_dv_neighbor *pos;
-#ifdef DEBUG_DV
- fprintf (stderr, "Table size %d Rand %d\n",
- curr_connected_neighbor_table_size + curr_neighbor_table_size,
- rand);
-#endif
- if (rand < curr_connected_neighbor_table_size)
- pos = connected_neighbors;
- else
- {
- pos = neighbors;
- rand = rand - curr_connected_neighbor_table_size;
- }
-
- i = 0;
- while ((pos != NULL) && (i < rand))
- {
- pos = pos->next;
- i++;
- }
-
- return pos;
-}
-
int
initialize_module_dv (GNUNET_CoreAPIForPlugins * capi)
{
int ok = GNUNET_OK;
- dvMutex = GNUNET_mutex_create (GNUNET_NO);
+ unsigned long long max_hosts;
+ ctx->dvMutex = GNUNET_mutex_create (GNUNET_NO);
coreAPI = capi;
GNUNET_GE_LOG (capi->ectx,
GNUNET_GE_DEBUG | GNUNET_GE_REQUEST | GNUNET_GE_USER,
_("`%s' registering P2P handler %d\n"),
"dv", GNUNET_P2P_PROTO_DV_NEIGHBOR_MESSAGE);
- neighbors = NULL;
- connected_neighbors = NULL;
+
if (GNUNET_SYSERR ==
coreAPI->
peer_disconnect_notification_register (&peer_disconnect_handler, NULL))
ok = GNUNET_SYSERR;
+ if (GNUNET_SYSERR ==
+ coreAPI->
+ peer_connect_notification_register (&peer_connect_handler, NULL))
+ ok = GNUNET_SYSERR;
if (GNUNET_SYSERR ==
coreAPI->
@@ -512,21 +459,37 @@
&p2pHandleDVNeighborMessage))
ok = GNUNET_SYSERR;
- connectionThread =
- GNUNET_thread_create (&connection_poll_thread, NULL, 1024 * 16);
- 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,
"DV",
"FISHEYEDEPTH",
- 0, -1, 3, &fisheye_depth);
+ 0, -1, 3, &ctx->fisheye_depth);
GNUNET_GC_get_configuration_value_number (coreAPI->cfg,
"DV",
"TABLESIZE",
- 0, -1, 100, &max_table_size);
+ 0, -1, 100, &ctx->max_table_size);
+ GNUNET_GC_get_configuration_value_number (coreAPI->cfg,
+
"gnunetd","connection-max-hosts",1,-1,50,
+ &max_hosts);
+
+ ctx->direct_neighbors = GNUNET_multi_hash_map_create (max_hosts);
+ if (ctx->direct_neighbors == NULL)
+ {
+ ok = GNUNET_SYSERR;
+ }
+
+ ctx->extended_neighbors = GNUNET_multi_hash_map_create (ctx->max_table_size
* 3);
+ if (ctx->extended_neighbors == NULL)
+ {
+ ok = GNUNET_SYSERR;
+ }
+
GNUNET_GE_ASSERT (capi->ectx,
0 == GNUNET_GC_set_configuration_value_string (capi->cfg,
capi->ectx,
@@ -541,16 +504,17 @@
void
done_module_dv ()
{
- closing = 1;
+ ctx->closing = 1;
coreAPI->
p2p_ciphertext_handler_unregister (GNUNET_P2P_PROTO_DV_NEIGHBOR_MESSAGE,
&p2pHandleDVNeighborMessage);
coreAPI->peer_disconnect_notification_unregister (&peer_disconnect_handler,
NULL);
+ coreAPI->peer_disconnect_notification_unregister (&peer_connect_handler,
+ NULL);
-
- GNUNET_mutex_destroy (dvMutex);
+ GNUNET_mutex_destroy (ctx->dvMutex);
coreAPI = NULL;
}
Added: GNUnet/src/applications/dv/module/heap.c
===================================================================
--- GNUnet/src/applications/dv/module/heap.c (rev 0)
+++ GNUnet/src/applications/dv/module/heap.c 2008-12-14 00:36:20 UTC (rev
8000)
@@ -0,0 +1,406 @@
+/*
+ This file is part of GNUnet.
+ (C) 2008 Christian Grothoff (and other contributing authors)
+
+ GNUnet is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published
+ by the Free Software Foundation; either version 2, or (at your
+ option) any later version.
+
+ GNUnet is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GNUnet; see the file COPYING. If not, write to the
+ Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @author Nathan Evans
+ * @file applications/dv/module/heap.c
+ * @brief Implementation of heap operations
+ */
+
+
+#include "dv.h"
+#include "heap.h"
+
+void printTree(struct GNUNET_dv_heap_node *root)
+{
+ if (root->neighbor != NULL)
+ fprintf(stdout,"%d\n",root->neighbor->cost);
+ if (root->left_child != NULL)
+ printTree(root->left_child);
+ if (root->right_child != NULL)
+ printTree(root->right_child);
+}
+
+static struct GNUNET_dv_heap_node *getNextPos(struct GNUNET_dv_heap *root)
+{
+ struct GNUNET_dv_heap_node *ret;
+ struct GNUNET_dv_heap_node *parent;
+ int pos;
+ int depth;
+ int i;
+
+ ret = malloc(sizeof(struct GNUNET_dv_heap_node));
+ pos = root->size + 1;
+ depth = (int)log2(pos);
+ ret->left_child = NULL;
+ ret->right_child = NULL;
+
+ if (depth == 0)
+ {
+ ret->parent = NULL;
+ root->root = ret;
+ }
+ else
+ {
+ parent = root->root;
+ for (i=depth;i>1;i--)
+ {
+ if (((pos / (1 << (i-1))) % 2) == 0)
+ parent = parent->left_child;
+ else
+ parent = parent->right_child;
+ }
+
+ ret->parent = parent;
+ if ((pos % 2) == 0)
+ parent->left_child = ret;
+ else
+ parent->right_child = ret;
+
+ }
+
+ return ret;
+
+}
+
+static struct GNUNET_dv_heap_node *
+getPos(struct GNUNET_dv_heap *root,unsigned int pos)
+{
+ struct GNUNET_dv_heap_node *ret;
+
+ int depth;
+ int i;
+
+ depth = (int)log2(pos);
+ ret = NULL;
+ if (pos > root->size)
+ {
+ return ret;
+ }
+ else
+ {
+ ret = root->root;
+ for (i=depth;i>0;i--)
+ {
+ if (((pos / (1 << (i-1))) % 2) == 0)
+ ret = ret->left_child;
+ else
+ ret = ret->right_child;
+ }
+ }
+
+ return ret;
+
+}
+
+void
+swapNodes(struct GNUNET_dv_heap_node *first, struct GNUNET_dv_heap_node
*second, struct GNUNET_dv_heap *root)
+{
+ struct GNUNET_dv_neighbor *tempNeighbor;
+
+ tempNeighbor = first->neighbor;
+ first->neighbor = second->neighbor;
+ second->neighbor = tempNeighbor;
+
+ if ((root->type == GNUNET_DV_MAX_HEAP))
+ {
+ first->neighbor->max_loc = first;
+ second->neighbor->max_loc = second;
+ }
+ else if ((root->type == GNUNET_DV_MAX_HEAP))
+ {
+ first->neighbor->min_loc = first;
+ second->neighbor->min_loc = second;
+ }
+
+ return;
+}
+
+void
+percolateHeap(struct GNUNET_dv_heap_node *pos, struct GNUNET_dv_heap *root)
+{
+
+ while((pos->parent != NULL) &&
+ (((root->type == GNUNET_DV_MAX_HEAP) &&
(pos->parent->neighbor->cost < pos->neighbor->cost)) ||
+ ((root->type == GNUNET_DV_MIN_HEAP) &&
(pos->parent->neighbor->cost > pos->neighbor->cost))))
+ {
+ swapNodes(pos,pos->parent,root);
+ pos = pos->parent;
+ }
+
+ return;
+}
+
+
+
+void
+percolateDownHeap(struct GNUNET_dv_heap_node *pos, struct GNUNET_dv_heap *root)
+{
+ struct GNUNET_dv_heap_node *switchNeighbor;
+
+ switchNeighbor = pos;
+
+ if ((root->type == GNUNET_DV_MAX_HEAP))
+ {
+ if ((pos->left_child != NULL) &&
(pos->left_child->neighbor->cost > switchNeighbor->neighbor->cost))
+ {
+ switchNeighbor = pos->left_child;
+ }
+
+ if ((pos->right_child != NULL) &&
(pos->right_child->neighbor->cost > switchNeighbor->neighbor->cost))
+ {
+ switchNeighbor = pos->right_child;
+ }
+ }
+ else if ((root->type == GNUNET_DV_MIN_HEAP))
+ {
+ if ((pos->left_child != NULL) &&
(pos->left_child->neighbor->cost < switchNeighbor->neighbor->cost))
+ {
+ switchNeighbor = pos->left_child;
+ }
+
+ if ((pos->right_child != NULL) &&
(pos->right_child->neighbor->cost < switchNeighbor->neighbor->cost))
+ {
+ switchNeighbor = pos->right_child;
+ }
+ }
+
+ if (switchNeighbor != pos)
+ {
+ swapNodes(switchNeighbor,pos,root);
+ percolateDownHeap(switchNeighbor,root);
+ }
+
+ return;
+}
+
+int
+GNUNET_DV_Heap_insert(struct GNUNET_dv_heap *root, struct GNUNET_dv_neighbor
*neighbor)
+{
+ struct GNUNET_dv_heap_node *new_pos;
+ int ret;
+ ret = GNUNET_YES;
+
+ if (root->max_size > root->size)
+ {
+ new_pos = getNextPos(root);
+ new_pos->neighbor = neighbor;
+ root->size++;
+ percolateHeap(new_pos,root);
+ }
+ else
+ {
+ ret = GNUNET_NO;
+ }
+
+ return ret;
+}
+
+struct GNUNET_dv_neighbor *
+GNUNET_DV_Heap_removeRoot(struct GNUNET_dv_heap *root)
+{
+ struct GNUNET_dv_neighbor *ret;
+ struct GNUNET_dv_heap_node *root_node;
+ struct GNUNET_dv_heap_node *last;
+
+ root_node = root->root;
+ ret = root_node->neighbor;
+ last = getPos(root,root->size);
+
+ if (last->parent->left_child == last)
+ last->parent->left_child = NULL;
+ else if (last->parent->right_child == last)
+ last->parent->right_child = NULL;
+
+ root_node->neighbor = last->neighbor;
+
+ if (root->traversal_pos == last)
+ {
+ root->traversal_pos = root->root;
+ }
+
+ GNUNET_free(last);
+ root->size--;
+ percolateDownHeap(root->root,root);
+ 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, unsigned int new_cost)
+{
+ int ret = GNUNET_YES;
+ neighbor->cost = new_cost;
+
+ ret = GNUNET_DV_Heap_updatedCost(root, neighbor);
+ return ret;
+}
+
+int
+GNUNET_DV_Heap_updatedCost(struct GNUNET_dv_heap *root, struct
GNUNET_dv_neighbor *neighbor)
+{
+ 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;
+
+ if ((root->type == GNUNET_DV_MAX_HEAP) && (neighbor->max_loc != NULL))
+ {
+ node = neighbor->max_loc;
+ }
+ else if ((root->type == GNUNET_DV_MIN_HEAP) && (neighbor->min_loc !=
NULL))
+ {
+ node = neighbor->min_loc;
+ }
+ else
+ return GNUNET_SYSERR;
+
+ parent = node->parent;
+
+ if ((root->type == GNUNET_DV_MAX_HEAP) && (parent != NULL) &&
(node->neighbor->cost > parent->neighbor->cost))
+ percolateHeap(neighbor->max_loc, root);
+ else if ((root->type == GNUNET_DV_MIN_HEAP) && (parent != NULL) &&
(node->neighbor->cost < parent->neighbor->cost))
+ percolateHeap(neighbor->min_loc,root);
+ else if (root->type == GNUNET_DV_MAX_HEAP)
+ percolateDownHeap(neighbor->max_loc, root);
+ else if (root->type == GNUNET_DV_MIN_HEAP)
+ percolateDownHeap(neighbor->min_loc, root);
+
+ return GNUNET_YES;
+}
+
+int
+GNUNET_DV_Heap_delete_matching_referrers(struct GNUNET_dv_heap *root, struct
GNUNET_dv_heap_node *node, GNUNET_PeerIdentity *toMatch)
+{
+ if (node->left_child != NULL)
+ {
+ 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, toMatch);
+ }
+ if ((node->neighbor != NULL) && (memcmp(node->neighbor, toMatch,
sizeof(struct GNUNET_PeerIdentity)) == 0))
+ {
+ GNUNET_DV_removeNode(root, node->neighbor);
+ }
+
+}
+
+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)
+{
+
+ if (node->left_child != NULL)
+ {
+ GNUNET_DV_Heap_Iterator(callee, root, node->left_child,
toMatch);
+ }
+
+ if (node->right_child != NULL)
+ {
+ GNUNET_DV_Heap_Iterator(callee, root,
node->right_child,toMatch);
+ }
+
+ if (node->neighbor != NULL)
+ {
+ callee(node->neighbor, root);
+ }
+}
+
+struct GNUNET_dv_neighbor *
+GNUNET_DV_Heap_Walk_getNext (struct GNUNET_dv_heap *root)
+{
+ unsigned int choice;
+ struct GNUNET_dv_neighbor *neighbor;
+
+ if ((root->traversal_pos == NULL) && (root->root != NULL))
+ {
+ root->traversal_pos = root->root;
+ }
+
+ if (root->traversal_pos == NULL)
+ return NULL;
+
+ neighbor = root->traversal_pos->neighbor;
+
+ 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;
+
+ return neighbor;
+
+}
+
+/* end of heap.h */
Added: GNUnet/src/applications/dv/module/heap.h
===================================================================
--- GNUnet/src/applications/dv/module/heap.h (rev 0)
+++ GNUnet/src/applications/dv/module/heap.h 2008-12-14 00:36:20 UTC (rev
8000)
@@ -0,0 +1,182 @@
+/*
+ This file is part of GNUnet.
+ (C) 2008 Christian Grothoff (and other contributing authors)
+
+ GNUnet is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published
+ by the Free Software Foundation; either version 2, or (at your
+ option) any later version.
+
+ GNUnet is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GNUnet; see the file COPYING. If not, write to the
+ Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @author Nathan Evans
+ * @file applications/dv/module/heap.h
+ * @brief Definitions of heap operations
+ */
+#include "gnunet_core.h"
+#include "dv.h"
+
+#ifndef HEAP_H_
+#define HEAP_H_
+
+/*
+ * Heap type, either max or min. Hopefully makes the
+ * implementation more useful.
+ */
+typedef enum
+{
+ GNUNET_DV_MAX_HEAP = 0,
+ GNUNET_DV_MIN_HEAP = 1,
+} GNUNET_DV_HeapType;
+
+/*
+ * Struct that is stored in hashmap, pointers to
+ * locations in min_heap and max_heap.
+ */
+struct GNUNET_dv_heap_info
+{
+ struct GNUNET_dv_heap_node *min_loc;
+
+ struct GNUNET_dv_heap_node *max_loc;
+
+};
+
+/*
+ * Heap base structure, contains current size,
+ * maximum allowed size, pointer to the root,
+ * and the heap type (max or min)
+ */
+struct GNUNET_dv_heap
+{
+ unsigned int size;
+
+ unsigned int max_size;
+
+ GNUNET_DV_HeapType type;
+
+ struct GNUNET_dv_heap_node *root;
+
+ struct GNUNET_dv_heap_node *traversal_pos;
+
+};
+
+/*
+ * Generic heap node structure, contains pointer to parent
+ * left child, right child, and actual neighbor.
+ */
+struct GNUNET_dv_heap_node
+{
+ struct GNUNET_dv_heap_node *parent;
+
+ struct GNUNET_dv_heap_node *left_child;
+
+ struct GNUNET_dv_heap_node *right_child;
+
+ struct GNUNET_dv_neighbor *neighbor;
+
+};
+
+/** FIXME:
+ * Smart heap iterator and iterate functions are literal
+ * prototypes, they are not yet implemented!!! Heap needs
+ * to be de-DV-ified. Just here to remind me (nate) that
+ * it still needs done!!!!!!!!!!!!!!
+ */
+
+/**
+ * Iterator for heap
+ *
+ * @param value - obj stored in heap
+ * @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);
+
+/**
+ * Iterate over all entries in the map.
+ *
+ * @param heap - the heap
+ * @param iterator - function to call on each entry
+ * @param cls - client argument (closure)
+ * @return - number of items handled
+ * GNUNET_SYSERR if there's a problem
+ */
+int GNUNET_DV_heap_iterate (const struct GNUNET_dv_heap *heap,
+ GNUNET_HeapIterator iterator,
+ void *cls);
+
+/**
+ * Simple stupid tree print. Prints in depth first order.
+ */
+void printTree(struct GNUNET_dv_heap_node *root);
+
+/**
+ * Inserts a new item into the heap, item is always neighbor now.
+ */
+int
+GNUNET_DV_Heap_insert(struct GNUNET_dv_heap *root, struct GNUNET_dv_neighbor
*neighbor);
+
+/**
+ * Removes root of the tree, is remove max if a max heap and remove min
+ * if a min heap, returns the data stored at the node.
+ */
+struct GNUNET_dv_neighbor *
+GNUNET_DV_Heap_removeRoot(struct GNUNET_dv_heap *root);
+
+/**
+ * Returns data stored at root of tree, doesn't affect anything
+ */
+struct GNUNET_dv_neighbor *
+GNUNET_DV_Heap_peekRoot(struct GNUNET_dv_heap *root);
+
+/**
+ * Removes any node from the tree based on the neighbor given, does
+ * not traverse the tree (backpointers) but may take more time due to
+ * percolation of nodes.
+ */
+struct GNUNET_dv_neighbor *
+GNUNET_DV_Heap_removeNode(struct GNUNET_dv_heap *root, struct
GNUNET_dv_neighbor *neighbor);
+
+/**
+ * Updates the cost of any node in the tree
+ */
+int
+GNUNET_DV_Heap_updateCost(struct GNUNET_dv_heap *root, struct
GNUNET_dv_neighbor *neighbor, unsigned int new_cost);
+
+/**
+ * Fixes the tree after a node's cost was externally modified
+ */
+int
+GNUNET_DV_Heap_updatedCost(struct GNUNET_dv_heap *root, struct
GNUNET_dv_neighbor *neighbor);
+
+/**
+ * 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, struct GNUNET_dv_heap_node *node,const
GNUNET_PeerIdentity *toMatch);
+
+
+/**
+ * Random walk of the tree, returns the data stored at the next random node
+ * in the walk. Calls callee with the data, or NULL if the tree is empty
+ * or some other problem crops up.
+ */
+struct GNUNET_dv_neighbor *
+GNUNET_DV_Heap_Walk_getNext (struct GNUNET_dv_heap *root);
+
+
+#endif /* HEAP_H_ */
+
+/* end of heap.h */
Added: GNUnet/src/applications/dv/module/heaptest.c
===================================================================
--- GNUnet/src/applications/dv/module/heaptest.c
(rev 0)
+++ GNUnet/src/applications/dv/module/heaptest.c 2008-12-14 00:36:20 UTC
(rev 8000)
@@ -0,0 +1,107 @@
+/*
+ This file is part of GNUnet.
+ (C) 2008 Christian Grothoff (and other contributing authors)
+
+ GNUnet is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published
+ by the Free Software Foundation; either version 2, or (at your
+ option) any later version.
+
+ GNUnet is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GNUnet; see the file COPYING. If not, write to the
+ Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @author Nathan Evans
+ * @file applications/dv/module/heaptest.c
+ * @brief Definitions of heap operations
+ */
+
+#include "heap.h"
+#include "dv.h"
+
+
+void iterator_callback(struct GNUNET_dv_neighbor *neighbor, struct
GNUNET_dv_heap *root)
+{
+ fprintf(stdout, "Node is:%d\n", neighbor->cost);
+}
+
+
+int main(int argc, char **argv)
+{
+ struct GNUNET_dv_heap *myHeap;
+ struct GNUNET_dv_neighbor *neighbor1;
+ struct GNUNET_dv_neighbor *neighbor2;
+ struct GNUNET_dv_neighbor *neighbor3;
+ struct GNUNET_dv_neighbor *neighbor4;
+ struct GNUNET_dv_neighbor *neighbor5;
+ struct GNUNET_dv_neighbor *neighbor6;
+
+ myHeap = malloc(sizeof(struct GNUNET_dv_heap));
+ myHeap->type = GNUNET_DV_MAX_HEAP;
+ myHeap->max_size = 10;
+ myHeap->size = 0;
+
+ neighbor1 = malloc(sizeof(struct GNUNET_dv_neighbor));
+ neighbor2 = malloc(sizeof(struct GNUNET_dv_neighbor));
+ neighbor3 = malloc(sizeof(struct GNUNET_dv_neighbor));
+ neighbor4 = malloc(sizeof(struct GNUNET_dv_neighbor));
+ neighbor5 = malloc(sizeof(struct GNUNET_dv_neighbor));
+ neighbor6 = malloc(sizeof(struct GNUNET_dv_neighbor));
+
+ neighbor1->cost = 60;
+ neighbor2->cost = 50;
+ neighbor3->cost = 70;
+ neighbor4->cost = 120;
+ neighbor5->cost = 100;
+ neighbor6->cost = 30;
+
+ fprintf(stdout,"Inserting\n");
+ GNUNET_DV_Heap_insert(myHeap,neighbor1);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Inserting\n");
+ GNUNET_DV_Heap_insert(myHeap,neighbor2);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Inserting\n");
+ GNUNET_DV_Heap_insert(myHeap,neighbor3);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Inserting\n");
+ GNUNET_DV_Heap_insert(myHeap,neighbor4);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Inserting\n");
+ GNUNET_DV_Heap_insert(myHeap,neighbor5);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Inserting\n");
+ GNUNET_DV_Heap_insert(myHeap,neighbor6);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Removing\n");
+ GNUNET_DV_Heap_removeNode(myHeap,neighbor5);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Removing\n");
+ GNUNET_DV_Heap_removeRoot(myHeap);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Updating\n");
+ GNUNET_DV_Heap_updateCost(myHeap, neighbor6, 200);
+ printTree(myHeap->root);
+
+ fprintf(stdout,"Iterating\n");
+ GNUNET_DV_Heap_Iterator (iterator_callback, myHeap, myHeap->root);
+ return 0;
+}
+
+/* end of heaptest.c */
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r8000 - GNUnet/src/applications/dv/module,
gnunet <=