LCOV - code coverage report
Current view: top level - lib/util/tests - binsearch.c (source / functions) Hit Total Coverage
Test: coverage report for master 2b515b7d Lines: 61 64 95.3 %
Date: 2024-02-28 12:06:22 Functions: 3 5 60.0 %

          Line data    Source code
       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 "torture/torture.h"
      27             : #include "torture/local/proto.h"
      28             : 
      29          33 : static int int_cmp(int a, int b)
      30             : {
      31          33 :         return a - b;
      32             : }
      33             : 
      34         132 : static int int_cmp_p(int a, int *b)
      35             : {
      36         132 :         return a - *b;
      37             : }
      38             : 
      39           1 : static bool test_binsearch_v(struct torture_context *tctx)
      40             : {
      41           1 :         int array[] = { -11, -7, 0, 1, 723, 1000000};
      42           1 :         int misses[] = { -121, 17, -10, 10, -1, -723, 1000002};
      43           1 :         int i;
      44           1 :         int *result = NULL;
      45             : 
      46           8 :         for (i = 0; i < ARRAY_SIZE(misses); i++) {
      47          26 :                 BINARY_ARRAY_SEARCH_V(array, ARRAY_SIZE(array),
      48             :                                       misses[i], int_cmp, result);
      49           7 :                 torture_comment(tctx, "looking for misses[%d] == %d\n", i, misses[i]);
      50           7 :                 torture_assert(tctx, result == NULL, "failed to miss");
      51             :         }
      52             : 
      53           7 :         for (i = 0; i < ARRAY_SIZE(array); i++) {
      54          14 :                 BINARY_ARRAY_SEARCH_V(array, ARRAY_SIZE(array),
      55             :                                       array[i], int_cmp, result);
      56           6 :                 torture_comment(tctx, "looking for array[%d] == %d, %p; got %p\n",
      57             :                                 i, array[i], &array[i], result);
      58           6 :                 torture_assert(tctx, result == &array[i],
      59             :                                "failed to find element");
      60             :         }
      61           0 :         return true;
      62             : }
      63             : 
      64           1 : static bool test_binsearch_gte(struct torture_context *tctx)
      65             : {
      66           1 :         int array[] = { -11, -7, -7, -7, -1, 0, 0, 1, 723, 723, 723,
      67             :                         724, 724, 10000};
      68           1 :         size_t a_len = ARRAY_SIZE(array);
      69           1 :         int targets[] = { -121, -8, -7, -6, 17, -10, 10, -1, 723,
      70             :                           724, 725, 10002, 10000, 0, -11, 1, 11};
      71           1 :         int i, j, target;
      72           1 :         int *result = NULL, *next = NULL;
      73             : 
      74          18 :         for (i = 0; i < ARRAY_SIZE(targets); i++) {
      75          17 :                 target = targets[i];
      76          17 :                 torture_comment(tctx, "looking for targets[%d] %d\n",
      77             :                                 i, target);
      78             : 
      79         100 :                 BINARY_ARRAY_SEARCH_GTE(array, a_len, target,
      80             :                                         int_cmp_p, result, next);
      81             : 
      82          17 :                 if (result == NULL) {
      83             :                         /* we think there is no exact match */
      84         135 :                         for (j = 0; j < a_len; j++) {
      85         126 :                                 if (target == array[j]) {
      86           0 :                                         torture_comment(tctx,
      87             :                                                         "failed to find %d\n",
      88             :                                                         targets[i]);
      89         126 :                                         torture_fail(tctx,
      90             :                                                      "result is wrongly NULL");
      91             :                                 }
      92             :                         }
      93           9 :                         if (next != NULL) {
      94           8 :                                 torture_assert(tctx, (next >= array &&
      95             :                                                       next < array + a_len),
      96             :                                                "next is out of bounds");
      97             : 
      98           8 :                                 torture_assert(tctx, *next > target,
      99             :                                                "next <= target");
     100           8 :                                 if (target <= array[0]) {
     101           1 :                                         torture_assert(tctx, next == array,
     102             :                                                        "search before start failed");
     103             :                                 }
     104           8 :                                 if (next != array) {
     105           7 :                                         torture_assert(tctx, next[-1] < target,
     106             :                                                        "next[-1] >= target");
     107             :                                 }
     108             :                         }
     109             :                         else {
     110           1 :                                 torture_assert(tctx, array[a_len - 1] < target,
     111             :                                                "next was not found\n");
     112             :                         }
     113             :                 } else {
     114             :                         /* we think we found an exact match */
     115           8 :                         torture_assert(tctx, *result == target,
     116             :                                        "result has wrong value");
     117             : 
     118           8 :                         torture_assert(tctx, (result >= array &&
     119             :                                               result < array + a_len),
     120             :                                        "result is out of bounds!");
     121             : 
     122           8 :                         torture_assert(tctx, next == NULL,
     123             :                                        "next should be NULL on exact match\n");
     124           8 :                         if (result != array) {
     125           7 :                                 torture_assert(tctx, result[-1] != target,
     126             :                                                "didn't find first target\n");
     127             :                         }
     128             :                 }
     129          17 :                 if (target >= array[a_len - 1]) {
     130          17 :                         torture_assert(tctx, next == NULL,
     131             :                                        "next is not NULL at array end\n");
     132             :                 }
     133             :         }
     134             : 
     135             :         /* try again, with result and next the same pointer */
     136          18 :         for (i = 0; i < ARRAY_SIZE(targets); i++) {
     137          17 :                 target = targets[i];
     138          17 :                 torture_comment(tctx, "looking for targets[%d] %d\n",
     139             :                                 i, target);
     140             : 
     141         100 :                 BINARY_ARRAY_SEARCH_GTE(array, a_len, target,
     142             :                                         int_cmp_p, result, result);
     143             : 
     144          17 :                 if (result == NULL) {
     145             :                         /* we think the target is greater than all elements */
     146           1 :                         torture_assert(tctx, array[a_len - 1] < target,
     147             :                                        "element >= target not found\n");
     148             :                 } else {
     149             :                         /* we think an element is >= target */
     150          16 :                         torture_assert(tctx, *result >= target,
     151             :                                        "result has wrong value");
     152             : 
     153          16 :                         torture_assert(tctx, (result >= array &&
     154             :                                               result < array + a_len),
     155             :                                        "result is out of bounds!");
     156             : 
     157          16 :                         if (result != array) {
     158          17 :                                 torture_assert(tctx, result[-1] < target,
     159             :                                                "didn't find first target\n");
     160             :                         }
     161             :                 }
     162             :         }
     163             : 
     164           0 :         return true;
     165             : }
     166             : 
     167        2379 : struct torture_suite *torture_local_util_binsearch(TALLOC_CTX *mem_ctx)
     168             : {
     169        2379 :         struct torture_suite *suite = torture_suite_create(mem_ctx, "binsearch");
     170        2379 :         torture_suite_add_simple_test(suite, "binsearch_v", test_binsearch_v);
     171        2379 :         torture_suite_add_simple_test(suite, "binsearch_gte", test_binsearch_gte);
     172        2379 :         return suite;
     173             : }

Generated by: LCOV version 1.14