lib/util/tests/binsearch.c

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    Tests for binsearch.h macros.
   5
   6    Copyright Catalyst IT 2016.
   7
   8    Written by Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
   9
  10    This program is free software; you can redistribute it and/or modify
  11    it under the terms of the GNU General Public License as published by
  12    the Free Software Foundation; either version 3 of the License, or
  13    (at your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18    GNU General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 #include "includes.h"
  25 #include "lib/util/binsearch.h"
  26 #include "lib/util/tsort.h"
  27 #include "torture/torture.h"
  28 #include "torture/local/proto.h"
  29
  30 static int int_cmp(int a, int b)
  31 {
  32         return NUMERIC_CMP(a, b);
  33 }
  34
  35 static int int_cmp_p(int a, int *b)
  36 {
  37         int _b = *b;
  38         return NUMERIC_CMP(a, _b);
  39 }
  40
  41 static bool test_binsearch_v(struct torture_context *tctx)
  42 {
  43         int array[] = { -11, -7, 0, 1, 723, 1000000};
  44         int misses[] = { -121, 17, -10, 10, -1, -723, 1000002};
  45         int i;
  46         int *result = NULL;
  47
  48         for (i = 0; i < ARRAY_SIZE(misses); i++) {
  49                 BINARY_ARRAY_SEARCH_V(array, ARRAY_SIZE(array),
  50                                       misses[i], int_cmp, result);
  51                 torture_comment(tctx, "looking for misses[%d] == %d\n", i, misses[i]);
  52                 torture_assert(tctx, result == NULL, "failed to miss");
  53         }
  54
  55         for (i = 0; i < ARRAY_SIZE(array); i++) {
  56                 BINARY_ARRAY_SEARCH_V(array, ARRAY_SIZE(array),
  57                                       array[i], int_cmp, result);
  58                 torture_comment(tctx, "looking for array[%d] == %d, %p; got %p\n",
  59                                 i, array[i], &array[i], result);
  60                 torture_assert(tctx, result == &array[i],
  61                                "failed to find element");
  62         }
  63         return true;
  64 }
  65
  66 static bool test_binsearch_gte(struct torture_context *tctx)
  67 {
  68         int array[] = { -11, -7, -7, -7, -1, 0, 0, 1, 723, 723, 723,
  69                         724, 724, 10000};
  70         size_t a_len = ARRAY_SIZE(array);
  71         int targets[] = { -121, -8, -7, -6, 17, -10, 10, -1, 723,
  72                           724, 725, 10002, 10000, 0, -11, 1, 11};
  73         int i, j, target;
  74         int *result = NULL, *next = NULL;
  75
  76         for (i = 0; i < ARRAY_SIZE(targets); i++) {
  77                 target = targets[i];
  78                 torture_comment(tctx, "looking for targets[%d] %d\n",
  79                                 i, target);
  80
  81                 BINARY_ARRAY_SEARCH_GTE(array, a_len, target,
  82                                         int_cmp_p, result, next);
  83
  84                 if (result == NULL) {
  85                         /* we think there is no exact match */
  86                         for (j = 0; j < a_len; j++) {
  87                                 if (target == array[j]) {
  88                                         torture_comment(tctx,
  89                                                         "failed to find %d\n",
  90                                                         targets[i]);
  91                                         torture_fail(tctx,
  92                                                      "result is wrongly NULL");
  93                                 }
  94                         }
  95                         if (next != NULL) {
  96                                 torture_assert(tctx, (next >= array &&
  97                                                       next < array + a_len),
  98                                                "next is out of bounds");
  99
 100                                 torture_assert(tctx, *next > target,
 101                                                "next <= target");
 102                                 if (target <= array[0]) {
 103                                         torture_assert(tctx, next == array,
 104                                                        "search before start failed");
 105                                 }
 106                                 if (next != array) {
 107                                         torture_assert(tctx, next[-1] < target,
 108                                                        "next[-1] >= target");
 109                                 }
 110                         }
 111                         else {
 112                                 torture_assert(tctx, array[a_len - 1] < target,
 113                                                "next was not found\n");
 114                         }
 115                 } else {
 116                         /* we think we found an exact match */
 117                         torture_assert(tctx, *result == target,
 118                                        "result has wrong value");
 119
 120                         torture_assert(tctx, (result >= array &&
 121                                               result < array + a_len),
 122                                        "result is out of bounds!");
 123
 124                         torture_assert(tctx, next == NULL,
 125                                        "next should be NULL on exact match\n");
 126                         if (result != array) {
 127                                 torture_assert(tctx, result[-1] != target,
 128                                                "didn't find first target\n");
 129                         }
 130                 }
 131                 if (target >= array[a_len - 1]) {
 132                         torture_assert(tctx, next == NULL,
 133                                        "next is not NULL at array end\n");
 134                 }
 135         }
 136
 137         /* try again, with result and next the same pointer */
 138         for (i = 0; i < ARRAY_SIZE(targets); i++) {
 139                 target = targets[i];
 140                 torture_comment(tctx, "looking for targets[%d] %d\n",
 141                                 i, target);
 142
 143                 BINARY_ARRAY_SEARCH_GTE(array, a_len, target,
 144                                         int_cmp_p, result, result);
 145
 146                 if (result == NULL) {
 147                         /* we think the target is greater than all elements */
 148                         torture_assert(tctx, array[a_len - 1] < target,
 149                                        "element >= target not found\n");
 150                 } else {
 151                         /* we think an element is >= target */
 152                         torture_assert(tctx, *result >= target,
 153                                        "result has wrong value");
 154
 155                         torture_assert(tctx, (result >= array &&
 156                                               result < array + a_len),
 157                                        "result is out of bounds!");
 158
 159                         if (result != array) {
 160                                 torture_assert(tctx, result[-1] < target,
 161                                                "didn't find first target\n");
 162                         }
 163                 }
 164         }
 165
 166         return true;
 167 }
 168
 169 struct torture_suite *torture_local_util_binsearch(TALLOC_CTX *mem_ctx)
 170 {
 171         struct torture_suite *suite = torture_suite_create(mem_ctx, "binsearch");
 172         torture_suite_add_simple_test(suite, "binsearch_v", test_binsearch_v);
 173         torture_suite_add_simple_test(suite, "binsearch_gte", test_binsearch_gte);
 174         return suite;
 175 }