-add adv port

[oweals/gnunet.git] / src / util / test_container_heap.c

diff --git a/src/util/test_container_heap.c b/src/util/test_container_heap.c
index b24624ad8c194c2788a529c341d9acf8bae3849e..a2a004aa790758f3e76ae7b171636c944d900b70 100644 (file)
--- a/src/util/test_container_heap.c
+++ b/src/util/test_container_heap.c
@@ -4,7 +4,7 @@
 
  GNUnet is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published
 
  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
+ by the Free Software Foundation; either version 3, or (at your

  option) any later version.
 
  GNUnet is distributed in the hope that it will be useful, but
  option) any later version.
 
  GNUnet is distributed in the hope that it will be useful, but


@@ -29,14 +29,19 @@
 #include "gnunet_container_lib.h"
 
 static int
 #include "gnunet_container_lib.h"
 
 static int

-iterator_callback (void *cls,
-                  struct GNUNET_CONTAINER_HeapNode *node,
-                  void *element, 
-                  GNUNET_CONTAINER_HeapCostType cost)
+iterator_callback (void *cls, struct GNUNET_CONTAINER_HeapNode *node,
+                   void *element, GNUNET_CONTAINER_HeapCostType cost)

 {
   return GNUNET_OK;
 }
 
 {
   return GNUNET_OK;
 }
 

+static int
+nstrcmp (const char *a, const char *b)
+{
+  GNUNET_assert (a != NULL);
+  GNUNET_assert (b != NULL);
+  return strcmp (a, b);
+}

 
 static int
 check ()
 
 static int
 check ()


@@ -48,16 +53,43 @@ check ()
   struct GNUNET_CONTAINER_HeapNode *n4;
   struct GNUNET_CONTAINER_HeapNode *n5;
   struct GNUNET_CONTAINER_HeapNode *n6;
   struct GNUNET_CONTAINER_HeapNode *n4;
   struct GNUNET_CONTAINER_HeapNode *n5;
   struct GNUNET_CONTAINER_HeapNode *n6;

+  struct GNUNET_CONTAINER_HeapNode *n7;
+  struct GNUNET_CONTAINER_HeapNode *n8;
+  const char *r;

 
   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 
   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);

+
+  // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch
+  n1 = GNUNET_CONTAINER_heap_remove_root (myHeap);
+  GNUNET_assert (NULL == n1);
+
+  // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch
+  n1 = GNUNET_CONTAINER_heap_peek (myHeap);
+  GNUNET_assert (NULL == n1);
+
+  // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch
+  n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_assert (NULL == n1);
+

   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
   GNUNET_assert (NULL != n1);
   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
   GNUNET_assert (NULL != n1);

+
+
+  // GNUNET_CONTAINER_heap_peek not empty, taking if-branch
+  n2 = NULL;
+  n2 = GNUNET_CONTAINER_heap_peek (myHeap);
+  GNUNET_assert (NULL != n2);
+
+  // GNUNET_CONTAINER_heap_walk_get_next: 1 element
+  n1 = NULL;
+  n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_assert (NULL != n1);
+

   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
   GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
   GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));

-  GNUNET_assert (0 == strcmp ("78",
-                             GNUNET_CONTAINER_heap_remove_node (myHeap, n2)));
+  GNUNET_assert (0 == strcmp ("78", GNUNET_CONTAINER_heap_remove_node (n2)));

   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
 
   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
 


@@ -67,24 +99,183 @@ check ()
   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
 
   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
 
   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);

-  GNUNET_CONTAINER_heap_update_cost (myHeap, n4, 0);
+  GNUNET_CONTAINER_heap_update_cost (myHeap, n4, 50);

   GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
   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_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));
   GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
   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_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));

-  GNUNET_CONTAINER_heap_remove_node (myHeap, n5);
-  GNUNET_assert (0 == strcmp ("11",
-                             GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n1 */
+  GNUNET_CONTAINER_heap_remove_node (n5);
+  r = GNUNET_CONTAINER_heap_remove_root (myHeap);       /* n1 */
+  GNUNET_assert (NULL != r);
+  GNUNET_assert (0 == strcmp ("11", r));

   GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);
   GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);

