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