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 3, 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 nstrcmp (const char *a,
  42          const char *b)
  43 {
  44   GNUNET_assert (a != NULL);
  45   GNUNET_assert (b != NULL);
  46   return strcmp (a,b);
  47 }
  48
  49 static int
  50 check ()
  51 {
  52   struct GNUNET_CONTAINER_Heap *myHeap;
  53   struct GNUNET_CONTAINER_HeapNode *n1;
  54   struct GNUNET_CONTAINER_HeapNode *n2;
  55   struct GNUNET_CONTAINER_HeapNode *n3;
  56   struct GNUNET_CONTAINER_HeapNode *n4;
  57   struct GNUNET_CONTAINER_HeapNode *n5;
  58   struct GNUNET_CONTAINER_HeapNode *n6;
  59   struct GNUNET_CONTAINER_HeapNode *n7;
  60   struct GNUNET_CONTAINER_HeapNode *n8;
  61   const char *r;
  62
  63   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
  64
  65   // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch
  66   n1 = GNUNET_CONTAINER_heap_remove_root (myHeap);
  67   GNUNET_assert (NULL == n1);
  68
  69   // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch
  70   n1 = GNUNET_CONTAINER_heap_peek (myHeap);
  71   GNUNET_assert (NULL == n1);
  72
  73   // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch
  74   n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
  75   GNUNET_assert (NULL == n1);
  76
  77   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
  78   GNUNET_assert (NULL != n1);
  79
  80
  81   // GNUNET_CONTAINER_heap_peek not empty, taking if-branch
  82   n2 = NULL;
  83   n2 = GNUNET_CONTAINER_heap_peek (myHeap);
  84   GNUNET_assert (NULL != n2);
  85
  86   // GNUNET_CONTAINER_heap_walk_get_next: 1 element
  87   n1 = NULL;
  88   n1 = GNUNET_CONTAINER_heap_walk_get_next(myHeap);
  89   GNUNET_assert (NULL != n1);
  90
  91   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
  92   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
  93   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
  94   GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
  95   GNUNET_assert (0 == strcmp ("78",
  96                               GNUNET_CONTAINER_heap_remove_node (n2)));
  97   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
  98   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
  99
 100   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
 101   GNUNET_CONTAINER_heap_update_cost (myHeap, n3, 15);
 102   GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
 103   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
 104
 105   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
 106   GNUNET_CONTAINER_heap_update_cost (myHeap, n4, 50);
 107   GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
 108   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
 109
 110   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
 111   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
 112   GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));
 113   GNUNET_CONTAINER_heap_remove_node (n5);
 114   r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n1 */
 115   GNUNET_assert (NULL != r);
 116   GNUNET_assert (0 == strcmp ("11",
 117                               r));
 118   GNUNET_CONTAINER_heap_update_cost (myHeap, n6, 200);
 119   GNUNET_CONTAINER_heap_remove_node (n3);
 120   r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n4 */
 121   GNUNET_assert (NULL != r);
 122   GNUNET_assert (0 == strcmp ("50",
 123                               r));
 124   r = GNUNET_CONTAINER_heap_remove_root (myHeap); /* n6 */
 125   GNUNET_assert (NULL != r);
 126   GNUNET_assert (0 == strcmp ("30/200", r));
 127   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));
 128
 129   GNUNET_CONTAINER_heap_destroy (myHeap);
 130
 131   // My additions to a complete testcase
 132   // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN
 133   // Testing remove_node
 134
 135   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 136
 137   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 138   GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
 139
 140   r = GNUNET_CONTAINER_heap_remove_node (n1);
 141   GNUNET_assert (NULL != r);
 142   GNUNET_assert (0 == strcmp ("10", r));
 143
 144   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 145   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 146
 147   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 148   r = GNUNET_CONTAINER_heap_remove_node (n2);
 149   GNUNET_assert (NULL != r);
 150   GNUNET_assert (0 == strcmp ("20", r));
 151   r = GNUNET_CONTAINER_heap_remove_node (n1);
 152   GNUNET_assert (NULL != r);
 153   GNUNET_assert (0 == strcmp ("10", r));
 154
 155   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 156   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 157   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 158
 159   GNUNET_CONTAINER_heap_remove_node (n2);
 160   GNUNET_CONTAINER_heap_remove_node (n1);
 161   r = GNUNET_CONTAINER_heap_remove_root (myHeap);
 162   GNUNET_assert (NULL != r);
 163   GNUNET_assert (0 == strcmp ("30", r));
 164
 165   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 166   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 167   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 168
 169   GNUNET_CONTAINER_heap_remove_node (n2);
 170   GNUNET_CONTAINER_heap_remove_node (n1);
 171   r = GNUNET_CONTAINER_heap_remove_node ( n3);
 172   GNUNET_assert (NULL != r);
 173   GNUNET_assert (0 == strcmp ("30", r));
 174
 175   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 176   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 177   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 178
 179   GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
 180   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 181   GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 182
 183   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 184   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 185   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 186   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
 187   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
 188   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
 189
 190   // Inserting nodes deeper in the tree with lower costs
 191   n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
 192   n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
 193
 194   GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
 195
 196   // Cleaning up...
 197   GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
 198   GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
 199
 200   // Testing heap_walk_get_next
 201   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 202   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 203   GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
 204   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 205   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 206
 207   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
 208   GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
 209   GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
 210   GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
 211   GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
 212
 213   // End Testing remove_node
 214
 215   // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX
 216   GNUNET_CONTAINER_heap_destroy (myHeap);
 217
 218     myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
 219
 220   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 221   GNUNET_CONTAINER_heap_update_cost (myHeap, n1, 15);
 222
 223   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
 224
 225   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 226   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 227
 228   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 229   GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
 230   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
 231
 232   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 233   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 234   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 235
 236   GNUNET_CONTAINER_heap_remove_node (n2);
 237   GNUNET_CONTAINER_heap_remove_node (n1);
 238   GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 239
 240   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 241   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 242   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 243
 244   GNUNET_CONTAINER_heap_remove_node (n2);
 245   GNUNET_CONTAINER_heap_remove_node (n1);
 246   GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
 247
 248   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 249   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 250   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 251   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
 252   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
 253   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
 254
 255   // Inserting nodes deeper in the tree with lower costs
 256   n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
 257   n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
 258
 259   GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
 260
 261   // Cleaning up...
 262   GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
 263   GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
 264
 265   // Testing heap_walk_get_next
 266   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 267   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 268   GNUNET_CONTAINER_heap_walk_get_next (myHeap);;
 269   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 270   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 271
 272   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
 273   GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
 274   GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
 275   GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
 276   GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
 277
 278   // End Testing remove_node
 279
 280   GNUNET_CONTAINER_heap_destroy (myHeap);
 281
 282   return 0;
 283 }
 284
 285
 286 int
 287 main (int argc, char **argv)
 288 {
 289   GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
 290   return check();
 291 }
 292
 293 /* end of test_container_heap.c */