[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r8364 - GNUnet/src/applications/dv/module
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r8364 - GNUnet/src/applications/dv/module |
|
Date: |
Tue, 31 Mar 2009 19:04:38 -0600 |
Author: nevans
Date: 2009-03-31 19:04:38 -0600 (Tue, 31 Mar 2009)
New Revision: 8364
Removed:
GNUnet/src/applications/dv/module/heap.c
GNUnet/src/applications/dv/module/heaptest.c
Modified:
GNUnet/src/applications/dv/module/Makefile.am
GNUnet/src/applications/dv/module/dv.c
GNUnet/src/applications/dv/module/dv_heaptest.c
GNUnet/src/applications/dv/module/heap.h
Log:
move heap to containers
Modified: GNUnet/src/applications/dv/module/Makefile.am
===================================================================
--- GNUnet/src/applications/dv/module/Makefile.am 2009-03-31 22:39:56 UTC
(rev 8363)
+++ GNUnet/src/applications/dv/module/Makefile.am 2009-04-01 01:04:38 UTC
(rev 8364)
@@ -9,17 +9,12 @@
plugindir = $(libdir)/GNUnet
-noinst_LTLIBRARIES = libheap.la
-
-libheap_la_SOURCES = \
- dv.c heap.c
-
plugin_LTLIBRARIES = \
libgnunetmodule_dv.la \
libgnunetmodule_dv_tbench.la
libgnunetmodule_dv_la_SOURCES = \
- dv.c heap.c
+ dv.c
libgnunetmodule_dv_la_LDFLAGS = \
$(GN_PLUGIN_LDFLAGS)
libgnunetmodule_dv_la_LIBADD = \
@@ -37,7 +32,6 @@
check_PROGRAMS = \
- heaptest \
dv_heaptest \
dvtest
@@ -47,22 +41,14 @@
dvtest.c
dvtest_LDADD = \
$(top_builddir)/src/util/libgnunetutil.la \
- $(top_builddir)/src/applications/dv/module/libheap.la \
$(top_builddir)/src/applications/stats/libgnunetstatsapi.la \
$(top_builddir)/src/applications/testing/libgnunetremoteapi.la \
$(top_builddir)/src/applications/testing/libgnunettestingapi.la
-heaptest_SOURCES = \
- heaptest.c
-heaptest_LDADD = \
- $(top_builddir)/src/util/libgnunetutil.la \
- $(top_builddir)/src/applications/dv/module/libheap.la
-
dv_heaptest_SOURCES = \
dv_heaptest.c
dv_heaptest_LDADD = \
- $(top_builddir)/src/util/libgnunetutil.la \
- $(top_builddir)/src/applications/dv/module/libheap.la
+ $(top_builddir)/src/util/libgnunetutil.la
EXTRA_DIST = \
check.conf \
Modified: GNUnet/src/applications/dv/module/dv.c
===================================================================
--- GNUnet/src/applications/dv/module/dv.c 2009-03-31 22:39:56 UTC (rev
8363)
+++ GNUnet/src/applications/dv/module/dv.c 2009-04-01 01:04:38 UTC (rev
8364)
@@ -31,7 +31,6 @@
#include "gnunet_core.h"
#include "gnunet_dv_service.h"
#include "dv.h"
-#include "heap.h"
#define DEBUG_DV_MAINTAIN GNUNET_YES
#define DEBUG_DV GNUNET_NO
@@ -54,8 +53,8 @@
struct GNUNET_MultiHashMap *direct_neighbors;
struct GNUNET_MultiHashMap *extended_neighbors;
- struct GNUNET_dv_heap neighbor_min_heap;
- struct GNUNET_dv_heap neighbor_max_heap;
+ struct GNUNET_CONTAINER_Heap *neighbor_min_heap;
+ struct GNUNET_CONTAINER_Heap *neighbor_max_heap;
};
@@ -111,8 +110,8 @@
static int
delete_neighbor(struct GNUNET_dv_neighbor *neighbor)
{
- GNUNET_DV_Heap_removeNode (&ctx->neighbor_max_heap, neighbor);
- GNUNET_DV_Heap_removeNode (&ctx->neighbor_min_heap, neighbor);
+ GNUNET_CONTAINER_heap_remove_node (ctx->neighbor_max_heap, neighbor);
+ GNUNET_CONTAINER_heap_remove_node (ctx->neighbor_min_heap, neighbor);
GNUNET_multi_hash_map_remove_all (ctx->extended_neighbors,
&neighbor->neighbor->hashPubKey);
@@ -168,12 +167,13 @@
* cls - unused
*/
static int
-delete_expired_callback (struct GNUNET_dv_neighbor *neighbor,
- struct GNUNET_dv_heap *root, void *cls)
+delete_expired_callback (void * element, GNUNET_CostType cost,
+ struct GNUNET_CONTAINER_Heap *root, void *cls)
{
GNUNET_CronTime now;
now = GNUNET_get_time();
-
+ struct GNUNET_dv_neighbor *neighbor;
+ neighbor = (struct GNUNET_dv_neighbor *)element;
if ((GNUNET_NO == GNUNET_multi_hash_map_contains(ctx->direct_neighbors,
&neighbor->neighbor->hashPubKey)) && (now - neighbor->last_activity >
GNUNET_DV_PEER_EXPIRATION_TIME))
{
#if DEBUG_DV_MAINTAIN
@@ -198,8 +198,7 @@
maintain_dv_job (void *unused)
{
GNUNET_mutex_lock (ctx->dvMutex);
- GNUNET_DV_Heap_Iterator (&ctx->neighbor_max_heap,
- ctx->neighbor_max_heap.root,
+ GNUNET_CONTAINER_heap_iterate (ctx->neighbor_max_heap,
&delete_expired_callback, NULL);
GNUNET_mutex_unlock (ctx->dvMutex);
@@ -575,8 +574,8 @@
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);
+ GNUNET_CONTAINER_heap_insert (ctx->neighbor_max_heap, neighbor, cost);
+ GNUNET_CONTAINER_heap_insert (ctx->neighbor_min_heap, neighbor, cost);
}
else
@@ -595,8 +594,8 @@
{
neighbor->cost = cost;
neighbor->last_activity = now;
- GNUNET_DV_Heap_updatedCost (&ctx->neighbor_max_heap, neighbor);
- GNUNET_DV_Heap_updatedCost (&ctx->neighbor_min_heap, neighbor);
+ GNUNET_CONTAINER_heap_update_cost (ctx->neighbor_max_heap, neighbor,
cost);
+ GNUNET_CONTAINER_heap_update_cost (ctx->neighbor_min_heap, neighbor,
cost);
}
else if (neighbor->cost > cost)
{
@@ -621,8 +620,8 @@
&peer->hashPubKey, neighbor,
GNUNET_MultiHashMapOption_REPLACE);
- GNUNET_DV_Heap_insert (&ctx->neighbor_max_heap, neighbor);
- GNUNET_DV_Heap_insert (&ctx->neighbor_min_heap, neighbor);
+ GNUNET_CONTAINER_heap_insert (ctx->neighbor_max_heap, neighbor,
cost);
+ GNUNET_CONTAINER_heap_insert (ctx->neighbor_min_heap, neighbor,
cost);
}
else if(neighbor->cost == cost)
{
@@ -754,9 +753,11 @@
* cls - the peer identity to compare neighbor's identity to
*/
static int
-delete_callback (struct GNUNET_dv_neighbor *neighbor,
- struct GNUNET_dv_heap *root, void *cls)
+delete_callback (void *element, GNUNET_CostType cost,
+ struct GNUNET_CONTAINER_Heap *root, void *cls)
{
+ struct GNUNET_dv_neighbor *neighbor;
+ neighbor = (struct GNUNET_dv_neighbor *)element;
GNUNET_PeerIdentity *toMatch = cls;
#if DEBUG_DV
GNUNET_EncName encNeighbor;
@@ -831,8 +832,7 @@
&peer->hashPubKey);
if (neighbor != NULL)
{
- GNUNET_DV_Heap_Iterator (&ctx->neighbor_max_heap,
- ctx->neighbor_max_heap.root,
+ GNUNET_CONTAINER_heap_iterate (ctx->neighbor_max_heap,
&delete_callback, (void *) peer);
/* Note that we do not use delete_neighbor here because
* we are deleting from the direct neighbor list! */
@@ -879,7 +879,7 @@
static struct GNUNET_dv_neighbor *
chooseAboutNeighbor ()
{
- if (ctx->neighbor_min_heap.size == 0)
+ if (GNUNET_CONTAINER_heap_get_size(ctx->neighbor_min_heap) == 0)
return NULL;
#if DEBUG_DV
@@ -890,7 +890,7 @@
ctx->neighbor_max_heap.size);
#endif
- return GNUNET_DV_Heap_Walk_getNext (&ctx->neighbor_min_heap);
+ return GNUNET_CONTAINER_heap_walk_get_next (ctx->neighbor_min_heap);
}
@@ -975,12 +975,8 @@
api.dv_connections_iterate = &GNUNET_DV_connection_iterate_peers;
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->neighbor_max_heap.traversal_pos = NULL;
- ctx->neighbor_min_heap.traversal_pos = NULL;
+ ctx->neighbor_min_heap = GNUNET_CONTAINER_heap_create(GNUNET_MIN_HEAP);
+ ctx->neighbor_max_heap = GNUNET_CONTAINER_heap_create(GNUNET_MAX_HEAP);
ctx->send_interval = GNUNET_DV_DEFAULT_SEND_INTERVAL;
ctx->dvMutex = GNUNET_mutex_create (GNUNET_NO);
coreAPI = capi;
Modified: GNUnet/src/applications/dv/module/dv_heaptest.c
===================================================================
--- GNUnet/src/applications/dv/module/dv_heaptest.c 2009-03-31 22:39:56 UTC
(rev 8363)
+++ GNUnet/src/applications/dv/module/dv_heaptest.c 2009-04-01 01:04:38 UTC
(rev 8364)
@@ -59,7 +59,7 @@
{
int ret;
ret = heapverify;
- if (root->type == GNUNET_DV_MAX_HEAP)
+ if (root->type == GNUNET_CONTAINER_MAX_HEAP)
{
if ((neighbor->max_loc->left_child != NULL)
&& (neighbor->cost < neighbor->max_loc->left_child->neighbor->cost))
@@ -74,7 +74,7 @@
ret = GNUNET_SYSERR;
}
}
- else if (root->type == GNUNET_DV_MIN_HEAP)
+ else if (root->type == GNUNET_CONTAINER_MIN_HEAP)
{
if ((neighbor->min_loc->left_child != NULL)
&& (neighbor->cost > neighbor->min_loc->left_child->neighbor->cost))
@@ -133,18 +133,9 @@
//int vals[6] = {70, 26, 53, 100, 35, 95};
struct GNUNET_dv_neighbor *neighbors[TESTS];
ret = GNUNET_OK;
- maxHeap = malloc (sizeof (struct GNUNET_dv_heap));
- maxHeap->type = GNUNET_DV_MAX_HEAP;
- maxHeap->max_size = MAX_SIZE;
- maxHeap->size = 0;
- maxHeap->traversal_pos = NULL;
+ maxHeap = GNUNET_CONTAINER_heap_create(GNUNET_MAX_HEAP);
+ minHeap = GNUNET_CONTAINER_heap_create(GNUNET_MIN_HEAP);
- minHeap = malloc (sizeof (struct GNUNET_dv_heap));
- minHeap->type = GNUNET_DV_MIN_HEAP;
- minHeap->max_size = MAX_SIZE;
- minHeap->size = 0;
- minHeap->traversal_pos = NULL;
-
for (i = 0; i < TESTS; i++)
{
neighbors[i] = NULL;
@@ -172,8 +163,8 @@
&neighbors[cur_pos]->neighbor->hashPubKey);
//neighbors[cur_pos]->cost = temp_rand;
neighbors[cur_pos]->cost = temp_rand;
- GNUNET_DV_Heap_insert (maxHeap, neighbors[cur_pos]);
- GNUNET_DV_Heap_insert (minHeap, neighbors[cur_pos]);
+ GNUNET_CONTAINER_heap_insert (maxHeap, neighbors[cur_pos]);
+ GNUNET_CONTAINER_heap_insert (minHeap, neighbors[cur_pos]);
cur_pos++;
break;
@@ -182,15 +173,16 @@
temp_rand = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 100) + 1;
fprintf (stderr, "Updating node %d (cost %d) with new cost %d\n",
temp_node + 1, neighbors[temp_node]->cost, temp_rand);
- GNUNET_DV_Heap_updateCost (maxHeap, neighbors[temp_node],
+ GNUNET_CONTAINER_heap_update_cost (maxHeap, neighbors[temp_node],
temp_rand);
- GNUNET_DV_Heap_updatedCost (minHeap, neighbors[temp_node]);
+ GNUNET_CONTAINER_heap_update_Cost (minHeap, neighbors[temp_node],
+ temp_rand);
break;
case 3:
fprintf (stderr, "Removing node %d with cost %d\n", cur_pos,
neighbors[cur_pos - 1]->cost);
- GNUNET_DV_Heap_removeNode (maxHeap, neighbors[cur_pos - 1]);
- GNUNET_DV_Heap_removeNode (minHeap, neighbors[cur_pos - 1]);
+ GNUNET_CONTAINER_heap_remove_node (maxHeap, neighbors[cur_pos - 1]);
+ GNUNET_CONTAINER_heap_remove_node (minHeap, neighbors[cur_pos - 1]);
GNUNET_free (neighbors[cur_pos - 1]->neighbor);
GNUNET_free (neighbors[cur_pos - 1]);
neighbors[cur_pos - 1] = NULL;
@@ -201,57 +193,9 @@
break;
}
- for (j = 0; j < cur_pos; j++)
- {
- if (check_node (neighbors[j]) != GNUNET_OK)
- {
- fprintf (stderr, "\n\n\tEPIC FAIL\n\n");
- if ((neighbors[j]->max_loc->neighbor != neighbors[j]))
- {
- fprintf (stderr, "node at position %d has bad max_loc\n",
- j);
- }
- if (neighbors[j]->min_loc->neighbor != neighbors[j])
- {
- fprintf (stderr, "node at position %d has bad min_loc\n",
- j);
- }
- ret = GNUNET_SYSERR;
- }
- }
- heapverify = GNUNET_OK;
- GNUNET_DV_Heap_Iterator (minHeap, minHeap->root, &heap_verify_callback,
- NULL);
- if (heapverify != GNUNET_OK)
- {
- fprintf (stderr, "Min heap property broken!\n");
- return GNUNET_SYSERR;
- }
-
- GNUNET_DV_Heap_Iterator (maxHeap, maxHeap->root, &heap_verify_callback,
- NULL);
- if (heapverify != GNUNET_OK)
- {
- fprintf (stderr, "Max heap property broken!\n");
- return GNUNET_SYSERR;
- }
-
if (ret != GNUNET_OK)
return GNUNET_SYSERR;
- tempmaxsize = 0;
- tempminsize = 0;
- GNUNET_DV_Heap_Iterator (maxHeap, maxHeap->root, &count_max_callback,
- NULL);
- GNUNET_DV_Heap_Iterator (minHeap, minHeap->root, &count_min_callback,
- NULL);
-
- if ((tempmaxsize != cur_pos) || (tempminsize != cur_pos)
- || (maxHeap->size != cur_pos) || (minHeap->size != cur_pos))
- {
- fprintf (stderr, "Incorrect heap sizes!\n");
- return GNUNET_SYSERR;
- }
}
return 0;
Deleted: GNUnet/src/applications/dv/module/heap.c
===================================================================
--- GNUnet/src/applications/dv/module/heap.c 2009-03-31 22:39:56 UTC (rev
8363)
+++ GNUnet/src/applications/dv/module/heap.c 2009-04-01 01:04:38 UTC (rev
8364)
@@ -1,463 +0,0 @@
-/*
- 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 "platform.h"
-#include "gnunet_protocols.h"
-#include "gnunet_util.h"
-#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)
- {
- fprintf (stdout, "LEFT of %d\n", root->neighbor->cost);
- printTree (root->left_child);
- }
- if (root->right_child != NULL)
- {
- fprintf (stdout, "RIGHT of %d\n", root->neighbor->cost);
- 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 = GNUNET_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_MIN_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;
-}
-
-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);
- if (root->type == GNUNET_DV_MAX_HEAP)
- last->neighbor->max_loc = del_node->neighbor->max_loc;
- else if (root->type == GNUNET_DV_MIN_HEAP)
- last->neighbor->min_loc = del_node->neighbor->min_loc;
-
- 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)
-{
- 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++;
- 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
- {
- 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;
-}
-
-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;
-
- 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)
-{
- int count = 0;
- if (node->left_child != NULL)
- {
- count +=
- GNUNET_DV_Heap_delete_matching_referrers (root, node->left_child,
- toMatch);
- }
- if (node->right_child != NULL)
- {
- count +=
- GNUNET_DV_Heap_delete_matching_referrers (root, node->right_child,
- toMatch);
- }
- if ((node->neighbor != NULL)
- &&
- (memcmp (node->neighbor, toMatch, sizeof (GNUNET_PeerIdentity)) == 0))
- {
- GNUNET_DV_Heap_removeNode (root, node->neighbor);
- count++;
- }
-
- return count;
-
-}
-
-void
-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 (root, node->left_child, iterator, cls);
- }
-
- if (node->right_child != NULL)
- {
- GNUNET_DV_Heap_Iterator (root, node->right_child, iterator, cls);
- }
-
- if (node->neighbor != NULL)
- {
- iterator (node->neighbor, root, cls);
- }
-}
-
-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, 2);
-
- switch (choice)
- {
- case 1:
- root->traversal_pos = root->traversal_pos->right_child;
- break;
- case 0:
- root->traversal_pos = root->traversal_pos->left_child;
- break;
- }
-
- return neighbor;
-
-}
-
-/* end of heap.h */
Modified: GNUnet/src/applications/dv/module/heap.h
===================================================================
--- GNUnet/src/applications/dv/module/heap.h 2009-03-31 22:39:56 UTC (rev
8363)
+++ GNUnet/src/applications/dv/module/heap.h 2009-04-01 01:04:38 UTC (rev
8364)
@@ -24,68 +24,40 @@
* @brief Definitions of heap operations
*/
#include "gnunet_core.h"
-#include "dv.h"
#ifndef HEAP_H_
#define HEAP_H_
+typedef unsigned int GNUNET_CostType;
+
/*
* 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;
+ GNUNET_MAX_HEAP = 0,
+ GNUNET_MIN_HEAP = 1,
+} GNUNET_CONTAINER_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_CONTAINER_Heap;
- 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)
+/** FIXME:
+ * Heap needs to be de-DV-ified. Just here to remind me
+ * (nate) that it still needs done!!!!!!!!!!!!!!
*/
-struct GNUNET_dv_heap
-{
- unsigned int size;
- unsigned int max_size;
+struct GNUNET_CONTAINER_Heap *
+GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HeapType type);
- GNUNET_DV_HeapType type;
+void
+GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap * h);
- 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:
* Heap needs to be de-DV-ified. Just here to remind me
* (nate) that it still needs done!!!!!!!!!!!!!!
@@ -101,8 +73,10 @@
* iterate,
* GNUNET_NO if not.
*/
-typedef int (*GNUNET_HeapIterator) (struct GNUNET_dv_neighbor * neighbor,
- struct GNUNET_dv_heap * root, void *cls);
+typedef int (*GNUNET_CONTAINER_HeapIterator) (void * element,
+ GNUNET_CostType cost,
+ struct GNUNET_CONTAINER_Heap * root,
+ void *cls);
/**
* Iterate over all entries in the map.
@@ -113,79 +87,62 @@
* @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);
+int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
+ GNUNET_CONTAINER_HeapIterator iterator, void *cls);
-/**
- * Simple stupid tree print. Prints in depth first order.
- * To stdout.
- */
-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);
+GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
+ void * element, GNUNET_CostType cost);
/**
* 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);
+void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root);
/**
* Returns data stored at root of tree, doesn't effect anything
*/
-struct GNUNET_dv_neighbor *GNUNET_DV_Heap_peekRoot (struct GNUNET_dv_heap
- *root);
+void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_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);
+void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
+ void *element);
/**
* 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);
+GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
+ void * element,
+ GNUNET_CostType 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 (struct GNUNET_dv_heap *root,
- struct GNUNET_dv_heap_node *node,
- GNUNET_HeapIterator iterator, void *cls);
-
-
-/**
* 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
+void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap
*root);
+void
+printTree (struct GNUNET_CONTAINER_Heap *root);
+/*
+ * Returns the current size of the heap
+ *
+ * @param heap the heap to get the size of
+ */
+unsigned int
+GNUNET_CONTAINER_heap_get_size(struct GNUNET_CONTAINER_Heap *heap);
#endif /* HEAP_H_ */
/* end of heap.h */
Deleted: GNUnet/src/applications/dv/module/heaptest.c
===================================================================
--- GNUnet/src/applications/dv/module/heaptest.c 2009-03-31 22:39:56 UTC
(rev 8363)
+++ GNUnet/src/applications/dv/module/heaptest.c 2009-04-01 01:04:38 UTC
(rev 8364)
@@ -1,111 +0,0 @@
-/*
- 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 Test of heap operations
- */
-
-#include "heap.h"
-#include "dv.h"
-
-
-static int
-iterator_callback (struct GNUNET_dv_neighbor *neighbor,
- struct GNUNET_dv_heap *root, void *cls)
-{
- fprintf (stdout, "%d\n", neighbor->cost);
-
- return GNUNET_OK;
-}
-
-
-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;
-
- GNUNET_DV_Heap_insert (myHeap, neighbor1);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_insert (myHeap, neighbor2);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_insert (myHeap, neighbor3);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_insert (myHeap, neighbor4);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_insert (myHeap, neighbor5);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_insert (myHeap, neighbor6);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_removeNode (myHeap, neighbor5);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_removeRoot (myHeap);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_updateCost (myHeap, neighbor6, 200);
- fprintf (stdout, "\n");
- printTree (myHeap->root);
-
- GNUNET_DV_Heap_Iterator (myHeap, myHeap->root, iterator_callback, NULL);
- return 0;
-}
-
-/* end of heaptest.c */
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r8364 - GNUnet/src/applications/dv/module,
gnunet <=