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