obt/bsearch_unittest.c

   1 #include "obt/unittest_base.h"
   2
   3 #include "obt/bsearch.h"
   4
   5 #include <glib.h>
   6
   7 static void empty() {
   8     TEST_START();
   9
  10     BSEARCH_SETUP();
  11     int* array = NULL;
  12     guint array_size = 0;
  13
  14     /* Search in an empty array. */
  15     BSEARCH(int, array, 0, array_size, 10);
  16     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  17     EXPECT_UINT_EQ(0, BSEARCH_AT());
  18
  19     /* Search in an empty array with a non-zero starting position. */
  20     BSEARCH(int, array, 10, array_size, -10);
  21     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  22     EXPECT_UINT_EQ(10, BSEARCH_AT());
  23
  24     TEST_END();
  25 }
  26
  27 static void single_element() {
  28     TEST_START();
  29
  30     BSEARCH_SETUP();
  31     int array[1];
  32     guint array_size = 1;
  33
  34     /* Search for something smaller than the only element. */
  35     array[0] = 20;
  36     BSEARCH(int, array, 0, array_size, -10);
  37     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  38     EXPECT_UINT_EQ(0, BSEARCH_AT());
  39     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
  40
  41     /* Search for something bigger than the only element. */
  42     array[0] = 20;
  43     BSEARCH(int, array, 0, array_size, 30);
  44     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  45     EXPECT_UINT_EQ(0, BSEARCH_AT());
  46     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
  47
  48     /* Search for something smaller than the only element. */
  49     array[0] = -20;
  50     BSEARCH(int, array, 0, array_size, -30);
  51     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  52     EXPECT_UINT_EQ(0, BSEARCH_AT());
  53     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
  54
  55     /* Search for something bigger than the only element. */
  56     array[0] = -20;
  57     BSEARCH(int, array, 0, array_size, 10);
  58     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  59     EXPECT_UINT_EQ(0, BSEARCH_AT());
  60     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
  61
  62     /* Search for the only element that exists. */
  63     array[0] = -20;
  64     BSEARCH(int, array, 0, array_size, -20);
  65     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
  66     EXPECT_UINT_EQ(0, BSEARCH_AT());
  67     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
  68
  69     TEST_END();
  70 }
  71
  72 static void single_element_nonzero_start() {
  73     TEST_START();
  74
  75     BSEARCH_SETUP();
  76     int array[10];
  77     guint array_start = 9;
  78     guint array_size = 1;
  79
  80     /* Search for something smaller than the only element. */
  81     array[array_start] = 20;
  82     BSEARCH(int, array, array_start, array_size, -10);
  83     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  84     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
  85     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
  86
  87     /* Search for something bigger than the only element. */
  88     array[array_start] = 20;
  89     BSEARCH(int, array, array_start, array_size, 30);
  90     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  91     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
  92     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
  93
  94     /* Search for something smaller than the only element. */
  95     array[array_start] = -20;
  96     BSEARCH(int, array, array_start, array_size, -30);
  97     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
  98     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
  99     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 100
 101     /* Search for something bigger than the only element. */
 102     array[array_start] = -20;
 103     BSEARCH(int, array, array_start, array_size, 10);
 104     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 105     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
 106     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 107
 108     /* Search for the only element that exists. */
 109     array[array_start] = -20;
 110     BSEARCH(int, array, array_start, array_size, -20);
 111     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 112     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
 113     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 114
 115     TEST_END();
 116 }
 117
 118 static void present() {
 119     TEST_START();
 120
 121     BSEARCH_SETUP();
 122     int array[5];
 123     guint array_start = 0;
 124     guint array_size = 5;
 125
 126     array[0] = 10;
 127     array[1] = 12;
 128     array[2] = 14;
 129     array[3] = 16;
 130     array[4] = 18;
 131
 132     /* Search for something that is in the array. */
 133
 134     BSEARCH(int, array, array_start, array_size, 10);
 135     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 136     EXPECT_UINT_EQ(0, BSEARCH_AT());
 137     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 138
 139     BSEARCH(int, array, array_start, array_size, 12);
 140     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 141     EXPECT_UINT_EQ(1, BSEARCH_AT());
 142     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 143
 144     BSEARCH(int, array, array_start, array_size, 14);
 145     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 146     EXPECT_UINT_EQ(2, BSEARCH_AT());
 147     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 148
 149     BSEARCH(int, array, array_start, array_size, 16);
 150     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 151     EXPECT_UINT_EQ(3, BSEARCH_AT());
 152     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 153
 154     BSEARCH(int, array, array_start, array_size, 18);
 155     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 156     EXPECT_UINT_EQ(4, BSEARCH_AT());
 157     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 158
 159     TEST_END();
 160 }
 161
 162 static void present_nonzero_start() {
 163     TEST_START();
 164
 165     BSEARCH_SETUP();
 166     int array[5];
 167     guint array_start = 2;
 168     guint array_size = 3;
 169
 170     array[0] = 10;
 171     array[1] = 12;
 172     array[2] = 14;
 173     array[3] = 16;
 174     array[4] = 18;
 175
 176     /* Search for something that is in the array. */
 177
 178     BSEARCH(int, array, array_start, array_size, 10);
 179     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 180     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
 181     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 182
 183     BSEARCH(int, array, array_start, array_size, 12);
 184     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 185     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
 186     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 187
 188     BSEARCH(int, array, array_start, array_size, 14);
 189     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 190     EXPECT_UINT_EQ(2, BSEARCH_AT());
 191     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 192
 193     BSEARCH(int, array, array_start, array_size, 16);
 194     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 195     EXPECT_UINT_EQ(3, BSEARCH_AT());
 196     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 197
 198     BSEARCH(int, array, array_start, array_size, 18);
 199     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
 200     EXPECT_UINT_EQ(4, BSEARCH_AT());
 201     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 202
 203     TEST_END();
 204 }
 205
 206 static void missing() {
 207     TEST_START();
 208
 209     BSEARCH_SETUP();
 210     int array[5];
 211     guint array_start = 0;
 212     guint array_size = 5;
 213
 214     array[0] = 10;
 215     array[1] = 12;
 216     array[2] = 14;
 217     array[3] = 16;
 218     array[4] = 18;
 219
 220     /* Search for something that is _not_ in the array. */
 221
 222     BSEARCH(int, array, array_start, array_size, 9);
 223     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 224     EXPECT_UINT_EQ(0, BSEARCH_AT());
 225     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 226
 227     BSEARCH(int, array, array_start, array_size, 11);
 228     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 229     EXPECT_UINT_EQ(0, BSEARCH_AT());
 230     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 231
 232     BSEARCH(int, array, array_start, array_size, 13);
 233     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 234     EXPECT_UINT_EQ(1, BSEARCH_AT());
 235     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 236
 237     BSEARCH(int, array, array_start, array_size, 15);
 238     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 239     EXPECT_UINT_EQ(2, BSEARCH_AT());
 240     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 241
 242     BSEARCH(int, array, array_start, array_size, 17);
 243     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 244     EXPECT_UINT_EQ(3, BSEARCH_AT());
 245     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 246
 247     BSEARCH(int, array, array_start, array_size, 19);
 248     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 249     EXPECT_UINT_EQ(4, BSEARCH_AT());
 250     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 251
 252     TEST_END();
 253 }
 254
 255 static void missing_nonzero_start() {
 256     TEST_START();
 257
 258     BSEARCH_SETUP();
 259     int array[5];
 260     guint array_start = 2;
 261     guint array_size = 3;
 262
 263     array[0] = 10;
 264     array[1] = 12;
 265     array[2] = 14;
 266     array[3] = 16;
 267     array[4] = 18;
 268
 269     /* Search for something that is _not_ in the array. */
 270
 271     BSEARCH(int, array, array_start, array_size, 9);
 272     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 273     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
 274     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 275
 276     BSEARCH(int, array, array_start, array_size, 11);
 277     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 278     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
 279     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 280
 281     BSEARCH(int, array, array_start, array_size, 13);
 282     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 283     EXPECT_UINT_EQ(array_start, BSEARCH_AT());
 284     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
 285
 286     BSEARCH(int, array, array_start, array_size, 15);
 287     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 288     EXPECT_UINT_EQ(2, BSEARCH_AT());
 289     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 290
 291     BSEARCH(int, array, array_start, array_size, 17);
 292     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 293     EXPECT_UINT_EQ(3, BSEARCH_AT());
 294     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 295
 296     BSEARCH(int, array, array_start, array_size, 19);
 297     EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
 298     EXPECT_UINT_EQ(4, BSEARCH_AT());
 299     EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
 300
 301     TEST_END();
 302 }
 303
 304 void run_bsearch_unittest() {
 305     unittest_start_suite("bsearch");
 306
 307     empty();
 308     single_element();
 309     single_element_nonzero_start();
 310     present();
 311     present_nonzero_start();
 312     missing();
 313     missing_nonzero_start();
 314
 315     unittest_end_suite();
 316 }