projects / oweals / gnunet.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
-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 9e6a29ea487fb4183cc29d83024e1a08f7b05c46..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
@@ -28,66 +28,263 @@
 #include "gnunet_common.h"
 #include "gnunet_container_lib.h"
 
 #include "gnunet_common.h"
 #include "gnunet_container_lib.h"
 
-struct TestItem
+static int
+iterator_callback (void *cls, struct GNUNET_CONTAINER_HeapNode *node,
+                   void *element, GNUNET_CONTAINER_HeapCostType cost)
 {
 {
-  unsigned int cost;
-};
+  return GNUNET_OK;
+}
 
 static int
 
 static int
-iterator_callback (void *cls, void *element, GNUNET_CONTAINER_HeapCost cost)
+nstrcmp (const char *a, const char *b)
 {
 {
-  struct TestItem *node;
-  node = (struct TestItem *) element;
-#ifdef VERBOSE
-  fprintf (stdout, "%d\n", node->cost);
-#endif
-
-  return GNUNET_OK;
+  GNUNET_assert (a != NULL);
+  GNUNET_assert (b != NULL);
+  return strcmp (a, b);
 }
 
 }
 
-int
-main (int argc, char **argv)
+static int
+check ()
 {
   struct GNUNET_CONTAINER_Heap *myHeap;
 {
   struct GNUNET_CONTAINER_Heap *myHeap;
-  struct TestItem neighbor1;
-  struct TestItem neighbor2;
-  struct TestItem neighbor3;
-  struct TestItem neighbor4;
-  struct TestItem neighbor5;
-  struct TestItem 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;
+  struct GNUNET_CONTAINER_HeapNode *n7;
+  struct GNUNET_CONTAINER_HeapNode *n8;
+  const char *r;
 
 
-  GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
+  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);
+
+
+  // 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_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);
+
+  n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
+  GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15);
+  GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
+  GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
+
+  n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
+  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_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_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_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);
 
   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
 
 
   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
 
-  neighbor1.cost = 60;
-  neighbor2.cost = 50;
-  neighbor3.cost = 70;
-  neighbor4.cost = 120;
-  neighbor5.cost = 100;
-  neighbor6.cost = 30;
-
-  GNUNET_CONTAINER_heap_insert (myHeap, &neighbor1, neighbor1.cost);
-  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
-  GNUNET_CONTAINER_heap_insert (myHeap, &neighbor2, neighbor2.cost);
-  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
-  GNUNET_CONTAINER_heap_insert (myHeap, &neighbor3, neighbor3.cost);
-  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
-  GNUNET_CONTAINER_heap_insert (myHeap, &neighbor4, neighbor4.cost);
-  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);
+  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;
 }
 
   GNUNET_CONTAINER_heap_destroy (myHeap);
 
   return 0;
 }
 
+
+int
+main (int argc, char **argv)
+{
+  GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
+  return check ();
+}
+
 /* end of test_container_heap.c */
 /* end of test_container_heap.c */
Unnamed repository; edit this file 'description' to name the repository.