[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r9870 - in GNUnet/src: applications/dv/module applications/
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r9870 - in GNUnet/src: applications/dv/module applications/dv_dht/module include util/containers |
|
Date: |
Wed, 23 Dec 2009 15:58:45 +0100 |
Author: grothoff
Date: 2009-12-23 15:58:45 +0100 (Wed, 23 Dec 2009)
New Revision: 9870
Modified:
GNUnet/src/applications/dv/module/dv.c
GNUnet/src/applications/dv_dht/module/routing.c
GNUnet/src/include/dv.h
GNUnet/src/include/gnunet_util_containers.h
GNUnet/src/util/containers/heap.c
GNUnet/src/util/containers/heaptest.c
Log:
cleaning up heap API and fixing implementation
Modified: GNUnet/src/applications/dv/module/dv.c
===================================================================
--- GNUnet/src/applications/dv/module/dv.c 2009-12-23 12:04:09 UTC (rev
9869)
+++ GNUnet/src/applications/dv/module/dv.c 2009-12-23 14:58:45 UTC (rev
9870)
@@ -65,7 +65,54 @@
GNUNET_PeerIdentity identity;
};
+
/*
+ * Struct where actual neighbor information is stored,
+ * referenced by min_heap and max_heap. Freeing dealt
+ * with when items removed from hashmap.
+ */
+struct GNUNET_dv_neighbor
+{
+ /*
+ * Back-pointer location in min heap
+ */
+ struct GNUNET_CONTAINER_HeapNode *min_loc;
+
+ /*
+ * Back-pointer location in max heap
+ */
+ struct GNUNET_CONTAINER_HeapNode *max_loc;
+
+ /**
+ * Identity of neighbor.
+ */
+ GNUNET_PeerIdentity neighbor;
+
+ /**
+ * Identity of referrer (where we got the information)
+ */
+ GNUNET_PeerIdentity *referrer;
+
+ /**
+ * Cost to neighbor, used for actual distance vector computations
+ */
+ unsigned int cost;
+
+ /**
+ * Last time we received routing information from this peer
+ */
+ GNUNET_CronTime last_activity;
+
+ /*
+ * Random identifier we use for this peer, to be used as shortcut
+ * instead of sending full peer id for each message
+ */
+ unsigned int neighbor_id;
+};
+
+
+
+/*
* Global construct
*/
struct GNUNET_DV_Context
@@ -98,6 +145,7 @@
{
GNUNET_NodeIteratorCallback method;
void *arg;
+ int cnt;
};
static char shortID[5];
@@ -156,8 +204,10 @@
static int
delete_neighbor (struct GNUNET_dv_neighbor *neighbor)
{
- GNUNET_CONTAINER_heap_remove_node (ctx->neighbor_max_heap, neighbor);
- GNUNET_CONTAINER_heap_remove_node (ctx->neighbor_min_heap, neighbor);
+ GNUNET_CONTAINER_heap_remove_node (ctx->neighbor_max_heap,
+ neighbor->max_loc);
+ GNUNET_CONTAINER_heap_remove_node (ctx->neighbor_min_heap,
+ neighbor->min_loc);
GNUNET_multi_hash_map_remove_all (ctx->extended_neighbors,
&neighbor->neighbor.hashPubKey);
GNUNET_free_non_null (neighbor->referrer);
@@ -170,12 +220,15 @@
* A callback for iterating over all known nodes.
*/
static int
-connection_iterate_callback (void *element, GNUNET_CostType cost,
- struct GNUNET_CONTAINER_Heap *root, void *cls)
+connection_iterate_callback (void *cls,
+ struct GNUNET_CONTAINER_HeapNode *node,
+ void *element,
+ GNUNET_CONTAINER_HeapCostType cost)
{
struct GNUNET_dv_neighbor *neighbor = element;
struct callbackWrapper *wrap = cls;
wrap->method (&neighbor->neighbor, wrap->arg);
+ wrap->cnt++;
return GNUNET_OK;
}
@@ -188,8 +241,10 @@
* cls - unused
*/
static int
-delete_expired_callback (void *element, GNUNET_CostType cost,
- struct GNUNET_CONTAINER_Heap *root, void *cls)
+delete_expired_callback (void *cls,
+ struct GNUNET_CONTAINER_HeapNode *node,
+ void *element,
+ GNUNET_CONTAINER_HeapCostType cost)
{
struct GNUNET_dv_neighbor *neighbor = element;
GNUNET_CronTime now;
@@ -261,16 +316,15 @@
void *arg)
{
struct callbackWrapper wrap;
- int ret;
wrap.method = method;
wrap.arg = arg;
+ wrap.cnt = 0;
GNUNET_mutex_lock (ctx->dvMutex);
- ret =
- GNUNET_CONTAINER_heap_iterate (ctx->neighbor_max_heap,
- &connection_iterate_callback, &wrap);
+ GNUNET_CONTAINER_heap_iterate (ctx->neighbor_max_heap,
+ &connection_iterate_callback, &wrap);
GNUNET_mutex_unlock (ctx->dvMutex);
- return ret;
+ return wrap.cnt;
}
@@ -844,8 +898,8 @@
&peer->hashPubKey, neighbor,
GNUNET_MultiHashMapOption_REPLACE);
- GNUNET_CONTAINER_heap_insert (ctx->neighbor_max_heap, neighbor, cost);
- GNUNET_CONTAINER_heap_insert (ctx->neighbor_min_heap, neighbor, cost);
+ neighbor->max_loc = GNUNET_CONTAINER_heap_insert
(ctx->neighbor_max_heap, neighbor, cost);
+ neighbor->min_loc = GNUNET_CONTAINER_heap_insert
(ctx->neighbor_min_heap, neighbor, cost);
if (stats != NULL)
stats->change (stat_dv_total_peers, 1);
GNUNET_mutex_unlock (ctx->dvMutex);
@@ -866,9 +920,11 @@
{
/* update cost */
neighbor->cost = cost;
- GNUNET_CONTAINER_heap_update_cost (ctx->neighbor_max_heap, neighbor,
+ GNUNET_CONTAINER_heap_update_cost (ctx->neighbor_max_heap,
+ neighbor->max_loc,
cost);
- GNUNET_CONTAINER_heap_update_cost (ctx->neighbor_min_heap, neighbor,
+ GNUNET_CONTAINER_heap_update_cost (ctx->neighbor_min_heap,
+ neighbor->min_loc,
cost);
}
GNUNET_mutex_unlock (ctx->dvMutex);
@@ -901,8 +957,8 @@
&peer->hashPubKey, neighbor,
GNUNET_MultiHashMapOption_REPLACE);
- GNUNET_CONTAINER_heap_insert (ctx->neighbor_max_heap, neighbor, cost);
- GNUNET_CONTAINER_heap_insert (ctx->neighbor_min_heap, neighbor, cost);
+ neighbor->max_loc = GNUNET_CONTAINER_heap_insert (ctx->neighbor_max_heap,
neighbor, cost);
+ neighbor->min_loc = GNUNET_CONTAINER_heap_insert (ctx->neighbor_min_heap,
neighbor, cost);
#if DEBUG_DV
GNUNET_GE_LOG (coreAPI->ectx,
GNUNET_GE_WARNING | GNUNET_GE_ADMIN | GNUNET_GE_USER |
@@ -1022,8 +1078,10 @@
* @param cls the peer identity to compare neighbor's identity to
*/
static int
-delete_callback (void *element, GNUNET_CostType cost,
- struct GNUNET_CONTAINER_Heap *root, void *cls)
+delete_callback (void *cls,
+ struct GNUNET_CONTAINER_HeapNode *node,
+ void *element,
+ GNUNET_CONTAINER_HeapCostType cost)
{
struct GNUNET_dv_neighbor *neighbor = element;
GNUNET_PeerIdentity *toMatch = cls;
@@ -1327,8 +1385,8 @@
}
ctx = GNUNET_malloc (sizeof (struct GNUNET_DV_Context));
- ctx->neighbor_min_heap = GNUNET_CONTAINER_heap_create (GNUNET_MIN_HEAP);
- ctx->neighbor_max_heap = GNUNET_CONTAINER_heap_create (GNUNET_MAX_HEAP);
+ ctx->neighbor_min_heap = GNUNET_CONTAINER_heap_create
(GNUNET_CONTAINER_HEAP_ORDER_MIN);
+ ctx->neighbor_max_heap = GNUNET_CONTAINER_heap_create
(GNUNET_CONTAINER_HEAP_ORDER_MAX);
ctx->send_interval = GNUNET_DV_DEFAULT_SEND_INTERVAL;
ctx->dvMutex = capi->global_lock_get ();
Modified: GNUnet/src/applications/dv_dht/module/routing.c
===================================================================
--- GNUnet/src/applications/dv_dht/module/routing.c 2009-12-23 12:04:09 UTC
(rev 9869)
+++ GNUnet/src/applications/dv_dht/module/routing.c 2009-12-23 14:58:45 UTC
(rev 9870)
@@ -234,6 +234,8 @@
*/
struct GNUNET_BloomFilter *bloom_results;
+ struct GNUNET_CONTAINER_HeapNode *hnode;
+
} DV_DHTQueryRecord;
/*
@@ -721,7 +723,7 @@
if (GNUNET_multi_hash_map_contains (new_records.hashmap, &get->key))
{
q = GNUNET_multi_hash_map_get (new_records.hashmap, &get->key);
- GNUNET_CONTAINER_heap_remove_node (new_records.minHeap, q);
+ GNUNET_CONTAINER_heap_remove_node (new_records.minHeap, q->hnode);
}
else
{
@@ -778,7 +780,7 @@
#endif
}
- GNUNET_CONTAINER_heap_insert (new_records.minHeap, q, now);
+ q->hnode = GNUNET_CONTAINER_heap_insert (new_records.minHeap, q, now);
GNUNET_multi_hash_map_put (new_records.hashmap, &get->key, q,
GNUNET_MultiHashMapOption_REPLACE);
@@ -1355,7 +1357,7 @@
}
}
GNUNET_multi_hash_map_remove (new_records.hashmap, key, q);
- GNUNET_CONTAINER_heap_remove_node (new_records.minHeap, q);
+ GNUNET_CONTAINER_heap_remove_node (new_records.minHeap, q->hnode);
records_removed++;
}
@@ -1554,7 +1556,7 @@
rt_size = (unsigned int) rts;
new_records.hashmap = GNUNET_multi_hash_map_create ((unsigned int) rts);
- new_records.minHeap = GNUNET_CONTAINER_heap_create (GNUNET_MIN_HEAP);
+ new_records.minHeap = GNUNET_CONTAINER_heap_create
(GNUNET_CONTAINER_HEAP_ORDER_MIN);
memset (&nulldata, 0, sizeof (nulldata));
lock = GNUNET_mutex_create (GNUNET_NO);
Modified: GNUnet/src/include/dv.h
===================================================================
--- GNUnet/src/include/dv.h 2009-12-23 12:04:09 UTC (rev 9869)
+++ GNUnet/src/include/dv.h 2009-12-23 14:58:45 UTC (rev 9870)
@@ -107,50 +107,7 @@
} p2p_dv_MESSAGE_Data;
-/*
- * Struct where actual neighbor information is stored,
- * referenced by min_heap and max_heap. Freeing dealt
- * with when items removed from hashmap.
- */
-struct GNUNET_dv_neighbor
-{
- /*
- * Back-pointer location in min heap
- */
- struct GNUNET_dv_heap_node *min_loc;
- /*
- * Back-pointer location in max heap
- */
- struct GNUNET_dv_heap_node *max_loc;
-
- /**
- * Identity of neighbor.
- */
- GNUNET_PeerIdentity neighbor;
-
- /**
- * Identity of referrer (where we got the information)
- */
- GNUNET_PeerIdentity *referrer;
-
- /**
- * Cost to neighbor, used for actual distance vector computations
- */
- unsigned int cost;
-
- /**
- * Last time we received routing information from this peer
- */
- GNUNET_CronTime last_activity;
-
- /*
- * Random identifier we use for this peer, to be used as shortcut
- * instead of sending full peer id for each message
- */
- unsigned int neighbor_id;
-};
-
#endif
/* end of dv.h */
Modified: GNUnet/src/include/gnunet_util_containers.h
===================================================================
--- GNUnet/src/include/gnunet_util_containers.h 2009-12-23 12:04:09 UTC (rev
9869)
+++ GNUnet/src/include/gnunet_util_containers.h 2009-12-23 14:58:45 UTC (rev
9870)
@@ -578,107 +578,171 @@
(element)->next->prev = (element)->prev;
-typedef unsigned long long GNUNET_CostType;
+/**
+ * Type for costs in a heap.
+ */
+typedef unsigned long long GNUNET_CONTAINER_HeapCostType;
-/*
- * Heap type, either max or min. Hopefully makes the
- * implementation more useful.
+/**
+ * Heap sort order.
*/
-typedef enum
+enum GNUNET_CONTAINER_HeapOrder
{
- GNUNET_MAX_HEAP = 0,
- GNUNET_MIN_HEAP = 1,
-} GNUNET_CONTAINER_HeapType;
+ /**
+ * Element with largest cost is on top.
+ */
+ GNUNET_CONTAINER_HEAP_ORDER_MAX,
-/*
- * Struct that is stored in hashmap, pointers to
- * locations in min_heap and max_heap.
+ /**
+ * Element with minimal cost is on top.
+ */
+ GNUNET_CONTAINER_HEAP_ORDER_MIN
+};
+
+
+/**
+ * Handle to a heap.
*/
struct GNUNET_CONTAINER_Heap;
-struct GNUNET_CONTAINER_Heap
- *GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HeapType type);
-void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *h);
+/**
+ * Handle to a node in a heap.
+ */
+struct GNUNET_CONTAINER_HeapNode;
+
/**
- * Iterator for heap
+ * Create a new 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.
+ * @param order how should the heap be sorted?
+ * @return handle to the heap
*/
-typedef int (*GNUNET_CONTAINER_HeapIterator) (void *element,
- GNUNET_CostType cost,
- struct GNUNET_CONTAINER_Heap *
- root, void *cls);
+struct GNUNET_CONTAINER_Heap *
+GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
+
/**
- * Iterate over all entries in the map.
+ * Destroys the heap. Only call on a heap that
+ * is already empty.
*
- * @param heap - the heap
- * @param iterator - function to call on each entry
- * @param cls - client argument (closure)
- * @return GNUNET_YES if we iterated over all items, otherwise GNUNET_NO
+ * @param heap heap to destroy
*/
-int GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
- GNUNET_CONTAINER_HeapIterator iterator,
- void *cls);
+void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
/**
- * Inserts a new item into the heap, item is always neighbor now.
+ * Get element stored at root of heap.
+ *
+ * @param heap heap to inspect
+ * @return NULL if heap is empty
*/
-int
-GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
- void *element, GNUNET_CostType cost);
+void *
+GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
+
/**
- * 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.
+ * Get the current size of the heap
+ *
+ * @param heap the heap to get the size of
+ * @return number of elements stored
*/
-void *GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root);
+unsigned int
+GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap);
+
/**
- * Returns data stored at root of tree, doesn't effect anything
+ * Iterator for heap
+ *
+ * @param cls closure
+ * @param node internal node of the heap
+ * @param element value stored at the node
+ * @param cost cost associated with the node
+ * @return GNUNET_YES if we should continue to iterate,
+ * GNUNET_NO if not.
*/
-void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *root);
+typedef int (*GNUNET_CONTAINER_HeapIterator) (void *cls,
+ struct GNUNET_CONTAINER_HeapNode
*node,
+ void *element,
+ GNUNET_CONTAINER_HeapCostType
cost);
+
/**
- * 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.
+ * Iterate over all entries in the heap.
+ *
+ * @param heap the heap
+ * @param iterator function to call on each entry
+ * @param iterator_cls closure for iterator
*/
-void *GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
- void *element);
+void
+GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
+ GNUNET_CONTAINER_HeapIterator iterator,
+ void *iterator_cls);
+
/**
- * Updates the cost of any node in the tree
+ * Perform a random walk of the tree. The walk is biased
+ * towards elements closer to the root of the tree (since
+ * each walk starts at the root and ends at a random leaf).
+ * The heap internally tracks the current position of the
+ * walk.
+ *
+ * @param heap heap to walk
+ * @return data stored at the next random node in the walk;
+ * NULL if the tree is empty.
*/
-int
-GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
- void *element, GNUNET_CostType new_cost);
+void *
+GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
+
/**
- * 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.
+ * Inserts a new element into the heap.
+ *
+ * @param heap heap to modify
+ * @param element element to insert
+ * @param cost cost for the element
+ * @return node for the new element
*/
-void *GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap
- *root);
+struct GNUNET_CONTAINER_HeapNode *
+GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
+ void *element,
+ GNUNET_CONTAINER_HeapCostType cost);
-/*
- * Returns the current size of the heap
+
+/**
+ * Remove root of the heap.
*
- * @param heap the heap to get the size of
+ * @param heap heap to modify
+ * @return element data stored at the root node
*/
-unsigned int
-GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap);
+void *
+GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
+/**
+ * Removes a node from the heap.
+ *
+ * @param heap heap to modify
+ * @param node node to remove
+ * @return element data stored at the node, NULL if heap is empty
+ */
+void *
+GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *node);
+
+
+/**
+ * Updates the cost of any node in the tree
+ *
+ * @param heap heap to modify
+ * @param node node for which the cost is to be changed
+ * @param new_cost new cost for the node
+ */
+void
+GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *node,
+ GNUNET_CONTAINER_HeapCostType new_cost);
+
#if 0 /* keep Emacsens' auto-indent happy */
{
#endif
Modified: GNUnet/src/util/containers/heap.c
===================================================================
--- GNUnet/src/util/containers/heap.c 2009-12-23 12:04:09 UTC (rev 9869)
+++ GNUnet/src/util/containers/heap.c 2009-12-23 14:58:45 UTC (rev 9870)
@@ -1,6 +1,6 @@
/*
This file is part of GNUnet.
- (C) 2008 Christian Grothoff (and other contributing authors)
+ (C) 2008, 2009 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
@@ -19,9 +19,10 @@
*/
/**
+ * @file util/containers/heap.c
+ * @brief Implementation of a heap
* @author Nathan Evans
- * @file applications/dv/module/heap.c
- * @brief Implementation of heap operations
+ * @author Christian Grothoff
*/
#include "platform.h"
@@ -30,530 +31,518 @@
#include "gnunet_util_containers.h"
-/*
- * Generic heap node structure, contains pointer to parent
- * left child, right child, and actual neighbor.
+#define DEBUG 0
+
+/**
+ * Node in the heap.
*/
-struct GNUNET_CONTAINER_heap_node
+struct GNUNET_CONTAINER_HeapNode
{
- struct GNUNET_CONTAINER_heap_node *parent;
+ /**
+ * Parent node.
+ */
+ struct GNUNET_CONTAINER_HeapNode *parent;
- struct GNUNET_CONTAINER_heap_node *left_child;
+ /**
+ * Left child.
+ */
+ struct GNUNET_CONTAINER_HeapNode *left_child;
- struct GNUNET_CONTAINER_heap_node *right_child;
+ /**
+ * Right child.
+ */
+ struct GNUNET_CONTAINER_HeapNode *right_child;
- GNUNET_CostType cost;
-
+ /**
+ * Our element.
+ */
void *element;
+ /**
+ * Cost for this element.
+ */
+ GNUNET_CONTAINER_HeapCostType cost;
+
+ /**
+ * Number of elements below this node in the heap
+ * (excluding this node itself).
+ */
+ unsigned int tree_size;
+
};
+/**
+ * Handle to a node in a heap.
+ */
struct GNUNET_CONTAINER_Heap
{
- unsigned int size;
- unsigned int max_size;
+ /**
+ * Root of the heap.
+ */
+ struct GNUNET_CONTAINER_HeapNode *root;
- GNUNET_CONTAINER_HeapType type;
+ /**
+ * Current position of our random walk.
+ */
+ struct GNUNET_CONTAINER_HeapNode *walk_pos;
- struct GNUNET_CONTAINER_heap_node *root;
+ /**
+ * Number of elements in the heap.
+ */
+ unsigned int size;
+
+ /**
+ * How is the heap sorted?
+ */
+ enum GNUNET_CONTAINER_HeapOrder order;
- struct GNUNET_CONTAINER_heap_node *traversal_pos;
-
};
-int
-next_power_of_2 (int v)
-{
- v |= v >> 1;
- v |= v >> 2;
- v |= v >> 4;
- v |= v >> 8;
- v |= v >> 16;
- v++;
- return v;
-}
-void
-internal_print (struct GNUNET_CONTAINER_heap_node *root)
-{
- fprintf (stdout, "%d\n", (int) root->cost);
- if (root->left_child != NULL)
- {
- fprintf (stdout, "LEFT of %d\n", (int) root->cost);
- internal_print (root->left_child);
- }
- if (root->right_child != NULL)
- {
- fprintf (stdout, "RIGHT of %d\n", (int) root->cost);
- internal_print (root->right_child);
- }
+#if DEBUG
+/**
+ * Check if internal invariants hold for the given node.
+ *
+ * @param node subtree to check
+ */
+static void
+check (const struct GNUNET_CONTAINER_HeapNode *node)
+{
+ if (NULL == node)
+ return;
+ GNUNET_GE_ASSERT (NULL,
+ node->tree_size ==
+ ( (node->left_child == NULL) ? 0 : 1 +
node->left_child->tree_size) +
+ ( (node->right_child == NULL) ? 0 : 1 +
node->right_child->tree_size) );
+ check (node->left_child);
+ check (node->right_child);
}
-void
-printTree (struct GNUNET_CONTAINER_Heap *root)
-{
- internal_print (root->root);
-}
+#define CHECK(n) check(n)
+#else
+#define CHECK(n) do {} while (0)
+#endif
+
+
+/**
+ * Create a new heap.
+ *
+ * @param order how should the heap be sorted?
+ * @return handle to the heap
+ */
struct GNUNET_CONTAINER_Heap *
-GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HeapType type)
+GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
{
struct GNUNET_CONTAINER_Heap *heap;
- heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
- if (heap == NULL)
- return heap;
- heap->max_size = -1;
- heap->type = type;
- heap->root = NULL;
- heap->traversal_pos = NULL;
- heap->size = 0;
+ heap = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_Heap));
+ heap->order = order;
return heap;
}
-void *
-GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *root)
-{
- if ((root == NULL) || (root->root == NULL))
- return NULL;
- return root->root->element;
-}
+/**
+ * Destroys the heap. Only call on a heap that
+ * is already empty.
+ *
+ * @param heap heap to destroy
+ */
void
GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
{
- while (heap->size > 0)
- GNUNET_CONTAINER_heap_remove_root (heap);
+ GNUNET_GE_BREAK (NULL, heap->size == 0);
GNUNET_free (heap);
}
-struct GNUNET_CONTAINER_heap_node *
-find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
-{
- struct GNUNET_CONTAINER_heap_node *ret;
- ret = NULL;
- if ((node != NULL) && (node->element == element))
- {
- ret = node;
- }
-
- if ((ret == NULL) && (node != NULL) && (node->left_child != NULL))
- {
- ret = find_element (node->left_child, element);
- }
-
- if ((ret == NULL) && (node != NULL) && (node->right_child != NULL))
- {
- ret = find_element (node->right_child, element);
- }
-
- return ret;
-}
-
-static struct GNUNET_CONTAINER_heap_node *
-getNextPos (struct GNUNET_CONTAINER_Heap *root)
+/**
+ * Get element stored at root of heap.
+ *
+ * @param heap heap to inspect
+ * @return NULL if heap is empty
+ */
+void *
+GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
{
- struct GNUNET_CONTAINER_heap_node *ret;
- struct GNUNET_CONTAINER_heap_node *parent;
- int pos;
- int i;
-
- ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
- pos = root->size + 1;
- ret->left_child = NULL;
- ret->right_child = NULL;
-
- if (0 == root->size)
- {
- ret->parent = NULL;
- root->root = ret;
- }
- else
- {
- parent = root->root;
- for (i = next_power_of_2 (pos) >> 2; i > 1; i >>= 1)
- {
- if (((pos / i) % 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;
-
+ if (heap->root == NULL)
+ return NULL;
+ return heap->root->element;
}
-static struct GNUNET_CONTAINER_heap_node *
-getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
-{
- struct GNUNET_CONTAINER_heap_node *ret;
- unsigned int i;
- ret = NULL;
- if (pos > root->size)
- {
- return ret;
- }
- else
- {
- ret = root->root;
- for (i = next_power_of_2 (pos) >> 2; i > 0; i >>= 1)
- {
- if (((pos / i) % 2) == 0)
- ret = ret->left_child;
- else
- ret = ret->right_child;
- }
- }
-
- return ret;
-
-}
-
-void
-swapNodes (struct GNUNET_CONTAINER_heap_node *first,
- struct GNUNET_CONTAINER_heap_node *second,
- struct GNUNET_CONTAINER_Heap *root)
+/**
+ * Get the current size of the heap
+ *
+ * @param heap the heap to get the size of
+ * @return number of elements stored
+ */
+unsigned int
+GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
{
- void *temp_element;
- GNUNET_CostType temp_cost;
-
- temp_element = first->element;
- temp_cost = first->cost;
- first->element = second->element;
- first->cost = second->cost;
- second->element = temp_element;
- second->cost = temp_cost;
-
-/*
- * I still worry that there is some good reason for
- * elements being location aware... but it eludes me
- * for the moment...
- 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;
+ return heap->size;
}
-void
-percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
- struct GNUNET_CONTAINER_Heap *root)
-{
- while ((pos->parent != NULL) &&
- (((root->type == GNUNET_MAX_HEAP)
- && (pos->parent->cost < pos->cost))
- || ((root->type == GNUNET_MIN_HEAP)
- && (pos->parent->cost > pos->cost))))
- {
- swapNodes (pos, pos->parent, root);
- pos = pos->parent;
- }
-
- return;
+/**
+ * Iterate over the children of the given node.
+ *
+ * @param heap argument to give to iterator
+ * @param node node to iterate over
+ * @param iterator function to call on each node
+ * @param iterator_cls closure for iterator
+ * @return GNUNET_YES to continue to iterate
+ */
+static int
+node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *node,
+ GNUNET_CONTAINER_HeapIterator iterator,
+ void *iterator_cls)
+{
+ if (node == NULL)
+ return GNUNET_YES;
+ if (GNUNET_YES != node_iterator (heap,
+ node->left_child,
+ iterator,
+ iterator_cls))
+ return GNUNET_NO;
+ if (GNUNET_YES != node_iterator (heap,
+ node->right_child,
+ iterator,
+ iterator_cls))
+ return GNUNET_NO;
+ return iterator (iterator_cls,
+ node,
+ node->element,
+ node->cost);
}
-
+/**
+ * Iterate over all entries in the heap.
+ *
+ * @param heap the heap
+ * @param iterator function to call on each entry
+ * @param iterator_cls closure for iterator
+ */
void
-percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
- struct GNUNET_CONTAINER_Heap *root)
+GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
+ GNUNET_CONTAINER_HeapIterator iterator,
+ void *iterator_cls)
{
- struct GNUNET_CONTAINER_heap_node *switchNeighbor;
-
- switchNeighbor = pos;
-
- if ((root->type == GNUNET_MAX_HEAP))
- {
- if ((pos->left_child != NULL)
- && (pos->left_child->cost > switchNeighbor->cost))
- {
- switchNeighbor = pos->left_child;
- }
-
- if ((pos->right_child != NULL)
- && (pos->right_child->cost > switchNeighbor->cost))
- {
- switchNeighbor = pos->right_child;
- }
- }
- else if ((root->type == GNUNET_MIN_HEAP))
- {
- if ((pos->left_child != NULL)
- && (pos->left_child->cost < switchNeighbor->cost))
- {
- switchNeighbor = pos->left_child;
- }
-
- if ((pos->right_child != NULL)
- && (pos->right_child->cost < switchNeighbor->cost))
- {
- switchNeighbor = pos->right_child;
- }
- }
-
- if (switchNeighbor != pos)
- {
- swapNodes (switchNeighbor, pos, root);
- percolateDownHeap (switchNeighbor, root);
- }
-
- return;
+ (void) node_iterator (heap, heap->root, iterator, iterator_cls);
}
+
+/**
+ * Perform a random walk of the tree. The walk is biased
+ * towards elements closer to the root of the tree (since
+ * each walk starts at the root and ends at a random leaf).
+ * The heap internally tracks the current position of the
+ * walk.
+ *
+ * @param heap heap to walk
+ * @return data stored at the next random node in the walk;
+ * NULL if the tree is empty.
+ */
void *
-GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
- void *element)
+GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
{
- void *ret;
- struct GNUNET_CONTAINER_heap_node *del_node;
- struct GNUNET_CONTAINER_heap_node *last;
- GNUNET_CostType old_cost;
+ struct GNUNET_CONTAINER_HeapNode *pos;
+ void *element;
- del_node = NULL;
- del_node = find_element (root->root, element);
-
- if (del_node == NULL)
+ if (heap->root == NULL)
return NULL;
- else if (del_node == root->root)
- return GNUNET_CONTAINER_heap_remove_root (root);
+ pos = heap->walk_pos;
+ if (pos == NULL)
+ pos = heap->root;
+ element = pos->element;
+ heap->walk_pos
+ = (0 == GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2))
+ ? pos->right_child
+ : pos->left_child;
+ return element;
+}
- ret = del_node->element;
- last = getPos (root, root->size);
- root->size = root->size - 1;
- old_cost = del_node->cost;
- del_node->element = last->element;
- del_node->cost = last->cost;
- if (last->parent->left_child == last)
- last->parent->left_child = NULL;
- if (last->parent->right_child == last)
- last->parent->right_child = NULL;
+/**
+ * Insert the given node 'node' into the subtree starting
+ * at 'pos' (while keeping the tree somewhat balanced).
+ *
+ * @param pos existing tree
+ * @param node node to insert (which may be a subtree itself)
+ */
+static void
+insert_node (struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *pos,
+ struct GNUNET_CONTAINER_HeapNode *node)
+{
+ struct GNUNET_CONTAINER_HeapNode *parent;
- if (root->traversal_pos == last)
+ GNUNET_GE_ASSERT (NULL, node->parent == NULL);
+ while ( (pos->cost < node->cost) ^ (heap->order ==
GNUNET_CONTAINER_HEAP_ORDER_MAX) )
{
- root->traversal_pos = root->root;
+ /* node is descendent of pos */
+ pos->tree_size += (1 + node->tree_size);
+ if (pos->left_child == NULL)
+ {
+ pos->left_child = node;
+ node->parent = pos;
+ return;
+ }
+ if (pos->right_child == NULL)
+ {
+ pos->right_child = node;
+ node->parent = pos;
+ return;
+ }
+ /* keep it balanced by descending into smaller subtree */
+ if (pos->left_child->tree_size < pos->right_child->tree_size)
+ pos = pos->left_child;
+ else
+ pos = pos->right_child;
}
-
- if (last == del_node)
+ /* make 'node' parent of 'pos' */
+ parent = pos->parent;
+ pos->parent = NULL;
+ node->parent = parent;
+ if (NULL == parent)
{
- GNUNET_free (last);
- return ret;
+ heap->root = node;
}
-
- GNUNET_free (last);
-
-
- if (del_node->cost > old_cost)
+ else
{
- if (root->type == GNUNET_MAX_HEAP)
- percolateHeap (del_node, root);
- else if (root->type == GNUNET_MIN_HEAP)
- percolateDownHeap (del_node, root);
+ if (parent->left_child == pos)
+ parent->left_child = node;
+ else
+ parent->right_child = node;
}
- else if (del_node->cost < old_cost)
- {
- if (root->type == GNUNET_MAX_HEAP)
- percolateDownHeap (del_node, root);
- else if (root->type == GNUNET_MIN_HEAP)
- percolateHeap (del_node, root);
- }
-
- return ret;
+ /* insert 'pos' below 'node' */
+ insert_node (heap, node, pos);
+ CHECK (pos);
}
-int
-GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
- void *element, GNUNET_CostType cost)
+
+/**
+ * Inserts a new element into the heap.
+ *
+ * @param heap heap to modify
+ * @param element element to insert
+ * @param cost cost for the element
+ * @return node for the new element
+ */
+struct GNUNET_CONTAINER_HeapNode *
+GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
+ void *element,
+ GNUNET_CONTAINER_HeapCostType cost)
{
- struct GNUNET_CONTAINER_heap_node *new_pos;
- int ret;
- ret = GNUNET_YES;
+ struct GNUNET_CONTAINER_HeapNode *node;
- if (root->max_size > root->size)
- {
- new_pos = getNextPos (root);
- new_pos->element = element;
- new_pos->cost = cost;
- root->size++;
- /*We no longer can tolerate pointers between heaps :( */
- /*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);
- }
+ node = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_HeapNode));
+ node->element = element;
+ node->cost = cost;
+ heap->size++;
+ if (NULL == heap->root)
+ heap->root = node;
else
- {
- ret = GNUNET_NO;
- }
-
- return ret;
+ insert_node (heap, heap->root, node);
+ GNUNET_GE_ASSERT (NULL, heap->size == heap->root->tree_size + 1);
+ CHECK (heap->root);
+ return node;
}
+
+/**
+ * Remove root of the heap.
+ *
+ * @param heap heap to modify
+ * @return element data stored at the root node, NULL if heap is empty
+ */
void *
-GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
+GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
{
void *ret;
- struct GNUNET_CONTAINER_heap_node *root_node;
- struct GNUNET_CONTAINER_heap_node *last;
+ struct GNUNET_CONTAINER_HeapNode *root;
- if ((root == NULL) || (root->size == 0) || (root->root == NULL))
+ if (NULL == (root = heap->root))
return NULL;
-
- root_node = root->root;
- ret = root_node->element;
- last = getPos (root, root->size);
-
- if ((root_node == last) && (root->size == 1)) /* We are removing the last
node in the heap! */
+ heap->size--;
+ ret = root->element;
+ if (root->left_child == NULL)
{
- GNUNET_free (root->root);
- root->root = NULL;
- root->traversal_pos = NULL;
- root->size = 0;
- return ret;
+ heap->root = root->right_child;
+ if (root->right_child != NULL)
+ root->right_child->parent = NULL;
}
-
- 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->element = last->element;
- root_node->cost = last->cost;
-
- if (root->traversal_pos == last)
+ else if (root->right_child == NULL)
{
- root->traversal_pos = root->root;
+ heap->root = root->left_child;
+ if (root->left_child != NULL)
+ root->left_child->parent = NULL;
}
-
- GNUNET_free (last);
- root->size--;
- percolateDownHeap (root->root, root);
+ else
+ {
+ root->left_child->parent = NULL;
+ root->right_child->parent = NULL;
+ heap->root = root->left_child;
+ insert_node (heap, heap->root, root->right_child);
+ }
+ GNUNET_free (root);
+#if DEBUG
+ GNUNET_GE_ASSERT (NULL,
+ ( (heap->size == 0) &&
+ (heap->root == NULL) ) ||
+ (heap->size == heap->root->tree_size + 1) );
+ CHECK (heap->root);
+#endif
return ret;
}
-static int
-updatedCost (struct GNUNET_CONTAINER_Heap *root,
- struct GNUNET_CONTAINER_heap_node *node)
-{
- struct GNUNET_CONTAINER_heap_node *parent;
- if (node == NULL)
- return GNUNET_SYSERR;
-
- parent = node->parent;
-
- if ((root->type == GNUNET_MAX_HEAP) && (parent != NULL)
- && (node->cost > parent->cost))
- percolateHeap (node, root);
- else if ((root->type == GNUNET_MIN_HEAP) && (parent != NULL)
- && (node->cost < parent->cost))
- percolateHeap (node, root);
- else if (root->type == GNUNET_MAX_HEAP)
- percolateDownHeap (node, root);
- else if (root->type == GNUNET_MIN_HEAP)
- percolateDownHeap (node, root);
-
- return GNUNET_YES;
-}
-
-
-int
-GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
- void *element, GNUNET_CostType new_cost)
+/**
+ * Remove the given node 'node' from the tree and update
+ * the 'tree_size' fields accordingly. Preserves the
+ * children of 'node' and does NOT change the overall
+ * 'size' field of the tree.
+ */
+static void
+remove_node (struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *node)
{
- struct GNUNET_CONTAINER_heap_node *node;
- int ret = GNUNET_YES;
- node = find_element (root->root, element);
- if (node == NULL)
- return GNUNET_NO;
+ struct GNUNET_CONTAINER_HeapNode *ancestor;
- node->cost = new_cost;
- ret = updatedCost (root, node);
- return ret;
-}
+ /* update 'size' of the ancestors */
+ ancestor = node;
+ while (NULL != (ancestor = ancestor->parent))
+ ancestor->tree_size--;
-int
-internal_iterator (struct GNUNET_CONTAINER_Heap *root,
- struct GNUNET_CONTAINER_heap_node *node,
- GNUNET_CONTAINER_HeapIterator iterator, void *cls)
-{
- int ret;
- if (node == NULL)
- return GNUNET_YES;
- if (GNUNET_YES !=
- (ret = internal_iterator (root, node->left_child, iterator, cls)))
- return ret;
- if (GNUNET_YES !=
- (ret = internal_iterator (root, node->right_child, iterator, cls)))
- return ret;
- return iterator (node->element, node->cost, root, cls);
-}
+ /* update 'size' of node itself */
+ if (node->left_child != NULL)
+ node->tree_size -= (1 + node->left_child->tree_size);
+ if (node->right_child != NULL)
+ node->tree_size -= (1 + node->right_child->tree_size);
-int
-GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
- GNUNET_CONTAINER_HeapIterator iterator,
- void *cls)
-{
- return internal_iterator (heap, heap->root, iterator, cls);
-}
-
-void *
-GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
-{
- unsigned int choice;
- void *element;
-
- if ((root->traversal_pos == NULL) && (root->root != NULL))
+ /* unlink 'node' itself and insert children in its place */
+ if (node->parent == NULL)
{
- root->traversal_pos = root->root;
+ if (node->left_child != NULL)
+ {
+ heap->root = node->left_child;
+ node->left_child->parent = NULL;
+ if (node->right_child != NULL)
+ {
+ node->right_child->parent = NULL;
+ insert_node (heap, heap->root, node->right_child);
+ }
+ }
+ else
+ {
+ heap->root = node->right_child;
+ if (node->right_child != NULL)
+ node->right_child->parent = NULL;
+ }
}
-
- if (root->traversal_pos == NULL)
- return NULL;
-
- element = root->traversal_pos->element;
-
- choice = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2);
-
- switch (choice)
+ else
{
- case 1:
- root->traversal_pos = root->traversal_pos->right_child;
- break;
- case 0:
- root->traversal_pos = root->traversal_pos->left_child;
- break;
+ if (node->parent->left_child == node)
+ node->parent->left_child = NULL;
+ else
+ node->parent->right_child = NULL;
+ if (node->left_child != NULL)
+ {
+ node->left_child->parent = NULL;
+ node->parent->tree_size -= (1 + node->left_child->tree_size);
+ insert_node (heap, node->parent, node->left_child);
+ }
+ if (node->right_child != NULL)
+ {
+ node->right_child->parent = NULL;
+ node->parent->tree_size -= (1 + node->right_child->tree_size);
+ insert_node (heap, node->parent, node->right_child);
+ }
}
+ node->parent = NULL;
+ node->left_child = NULL;
+ node->right_child = NULL;
+ GNUNET_GE_ASSERT (NULL, node->tree_size == 0);
+ CHECK (heap->root);
+}
- return element;
+/**
+ * Removes a node from the heap.
+ *
+ * @param heap heap to modify
+ * @param node node to remove
+ * @return element data stored at the node
+ */
+void *
+GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *node)
+{
+ void *ret;
+
+ CHECK (heap->root);
+ if (heap->walk_pos == node)
+ (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
+ remove_node (heap, node);
+ heap->size--;
+ ret = node->element;
+ if (heap->walk_pos == node)
+ heap->walk_pos = NULL;
+ GNUNET_free (node);
+#if DEBUG
+ CHECK (heap->root);
+ GNUNET_GE_ASSERT (NULL,
+ ( (heap->size == 0) &&
+ (heap->root == NULL) ) ||
+ (heap->size == heap->root->tree_size + 1) );
+#endif
+ return ret;
}
-unsigned int
-GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
+
+/**
+ * Updates the cost of any node in the tree
+ *
+ * @param heap heap to modify
+ * @param node node for which the cost is to be changed
+ * @param new_cost new cost for the node
+ */
+void
+GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *node,
+ GNUNET_CONTAINER_HeapCostType new_cost)
{
- return heap->size;
+#if DEBUG
+ GNUNET_GE_ASSERT (NULL,
+ ( (heap->size == 0) &&
+ (heap->root == NULL) ) ||
+ (heap->size == heap->root->tree_size + 1) );
+ CHECK (heap->root);
+#endif
+ remove_node (heap, node);
+#if DEBUG
+ CHECK (heap->root);
+ GNUNET_GE_ASSERT (NULL,
+ ( (heap->size == 1) &&
+ (heap->root == NULL) ) ||
+ (heap->size == heap->root->tree_size + 2) );
+#endif
+ node->cost = new_cost;
+ if (heap->root == NULL)
+ heap->root = node;
+ else
+ insert_node (heap, heap->root, node);
+#if DEBUG
+ CHECK (heap->root);
+ GNUNET_GE_ASSERT (NULL,
+ ( (heap->size == 0) &&
+ (heap->root == NULL) ) ||
+ (heap->size == heap->root->tree_size + 1) );
+#endif
}
+
/* end of heap.c */
Modified: GNUnet/src/util/containers/heaptest.c
===================================================================
--- GNUnet/src/util/containers/heaptest.c 2009-12-23 12:04:09 UTC (rev
9869)
+++ GNUnet/src/util/containers/heaptest.c 2009-12-23 14:58:45 UTC (rev
9870)
@@ -20,10 +20,11 @@
/**
* @author Nathan Evans
+ * @author Christian Grothoff
* @file util/containers/heaptest.c
* @brief Test of heap operations
*/
-
+#include "platform.h"
#include "gnunet_util.h"
#include "gnunet_util_containers.h"
#include "dv.h"
@@ -31,15 +32,11 @@
#define VERBOSE GNUNET_NO
static int
-iterator_callback (void *element, GNUNET_CostType cost,
- struct GNUNET_CONTAINER_Heap *root, void *cls)
+iterator_callback (void *cls,
+ struct GNUNET_CONTAINER_HeapNode *node,
+ void *element,
+ GNUNET_CONTAINER_HeapCostType cost)
{
-#if VERBOSE
- struct GNUNET_dv_neighbor *node;
- node = (struct GNUNET_dv_neighbor *) element;
- fprintf (stdout, "%d\n", node->cost);
- //fprintf (stdout, "%d\n", ((struct GNUNET_dv_neighbor *)element)->cost);
-#endif
return GNUNET_OK;
}
@@ -48,75 +45,58 @@
main (int argc, char **argv)
{
struct GNUNET_CONTAINER_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;
+ struct GNUNET_CONTAINER_HeapNode *n1;
+ struct GNUNET_CONTAINER_HeapNode *n2;
+ struct GNUNET_CONTAINER_HeapNode *n3;
+ struct GNUNET_CONTAINER_HeapNode *n4;
+ struct GNUNET_CONTAINER_HeapNode *n5;
+ struct GNUNET_CONTAINER_HeapNode *n6;
- myHeap = GNUNET_CONTAINER_heap_create (GNUNET_MIN_HEAP);
+ myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
+ n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
+ GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
+ GNUNET_GE_ASSERT (NULL,
+ 1 == GNUNET_CONTAINER_heap_get_size (myHeap));
+ n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
+ GNUNET_GE_ASSERT (NULL,
+ 2 == GNUNET_CONTAINER_heap_get_size (myHeap));
+ GNUNET_GE_ASSERT (NULL,
+ 0 == strcmp ("78",
+ GNUNET_CONTAINER_heap_remove_node (myHeap,
n2)));
+ GNUNET_GE_ASSERT (NULL,
+ 1 == GNUNET_CONTAINER_heap_get_size (myHeap));
+ GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
- 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));
+ n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
+ GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15);
+ GNUNET_GE_ASSERT (NULL,
+ 2 == GNUNET_CONTAINER_heap_get_size (myHeap));
+ GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
- neighbor1->cost = 11;
- neighbor2->cost = 78;
- neighbor3->cost = 5;
- neighbor4->cost = 50;
- neighbor5->cost = 100;
- neighbor6->cost = 30;
+ n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
+ GNUNET_GE_ASSERT (NULL,
+ 3 == GNUNET_CONTAINER_heap_get_size (myHeap));
+ GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
- GNUNET_CONTAINER_heap_insert (myHeap, neighbor1, neighbor1->cost);
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
- fprintf (stderr, "size is %d\n", GNUNET_CONTAINER_heap_get_size (myHeap));
-
- GNUNET_CONTAINER_heap_insert (myHeap, neighbor2, neighbor2->cost);
- fprintf (stderr, "size is %d\n", GNUNET_CONTAINER_heap_get_size (myHeap));
-
- GNUNET_CONTAINER_heap_remove_node (myHeap, neighbor2);
- fprintf (stderr, "size is %d\n", GNUNET_CONTAINER_heap_get_size (myHeap));
-
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
- GNUNET_CONTAINER_heap_insert (myHeap, neighbor3, neighbor3->cost);
- GNUNET_CONTAINER_heap_update_cost (myHeap, neighbor3, 15);
- fprintf (stderr, "size is %d\n", GNUNET_CONTAINER_heap_get_size (myHeap));
-
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
- GNUNET_CONTAINER_heap_insert (myHeap, neighbor4, neighbor4->cost);
- fprintf (stderr, "size is %d\n", GNUNET_CONTAINER_heap_get_size (myHeap));
-
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
- GNUNET_CONTAINER_heap_insert (myHeap, neighbor5, neighbor5->cost);
-
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
- GNUNET_CONTAINER_heap_insert (myHeap, neighbor6, neighbor6->cost);
-
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
- GNUNET_CONTAINER_heap_remove_node (myHeap, neighbor5);
-
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
- GNUNET_CONTAINER_heap_remove_root (myHeap);
-
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
- GNUNET_CONTAINER_heap_update_cost (myHeap, neighbor6, 200);
- GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
-
+ n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
+ n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
+ GNUNET_GE_ASSERT (NULL,
+ 5 == GNUNET_CONTAINER_heap_get_size (myHeap));
+ GNUNET_CONTAINER_heap_remove_node (myHeap, n5);
+ GNUNET_GE_ASSERT (NULL,
+ 0 == strcmp ("11",
+ GNUNET_CONTAINER_heap_remove_root (myHeap)));
/* n1 */
+ GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);
+ GNUNET_CONTAINER_heap_remove_node (myHeap, n3);
+ GNUNET_GE_ASSERT (NULL,
+ 0 == strcmp ("50",
+ GNUNET_CONTAINER_heap_remove_root (myHeap)));
/* n4 */
+ GNUNET_GE_ASSERT (NULL,
+ 0 == strcmp ("30/200",
+ GNUNET_CONTAINER_heap_remove_root (myHeap)));
/* n6 */
+ GNUNET_GE_ASSERT (NULL, 0 == GNUNET_CONTAINER_heap_get_size (myHeap));
GNUNET_CONTAINER_heap_destroy (myHeap);
-
- GNUNET_free (neighbor1);
- GNUNET_free (neighbor2);
- GNUNET_free (neighbor3);
- GNUNET_free (neighbor4);
- GNUNET_free (neighbor5);
- GNUNET_free (neighbor6);
-
return 0;
-
}
/* end of heaptest.c */
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r9870 - in GNUnet/src: applications/dv/module applications/dv_dht/module include util/containers,
gnunet <=