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