src/util/test_container_heap.c

   1 /*
   2  This file is part of GNUnet.
   3  (C) 2008 Christian Grothoff (and other contributing authors)
   4
   5  GNUnet is free software; you can redistribute it and/or modify
   6  it under the terms of the GNU General Public License as published
   7  by the Free Software Foundation; either version 2, or (at your
   8  option) any later version.
   9
  10  GNUnet is distributed in the hope that it will be useful, but
  11  WITHOUT ANY WARRANTY; without even the implied warranty of
  12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  General Public License for more details.
  14
  15  You should have received a copy of the GNU General Public License
  16  along with GNUnet; see the file COPYING.  If not, write to the
  17  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18  Boston, MA 02111-1307, USA.
  19  */
  20
  21 /**
  22  * @author Nathan Evans
  23  * @file util/test_container_heap.c
  24  * @brief Test of heap operations
  25  */
  26
  27 #include "platform.h"
  28 #include "gnunet_common.h"
  29 #include "gnunet_container_lib.h"
  30
  31 static int
  32 iterator_callback (void *cls,
  33                    struct GNUNET_CONTAINER_HeapNode *node,
  34                    void *element,
  35                    GNUNET_CONTAINER_HeapCostType cost)
  36 {
  37   return GNUNET_OK;
  38 }
  39
  40 static int
  41 check ()
  42 {
  43   struct GNUNET_CONTAINER_Heap *myHeap;
  44   struct GNUNET_CONTAINER_HeapNode *n1;
  45   struct GNUNET_CONTAINER_HeapNode *n2;
  46   struct GNUNET_CONTAINER_HeapNode *n3;
  47   struct GNUNET_CONTAINER_HeapNode *n4;
  48   struct GNUNET_CONTAINER_HeapNode *n5;
  49   struct GNUNET_CONTAINER_HeapNode *n6;
  50   struct GNUNET_CONTAINER_HeapNode *n7;
  51   struct GNUNET_CONTAINER_HeapNode *n8;
  52
  53   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
  54
  55   // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch
  56   n1 = GNUNET_CONTAINER_heap_remove_root (myHeap);
  57   GNUNET_assert (NULL == n1);
  58
  59   // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch
  60   n1 = GNUNET_CONTAINER_heap_peek (myHeap);
  61   GNUNET_assert (NULL == n1);
  62
  63   // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch
  64   n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
  65   GNUNET_assert (NULL == n1);
  66
  67   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
  68   GNUNET_assert (NULL != n1);
  69
  70
  71   // GNUNET_CONTAINER_heap_peek not empty, taking if-branch
  72   n2 = NULL;
  73   n2 = GNUNET_CONTAINER_heap_peek (myHeap);
  74   GNUNET_assert (NULL != n2);
  75
  76   // GNUNET_CONTAINER_heap_walk_get_next: 1 element
  77   n1 = NULL;
  78   n1 = GNUNET_CONTAINER_heap_walk_get_next(myHeap);
  79   GNUNET_assert (NULL != n1);
  80
  81   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
  82   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
  83   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
  84   GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
  85   GNUNET_assert (0 == strcmp ("78",
  86                               GNUNET_CONTAINER_heap_remove_node (myHeap, n2)));
  87   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
  88   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
  89
  90   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
  91   GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15);
  92   GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
  93   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
  94
  95   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
  96   GNUNET_CONTAINER_heap_update_cost (myHeap, n4, 50);
  97   GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
  98   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
  99
 100   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
 101   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
 102   GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));
 103   GNUNET_CONTAINER_heap_remove_node (myHeap, n5);
 104   GNUNET_assert (0 == strcmp ("11",
 105                               GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n1 */
 106   GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);
 107   GNUNET_CONTAINER_heap_remove_node (myHeap, n3);
 108   GNUNET_assert (0 == strcmp ("50",
 109                               GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n4 */
 110   GNUNET_assert (0 == strcmp ("30/200",
 111                               GNUNET_CONTAINER_heap_remove_root (myHeap))); /* n6 */
 112   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));
 113
 114   GNUNET_CONTAINER_heap_destroy (myHeap);
 115
 116   // My additions to a complete testcase
 117   // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN
 118   // Testing remove_node
 119
 120   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 121
 122   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 123   GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
 124
 125   GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
 126
 127   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 128   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 129
 130   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 131   GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
 132   GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
 133
 134   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 135   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 136   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 137
 138   GNUNET_CONTAINER_heap_remove_node (myHeap,n2);
 139   GNUNET_CONTAINER_heap_remove_node (myHeap,n1);
 140   GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 141
 142   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 143   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 144   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 145
 146   GNUNET_CONTAINER_heap_remove_node (myHeap,n2);
 147   GNUNET_CONTAINER_heap_remove_node (myHeap,n1);
 148   GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3)));
 149
 150   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 151   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 152   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 153
 154   GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
 155   GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 156   GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 157
 158   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 159   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 160   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 161   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
 162   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
 163   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
 164
 165   // Inserting nodes deeper in the tree with lower costs
 166   n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
 167   n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
 168
 169   GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3)));
 170
 171   // Cleaning up...
 172   GNUNET_assert (0 == strcmp ("60", GNUNET_CONTAINER_heap_remove_node (myHeap,n6)));
 173   GNUNET_assert (0 == strcmp ("50", GNUNET_CONTAINER_heap_remove_node (myHeap,n5)));
 174
 175   // Testing heap_walk_get_next
 176   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 177   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 178   GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
 179   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 180   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 181
 182   GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
 183   GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
 184   GNUNET_assert (0 == strcmp ("40", GNUNET_CONTAINER_heap_remove_node (myHeap,n4)));
 185   GNUNET_assert (0 == strcmp ("70", GNUNET_CONTAINER_heap_remove_node (myHeap,n7)));
 186   GNUNET_assert (0 == strcmp ("80", GNUNET_CONTAINER_heap_remove_node (myHeap,n8)));
 187
 188   // End Testing remove_node
 189
 190   // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX
 191   GNUNET_CONTAINER_heap_destroy (myHeap);
 192
 193     myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
 194
 195   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 196   GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
 197
 198   GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
 199
 200   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 201   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 202
 203   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 204   GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
 205   GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
 206
 207   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 208   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 209   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 210
 211   GNUNET_CONTAINER_heap_remove_node (myHeap,n2);
 212   GNUNET_CONTAINER_heap_remove_node (myHeap,n1);
 213   GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 214
 215   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 216   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 217   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 218
 219   GNUNET_CONTAINER_heap_remove_node (myHeap,n2);
 220   GNUNET_CONTAINER_heap_remove_node (myHeap,n1);
 221   GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3)));
 222
 223   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 224   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 225   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 226   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
 227   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
 228   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
 229
 230   // Inserting nodes deeper in the tree with lower costs
 231   n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
 232   n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
 233
 234   GNUNET_assert (0 == strcmp ("30", GNUNET_CONTAINER_heap_remove_node (myHeap,n3)));
 235
 236   // Cleaning up...
 237   GNUNET_assert (0 == strcmp ("60", GNUNET_CONTAINER_heap_remove_node (myHeap,n6)));
 238   GNUNET_assert (0 == strcmp ("50", GNUNET_CONTAINER_heap_remove_node (myHeap,n5)));
 239
 240   // Testing heap_walk_get_next
 241   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 242   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 243   GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
 244   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 245   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 246
 247   GNUNET_assert (0 == strcmp ("10", GNUNET_CONTAINER_heap_remove_node (myHeap,n1)));
 248   GNUNET_assert (0 == strcmp ("20", GNUNET_CONTAINER_heap_remove_node (myHeap,n2)));
 249   GNUNET_assert (0 == strcmp ("40", GNUNET_CONTAINER_heap_remove_node (myHeap,n4)));
 250   GNUNET_assert (0 == strcmp ("70", GNUNET_CONTAINER_heap_remove_node (myHeap,n7)));
 251   GNUNET_assert (0 == strcmp ("80", GNUNET_CONTAINER_heap_remove_node (myHeap,n8)));
 252
 253   // End Testing remove_node
 254
 255   GNUNET_CONTAINER_heap_destroy (myHeap);
 256
 257   return 0;
 258 }
 259
 260
 261 int
 262 main (int argc, char **argv)
 263 {
 264   GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
 265   return check();
 266 }
 267
 268 /* end of test_container_heap.c */