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