src/util/test_container_heap.c

   1 /*
   2    This file is part of GNUnet.
   3    Copyright (C) 2008 GNUnet e.V.
   4
   5    GNUnet is free software: you can redistribute it and/or modify it
   6    under the terms of the GNU Affero General Public License as published
   7    by the Free Software Foundation, either version 3 of the License,
   8    or (at your 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    Affero General Public License for more details.
  14
  15    You should have received a copy of the GNU Affero General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  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_util_lib.h"
  29
  30 static int
  31 iterator_callback (void *cls,
  32                    struct GNUNET_CONTAINER_HeapNode *node,
  33                    void *element, GNUNET_CONTAINER_HeapCostType cost)
  34 {
  35   return GNUNET_OK;
  36 }
  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
  48 static int
  49 check ()
  50 {
  51   struct GNUNET_CONTAINER_Heap *myHeap;
  52   struct GNUNET_CONTAINER_HeapNode *n1;
  53   struct GNUNET_CONTAINER_HeapNode *n2;
  54   struct GNUNET_CONTAINER_HeapNode *n3;
  55   struct GNUNET_CONTAINER_HeapNode *n4;
  56   struct GNUNET_CONTAINER_HeapNode *n5;
  57   struct GNUNET_CONTAINER_HeapNode *n6;
  58   struct GNUNET_CONTAINER_HeapNode *n7;
  59   struct GNUNET_CONTAINER_HeapNode *n8;
  60   const char *r;
  61
  62   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
  63
  64   // GNUNET_CONTAINER_heap_remove_root heap empty, taking if-branch
  65   n1 = GNUNET_CONTAINER_heap_remove_root (myHeap);
  66   GNUNET_assert (NULL == n1);
  67
  68   // GNUNET_CONTAINER_heap_peek heap empty, taking if-branch
  69   n1 = GNUNET_CONTAINER_heap_peek (myHeap);
  70   GNUNET_assert (NULL == n1);
  71
  72   // GNUNET_CONTAINER_heap_walk_get_next: heap empty, taking if-branch
  73   n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
  74   GNUNET_assert (NULL == n1);
  75
  76   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "11", 11);
  77   GNUNET_assert (NULL != n1);
  78
  79
  80   // GNUNET_CONTAINER_heap_peek not empty, taking if-branch
  81   n2 = NULL;
  82   n2 = GNUNET_CONTAINER_heap_peek (myHeap);
  83   GNUNET_assert (NULL != n2);
  84
  85   // GNUNET_CONTAINER_heap_walk_get_next: 1 element
  86   n1 = NULL;
  87   n1 = GNUNET_CONTAINER_heap_walk_get_next (myHeap);
  88   GNUNET_assert (NULL != n1);
  89
  90   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
  91   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
  92   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "78", 78);
  93   GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
  94   GNUNET_assert (0 == strcmp ("78", GNUNET_CONTAINER_heap_remove_node (n2)));
  95   GNUNET_assert (1 == GNUNET_CONTAINER_heap_get_size (myHeap));
  96   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
  97
  98   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "15", 5);
  99   GNUNET_CONTAINER_heap_update_cost (n3, 15);
 100   GNUNET_assert (2 == GNUNET_CONTAINER_heap_get_size (myHeap));
 101   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
 102
 103   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
 104   GNUNET_CONTAINER_heap_update_cost (n4, 50);
 105   GNUNET_assert (3 == GNUNET_CONTAINER_heap_get_size (myHeap));
 106   GNUNET_CONTAINER_heap_iterate (myHeap, &iterator_callback, NULL);
 107
 108   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "100", 100);
 109   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "30/200", 30);
 110   GNUNET_assert (5 == GNUNET_CONTAINER_heap_get_size (myHeap));
 111   GNUNET_CONTAINER_heap_remove_node (n5);
 112   r = GNUNET_CONTAINER_heap_remove_root (myHeap);        /* n1 */
 113   GNUNET_assert (NULL != r);
 114   GNUNET_assert (0 == strcmp ("11", r));
 115   GNUNET_CONTAINER_heap_update_cost (n6, 200);
 116   GNUNET_CONTAINER_heap_remove_node (n3);
 117   r = GNUNET_CONTAINER_heap_remove_root (myHeap);        /* n4 */
 118   GNUNET_assert (NULL != r);
 119   GNUNET_assert (0 == strcmp ("50", r));
 120   r = GNUNET_CONTAINER_heap_remove_root (myHeap);        /* n6 */
 121   GNUNET_assert (NULL != r);
 122   GNUNET_assert (0 == strcmp ("30/200", r));
 123   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (myHeap));
 124
 125   GNUNET_CONTAINER_heap_destroy (myHeap);
 126
 127   // My additions to a complete testcase
 128   // Testing a GNUNET_CONTAINER_HEAP_ORDER_MIN
 129   // Testing remove_node
 130
 131   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 132
 133   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 134   GNUNET_CONTAINER_heap_update_cost (n1, 15);
 135
 136   r = GNUNET_CONTAINER_heap_remove_node (n1);
 137   GNUNET_assert (NULL != r);
 138   GNUNET_assert (0 == strcmp ("10", r));
 139
 140   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 141   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 142
 143   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 144   r = GNUNET_CONTAINER_heap_remove_node (n2);
 145   GNUNET_assert (NULL != r);
 146   GNUNET_assert (0 == strcmp ("20", r));
 147   r = GNUNET_CONTAINER_heap_remove_node (n1);
 148   GNUNET_assert (NULL != r);
 149   GNUNET_assert (0 == strcmp ("10", r));
 150
 151   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 152   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 153   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 154
 155   GNUNET_CONTAINER_heap_remove_node (n2);
 156   GNUNET_CONTAINER_heap_remove_node (n1);
 157   r = GNUNET_CONTAINER_heap_remove_root (myHeap);
 158   GNUNET_assert (NULL != r);
 159   GNUNET_assert (0 == strcmp ("30", r));
 160
 161   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 162   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 163   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 164
 165   GNUNET_CONTAINER_heap_remove_node (n2);
 166   GNUNET_CONTAINER_heap_remove_node (n1);
 167   r = GNUNET_CONTAINER_heap_remove_node (n3);
 168   GNUNET_assert (NULL != r);
 169   GNUNET_assert (0 == strcmp ("30", r));
 170
 171   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 172   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 173   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 174
 175   GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
 176   GNUNET_assert (0 ==
 177                  nstrcmp ("10", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 178   GNUNET_assert (0 ==
 179                  nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 180
 181   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 182   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 183   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 184   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
 185   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
 186   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
 187
 188   // Inserting nodes deeper in the tree with lower costs
 189   n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
 190   n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
 191
 192   GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
 193
 194   // Cleaning up...
 195   GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
 196   GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
 197
 198   // Testing heap_walk_get_next
 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   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 204
 205   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
 206   GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
 207   GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
 208   GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
 209   GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
 210
 211   // End Testing remove_node
 212
 213   // Testing a GNUNET_CONTAINER_HEAP_ORDER_MAX
 214   GNUNET_CONTAINER_heap_destroy (myHeap);
 215
 216   myHeap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
 217
 218   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 219   GNUNET_CONTAINER_heap_update_cost (n1, 15);
 220
 221   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
 222
 223   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 224   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 225
 226   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 227   GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
 228   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
 229
 230   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 231   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 232   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 233
 234   GNUNET_CONTAINER_heap_remove_node (n2);
 235   GNUNET_CONTAINER_heap_remove_node (n1);
 236   GNUNET_assert (0 ==
 237                  nstrcmp ("30", GNUNET_CONTAINER_heap_remove_root (myHeap)));
 238
 239   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 240   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 10);
 241   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 10);
 242
 243   GNUNET_CONTAINER_heap_remove_node (n2);
 244   GNUNET_CONTAINER_heap_remove_node (n1);
 245   GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
 246
 247   n1 = GNUNET_CONTAINER_heap_insert (myHeap, "10", 10);
 248   n2 = GNUNET_CONTAINER_heap_insert (myHeap, "20", 20);
 249   n3 = GNUNET_CONTAINER_heap_insert (myHeap, "30", 30);
 250   n4 = GNUNET_CONTAINER_heap_insert (myHeap, "40", 40);
 251   n5 = GNUNET_CONTAINER_heap_insert (myHeap, "50", 50);
 252   n6 = GNUNET_CONTAINER_heap_insert (myHeap, "60", 60);
 253
 254   // Inserting nodes deeper in the tree with lower costs
 255   n7 = GNUNET_CONTAINER_heap_insert (myHeap, "70", 10);
 256   n8 = GNUNET_CONTAINER_heap_insert (myHeap, "80", 10);
 257
 258   GNUNET_assert (0 == nstrcmp ("30", GNUNET_CONTAINER_heap_remove_node (n3)));
 259
 260   // Cleaning up...
 261   GNUNET_assert (0 == nstrcmp ("60", GNUNET_CONTAINER_heap_remove_node (n6)));
 262   GNUNET_assert (0 == nstrcmp ("50", GNUNET_CONTAINER_heap_remove_node (n5)));
 263
 264   // Testing heap_walk_get_next
 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   GNUNET_CONTAINER_heap_walk_get_next (myHeap);
 270
 271   GNUNET_assert (0 == nstrcmp ("10", GNUNET_CONTAINER_heap_remove_node (n1)));
 272   GNUNET_assert (0 == nstrcmp ("20", GNUNET_CONTAINER_heap_remove_node (n2)));
 273   GNUNET_assert (0 == nstrcmp ("40", GNUNET_CONTAINER_heap_remove_node (n4)));
 274   GNUNET_assert (0 == nstrcmp ("70", GNUNET_CONTAINER_heap_remove_node (n7)));
 275   GNUNET_assert (0 == nstrcmp ("80", GNUNET_CONTAINER_heap_remove_node (n8)));
 276
 277   // End Testing remove_node
 278
 279   GNUNET_CONTAINER_heap_destroy (myHeap);
 280
 281   return 0;
 282 }
 283
 284
 285 int
 286 main (int argc, char **argv)
 287 {
 288   GNUNET_log_setup ("test-container-heap", "WARNING", NULL);
 289   return check ();
 290 }
 291
 292
 293 /* end of test_container_heap.c */