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