-  GNUNET_CONTAINER_heap_remove_node (myHeap, n3); 
-  GNUNET_assert (0 == strcmp ("50",
-                             GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n4 */
-  GNUNET_assert (0 == strcmp ("30/200",
-                             GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n6 */
+  GNUNET_CONTAINER_heap_remove_node (n3);
+  r = GNUNET_CONTAINER_heap_remove_root (myHeap);       /* n4 */
+  GNUNET_assert (NULL != r);
+  GNUNET_assert (0 == strcmp ("50", r));
+  r = GNUNET_CONTAINER_heap_remove_root (myHeap);       /* n6 */
+  GNUNET_assert (NULL != r);
+  GNUNET_assert (0 == strcmp ("30/200", r));

   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));
   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));

+
+  GNUNET_CONTAINER_heap_destroy (myHeap);
+
+  // My additions to a complete testcase
+  // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN
+  // Testing remove_node
+
+  myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
+
+  r = GNUNET_CONTAINER_heap_remove_node (n1);
+  GNUNET_assert (NULL != r);
+  GNUNET_assert (0 == strcmp ("10", r));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
+
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  r = GNUNET_CONTAINER_heap_remove_node (n2);
+  GNUNET_assert (NULL != r);
+  GNUNET_assert (0 == strcmp ("20", r));
+  r = GNUNET_CONTAINER_heap_remove_node (n1);
+  GNUNET_assert (NULL != r);
+  GNUNET_assert (0 == strcmp ("10", r));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
+  n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
+
+  GNUNET_CONTAINER_heap_remove_node (n2);
+  GNUNET_CONTAINER_heap_remove_node (n1);
+  r = GNUNET_CONTAINER_heap_remove_root (myHeap);
+  GNUNET_assert (NULL != r);
+  GNUNET_assert (0 == strcmp ("30", r));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
+  n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
+
+  GNUNET_CONTAINER_heap_remove_node (n2);
+  GNUNET_CONTAINER_heap_remove_node (n1);
+  r = GNUNET_CONTAINER_heap_remove_node (n3);
+  GNUNET_assert (NULL != r);
+  GNUNET_assert (0 == strcmp ("30", r));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
+  n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
+
+  GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
+  GNUNET_assert (0 ==
+                 nstrcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap)));
+  GNUNET_assert (0 ==
+                 nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
+  n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
+  n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
+  n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
+  n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
+
+  // Inserting nodes deeper in the tree with lower costs
+  n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
+  n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
+
+  GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
+
+  // Cleaning up...
+  GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
+  GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
+
+  // Testing heap_walk_get_next
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+
+  GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
+  GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
+  GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
+  GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
+  GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
+
+  // End Testing remove_node
+
+  // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX

   GNUNET_CONTAINER_heap_destroy (myHeap);
   GNUNET_CONTAINER_heap_destroy (myHeap);

+
+  myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
+
+  GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
+
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
+  GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
+  n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
+
+  GNUNET_CONTAINER_heap_remove_node (n2);
+  GNUNET_CONTAINER_heap_remove_node (n1);
+  GNUNET_assert (0 ==
+                 nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
+  n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
+
+  GNUNET_CONTAINER_heap_remove_node (n2);
+  GNUNET_CONTAINER_heap_remove_node (n1);
+  GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
+
+  n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
+  n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
+  n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
+  n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
+  n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
+  n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
+
+  // Inserting nodes deeper in the tree with lower costs
+  n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
+  n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
+
+  GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
+
+  // Cleaning up...
+  GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
+  GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
+
+  // Testing heap_walk_get_next
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+  GNUNET_CONTAINER_heap_walk_get_next (myHeap);
+
+  GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
+  GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
+  GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
+  GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
+  GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
+
+  // End Testing remove_node
+
+  GNUNET_CONTAINER_heap_destroy (myHeap);
+

   return 0;
 }
 
   return 0;
 }
 


@@ -93,7 +284,7 @@ int
 main (int argc, char **argv)
 {
   GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
 main (int argc, char **argv)
 {
   GNUNET_log_setup ("test-container-heap", "WARNING", NULL);

-  return check();
+  return check ();

 }
 
 /* end of test_container_heap.c */
 }
 
 /* end of test_container_heap.c */